btreefileuos.java

国外的数据结构与算法分析用书

/* BtreeFileUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
package dslib.file;

import dslib.base.*;
import dslib.dictionary.*;
import java.io.Serializable;
import dslib.exception.*;

/**	This class defines a Btree used for index-sequential files 
	that implements a full PKeyed dictionary. */
public class BtreeFileUos implements PKeyedDictUos
{
	/**	The order of this Btree. */
	protected int order;

	/**	The root node for this tree.  It may be either a leaf or an interior node. */
	protected BtreeNodeUos rootNode;

	/**	The file where the records are stored. */
	protected BtreeBlockFileUos dataFile;

	/**	The file that contains the nodes of this tree. */
	protected BtreeNodeFileUos nodeFile;
 
	/**	The address of the first block with respect to sequential ordering. */
	protected long adrFirstBlock;

	/**	The file address for the current block. */
	public long adrCurrentBlock; // !!

	/**	The current block that contains the current item and its key. */
	public BtreeBlockUos currentBlock; //!!

	/**	The index within the block where the current item is located,
		set to -1 for the after state. */
	public int indexInBlock; //!!

	/**	Make a Btree with order d that uses the files passed in
		for storing nodes and data.  When written to disk, the nodes must 
		have a maximum size of nodeSize, and the blocks must have a
		maximum size of blockSize. <br>
		Analysis : Time = O(1) + 2 file reads
		@param d The order of the btree that will be created
		@param dataFileName The name of the file where data is stored
		@param nodeFileName The name of the file where nodes are stored
		@param blockSize The maximum size (in bytes) that a block can have when written to disk
		@param nodeSize The maximum size (in bytes) that a node can have when written to disk */
	public BtreeFileUos(int d, String  dataFileName, String nodeFileName, int blockSize, int nodeSize) 
	{
		order = d;
		dataFile = new BtreeBlockFileUos(dataFileName, blockSize);
		nodeFile = new BtreeNodeFileUos(nodeFileName, nodeSize);
		goBefore();
	}

	/**	Restore a Btree that was previously made and saved. <br>
		Analysis : Time = O(1) + 4 file reads 
		@param dataFileName The name of the data file associated with a previous btree */
	public BtreeFileUos(String dataFileName) 
	{
		/* Reopen a Btree that was saved to disk */
		dataFile = new BtreeBlockFileUos(dataFileName);
		BtreeFileHeaderUos savedHeader = dataFile.header;
		nodeFile = new BtreeNodeFileUos(savedHeader);
		order = savedHeader.BtreeOrder; 

		/* Decide how to make the root */
		if (savedHeader.treeEmpty) /* Restore an empty tree */
			rootNode = null;  
		else if (savedHeader.rootIsALeaf) 
			rootNode = new BtreeLeafUos(savedHeader.rootAddress, dataFile);
		else
		{
			BtreeInteriorUos interiorRoot = nodeFile.readNode(savedHeader.rootAddress);
			interiorRoot.setDataFile(dataFile);
			interiorRoot.setNodeFile(nodeFile);
			rootNode = interiorRoot; 
		}
		goBefore(); 
	}

	/**	Access function for dataFile. <br>
		Analysis: Time = O(1) */
	public BtreeBlockFileUos dataFile()
	{
		return dataFile;
	}

	/**	Access function for nodeFile. <br>
		Analysis: Time = O(1) */
	public BtreeNodeFileUos nodeFile()
	{
		return nodeFile;
	}

	/**	Access function for order. <br>
		Analysis: Time = O(1) */
	public int order()
	{
		return order;	
	}

	/**	Is the Btree empty?. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return (rootNode == null);
	}

	/**	Is the Btree full? The answer is always false. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	Is there a current item?. <br>
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return adrCurrentBlock != -1;
	}

	/**	The key associated with the current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists()
		</ul> */
	public Comparable itemKey() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist");
			
		return currentBlock.getRecord(indexInBlock).key;
	}

	/**	The current item in the Btree file. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists()
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist");
			
		return currentBlock.getRecord(indexInBlock).item;
	}

	/**	The current key-item pair. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists()
		</ul> */
	public PairUos keyItemPair() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist");
			
		return new PairUos(itemKey(), item());
	}

	/**	Does this tree contain an entry with key searchKey. <br>
		Analysis: Time = O(h) + O(h) file reads, where h = the height of the tree.
		@param searchKey The key of the item being sought */
	public boolean has(Comparable searchKey)
	{
		if (isEmpty())
			return false;
		else
			return rootNode.has(searchKey);
	}

	/**	Move to the item with key searchKey. <br>
		Analysis: Time = O(h) + O(h) file reads, where h = the height of the tree
		@param searchKey The key of the item being sought */
	public void search(Comparable searchKey)
	{
		if (isEmpty())
			goBefore();
		else
			rootNode.search(searchKey, this);
	}

	/**	Insert newItem into the tree with key k. <br>
		Analysis: Time = O(h) + O(h) file operations, where
		h = the height of this tree. 
		@param k The key of the item that will be inserted
		@param newItem The new item to be inserted */
	public void insert(Comparable k, Object newItem)
	{
		if (rootNode == null) /* Nothing is in the tree yet */
		{
			BtreeBlockUos insertBlock = new BtreeBlockUos();
			/* The return value should always be null */
			if (insertBlock.insert(k, newItem) != null)
				throw new UosException("Error in insert() of BtreeFleUos");

			long newAddress = dataFile.getNextAddress();
			rootNode = new BtreeLeafUos(insertBlock, newAddress, dataFile);
			adrFirstBlock = newAddress;
		}
		else
		{
			PairUos pair = rootNode.insert(k, newItem, this);
			if ((pair != null) && (pair.secondItem() != null)) 
			{
				BtreeNodeUos extraNode = (BtreeNodeUos) pair.secondItem();
				/* Make a new root from the old root and the returned node */
				rootNode = new BtreeInteriorUos(rootNode, extraNode, 
								(Comparable) pair.firstItem(), nodeFile, dataFile, order);
			}
		}
	}

	/*	Delete the item with the key k. <br>
		Analysis: Time = O(h) + O(h) file operations, where h = the height of the tree. <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul>
		@param k The key of the item to be deleted */
	public void delete(Comparable k)
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot delete an item that does not exist");
		
		/* if deleting the current item, go to the next item */
		if (itemExists() && k.compareTo(itemKey()) == 0)
			goForth();
		PairUos pair = rootNode.delete(k, this);
		if (((Boolean)pair.firstItem()).booleanValue()) 
			rootNode = null; 
		else if (rootNode instanceof BtreeInteriorUos) 
		{
			/*	Although the root node doesn't need to be deleted, if it 
				is an interior node it may only have one child.  If so, 
				collapse the link to that one child. */
			BtreeInteriorUos interiorNode = (BtreeInteriorUos) rootNode;
			if (interiorNode.childCount == 1)
			{
				rootNode = interiorNode.child(1);
				rootNode.setParent(null);
				nodeFile.recoverNodeAddress(interiorNode.fileAddress());
			}
		}
	}

	/**	Delete the current item. <br>
		Analysis: Time = O(h) + O(h) file operations, where h = the height of the tree <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("No current item to delete");

		delete(itemKey());
	}

	/**	Return the item with key k. <br>