binarytree.java

Office格式转换代码

                        Node newNode = new Node(( Comparable ) key,
                                                ( Comparable ) value);

                        insertValue(newNode);
                        node.setRight(newNode, _KEY);
                        newNode.setParent(node, _KEY);
                        doRedBlackInsert(newNode, _KEY);
                        grow();
                        break;
                    }
                }
            }
        }
        return null;
    }

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

    public Object remove(final Object key)
    {
        return doRemove(( Comparable ) key, _KEY);
    }

    /**
     * Removes all mappings from this map
     */

    public void clear()
    {
        modify();
        _size           = 0;
        _root[ _KEY ]   = null;
        _root[ _VALUE ] = null;
    }

    /**
     * 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.
     *
     * @return a set view of the keys contained in this map.
     */

    public Set keySet()
    {
        if (_key_set[ _KEY ] == null)
        {
            _key_set[ _KEY ] = new AbstractSet()
            {
                public Iterator iterator()
                {
                    return new BinaryTreeIterator(_KEY)
                    {
                        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[ _KEY ];
    }

    /**
     * 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.
     *
     * @return a collection view of the values contained in this map.
     */

    public Collection values()
    {
        if (_value_collection[ _KEY ] == null)
        {
            _value_collection[ _KEY ] = new AbstractCollection()
            {
                public Iterator iterator()
                {
                    return new BinaryTreeIterator(_KEY)
                    {
                        protected Object doGetNext()
                        {
                            return _last_returned_node.getData(_VALUE);
                        }
                    };
                }

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

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

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

                    removeValue(o);
                    return _size != old_size;
                }

                public boolean removeAll(Collection c)
                {
                    boolean  modified = false;
                    Iterator iter     = c.iterator();

                    while (iter.hasNext())
                    {
                        if (removeValue(iter.next()) != null)
                        {
                            modified = true;
                        }
                    }
                    return modified;
                }

                public void clear()
                {
                    BinaryTree.this.clear();
                }
            };
        }
        return _value_collection[ _KEY ];
    }

    /**
     * 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.
     *
     * @return a set view of the mappings contained in this map.
     */

    public Set entrySet()
    {
        if (_entry_set[ _KEY ] == null)
        {
            _entry_set[ _KEY ] = new AbstractSet()
            {
                public Iterator iterator()
                {
                    return new BinaryTreeIterator(_KEY)
                    {
                        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    value = entry.getValue();
                    Node      node  = lookup(( Comparable ) entry.getKey(),
                                             _KEY);

                    return (node != null)
                           && node.getData(_VALUE).equals(value);
                }

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

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

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

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

    /* **********  END  implementation of Map ********** */
    private abstract class BinaryTreeIterator
        implements Iterator
    {
        private int    _expected_modifications;
        protected Node _last_returned_node;
        private Node   _next_node;
        private int    _type;

        /**
         * Constructor
         *
         * @param type
         */

        BinaryTreeIterator(final int type)
        {
            _type                   = type;
            _expected_modifications = BinaryTree.this._modifications;
            _last_returned_node     = null;
            _next_node              = leastNode(_root[ _type ], _type);
        }

        /**
         * @return 'next', whatever that means for a given kind of
         *         BinaryTreeIterator
         */

        protected abstract Object doGetNext();

        /* ********** START implementation of Iterator ********** */

        /**
         * @return true if the iterator has more elements.
         */

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

        /**
         * @return the next element in the iteration.
         *
         * @exception NoSuchElementException if iteration has no more
         *                                   elements.
         * @exception ConcurrentModificationException if the
         *                                            BinaryTree is
         *                                            modified behind
         *                                            the iterator's
         *                                            back
         */

        public final Object next()
            throws NoSuchElementException, ConcurrentModificationException
        {
            if (_next_node == null)
            {
                throw new NoSuchElementException();
            }
            if (_modifications != _expected_modifications)
            {
                throw new ConcurrentModificationException();
            }
            _last_returned_node = _next_node;
            _next_node          = nextGreater(_next_node, _type);
            return doGetNext();
        }

        /**
         * Removes from the underlying collection the last element
         * returned by the iterator. This method can be called only
         * once per call to next. The behavior of an iterator is
         * unspecified if the underlying collection is modified while
         * the iteration is in progress in any way other than by
         * calling this method.
         *
         * @exception IllegalStateException if the next method has not
         *                                  yet been called, or the
         *                                  remove method has already
         *                                  been called after the last
         *                                  call to the next method.
         * @exception ConcurrentModificationException if the
         *                                            BinaryTree is
         *                                            modified behind
         *                                            the iterator's
         *                                            back
         */

        public final void remove()
            throws IllegalStateException, ConcurrentModificationException
        {
            if (_last_returned_node == null)
            {
                throw new IllegalStateException();
            }
            if (_modifications != _expected_modifications)
            {
                throw new ConcurrentModificationException();
            }
            doRedBlackDelete(_last_returned_node);
            _expected_modifications++;
            _last_returned_node = null;
        }

        /* **********  END  implementation of Iterator ********** */
    }   // end private abstract class BinaryTreeIterator

    // final for performance
    private static final class Node
        implements Map.Entry
    {
        private Comparable[] _data;
        private Node[]       _left;
        private Node[]       _right;
        private Node[]       _parent;
        private boolean[]    _black;
        private int          _hashcode;
        private boolean      _calculated_hashcode;

        /**
         * Make a new cell with given key and value, and with null
         * links, and black (true) colors.
         *
         * @param key
         * @param value
         */

        Node(final Comparable key, final Comparable value)
        {
            _data                = new Comparable[]
            {
                key, value
            };
            _left                = new Node[]
            {
                null, null
            };
            _right               = new Node[]
            {
                null, null
            };
            _parent