ptolemy.backtrack.util.java.util

Class TreeSet

java.lang.Object

ptolemy.backtrack.util.java.util.AbstractCollection

ptolemy.backtrack.util.java.util.AbstractSet

ptolemy.backtrack.util.java.util.TreeSet

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Rollbackable, Collection, Set, SortedSet

public class TreeSet
extends AbstractSet
implements SortedSet, java.lang.Cloneable, java.io.Serializable, Rollbackable

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

Author:

Jon Zeppieri, Bryce McKinlay, Eric Blake (ebb9@email.byu.edu)

See Also:

Collection, Set, HashSet, LinkedHashSet, Comparable, Comparator, Collections.synchronizedSortedSet(SortedSet), TreeMap, Serialized Form

Status

updated to 1.4

Field Summary

Fields inherited from class ptolemy.backtrack.util.java.util.AbstractCollection

$CHECKPOINT, $RECORD$$CHECKPOINT

Constructor Summary

Constructors

Constructor and Description
TreeSet() Construct a new TreeSet whose backing TreeMap using the "natural" ordering of keys.
TreeSet(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.
TreeSet(java.util.Comparator comparator) Construct a new TreeSet whose backing TreeMap uses the supplied Comparator.
TreeSet(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

Modifier and Type	Method and Description
void	$COMMIT(long timestamp) Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.
void	$RESTORE(long timestamp, boolean trim) Restore a previous state to all the private fields of this rollbackable object.
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(Collection c) Adds all of the elements in the supplied Collection to this TreeSet.
void	clear() Removes all elements in this Set.
java.lang.Object	clone() Returns a shallow copy of 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.
SortedSet	headSet(java.lang.Object to) Returns a view of this Set including all elements less than to.
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.
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
SortedSet	subSet(java.lang.Object from, java.lang.Object to) Returns a view of this Set including all elements greater or equal to from and less than to (a half-open interval).
SortedSet	tailSet(java.lang.Object from) Returns a view of this Set including all elements greater or equal to from.

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractCollection

$GET$CHECKPOINT, $SET$CHECKPOINT, containsAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface ptolemy.backtrack.util.java.util.SortedSet

$GET$CHECKPOINT, $SET$CHECKPOINT

Methods inherited from interface ptolemy.backtrack.util.java.util.Set

containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Constructor Detail

TreeSet

public TreeSet()

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

TreeSet

public TreeSet(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

TreeSet

public TreeSet(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

TreeSet

public TreeSet(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

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 Collection

Specified by:

add in interface Set

Overrides:

add in class AbstractCollection

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(Collection c)

Adds all of the elements in the supplied Collection to this TreeSet.

Specified by:

addAll in interface Collection

Specified by:

addAll in interface Set

Overrides:

addAll in class AbstractCollection

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:

AbstractCollection.add(Object)

clear

public void clear()

Removes all elements in this Set.

Specified by:

clear in interface Collection

Specified by:

clear in interface Set

Overrides:

clear in class AbstractCollection

See Also:

Iterator.remove()

clone

public java.lang.Object clone()

Returns a shallow copy of this Set. The elements are not cloned.

Overrides:

clone in class java.lang.Object

Returns:

the cloned set

comparator

public java.util.Comparator comparator()

Returns this Set's comparator.

Specified by:

comparator in interface 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 Collection

Specified by:

contains in interface Set

Overrides:

contains in class AbstractCollection

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 SortedSet

Returns:

the first element

Throws:

java.util.NoSuchElementException - if the set is empty

headSet

public SortedSet headSet(java.lang.Object to)

Returns a view of this Set including all elements less than to. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an{

Specified by:

headSet in interface SortedSet

Parameters:

to - the (exclusive) cutoff point

Returns:

a view of the set less than the cutoff

Throws:

java.lang.ClassCastException - if to is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if to is null, but the comparator does not tolerate null elements

isEmpty

public boolean isEmpty()

Returns true if this Set has size 0, false otherwise.

Specified by:

isEmpty in interface Collection

Specified by:

isEmpty in interface Set

Overrides:

isEmpty in class AbstractCollection

Returns:

true if the set is empty

See Also:

AbstractCollection.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 Collection

Specified by:

iterator in interface Set

Specified by:

iterator in class AbstractCollection

Returns:

an iterator

last

public java.lang.Object last()

Returns the last (by order) element in this Set.

Specified by:

last in interface 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 Collection

Specified by:

remove in interface Set

Overrides:

remove in class AbstractCollection

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 Collection

Specified by:

size in interface Set

Specified by:

size in class AbstractCollection

Returns:

the set size

subSet

public SortedSet subSet(java.lang.Object from,
                        java.lang.Object to)

Returns a view of this Set including all elements greater or equal to from and less than to (a half-open interval). The returned set is backed by the original, so changes in one appear in the other. The subset will throw an {

Specified by:

subSet in interface SortedSet

Parameters:

from - the (inclusive) low cutoff point

to - the (exclusive) high cutoff point

Returns:

a view of the set between the cutoffs

Throws:

java.lang.ClassCastException - if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if from or to is null, but the comparator does not tolerate null elements

java.lang.IllegalArgumentException - if from is greater than to

tailSet

public SortedSet tailSet(java.lang.Object from)

Returns a view of this Set including all elements greater or equal to from. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an{

Specified by:

tailSet in interface SortedSet

Parameters:

from - the (inclusive) low cutoff point

Returns:

a view of the set above the cutoff

Throws:

java.lang.ClassCastException - if from is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if from is null, but the comparator does not tolerate null elements

$COMMIT

public void $COMMIT(long timestamp)

Description copied from interface: Rollbackable

Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.

Specified by:

$COMMIT in interface Rollbackable

Specified by:

$COMMIT in interface Collection

Specified by:

$COMMIT in interface Set

Specified by:

$COMMIT in interface SortedSet

Overrides:

$COMMIT in class AbstractSet

Parameters:

timestamp - The timestamp.

$RESTORE

public void $RESTORE(long timestamp,
                     boolean trim)

Description copied from interface: Rollbackable

Restore a previous state to all the private fields of this rollbackable object.

Specified by:

$RESTORE in interface Rollbackable

Specified by:

$RESTORE in interface Collection

Specified by:

$RESTORE in interface Set

Specified by:

$RESTORE in interface SortedSet

Overrides:

$RESTORE in class AbstractSet

Parameters:

timestamp - The timestamp taken at the time when the previous state was recorded.

trim - Whether to delete the records used for the rollback.

See Also:

Checkpoint.rollback(long, boolean)