btreeinterioruos.java

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

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

package dslib.file;

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

/** This class defines the Btree interior node that can be stored on disk. */ 
public class BtreeInteriorUos extends BtreeNodeUos 
{
    /** The order of the Btree in which this node belongs. */
    protected int order;

    /** The keys for the subtrees. */
    protected Comparable[] keys;
   
    /** The file addresses for the children. */
    protected long[] childFileAddress;

    /** The number of children of this node. */
    protected int childCount;

    /** Does this node have leaf child?. */
    protected boolean leafChildren; 
 
    /** The file that contains the other interior nodes. */
    protected transient BtreeNodeFileUos nodeFile;
    
    /** The file that contains the blocks and the Btree file header. */
    protected transient BtreeBlockFileUos dataFile;
    
    /** Make an interior node with the 2 children that are passed in as parameters.  
        Also passed in is the node and data file and Btree order that every 
        interior node needs to know. <br>
        Analysis : Time = O(newOrder) + 1 file write
        @param child1 The first child for this node
        @param child2 The second child for this node
        @param child2LowKey The lowest key associated with child2
        @param n The node file that this node will use
        @param d The data file that this node will use
        @param newOrder The order of the Btree */
    public BtreeInteriorUos (BtreeNodeUos child1, BtreeNodeUos child2, Comparable child2LowKey, 
                BtreeNodeFileUos n, BtreeBlockFileUos d, int newOrder)
    {
        order = newOrder;
        nodeFile = n;
        dataFile = d;
        fileAddress = nodeFile.getNextFileAddress();  
      
        /* See what type of children were passed in */
        if (child1 instanceof BtreeLeafUos)
            setLeafChildren(true);
        else
            setLeafChildren(false);
 
        /* Record child file addresses */
        childFileAddress = new long[2*order + 1];
        putChildFileAddress(child1.fileAddress(), 1);
        child1.setParent(this);
        putChildFileAddress(child2.fileAddress(), 2);
        child2.setParent(this);
        childCount = 2;
        
        /* Set up the keys */
        keys = new Comparable[2 * order];
        putKey(child2LowKey, 2);
        nodeFile.writeNode(this);
    }
 

    /** Create a node from a full node and another extra child that has
        the largest key.  Of the nodes, this node is given the 
        half of the children with largest keys. <br>
        Analysis : Time = O(order) + 2 file writes
        @param fullNode A node that has the maximum number of children
        @param extraChildFileAddress The file address of the extra child
        @param extraChildLowKey The lowest key of the extra child */
    public BtreeInteriorUos(BtreeInteriorUos fullNode, 
                long extraChildFileAddress, Comparable extraChildLowKey)
    {
        order = fullNode.order;
        nodeFile = fullNode.nodeFile;
        dataFile = fullNode.dataFile;
        fileAddress = nodeFile.getNextFileAddress();
        leafChildren = fullNode.leafChildren;
        childFileAddress = new long[2 * order + 1];
        keys = new Comparable[2 * order];
     
        /* Move the last half of fullNode's children here */
        int myIndex = 1;
        for (int indexInFull = order+2; indexInFull <= 2*order+1; indexInFull++)
        {
            /* Copy over a child address */
            putChildFileAddress(fullNode.getChildFileAddress(indexInFull), myIndex);
            child(myIndex).setParent(this);
            fullNode.putChildFileAddress(0, indexInFull);
            
            /* Copy over a key, if one exists */
            if (myIndex > 1)
                putKey(fullNode.getKey(indexInFull), myIndex);
            fullNode.putKey(null, indexInFull);
          
            myIndex++;
        }
        fullNode.setChildCount(order+1);
        nodeFile.writeNode(fullNode);
        
        /* Enter the extra child */
        putChildFileAddress(extraChildFileAddress, order + 1);
        child(order + 1).setParent(this);
        putKey(extraChildLowKey, order + 1);  
        childCount = order + 1;
        nodeFile.writeNode(this);
    }

    /** Does the tree have the maximum number of children?. <br> 
        Analysis : Time = O(1) */
    public boolean isFull() 
    {
        return (childCount == (2*order + 1));
    }

    /** Set the node file to be nf. <br>
        Analysis : Time = O(1) 
        @param nf The new node file for this node */
    public void setNodeFile(BtreeNodeFileUos nf) 
    {
        nodeFile = nf;
    }

    /** The node file associated with this tree. <br>
        Analysis : Time = O(1) */
    public BtreeNodeFileUos nodeFile() 
    {
        return nodeFile;
    }

    /** Set the data file to be df. <br>
        Analysis : Time = O(1) 
        @param df The new data file for this node */
    public void setDataFile(BtreeBlockFileUos df)
    {
        dataFile = df;
    }
    
    /** The data file associated with this tree. <br>
        Analysis : Time = O(1) */
    public BtreeBlockFileUos dataFile() 
    {
        return dataFile;
    }
    
    /** Set the child count to be nc. <br>
        Analysis : Time = O(1) 
        @param nc The new child count */
    public void setChildCount(int nc)
    {
        childCount = nc;
    }

    /** Assign a boolean value to the leafChild variable. <br>
        Analysis : Time = O(1) 
        @param b The new value of leafChildren */
    public void  setLeafChildren(boolean b)
    {
        leafChildren = b;
    }
 
    /** Return the index for the child that should have the specified key. <br>
        Analysis : Time = O(childCount) 
        @param key The key to obtain an index for */
    public int obtainIndex(Comparable key) 
    {
        for (int i=2; i <= childCount; i++)
        {
            if (key.compareTo(getKey(i)) < 0)
                return i-1;
        }
        return childCount;
    }

