btreeset.java

Office格式转换代码

                    {
                        if (parentIndex.empty()) break;
                        currentNode = currentNode.parent;
                        index = ((Integer)parentIndex.pop()).intValue();
                    }

                    if (index == currentNode.nrElements) return null; //Reached root and he has no more children
                    return currentNode.entries[index++].element;
                }

                else
                { //Your a leaf and the root
                    if (index == currentNode.nrElements) return null;
                    return currentNode.entries[index++].element;
                }
            }

            else
            { //Your not a leaf so simply find and return the successor of lastReturned
                currentNode = currentNode.entries[index].child;
                parentIndex.push(new Integer(index));

                while (currentNode.entries[0].child != null)
                {
                    currentNode = currentNode.entries[0].child;
                    parentIndex.push(new Integer(0));
                }

                index = 1;
                return currentNode.entries[0].element;
            }
        }
    }


    public static class Entry
    {

        public Object element;
        public BTreeNode child;
    }


    public class BTreeNode
    {

        public Entry[] entries;
        public BTreeNode parent;
        private int nrElements = 0;
        private final int MIN = (BTreeSet.this.order - 1) / 2;

        BTreeNode(BTreeNode parent)
        {
            this.parent = parent;
            entries = new Entry[BTreeSet.this.order];
            entries[0] = new Entry();
        }

        boolean insert(Object x, int parentIndex)
        {
            if (isFull())
            { // If full, you must split and promote splitNode before inserting
                Object splitNode = entries[nrElements / 2].element;
                BTreeNode rightSibling = split();

                if (isRoot())
                { // Grow a level
                    splitRoot(splitNode, this, rightSibling);
                    // Determine where to insert
                    if (BTreeSet.this.compare(x, BTreeSet.this.root.entries[0].element) < 0) insert(x, 0);
                    else rightSibling.insert(x, 1);
                }

                else
                { // Promote splitNode
                    parent.insertSplitNode(splitNode, this, rightSibling, parentIndex);
                    if (BTreeSet.this.compare(x, parent.entries[parentIndex].element) < 0) return insert(x, parentIndex);
                    else return rightSibling.insert(x, parentIndex + 1);
                }
            }

            else if (isLeaf())
            { // If leaf, simply insert the non-duplicate element
                int insertAt = childToInsertAt(x, true);
                if (insertAt == -1) return false; // Determine if the element already exists
                else
                {
                    insertNewElement(x, insertAt);
                    BTreeSet.this.size++;
                    return true;
                }
            }

            else
            { // If not full and not leaf recursively find correct node to insert at
                int insertAt = childToInsertAt(x, true);
                return (insertAt == -1 ? false : entries[insertAt].child.insert(x, insertAt));
            }
            return false;
        }

        boolean includes(Object x)
        {
            int index = childToInsertAt(x, true);
            if (index == -1) return true;
            if (entries[index] == null || entries[index].child == null) return false;
            return entries[index].child.includes(x);
        }

        boolean delete(Object x, int parentIndex)
        {
            int i = childToInsertAt(x, true);
            int priorParentIndex = parentIndex;
            BTreeNode temp = this;
            if (i != -1)
            {
                do
                {
                    if (temp.entries[i] == null || temp.entries[i].child == null) return false;
                    temp = temp.entries[i].child;
                    priorParentIndex = parentIndex;
                    parentIndex = i;
                    i = temp.childToInsertAt(x, true);
                } while (i != -1);
            } // Now temp contains element to delete and temp's parentIndex is parentIndex

            if (temp.isLeaf())
            { // If leaf and have more than MIN elements, simply delete
                if (temp.nrElements > MIN)
                {
                    temp.deleteElement(x);
                    BTreeSet.this.size--;
                    return true;
                }

                else
                { // If leaf and have less than MIN elements, than prepare the BTreeSet for deletion
                    temp.prepareForDeletion(parentIndex);
                    temp.deleteElement(x);
                    BTreeSet.this.size--;
                    temp.fixAfterDeletion(priorParentIndex);
                    return true;
                }
            }

            else
            { // Only delete at leaf so first switch with successor than delete
                temp.switchWithSuccessor(x);
                parentIndex = temp.childToInsertAt(x, false) + 1;
                return temp.entries[parentIndex].child.delete(x, parentIndex);
            }
        }


        private boolean isFull() { return nrElements == (BTreeSet.this.order - 1); }

        private boolean isLeaf() { return entries[0].child == null; }

        private boolean isRoot() { return parent == null; }

        /*
         * Splits a BTreeNode into two BTreeNodes, removing the splitNode from the
         * calling BTreeNode.
        */
        private BTreeNode split()
        {
            BTreeNode rightSibling = new BTreeNode(parent);
            int index = nrElements / 2;
            entries[index++].element = null;

            for (int i = 0, nr = nrElements; index <= nr; i++, index++)
            {
                rightSibling.entries[i] = entries[index];
                if (rightSibling.entries[i] != null && rightSibling.entries[i].child != null)
                    rightSibling.entries[i].child.parent = rightSibling;
                entries[index] = null;
                nrElements--;
                rightSibling.nrElements++;
            }

            rightSibling.nrElements--; // Need to correct for copying the last Entry which has a null element and a child
            return rightSibling;
        }

        /*
         * Creates a new BTreeSet.root which contains only the splitNode and pointers
         * to it's left and right child.
        */
        private void splitRoot(Object splitNode, BTreeNode left, BTreeNode right)
        {
            BTreeNode newRoot = new BTreeNode(null);
            newRoot.entries[0].element = splitNode;
            newRoot.entries[0].child = left;
            newRoot.entries[1] = new Entry();
            newRoot.entries[1].child = right;
            newRoot.nrElements = 1;
            left.parent = right.parent = newRoot;
            BTreeSet.this.root = newRoot;
        }

        private void insertSplitNode(Object splitNode, BTreeNode left, BTreeNode right, int insertAt)
        {
            for (int i = nrElements; i >= insertAt; i--) entries[i + 1] = entries[i];

            entries[insertAt] = new Entry();
            entries[insertAt].element = splitNode;
            entries[insertAt].child = left;
            entries[insertAt + 1].child = right;

            nrElements++;
        }

        private void insertNewElement(Object x, int insertAt)
        {

            for (int i = nrElements; i > insertAt; i--) entries[i] = entries[i - 1];

            entries[insertAt] = new Entry();
            entries[insertAt].element = x;

            nrElements++;
        }

        /*
         * Possibly a deceptive name for a pretty cool method.  Uses binary search
         * to determine the postion in entries[] in which to traverse to find the correct
         * BTreeNode in which to insert a new element.  If the element exists in the calling
         * BTreeNode than -1 is returned.  When the parameter position is true and the element
         * is present in the calling BTreeNode -1 is returned, if position is false and the
         * element is contained in the calling BTreeNode than the position of the element
         * in entries[] is returned.
        */
        private int childToInsertAt(Object x, boolean position)
        {
            int index = nrElements / 2;

            if (entries[index] == null || entries[index].element == null) return index;

            int lo = 0, hi = nrElements - 1;
            while (lo <= hi)
            {
                if (BTreeSet.this.compare(x, entries[index].element) > 0)
                {
                    lo = index + 1;
                    index = (hi + lo) / 2;
                }
                else
                {
                    hi = index - 1;
                    index = (hi + lo) / 2;
                }
            }

            hi++;
            if (entries[hi] == null || entries[hi].element == null) return hi;
            return (!position ? hi : BTreeSet.this.compare(x, entries[hi].element) == 0 ? -1 : hi);
        }


        private void deleteElement(Object x)
        {
            int index = childToInsertAt(x, false);
            for (; index < (nrElements - 1); index++) entries[index] = entries[index + 1];

            if (nrElements == 1) entries[index] = new Entry(); // This is root and it is empty
            else entries[index] = null;

            nrElements--;
        }

        private void prepareForDeletion(int parentIndex)
        {
            if (isRoot()) return; // Don't attempt to steal or merge if your the root

            // If not root then try to steal left
            else if (parentIndex != 0 && parent.entries[parentIndex - 1].child.nrElements > MIN)
            {
                stealLeft(parentIndex);
                return;
            }

            // If not root and can't steal left try to steal right
            else if (parentIndex < entries.length && parent.entries[parentIndex + 1] != null && parent.entries[parentIndex + 1].child != null && parent.entries[parentIndex + 1].child.nrElements > MIN)
            {
                    stealRight(parentIndex);
                    return;
            }

            // If not root and can't steal left or right then try to merge left
            else if (parentIndex != 0) {
                mergeLeft(parentIndex);
                return;
            }