btreeset.java

java 读写word excel ppt

/* ====================================================================
   Licensed to the Apache Software Foundation (ASF) under one or more
   contributor license agreements.  See the NOTICE file distributed with
   this work for additional information regarding copyright ownership.
   The ASF licenses this file to You under the Apache License, Version 2.0
   (the "License"); you may not use this file except in compliance with
   the License.  You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
==================================================================== */
        


package org.apache.poi.hdf.extractor.util;

import java.util.*;


/*
 * A B-Tree like implementation of the java.util.Set inteface.  This is a modifiable set
 * and thus allows elements to be added and removed.  An instance of java.util.Comparator
 * must be provided at construction else all Objects added to the set must implement
 * java.util.Comparable and must be comparable to one another.  No duplicate elements
 * will be allowed in any BTreeSet in accordance with the specifications of the Set interface.
 * Any attempt to add a null element will result in an IllegalArgumentException being thrown.
 * The java.util.Iterator returned by the iterator method guarantees the elements returned
 * are in ascending order.  The Iterator.remove() method is supported.
 * Comment me
 *
 * @author Ryan Ackley 
 *
*/

public class BTreeSet extends AbstractSet implements Set {

    /*
     * Instance Variables
    */
    public BTreeNode root;
    private Comparator comparator = null;
    private int order;
    private int size = 0;

    /*
     *                             Constructors
     * A no-arg constructor is supported in accordance with the specifications of the
     * java.util.Collections interface.  If the order for the B-Tree is not specified
     * at construction it defaults to 32.
    */

    public BTreeSet() {
        this(6);           // Default order for a BTreeSet is 32
    }

    public BTreeSet(Collection c) {
        this(6);           // Default order for a BTreeSet is 32
        addAll(c);
    }

    public BTreeSet(int order) {
        this(order, null);
    }

    public BTreeSet(int order, Comparator comparator) {
        this.order = order;
        this.comparator = comparator;
        root = new BTreeNode(null);
    }


    /*
     * Public Methods
    */
    public boolean add(Object x) throws IllegalArgumentException {
        if (x == null) throw new IllegalArgumentException();
        return root.insert(x, -1);
    }

    public boolean contains(Object x) {
        return root.includes(x);
    }

    public boolean remove(Object x) {
        if (x == null) return false;
        return root.delete(x, -1);
    }

    public int size() {
        return size;
    }

    public void clear() {
        root = new BTreeNode(null);
        size = 0;
    }

    public java.util.Iterator iterator() {
        return new Iterator();
    }


    /*
     * Private methods
    */
    private int compare(Object x, Object y) {
        return (comparator == null ? ((Comparable)x).compareTo(y) : comparator.compare(x, y));
    }



    /*
     * Inner Classes
    */

    /*
     * Guarantees that the Objects are returned in ascending order.  Due to the volatile
     * structure of a B-Tree (many splits, steals and merges can happen in a single call to remove)
     * this Iterator does not attempt to track any concurrent changes that are happening to
     * it's BTreeSet.  Therefore, after every call to BTreeSet.remove or BTreeSet.add a new
     * Iterator should be constructed.  If no new Iterator is constructed than there is a
     * chance of receiving a NullPointerException. The Iterator.delete method is supported.
    */

    private class Iterator implements java.util.Iterator {
        private int index = 0;
        private Stack parentIndex = new Stack(); // Contains all parentIndicies for currentNode
        private Object lastReturned = null;
        private Object next;
        private BTreeNode currentNode;

        Iterator() {
            currentNode = firstNode();
            next = nextElement();
        }

        public boolean hasNext() {
            return next != null;
        }

        public Object next() {
            if (next == null) throw new NoSuchElementException();

            lastReturned = next;
            next = nextElement();
            return lastReturned;
        }

        public void remove() {
            if (lastReturned == null) throw new NoSuchElementException();

            BTreeSet.this.remove(lastReturned);
            lastReturned = null;
        }

        private BTreeNode firstNode() {
            BTreeNode temp = BTreeSet.this.root;

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

            return temp;
        }

        private Object nextElement() {
            if (currentNode.isLeaf()) {
                if (index < currentNode.nrElements) return currentNode.entries[index++].element;

                else if (!parentIndex.empty()) { //All elements have been returned, return successor of lastReturned if it exists
                    currentNode = currentNode.parent;
                    index = ((Integer)parentIndex.pop()).intValue();

                    while (index == currentNode.nrElements) {
                        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;