btreeblockuos.java

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

/* BtreeBlockUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.file;
import java.io.Serializable;

/**	A block of records with insertion and retrieval operations. */
public class BtreeBlockUos implements Serializable, Cloneable
{ 
	/*	The records are indexed 1 through num, but placed in 
		locations 0 through num-1 in array records. */
 
	/**	The internal representation of the block */
	private BtreeRecordUos[] records;
 
	/**	The number of records in this block */
	protected int num;

	/**	The maximum number of records per block */
	protected static int blockingFactor = 3;
	
	/**	Return the number of records per block. <br>
		Analysis : Time = O(1) */
	public int blockingFactor()
	{
		return blockingFactor;
	}

	/**	Make a block with room for blockingFactor records. <br>
		Analysis: Time = O(blockingFactor) */
	public BtreeBlockUos()      
	{
		records = new BtreeRecordUos[blockingFactor];
		num = 0;
		adrPrevBlock = -1;
		adrNextBlock = -1;
	}
  
	/**	The address of the previous block in the BtreeFile. */
	protected long adrPrevBlock;

	/**	Set a new value for adrPrevBlock. <br>
		Analysis: Time = O(1) 
		@param newValue The new value for adrPrevBlock */
	public void setAdrPrevBlock (long newValue) 
	{
		adrPrevBlock = newValue;	
	}

	/**	The address of the next block in the BtreeFile. */
	protected long adrNextBlock;

	/**	Set a new value for adrNextBlock. <br>
		Analysis: Time = O(1) 
		@param newValue The new value for adrNextBlock */
	public void setAdrNextBlock (long newValue) 
	{
		adrNextBlock = newValue;	
	}

	/**	Return the ith record in the record. <br>
		Analysis : Time = O(1) 
		@param i The index of the record that will be returned */
	public BtreeRecordUos getRecord(int i) 
	{
		return records[i-1];
	} 

	/**	Place newRec in position i. <br>
		Analysis : Time = O(1) 
		@param newRec The new record
		@param i The index where the new record will be placed */
	public void putRecord(BtreeRecordUos newRec, int i)
	{
		records[i-1] = newRec;
	}

	/**	Set num to the value of newNum. <br>
		Analysis: Time = O(1) 
		@param newNum The new value for num */
	public void setNum (int newNum) 
	{
		num = newNum;	
	}

	/**	String representation of the records in the block. <br> 
		Analysis: Time = O(num) */
	public String toString() 
	{
		String result = "\n"; 
		for (int i = 1; i <= num; i++)
			result += getRecord(i).toString() + "\n";

		return result;
	} 

	/**	String representation of the keys in the block. <br> 
		Analysis: Time = O(num) */
	public String keyToString()
	{
		String result = "";
		for (int i = 1; i <= num; i++)
			result += getRecord(i).keyToString() + "  ";
		return result;
	}

	/**	String representation of the complete block for printing. <br> 
		Analysis: Time = O(blockingFactor) */
	public String toStringComplete() 
	{
		String result = "\nAddress of the previous block: " + adrPrevBlock + "\n"; 
		for (int i = 1; i <= blockingFactor; i++)
			if (getRecord(i) != null)
				result += getRecord(i).toString() + "\n";
			else
				result += "null\n";
		return result + "Address of the next block: " + adrNextBlock + "\n";
	} 
    

	/**	Return the index of the record with key `sKey', or else 0 for not found. <br> 
		Analysis: Time = O(num) 
		@param sKey The key being sought within this block */
	public int search(Comparable sKey) 
	{
		int i;
		for (i=1; (i<=num) && (sKey.compareTo(getRecord(i).key)!=0); i++);

		if (i > num) 
			return 0; 
		else
			return i;
	}

	/**	Remove the ith record from the block. <br> 
		Analysis: Time = O(num) 
		@param i The index of the record to delete */
	public void deleteIth(int i)
	{
		for (int j=i+1; j!=num+1; j++)
			putRecord(getRecord(j), j-1);
	    putRecord(null, num);
		num--;
	}
 
	/**	Insert the key and newInfo into a record in the block (ordered by key).
		If overflow, move half the records to the Result returned. <br>
		Analysis: Time = O(num) 
		@param newKey The key of the new information 
		@param newInfo The new information to store in a record within this block */
	public BtreeBlockUos insert(Comparable newKey, Object newInfo) 
	{ 
		if (num < blockingFactor)
		{
			/* No overflow so just shift the records with larger keys */
		    int i = num;
			while ((i > 0) && (newKey.compareTo(getRecord(i).key)<=0))
			{
				putRecord(getRecord(i), i+1);
				i = i - 1;
			}
			BtreeRecordUos newRec = new BtreeRecordUos(newKey, newInfo);
			putRecord(newRec, i+1);
			num = num + 1;
			return null;
		}
		else 
			/* Overflow so need to make a result block with half the records. */
			return splitBlock(newKey, newInfo);
	}	 
  
	 


	/**	This routine splits the Current block into two blocks.
		The current block is given the smaller key values  
		and the block with larger key values will be returned.  extraInfo 
		and extraKey will be in a record of one of the two blocks. <br>
		Analysis : Time = O(num)
		@param extraKey The key of the record that forced a split
		@param extraInfo The information in the record that forced a split */
	protected BtreeBlockUos splitBlock(Comparable extraKey, Object extraInfo)   
	{
		BtreeRecordUos newRecord = new BtreeRecordUos(extraKey, extraInfo);

		BtreeBlockUos result = new BtreeBlockUos();
		/* Fill result with the larger keyed records */
		int numForResult = Math.round(((float)blockingFactor + 1.0f) / 2.0f);
		boolean newRecordPlaced = false; 
		int indexInCurrent = num;
		for (int indexInResult = numForResult; indexInResult > 0; indexInResult--)
		{
			if ((! newRecordPlaced) && 
				(newRecord.key.compareTo(getRecord(indexInCurrent).key) > 0)) 
			{
				result.putRecord(newRecord, indexInResult);
				newRecordPlaced = true;
			}
			else
			{
				result.putRecord(getRecord(indexInCurrent), indexInResult);
				indexInCurrent--;   
			}
		}
		result.setNum(numForResult);
     	 
		/* If new record not yet placed, shift records to place it. */
		if (! newRecordPlaced)
		{
			while ((indexInCurrent != 0)
				&& (getRecord(indexInCurrent).key.compareTo(newRecord.key) > 0))
			{
				putRecord(getRecord(indexInCurrent), indexInCurrent + 1);
				indexInCurrent--;
			}
			putRecord(newRecord, indexInCurrent + 1);
			newRecordPlaced = true;
		}
		num = num + 1 - numForResult;
		for (indexInCurrent=num+1; indexInCurrent<=blockingFactor; indexInCurrent++)
			putRecord(null, indexInCurrent);
		return result;
	}

	/**	Return a clone of this block. */
	public Object clone()
	{
		try
		{
			BtreeBlockUos clone = new BtreeBlockUos();
			for (int i=1; i <=num; i++)
				clone.putRecord(getRecord(i), i); 

			clone.setNum(num);
			return clone;
		} catch(Exception e) {System.err.println(e); }
		return null;
	}
}