TreeSet (Java 2 Platform SE 5.0) (original) (raw)


java.util

Class TreeSet

java.lang.Object extended by java.util.AbstractCollection extended by java.util.AbstractSet extended by java.util.TreeSet

All Implemented Interfaces:

Serializable, Cloneable, Iterable, Collection, Set, SortedSet


public class TreeSet

extends AbstractSet

implements SortedSet, Cloneable, Serializable

This class implements the Set interface, backed by aTreeMap instance. This class guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements (see Comparable), or by the comparator provided at set 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 set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all key comparisons using its compareTo (orcompare) method, so two keys that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set_is_ well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

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

 SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

The Iterators returned by this class's iterator method are_fail-fast_: if the set 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.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

This class is a member of the Java Collections Framework.

Since:

1.2

See Also:

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


Constructor Summary
TreeSet() Constructs a new, empty set, sorted according to the elements' natural order.
TreeSet(Collection<? extends E> c) Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order.
TreeSet(Comparator<? super E> c) Constructs a new, empty set, sorted according to the specified comparator.
TreeSet(SortedSet<E> s) Constructs a new set containing the same elements as the specified sorted set, sorted according to the same ordering.
Method Summary
boolean add(E o) Adds the specified element to this set if it is not already present.
boolean addAll(Collection<? extends E> c) Adds all of the elements in the specified collection to this set.
void clear() Removes all of the elements from this set.
Object clone() Returns a shallow copy of this TreeSet instance.
Comparator<? super E> comparator() Returns the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.
boolean contains(Object o) Returns true if this set contains the specified element.
E first() Returns the first (lowest) element currently in this sorted set.
SortedSet<E> headSet(E toElement) Returns a view of the portion of this set whose elements are strictly less than toElement.
boolean isEmpty() Returns true if this set contains no elements.
Iterator<E> iterator() Returns an iterator over the elements in this set.
E last() Returns the last (highest) element currently in this sorted set.
boolean remove(Object o) Removes the specified element from this set if it is present.
int size() Returns the number of elements in this set (its cardinality).
SortedSet<E> [subSet](../../java/util/TreeSet.html#subSet%28E, E%29)(E fromElement,E toElement) Returns a view of the portion of this set whose elements range fromfromElement, inclusive, to toElement, exclusive.
SortedSet<E> tailSet(E fromElement) Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
Methods inherited from class java.util.AbstractCollection
containsAll, retainAll, toArray, toArray, toString
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, [wait](../../java/lang/Object.html#wait%28long, int%29)
Methods inherited from interface java.util.Set
containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray
Constructor Detail

TreeSet

public TreeSet()

Constructs a new, empty set, sorted according to the elements' natural order. All elements inserted into the set must implement theComparable interface. Furthermore, all such elements must be_mutually comparable_: e1.compareTo(e2) must not throw aClassCastException for any elements e1 ande2 in the set. If the user attempts to add an element to the set that violates this constraint (for example, the user attempts to add a string element to a set whose elements are integers), theadd(Object) call will throw a ClassCastException.

See Also:

Comparable


TreeSet

public TreeSet(Comparator<? super E> c)

Constructs a new, empty set, sorted according to the specified comparator. All elements inserted into the set must be mutually comparable by the specified comparator: comparator.compare(e1, e2) must not throw a ClassCastException for any elementse1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint, theadd(Object) call will throw a ClassCastException.

Parameters:

c - the comparator that will be used to sort this set. Anull value indicates that the elements' natural ordering should be used.


TreeSet

public TreeSet(Collection<? extends E> c)

Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order. All keys inserted into the set must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw aClassCastException for any elements k1 andk2 in the set.

Parameters:

c - The elements that will comprise the new set.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if the keys in the specified collection are not comparable, or are not mutually comparable.

[NullPointerException](../../java/lang/NullPointerException.html "class in java.lang") - if the specified collection is null.


TreeSet

public TreeSet(SortedSet<E> s)

Constructs a new set containing the same elements as the specified sorted set, sorted according to the same ordering.

Parameters:

s - sorted set whose elements will comprise the new set.

Throws:

[NullPointerException](../../java/lang/NullPointerException.html "class in java.lang") - if the specified sorted set is null.

Method Detail

iterator

public Iterator<E> iterator()

Returns an iterator over the elements in this set. The elements are returned in ascending order.

Specified by:

[iterator](../../java/lang/Iterable.html#iterator%28%29) in interface [Iterable](../../java/lang/Iterable.html "interface in java.lang")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[iterator](../../java/util/Collection.html#iterator%28%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[iterator](../../java/util/Set.html#iterator%28%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[iterator](../../java/util/AbstractCollection.html#iterator%28%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Returns:

an iterator over the elements in this set.


size

public int size()

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

Specified by:

[size](../../java/util/Collection.html#size%28%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[size](../../java/util/Set.html#size%28%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[size](../../java/util/AbstractCollection.html#size%28%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Returns:

the number of elements in this set (its cardinality).


isEmpty

public boolean isEmpty()

Returns true if this set contains no elements.

Specified by:

[isEmpty](../../java/util/Collection.html#isEmpty%28%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[isEmpty](../../java/util/Set.html#isEmpty%28%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Overrides:

[isEmpty](../../java/util/AbstractCollection.html#isEmpty%28%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Returns:

true if this set contains no elements.


contains

public boolean contains(Object o)

Returns true if this set contains the specified element.

Specified by:

[contains](../../java/util/Collection.html#contains%28java.lang.Object%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[contains](../../java/util/Set.html#contains%28java.lang.Object%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Overrides:

[contains](../../java/util/AbstractCollection.html#contains%28java.lang.Object%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

o - the object to be checked for containment in this set.

Returns:

true if this set contains the specified element.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if the specified object cannot be compared with the elements currently in the set.


add

public boolean add(E o)

Adds the specified element to this set if it is not already present.

Specified by:

[add](../../java/util/Collection.html#add%28E%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[add](../../java/util/Set.html#add%28E%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Overrides:

[add](../../java/util/AbstractCollection.html#add%28E%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

o - element to be added to this set.

Returns:

true if the set did not already contain the specified element.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if the specified object cannot be compared with the elements currently in the set.


remove

public boolean remove(Object o)

Removes the specified element from this set if it is present.

Specified by:

[remove](../../java/util/Collection.html#remove%28java.lang.Object%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[remove](../../java/util/Set.html#remove%28java.lang.Object%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Overrides:

[remove](../../java/util/AbstractCollection.html#remove%28java.lang.Object%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

o - object to be removed from this set, if present.

Returns:

true if the set contained the specified element.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if the specified object cannot be compared with the elements currently in the set.


clear

public void clear()

Removes all of the elements from this set.

Specified by:

[clear](../../java/util/Collection.html#clear%28%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[clear](../../java/util/Set.html#clear%28%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Overrides:

[clear](../../java/util/AbstractCollection.html#clear%28%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>


addAll

public boolean addAll(Collection<? extends E> c)

Adds all of the elements in the specified collection to this set.

Specified by:

[addAll](../../java/util/Collection.html#addAll%28java.util.Collection%29) in interface [Collection](../../java/util/Collection.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Specified by:

[addAll](../../java/util/Set.html#addAll%28java.util.Collection%29) in interface [Set](../../java/util/Set.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Overrides:

[addAll](../../java/util/AbstractCollection.html#addAll%28java.util.Collection%29) in class [AbstractCollection](../../java/util/AbstractCollection.html "class in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

c - elements to be added

Returns:

true if this set changed as a result of the call.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if the elements provided cannot be compared with the elements currently in the set.

[NullPointerException](../../java/lang/NullPointerException.html "class in java.lang") - of the specified collection is null.

See Also:

AbstractCollection.add(Object)


subSet

public SortedSet<E> subSet(E fromElement, E toElement)

Returns a view of the portion of this set whose elements range fromfromElement, inclusive, to toElement, exclusive. (IffromElement and toElement are equal, the returned sorted set is empty.) The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional Set operations.

The sorted set returned by this method will throw anIllegalArgumentException 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 of a specified value, merely request the subrange from lowEndpoint tosuccessor(highEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s from low tohigh, inclusive:

 SortedSet sub = s.subSet(low, high+"\0");

A similar 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 tohigh, exclusive:

 SortedSet sub = s.subSet(low+"\0", high);

Specified by:

[subSet](../../java/util/SortedSet.html#subSet%28E, E%29) in interface [SortedSet](../../java/util/SortedSet.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

fromElement - low endpoint (inclusive) of the subSet.

toElement - high endpoint (exclusive) of the subSet.

Returns:

a view of the portion of this set whose elements range fromfromElement, inclusive, to toElement, exclusive.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if fromElement andtoElement cannot be compared to one another using this set's comparator (or, if the set has no comparator, using natural ordering).

[IllegalArgumentException](../../java/lang/IllegalArgumentException.html "class in java.lang") - if fromElement is greater thantoElement.

[NullPointerException](../../java/lang/NullPointerException.html "class in java.lang") - if fromElement ortoElement is null and this set uses natural order, or its comparator does not tolerate null elements.


headSet

public SortedSet<E> headSet(E toElement)

Returns a view of the portion of this set whose elements are strictly less than toElement. The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional set operations.

The sorted set returned by this method will throw anIllegalArgumentException 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 of a specified value, merely request a headSet bounded bysuccessor(highEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s that are less than or equal to high:

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

Specified by:

[headSet](../../java/util/SortedSet.html#headSet%28E%29) in interface [SortedSet](../../java/util/SortedSet.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

toElement - high endpoint (exclusive) of the headSet.

Returns:

a view of the portion of this set whose elements are strictly less than toElement.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if toElement is not compatible with this set's comparator (or, if the set has no comparator, if toElement does not implement Comparable).

[IllegalArgumentException](../../java/lang/IllegalArgumentException.html "class in java.lang") - if this set is itself a subSet, headSet, or tailSet, and toElement is not within the specified range of the subSet, headSet, or tailSet.

[NullPointerException](../../java/lang/NullPointerException.html "class in java.lang") - if toElement is null and this set uses natural ordering, or its comparator does not tolerate null elements.


tailSet

public SortedSet<E> tailSet(E fromElement)

Returns a view of the portion of this set whose elements are greater than or equal to fromElement. The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional set operations.

The sorted set returned by this method will throw anIllegalArgumentException if the user attempts to insert an element less than fromElement. 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 of a specified value, merely request a tailSet bounded bysuccessor(lowEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s that are strictly greater than low:

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

Specified by:

[tailSet](../../java/util/SortedSet.html#tailSet%28E%29) in interface [SortedSet](../../java/util/SortedSet.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Parameters:

fromElement - low endpoint (inclusive) of the tailSet.

Returns:

a view of the portion of this set whose elements are greater than or equal to fromElement.

Throws:

[ClassCastException](../../java/lang/ClassCastException.html "class in java.lang") - if fromElement is not compatible with this set's comparator (or, if the set has no comparator, if fromElement does not implement Comparable).

[IllegalArgumentException](../../java/lang/IllegalArgumentException.html "class in java.lang") - if this set is itself a subSet, headSet, or tailSet, and fromElement is not within the specified range of the subSet, headSet, or tailSet.

[NullPointerException](../../java/lang/NullPointerException.html "class in java.lang") - if fromElement is null and this set uses natural ordering, or its comparator does not tolerate null elements.


comparator

public Comparator<? super E> comparator()

Returns the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.

Specified by:

[comparator](../../java/util/SortedSet.html#comparator%28%29) in interface [SortedSet](../../java/util/SortedSet.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Returns:

the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.


first

public E first()

Returns the first (lowest) element currently in this sorted set.

Specified by:

[first](../../java/util/SortedSet.html#first%28%29) in interface [SortedSet](../../java/util/SortedSet.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Returns:

the first (lowest) element currently in this sorted set.

Throws:

[NoSuchElementException](../../java/util/NoSuchElementException.html "class in java.util") - sorted set is empty.


last

public E last()

Returns the last (highest) element currently in this sorted set.

Specified by:

[last](../../java/util/SortedSet.html#last%28%29) in interface [SortedSet](../../java/util/SortedSet.html "interface in java.util")<[E](../../java/util/TreeSet.html "type parameter in TreeSet")>

Returns:

the last (highest) element currently in this sorted set.

Throws:

[NoSuchElementException](../../java/util/NoSuchElementException.html "class in java.util") - sorted set is empty.


clone

public Object clone()

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

Overrides:

[clone](../../java/lang/Object.html#clone%28%29) in class [Object](../../java/lang/Object.html "class in java.lang")

Returns:

a shallow copy of this set.

See Also:

Cloneable



Submit a bug or feature
For further API reference and developer documentation, see Java 2 SDK SE Developer Documentation. That documentation contains more detailed, developer-targeted descriptions, with conceptual overviews, definitions of terms, workarounds, and working code examples.

Copyright © 2004, 2010 Oracle and/or its affiliates. All rights reserved. Use is subject to license terms. Also see the documentation redistribution policy.