basetreemapimpl.java

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

/*
 * $Id: BaseTreeMapImpl.java,v 1.12.2.2 2004/01/15 22:02:37 per_nyfelt Exp $
 * This file is based on TreeMap.java from GNU Classpath. Quote:

TreeMap.java -- a class providing a basic Red-Black Tree data structure,
mapping Object --> Object
Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version.

 * end quote.
 *
 * This file is licenced under the same conditions as its original (GPL +
 * "special exception").
 */

package org.ozoneDB.collections;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * <p>You are encouraged NOT to use this interface, but rather just use {@link
 * OzoneTreeMap}, which does not contain the 'internal' methods, or even
 * {@link java.util.SortedMap}, which does not have any ozone dependency at all</p>
 * <p>This class functions as a sort of base class for ozone aware treemaps,
 * were those treemaps themselves can implement if the nodes in the tree are
 * ozone objects themselves or merely serializables.</p>
 *
 * This class provides a red-black tree implementation of the SortedMap
 * interface.  Elements in the Map will be sorted by either a user-provided
 * Comparator object, or by the natural ordering of the keys.
 *
 * The algorithms are adopted from Corman, Leiserson, and Rivest's
 * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
 * insertion and deletion of elements.  That being said, there is a large
 * enough constant coefficient in front of that "log n" (overhead involved
 * in keeping the tree balanced), that TreeMap may not be the best choice
 * for small collections. If something is already sorted, you may want to
 * just use a LinkedHashMap to maintain the order while providing O(1) access.
 *
 * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
 * only if a Comparator is used which can deal with them; natural ordering
 * cannot cope with null.  Null values are always allowed. Note that the
 * ordering must be <i>consistent with equals</i> to correctly implement
 * the Map interface. If this condition is violated, the map is still
 * well-behaved, but you may have suprising results when comparing it to
 * other maps.<p>
 *
 * This implementation is not synchronized. If you need to share this between
 * multiple threads, do something like:<br>
 * <code>SortedMap m
 *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
 *
 * <p>The iterators are <i>fail-fast</i>, meaning that any structural
 * modification, except for <code>remove()</code> called on the iterator
 * itself, cause the iterator to throw a
 * <code>ConcurrentModificationException</code> rather than exhibit
 * non-deterministic behavior.</p>
 *
 * <p>Note that calling <code>iterator()</code> may result in the creation of
 * an ozone object and thus in a write-action for the db. This is dependend
 * of the implementation. Also, the first call to <code>entrySet()</code>,
 * <code>keySet()</code> and <code>values()</code> also result in the creation
 * of a new ozone object.</p>
 *
 * @author Jon Zeppieri
 * @author Bryce McKinlay
 * @author Eric Blake <[e-mail]>
 * @author <a href="mailto:ozoneATmekenkampD0Tcom">Leo Mekenkamp (mind the anti-sp@m)</a> (adaptation for ozone)
 * @see java.util.TreeMap
 * @see java.util.Collections#synchronizedSortedMap(SortedMap)
 */
public abstract class BaseTreeMapImpl extends AbstractOzoneMap implements BaseTreeMap, OzoneSortedMap, Cloneable {
    // Implementation note:
    // A red-black tree is a binary search tree with the additional properties
    // that all paths to a leaf node visit the same number of black nodes,
    // and no red node has red children. To avoid some null-pointer checks,
    // we use the special node nil which is always black, has no relatives,
    // and has key and value of null (but is not equal to a mapping of null).

    private static final long serialVersionUID = 1L;

    /**
     * Sentinal node, used to avoid null checks for corner cases and make the
     * delete rebalance code simpler. The rebalance code must never assign
     * the parent, left, or right of nil, but may safely reassign the color
     * to be black. This object must never be used as a key in a TreeMap, or
     * it will break bounds checking of a SubMap.
     */
    static final BaseTreeMap.Node nilNode = new NilNode();

    private static final class NilNode implements BaseTreeMap.Node {

        private static final long serialVersionUID = 1L;

        public int getColor() {
            return BaseTreeMap.Node.BLACK;
        }

        public Object getKey() {
            return null;
        }

        public BaseTreeMap.Node getLeft() {
            return this;
        }

        public BaseTreeMap.Node getParent() {
            return this;
        }

        public BaseTreeMap.Node getRight() {
            return this;
        }

        public Object getValue() {
            return null;
        }

        public boolean isNil() {
            return true;
        }

        public void setColor(int color) {
            if (color != BaseTreeMap.Node.BLACK) throw new UnsupportedOperationException();
        }

        public void setLeft(BaseTreeMap.Node left) {
            throw new UnsupportedOperationException();
        }

        public void setParent(BaseTreeMap.Node parent) {
            throw new UnsupportedOperationException();
        }

        public void setRight(BaseTreeMap.Node right) {
            throw new UnsupportedOperationException();
        }

