/*
 *                 Sun Public License Notice
 * 
 * The contents of this file are subject to the Sun Public License
 * Version 1.0 (the "License"). You may not use this file except in
 * compliance with the License. A copy of the License is available at
 * http://www.sun.com/
 * 
 * The Original Code is NetBeans. The Initial Developer of the Original
 * Code is Sun Microsystems, Inc. Portions Copyright 1997-2001 Sun
 * Microsystems, Inc. All Rights Reserved.
 */
package org.netbeans.mdr.persistence.btreeimpl.btreeindex;

import org.netbeans.mdr.persistence.*;
import java.io.*;
import java.util.Arrays;

/**
 * Implementation of a BtreePage with fixed key length and fixed data length that
 * are stored in compressed form if all the stored keys or data prefixes are
 * strings of zeros (these prefixes are excluded then).
 */
public class ShrinkablePage extends BtreePage {
    
    private static boolean debug = false;
    
    private static final byte KEYS_SHRINKED_MASK = 1;
    private static final byte DATA_SHRINKED_MASK = 2;
    
    // length of the key prefix relavant to the page compression
    static final int KEY_ZERO_PREFIX_LENGTH = MOFID.LENGTH / 2;
    // length of the data prefix relavant to the page compression
    static final int DATA_ZERO_PREFIX_LENGTH = MOFID.LENGTH / 2;
    
    // length of the key - determined by key info
    int	keyLengthX;
    // length of data - determined by data info
    int dataLengthX;
    
    // flag indicating if the keys are stored in the compressed form
    boolean keysShrinked;
    // flag indicating if the data are stored in the compressed form
    boolean dataShrinked;
    // true if keys are shrinkable
    boolean keysShrinkable;
    // true if data are shrinkable
    boolean dataShrinkable;
    
    // number of bytes currently used to store a key
    int currentKeyLength;
    // number of bytes currently used to store data
    int currentDataLength;
    
    /*
    // number of keys with non-zero prefix stored in the page
    int longKeysCount;
    // number of data with non-zero prefix stored in the page
    int longDataCount;
     */
    
    // flag indicating if an operation requires key parts of entries to expanded (from shrinked form)
    boolean expandKeys;
    // flag indicating if an operation requires data parts of entries to expanded (from shrinked form)
    boolean expandData;
    
    /**
     * Initialize a newly-instantiated or recycled ShrinkablePage. Note that the
     * isNew parameter pertains to whether a new page is being added to the
     * btree, not to whether this BtreePage object is new or recycled.
     *
     * @param	btree		btree to which this page belongs
     * @param	pageId		page ID in byte array
     * @param	pageBuffer	page buffer
     * @param	isNew		is this page new to the btree
     */
    public void init(Btree btree, byte[] pageId, byte[] pageBuffer, 
  				boolean isNew) throws StorageException {

        if (initialized) {
            /* This page was found in cache and doesn't need initialization */
            return;
        }
        
        super.init(btree, pageId, pageBuffer, isNew);                        
        
        headerLength++;
        
	keyLengthX = btree.keyInfo.getLength();
        dataLengthX = btree.dataInfo.getLength();
        
        keysShrinkable = btree.keyInfo instanceof MOFIDInfo;
        dataShrinkable = btree.dataInfo instanceof MOFIDInfo;        
                        
        if (isNew) {
            keysShrinked = keysShrinkable;
            dataShrinked = dataShrinkable;            
            freeStart++;
        } else {
            keysShrinked = (pageBuffer [headerLength - 1] & KEYS_SHRINKED_MASK) > 0;
            dataShrinked = (pageBuffer [headerLength - 1] & DATA_SHRINKED_MASK) > 0;
        }
        
        currentKeyLength = keysShrinked ? MOFID.LENGTH / 2 : keyLengthX;
        currentDataLength = dataShrinked ? MOFID.LENGTH / 2 : dataLengthX;                
        
        /*
        longKeysCount = 0;
        longDataCount = 0;
         */
    }

    /**
     * Returns the number of entries currently on this page.
     *
     * @return	number of entries on this page
     */
    int numEntries() {        
        return (freeStart - headerLength)/(currentKeyLength + currentDataLength);
    }

    /**
     * Returns the offset in the page where a specified entry's key is located.
     *
     * @param entryNum	entry number
     *
     * @return	offset of entryNum's key
     */
    int keyOffset(int entryNum) {
        return headerLength + (entryNum * (currentKeyLength + currentDataLength));
    }

