btreeleafuos.java

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

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

package dslib.file;

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

/** This class defines a leaf for a Btree. */
public class BtreeLeafUos extends BtreeNodeUos
{
    /** The block associated with this leaf. */
    protected BtreeBlockUos myBlock;

    /** The lowest key in the block associated with this leaf.  <br> 
        Analysis: Time = O(1) */
    protected Comparable lowKey()
    {
        return myBlock.getRecord(1).key;
    }

    /** The file where the block associated with this leaf is stored. */
    protected transient BtreeBlockFileUos dataFile;
  
    /** Read the information for this leaf from address ba of file dfile. <br> 
        Analysis: Time = O(1) + 1 file read. 
        @param ba The block address for the block associated with this leaf
        @param dfile The block file associated with this leaf */
    public BtreeLeafUos(long ba, BtreeBlockFileUos dfile) 
    {
        fileAddress = ba;
        dataFile = dfile;
        myBlock = dataFile.readBlock(ba);
    }

    /** Create a leaf from a block, and write the block to disk at the 
        specified address in the specified file. <br>
        Analysis: Time = O(1) + 1 file write
        @param blk The block to be associated with this leaf
        @param ba The block address for the block associated with this leaf
        @param d The block file associated with this leaf */
    public BtreeLeafUos(BtreeBlockUos blk, long ba, BtreeBlockFileUos d)
    {
        myBlock = blk;
        fileAddress = ba;
        dataFile = d;
        dataFile.writeBlock(blk, ba);
    }
 
    /** Seek and return the block associated with this node. <br> 
        Analysis : Time = O(1) + 1 file read */
    public BtreeBlockUos getMyBlock()
    { 
        return dataFile.readBlock(fileAddress());
    }

    /** Update the search related variables within the treeHeader
        according to search results pertaining to itemKey. <br> 
        Analysis : Time = O(getMyBlock.num) 
        @param itemKey The key of the item being sought
        @param treeHeader The Btree in which this node belongs */
    public void search (Comparable itemKey, BtreeFileUos treeHeader)
    {
        int index = myBlock.search(itemKey);
        if (index > 0) 
        {
            treeHeader.currentBlock = myBlock;
            treeHeader.adrCurrentBlock = fileAddress();
            treeHeader.indexInBlock = index;
        }
        else
        {
            treeHeader.goBefore();
        } 
    }

    /** Return true if an item with key itemKey exists. <br> 
        Analysis : Time = O(getMyBlock.num) 
        @param itemKey The key of the item to search for */
    public boolean has (Comparable itemKey)
    {
        return (myBlock.search(itemKey) > 0);
    }

    /** Make a record with the arguments and insert it into the block for
        this leaf.  If there is an overflow, create a new leaf corresponding
        to the block with the larger keys, and return its low value and it. <br>
        Analysis : Time = O(myBlock.num) + 4 file writes and 1 file read. 
        @param itemKey The key of the item to be inserted
        @param itemContents The new item to be inserted */
    public PairUos insert(Comparable itemKey, Object itemContents, BtreeFileUos treeHeader)
    {
        Comparable saveCurKey;  // save the current key if the current block is myBlock
        if (treeHeader.itemExists() & treeHeader.adrCurrentBlock == fileAddress)
            saveCurKey = treeHeader.itemKey();
        else
            saveCurKey = null;
        
        BtreeBlockUos extraBlock = myBlock.insert(itemKey, itemContents);  

        if (extraBlock != null) 
        {
            /* Block split -> make a leaf to pass up */
            long newAddress = dataFile.getNextAddress();
            BtreeLeafUos newLeaf = new BtreeLeafUos(extraBlock, newAddress, dataFile);
            
            /* Link the new block into the list of blocks */
            if (myBlock.adrNextBlock != -1)
            {
                BtreeBlockUos nextBlock = dataFile.readBlock(myBlock.adrNextBlock);
                nextBlock.adrPrevBlock = newAddress;
                dataFile.writeBlock(nextBlock, myBlock.adrNextBlock);
            }
            extraBlock.adrNextBlock = myBlock.adrNextBlock;
            extraBlock.adrPrevBlock = fileAddress;
            myBlock.adrNextBlock = newAddress;
    
            /* Save the blocks since they were changed */
            dataFile.writeBlock(myBlock, fileAddress());
            dataFile.writeBlock(extraBlock, newAddress);
        
            /* If necessary, update the header information for the current item */
            if (saveCurKey != null)
            {
                int index = myBlock.search(saveCurKey);
                if (index != 0)
				{
					treeHeader.indexInBlock = index;
                    treeHeader.currentBlock = myBlock;
				}
                else
				{
                    treeHeader.indexInBlock = extraBlock.search(saveCurKey);
                    treeHeader.currentBlock = extraBlock;
                    treeHeader.adrCurrentBlock = newAddress;
                }
            } 

            return new PairUos(newLeaf.lowKey(), newLeaf);
        } 
        else
        {
            /* Save my block since it changed */
            dataFile.writeBlock(myBlock, fileAddress());
            
            /* If necessary, update the header information for the current item */
            if (saveCurKey != null)
			{
                treeHeader.indexInBlock = myBlock.search(saveCurKey);
                treeHeader.currentBlock = myBlock;
			}
    
            return null;
        }
    }

