btreeset.java

Office格式转换代码

/* ====================================================================
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2003 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation" and
 *    "Apache POI" must not be used to endorse or promote products
 *    derived from this software without prior written permission. For
 *    written permission, please contact [e-mail].
 *
 * 5. Products derived from this software may not be called "Apache",
 *    "Apache POI", nor may "Apache" appear in their name, without
 *    prior written permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */


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

import java.util.*;

import org.apache.poi.hdf.model.hdftypes.PropertyNode;

/*
 * 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
{

    /*
     * 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();
    }

    public static ArrayList findProperties(int start, int end, BTreeSet.BTreeNode root)
    {
      ArrayList results = new ArrayList();
      BTreeSet.Entry[] entries = root.entries;

      for(int x = 0; x < entries.length; x++)
      {
        if(entries[x] != null)
        {
          BTreeSet.BTreeNode child = entries[x].child;
          PropertyNode xNode = (PropertyNode)entries[x].element;
          if(xNode != null)
          {
            int xStart = xNode.getStart();
            int xEnd = xNode.getEnd();
            if(xStart < end)
            {
              if(xStart >= start)
              {
                if(child != null)
                {
                  ArrayList beforeItems = findProperties(start, end, child);
                  results.addAll(beforeItems);
                }
                results.add(xNode);
              }
              else if(start < xEnd)
              {
                results.add(xNode);
                //break;
              }
            }
            else
            {
              if(child != null)
              {
                ArrayList beforeItems = findProperties(start, end, child);
                results.addAll(beforeItems);
              }
              break;
            }
          }
          else if(child != null)
          {
            ArrayList afterItems = findProperties(start, end, child);
            results.addAll(afterItems);
          }
        }
        else
        {
          break;
        }
      }
      return results;
    }
    /*
     * 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)