basetreemapimpl.java

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

    private BaseTreeMap.Node lastNode() {
        // Exploit fact that nil.right == nil.
        BaseTreeMap.Node node = root;
        while (!node.getRight().isNil()) {
            node = node.getRight();
        }
        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>
     *
     * Find the "lowest" node which is &gt;= key. If key is nil, return either
     * nil or the first node, depending on the parameter first.
     * Package visible for use by nested classes.
     *
     * @param key the lower bound, inclusive
     * @param first true to return the first element instead of nil for nil key
     * @return the next node
     */
    public final BaseTreeMap.Node _org_ozoneDB_lowestGreaterThan(Object key, boolean first) {
        if ((key instanceof BaseTreeMap.Node) && ((BaseTreeMap.Node) key).isNil()) {
            return first ? _org_ozoneDB_firstNode() : nilNode;
        }

        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 {
                return current;
            }
        }
        return comparison > 0 ? _org_ozoneDB_successor(last) : last;
    }

    /**
     * Return the node preceding the given one, or nil if there isn't one.
     *
     * @param node the current node, not nil
     * @return the prior node in sorted order
     */
    private BaseTreeMap.Node predecessor(BaseTreeMap.Node node) {
        if (!node.getLeft().isNil()) {
            node = node.getLeft();
            while (!node.getRight().isNil()) {
                node = node.getRight();
            }
            return node;
        }

        BaseTreeMap.Node parent = node.getParent();
        // Exploit fact that nil.left == nil and node is non-nil.
        while (node.equals(parent.getLeft())) {
            node = parent;
            parent = node.getParent();
        }
        return parent;
    }

    /**
     * <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 tree from sorted keys in linear time, with values of "".
     * Package visible for use by TreeSet.
     *
     * @param keys the iterator over the sorted keys
     * @param count the number of nodes to insert
     * @see java.util.TreeSet#TreeSet(java.util.SortedSet)
     */
    public final void _org_ozoneDB_putKeysLinear(Iterator keys, int count) {
        _org_ozoneDB_fabricateTree(count);
        BaseTreeMap.Node node = _org_ozoneDB_firstNode();

        while (--count >= 0) {
            node.setKey(keys.next());
            node.setValue("");
            node = _org_ozoneDB_successor(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>
     *
     * Remove node from tree. This will increment modCount and decrement size.
     * Node must exist in the tree. Package visible for use by nested classes.
     *
     * @param node the node to remove
     */
    public final void _org_ozoneDB_removeNode(BaseTreeMap.Node node) {
        BaseTreeMap.Node splice;
        BaseTreeMap.Node child;

        modCount++;
        size--;

        // Find splice, the node at the position to actually remove from the tree.
        if (node.getLeft().isNil()) {
            // Node to be deleted has 0 or 1 children.
            splice = node;
            child = node.getRight();
        } else if (node.getRight().isNil()) {
            // Node to be deleted has 1 child.
            splice = node;
            child = node.getLeft();
        } else {
            // Node has 2 children. Splice is node's predecessor, and we swap
            // its contents into node.
            splice = node.getLeft();
            while (!splice.getRight().isNil()) {
                splice = splice.getRight();
            }
            child = splice.getLeft();
            node.setKey(splice.getKey());
            node.setValue(splice.getValue());
        }

        // Unlink splice from the tree.
        BaseTreeMap.Node parent = splice.getParent();
        if (!child.isNil()) {
            child.setParent(parent);
        }
        if (parent.isNil()) {
            // Special case for 0 or 1 node remaining.
            root = child;
            return;
        }
        if (splice.equals(parent.getLeft())) {
            parent.setLeft(child);
        } else {
            parent.setRight(child);
        }

        if (splice.getColor() == BaseTreeMap.Node.BLACK) {
            deleteFixup(child, parent);
        }
    }

    /**
     * Rotate node n to the left.
     *
     * @param node the node to rotate
     */
    private void rotateLeft(BaseTreeMap.Node node) {
        BaseTreeMap.Node child = node.getRight();
        // if (node == nil || child == nil)
        //   throw new InternalError();

        // Establish node.right link.
        node.setRight(child.getLeft());
        if (!child.getLeft().isNil()) {
            child.getLeft().setParent(node);
        }

        // Establish child->parent link.
        child.setParent(node.getParent());
        if (!node.getParent().isNil()) {
            if (node.equals(node.getParent().getLeft())) {
                node.getParent().setLeft(child);
            } else {
                node.getParent().setRight(child);
            }
        } else {
            root = child;
        }

        // Link n and child.
        child.setLeft(node);
        node.setParent(child);
    }

    /**
     * Rotate node n to the right.
     *
     * @param node the node to rotate
     */
    private void rotateRight(BaseTreeMap.Node node) {
        BaseTreeMap.Node child = node.getLeft();
        // if (node == nil || child == nil)
        //   throw new InternalError();

        // Establish node.left link.
        node.setLeft(child.getRight());
        if (!child.getRight().isNil()) {
            child.getRight().setParent(node);
        }

        // Establish child->parent link.
        child.setParent(node.getParent());
        if (!node.getParent().isNil()) {
            if (node.equals(node.getParent().getRight())) {
                node.getParent().setRight(child);
            } else {
                node.getParent().setLeft(child);
            }
        } else {
            root = child;
        }

        // Link n and child.
        child.setRight(node);
        node.setParent(child);
    }

    /**
     * <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 node following the given one, or nil if there isn't one.
     * Package visible for use by nested classes.
     *
     * @param node the current node, not nil
     * @return the next node in sorted order
     */
    public final BaseTreeMap.Node _org_ozoneDB_successor(BaseTreeMap.Node node) {
        if (!node.getRight().isNil()) {
            node = node.getRight();
            while (!node.getLeft().isNil()) {
                node = node.getLeft();
            }
            return node;
        }

        BaseTreeMap.Node parent = node.getParent();
        
        // Exploit fact that nil.right == nil and node is non-nil.
        // First test for identical nodes, because this method is also called
        // indirectly from readObject, so if one of these nodes contain an
        // OzoneProxy for an OzoneObject with overridden equals(), that proxy
        // will cause the object to be loaded when equals() is called. But if
        // that object is in the same cluster as this TreeMap, than the cluster
        // will get loaded while it is loading, causing endless recursion...
        while (node == parent.getRight() || node.equals(parent.getRight())) {
            node = parent;
            parent = parent.getParent();
        }
        return parent;
    }

    /** <p>Returns a <code>SortedMap</code> that contains the same entries as this
     * persistent one; it is (by nature of the client-server enviromnent) always
     * a 'deep' copy of this <code>OzoneSortedMap</code>. I.e. the contents of
     * this <code>OzoneSortedMap</code> instance are always copied to the client
     * by use of serialization.</p>
     *
     */
    public SortedMap getClientSortedMap() {
        return getClientTreeMap();
    }

    /** <p>Returns a <code>Map</code> that contains the same entries as this
     * persistent one; it is (by nature of the client-server enviromnent) always
     * a 'deep' copy of this <code>OzoneMap</code>. I.e. the contents of
     * this <code>OzoneMap</code> instance are always copied to the client
     * by use of serialization.</p>
     *
     */
    public Map getClientMap() {
        return getClientTreeMap();
    }

    /** <p>Returns a <code>TreeMap</code> that contains the same entries as this
     * persistent one; it is (by nature of the client-server enviromnent) always
     * a 'deep' copy of this <code>OzoneTreeMap</code>. I.e. the contents of
     * this <code>OzoneTreeMap</code> instance are always copied to the client
     * by use of serialization.</p>
     *
     */
    public TreeMap getClientTreeMap() {
        // do not make use of TreeMap(SortedSet) because that one calls our
        // iterator() and we don't want that, because we want to use an internal
        // iterator for speed and possible read-only db
        TreeMap result = new TreeMap(comparator());
        for (Iterator i = ((OzoneSet) entrySet())._org_ozoneDB_internalIterator(); i.hasNext(); ) {
            Map.Entry entry = (Map.Entry) i.next();
            result.put(entry.getKey(), entry.getValue());
        }
        return result;
    }

    public void _org_ozoneDB_resetEntries() {
        this.entries = null;
    }

    /** <p>DO NOT CALL THIS METHOD DIRECTLY.</p>
     * <p>This method is called by an <code>Iterator</code> to find out if this
     * collection has changed during the lifespan of that <code>Iterator</code></p>
     *
     */
    public int _org_ozoneDB_getModification() {
        return modCount;
    }

    /** <p>Basically nothing more than a typecasted <code>HeadMap</code> method.
     * Because subsets are also <code>OzoneSortedMap</code>s, this method is
     * provided to do away with the need for a typecast.</p>
     *
     */
    public OzoneSortedMap ozoneHeadMap(Object toKey) {
        return (OzoneSortedMap) headMap(toKey);
    }

    /** <p>Basically nothing more than a typecasted <code>SubMap</code> method.
     * Because subsets are also <code>OzoneSortedMap</code>s, this method is
     * provided to do away with the need for a typecast.</p>
     *
     */
    public OzoneSortedMap ozoneSubMap(Object fromKey, Object toKey) {
        return (OzoneSortedMap) subMap(fromKey, toKey);
    }

    /** <p>Basically nothing more than a typecasted <code>TailMap</code> method.</p>
     * Because subsets are also <code>OzoneSortedMap</code>s, this method is
     * provided to do away with the need for a typecast.</p>
     *
     */
    public OzoneSortedMap ozoneTailMap(Object toKey) {
        return (OzoneSortedMap) tailMap(toKey);
    }

    protected abstract BaseTreeMap.Node newNode(Object key, Object value, int color);

    protected abstract BaseTreeMap emptyClone();

}