basetreemapimpl.java

Java的面向对象数据库系统的源代码

//            values = BaseTreeMapImpl_valuesFactory.getDefault.create(self());
            values = (Collection) database().createObject(
                    _BaseTreeMap_values.class,
                    new Class[] {BaseTreeMap.class},
                    new Object[] {self()}
            );
        }
        return values;
    }

    /**
     * <p>DO NOT USE THIS METHOD DIRECTLY!</p><p>Must unfortunately be
     * public because of the proxy structure ozone uses combined with the fact
     * that java does not support protected or package methods in interfaces.
     * This method needs to be callable from iterators, submaps, etc./p>
     *
     * @param o1 the first object
     * @param o2 the second object
     * @throws ClassCastException if o1 and o2 are not mutually comparable,
     *         or are not Comparable with natural ordering
     * @throws NullPointerException if o1 or o2 is null with natural ordering
     */
    public final int _org_ozoneDB_compare(Object o1, Object o2) {
        return comparator == null ? ((Comparable) o1).compareTo(o2) : comparator.compare(o1, o2);
    }

    /**
     * Maintain red-black balance after deleting a node.
     *
     * @param node the child of the node just deleted, possibly nil
     * @param parent the parent of the node just deleted, never nil
     */
    private void deleteFixup(BaseTreeMap.Node node, BaseTreeMap.Node parent) {
        // if (parent == nil)
        //   throw new InternalError();
        // If a black node has been removed, we need to rebalance to avoid
        // violating the "same number of black nodes on any path" rule. If
        // node is red, we can simply recolor it black and all is well.
        while (!node.equals(root) && (node.getColor() == BaseTreeMap.Node.BLACK)) {
            if (node.equals(parent.getLeft())) {
                // Rebalance left side.
                BaseTreeMap.Node sibling = parent.getRight();
                // if (sibling == nil)
                //   throw new InternalError();
                if (sibling.getColor() == BaseTreeMap.Node.RED) {
                    // Case 1: Sibling is red.
                    // Recolor sibling and parent, and rotate parent left.
                    sibling.setColor(BaseTreeMap.Node.BLACK);
                    parent.setColor(BaseTreeMap.Node.RED);
                    rotateLeft(parent);
                    sibling = parent.getRight();
                }

                if ((sibling.getLeft().getColor() == BaseTreeMap.Node.BLACK) && (sibling.getRight().getColor() == BaseTreeMap.Node.BLACK)) {
                    // Case 2: Sibling has no red children.
                    // Recolor sibling, and move to parent.
                    sibling.setColor(BaseTreeMap.Node.RED);
                    node = parent;
                    parent = parent.getParent();
                } else {
                    if (sibling.getRight().getColor() == BaseTreeMap.Node.BLACK) {
                        // Case 3: Sibling has red left child.
                        // Recolor sibling and left child, rotate sibling right.
                        sibling.getLeft().setColor(BaseTreeMap.Node.BLACK);
                        sibling.setColor(BaseTreeMap.Node.RED);
                        rotateRight(sibling);
                        sibling = parent.getRight();
                    }
                    // Case 4: Sibling has red right child. Recolor sibling,
                    // right child, and parent, and rotate parent left.
                    sibling.setColor(parent.getColor());
                    parent.setColor(BaseTreeMap.Node.BLACK);
                    sibling.getRight().setColor(BaseTreeMap.Node.BLACK);
                    rotateLeft(parent);
                    node = root; // Finished.
                }
            } else {
                // Symmetric "mirror" of left-side case.
                BaseTreeMap.Node sibling = parent.getLeft();
                // if (sibling == nil)
                //   throw new InternalError();
                if (sibling.getColor() == BaseTreeMap.Node.RED) {
                    // Case 1: Sibling is red.
                    // Recolor sibling and parent, and rotate parent right.
                    sibling.setColor(BaseTreeMap.Node.BLACK);
                    parent.setColor(BaseTreeMap.Node.RED);
                    rotateRight(parent);
                    sibling = parent.getLeft();
                }

                if ((sibling.getRight().getColor() == BaseTreeMap.Node.BLACK) && (sibling.getLeft().getColor() == BaseTreeMap.Node.BLACK)) {
                    // Case 2: Sibling has no red children.
                    // Recolor sibling, and move to parent.
                    sibling.setColor(BaseTreeMap.Node.RED);
                    node = parent;
                    parent = parent.getParent();
                } else {
                    if (sibling.getLeft().getColor() == BaseTreeMap.Node.BLACK) {
                        // Case 3: Sibling has red right child.
                        // Recolor sibling and right child, rotate sibling left.
                        sibling.getRight().setColor(BaseTreeMap.Node.BLACK);
                        sibling.setColor(BaseTreeMap.Node.RED);
                        rotateLeft(sibling);
                        sibling = parent.getLeft();
                    }
                    // Case 4: Sibling has red left child. Recolor sibling,
                    // left child, and parent, and rotate parent right.
                    sibling.setColor(parent.getColor());
                    parent.setColor(BaseTreeMap.Node.BLACK);
                    sibling.getLeft().setColor(BaseTreeMap.Node.BLACK);
                    rotateRight(parent);
                    node = root; // Finished.
                }
            }
        }
        node.setColor(BaseTreeMap.Node.BLACK);
    }

    /**
     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
     * public because of the proxy structure ozone uses combined with the fact
     * that java does not support protected or package methods in interfaces.
     * This method needs to be callable from iterators and submaps./p>
     *
     * Construct a perfectly balanced tree consisting of n "blank" nodes. This
     * permits a tree to be generated from pre-sorted input in linear time.
     *
     * @param count the number of blank nodes, non-negative
     */
    public void _org_ozoneDB_fabricateTree(final int count) {
        if (count == 0) {
            return;
        }

        // We color every row of nodes black, except for the overflow nodes.
        // I believe that this is the optimal arrangement. We construct the tree
        // in place by temporarily linking each node to the next node in the row,
        // then updating those links to the children when working on the next row.

        // Make the root node.
        root = newNode(null, null, BaseTreeMap.Node.BLACK);
        size = count;
        BaseTreeMap.Node row = root;
        int rowsize;

        // Fill each row that is completely full of nodes.
        for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) {
            BaseTreeMap.Node parent = row;
            BaseTreeMap.Node last = null;
            for (int i = 0; i < rowsize; i += 2) {
                BaseTreeMap.Node left = newNode(null, null, BaseTreeMap.Node.BLACK);
                BaseTreeMap.Node right = newNode(null, null, BaseTreeMap.Node.BLACK);
                left.setParent(parent);
                left.setRight(right);
                right.setParent(parent);
                parent.setLeft(left);
                BaseTreeMap.Node next = parent.getRight();
                parent.setRight(right);
                parent = next;
                if (last != null) {
                    last.setRight(left);
                }
                last = right;
            }
            row = row.getLeft();
        }

        // Now do the partial final row in red.
        int overflow = count - rowsize;
        BaseTreeMap.Node parent = row;
        int i;
        for (i = 0; i < overflow; i += 2) {
            BaseTreeMap.Node left = newNode(null, null, BaseTreeMap.Node.RED);
            BaseTreeMap.Node right = newNode(null, null, BaseTreeMap.Node.RED);
            left.setParent(parent);
            right.setParent(parent);
            parent.setLeft(left);
            BaseTreeMap.Node next = parent.getRight();
            parent.setRight(right);
            parent = next;
        }
        // Add a lone left node if necessary.
        if (i - overflow == 0) {
            BaseTreeMap.Node left = newNode(null, null, BaseTreeMap.Node.RED);
            left.setParent(parent);
            parent.setLeft(left);
            parent = parent.getRight();
            left.getParent().setRight(nilNode);
        }
        // Unlink the remaining nodes of the previous row.
        while (!parent.isNil()) {
            BaseTreeMap.Node next = parent.getRight();
            parent.setRight(nilNode);
            parent = next;
        }
    }

    /**
     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
     * public because of the proxy structure ozone uses combined with the fact
     * that java does not support protected or package methods in interfaces.
     * This method needs to be callable from iterators and submaps./p>
     *
     * Returns the first sorted node in the map, or nil if empty. Package
     * visible for use by nested classes.
     *
     * @return the first node
     */
    public final BaseTreeMap.Node _org_ozoneDB_firstNode() {
        // Exploit fact that nil.left == nil.
        BaseTreeMap.Node node = root;
        while (!node.getLeft().isNil()) {
            node = node.getLeft();
        }
        return node;
    }

    /**
     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
     * public because of the proxy structure ozone uses combined with the fact
     * that java does not support protected or package methods in interfaces.
     * This method needs to be callable from iterators and submaps./p>
     *
     * Return the TreeMap.Node associated with key, or the nil node if no such
     * node exists in the tree. Package visible for use by nested classes.
     *
     * @param key the key to search for
     * @return the node where the key is found, or nil
     */
    public final BaseTreeMap.Node _org_ozoneDB_getNode(Object key) {
        BaseTreeMap.Node current = root;
        while (!current.isNil()) {
            int comparison = _org_ozoneDB_compare(key, current.getKey());
            if (comparison > 0) {
                current = current.getRight();
            } else if (comparison < 0) {
                current = current.getLeft();
            } else {
                return current;
            }
        }
        return current;
    }

    /**
     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
     * public because of the proxy structure ozone uses combined with the fact
     * that java does not support protected or package methods in interfaces.
     * This method needs to be callable from iterators and submaps./p>
     *
     * Find the "highest" node which is &lt; key. If key is nil, return last
     * node. Package visible for use by nested classes.
     *
     * @param key the upper bound, exclusive
     * @return the previous node
     */
    public final BaseTreeMap.Node _org_ozoneDB_highestLessThan(Object key) {
        if ((key instanceof BaseTreeMap.Node) && ((BaseTreeMap.Node) key).isNil()) {
            return lastNode();
        }

        BaseTreeMap.Node last = nilNode;
        BaseTreeMap.Node current = root;
        int comparison = 0;

        while (!current.isNil()) {
            last = current;
            comparison = _org_ozoneDB_compare(key, current.getKey());
            if (comparison > 0) {
                current = current.getRight();
            } else if (comparison < 0) {
                current = current.getLeft();
            } else {// Exact match.
                return predecessor(last);
            }
        }
        return comparison <= 0 ? predecessor(last) : last;
    }

    /**
     * Maintain red-black balance after inserting a new node.
     *
     * @param n the newly inserted node
     */
    private void insertFixup(BaseTreeMap.Node n) {
        // Only need to rebalance when parent is a BaseTreeMap.Node.RED node, and while at least
        // 2 levels deep into the tree (ie: node has a grandparent). Remember
        // that nil.color == BaseTreeMap.Node.BLACK.
        while (n.getParent().getColor() == BaseTreeMap.Node.RED && !n.getParent().getParent().isNil()) {
            if (n.getParent().equals(n.getParent().getParent().getLeft())) {
                BaseTreeMap.Node uncle = n.getParent().getParent().getRight();
                // Uncle may be nil, in which case it is BaseTreeMap.Node.BLACK.
                if (uncle.getColor() == BaseTreeMap.Node.RED) {
                    // Case 1. Uncle is BaseTreeMap.Node.RED: Change colors of parent, uncle,
                    // and grandparent, and move n to grandparent.
                    n.getParent().setColor(BaseTreeMap.Node.BLACK);
                    uncle.setColor(BaseTreeMap.Node.BLACK);
                    uncle.getParent().setColor(BaseTreeMap.Node.RED);
                    n = uncle.getParent();
                } else {
                    if (n.equals(n.getParent().getRight())) {
                        // Case 2. Uncle is BaseTreeMap.Node.BLACK and x is right child.
                        // Move n to parent, and rotate n left.
                        n = n.getParent();
                        rotateLeft(n);
                    }
                    // Case 3. Uncle is BaseTreeMap.Node.BLACK and x is left child.
                    // Recolor parent, grandparent, and rotate grandparent right.
                    n.getParent().setColor(BaseTreeMap.Node.BLACK);
                    n.getParent().getParent().setColor(BaseTreeMap.Node.RED);
                    rotateRight(n.getParent().getParent());
                }
            } else {
                // Mirror image of above code.
                BaseTreeMap.Node uncle = n.getParent().getParent().getLeft();
                // Uncle may be nil, in which case it is BaseTreeMap.Node.BLACK.
                if (uncle.getColor() == BaseTreeMap.Node.RED) {
                    // Case 1. Uncle is BaseTreeMap.Node.RED: Change colors of parent, uncle,
                    // and grandparent, and move n to grandparent.
                    n.getParent().setColor(BaseTreeMap.Node.BLACK);
                    uncle.setColor(BaseTreeMap.Node.BLACK);
                    uncle.getParent().setColor(BaseTreeMap.Node.RED);
                    n = uncle.getParent();
                } else {
                    if (n.equals(n.getParent().getLeft())) {
                        // Case 2. Uncle is BaseTreeMap.Node.BLACK and x is left child.
                        // Move n to parent, and rotate n right.
                        n = n.getParent();
                        rotateRight(n);
                    }
                    // Case 3. Uncle is BaseTreeMap.Node.BLACK and x is right child.
                    // Recolor parent, grandparent, and rotate grandparent left.
                    n.getParent().setColor(BaseTreeMap.Node.BLACK);
                    n.getParent().getParent().setColor(BaseTreeMap.Node.RED);
                    rotateLeft(n.getParent().getParent());
                }
            }
        }
        root.setColor(BaseTreeMap.Node.BLACK);
    }

    /**
     * Returns the last sorted node in the map, or nil if empty.
     *
     * @return the last node
     */