org.ozoneDB.collections
Class FullTreeMapImpl
java.lang.Object
org.ozoneDB.OzoneObject
org.ozoneDB.collections.AbstractOzoneMap
org.ozoneDB.collections.BaseTreeMapImpl
org.ozoneDB.collections.FullTreeMapImpl
- All Implemented Interfaces:
- BaseTreeMap, java.lang.Cloneable, FullTreeMap, java.util.Map, org.ozoneDB.OzoneCompatible, org.ozoneDB.OzoneCompatibleOrProxy, OzoneMap, org.ozoneDB.OzoneRemote, OzoneSortedMap, OzoneTreeMap, java.io.Serializable, java.util.SortedMap
- public class FullTreeMapImpl
- extends BaseTreeMapImpl
- implements FullTreeMap
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()
results in the creation of a new ozone object.
NOTE: Because of issues with implementing 2 Ozone objects that have
to share non-Ozone objects, it can happen that a FullXxx
instance is written to the backend-store while the Iterator
remains in memory. If that happens you will receive a ConcurrentModificationException
.
If you receive such an exception and are completely sure that the collection
has not been changed (objects added or removed from it) by another process,
you should increase the memory available to the Ozone server, or decrease the
time between successive calls on the methods of the iterator. It should be
noted that there is no way to guarantee that an exception is thrown in this
situation, just like there is no guarantee that an exception will be thrown
when a 'regular' java.util.Collection
is changed while an
iterator is at the same time iterating over it. This is theory, but in the
real world the changes of this happening are negligable.
- 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 |
FullTreeMapImpl()
Instantiate a new TreeMap with no elements, using the keys' natural
ordering to sort. |
FullTreeMapImpl(java.util.Comparator c)
Instantiate a new TreeMap with no elements, using the provided comparator
to sort. |
FullTreeMapImpl(java.util.Map map)
Instantiate a new TreeMap, initializing it with all of the elements in
the provided Map. |
FullTreeMapImpl(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, 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 |
FullTreeMapImpl
public FullTreeMapImpl()
- 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
FullTreeMapImpl
public FullTreeMapImpl(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
FullTreeMapImpl
public FullTreeMapImpl(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
FullTreeMapImpl
public FullTreeMapImpl(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
onActivate
public void onActivate()
- Called automatically by Ozone. Increments the modification counter to
make sure all
Iterator
s that were connected to a previous
(memory) instance of this database object are invalidated.
- Specified by:
onActivate
in interface org.ozoneDB.OzoneCompatible
Copyright © 2004 The Ozone Database Project - www.ozone-db.org. All Rights Reserved.