    /**
     * Returns the length of a specified entry's key.
     *
     * @param entryNum	entry number
     *
     * @return	length of entryNum's key
     */
    int keyLength(int entryNum) {
        return keyLengthX;
    }
    
    /**
     * Returns the data value for the specified entry.
     *
     * @param entryNum	entry number
     *
     * @return	new byte array containing the data at entryNum
     */
    byte[] getData(int entryNum) {
        byte[] data = new byte[dataLengthX];
        if (dataShrinked) {
            System.arraycopy(pageBuffer, keyOffset(entryNum) + currentKeyLength,
				data, DATA_ZERO_PREFIX_LENGTH, currentDataLength);
            Arrays.fill(data, 0, DATA_ZERO_PREFIX_LENGTH, (byte) 0);
        } else {
            System.arraycopy(pageBuffer, keyOffset(entryNum) + currentKeyLength,
				data, 0, currentDataLength);
        }
        
        if (debug) {
            System.out.println("getData called: " + entryNum);
        }
        
	return data;
    }

    /**
     * Returns the key for the specified entry.
     *
     * @param entryNum	entry number
     *
     * @return	new byte array containing the key at entryNum
     */
    byte[] getKey(int entryNum) {
        byte[] key = new byte[keyLengthX];
        if (keysShrinked) {
            System.arraycopy(pageBuffer, keyOffset(entryNum), key, 
                    KEY_ZERO_PREFIX_LENGTH, currentKeyLength);
            Arrays.fill(key, 0, KEY_ZERO_PREFIX_LENGTH, (byte) 0);
        } else {
            System.arraycopy(pageBuffer, keyOffset(entryNum), key, 0, currentKeyLength);
        }
        
        if (debug) {
            System.out.print("getKey: ");
            for (int x = 0; x < key.length; x++)
                System.out.print(key[x] + ":");
            System.out.println("");
        }
	return key;
    }

    protected byte compare(byte[] key, int entryNum) {

        if (!isLeaf() && (entryNum == 0) 
		&& pageSource.isNoPage(previousPage)) {
	    return EntryTypeInfo.GREATER;
	}
        
        int index = 0;
        if (keysShrinkable && keysShrinked) {
            for (; index < KEY_ZERO_PREFIX_LENGTH; index++) {
                if (key [index] < 0) {
                    return EntryTypeInfo.LESS;
                } else if (key [index] > 0) {
                    return EntryTypeInfo.GREATER;
                }
            } // for
        } // if
        int offset = keyOffset (entryNum);
	for (; index < key.length; index++, offset++) {
	    if (key[index] < pageBuffer[offset]) {
	        return EntryTypeInfo.LESS;
	    } else if (key[index] > pageBuffer[offset]) {
	        return EntryTypeInfo.GREATER;
	    } 
        }
        return EntryTypeInfo.EQUAL;
    }
    
    protected byte compareData(byte[] data, int entryNum) {

	int index = 0;
        if (dataShrinkable && dataShrinked) {
            for (; index < DATA_ZERO_PREFIX_LENGTH; index++) {
                if (data [index] < 0) {
                    return EntryTypeInfo.LESS;
                } else if (data [index] > 0) {
                    return EntryTypeInfo.GREATER;
                }
            } // for
        } // if
        int offset = keyOffset (entryNum) + currentKeyLength;
	for (; index < data.length; index++, offset++) {
	    if (data[index] < pageBuffer[offset]) {
	        return EntryTypeInfo.LESS;
	    } else if (data[index] > pageBuffer[offset]) {
	        return EntryTypeInfo.GREATER;
	    } 
        }
        return EntryTypeInfo.EQUAL;
    }
    
