btreenodeuos.java

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

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

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

/**	BtreeNodeUos is the super class for both BtreeInteriorUos and BtreeLeafUos. */
public abstract class BtreeNodeUos implements Serializable
{
	/**	The parent of this node */
	protected transient BtreeInteriorUos parent;
	
	/**	The parent of this node */
	public BtreeInteriorUos parent()
	{
		return parent;
	}
	
	/**	Set the parent of this node to be newParent. <br>
		Analysis: Time = O(1) 
		@param newParent The new parent for this node */
	public void setParent(BtreeInteriorUos newParent)
	{
		parent = newParent;
	}

	/**	If this node is an interior node, this variable refers to
		the location where the node is stored in the node file. If this
		is a leaf node, this variable refers to the address of the
		block associated with the leaf. */
	protected long fileAddress;

	/**	Return fileAddress where this node is stored on disk. <br> 
		Analysis: Time = O(1) */
	public long fileAddress()
	{
		return fileAddress;
	}

	/**	Set fileAddress to be newFileAddress. <br>
		Analysis: Time = O(1) 
		@param newFileAddress The new file address for this node */
	public void setFileAddress(long newFileAddress)
	{
		fileAddress = newFileAddress;
	}
	
	/**	Search for an item in or below this node with key itemKey,
		and save the result of the search in fields of the treeHeader. */
	abstract public void search(Comparable key, BtreeFileUos treeHeader);

	/**	Does this node, or one below it, have an item with key itemKey?. */
	abstract public boolean has(Comparable key);

	/**	Place item into the proper subtree with its key, and if a new node
		was created, return its low value and the node. */
	abstract public PairUos insert(Comparable key, Object item, BtreeFileUos treeHeader);

	/**	Delete the entry with key itemKey, and return a boolean to indicate 
		whether this node needs to be deleted and the low value of this node. */
	abstract public PairUos delete(Comparable itemKey, BtreeFileUos treeHeader);
	
	/**	String representation of the node */
	abstract public String formatToString(int index, String indentation);
	
	/**	The smallest key value of the tree.  If the correct key is not stored
		for a child in this node or a descendant node throw an exception. <br>
		Analysis : Time = O(n) file reads, n = number of descendant nodes */
	abstract protected Object minOfValidTree();
}