binarytree.java

Office格式转换代码

        if (_value_collection[ _VALUE ] == null)
        {
            _value_collection[ _VALUE ] = new AbstractCollection()
            {
                public Iterator iterator()
                {
                    return new BinaryTreeIterator(_VALUE)
                    {
                        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[ _VALUE ];
    }

    /**
     * common remove logic (remove by key or remove by value)
     *
     * @param o the key, or value, that we're looking for
     * @param index _KEY or _VALUE
     *
     * @return the key, if remove by value, or the value, if remove by
     *         key. null if the specified key or value could not be
     *         found
     */

    private Object doRemove(final Comparable o, final int index)
    {
        Node   node = lookup(o, index);
        Object rval = null;

        if (node != null)
        {
            rval = node.getData(oppositeIndex(index));
            doRedBlackDelete(node);
        }
        return rval;
    }

    /**
     * common get logic, used to get by key or get by value
     *
     * @param o the key or value that we're looking for
     * @param index _KEY or _VALUE
     *
     * @return the key (if the value was mapped) or the value (if the
     *         key was mapped); null if we couldn't find the specified
     *         object
     */

    private Object doGet(final Comparable o, final int index)
    {
        checkNonNullComparable(o, index);
        Node node = lookup(o, index);

        return ((node == null) ? null
                               : node.getData(oppositeIndex(index)));
    }

    /**
     * Get the opposite index of the specified index
     *
     * @param index _KEY or _VALUE
     *
     * @return _VALUE (if _KEY was specified), else _KEY
     */

    private int oppositeIndex(final int index)
    {

        // old trick ... to find the opposite of a value, m or n,
        // subtract the value from the sum of the two possible
        // values. (m + n) - m = n; (m + n) - n = m
        return _INDEX_SUM - index;
    }

    /**
     * do the actual lookup of a piece of data
     *
     * @param data the key or value to be looked up
     * @param index _KEY or _VALUE
     *
     * @return the desired Node, or null if there is no mapping of the
     *         specified data
     */

    private Node lookup(final Comparable data, final int index)
    {
        Node rval = null;
        Node node = _root[ index ];

        while (node != null)
        {
            int cmp = compare(data, node.getData(index));

            if (cmp == 0)
            {
                rval = node;
                break;
            }
            else
            {
                node = (cmp < 0) ? node.getLeft(index)
                                 : node.getRight(index);
            }
        }
        return rval;
    }

    /**
     * Compare two objects
     *
     * @param o1 the first object
     * @param o2 the second object
     *
     * @return negative value if o1 < o2; 0 if o1 == o2; positive
     *         value if o1 > o2
     */

    private static int compare(final Comparable o1, final Comparable o2)
    {
        return (( Comparable ) o1).compareTo(o2);
    }

    /**
     * find the least node from a given node. very useful for starting
     * a sorting iterator ...
     *
     * @param node the node from which we will start searching
     * @param index _KEY or _VALUE
     *
     * @return the smallest node, from the specified node, in the
     *         specified mapping
     */

    private static Node leastNode(final Node node, final int index)
    {
        Node rval = node;

        if (rval != null)
        {
            while (rval.getLeft(index) != null)
            {
                rval = rval.getLeft(index);
            }
        }
        return rval;
    }

    /**
     * get the next larger node from the specified node
     *
     * @param node the node to be searched from
     * @param index _KEY or _VALUE
     *
     * @return the specified node
     */

    private Node nextGreater(final Node node, final int index)
    {
        Node rval = null;

        if (node == null)
        {
            rval = null;
        }
        else if (node.getRight(index) != null)
        {

            // everything to the node's right is larger. The least of
            // the right node's descendents is the next larger node
            rval = leastNode(node.getRight(index), index);
        }
        else
        {

            // traverse up our ancestry until we find an ancestor that
            // is null or one whose left child is our ancestor. If we
            // find a null, then this node IS the largest node in the
            // tree, and there is no greater node. Otherwise, we are
            // the largest node in the subtree on that ancestor's left
            // ... and that ancestor is the next greatest node
            Node parent = node.getParent(index);
            Node child  = node;

            while ((parent != null) && (child == parent.getRight(index)))
            {
                child  = parent;
                parent = parent.getParent(index);
            }
            rval = parent;
        }
        return rval;
    }

    /**
     * copy the color from one node to another, dealing with the fact
     * that one or both nodes may, in fact, be null
     *
     * @param from the node whose color we're copying; may be null
     * @param to the node whose color we're changing; may be null
     * @param index _KEY or _VALUE
     */

    private static void copyColor(final Node from, final Node to,
                                  final int index)
    {
        if (to != null)
        {
            if (from == null)
            {

                // by default, make it black
                to.setBlack(index);
            }
            else
            {
                to.copyColor(from, index);
            }
        }
    }

    /**
     * is the specified node red? if the node does not exist, no, it's
     * black, thank you
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static boolean isRed(final Node node, final int index)
    {
        return ((node == null) ? false
                               : node.isRed(index));
    }

    /**
     * is the specified black red? if the node does not exist, sure,
     * it's black, thank you
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static boolean isBlack(final Node node, final int index)
    {
        return ((node == null) ? true
                               : node.isBlack(index));
    }

    /**
     * force a node (if it exists) red
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static void makeRed(final Node node, final int index)
    {
        if (node != null)
        {
            node.setRed(index);
        }
    }

    /**
     * force a node (if it exists) black
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static void makeBlack(final Node node, final int index)
    {
        if (node != null)
        {
            node.setBlack(index);
        }
    }

    /**
     * get a node's grandparent. mind you, the node, its parent, or
     * its grandparent may not exist. no problem
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static Node getGrandParent(final Node node, final int index)
    {
        return getParent(getParent(node, index), index);
    }

    /**
     * get a node's parent. mind you, the node, or its parent, may not
     * exist. no problem
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static Node getParent(final Node node, final int index)
    {
        return ((node == null) ? null
                               : node.getParent(index));
    }

    /**
     * get a node's right child. mind you, the node may not exist. no
     * problem
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static Node getRightChild(final Node node, final int index)
    {
        return (node == null) ? null
                              : node.getRight(index);
    }

    /**
     * get a node's left child. mind you, the node may not exist. no
     * problem
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static Node getLeftChild(final Node node, final int index)
    {
        return (node == null) ? null
                              : node.getLeft(index);
    }

    /**
     * is this node its parent's left child? mind you, the node, or
     * its parent, may not exist. no problem. if the node doesn't
     * exist ... it's its non-existent parent's left child. If the
     * node does exist but has no parent ... no, we're not the
     * non-existent parent's left child. Otherwise (both the specified
     * node AND its parent exist), check.
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static boolean isLeftChild(final Node node, final int index)
    {
        return (node == null) ? true
                              : ((node.getParent(index) == null) ? false
                                                                 : (node