Class java.util.TreeSet


Overview \| Package \| Class \| Tree \| Index \| Help
PREV CLASS \| NEXT CLASS	FRAMES \| NO FRAMES
SUMMARY: INNER \| FIELD \| CONSTR \| METHOD	DETAIL: FIELD \| CONSTR \| METHOD

Class java.util.TreeSet

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--java.util.AbstractSet
              |
              +--java.util.TreeSet

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

This class implements the Set interface, backed by a TreeMap. This class guarantees that the Map will be in ascending key order, sorted according to the natural order for the key Class (see Comparable), or by the Comparator provided at TreeSet creation time, depending on which constructor is used. Note that this ordering must be total in order for the Tree to function properly. (A total ordering is an ordering for which a.compareTo(b)==0 implies that a.equals(b); see OrderedSet for further details.)

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

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.

Since:: JDK1.2
Version:: 1.10 05/06/98
See Also:: Collection, Set, java.util.HashSet, java.lang.Comparable, Comparator, Collections.synchronizedSet, TreeMap, Serialized Form

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

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

Methods inherited from class java.util.AbstractSet
equals, hashCode

Methods inherited from class java.util.AbstractCollection
add, addAll, clear, contains, containsAll, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray, toString

Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notifyAll, notify, toString, wait, wait, wait

Constructor Detail

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:: java.lang.Comparable

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.

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.

TreeSet

public TreeSet(SortedSet s)

Constructs a new TreeSet containing the same elements as the given SortedSet, sorted according to the same ordering.

Method Detail

iterator

public Iterator iterator()

Returns an Iterator over the elements in this TreeSet. The elements are returned in ascending order.

Overrides:: iterator in class java.util.AbstractCollection

size

public int size()

Returns the number of elements in this TreeSet (its cardinality).

Overrides:: size in class java.util.AbstractCollection

isEmpty

public boolean isEmpty()

Returns true if this TreeSet contains no elements.

Overrides:: isEmpty in class java.util.AbstractCollection

contains

public boolean contains(java.lang.Object o)

Returns true if this TreeSet contains the specified element.

Overrides:: contains in class java.util.AbstractCollection

add

public boolean add(java.lang.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.
Overrides:: add in class java.util.AbstractCollection

remove

public boolean remove(java.lang.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.
Overrides:: remove in class java.util.AbstractCollection

clear

public void clear()

Removes all of the elements from this Set.

Overrides:: clear in class java.util.AbstractCollection

subSet

public SortedSet subSet(java.lang.Object fromElement,
                        java.lang.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.

Specified by:: subSet in interface SortedSet
Parameters:: fromElement - low endpoint (inclusive) of the subSet.; toElement - high endpoint (exclusive) of the subSet.
Throws:: ClassCastException - fromElement or toElement cannot be compared with the elements currently in the TreeSet.; NullPointerException - fromElement or toElement is null and this TreeSet uses natural ordering, or its comparator does not tolerate null elements.; java.lang.IllegalArgumentException - fromElement is greater than toElement.

headSet

public SortedSet headSet(java.lang.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.

Specified by:: headSet in interface SortedSet
Parameters:: toElement - high endpoint (exclusive) of the headSet.
Throws:: ClassCastException - toElement cannot be compared with the elements currently in the TreeSet.; NullPointerException - toElement is null and this TreeSet uses natural ordering, or its comparator does not tolerate null elements.

tailSet

public SortedSet tailSet(java.lang.Object fromElement)

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

Specified by:: tailSet in interface SortedSet
Parameters:: toElement - high endpoint (exclusive) of the headSet.
Throws:: ClassCastException - toElement cannot be compared with the elements currently in the TreeSet.; NullPointerException - toElement is null and this TreeSet uses natural ordering, or its comparator does not tolerate null elements.

comparator

public Comparator comparator()

Returns the comparator used to order this TreeMap, or null if this TreeMap uses its keys natural ordering.

Specified by:: comparator in interface SortedSet

first

public java.lang.Object first()

Returns the first (lowest) element currently in this TreeSet.

Specified by:: first in interface SortedSet
Returns:: the first (lowest) element currently in this TreeSet.
Throws:: NoSuchElementException - Set is empty.

last

public java.lang.Object last()

Returns the last (highest) element currently in this TreeSet.

Specified by:: last in interface SortedSet
Returns:: the last (highest) element currently in this TreeSet.
Throws:: NoSuchElementException - Set is empty.

clone

public java.lang.Object clone()

Returns a shallow copy of this TreeSet. (The elements themselves are not cloned.)

Overrides:: clone in class java.lang.Object


Overview \| Package \| Class \| Tree \| Index \| Help
PREV CLASS \| NEXT CLASS	FRAMES \| NO FRAMES
SUMMARY: INNER \| FIELD \| CONSTR \| METHOD	DETAIL: FIELD \| CONSTR \| METHOD


Overview \| Package \| Class \| Tree \| Index \| Help
PREV CLASS \| NEXT CLASS	FRAMES \| NO FRAMES
SUMMARY: INNER \| FIELD \| CONSTR \| METHOD	DETAIL: FIELD \| CONSTR \| METHOD


Overview \| Package \| Class \| Tree \| Index \| Help
PREV CLASS \| NEXT CLASS	FRAMES \| NO FRAMES
SUMMARY: INNER \| FIELD \| CONSTR \| METHOD	DETAIL: FIELD \| CONSTR \| METHOD