nodetreemapimpl.java

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

// You can redistribute this software and/or modify it under the terms of
// the Ozone Library License version 1 published by ozone-db.org.
//
// This file is
// Copyright (C) 2002-@year@ Leo Mekenkamp. All rights reserved.
// $Id: NodeTreeMapImpl.java,v 1.6 2003/11/27 15:55:11 leomekenkamp Exp $

package org.ozoneDB.collections;

import java.util.Comparator;
import java.util.Map;
import java.util.SortedMap;

/**
 * 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>
 *
 * 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>Note that the first call to <code>entrySet()</code>, <code>keySet()</code>
 * and <code>values()</code> 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 class NodeTreeMapImpl extends BaseTreeMapImpl implements NodeTreeMap {
    // 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;

    /**
     * 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 NodeTreeMapImpl() {
    }

    /**
     * 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 NodeTreeMapImpl(Comparator c) {
        super(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 NodeTreeMapImpl(Map map) {
        super(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 NodeTreeMapImpl(SortedMap sm) {
        super(sm); // super sm ??? LOL!
    }

    protected BaseTreeMap emptyClone() {
        // TODO: when FakeFactoryGenerator is finished replace with
        // return FullTreeMapImplFactory.getDefault().create();
        return (BaseTreeMap) database().createObject(NodeTreeMapImpl.class);
    }

    protected BaseTreeMap.Node newNode(Object key, Object value, int color) {
        // TODO: when FakeFactoryGenerator is finished replace with
        // _NodeTreeMap_OzoneNode result return _NodeTreeMap_OzoneNodeImplFactory.getDefault().create(key, value, color);
        _NodeTreeMap_OzoneNode result = (_NodeTreeMap_OzoneNode) database().createObject(
                _NodeTreeMap_OzoneNodeImpl.class,
                new Class[] {Object.class, Object.class, int.class},
                new Object[] {key, value, new Integer(color)}
        );
        return result;
    }

    public boolean _org_ozoneDB_alwaysUseInternalIterator() {
        return true;
    }
    
}