org.ozoneDB.collections
Class NodeTreeMapImpl

java.lang.Object
  extended byorg.ozoneDB.OzoneObject
      extended byorg.ozoneDB.collections.AbstractOzoneMap
          extended byorg.ozoneDB.collections.BaseTreeMapImpl
              extended byorg.ozoneDB.collections.NodeTreeMapImpl
All Implemented Interfaces:
BaseTreeMap, java.lang.Cloneable, java.util.Map, NodeTreeMap, org.ozoneDB.OzoneCompatible, org.ozoneDB.OzoneCompatibleOrProxy, OzoneMap, org.ozoneDB.OzoneRemote, OzoneSortedMap, OzoneTreeMap, java.io.Serializable, java.util.SortedMap

public class NodeTreeMapImpl
extends BaseTreeMapImpl
implements NodeTreeMap

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 Introduction to Algorithms. 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 consistent with equals 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.

This implementation is not synchronized. If you need to share this between multiple threads, do something like:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a ConcurrentModificationException rather than exhibit non-deterministic behavior.

Note that the first call to entrySet(), keySet() and values() result in the creation of a new ozone object.

Author:
Jon Zeppieri, Bryce McKinlay, Eric Blake , Leo Mekenkamp (mind the anti-sp@m) (adaptation for ozone)
See Also:
TreeMap, Collections.synchronizedSortedMap(SortedMap), Serialized Form

Nested Class Summary
 
Nested classes inherited from class org.ozoneDB.collections.BaseTreeMap
BaseTreeMap.Node
 
Nested classes inherited from class java.util.Map
java.util.Map.Entry
 
Field Summary
 
Fields inherited from class org.ozoneDB.collections.BaseTreeMapImpl
modCount, root, size
 
Fields inherited from class org.ozoneDB.collections.AbstractOzoneMap
keys, values
 
Constructor Summary
NodeTreeMapImpl()
          Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort.
NodeTreeMapImpl(java.util.Comparator c)
          Instantiate a new TreeMap with no elements, using the provided comparator to sort.
NodeTreeMapImpl(java.util.Map map)
          Instantiate a new TreeMap, initializing it with all of the elements in the provided Map.
NodeTreeMapImpl(java.util.SortedMap sm)
          Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap.
 
Method Summary
 boolean _org_ozoneDB_alwaysUseInternalIterator()
           
protected  BaseTreeMap emptyClone()
           
protected  BaseTreeMap.Node newNode(java.lang.Object key, java.lang.Object value, int color)
           
 
Methods inherited from class org.ozoneDB.collections.BaseTreeMapImpl
_org_ozoneDB_compare, _org_ozoneDB_entrySet, _org_ozoneDB_fabricateTree, _org_ozoneDB_firstNode, _org_ozoneDB_getModification, _org_ozoneDB_getNode, _org_ozoneDB_highestLessThan, _org_ozoneDB_keySet, _org_ozoneDB_lowestGreaterThan, _org_ozoneDB_putKeysLinear, _org_ozoneDB_removeNode, _org_ozoneDB_resetEntries, _org_ozoneDB_successor, _org_ozoneDB_values, clear, clone, comparator, containsKey, containsValue, entrySet, firstKey, get, getClientMap, getClientSortedMap, getClientTreeMap, headMap, keySet, lastKey, onCreate, ozoneHeadMap, ozoneSubMap, ozoneTailMap, put, putAll, remove, size, subMap, tailMap, values
 
Methods inherited from class org.ozoneDB.collections.AbstractOzoneMap
equals, hashCode, isEmpty, ozoneEntrySet, ozoneKeySet, ozoneValues, toString
 
Methods inherited from class org.ozoneDB.OzoneObject
container, database, deleteRecursive, getHandle, getObjectID, handle, onActivate, onDelete, onPassivate, requireWriteLocking, self, setContainer, toXML
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface org.ozoneDB.collections.BaseTreeMap
_org_ozoneDB_compare, _org_ozoneDB_entrySet, _org_ozoneDB_fabricateTree, _org_ozoneDB_firstNode, _org_ozoneDB_getModification, _org_ozoneDB_getNode, _org_ozoneDB_highestLessThan, _org_ozoneDB_keySet, _org_ozoneDB_lowestGreaterThan, _org_ozoneDB_putKeysLinear, _org_ozoneDB_removeNode, _org_ozoneDB_resetEntries, _org_ozoneDB_successor, _org_ozoneDB_values
 
Methods inherited from interface org.ozoneDB.collections.OzoneTreeMap
getClientTreeMap
 
Methods inherited from interface org.ozoneDB.collections.OzoneSortedMap
getClientSortedMap, ozoneHeadMap, ozoneSubMap, ozoneTailMap
 
Methods inherited from interface org.ozoneDB.collections.OzoneMap
clear, getClientMap, ozoneEntrySet, ozoneKeySet, ozoneValues, put, putAll, remove
 
Methods inherited from interface java.util.Map
containsKey, containsValue, entrySet, equals, get, hashCode, isEmpty, keySet, size, values
 
Methods inherited from interface org.ozoneDB.OzoneCompatibleOrProxy
getObjectID
 
Methods inherited from interface java.util.SortedMap
comparator, firstKey, headMap, lastKey, subMap, tailMap
 

Constructor Detail

NodeTreeMapImpl

public NodeTreeMapImpl()
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 mutually comparable, otherwise map operations may throw a ClassCastException. Attempts to use a null key will throw a NullPointerException.

See Also:
Comparable

NodeTreeMapImpl

public NodeTreeMapImpl(java.util.Comparator c)
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 ClassCastException.

Parameters:
c - (comparator) the sort order for the keys of this map, or null for the natural order

NodeTreeMapImpl

public NodeTreeMapImpl(java.util.Map map)
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 ClassCastException.

Parameters:
map - a Map, whose entries will be put into this TreeMap
Throws:
java.lang.ClassCastException - if the keys in the provided Map are not comparable
java.lang.NullPointerException - if map is null
See Also:
Comparable

NodeTreeMapImpl

public NodeTreeMapImpl(java.util.SortedMap sm)
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.

Parameters:
sm - a SortedMap, whose entries will be put into this TreeMap
Throws:
java.lang.NullPointerException - if sm is null
Method Detail

emptyClone

protected BaseTreeMap emptyClone()
Specified by:
emptyClone in class BaseTreeMapImpl

newNode

protected BaseTreeMap.Node newNode(java.lang.Object key,
                                   java.lang.Object value,
                                   int color)
Specified by:
newNode in class BaseTreeMapImpl

_org_ozoneDB_alwaysUseInternalIterator

public boolean _org_ozoneDB_alwaysUseInternalIterator()
Specified by:
_org_ozoneDB_alwaysUseInternalIterator in interface BaseTreeMap


Copyright © 2004 The Ozone Database Project - www.ozone-db.org. All Rights Reserved.