Contents | Package | Class | Tree | Deprecated | Index | Help Java 1.2 Beta 3
PREV | NEXT SHOW LISTS | HIDE LISTS

Class java.util.TreeSet

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

public class TreeSet
extends AbstractSet
implements SortedSet, Cloneable, 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
See Also:
Collection, Set, HashSet, Comparable, Comparator, Collections.synchronizedSet, TreeMap

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(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.
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(Object o)
Returns true if this TreeSet contains the specified element.
Object  first()
Returns the first (lowest) element currently in this TreeSet.
SortedSet  headSet(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.
Object  last()
Returns the last (highest) element currently in this TreeSet.
boolean  remove(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(Object fromElement, Object toElement)
Returns a view of the portion of this TreeSet whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet  tailSet(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, notify, notifyAll, 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:
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 AbstractCollection

size

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

isEmpty

public boolean isEmpty()
Returns true if this TreeSet contains no elements.
Overrides:
isEmpty in class AbstractCollection

contains

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

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.
Overrides:
add in class AbstractCollection

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.
Overrides:
remove in class AbstractCollection

clear

public void clear()
Removes all of the elements from this Set.
Overrides:
clear in class AbstractCollection

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.

Implements:
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.
IllegalArgumentException - fromElement is greater than toElement.

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.

Implements:
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(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.

Implements:
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.
Implements:
comparator in interface SortedSet

first

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

last

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

clone

public Object clone()
Returns a shallow copy of this TreeSet. (The elements themselves are not cloned.)
Overrides:
clone in class Object

Contents | Package | Class | Tree | Deprecated | Index | Help Java 1.2 Beta 3
PREV | NEXT SHOW LISTS | HIDE LISTS

Submit a bug or feature
Submit comments/suggestions about new javadoc look.
Java is a trademark or registered trademark of Sun Microsystems, Inc. in the US and other countries.
Copyright 1993-1998 Sun Microsystems, Inc. 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. All Rights Reserved.