org.ozoneDB.collections
Class BaseTreeSetImpl

java.lang.Object
  extended byorg.ozoneDB.OzoneObject
      extended byorg.ozoneDB.collections.AbstractOzoneCollection
          extended byorg.ozoneDB.collections.AbstractOzoneSet
              extended byorg.ozoneDB.collections.BaseTreeSetImpl
All Implemented Interfaces:
BaseTreeSet, java.lang.Cloneable, java.util.Collection, OzoneCollection, org.ozoneDB.OzoneCompatible, org.ozoneDB.OzoneCompatibleOrProxy, org.ozoneDB.OzoneRemote, OzoneSet, OzoneSortedSet, OzoneTreeSet, java.io.Serializable, java.util.Set, java.util.SortedSet
Direct Known Subclasses:
FullTreeSetImpl, NodeTreeSetImpl

public abstract class BaseTreeSetImpl
extends AbstractOzoneSet
implements BaseTreeSet, java.lang.Cloneable, java.io.Serializable

This class provides a TreeMap-backed implementation of the SortedSet interface. The elements will be sorted according to their natural order, or according to the provided Comparator.

Most operations are O(log n), but there is so much overhead that this makes small sets expensive. Note that the ordering must be consistent with equals to correctly implement the Set interface. If this condition is violated, the set is still well-behaved, but you may have suprising results when comparing it to other sets.

This implementation is not synchronized. If you need to share this between multiple threads, do something like:
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

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.

Since:
1.2 status updated to 1.4
Author:
Jon Zeppieri, Bryce McKinlay, Eric Blake , Leo Mekenkamp (mind the anti-sp@m) (adaptation for ozone)
See Also:
Collection, Set, HashSet, LinkedHashSet, Comparable, Comparator, Collections.synchronizedSortedSet(SortedSet), TreeMap, Serialized Form

Field Summary
protected  java.util.SortedMap map
          The SortedMap which backs this Set.
 
Constructor Summary
  BaseTreeSetImpl()
          Construct a new TreeSet whose backing TreeMap using the "natural" ordering of keys.
  BaseTreeSetImpl(java.util.Collection collection)
          Construct a new TreeSet whose backing TreeMap uses the "natural" orering of the keys and which contains all of the elements in the supplied Collection.
  BaseTreeSetImpl(java.util.Comparator comparator)
          Construct a new TreeSet whose backing TreeMap uses the supplied Comparator.
protected BaseTreeSetImpl(int ctorWithoutCreatingNewBackingMap)
          Basically a hack to prevent creationg of yet another map which backs this BaseTreeSet but will be overwritten almost immediately by ctor FullTreeSetImpl(SortedMap backingMap, DoNotUse_SeeJavadoc x)
  BaseTreeSetImpl(java.util.SortedSet sortedSet)
          Construct a new TreeSet, using the same key ordering as the supplied SortedSet and containing all of the elements in the supplied SortedSet.
 
Method Summary
 java.util.Iterator _org_ozoneDB_internalIterator()
           
 boolean add(java.lang.Object obj)
          Adds the spplied Object to the Set if it is not already in the Set; returns true if the element is added, false otherwise.
 boolean addAll(java.util.Collection c)
          Adds all of the elements in the supplied Collection to this TreeSet.
 void clear()
          Removes all elements in this Set.
 java.util.Comparator comparator()
          Returns this Set's comparator.
 boolean contains(java.lang.Object obj)
          Returns true if this Set contains the supplied Object, false otherwise.
 java.lang.Object first()
          Returns the first (by order) element in this Set.
 java.util.Collection getClientCollection()
          Returns a Collection that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneCollection.
 java.util.Set getClientSet()
          Returns a Set that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneSet.
 java.util.SortedSet getClientSortedSet()
          Returns a SortedSet that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneSortedSet.
 java.util.TreeSet getClientTreeSet()
          Returns a TreeSet that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneTreeSet.
 boolean isEmpty()
          Returns true if this Set has size 0, false otherwise.
 java.util.Iterator iterator()
          Returns in Iterator over the elements in this TreeSet, which traverses in ascending order.
 java.lang.Object last()
          Returns the last (by order) element in this Set.
protected abstract  java.util.SortedMap newBackingMap()
           
protected abstract  java.util.SortedMap newBackingMap(java.util.Comparator comparator)
           
 void onCreate()
           
 OzoneSortedSet ozoneHeadSet(java.lang.Object toElement)
          Basically nothing more than a typecasted HeadSet method.
 OzoneSortedSet ozoneSubSet(java.lang.Object fromElement, java.lang.Object toElement)
          Basically nothing more than a typecasted SubSet method.
 OzoneSortedSet ozoneTailSet(java.lang.Object toElement)
          Basically nothing more than a typecasted TailSet method.
 boolean remove(java.lang.Object obj)
          If the supplied Object is in this Set, it is removed, and true is returned; otherwise, false is returned.
 int size()
          Returns the number of elements in this Set
 java.lang.String toString()
          Returns a string representation of the object.
 