        public Object setValue(Object value) {
            throw new UnsupportedOperationException();
        }

        public void setKey(Object key) {
            throw new UnsupportedOperationException();
        }

        public boolean equals(Object o) {
            return (o instanceof BaseTreeMap.Node) && ((BaseTreeMap.Node) o).isNil();
        }
    };

    /**
     * The root node of this TreeMap.
     */
    protected BaseTreeMap.Node root = nilNode;

    /**
     * The size of this TreeMap.
     */
    protected int size;

    /**
     * The cache for {@link #entrySet()}.
     */
    private Set entries;

    /**
     * Counts the number of modifications this TreeMap has undergone, used
     * by Iterators to know when to throw ConcurrentModificationExceptions.
     */
    protected int modCount;

    /**
     * This TreeMap's comparator, or null for natural ordering.
     * @serial the comparator ordering this tree, or null
     */
    private final Comparator comparator;

    /**
     * Instantiate a new TreeMap with no elements, using the keys' natural
     * ordering to sort. All entries in the map must have a key which implements
     * Comparable, and which are <i>mutually comparable</i>, otherwise map
     * operations may throw a {@link ClassCastException}. Attempts to use
     * a null key will throw a {@link NullPointerException}.
     *
     * @see Comparable
     */
    public BaseTreeMapImpl() {
        this((Comparator) null);
    }

    /**
     * Instantiate a new TreeMap with no elements, using the provided comparator
     * to sort. All entries in the map must have keys which are mutually
     * comparable by the Comparator, otherwise map operations may throw a
     * {@link ClassCastException}.
     *
     * @param c (comparator) the sort order for the keys of this map, or null
     *        for the natural order
     */
    public BaseTreeMapImpl(Comparator c) {
        comparator = c;
    }

    /**
     * Instantiate a new TreeMap, initializing it with all of the elements in
     * the provided Map.  The elements will be sorted using the natural
     * ordering of the keys. This algorithm runs in n*log(n) time. All entries
     * in the map must have keys which implement Comparable and are mutually
     * comparable, otherwise map operations may throw a
     * {@link ClassCastException}.
     *
     * @param map a Map, whose entries will be put into this TreeMap
     * @throws ClassCastException if the keys in the provided Map are not
     *         comparable
     * @throws NullPointerException if map is null
     * @see Comparable
     */
    public BaseTreeMapImpl(Map map) {
        this((Comparator) null);
        putAll(map);
    }

    /**
     * Instantiate a new TreeMap, initializing it with all of the elements in
     * the provided SortedMap.  The elements will be sorted using the same
     * comparator as in the provided SortedMap. This runs in linear time.
     *
     * @param sm a SortedMap, whose entries will be put into this TreeMap
     * @throws NullPointerException if sm is null
     */
    public BaseTreeMapImpl(SortedMap sm) {
        this(sm.comparator());
        int pos = sm.size();
        Iterator itr = sm.entrySet().iterator();

        _org_ozoneDB_fabricateTree(pos);
        BaseTreeMap.Node node = _org_ozoneDB_firstNode();

        while (--pos >= 0) {
            Map.Entry me = (Map.Entry) itr.next();
            node.setKey(me.getKey());
            node.setValue(me.getValue());
            node = _org_ozoneDB_successor(node);
        }
    }

    public void onCreate() {
        super.onCreate();
    }

    /**
     * Clears the Map so it has no keys. This is O(1).
     */
    public void clear() {
        if (size > 0) {
            modCount++;
            root = nilNode;
            size = 0;
        }
    }

    /**
     * Returns a shallow clone of this TreeMap. The Map itself is cloned,
     * but its contents are not.
     *
     * @return the clone
     */
    public Object clone() {
        BaseTreeMap copy = emptyClone();
//        try {
//// TODO: replace when FakeFactoryGenerator is ready
////            copy = BaseTreeMapImplFactory.getDefault().create(self());
//            copy = (BaseTreeMap) database().createObject(BaseTreeMap.class, BaseTreeMap.class.getName(), new Object[] {self()});
//        } catch (Exception e) {
//            throw new RuntimeException(e);
//        }
        copy._org_ozoneDB_resetEntries();
        copy._org_ozoneDB_fabricateTree(size);

        BaseTreeMap.Node node = _org_ozoneDB_firstNode();
        BaseTreeMap.Node cnode = copy._org_ozoneDB_firstNode();

        while (!node.isNil()) {
            cnode.setKey(node.getKey());
            cnode.setValue(node.getValue());
            node = _org_ozoneDB_successor(node);
            cnode = copy._org_ozoneDB_successor(cnode);
        }
        return copy;
    }

    /**
     * Return the comparator used to sort this map, or null if it is by
     * natural order.
     *
     * @return the map's comparator
     */
    public Comparator comparator() {
        return comparator;
    }

    /**
     * Returns true if the map contains a mapping for the given key.
     *
     * @param key the key to look for