    /*
     * Inserts an entry at the specified location.
     *
     * @param entry 	BtreeEntry to be inserted
     * @param entryNum 	location where entry is to be inserted
     *
     * @return	If a split occurred, an entry to be inserted in this page's
     *		parent is returned; otherwise null is returned.
     */
    BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
    				throws StorageException {                                        
                                        
        if (debug) {
            System.out.print("insert called: ");            
            for (int x = 0; x < entry.key.length; x++) {
                System.out.print(entry.key [x]);
            }
            System.out.println("");
        }
        
        if (debug) {                            
            for (int x = 0; x < entry.key.length; x++)
                System.out.print(entry.key[x] + ":");
            System.out.print("  ");
            for (int x = 0; x < entry.data.length; x++)
                System.out.print(entry.data[x] + ":");
            System.out.println();
        }
                                    
        int offset;
        int space = 0;
        
        expandKeys = false;
        expandData = false;

        pageSource.dirtyPage(this);

        if (keysShrinked && hasLongKey (entry)) {
            expandKeys = true;
            space += numEntries () * KEY_ZERO_PREFIX_LENGTH + entry.key.length;
        }
        if (dataShrinked && hasLongData (entry)) {
            expandData = true;
            space += numEntries () * DATA_ZERO_PREFIX_LENGTH + entry.data.length;
        }
        if (!expandKeys)
            space += currentKeyLength;
        if (!expandData)
            space += currentDataLength;

        if (btree.pageSize - freeStart - keyLengthX - dataLengthX >= space) {
	    insertHere(entry, entryNum, resultPosition);            
	    return null;
	} else {            
	    BtreeEntry result = split(entry, entryNum, resultPosition);            
            return result;
	}
    }