    /** Delete the entry with key itemKey, and return as the first item of the
        pair a boolean to indicate whether this node needs to be deleted. 
        If the block is not empty and has a new low value, return the new low
        value as the second item of the pair, else return null in the pair.  <br>
        Analysis: Time = O(myBlock.num) + at most 2 file reads and writes. 
        PRECONDITION: <br>
        <ul>
            has(itemKey)
        </ul>
        @param itemKey The key of the item to be deleted */
    public PairUos delete(Comparable itemKey, BtreeFileUos treeHeader)
    {
        if (!has(itemKey))
            throw new ItemNotFoundUosException("Cannot delete an item that does not exist");
        
        /* If deleting the current item, go to the next item */
        if (treeHeader.itemExists() && treeHeader.itemKey().compareTo(itemKey) == 0)
            treeHeader.goForth();

        Comparable saveCurKey;  // save the current key if the current block is myBlock
        if (treeHeader.itemExists() & treeHeader.adrCurrentBlock == fileAddress)
            saveCurKey = treeHeader.itemKey();
        else
            saveCurKey = null;
        
        int delIndex = myBlock.search(itemKey);
        myBlock.deleteIth(delIndex);
        if (myBlock.num == 0) 
        {
            /* Remove the block from the list of blocks */
            if (myBlock.adrNextBlock != -1)
            {
                BtreeBlockUos nextBlock = dataFile.readBlock(myBlock.adrNextBlock);
                nextBlock.adrPrevBlock = myBlock.adrPrevBlock;
                dataFile.writeBlock(nextBlock, myBlock.adrNextBlock);
            }
            if (myBlock.adrPrevBlock != -1)
            {
                BtreeBlockUos prevBlock = dataFile.readBlock(myBlock.adrPrevBlock);
                prevBlock.adrNextBlock = myBlock.adrNextBlock;
                dataFile.writeBlock(prevBlock, myBlock.adrPrevBlock);
            }
            else
                treeHeader.adrFirstBlock = myBlock.adrNextBlock;
    
            dataFile.returnAddress(fileAddress());
            return new PairUos(new Boolean(true), null);    
        }
        else
        {
            dataFile.writeBlock(myBlock, fileAddress());
            if (saveCurKey != null)
			{
                treeHeader.indexInBlock = myBlock.search(saveCurKey);
                treeHeader.currentBlock = myBlock;
			}
    
            if (delIndex == 1)
                return new PairUos(new Boolean(false), myBlock.getRecord(1).key);
            else
                return new PairUos(new Boolean(false), null);
        } 
    }

    /** Return a string representation of the leaf node. <br>
        Analysis : Time = O(myBlock.num) */
    public String toString()
    {
        return myBlock.toString();
    }
    
    /** Return a string representation of the leaf node with the proper indentation. <br>
        Analysis: Time = O(myBlock.num) */
    public String formatToString(int index, String indent)
    {
        return "\n" + indent + "leaf content: " + myBlock.keyToString()
                + " My address: " + fileAddress + "  prev & cur: " 
                + myBlock.adrPrevBlock + ", " + myBlock.adrNextBlock;
    }
    
    /** The smallest key value of the node. No tree to check, so it is always valid. <br>
        Analysis : Time = O(myBlock.num) */
    protected Object minOfValidTree()
    {
        return myBlock.getRecord(1).key;
    }
    }