org.ozoneDB.collections
Class NodeTreeMapImpl
java.lang.Object
org.ozoneDB.OzoneObject
org.ozoneDB.collections.AbstractOzoneMap
org.ozoneDB.collections.BaseTreeMapImpl
org.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 classes inherited from class java.util.Map |
java.util.Map.Entry |
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. |
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.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 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 |
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
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.