    /*
     * Replaces the entry at the specified location with the passed-in entry.     
     *
     * @param entry BtreeEntry to be inserted
     * @param entryNum location where entry is to be inserted
     *
     * @return
     */
    BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult position) throws StorageException {

        if (debug) {
            System.out.println("replace called");
        }
        
        pageSource.dirtyPage(this);

        if (dataShrinked && hasLongData (entry)) {            
            int space = numEntries () * (currentKeyLength + dataLengthX);
            if (btree.pageSize - freeStart - keyLengthX - dataLengthX < space) {
                delete (entryNum, entryNum);
                return insert (entry, entryNum, position);                
            } else {
                expandData ();
            }
        }
        
        int offset = keyOffset(entryNum) + currentKeyLength;
        int dataStart = dataShrinked ? DATA_ZERO_PREFIX_LENGTH : 0;
	System.arraycopy(entry.data, dataStart, pageBuffer, offset, currentDataLength);                
        
	return null;
    }
    
    private void insertHere(BtreeEntry entry, int entryNum, SearchResult resultPosition) {

        if (debug) {
            //if (expandKeys || expandData) {
                dump ();
                dumpBuffer ();
            //}
        }    
        
        int offset;
        if (expandKeys)
            expandKeys ();
        if (expandData)
            expandData ();
        
	offset = keyOffset(entryNum);
	if (offset != freeStart) {
	    /* Shift entries down to make room for this one */
	    System.arraycopy(pageBuffer, offset, 
		    pageBuffer, offset + (currentKeyLength + currentDataLength),
		    freeStart - offset);
	}
        copyEntry (offset, entry);	
	freeStart += currentKeyLength + currentDataLength;
        
        if (resultPosition != null) {
            resultPosition.entryNum = entryNum;
            resultPosition.matched = true;
            resultPosition.page = this;
            resultPosition.skipCount = 0;
        }

        if (debug) {
            //if ((expandKeys || expandData)) {         
                //System.out.print("insert called: ");            
                for (int x = 0; x < entry.key.length; x++) {
                    System.out.print(entry.key [x]);
                }
                System.out.println("");
                dump ();
                dumpBuffer ();
            //}
        }
        
    }

    /**
     * Deletes an entry or range of entries from this page.
     *
     * @param	first	entry number of first entry to be deleted
     * @param	last	entry number of last entry to be deleted
     */
    void delete(int firstEntry, int lastEntry) throws StorageException {
        int startOffset, endOffset;

        if (debug) {
            System.out.println("delete called: " + firstEntry + " " + lastEntry);
        }
        
	pageSource.dirtyPage(this);

	startOffset = keyOffset(firstEntry);
	endOffset = keyOffset(lastEntry+1);
	if (freeStart != endOffset) {
	    System.arraycopy(pageBuffer, endOffset, pageBuffer, startOffset,
				freeStart - endOffset);
	}
	freeStart -= endOffset - startOffset;
    }

    /**
     * Splits the entries on the current page between two pages, and inserts
     * an entry into its correct location on one of those pages. The left
     * page may be this page or it may be a different page.  The right page is
     * always a different page from this.
     *
     * @param	left	left page to move entries to (may be this page)
     * @param	right	right page to move entries to
     * @param	entry	BtreeEntry to be inserted 
     * @param	newEntryNum insert location relative to the current page
     *
     * @return	new byte array containing first key on right page
     */
    byte[] splitEntries(BtreePage leftPage, BtreePage rightPage, BtreeEntry entry,
    			int entryNum, SearchResult resultPosition) { 
    
	int 	entryLength;
	int 	offset;
	int 	midpoint;
        int     half;
	int 	copyLength;
	boolean insertLeft;
	byte[]	rightKey;                
    
        if (debug) {
            System.out.println("Split entries called.");
        }
        
        ShrinkablePage left = (ShrinkablePage) leftPage;
        ShrinkablePage right = (ShrinkablePage) rightPage;
        
        copyState (right);
        if (left != this)
            copyState (left);
        
	offset = keyOffset(entryNum);
	entryLength = currentKeyLength + currentDataLength;
        half = numEntries()/2;
	midpoint = headerLength + half*entryLength;
	insertLeft = offset < midpoint;

	// Move second half of entries to right page.
	if (insertLeft) {
	    copyLength = this.freeStart - midpoint;
	} else {
	    // First just copy entries up to the insert point
	    copyLength = offset - midpoint;
	}
        
        // record position of inserted entry
        if (resultPosition != null) {
            resultPosition.matched = true;
            resultPosition.skipCount = 0;
            if (insertLeft) {
                resultPosition.page = left;
                resultPosition.entryNum = entryNum;
            } else {
                resultPosition.page = right;
                resultPosition.entryNum = entryNum - half;
            }
        }
        
	if (copyLength > 0) {
	    System.arraycopy(this.pageBuffer, midpoint, right.pageBuffer, 
			right.freeStart, copyLength);
	    right.freeStart += copyLength;
	}
	if (!insertLeft) {
	    // System.arraycopy(entry.key, 0, right.pageBuffer, right.freeStart, currentKeyLength);
	    right.freeStart += currentKeyLength;
	    // System.arraycopy(entry.data, 0, right.pageBuffer, right.freeStart, currentDataLength);
	    right.freeStart += currentDataLength;
	    if (this.freeStart != offset) {
	        System.arraycopy(this.pageBuffer, offset, right.pageBuffer, 
			right.freeStart, this.freeStart - offset);
	        right.freeStart += this.freeStart - offset;
	    }
            if (expandKeys)
                right.expandKeys ();
            if (expandData)
                right.expandData ();
            right.copyEntry (right.keyOffset (entryNum - half), entry);
	}
	
	// Move first half of entries to left page, if left page is new.
	// Either way, insert the new entry if it belongs here.
	if (left != this) {
	    if (insertLeft) {
		copyLength = offset - headerLength;
	    } else {
		copyLength = midpoint - headerLength;
	    } 
	    if (copyLength > 0) {
	        System.arraycopy(this.pageBuffer, headerLength, 
				left.pageBuffer, left.freeStart, copyLength);
	    }
	}

	if (insertLeft) {
	    if (midpoint != offset) {
	        System.arraycopy(this.pageBuffer, offset, left.pageBuffer, 
			offset+entryLength, midpoint - offset);
	    }
            left.freeStart = midpoint + entryLength;
            if (expandKeys)
                left.expandKeys ();
            if (expandData)
                left.expandData ();
            left.copyEntry (keyOffset (entryNum), entry);
	    // System.arraycopy(entry.key, 0, left.pageBuffer, offset, keyLength);
	    // System.arraycopy(entry.data, 0, left.pageBuffer, offset + keyLength, dataLength);
	} else {
	    left.freeStart = midpoint;
	}
	if (left != this) {
	    // All entries were moved off of this page
	    this.freeStart = headerLength;            
	}
        /*
	rightKey = new byte[keyLength];
	System.arraycopy(right.pageBuffer, headerLength, rightKey, 0, keyLength);
	return rightKey;
         */
        
        int entNum = insertLeft ? entryNum : entryNum - half;
        BtreePage pg = insertLeft ? left : right;
        
        /*
        try {            
            System.out.println("============");            
            for (int x = 0; x < entry.key.length; x++)
                System.out.print(entry.key[x]);
            System.out.print("  ");
            for (int x = 0; x < entry.data.length; x++)
                System.out.print(entry.data[x]);
            System.out.println();
            
            pg.getKey (entNum);
            pg.getData (entNum);
            System.out.println("============");
        } catch (Exception e) {
        }
        */
        
        // System.out.println("split done: " + left.numEntries () + " " + right.numEntries ());
        
        return right.getKey (0);
    }
    
    public void store() {

	super.store();

        byte val = 0;	
        if (keysShrinked) {
            val += KEYS_SHRINKED_MASK;
        }
        if (dataShrinked) {
            val += DATA_SHRINKED_MASK;
        }
        pageBuffer [headerLength - 1] = val;
    }
    
    // helper methods ...........................................................
    
    /**
     * @return true if the entry's key prefix does not consist of 0's
     */
    private boolean hasLongKey (BtreeEntry entry) {
        for (int x = 0; x < KEY_ZERO_PREFIX_LENGTH; x++) {
            if (entry.key [x] != 0)
                return true;
        } // for
        return false;
    }
    
    /**
     * @return true if the entry's data prefix does not consist of 0's
     */
    private boolean hasLongData (BtreeEntry entry) {
        for (int x = 0; x < KEY_ZERO_PREFIX_LENGTH; x++) {
            if (entry.data [x] != 0)
                return true;
        } // for
        return false;
    }
    
    void expandKeys () {
        if (debug) {
            System.out.println("expand keys called");
            dump ();
        }
        
        int numEntries = numEntries ();
        int length = numEntries * (currentKeyLength + currentDataLength);
        byte [] tempBuffer = new byte [length];
        System.arraycopy (pageBuffer, headerLength, tempBuffer, 0, length);
        for (int i = 0; i < numEntries; i++) {
            int index = headerLength + i*(keyLengthX + currentDataLength);
            Arrays.fill (pageBuffer, index, 
                index + KEY_ZERO_PREFIX_LENGTH, (byte) 0);
            System.arraycopy (tempBuffer, i*(currentKeyLength + currentDataLength), pageBuffer, 
                KEY_ZERO_PREFIX_LENGTH + index, 
                currentKeyLength + currentDataLength);
        }
        freeStart += numEntries * KEY_ZERO_PREFIX_LENGTH;
        currentKeyLength = keyLengthX;
        keysShrinked = false;
        
        if (debug) {
            dump ();            
        }
    }
    
    void expandData () {
        if (debug) {
            System.out.println("expand data called");
        }
        
        int numEntries = numEntries ();
        int length = numEntries * (currentKeyLength + currentDataLength);
        byte [] tempBuffer = new byte [length];
        System.arraycopy (pageBuffer, headerLength, tempBuffer, 0, length);
        for (int i = 0; i < numEntries; i++) {
            int index = headerLength + currentKeyLength + i*(currentKeyLength + dataLengthX);
            System.arraycopy (tempBuffer, 
                i*(currentKeyLength + currentDataLength), 
                pageBuffer, 
                headerLength + i*(keyLengthX + currentDataLength), currentKeyLength);
            Arrays.fill (pageBuffer, 
                index, 
                index + DATA_ZERO_PREFIX_LENGTH, (byte) 0);
            System.arraycopy (tempBuffer, 
                currentKeyLength + i*(currentKeyLength + currentDataLength), 
                pageBuffer, 
                headerLength + currentKeyLength + DATA_ZERO_PREFIX_LENGTH + i*(keyLengthX + currentDataLength), 
                currentDataLength);
        }
        freeStart += numEntries * DATA_ZERO_PREFIX_LENGTH;
        currentDataLength = dataLengthX;
        dataShrinked = false;
    }
    
    void copyEntry (int offset, BtreeEntry entry) {
        int keyStart = keysShrinked ? KEY_ZERO_PREFIX_LENGTH : 0;
        int dataStart = dataShrinked ? DATA_ZERO_PREFIX_LENGTH : 0;        
        System.arraycopy(entry.key, keyStart, pageBuffer, offset, currentKeyLength);        
	System.arraycopy(entry.data, dataStart, pageBuffer, 
            offset + currentKeyLength, currentDataLength);
    }
    
    private void copyState (ShrinkablePage page) {
        page.keysShrinked = keysShrinked;
        page.dataShrinked = dataShrinked;
        page.currentKeyLength = currentKeyLength;
        page.currentDataLength = currentDataLength;
    }
    
    public void dump () {
        System.out.println("# entries: " + numEntries () + " ------------------");
        for (int i = 0; i < numEntries (); i++) {
            boolean temp = debug;
            debug = true;
            getKey (i);
            System.out.print("  ");
            getData (i);
            debug = temp;
        }
        System.out.println("----------------------------------");
    }
    
    public void dumpBuffer () {
        System.out.print("buff: ");
        for (int x = headerLength; x < freeStart; x++) {
            System.out.print(pageBuffer[x] + ".");
        }
        System.out.println("");
    }
    
}