btreefileuos.java

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

		Analysis: Time = O(h) + O(h) file reads, where h = the height of the tree <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul>
		@param k The key of the item to obtain */ 
	public Object obtain(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot obtain an item that is not in the tree");

		CursorUos savePos = currentPosition();
		search(k);
		Object result = item();
		goPosition(savePos);
		return result;
	}

	/**	Set the item with key k be equal to x. <br>
		Analysis: Time = O(h) + O(h) file reads, where h = the height of the tree <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul>
		@param k The key of the item to set
		@param x The new value to be associated with key k */
	public void set(Comparable k, Object x) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot set an item that does not exist");
		
		CursorUos savePos = currentPosition();
		search(k);
		setItem(x);
		goPosition(savePos);
	}

	/**	Set value of the current item and write it to disk within the current block. <br>
		Analysis: Time = O(1) + 1 file read and write <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul>
		@param value The new value for the current item */
	public void setItem(Object value) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There must be a current item to set it");

		BtreeRecordUos updateRecord = new BtreeRecordUos(itemKey(), value);
		currentBlock.putRecord(updateRecord, indexInBlock);
		dataFile.writeBlock(currentBlock, adrCurrentBlock);
	}

	/**	Is the current position before the start of the structure?. <br>
		Analysis: Time = O(1) */
	public boolean before()
	{
		return isEmpty() || (!itemExists() && !after());
	}

	/**	Move prior to the first item. <br>
		Analysis: Time = O(1) */
	public void goBefore()
	{
		adrCurrentBlock = -1;
		indexInBlock = 0;
		currentBlock = null;
	}

	/**	Is the current position after the end of the structure?. <br>
		Analysis: Time = O(1) */
	public boolean after()
	{
		return isEmpty() || indexInBlock == -1;
	}

	/**	Move after the last item. <br>
		Analysis: Time = O(1) */
	public void goAfter()
	{
		adrCurrentBlock = -1;
		indexInBlock = -1;
		currentBlock = null;
	}

	/**	Go to the first item in the Btree. <br>
		Analysis: Time = O(1) + at most 1 file read */
	public void goFirst()
	{
		if (rootNode != null)
		{
			adrCurrentBlock = adrFirstBlock;
			currentBlock = dataFile.readBlock(adrCurrentBlock);
			indexInBlock = 1;
		}
		else
		{
			goAfter();
		}
	}

	/**	Advance one item in the Btree. <br>
		Analysis: Time = O(1) + at most 1 file read   
		PRECONDITION: <br>
		<ul>
			!after()
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Can't goForth() when after.");
			
		if (before())
			goFirst();
		else if (indexInBlock < currentBlock.num)
			indexInBlock ++;
		else if (currentBlock.adrNextBlock == -1)
			goAfter();
		else
		{
			adrCurrentBlock = currentBlock.adrNextBlock;
			currentBlock = dataFile.readBlock(adrCurrentBlock);
			indexInBlock = 1;
		}
	}

	/**	For current node n, determine its next sibling in parent node p. <br>
		Analysis: Time = O(n), n = the number of children in the parent */
	protected BtreeNodeUos nextSibling(BtreeInteriorUos p, BtreeNodeUos n)
	{
		if (p == null)
			return null;
		else
		{
			int indexInParent = p.indexOfAddress(n.fileAddress);
			if (indexInParent < p.childCount)
				return p.child(indexInParent+1);
			else
				throw new Error("Cannot find child in parent node");
		}
	}

	/**	Return the current position within the tree. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		return new BtreeCursorUos(adrCurrentBlock, currentBlock, indexInBlock);
	}

	/**	Move to cursor to the specified position. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			pos instanceof BtreePCursorUos 
		</ul> 
		@param pos The position to become the current position */
	public void goPosition(CursorUos pos) throws InvalidArgumentUosException
	{
		if (!(pos instanceof BtreeCursorUos))
			throw new InvalidArgumentUosException("Position in a Btree must be a BtreeCursorUos");
			 
		adrCurrentBlock = ((BtreeCursorUos)pos).address;
		currentBlock = ((BtreeCursorUos)pos).block;
		indexInBlock = ((BtreeCursorUos)pos).index;
	}

	/**	Clear the tree of all its contents. <br>
		Analysis: Time = O(1) */
	public void wipeOut() 
	{
		rootNode = null; 
		goBefore();
		/* Clear the files */
		nodeFile = new BtreeNodeFileUos(nodeFile.name, nodeFile.nodeSize);
		dataFile = new BtreeBlockFileUos(dataFile.name, dataFile.blockSize);
	}

	/**	Returns a string representation of the key-item pairs in ascending key order. <br>
		Analysis: Time = O(b) file reads, where b = the number of blocks in the file. */
	public String sequentialToString()
	{
		if (isEmpty())
			return "";
		else
		{
			String result = "\n";
			BtreeBlockUos block = null;
			for (long fileAddress = adrFirstBlock; fileAddress != -1; fileAddress = block.adrNextBlock)
			{
				block = dataFile.readBlock(fileAddress);
				result += block.toString();
			}
			return result;
		}
	}

	/**	Returns a string representation of the key-item pairs as they appear on disk. <br>
		Analysis: Time = O(b) file reads, where b is the number of blocks in the file. */
	public String serialToString()
	{
		return "\n" + dataFile.serialToString();
	}

	/**	Write a final header to the data file, write the root to disk if
		necessary and then close the files associated with this tree. <br>
		Analysis: Time = O(1) + 2 file writes. */
	public void closeFile()
	{
		/* Make sure the root gets written to disk if it is an interior node */
		if (rootNode instanceof BtreeInteriorUos)
			nodeFile.writeNode((BtreeInteriorUos) rootNode);

		/* Write an up-to-date header into the data file */
		BtreeFileHeaderUos finalHeader = new BtreeFileHeaderUos(this);
		dataFile.setHeader(finalHeader);
		dataFile.writeHeader();
		dataFile.close();
		nodeFile.close();
	}

	/**	Return a sequential output of the contents of the file. <br>
		Analysis: Time = O(b) file reads, where b = the number of blocks in the file. */
	public String toString()
	{
		return  "\nData File Name: " + dataFile.name 
				+ "\nContents: " + sequentialToString();
	}
	
	/**	Return a string representation of the tree with the proper indentation. <br> 
		Analysis: Time = O(n + b) file reads, where n = the number of the nodes in the tree,
											and b = the number of blocks in the file. */
	public String formatToString()
	{
		if (isEmpty())
			return new String();
		else 
			return "Address of the first block: " + adrFirstBlock  
							+ rootNode.formatToString(0, "");
	}

	/**	The number of times key k occurs within the dictionary. <br>
		Analysis: Time = O(h) file reads, where h = the height of the tree.
		@param k Key being counted in the dictionary */
	public int frequency(Comparable k)
	{
		if (has(k))
			return 1;
		else
			return 0;
	}

	/**	Is the correct key stored for the root node and all descendant nodes?. <br>
		Analysis : Time = O(n) file reads, n = number of nodes in the file */
	public boolean validTree()
	{
		if (rootNode == null)
			return true;
		else
			try
			{
				rootNode.minOfValidTree();
				return true;
			} catch (Exception e)
			{
				return false;
			}
	}
}