Prev Class | Next Class | Frames | No Frames |

Summary: Nested | Field | Method | Constr | Detail: Nested | Field | Method | Constr |

`java.lang.Object`

`java.util.AbstractCollection<E>`

`java.util.AbstractSet<E>`

`java.util.TreeSet<T>`

**Implemented Interfaces:**- NavigableSet, Cloneable, Collection<E>, Iterable<E>, Serializable, Set<E>

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

**See Also:**`Collection`

,`Set`

,`HashSet`

,`LinkedHashSet`

,`Comparable`

,`Comparator`

,`Collections.synchronizedSortedSet(SortedSet)`

,`TreeMap`

, Serialized Form

## Constructor Summary

`TreeSet()`

- Construct a new TreeSet whose backing TreeMap using the "natural" ordering of keys.

`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.

`TreeSet(T> comparator)`

- Construct a new TreeSet whose backing TreeMap uses the supplied Comparator.

`TreeSet(T> 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.

## Method Summary

`boolean`

`add(T 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(T> c)`

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

`T`

`ceiling(T e)`

- Returns the least or lowest element in the set greater than or
equal to the given element, or
`null`

if there is no such element.

`void`

`clear()`

- Removes all elements in this Set.

`Object`

`clone()`

- Returns a shallow copy of this Set.

`boolean`

`Iterator`

`descendingIterator()`

- Returns an iterator over the elements of this set in descending order.

`NavigableSet`

`descendingSet()`

- Returns a view of the set in reverse order.

`T`

`first()`

- Returns the first (by order) element in this Set.

`T`

`floor(T e)`

- Returns the greatest or highest element in the set less than or
equal to the given element, or
`null`

if there is no such element.

`SortedSet`

`headSet(T to)`

- Returns a view of this Set including all elements less than
`to`

.

`NavigableSet`

`headSet(T to, boolean inclusive)`

- Returns a view of this Set including all elements less than
(or equal to, if
`inclusive`

is true)`to`

.

`T`

`higher(T e)`

- Returns the least or lowest element in the set strictly greater
than the given element, or
`null`

if there is no such element.

`boolean`

`isEmpty()`

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

`Iterator`

`iterator()`

- Returns in Iterator over the elements in this TreeSet, which traverses in ascending order.

`T`

`last()`

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

`T`

`lower(T e)`

- Returns the greatest or highest element in the set strictly less
than the given element, or
`null`

if there is no such element.

`T`

`pollFirst()`

- Removes and returns the least or lowest element in the set,
or
`null`

if the map is empty.

`T`

`pollLast()`

- Removes and returns the greatest or highest element in the set,
or
`null`

if the map is empty.

`boolean`

`int`

`size()`

- Returns the number of elements in this Set

`SortedSet`

`subSet(T from, T to)`

- Returns a view of this Set including all elements greater or equal to
`from`

and less than`to`

(a half-open interval).

`NavigableSet`

`subSet(T from, boolean fromInclusive, T to, boolean toInclusive)`

- Returns a view of this Set including all elements greater than (or equal to,
if
`fromInclusive`

is true`from`

and less than (or equal to, if`toInclusive`

is true)`to`

.

`Comparator`

`super T> comparator()`

- Returns this Set's comparator.

`SortedSet`

`tailSet(T from)`

- Returns a view of this Set including all elements greater or equal to
`from`

.

`NavigableSet`

`tailSet(T from, boolean inclusive)`

- Returns a view of this Set including all elements greater (or equal to,
if
`inclusive`

is true)`from`

.

### Methods inherited from class java.util.AbstractSet<E>

`equals`

,`hashCode`

,`removeAll`

### Methods inherited from class java.util.AbstractCollection<E>

`T[] toArray`

,`add`

,`addAll`

,`clear`

,`contains`

,`containsAll`

,`isEmpty`

,`iterator`

,`remove`

,`removeAll`

,`retainAll`

,`size`

,`toArray`

,`toString`

### Methods inherited from class java.lang.Object

`clone`

,`equals`

,`extends Object> getClass`

,`finalize`

,`hashCode`

,`notify`

,`notifyAll`

,`toString`

,`wait`

,`wait`

,`wait`

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`

public TreeSet(SortedSetsortedSet)

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:`NullPointerException`

- if sortedSet is null

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

public TreeSet(T> 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:`ClassCastException`

- if the elements of the collection are not comparable`NullPointerException`

- if the collection is null

See Also:`Comparable`

public boolean add(T 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.

Parameters:`obj`

- the Object to be added to this Set

Throws:`ClassCastException`

- if the element cannot be compared with objects already in the set

public boolean addAll(T> c)

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

Parameters:`c`

- The collection to add

Returns:- true if the Set is altered, false otherwise

Throws:`NullPointerException`

- if c is null`ClassCastException`

- if an element in c cannot be compared with objects already in the set

public T ceiling(T e)

Returns the least or lowest element in the set greater than or equal to the given element, or`null`

if there is no such element.

Parameters:`e`

- the element relative to the returned element.

Returns:- the least element greater than or equal to the given element, or
`null`

if there is no such element.

Throws:`ClassCastException`

- if the specified element can not be compared with those in the map.`NullPointerException`

- if the element is`null`

and this set either uses natural ordering or a comparator that does not permit null elements.

Since:- 1.6

public void clear()

Removes all elements in this Set.

Specified by:- clear in interface Set<E>
- clear in interface Collection<E>

Overrides:- clear in interface AbstractCollection<E>

public Object clone()

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

Returns:- the cloned set

public boolean contains(Object obj)

Returns true if this Set contains the supplied Object, false otherwise.

Specified by:- contains in interface Set<E>
- contains in interface Collection<E>

Overrides:- contains in interface AbstractCollection<E>

Parameters:`obj`

- the Object to check for

Returns:- true if it is in the set

Throws:`ClassCastException`

- if obj cannot be compared with objects already in the set

public IteratordescendingIterator()

Returns an iterator over the elements of this set in descending order. This is equivalent to calling`descendingSet().iterator()`

.

Returns:- an iterator over the elements in descending order.

Since:- 1.6

public NavigableSetdescendingSet()

Returns a view of the set in reverse order. The descending set is backed by the original set, so that changes affect both sets. Any changes occurring to either set while an iteration is taking place (with the exception of a`Iterator.remove()`

operation) result in undefined behaviour from the iteration. The ordering of the descending set is the same as for a set with a`Comparator`

given by`Collections.reverseOrder()`

, and calling`descendingSet()`

on the descending set itself results in a view equivalent to the original set.

Returns:- a reverse order view of the set.

Since:- 1.6

public T first()

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

Returns:- the first element

Throws:`NoSuchElementException`

- if the set is empty

public T floor(T e)

Returns the greatest or highest element in the set less than or equal to the given element, or`null`

if there is no such element.

Parameters:`e`

- the element relative to the returned element.

Returns:- the greatest element less than or equal to the given element, or
`null`

if there is no such element.

Throws:`ClassCastException`

- if the specified element can not be compared with those in the map.`NullPointerException`

- if the element is`null`

and this set either uses natural ordering or a comparator that does not permit null elements.

Since:- 1.6

public SortedSetheadSet(T 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`IllegalArgumentException`

for any attempt to access or add an element beyond the specified cutoff. The returned set does not include the endpoint; if you want inclusion, pass the successor element or call`headSet(T,boolean)`

. This call is equivalent to`headSet(to, false)`

.

Parameters:`to`

- the (exclusive) cutoff point

Returns:- a view of the set less than the cutoff

Throws:`ClassCastException`

- if`to`

is not compatible with the comparator (or is not Comparable, for natural ordering)`NullPointerException`

- if to is null, but the comparator does not tolerate null elements

public NavigableSetheadSet(T to, boolean inclusive)

Returns a view of this Set including all elements less than (or equal to, if`inclusive`

is true)`to`

. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an`IllegalArgumentException`

for any attempt to access or add an element beyond the specified cutoff.

Parameters:`to`

- the cutoff point`inclusive`

- true if`to`

should be included.

Returns:- a view of the set for the specified range.

Throws:`ClassCastException`

- if`to`

is not compatible with the comparator (or is not Comparable, for natural ordering)`NullPointerException`

- if to is null, but the comparator does not tolerate null elements

public T higher(T e)

Returns the least or lowest element in the set strictly greater than the given element, or`null`

if there is no such element.

Parameters:`e`

- the element relative to the returned element.

Returns:- the least element greater than the given element, or
`null`

if there is no such element.

Throws:`ClassCastException`

- if the specified element can not be compared with those in the map.`NullPointerException`

- if the element is`null`

and this set either uses natural ordering or a comparator that does not permit null elements.

Since:- 1.6

public boolean isEmpty()

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

Specified by:- isEmpty in interface Set<E>
- isEmpty in interface Collection<E>

Overrides:- isEmpty in interface AbstractCollection<E>

Returns:- true if the set is empty

public Iteratoriterator()

Returns in Iterator over the elements in this TreeSet, which traverses in ascending order.

Specified by:- iterator in interface Set<E>
- iterator in interface Collection<E>
- iterator in interface Iterable<E>

Overrides:- iterator in interface AbstractCollection<E>

Returns:- an iterator

public T last()

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

Returns:- the last element

Throws:`NoSuchElementException`

- if the set is empty

public T lower(T e)

Returns the greatest or highest element in the set strictly less than the given element, or`null`

if there is no such element.

Parameters:`e`

- the element relative to the returned element.

Returns:- the greatest element less than the given element, or
`null`

if there is no such element.

Throws:`ClassCastException`

- if the specified element can not be compared with those in the map.`NullPointerException`

- if the element is`null`

and this set either uses natural ordering or a comparator that does not permit null elements.

Since:- 1.6

public T pollFirst()

Removes and returns the least or lowest element in the set, or`null`

if the map is empty.

Returns:- the removed first element, or
`null`

if the map is empty.

Since:- 1.6

public T pollLast()

Removes and returns the greatest or highest element in the set, or`null`

if the map is empty.

Returns:- the removed last element, or
`null`

if the map is empty.

Since:- 1.6

public boolean remove(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 Set<E>
- remove in interface Collection<E>

Overrides:- remove in interface AbstractCollection<E>

Parameters:`obj`

- the Object to remove from this Set

Returns:- true if the set was modified

Throws:`ClassCastException`

- if obj cannot be compared to set elements

public int size()

Returns the number of elements in this Set

Specified by:- size in interface Set<E>
- size in interface Collection<E>

Overrides:- size in interface AbstractCollection<E>

Returns:- the set size

public SortedSetsubSet(T from, T 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`IllegalArgumentException`

for any attempt to access or add an element beyond the specified cutoffs. The returned set includes the low endpoint but not the high; if you want to reverse this behavior on either end, pass in the successor element or call`subSet(T,boolean,T,boolean)`

. This is equivalent to calling`subSet(from,true,to,false)`

.

Parameters:`from`

- the (inclusive) low cutoff point`to`

- the (exclusive) high cutoff point

Returns:- a view of the set between the cutoffs

Throws:`ClassCastException`

- if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)`NullPointerException`

- if from or to is null, but the comparator does not tolerate null elements`IllegalArgumentException`

- if from is greater than to

public NavigableSetsubSet(T from, boolean fromInclusive, T to, boolean toInclusive)

Returns a view of this Set including all elements greater than (or equal to, if`fromInclusive`

is true`from`

and less than (or equal to, if`toInclusive`

is true)`to`

. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an`IllegalArgumentException`

for any attempt to access or add an element beyond the specified cutoffs.

Parameters:`from`

- the low cutoff point`fromInclusive`

- true if`from`

should be included.`to`

- the high cutoff point`toInclusive`

- true if`to`

should be included.

Returns:- a view of the set for the specified range.

Throws:`ClassCastException`

- if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)`NullPointerException`

- if from or to is null, but the comparator does not tolerate null elements`IllegalArgumentException`

- if from is greater than to

public Comparatorsuper T> comparator()

Returns this Set's comparator.

Returns:- the comparator, or null if the set uses natural ordering

public SortedSettailSet(T 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`IllegalArgumentException`

for any attempt to access or add an element beyond the specified cutoff. The returned set includes the endpoint; if you want to exclude it, pass in the successor element or call`tailSet(T,boolean)`

. This is equivalent to calling`tailSet(from, true)`

.

Parameters:`from`

- the (inclusive) low cutoff point

Returns:- a view of the set above the cutoff

Throws:`ClassCastException`

- if`from`

is not compatible with the comparator (or is not Comparable, for natural ordering)`NullPointerException`

- if from is null, but the comparator does not tolerate null elements

public NavigableSettailSet(T from, boolean inclusive)

Returns a view of this Set including all elements greater (or equal to, if`inclusive`

is true)`from`

. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an`IllegalArgumentException`

for any attempt to access or add an element beyond the specified cutoff.

Parameters:`from`

- the low cutoff point.`inclusive`

- true if`from`

should be included.

Returns:- a view of the set for the specified range.

Throws:`ClassCastException`

- if`from`

is not compatible with the comparator (or is not Comparable, for natural ordering)`NullPointerException`

- if from is null, but the comparator does not tolerate null elements

TreeSet.java -- a class providing a TreeMap-backed SortedSet
Copyright (C) 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.
Linking this library statically or dynamically with other modules is
making a combined work based on this library. Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.
As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module. An independent module is a module which is not derived from
or based on this library. If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version.