Methods inherited from class org.ozoneDB.collections.AbstractOzoneSet
equals, hashCode, removeAll
 
Methods inherited from class org.ozoneDB.collections.AbstractOzoneCollection
containsAll, retainAll, toArray, toArray
 
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
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface org.ozoneDB.collections.OzoneCollection
removeAll, retainAll
 
Methods inherited from interface java.util.Collection
containsAll, equals, hashCode, toArray, toArray
 
Methods inherited from interface org.ozoneDB.OzoneCompatibleOrProxy
getObjectID
 
Methods inherited from interface java.util.Set
containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray
 
Methods inherited from interface java.util.SortedSet
headSet, subSet, tailSet
 

Field Detail

map

protected java.util.SortedMap map
The SortedMap which backs this Set.

Constructor Detail

BaseTreeSetImpl

public BaseTreeSetImpl()
Construct a new TreeSet whose backing TreeMap using the "natural" ordering of keys. Elements that are not mutually comparable will cause ClassCastExceptions down the road.

See Also:
Comparable

BaseTreeSetImpl

protected BaseTreeSetImpl(int ctorWithoutCreatingNewBackingMap)
Basically a hack to prevent creationg of yet another map which backs this BaseTreeSet but will be overwritten almost immediately by ctor FullTreeSetImpl(SortedMap backingMap, DoNotUse_SeeJavadoc x)


BaseTreeSetImpl

public BaseTreeSetImpl(java.util.Comparator comparator)
Construct a new TreeSet whose backing TreeMap uses the supplied Comparator. Elements that are not mutually comparable will cause ClassCastExceptions down the road.

Parameters:
comparator - the Comparator this Set will use

BaseTreeSetImpl

public BaseTreeSetImpl(java.util.Collection collection)
Construct a new TreeSet whose backing TreeMap uses the "natural" orering of the keys and which contains all of the elements in the supplied Collection. This runs in n*log(n) time.

Parameters:
collection - the new Set will be initialized with all of the elements in this Collection
Throws:
java.lang.ClassCastException - if the elements of the collection are not comparable
java.lang.NullPointerException - if the collection is null
See Also:
Comparable

BaseTreeSetImpl

public BaseTreeSetImpl(java.util.SortedSet sortedSet)
Construct a new TreeSet, using the same key ordering as the supplied SortedSet and containing all of the elements in the supplied SortedSet. This constructor runs in linear time.

Parameters:
sortedSet - the new TreeSet will use this SortedSet's comparator and will initialize itself with all its elements
Throws:
java.lang.NullPointerException - if sortedSet is null
Method Detail

onCreate

public void onCreate()
Specified by:
onCreate in interface org.ozoneDB.OzoneCompatible

add

public boolean add(java.lang.Object obj)
Adds the spplied Object to the Set if it is not already in the Set; returns true if the element is added, false otherwise.

Specified by:
add in interface OzoneCollection
Overrides:
add in class AbstractOzoneCollection
Parameters:
obj - the Object to be added to this Set
Returns:
true if the add operation caused the Collection to change
Throws:
java.lang.ClassCastException - if the element cannot be compared with objects already in the set

addAll

public boolean addAll(java.util.Collection c)
Adds all of the elements in the supplied Collection to this TreeSet.

Specified by:
addAll in interface OzoneCollection
Overrides:
addAll in class AbstractOzoneCollection
Parameters:
c - The collection to add
Returns:
true if the Set is altered, false otherwise
Throws:
java.lang.NullPointerException - if c is null
java.lang.ClassCastException - if an element in c cannot be compared with objects already in the set
See Also:
AbstractOzoneCollection.add(Object)

clear

public void clear()
Removes all elements in this Set.

Specified by:
clear in interface OzoneCollection
Overrides:
clear in class AbstractOzoneCollection
See Also:
Iterator.remove()

comparator

public java.util.Comparator comparator()
Returns this Set's comparator.

Specified by:
comparator in interface java.util.SortedSet
Returns:
the comparator, or null if the set uses natural ordering

contains

public boolean contains(java.lang.Object obj)
Returns true if this Set contains the supplied Object, false otherwise.

Specified by:
contains in interface java.util.Collection
Overrides:
contains in class AbstractOzoneCollection
Parameters:
obj - the Object to check for
Returns:
true if it is in the set
Throws:
java.lang.ClassCastException - if obj cannot be compared with objects already in the set

first

public java.lang.Object first()
Returns the first (by order) element in this Set.

Specified by:
first in interface java.util.SortedSet
Returns:
the first element
Throws:
java.util.NoSuchElementException - if the set is empty

isEmpty

public boolean isEmpty()
Returns true if this Set has size 0, false otherwise.

Specified by:
isEmpty in interface java.util.Collection
Overrides:
isEmpty in class AbstractOzoneCollection
Returns:
true if the set is empty
See Also:
AbstractOzoneCollection.size()

iterator

