binarytree.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.util;

import java.util.*;

/**
 * Red-Black tree-based implementation of Map. This class guarantees
 * that the map will be in both ascending key order and ascending
 * value order, sorted according to the natural order for the key's
 * and value's classes.<p>
 *
 * This Map is intended for applications that need to be able to look
 * up a key-value pairing by either key or value, and need to do so
 * with equal efficiency.<p>
 *
 * While that goal could be accomplished by taking a pair of TreeMaps
 * and redirecting requests to the appropriate TreeMap (e.g.,
 * containsKey would be directed to the TreeMap that maps values to
 * keys, containsValue would be directed to the TreeMap that maps keys
 * to values), there are problems with that implementation,
 * particularly when trying to keep the two TreeMaps synchronized with
 * each other. And if the data contained in the TreeMaps is large, the
 * cost of redundant storage becomes significant.<p>
 *
 * This solution keeps the data properly synchronized and minimizes
 * the data storage. The red-black algorithm is based on TreeMap's,
 * but has been modified to simultaneously map a tree node by key and
 * by value. This doubles the cost of put operations (but so does
 * using two TreeMaps), and nearly doubles the cost of remove
 * operations (there is a savings in that the lookup of the node to be
 * removed only has to be performed once). And since only one node
 * contains the key and value, storage is significantly less than that
 * required by two TreeMaps.<p>
 *
 * There are some limitations placed on data kept in this Map. The
 * biggest one is this:<p>
 *
 * When performing a put operation, neither the key nor the value may
 * already exist in the Map. In the java.util Map implementations
 * (HashMap, TreeMap), you can perform a put with an already mapped
 * key, and neither cares about duplicate values at all ... but this
 * implementation's put method with throw an IllegalArgumentException
 * if either the key or the value is already in the Map.<p>
 *
 * Obviously, that same restriction (and consequence of failing to
 * heed that restriction) applies to the putAll method.<p>
 *
 * The Map.Entry instances returned by the appropriate methods will
 * not allow setValue() and will throw an
 * UnsupportedOperationException on attempts to call that method.<p>
 *
 * New methods are added to take advantage of the fact that values are
 * kept sorted independently of their keys:<p>
 *
 * Object getKeyForValue(Object value) is the opposite of get; it
 * takes a value and returns its key, if any.<p>
 *
 * Object removeValue(Object value) finds and removes the specified
 * value and returns the now un-used key.<p>
 *
 * Set entrySetByValue() returns the Map.Entry's in a Set whose
 * iterator will iterate over the Map.Entry's in ascending order by
 * their corresponding values.<p>
 *
 * Set keySetByValue() returns the keys in a Set whose iterator will
 * iterate over the keys in ascending order by their corresponding
 * values.<p>
 *
 * Collection valuesByValue() returns the values in a Collection whose
 * iterator will iterate over the values in ascending order.<p>
 *
 * @author Marc Johnson (mjohnson at apache dot org)
 */