    /** Return the ith key. <br> 
        Analysis: Time = O(1) */
    public Comparable getKey(int i) 
    {
        /* The first index for keys is at logical position 2, but since the 
           array starts at 0 the passed in index must be offset. */
        return keys[i-2];
    }

    /** Set the ith key to be newKey. <br> 
        Analysis: Time = O(1) 
        @param newKey The new key value for index i
        @param i The index for the new key */
    public void putKey(Comparable newKey, int i)
    {
        keys[i-2] = newKey;  // See getKey() for explanation of offset
    }

    /** Get the ith child file address. <br>
        Analysis: Time = O(1) 
        @param i The index of the child file address that is returned */
    public long getChildFileAddress(int i)
    {
        /* Logically children are in locations 1 through childCount,
           but the array indexing starts at 0. */
        return childFileAddress[i-1];
    }

    /** Place the block address n in spot i within the childFileAddress array. <br>
        Analysis : Time = O(1) 
        @param n The new block address
        @param i The index of the new block address */ 
    public void putChildFileAddress(long n, int i) 
    {
        /* Logically children are in locations 1 through childCount,
           but the array indexing starts at 0. */
        childFileAddress[i-1] = n;
    }

    /** Return the ith child of this node. <br> 
        Analysis : Time = O(1) + 1 file read.
        @param i The index of the child to retrieve */
    public BtreeNodeUos child(int i) 
    {
        /* Decide in which file to look */
        if (leafChildren)
        {
            BtreeLeafUos leafChild = new BtreeLeafUos(getChildFileAddress(i), dataFile);
            
            /* Set the parent feature */
            leafChild.setParent(this);
            return leafChild;
        }
        else
        {
            /* Read from node file */
            BtreeInteriorUos intChild = nodeFile.readNode(getChildFileAddress(i));
            intChild.setParent(this);
            intChild.setNodeFile(nodeFile);
            intChild.setDataFile(dataFile);
            return intChild;
        }
    }
  
    /** Search appropriate subtree for itemKey, and save 
        the result of the search in fields of the treeHeader. <br>
        Analysis : Time = O(h*order) + O(h) file reads, 
            where h = the height of the Btree rooted at this node. 
        @param itemKey The key of the item being sought
        @param treeHeader The Btree to which this node belongs */
    public void search(Comparable itemKey, BtreeFileUos treeHeader)
    {
        BtreeNodeUos searchChild = child(obtainIndex(itemKey));
        searchChild.search(itemKey, treeHeader);
    }


    /** Does an entry below this node have itemKey for a key. <br>
        Analysis : Time = O(h*order) + O(h) file reads, 
            where h = the height of the Btree rooted at this node. 
        @param itemKey The key of the item to search for */
    public boolean has(Comparable itemKey)
    { 
        BtreeNodeUos searchChild = child(obtainIndex(itemKey));
        return searchChild.has(itemKey);
    }   

    /** Place itemContents into proper subtree with key itemKey, and if a 
        new node was created, return its low value and the node. <br>
        Analysis : O(h*order) + O(h) file reads and writes,
            where h = the height of the tree rooted at this node. 
        @param itemKey The key of the item to be inserted
        @param itemContents The item to be inserted */
    public PairUos insert(Comparable itemKey, Object itemContents, BtreeFileUos treeHeader)
    {
        /* Determine where the new item belongs (in terms of which subtree) */
        int insertionIndex = obtainIndex(itemKey);      
        BtreeNodeUos insertionChild = child(insertionIndex);
        PairUos pair = insertionChild.insert(itemKey, itemContents, treeHeader); 

        if (pair == null)
            return null;
        else
        {
            /* There was a child returned, do something with it. */
            BtreeNodeUos newChild = (BtreeNodeUos) pair.secondItem();
            Comparable newChildLowKey = (Comparable) pair.firstItem();

            if (!isFull())
            {
                /* Shuffle other children over to make room */
                shuffleChildrenRight(insertionIndex+1);
                putChildFileAddress(newChild.fileAddress(), insertionIndex+1);
                child(insertionIndex+1).setParent(this);
                putKey(newChildLowKey, insertionIndex+1);
                childCount++;
                nodeFile.writeNode(this);
                return null;
            } 
            else
            {
                /* Split and return node with larger keys */
                /* First, save the largest (last) child, and insert the new one. */
                Comparable lastChildKey;
                long lastChildAddress;
                if (insertionIndex == (2 * order + 1)) 
                {
                    lastChildAddress = newChild.fileAddress();
                    lastChildKey = newChildLowKey;  
                }  
                else
                {
                    lastChildAddress = getChildFileAddress(childCount);
                    lastChildKey = getKey(childCount);
                    childCount--;
                    shuffleChildrenRight(insertionIndex+1);
                    /* Place newChild where it belongs */
                    putChildFileAddress(newChild.fileAddress(), insertionIndex + 1);
                    newChild.setParent(this);
                    putKey(newChildLowKey, insertionIndex + 1);
                    childCount++;
                }
                /* The lower bound for the key in the extra node is the lower bound
                   for the key of it's first child, that was in location order+2. */
                Comparable keyToPassUp = getKey(order + 2);
                BtreeInteriorUos extraNode = new BtreeInteriorUos(this, lastChildAddress, lastChildKey);
                return new PairUos(keyToPassUp, extraNode);
            } 
        }
    }
 
    /** 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.