doubleorderedmap.java

初级java程序员如果想要更深一步提高自己的实力

                    return modified;
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return collectionOfValues[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 SUM_OF_INDICES - 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 = rootNode[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 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 descendants 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 == node.getParent(index).getLeft(index)));
    }

    /**
     * is this node its parent's right 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 right child. If the
     * node does exist but has no parent ... no, we're not the
     * non-existent parent's right 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 isRightChild(final Node node, final int index) {

        return (node == null)
               ? true
               : ((node.getParent(index) == null)
                  ? false
                  : (node == node.getParent(index).getRight(index)));
    }

    /**
     * do a rotate left. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param index KEY or VALUE
     */
    private void rotateLeft(final Node node, final int index) {

        Node rightChild = node.getRight(index);

        node.setRight(rightChild.getLeft(index), index);

        if (rightChild.getLeft(index) != null) {
            rightChild.getLeft(index).setParent(node, index);
        }

        rightChild.setParent(node.getParent(index), index);

        if (node.getParent(index) == null) {

            // node was the root ... now its right child is the root
            rootNode[index] = rightChild;
        } else if (node.getParent(index).getLeft(index) == node) {
            node.getParent(index).setLeft(rightChild, index);
        } else {
            node.getParent(index).setRight(rightChild, index);
        }

        rightChild.setLeft(node, index);
        node.setParent(rightChild, index);
    }

    /**