All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class com.sun.java.util.collections.TreeSet

java.lang.Object
   |
   +----com.sun.java.util.collections.AbstractCollection
           |
           +----com.sun.java.util.collections.AbstractSet
                   |
                   +----com.sun.java.util.collections.TreeSet

public class TreeSet
extends AbstractSet
implements SortedSet, Cloneable, Serializable
This class implements the TreeSet interface, backed by a TreeMap. This class guarantees that the Set will be in ascending element order, sorted according to the natural order of the elements (see Comparable), or by the Comparator provided at TreeSet creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Note that the ordering maintained by a TreeSet (whether or not an explicit Comparator is provided) must be total if the TreeSet is to correctly implement the Set interface. (See Comparable or Comparator for a definition of total ordering.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the TreeSet, equal. The behavior of a TreeSet is well-defined even if its ordering is strictly partial; it just fails to obey the general contract of the Set interface.

Note that this implementation is not synchronized. If multiple threads access a TreeSet concurrently, and at least one of the threads modifies the TreeSet, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the TreeSet. If no such object exists, the TreeSet should be "wrapped" using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the TreeSet:

	Set s = Collections.synchronizedSet(new TreeSet(...));
 

The Iterators returned by TreeSet's iterator method are fail-fast: if the HashSet is modified at any time after the Iterator is created, in any way except through the Iterator's own remove method, the Iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the Iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

See Also:
Collection, Set, HashSet, Comparable, Comparator, synchronizedSet, TreeMap

Constructor Index

 o TreeSet()
Constructs a new, empty TreeSet, sorted according to the elements' natural order.
 o TreeSet(Collection)
Constructs a new TreeSet containing the elements in the specified Collection, sorted according to the elements' natural order.
 o TreeSet(Comparator)
Constructs a new, empty TreeSet, sorted according to the given comparator.
 o TreeSet(SortedSet)
Constructs a new TreeSet containing the same elements as the given SortedSet, sorted according to the same ordering.

Method Index

 o add(Object)
Adds the specified element to this Set if it is not already present.
 o addAll(Collection)
Adds all of the elements in the specified Collection to this TreeSet.
 o clear()
Removes all of the elements from this Set.
 o clone()
Returns a shallow copy of this TreeSet.
 o comparator()
Returns the comparator used to order this TreeMap, or null if this TreeMap uses its keys natural ordering.
 o contains(Object)
Returns true if this TreeSet contains the specified element.
 o first()
Returns the first (lowest) element currently in this TreeSet.
 o headSet(Object)
Returns a view of the portion of this TreeSet whose elements are strictly less than toElement.
 o isEmpty()
Returns true if this TreeSet contains no elements.
 o iterator()
Returns an Iterator over the elements in this TreeSet.
 o last()
Returns the last (highest) element currently in this TreeSet.
 o remove(Object)
Removes the given element from this Set if it is present.
 o size()
Returns the number of elements in this TreeSet (its cardinality).
 o subSet(Object, Object)
Returns a view of the portion of this TreeSet whose elements range from fromElement, inclusive, to toElement, exclusive.
 o tailSet(Object)
Returns a view of the portion of this TreeSet whose elements are strictly less than toElement.

Constructors

 o TreeSet
 public TreeSet()
Constructs a new, empty TreeSet, sorted according to the elements' natural order. All elements inserted into the TreeSet must implement the Comparable interface. Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) must not throw a typeMismatchException for any elements e1 and e2 in the TreeSet. If the user attempts to add an element to the TreeSet that violates this constraint (for example, the user attempts to add a String element to a TreeSet whose elements are Integers), the add(Object) call will throw a ClassCastException.

See Also:
Comparable
 o TreeSet
 public TreeSet(Comparator c)
Constructs a new, empty TreeSet, sorted according to the given comparator. All elements inserted into the TreeSet must be mutually comparable by the given comparator: comparator.compare(e1, e2) must not throw a typeMismatchException for any elements e1 and e2 in the TreeSet. If the user attempts to add an element to the TreeSet that violates this constraint, the add(Object) call will throw a ClassCastException.

 o TreeSet
 public TreeSet(Collection c)
Constructs a new TreeSet containing the elements in the specified Collection, sorted according to the elements' natural order. All keys inserted into the TreeSet must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a typeMismatchException for any elements k1 and k2 in the TreeSet.

Throws: ClassCastException
the keys in t are not Comparable, or are not mutually comparable.
 o TreeSet
 public TreeSet(SortedSet s)
Constructs a new TreeSet containing the same elements as the given SortedSet, sorted according to the same ordering.

Methods

 o iterator
 public Iterator iterator()
Returns an Iterator over the elements in this TreeSet. The elements are returned in ascending order.

Returns:
an Iterator over the elements in this TreeSet.
Overrides:
iterator in class AbstractCollection
 o size
 public int size()
Returns the number of elements in this TreeSet (its cardinality).

Returns:
the number of elements in this TreeSet (its cardinality).
Overrides:
size in class AbstractCollection
 o isEmpty
 public boolean isEmpty()
Returns true if this TreeSet contains no elements.

Returns:
true if this TreeSet contains no elements.
Overrides:
isEmpty in class AbstractCollection
 o contains
 public boolean contains(Object o)
Returns true if this TreeSet contains the specified element.

Returns:
true if this TreeSet contains the specified element.
Throws: ClassCastException
o cannot be compared with the elements currently in the TreeSet.
Overrides:
contains in class AbstractCollection
 o add
 public boolean add(Object o)
Adds the specified element to this Set if it is not already present.

Parameters:
o - element to be added to this Set.
Returns:
true if the Set did not already contain the specified element.
Throws: ClassCastException
o cannot be compared with the elements currently in the TreeSet.
Overrides:
add in class AbstractCollection
 o remove
 public boolean remove(Object o)
Removes the given element from this Set if it is present.

Parameters:
o - object to be removed from this Set, if present.
Returns:
true if the Set contained the specified element.
Throws: ClassCastException
o cannot be compared with the elements currently in the TreeSet.
Overrides:
remove in class AbstractCollection
 o clear
 public void clear()
Removes all of the elements from this Set.

Overrides:
clear in class AbstractCollection
 o addAll
 public boolean addAll(Collection c)
Adds all of the elements in the specified Collection to this TreeSet.

Parameters:
c - elements to be added
Throws: ClassCastException
elements of c cannot be compared with the elements currently in the TreeSet.
Overrides:
addAll in class AbstractCollection
 o subSet
 public SortedSet subSet(Object fromElement,
                         Object toElement)
Returns a view of the portion of this TreeSet whose elements range from fromElement, inclusive, to toElement, exclusive. The returned Set is backed by this TreeSet, so changes in the returned Set are reflected in this TreeSet, and vice-versa. The returned Set supports all optional Set operations.

The Set returned by this method will throw an IllegalArgumentException if the user attempts to insert an element outside the specified range.

Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you need a closed range (which includes both endpoints), and the element type allows for calculation of the successor a given value, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that s is a Set of Strings. The following idiom obtains a view containing all of the Strings in s from low to high, inclusive:

    Set sub = s.subSet(low, high+"\0");
A similarly technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the Strings in s from low to high, exclusive:
    Set sub = s.subSet(low+"\0", high);

Parameters:
fromElement - low endpoint (inclusive) of the subSet.
toElement - high endpoint (exclusive) of the subSet.
Returns:
a view of the portion of this TreeSet whose elements range from fromElement, inclusive, to toElement, exclusive.
Throws: NullPointerException
fromElement or toElement is null and this TreeSet uses natural ordering, or its comparator does not tolerate null elements.
Throws: IllegalArgumentException
fromElement is greater than toElement.
 o headSet
 public SortedSet headSet(Object toElement)
Returns a view of the portion of this TreeSet whose elements are strictly less than toElement. The returned Set is backed by this TreeSet, so changes in the returned Set are reflected in this TreeSet, and vice-versa. The returned Set supports all optional Set operations.

The Set returned by this method will throw an IllegalArgumentException if the user attempts to insert an element greater than or equal to toElement.

Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a headSet bounded by successor(highEndpoint). For example, suppose that s is a Set of Strings. The following idiom obtains a view containing all of the Strings in s that are less than or equal to high:

    Set head = s.headSet(high+"\0");

Parameters:
toElement - high endpoint (exclusive) of the headSet.
Returns:
a view of the portion of this TreeSet whose elements are strictly less than toElement.
Throws: NullPointerException
toElement is null and this TreeSet uses natural ordering, or its comparator does not tolerate null elements.
 o tailSet
 public SortedSet tailSet(Object fromElement)
Returns a view of the portion of this TreeSet whose elements are strictly less than toElement. The returned Set is backed by this TreeSet, so changes in the returned Set are reflected in this TreeSet, and vice-versa. The returned Set supports all optional Set operations.

The Set returned by this method will throw an IllegalArgumentException if the user attempts to insert an element greater than or equal to toElement.

Note: this method always returns a view that contains its (low) endpoint. If you need a view that does not contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a tailSet bounded by successor(lowEndpoint). For example, suppose that s is a Set of Strings. The following idiom obtains a view containing all of the Strings in s that are strictly greater than low:

    Set tail = s.tailSet(low+"\0");

Parameters:
fromElement - low endpoint (inclusive) of the tailSet.
Returns:
a view of the portion of this TreeSet whose elements are strictly less than toElement.
Throws: NullPointerException
fromElement is null and this TreeSet uses natural ordering, or its comparator does not tolerate null elements.
 o comparator
 public Comparator comparator()
Returns the comparator used to order this TreeMap, or null if this TreeMap uses its keys natural ordering.

Returns:
the comparator used to order this TreeMap, or null if this TreeMap uses its keys natural ordering.
 o first
 public Object first()
Returns the first (lowest) element currently in this TreeSet.

Returns:
the first (lowest) element currently in this TreeSet.
Throws: NoSuchElementException
Set is empty.
 o last
 public Object last()
Returns the last (highest) element currently in this TreeSet.

Returns:
the last (highest) element currently in this TreeSet.
Throws: NoSuchElementException
Set is empty.
 o clone
 public Object clone()
Returns a shallow copy of this TreeSet. (The elements themselves are not cloned.)

Returns:
a shallow copy of this TreeSet.
Overrides:
clone in class Object

All Packages  Class Hierarchy  This Package  Previous  Next  Index