public final class BinaryTree   // final for performance

    extends AbstractMap
{
    private Node[]                _root             = new Node[]
    {
        null, null
    };
    private int                   _size             = 0;
    private int                   _modifications    = 0;
    private Set[]                 _key_set          = new Set[]
    {
        null, null
    };
    private Set[]                 _entry_set        = new Set[]
    {
        null, null
    };
    private Collection[]          _value_collection = new Collection[]
    {
        null, null
    };
    private static final int      _KEY              = 0;
    private static final int      _VALUE            = 1;
    private static final int      _INDEX_SUM        = _KEY + _VALUE;
    private static final int      _MINIMUM_INDEX    = 0;
    private static final int      _INDEX_COUNT      = 2;
    private static final String[] _data_name        = new String[]
    {
        "key", "value"
    };

    /**
     * Construct a new BinaryTree
     */

    public BinaryTree()
    {
    }

    /**
     * Constructs a new BinaryTree from an existing Map, with keys and
     * values sorted
     *
     * @param map the map whose mappings are to be placed in this map.
     *
     * @exception ClassCastException if the keys in the map are not
     *                               Comparable, or are not mutually
     *                               comparable; also if the values in
     *                               the map are not Comparable, or
     *                               are not mutually Comparable
     * @exception NullPointerException if any key or value in the map
     *                                 is null
     * @exception IllegalArgumentException if there are duplicate keys
     *                                     or duplicate values in the
     *                                     map
     */

    public BinaryTree(final Map map)
        throws ClassCastException, NullPointerException,
                IllegalArgumentException
    {
        putAll(map);
    }

    /**
     * Returns the key to which this map maps the specified value.
     * Returns null if the map contains no mapping for this value.
     *
     * @param value value whose associated key is to be returned.
     *
     * @return the key to which this map maps the specified value, or
     *         null if the map contains no mapping for this value.
     *
     * @exception ClassCastException if the value is of an
     *                               inappropriate type for this map.
     * @exception NullPointerException if the value is null
     */

    public Object getKeyForValue(final Object value)
        throws ClassCastException, NullPointerException
    {
        return doGet(( Comparable ) value, _VALUE);
    }

    /**
     * Removes the mapping for this value from this map if present
     *
     * @param value value whose mapping is to be removed from the map.
     *
     * @return previous key associated with specified value, or null
     *         if there was no mapping for value.
     */

    public Object removeValue(final Object value)
    {
        return doRemove(( Comparable ) value, _VALUE);
    }

    /**
     * Returns a set view of the mappings contained in this map. Each
     * element in the returned set is a Map.Entry. The set is backed
     * by the map, so changes to the map are reflected in the set, and
     * vice-versa.  If the map is modified while an iteration over the
     * set is in progress, the results of the iteration are
     * undefined. The set supports element removal, which removes the
     * corresponding mapping from the map, via the Iterator.remove,
     * Set.remove, removeAll, retainAll and clear operations.  It does
     * not support the add or addAll operations.<p>
     *
     * The difference between this method and entrySet is that
     * entrySet's iterator() method returns an iterator that iterates
     * over the mappings in ascending order by key. This method's
     * iterator method iterates over the mappings in ascending order
     * by value.
     *
     * @return a set view of the mappings contained in this map.
     */

    public Set entrySetByValue()
    {
        if (_entry_set[ _VALUE ] == null)
        {
            _entry_set[ _VALUE ] = new AbstractSet()
            {
                public Iterator iterator()
                {
                    return new BinaryTreeIterator(_VALUE)
                    {
                        protected Object doGetNext()
                        {
                            return _last_returned_node;
                        }
                    };
                }

                public boolean contains(Object o)
                {
                    if (!(o instanceof Map.Entry))
                    {
                        return false;
                    }
                    Map.Entry entry = ( Map.Entry ) o;
                    Object    key   = entry.getKey();
                    Node      node  = lookup(( Comparable ) entry.getValue(),
                                             _VALUE);

                    return (node != null) && node.getData(_KEY).equals(key);
                }

                public boolean remove(Object o)
                {
                    if (!(o instanceof Map.Entry))
                    {
                        return false;
                    }
                    Map.Entry entry = ( Map.Entry ) o;
                    Object    key   = entry.getKey();
                    Node      node  = lookup(( Comparable ) entry.getValue(),
                                             _VALUE);

                    if ((node != null) && node.getData(_KEY).equals(key))
                    {
                        doRedBlackDelete(node);
                        return true;
                    }
                    return false;
                }

                public int size()
                {
                    return BinaryTree.this.size();
                }

                public void clear()
                {
                    BinaryTree.this.clear();
                }
            };
        }
        return _entry_set[ _VALUE ];
    }

    /**
     * Returns a set view of the keys contained in this map.  The set
     * is backed by the map, so changes to the map are reflected in
     * the set, and vice-versa. If the map is modified while an
     * iteration over the set is in progress, the results of the
     * iteration are undefined. The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
     * operations. It does not support the add or addAll
     * operations.<p>
     *
     * The difference between this method and keySet is that keySet's
     * iterator() method returns an iterator that iterates over the
     * keys in ascending order by key. This method's iterator method
     * iterates over the keys in ascending order by value.
     *
     * @return a set view of the keys contained in this map.
     */

    public Set keySetByValue()
    {
        if (_key_set[ _VALUE ] == null)
        {
            _key_set[ _VALUE ] = new AbstractSet()
            {
                public Iterator iterator()
                {
                    return new BinaryTreeIterator(_VALUE)
                    {
                        protected Object doGetNext()
                        {
                            return _last_returned_node.getData(_KEY);
                        }
                    };
                }

                public int size()
                {
                    return BinaryTree.this.size();
                }

                public boolean contains(Object o)
                {
                    return containsKey(o);
                }

                public boolean remove(Object o)
                {
                    int old_size = _size;

                    BinaryTree.this.remove(o);
                    return _size != old_size;
                }

                public void clear()
                {
                    BinaryTree.this.clear();
                }
            };
        }
        return _key_set[ _VALUE ];
    }

    /**
     * Returns a collection view of the values contained in this
     * map. The collection is backed by the map, so changes to the map
     * are reflected in the collection, and vice-versa. If the map is
     * modified while an iteration over the collection is in progress,
     * the results of the iteration are undefined. The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the Iterator.remove,
     * Collection.remove, removeAll, retainAll and clear operations.
     * It does not support the add or addAll operations.<p>
     *
     * The difference between this method and values is that values's
     * iterator() method returns an iterator that iterates over the
     * values in ascending order by key. This method's iterator method
     * iterates over the values in ascending order by key.
     *
     * @return a collection view of the values contained in this map.
     */

    public Collection valuesByValue()
    {