|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.ozoneDB.OzoneObject
org.ozoneDB.collections.AbstractOzoneMap
org.ozoneDB.collections.BaseTreeMapImpl
You are encouraged NOT to use this interface, but rather just use OzoneTreeMap
, which does not contain the 'internal' methods, or even
SortedMap
, which does not have any ozone dependency at all
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.
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 calling iterator()
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 entrySet()
,
keySet()
and values()
also result in the creation
of a new ozone object.
TreeMap
,
Collections.synchronizedSortedMap(SortedMap)
,
Serialized FormNested 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 | |
protected int |
modCount
Counts the number of modifications this TreeMap has undergone, used by Iterators to know when to throw ConcurrentModificationExceptions. |
protected BaseTreeMap.Node |
root
The root node of this TreeMap. |
protected int |
size
The size of this TreeMap. |
Fields inherited from class org.ozoneDB.collections.AbstractOzoneMap |
keys, values |
Constructor Summary | |
BaseTreeMapImpl()
Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort. |
|
BaseTreeMapImpl(java.util.Comparator c)
Instantiate a new TreeMap with no elements, using the provided comparator to sort. |
|
BaseTreeMapImpl(java.util.Map map)
Instantiate a new TreeMap, initializing it with all of the elements in the provided Map. |
|
BaseTreeMapImpl(java.util.SortedMap sm)
Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap. |
Method Summary | |
int |
_org_ozoneDB_compare(java.lang.Object o1,
java.lang.Object o2)
DO NOT USE THIS METHOD DIRECTLY! |
java.util.Set |
_org_ozoneDB_entrySet()
|
void |
_org_ozoneDB_fabricateTree(int count)
DO NOT USE THIS METHOD; for internal use only. |
BaseTreeMap.Node |
_org_ozoneDB_firstNode()
DO NOT USE THIS METHOD; for internal use only. |
int |
_org_ozoneDB_getModification()
DO NOT CALL THIS METHOD DIRECTLY. |
BaseTreeMap.Node |
_org_ozoneDB_getNode(java.lang.Object key)
DO NOT USE THIS METHOD; for internal use only. |
BaseTreeMap.Node |
_org_ozoneDB_highestLessThan(java.lang.Object key)
DO NOT USE THIS METHOD; for internal use only. |
java.util.Set |
_org_ozoneDB_keySet()
|
BaseTreeMap.Node |
_org_ozoneDB_lowestGreaterThan(java.lang.Object key,
boolean first)
DO NOT USE THIS METHOD; for internal use only. |
void |
_org_ozoneDB_putKeysLinear(java.util.Iterator keys,
int count)
DO NOT USE THIS METHOD; for internal use only. |
void |
_org_ozoneDB_removeNode(BaseTreeMap.Node node)
DO NOT USE THIS METHOD; for internal use only. |
void |
_org_ozoneDB_resetEntries()
|
BaseTreeMap.Node |
_org_ozoneDB_successor(BaseTreeMap.Node node)
DO NOT USE THIS METHOD; for internal use only. |
java.util.Collection |
_org_ozoneDB_values()
|
void |
clear()
Clears the Map so it has no keys. |
java.lang.Object |
clone()
Returns a shallow clone of this TreeMap. |
java.util.Comparator |
comparator()
Return the comparator used to sort this map, or null if it is by natural order. |
boolean |
containsKey(java.lang.Object key)
Returns true if the map contains a mapping for the given key. |
boolean |
containsValue(java.lang.Object value)
Returns true if the map contains at least one mapping to the given value. |
protected abstract BaseTreeMap |
emptyClone()
|
java.util.Set |
entrySet()
Returns a "set view" of this TreeMap's entries. |
java.lang.Object |
firstKey()
Returns the first (lowest) key in the map. |
java.lang.Object |
get(java.lang.Object key)
Return the value in this TreeMap associated with the supplied key, or null if the key maps to nothing. |
java.util.Map |
getClientMap()
Returns a Map that contains the same entries as this
persistent one; it is (by nature of the client-server enviromnent) always
a 'deep' copy of this OzoneMap . |
java.util.SortedMap |
getClientSortedMap()
Returns a SortedMap that contains the same entries as this
persistent one; it is (by nature of the client-server enviromnent) always
a 'deep' copy of this OzoneSortedMap . |
java.util.TreeMap |
getClientTreeMap()
Returns a TreeMap that contains the same entries as this
persistent one; it is (by nature of the client-server enviromnent) always
a 'deep' copy of this OzoneTreeMap . |
java.util.SortedMap |
headMap(java.lang.Object toKey)
Returns a view of this Map including all entries with keys less than toKey . |
java.util.Set |
keySet()
Returns a "set view" of this TreeMap's keys. |
java.lang.Object |
lastKey()
Returns the last (highest) key in the map. |
protected abstract BaseTreeMap.Node |
newNode(java.lang.Object key,
java.lang.Object value,
int color)
|
void |
onCreate()
|
OzoneSortedMap |
ozoneHeadMap(java.lang.Object toKey)
Basically nothing more than a typecasted HeadMap method.
|
OzoneSortedMap |
ozoneSubMap(java.lang.Object fromKey,
java.lang.Object toKey)
Basically nothing more than a typecasted SubMap method.
|
OzoneSortedMap |
ozoneTailMap(java.lang.Object toKey)
Basically nothing more than a typecasted TailMap method. |
java.lang.Object |
put(java.lang.Object key,
java.lang.Object value)
Puts the supplied value into the Map, mapped by the supplied key. |
void |
putAll(java.util.Map m)
Copies all elements of the given map into this hashtable. |
java.lang.Object |
remove(java.lang.Object key)
Removes from the TreeMap and returns the value which is mapped by the supplied key. |
int |
size()
Returns the number of key-value mappings currently in this Map. |
java.util.SortedMap |
subMap(java.lang.Object fromKey,
java.lang.Object toKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey and less than toKey (a
half-open interval). |
java.util.SortedMap |
tailMap(java.lang.Object fromKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey . |
java.util.Collection |
values()
Returns a "collection view" (or "bag view") of this TreeMap's 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_alwaysUseInternalIterator |
Methods inherited from interface org.ozoneDB.collections.OzoneMap |
ozoneEntrySet, ozoneKeySet, ozoneValues |
Methods inherited from interface java.util.Map |
equals, hashCode, isEmpty |
Methods inherited from interface org.ozoneDB.OzoneCompatibleOrProxy |
getObjectID |
Field Detail |
protected BaseTreeMap.Node root
protected int size
protected int modCount
Constructor Detail |
public BaseTreeMapImpl()
ClassCastException
. Attempts to use
a null key will throw a NullPointerException
.
Comparable
public BaseTreeMapImpl(java.util.Comparator c)
ClassCastException
.
c
- (comparator) the sort order for the keys of this map, or null
for the natural orderpublic BaseTreeMapImpl(java.util.Map map)
ClassCastException
.
map
- a Map, whose entries will be put into this TreeMap
java.lang.ClassCastException
- if the keys in the provided Map are not
comparable
java.lang.NullPointerException
- if map is nullComparable
public BaseTreeMapImpl(java.util.SortedMap sm)
sm
- a SortedMap, whose entries will be put into this TreeMap
java.lang.NullPointerException
- if sm is nullMethod Detail |
public void onCreate()
onCreate
in interface org.ozoneDB.OzoneCompatible
public void clear()
clear
in interface OzoneMap
clear
in class AbstractOzoneMap
Set.clear()
public java.lang.Object clone()
clone
in class AbstractOzoneMap
Cloneable
,
Object.clone()
public java.util.Comparator comparator()
comparator
in interface java.util.SortedMap
public boolean containsKey(java.lang.Object key)
containsKey
in interface java.util.Map
containsKey
in class AbstractOzoneMap
key
- the key to look for
java.lang.ClassCastException
- if key is not comparable to map elements
java.lang.NullPointerException
- if key is null and the comparator is not
tolerant of nullsAbstractOzoneMap.containsValue(Object)
public boolean containsValue(java.lang.Object value)
containsValue
in interface java.util.Map
containsValue
in class AbstractOzoneMap
value
- the value to look for
AbstractOzoneMap.containsKey(Object)
public java.util.Set entrySet()
Note that the iterators for all three views, from keySet(), entrySet(), and values(), traverse the TreeMap in sorted sequence.
entrySet
in interface java.util.Map
entrySet
in class AbstractOzoneMap
keySet()
,
values()
,
Map.Entry
public java.util.Set _org_ozoneDB_entrySet()
_org_ozoneDB_entrySet
in interface BaseTreeMap
public java.lang.Object firstKey()
firstKey
in interface java.util.SortedMap
java.util.NoSuchElementException
- if the map is emptypublic java.lang.Object get(java.lang.Object key)
null
if the key maps to nothing. NOTE: Since the value
could also be null, you must use containsKey to see if this key
actually maps to something.
get
in interface java.util.Map
get
in class AbstractOzoneMap
key
- the key for which to fetch an associated value
java.lang.ClassCastException
- if key is not comparable to elements in the map
java.lang.NullPointerException
- if key is null but the comparator does not
tolerate nullsput(Object, Object)
,
containsKey(Object)
public java.util.SortedMap headMap(java.lang.Object toKey)
toKey
. The returned map is backed by the original, so changes
in one appear in the other. The submap will throw an
IllegalArgumentException
for any attempt to access or add an
element beyond the specified cutoff. The returned map does not include
the endpoint; if you want inclusion, pass the successor element.
headMap
in interface java.util.SortedMap
toKey
- the (exclusive) cutoff point
java.lang.ClassCastException
- if toKey
is not compatible with
the comparator (or is not Comparable, for natural ordering)
java.lang.NullPointerException
- if toKey is null, but the comparator does not
tolerate null elementspublic java.util.Set keySet()
keySet
in interface java.util.Map
keySet
in class AbstractOzoneMap
values()
,
entrySet()
public java.util.Set _org_ozoneDB_keySet()
_org_ozoneDB_keySet
in interface BaseTreeMap
public java.lang.Object lastKey()
lastKey
in interface java.util.SortedMap
java.util.NoSuchElementException
- if the map is emptypublic java.lang.Object put(java.lang.Object key, java.lang.Object value)
equals()
this key. NOTE: Since the prior value could also be null, you must
first use containsKey if you want to see if you are replacing the
key's mapping.
put
in interface OzoneMap
put
in class AbstractOzoneMap
key
- the key used to locate the valuevalue
- the value to be stored in the HashMap
java.lang.ClassCastException
- if key is not comparable to current map keys
java.lang.NullPointerException
- if key is null, but the comparator does
not tolerate nullsget(Object)
,
Object.equals(Object)
public void putAll(java.util.Map m)
putAll
in interface OzoneMap
putAll
in class AbstractOzoneMap
m
- the map to be hashed into this
java.lang.ClassCastException
- if a key in m is not comparable with keys
in the map
java.lang.NullPointerException
- if a key in m is null, and the comparator
does not tolerate nullsAbstractOzoneMap.put(Object, Object)
public java.lang.Object remove(java.lang.Object key)
null
is returned. NOTE: Since the value
could also be null, you must use containsKey to see if you are
actually removing a mapping.
remove
in interface OzoneMap
remove
in class AbstractOzoneMap
key
- the key used to locate the value to remove
java.lang.ClassCastException
- if key is not comparable to current map keys
java.lang.NullPointerException
- if key is null, but the comparator does
not tolerate nullsIterator.remove()
public int size()
size
in interface java.util.Map
size
in class AbstractOzoneMap
Set.size()
public java.util.SortedMap subMap(java.lang.Object fromKey, java.lang.Object toKey)
fromKey
and less than toKey
(a
half-open interval). The returned map is backed by the original, so
changes in one appear in the other. The submap will throw an
IllegalArgumentException
for any attempt to access or add an
element beyond the specified cutoffs. The returned map includes the low
endpoint but not the high; if you want to reverse this behavior on
either end, pass in the successor element.
subMap
in interface java.util.SortedMap
fromKey
- the (inclusive) low cutoff pointtoKey
- the (exclusive) high cutoff point
java.lang.ClassCastException
- if either cutoff is not compatible with
the comparator (or is not Comparable, for natural ordering)
java.lang.NullPointerException
- if fromKey or toKey is null, but the
comparator does not tolerate null elements
java.lang.IllegalArgumentException
- if fromKey is greater than toKeypublic java.util.SortedMap tailMap(java.lang.Object fromKey)
fromKey
. The returned map is backed by the
original, so changes in one appear in the other. The submap will throw an
IllegalArgumentException
for any attempt to access or add an
element beyond the specified cutoff. The returned map includes the
endpoint; if you want to exclude it, pass in the successor element.
tailMap
in interface java.util.SortedMap
fromKey
- the (inclusive) low cutoff point
java.lang.ClassCastException
- if fromKey
is not compatible with
the comparator (or is not Comparable, for natural ordering)
java.lang.NullPointerException
- if fromKey is null, but the comparator
does not tolerate null elementspublic java.util.Collection values()
values
in interface java.util.Map
values
in class AbstractOzoneMap
keySet()
,
entrySet()
public java.util.Collection _org_ozoneDB_values()
_org_ozoneDB_values
in interface BaseTreeMap
public final int _org_ozoneDB_compare(java.lang.Object o1, java.lang.Object o2)
DO NOT USE THIS METHOD DIRECTLY!
Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators, submaps, etc./p>
_org_ozoneDB_compare
in interface BaseTreeMap
o1
- the first objecto2
- the second object
java.lang.ClassCastException
- if o1 and o2 are not mutually comparable,
or are not Comparable with natural ordering
java.lang.NullPointerException
- if o1 or o2 is null with natural orderingpublic void _org_ozoneDB_fabricateTree(int count)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Construct a perfectly balanced tree consisting of n "blank" nodes. This permits a tree to be generated from pre-sorted input in linear time.
_org_ozoneDB_fabricateTree
in interface BaseTreeMap
count
- the number of blank nodes, non-negativepublic final BaseTreeMap.Node _org_ozoneDB_firstNode()
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Returns the first sorted node in the map, or nil if empty. Package visible for use by nested classes.
_org_ozoneDB_firstNode
in interface BaseTreeMap
public final BaseTreeMap.Node _org_ozoneDB_getNode(java.lang.Object key)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Return the TreeMap.Node associated with key, or the nil node if no such node exists in the tree. Package visible for use by nested classes.
_org_ozoneDB_getNode
in interface BaseTreeMap
key
- the key to search for
public final BaseTreeMap.Node _org_ozoneDB_highestLessThan(java.lang.Object key)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Find the "highest" node which is < key. If key is nil, return last node. Package visible for use by nested classes.
_org_ozoneDB_highestLessThan
in interface BaseTreeMap
key
- the upper bound, exclusive
public final BaseTreeMap.Node _org_ozoneDB_lowestGreaterThan(java.lang.Object key, boolean first)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Find the "lowest" node which is >= key. If key is nil, return either nil or the first node, depending on the parameter first. Package visible for use by nested classes.
_org_ozoneDB_lowestGreaterThan
in interface BaseTreeMap
key
- the lower bound, inclusivefirst
- true to return the first element instead of nil for nil key
public final void _org_ozoneDB_putKeysLinear(java.util.Iterator keys, int count)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Construct a tree from sorted keys in linear time, with values of "". Package visible for use by TreeSet.
_org_ozoneDB_putKeysLinear
in interface BaseTreeMap
keys
- the iterator over the sorted keyscount
- the number of nodes to insertTreeSet.TreeSet(java.util.SortedSet)
public final void _org_ozoneDB_removeNode(BaseTreeMap.Node node)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Remove node from tree. This will increment modCount and decrement size. Node must exist in the tree. Package visible for use by nested classes.
_org_ozoneDB_removeNode
in interface BaseTreeMap
node
- the node to removepublic final BaseTreeMap.Node _org_ozoneDB_successor(BaseTreeMap.Node node)
DO NOT USE THIS METHOD; for internal use only. Must unfortunately be public because of the proxy structure ozone uses combined with the fact that java does not support protected or package methods in interfaces. This method needs to be callable from iterators and submaps./p> Return the node following the given one, or nil if there isn't one. Package visible for use by nested classes.
_org_ozoneDB_successor
in interface BaseTreeMap
node
- the current node, not nil
public java.util.SortedMap getClientSortedMap()
Returns a SortedMap
that contains the same entries as this
persistent one; it is (by nature of the client-server enviromnent) always
a 'deep' copy of this OzoneSortedMap
. I.e. the contents of
this OzoneSortedMap
instance are always copied to the client
by use of serialization.
getClientSortedMap
in interface OzoneSortedMap
public java.util.Map getClientMap()
Returns a Map
that contains the same entries as this
persistent one; it is (by nature of the client-server enviromnent) always
a 'deep' copy of this OzoneMap
. I.e. the contents of
this OzoneMap
instance are always copied to the client
by use of serialization.
getClientMap
in interface OzoneMap
public java.util.TreeMap getClientTreeMap()
Returns a TreeMap
that contains the same entries as this
persistent one; it is (by nature of the client-server enviromnent) always
a 'deep' copy of this OzoneTreeMap
. I.e. the contents of
this OzoneTreeMap
instance are always copied to the client
by use of serialization.
getClientTreeMap
in interface OzoneTreeMap
public void _org_ozoneDB_resetEntries()
_org_ozoneDB_resetEntries
in interface BaseTreeMap
public int _org_ozoneDB_getModification()
DO NOT CALL THIS METHOD DIRECTLY.
This method is called by an Iterator
to find out if this
collection has changed during the lifespan of that Iterator
_org_ozoneDB_getModification
in interface BaseTreeMap
public OzoneSortedMap ozoneHeadMap(java.lang.Object toKey)
Basically nothing more than a typecasted HeadMap
method.
Because subsets are also OzoneSortedMap
s, this method is
provided to do away with the need for a typecast.
ozoneHeadMap
in interface OzoneSortedMap
public OzoneSortedMap ozoneSubMap(java.lang.Object fromKey, java.lang.Object toKey)
Basically nothing more than a typecasted SubMap
method.
Because subsets are also OzoneSortedMap
s, this method is
provided to do away with the need for a typecast.
ozoneSubMap
in interface OzoneSortedMap
public OzoneSortedMap ozoneTailMap(java.lang.Object toKey)
Basically nothing more than a typecasted TailMap
method.
OzoneSortedMap
s, this method is
provided to do away with the need for a typecast.
ozoneTailMap
in interface OzoneSortedMap
protected abstract BaseTreeMap.Node newNode(java.lang.Object key, java.lang.Object value, int color)
protected abstract BaseTreeMap emptyClone()
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |