/*
 *                 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 org.netbeans.mdr.persistence.btreeimpl.btreestorage.*;	/* for BtreeMDRSource */
import java.util.*;
import java.io.*;
import java.text.*;

/**
 * Btree index implementation. This is the top of the 
 * Btree hierarchy which implements the
 * org.netbeans.mdr.persistence.Index interface hierarchy. This
 * abstract class and its subclasses contain the persistent state 
 * of a Btree and the public interface methods for accessing it.  
 * The main logic for searching and updating a
 * Btree is contained in the BtreePage class.
 *
 * 
The btreeindex package is as much as possible independent of the
 * btreestorage implementation.  However, there are a few dependencies which 
 * would need to be addressed if this code was to be used with some other
 * storage mechanism.  The main one is the need, when instantiating a
 * that was retrieved from the repository via Btree.read(), to instantiate the 
 * specific BtreePageSource implementation that this btree will use. The MOFID 
 * class also comes from the btreestorage package, and the Converter routines
 * from that package are used to convert integers to byte arrays and back.
 *
 * @author	Dana Bergen
 * @version	1.0
 */
public abstract class Btree extends Object implements Index, Streamable,
							StorageClient {

    protected BtreePageSource pageSource;
    protected BtreeStorage storage;		/* only used for MDR based btree */
    protected Storage.EntryType	keyType;
    protected Storage.EntryType	dataType;
    protected String 		name;

    protected EntryTypeInfo keyInfo; 
    protected EntryTypeInfo dataInfo;
    protected int	dataLength;
    protected int	pageIdLength;
    protected int 	pageSize;
    protected byte[]	rootPageId;

    protected boolean 	uniqueKeys;
    protected boolean 	uniqueValues;
    protected boolean 	hasBigKeys;

    /*
     * Operation types
     */
    static final byte ADD = 0;
    static final byte REPLACE = 1;
    static final byte REPLACE_IF_EXISTS = 2;
    /*
     * Status of current update operation.  We can get away with having these
     * globals because updates are single-threaded.
     */
    boolean failed;
    boolean replaced;

    /*
     * Synchronization (single writer, multiple readers)
     */
    private int activeReaders = 0;
    private int activeWriters = 0;
    private int waitingWriters = 0;
    int modCount = 0;

    public Btree(String name, Storage.EntryType keyType, 
    			     Storage.EntryType dataType, 
			     BtreePageSource pageSource) 
			     throws StorageException {

	BtreePage root;

	this.keyType = keyType;
	this.dataType = dataType;
	this.name = name;
	this.pageSource = pageSource;
	pageSize = pageSource.getPageSize();
        storage = pageSource.getStorage ();

	init();
    }

    /*
     * To be called after attributes have been populated by the
     * constructor or read().
     */
    protected void init() throws StorageException {

        BtreePage root;

        if (keyInfo != null) {
	    /* This object was found in cache and is already initialized */
	    return;
	}

	keyInfo = EntryTypeInfo.getEntryTypeInfo(keyType, storage);
	dataInfo = EntryTypeInfo.getEntryTypeInfo(dataType, storage);
	if (keyInfo == null) {
	    throw new StorageBadRequestException(
	    	MessageFormat.format(
			"Invalid index key type: ",
			new Object[] {keyType}));
	}
	if (dataInfo == null) {
	    throw new StorageBadRequestException(
	    	MessageFormat.format(
			"Invalid index data type: ",
			new Object[] {dataType}));
	}
        
        // this value is useless in case dataType == Storage.EntryType.STRING
	dataLength = dataInfo.getLength();

	pageIdLength = pageSource.getPageIdLength();

	if (rootPageId == null) {
	    /* 
	     * There are three possible scenarios: this is a new file-based
	     * btree; this is a new MDR object btree; or, this is an existing 
	     * file-based btree.  In the last case, getRootPage() will
	     * return the already-existing root page.  In the other cases, it
	     * will return a newly-constructed page.
	     */
	    root = pageSource.getRootPage(this);
	    rootPageId = new byte[pageIdLength];
	    System.arraycopy(root.pageId, 0, rootPageId, 0, root.pageId.length);
	    root.makeRoot();
        } else {
	    /* This is an existing MDR object btree. */
	    root = pageSource.getPage(rootPageId, this);
	}

	if (pageSource.isNoPage(root.nextPage)) {
	    hasBigKeys = false;
	} else {
	    hasBigKeys = true;
	}
	pageSource.unpinPage(root);
    }

    /*
     * Streamable Interface methods.  These are only used for Btree's
     * stored as MDR objects (when pageSource is a BtreeMDRSource).
     */

    public Btree() {
    }

    /**
     * Write the state of this Btree to the OutputStream.
     *
     * @param	outputStream	OutputStream
     */
    public void write(OutputStream outputStream) throws StorageException {

	/*
	 * We don't need synchronization because this will only happen
	 * at commit, or when the object is known to not be in use.
	 */
	try {
	    DataOutputStream out = new DataOutputStream(outputStream);

	    byte[] n = name.getBytes();
	    out.writeShort(n.length);
	    out.write(n);
	    out.writeByte(keyType.encode());
	    out.writeByte(dataType.encode());
	    out.writeBoolean(uniqueValues);
	    out.writeInt(pageSize);
	    out.write(rootPageId);
	} catch (IOException e) {
	    throw new StorageIOException(e);
	}
    }

    /**
     * Populate this Btree from the InputStream. The Storage reference will have
     * already been set up in setStorage.
     *
     * @param	inputStream	InputStream
     */
    public void read(InputStream inputStream) throws StorageException {

	try {
	    DataInputStream in = new DataInputStream(inputStream);

	    short length = in.readShort();
	    byte[] n = new byte[length];
	    in.read(n, 0, length);
	    name = new String(n);

	    keyType = Storage.EntryType.decodeEntryType(in.readByte());
	    dataType = Storage.EntryType.decodeEntryType(in.readByte());
	    uniqueValues = in.readBoolean();
	    pageSize = in.readInt();

	    pageSource = new BtreeMDRSource(storage, pageSize);

	    rootPageId = new byte[pageSource.getPageIdLength()];
	    in.read(rootPageId, 0, rootPageId.length);
	} catch (IOException e) {
	    throw new StorageIOException(e);
	}

	/* Now that we've read everything in, do the common initialization */
	init();
    }

    public void setStorage(Storage storage) {
        this.storage = (BtreeStorage) storage;
    }
    /*
     *
     * Index interface methods
     *
     */

    /** Returns the type of keys in index.
     * @return
     * @throws StorageException
     */
    public Storage.EntryType getKeyType() {
        return keyType;
    }

    /** Returns the type of values indexed by this index.
     * @return
     * @throws StorageException
     */
    public Storage.EntryType getValueType() {
        return dataType;
    }

    /** Returns the unique name of the index in the Storage.
     * @return
     * @throws StorageException
     */
    public String getName() {
        return name;
    }

    /** Returns a set view of the keys contained in this index.
     * Returned set is read only and may not be modified.
     * @return keys contained in this index
     * @throws StorageException
     */
    public Set keySet() throws StorageException {
        return new BtreeKeySet(this);
    }

    /**
     * Add a new entry to the index. 
     *
     * @param	key	key to insert	
     * @param	data	data associated with key
     *
     * @exception StorageBadRequestException 
     * 			If key or data are incorrect type, or if 
     *			the insert would violate the constraints of this index
     * @exception StorageException
     *			If a problem was encountered accessing storage
     */
    public void add(Object key, Object data) throws StorageException {
        beginWrite();
	try { 
	    failed = false;
	    btreePut(key, data, ADD, 0);

	    if (failed) {
		String message;
		if (uniqueKeys) {
		    message =
			MessageFormat.format("Key {0} already exists in index",
			    new Object[] {key});
		} else {
		    message =
			MessageFormat.format(
			    "Key-value pair {0}, {1} already exists in index",
			    new Object[] {key, data});
		}
		throw new StorageBadRequestException(message);
	    }
	} finally {
	    endWrite();
	}
    }

    /**
     * Remove all entries associated with the specified key.
     *
     * @param	key	key for entry to be removed
     *
     * @return	true if a matching entry was found
     *
     * @exception StorageException	If there was a problem reading or 
     *					writing pages
     */
    public boolean remove(Object key) throws StorageException {

        beginWrite();
	try { 
	    boolean result;
	    byte[] keyBuffer;

	    if ((keyBuffer = keyInfo.toBuffer(key)) == null) {
		throw new StorageBadRequestException(
		    MessageFormat.format(
		    "Invalid key type for this index: {0} received, {1} expected",
			    new Object[] {
				key.getClass().getName(),
				keyInfo.typeName()} ));
	    }	
	    BtreePage root = pageSource.getPage(rootPageId, this);
	    result = root.remove(keyBuffer);
	    pageSource.unpinPage(root);
	    return result;
	} finally {
	    endWrite();
	}
    }

    /*
     *
     * Common support functions
     *
     */

    /**
     * Returns the right kind of BtreePage for this btree.
     */
    public BtreePage pageFactory() {

        if (!dataInfo.isFixedLength())
            return new VarRecordPage();
	if (keyInfo.isFixedLength()) {
            if ((keyInfo instanceof MOFIDInfo) && (dataInfo instanceof MOFIDInfo)) {
                return new ShrinkablePage ();
            } else {            
                return new FixedKeyPage();
            }
	} else {
	    return new VarKeyPage();
	}
    }
    
    /**
     * Returns the tree's first record location, for initializing an Iterator.
     *
     * @return	SearchResult pointing to first record
     */
    SearchResult getFirst() throws StorageException {
        SearchResult result;

        BtreePage root = pageSource.getPage(rootPageId, this);
	result = root.getFirst();
	if (result.page != root) {
	    pageSource.unpinPage(root);
	}
	return result;
    }

    /**
     * Returns the location of the first entry for the specified key, for
     * initializing a BtreeListbyKeyIterator.
     *
     * @return SearchResult pointing to first record matching key
     */
    SearchResult getLocation(byte[] key) throws StorageException {
        SearchResult result;

        BtreePage root = pageSource.getPage(rootPageId, this);
	result = root.getLocation(key);
	if (result.page != root) {
	    pageSource.unpinPage(root);
	}
	return result;
    }

    protected void btreePut(Object key, Object data, byte operation, int index) 
    						throws StorageException {

	byte[] keyBuffer;
	byte[] dataBuffer;

	if ((keyBuffer = keyInfo.toBuffer(key)) == null) {
	    throw new StorageBadRequestException(
	    	MessageFormat.format(
		"Invalid key type for this index: {0} received, {1} expected",
			new Object[] {
			    key.getClass().getName(),
			    keyInfo.typeName()} ));
	}

	if ((dataBuffer = dataInfo.toBuffer(data)) == null) {
	    throw new StorageBadRequestException(
	    	MessageFormat.format(
		"Invalid data type for this index: {0} received, {1} expected",
			new Object[] {
			    data.getClass().getName(),
			    dataInfo.typeName()} ));
	}

	BtreePage root = pageSource.getPage(rootPageId, this);
	root.put(keyBuffer, dataBuffer, operation, index);
	pageSource.unpinPage(root);
    }

    /**
     * Returns the number of elements in this btree
     */
    int countRecords() throws StorageException {

        SearchResult location;
    	BtreePage savePage;
	int count = 0;

	location = getFirst();
	if (!location.matched) {
	    return 0;
	}

	do {
	    savePage = location.page;
	    BtreePage.getNext((byte[]) null, location);
	    count++;
	    if ((savePage != null) && (savePage != location.page)) {
	        pageSource.unpinPage(savePage);
	    }
	} while (location.matched); 

	if (location.page != null) {
	    pageSource.unpinPage(location.page);
	}
	return count;
    }

    boolean hasBigKeys() {
	return hasBigKeys;
    }

    void setHasBigKeys() {
        hasBigKeys = true;
    }

    void unsetHasBigKeys() {
        hasBigKeys = false;
    }

    /*
     * Synchronization methods
     */
    private boolean allowReader() {
        return waitingWriters == 0 && activeWriters == 0;
    }

    private boolean allowWriter() {
        return activeReaders == 0 && activeWriters == 0;
    }

    protected synchronized void beginRead() {
	while (!allowReader()) {
	    try { wait(); } catch (InterruptedException e) {}
	}
	activeReaders++;
    }

    protected synchronized void endRead() {
        activeReaders--;
	notifyAll();
    }
        
    protected synchronized void beginWrite() {
        waitingWriters++;
	while (!allowWriter()) {
	    try { wait(); } catch (InterruptedException e) {}
	}
	waitingWriters--;
	activeWriters++;
    }

    protected synchronized void endWrite() {
        activeWriters--;
	modCount++;
	notifyAll();
    }

    /*
     * For debugging.
     */
    /**
     * Print the contents of the btree for debugging purposes.
     *
     * @param out	PrintWriter to print btree to
     */
    public void dumpTree(PrintWriter out) throws StorageException {

	BtreePage root = pageSource.getPage(rootPageId, this);
	root.dumpTree(out);
	pageSource.unpinPage(root);
    }

    /**
     * Check the btree for consistency, for testing and debugging.
     *
     * @param out	PrintWriter to print results to
     *
     * @return	number of errors encountered
     */
    public int consistencyCheck(PrintWriter out) throws StorageException {
        int result;

	BtreePage root = pageSource.getPage(rootPageId, this);
	result = root.consistencyCheck(out);
	pageSource.unpinPage(root);
	return result;
    }

}