public java.util.Iterator iterator()
Returns in Iterator over the elements in this TreeSet, which traverses in ascending order.

Specified by:
iterator in interface java.util.Collection
Specified by:
iterator in class AbstractOzoneCollection
Returns:
an iterator

_org_ozoneDB_internalIterator

public java.util.Iterator _org_ozoneDB_internalIterator()
Specified by:
_org_ozoneDB_internalIterator in interface OzoneCollection

last

public java.lang.Object last()
Returns the last (by order) element in this Set.

Specified by:
last in interface java.util.SortedSet
Returns:
the last element
Throws:
java.util.NoSuchElementException - if the set is empty

remove

public boolean remove(java.lang.Object obj)
If the supplied Object is in this Set, it is removed, and true is returned; otherwise, false is returned.

Specified by:
remove in interface OzoneCollection
Overrides:
remove in class AbstractOzoneCollection
Parameters:
obj - the Object to remove from this Set
Returns:
true if the set was modified
Throws:
java.lang.ClassCastException - if obj cannot be compared to set elements
See Also:
Iterator.remove()

size

public int size()
Returns the number of elements in this Set

Specified by:
size in interface java.util.Collection
Specified by:
size in class AbstractOzoneCollection
Returns:
the set size

getClientCollection

public java.util.Collection getClientCollection()

Returns a Collection that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneCollection. I.e. the contents of this OzoneCollection instance are always copied to the client by use of serialization.
Note that the difference of calling iterator() compared to getClientCollection().iterator() is that in the first case you go through the real collection on the server and in the second case you go through a local copy on the client side.

Note that all subclasses of OzoneCollection (or OzoneMap) have getClientXxx() member functions that returns a collection of type Xxx; these simply return a typecasted result value from getClientCollection() or getClientMap.

Specified by:
getClientCollection in interface OzoneCollection
Overrides:
getClientCollection in class AbstractOzoneCollection

getClientSet

public java.util.Set getClientSet()

Returns a Set that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneSet. I.e. the contents of this OzoneSet instance are always copied to the client by use of serialization.

Note that the difference of calling iterator() compared to getClientSet().iterator() is that in the first case you go through the real collection on the server and in the second case you go through a local copy on the client side.

Specified by:
getClientSet in interface OzoneSet
Overrides:
getClientSet in class AbstractOzoneSet

getClientSortedSet

public java.util.SortedSet getClientSortedSet()

Returns a SortedSet that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneSortedSet. I.e. the contents of this OzoneSortedSet instance are always copied to the client by use of serialization.

Note that the difference of calling iterator() compared to getClientSortedSet().iterator() is that in the first case you go through the real collection on the server and in the second case you go through a local copy on the client side.

Specified by:
getClientSortedSet in interface OzoneSortedSet

ozoneHeadSet

public OzoneSortedSet ozoneHeadSet(java.lang.Object toElement)

Basically nothing more than a typecasted HeadSet method. Because subsets are also OzoneSortedSets, this method is provided to do away with the need for a typecast.

Specified by:
ozoneHeadSet in interface OzoneSortedSet

ozoneSubSet

public OzoneSortedSet ozoneSubSet(java.lang.Object fromElement,
                                  java.lang.Object toElement)

Basically nothing more than a typecasted SubSet method. Because subsets are also OzoneSortedSets, this method is provided to do away with the need for a typecast.

Specified by:
ozoneSubSet in interface OzoneSortedSet

ozoneTailSet

public OzoneSortedSet ozoneTailSet(java.lang.Object toElement)

Basically nothing more than a typecasted TailSet method.

Because subsets are also OzoneSortedSets, this method is provided to do away with the need for a typecast.

Specified by:
ozoneTailSet in interface OzoneSortedSet

getClientTreeSet

public java.util.TreeSet getClientTreeSet()

Returns a TreeSet that contains the same entries as this persistent one; it is (by nature of the client-server enviromnent) always a 'deep' copy of this OzoneTreeSet. I.e. the contents of this OzoneTreeSet instance are always copied to the client by use of serialization.

Note that the difference of calling iterator() compared to getClientTreeSet().iterator() is that in the first case you go through the real collection on the server and in the second case you go through a local copy on the client side.

Specified by:
getClientTreeSet in interface OzoneTreeSet

toString

public java.lang.String toString()
Returns a string representation of the object. In general, the toString method returns a string that "textually represents" this object. The result should be a concise but informative representation that is easy for a person to read. It is recommended that all subclasses override this method.

The toString method for class Object returns a string consisting of the name of the class of which the object is an instance, the at-sign character `@', and the unsigned hexadecimal representation of the hash code of the object. In other words, this method returns a string equal to the value of:

 getClass().getName() + '@' + Integer.toHexString(hashCode())
 

Overrides:
toString in class AbstractOzoneCollection
Returns:
a string representation of the object.

newBackingMap

protected abstract java.util.SortedMap newBackingMap()

newBackingMap

protected abstract java.util.SortedMap newBackingMap(java.util.Comparator comparator)


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