binarytree.java

Office格式转换代码

            {
                y.setLeft(x, index);
                y.setRight(x_old_right_child, index);
            }
            else
            {
                y.setRight(x, index);
                y.setLeft(x_old_left_child, index);
            }
        }
        else
        {
            x.setParent(y_old_parent, index);
            if (y_old_parent != null)
            {
                if (y_was_left_child)
                {
                    y_old_parent.setLeft(x, index);
                }
                else
                {
                    y_old_parent.setRight(x, index);
                }
            }
            y.setLeft(x_old_left_child, index);
            y.setRight(x_old_right_child, index);
        }
        if (y == x_old_parent)
        {   // y was x's parent
            y.setParent(x, index);
            if (x_was_left_child)
            {
                x.setLeft(y, index);
                x.setRight(y_old_right_child, index);
            }
            else
            {
                x.setRight(y, index);
                x.setLeft(y_old_left_child, index);
            }
        }
        else
        {
            y.setParent(x_old_parent, index);
            if (x_old_parent != null)
            {
                if (x_was_left_child)
                {
                    x_old_parent.setLeft(y, index);
                }
                else
                {
                    x_old_parent.setRight(y, index);
                }
            }
            x.setLeft(y_old_left_child, index);
            x.setRight(y_old_right_child, index);
        }

        // Fix children's parent pointers
        if (x.getLeft(index) != null)
        {
            x.getLeft(index).setParent(x, index);
        }
        if (x.getRight(index) != null)
        {
            x.getRight(index).setParent(x, index);
        }
        if (y.getLeft(index) != null)
        {
            y.getLeft(index).setParent(y, index);
        }
        if (y.getRight(index) != null)
        {
            y.getRight(index).setParent(y, index);
        }
        x.swapColors(y, index);

        // Check if _root changed
        if (_root[ index ] == x)
        {
            _root[ index ] = y;
        }
        else if (_root[ index ] == y)
        {
            _root[ index ] = x;
        }
    }

    /**
     * check if an object is fit to be proper input ... has to be
     * Comparable and non-null
     *
     * @param o the object being checked
     * @param index _KEY or _VALUE (used to put the right word in the
     *              exception message)
     *
     * @exception NullPointerException if o is null
     * @exception ClassCastException if o is not Comparable
     */

    private static void checkNonNullComparable(final Object o,
                                               final int index)
    {
        if (o == null)
        {
            throw new NullPointerException(_data_name[ index ]
                                           + " cannot be null");
        }
        if (!(o instanceof Comparable))
        {
            throw new ClassCastException(_data_name[ index ]
                                         + " must be Comparable");
        }
    }

    /**
     * check a key for validity (non-null and implements Comparable)
     *
     * @param key the key to be checked
     *
     * @exception NullPointerException if key is null
     * @exception ClassCastException if key is not Comparable
     */

    private static void checkKey(final Object key)
    {
        checkNonNullComparable(key, _KEY);
    }

    /**
     * check a value for validity (non-null and implements Comparable)
     *
     * @param value the value to be checked
     *
     * @exception NullPointerException if value is null
     * @exception ClassCastException if value is not Comparable
     */

    private static void checkValue(final Object value)
    {
        checkNonNullComparable(value, _VALUE);
    }

    /**
     * check a key and a value for validity (non-null and implements
     * Comparable)
     *
     * @param key the key to be checked
     * @param value the value to be checked
     *
     * @exception NullPointerException if key or value is null
     * @exception ClassCastException if key or value is not Comparable
     */

    private static void checkKeyAndValue(final Object key, final Object value)
    {
        checkKey(key);
        checkValue(value);
    }

    /**
     * increment the modification count -- used to check for
     * concurrent modification of the map through the map and through
     * an Iterator from one of its Set or Collection views
     */

    private void modify()
    {
        _modifications++;
    }

    /**
     * bump up the size and note that the map has changed
     */

    private void grow()
    {
        modify();
        _size++;
    }

    /**
     * decrement the size and note that the map has changed
     */

    private void shrink()
    {
        modify();
        _size--;
    }

    /**
     * insert a node by its value
     *
     * @param newNode the node to be inserted
     *
     * @exception IllegalArgumentException if the node already exists
     *                                     in the value mapping
     */

    private void insertValue(final Node newNode)
        throws IllegalArgumentException
    {
        Node node = _root[ _VALUE ];

        while (true)
        {
            int cmp = compare(newNode.getData(_VALUE), node.getData(_VALUE));

            if (cmp == 0)
            {
                throw new IllegalArgumentException(
                    "Cannot store a duplicate value (\""
                    + newNode.getData(_VALUE) + "\") in this Map");
            }
            else if (cmp < 0)
            {
                if (node.getLeft(_VALUE) != null)
                {
                    node = node.getLeft(_VALUE);
                }
                else
                {
                    node.setLeft(newNode, _VALUE);
                    newNode.setParent(node, _VALUE);
                    doRedBlackInsert(newNode, _VALUE);
                    break;
                }
            }
            else
            {   // cmp > 0
                if (node.getRight(_VALUE) != null)
                {
                    node = node.getRight(_VALUE);
                }
                else
                {
                    node.setRight(newNode, _VALUE);
                    newNode.setParent(node, _VALUE);
                    doRedBlackInsert(newNode, _VALUE);
                    break;
                }
            }
        }
    }

    /* ********** START implementation of Map ********** */

    /**
     * Returns the number of key-value mappings in this map. If the
     * map contains more than Integer.MAX_VALUE elements, returns
     * Integer.MAX_VALUE.
     *
     * @return the number of key-value mappings in this map.
     */

    public int size()
    {
        return _size;
    }

    /**
     * Returns true if this map contains a mapping for the specified
     * key.
     *
     * @param key key whose presence in this map is to be tested.
     *
     * @return true if this map contains a mapping for the specified
     *         key.
     *
     * @exception ClassCastException if the key is of an inappropriate
     *                               type for this map.
     * @exception NullPointerException if the key is null
     */

    public boolean containsKey(final Object key)
        throws ClassCastException, NullPointerException
    {
        checkKey(key);
        return lookup(( Comparable ) key, _KEY) != null;
    }

    /**
     * Returns true if this map maps one or more keys to the
     * specified value.
     *
     * @param value value whose presence in this map is to be tested.
     *
     * @return true if this map maps one or more keys to the specified
     *         value.
     */

    public boolean containsValue(final Object value)
    {
        checkValue(value);
        return lookup(( Comparable ) value, _VALUE) != null;
    }

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

    public Object get(final Object key)
        throws ClassCastException, NullPointerException
    {
        return doGet(( Comparable ) key, _KEY);
    }

    /**
     * Associates the specified value with the specified key in this
     * map.
     *
     * @param key key with which the specified value is to be
     *            associated.
     * @param value value to be associated with the specified key.
     *
     * @return null
     *
     * @exception ClassCastException if the class of the specified key
     *                               or value prevents it from being
     *                               stored in this map.
     * @exception NullPointerException if the specified key or value
     *                                 is null
     * @exception IllegalArgumentException if the key duplicates an
     *                                     existing key, or if the
     *                                     value duplicates an
     *                                     existing value
     */

    public Object put(final Object key, final Object value)
        throws ClassCastException, NullPointerException,
                IllegalArgumentException
    {
        checkKeyAndValue(key, value);
        Node node = _root[ _KEY ];

        if (node == null)
        {
            Node root = new Node(( Comparable ) key, ( Comparable ) value);

            _root[ _KEY ]   = root;
            _root[ _VALUE ] = root;
            grow();
        }
        else
        {
            while (true)
            {
                int cmp = compare(( Comparable ) key, node.getData(_KEY));

                if (cmp == 0)
                {
                    throw new IllegalArgumentException(
                        "Cannot store a duplicate key (\"" + key
                        + "\") in this Map");
                }
                else if (cmp < 0)
                {
                    if (node.getLeft(_KEY) != null)
                    {
                        node = node.getLeft(_KEY);
                    }
                    else
                    {
                        Node newNode = new Node(( Comparable ) key,
                                                ( Comparable ) value);

                        insertValue(newNode);
                        node.setLeft(newNode, _KEY);
                        newNode.setParent(node, _KEY);
                        doRedBlackInsert(newNode, _KEY);
                        grow();
                        break;
                    }
                }
                else
                {   // cmp > 0
                    if (node.getRight(_KEY) != null)
                    {
                        node = node.getRight(_KEY);
                    }
                    else
                    {