treebidimap.java

iBATIS似乎已远离众说纷纭的OR框架之列

                    if (isBlack(getRightChild(siblingNode, index), index)) {
                        makeBlack(getLeftChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateRight(siblingNode, index);

                        siblingNode = getRightChild(getParent(currentNode, index), index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode, index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getRightChild(siblingNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            } else {
                Node siblingNode = getLeftChild(getParent(currentNode, index), index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    siblingNode = getLeftChild(getParent(currentNode, index), index);
                }

                if (isBlack(getRightChild(siblingNode, index), index)
                    && isBlack(getLeftChild(siblingNode, index), index)) {
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getLeftChild(siblingNode, index), index)) {
                        makeBlack(getRightChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateLeft(siblingNode, index);

                        siblingNode = getLeftChild(getParent(currentNode, index), index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode, index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getLeftChild(siblingNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            }
        }

        makeBlack(currentNode, index);
    }

    /**
     * swap two nodes (except for their content), taking care of
     * special cases where one is the other's parent ... hey, it
     * happens.
     *
     * @param x one node
     * @param y another node
     * @param index  the KEY or VALUE int
     */
    private void swapPosition(final Node x, final Node y, final int index) {
        // Save initial values.
        Node xFormerParent = x.getParent(index);
        Node xFormerLeftChild = x.getLeft(index);
        Node xFormerRightChild = x.getRight(index);
        Node yFormerParent = y.getParent(index);
        Node yFormerLeftChild = y.getLeft(index);
        Node yFormerRightChild = y.getRight(index);
        boolean xWasLeftChild = (x.getParent(index) != null) && (x == x.getParent(index).getLeft(index));
        boolean yWasLeftChild = (y.getParent(index) != null) && (y == y.getParent(index).getLeft(index));

        // Swap, handling special cases of one being the other's parent.
        if (x == yFormerParent) { // x was y's parent
            x.setParent(y, index);

            if (yWasLeftChild) {
                y.setLeft(x, index);
                y.setRight(xFormerRightChild, index);
            } else {
                y.setRight(x, index);
                y.setLeft(xFormerLeftChild, index);
            }
        } else {
            x.setParent(yFormerParent, index);

            if (yFormerParent != null) {
                if (yWasLeftChild) {
                    yFormerParent.setLeft(x, index);
                } else {
                    yFormerParent.setRight(x, index);
                }
            }

            y.setLeft(xFormerLeftChild, index);
            y.setRight(xFormerRightChild, index);
        }

        if (y == xFormerParent) { // y was x's parent
            y.setParent(x, index);

            if (xWasLeftChild) {
                x.setLeft(y, index);
                x.setRight(yFormerRightChild, index);
            } else {
                x.setRight(y, index);
                x.setLeft(yFormerLeftChild, index);
            }
        } else {
            y.setParent(xFormerParent, index);

            if (xFormerParent != null) {
                if (xWasLeftChild) {
                    xFormerParent.setLeft(y, index);
                } else {
                    xFormerParent.setRight(y, index);
                }
            }

            x.setLeft(yFormerLeftChild, index);
            x.setRight(yFormerRightChild, 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 (rootNode[index] == x) {
            rootNode[index] = y;
        } else if (rootNode[index] == y) {
            rootNode[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  the KEY or VALUE int (used to put the right word in the
     *              exception message)
     *
     * @throws NullPointerException if o is null
     * @throws ClassCastException if o is not Comparable
     */
    private static void checkNonNullComparable(final Object o, final int index) {
        if (o == null) {
            throw new NullPointerException(dataName[index] + " cannot be null");
        }
        if (!(o instanceof Comparable)) {
            throw new ClassCastException(dataName[index] + " must be Comparable");
        }
    }

    /**
     * check a key for validity (non-null and implements Comparable)
     *
     * @param key the key to be checked
     *
     * @throws NullPointerException if key is null
     * @throws 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
     *
     * @throws NullPointerException if value is null
     * @throws 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
     *
     * @throws NullPointerException if key or value is null
     * @throws 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();
        nodeCount++;
    }

    /**
     * decrement the size and note that the map has changed
     */
    private void shrink() {
        modify();
        nodeCount--;
    }

    /**
     * insert a node by its value
     *
     * @param newNode the node to be inserted
     *
     * @throws IllegalArgumentException if the node already exists
     *                                     in the value mapping
     */
    private void insertValue(final Node newNode) throws IllegalArgumentException {
        Node node = rootNode[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;
                }
            }
        }
    }
    
    //-----------------------------------------------------------------------
    /**
     * Compares for equals as per the API.
     *
     * @param obj  the object to compare to
     * @param type  the KEY or VALUE int
     * @return true if equal
     */
    private boolean doEquals(Object obj, final int type) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof Map == false) {
            return false;
        }
        Map other = (Map) obj;
        if (other.size() != size()) {
            return false;
        }

        if (nodeCount > 0) {
            try {
                for (MapIterator it = new ViewMapIterator(this, type); it.hasNext(); ) {
                    Object key = it.next();
                    Object value = it.getValue();
                    if (value.equals(other.get(key)) == false) {
                        return false;
                    }
                }
            } catch (ClassCastException ex) {
                return false;
            } catch (NullPointerException ex) {
                return false;
            }
        }
        return true;
    }

    /**
     * Gets the hash code value for this map as per the API.
     *
     * @param type  the KEY or VALUE int
     * @return the hash code value for this map
     */
    private int doHashCode(final int type) {
        int total = 0;
        if (nodeCount > 0) {
            for (MapIterator it = new ViewMapIterator(this, type); it.hasNext(); ) {
                Object key = it.next();
                Object value = it.getValue();
                total += (key.hashCode() ^ value.hashCode());
            }
        }
        return total;
    }
    
    /**
     * Gets the string form of this map as per AbstractMap.
     *
     * @param type  the KEY or VALUE int
     * @return the string form of this map
     */
    private String doToString(final int type) {
        if (nodeCount == 0) {
            return "{}";
        }
        StringBuffer buf = new StringBuffer(nodeCount * 32);
        buf.append('{');
        MapIterator it = new ViewMapIterator(this, type);
        boolean hasNext = it.hasNext();
        while (hasNext) {
            Object key = it.next();
            Object value = it.getValue();
            buf.append(key == this ? "(this Map)" : key)
               .append('=')
               .append(value == this ? "(this Map)" : value);

            hasNext = it.hasNext();
            if (hasNext) {
                buf.append(", ");
            }
        }

        buf.append('}');
        return buf.toString();
    }

    //-----------------------------------------------------------------------
    /**
     * A view of this map.