A
NavigableSet implementation based on a
TreeMap.
The elements are ordered using their
natural
ordering, or by a
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 element comparisons using its compareTo (or
compare) method, so two elements 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 tree 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 the
Collections.synchronizedSortedSet
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.
| Constructors |
|---|
| public |
TreeSet()
Constructs a new, empty tree set, sorted according to the
natural ordering of its elements. All elements inserted into
the set must implement the Comparable interface.
Furthermore, all such elements must be mutually
comparable: e1.compareTo(e2) must not throw a
ClassCastException for any elements e1 and
e2 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), the add call will throw a
ClassCastException.
|
| public |
TreeSet(Comparator comparator)
Constructs a new, empty tree 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 elements
e1 and e2 in the set. If the user attempts to add
an element to the set that violates this constraint, the
add call will throw a ClassCastException.
| comparator | the comparator that will be used to order this set.
If null, the natural
ordering of the elements will be used. |
|
| public |
TreeSet(Collection c)
Constructs a new tree set containing the elements in the specified
collection, sorted according to the natural ordering of its
elements. All elements inserted into the set must implement the
Comparable interface. Furthermore, all such elements must be
mutually comparable: e1.compareTo(e2) must not throw a
ClassCastException for any elements e1 and
e2 in the set.
|
| public |
TreeSet(SortedSet s)
Constructs a new tree set containing the same elements and
using the same ordering as the specified sorted set.
| s | sorted set whose elements will comprise the new set |
| Throws | NullPointerException: if the specified sorted set is null |
|
| Methods |
|---|
| public boolean |
add(Object e)
Adds the specified element to this set if it is not already present.
More formally, adds the specified element e to this set if
the set contains no element e2 such that
(e==null ? e2==null : e.equals(e2)).
If this set already contains the element, the call leaves the set
unchanged and returns false.
| e | element to be added to this set |
| return | true if this set did not already contain the specified
element |
| Throws | ClassCastException: if the specified object cannot be compared
with the elements currently in this set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
|
| public boolean |
addAll(Collection c)
Adds all of the elements in the specified collection to this set.
| c | collection containing elements to be added to this set |
| return | true if this set changed as a result of the call |
| Throws | ClassCastException: if the elements provided cannot be compared
with the elements currently in the set |
| Throws | NullPointerException: if the specified collection is null or
if any element is null and this set uses natural ordering, or
its comparator does not permit null elements |
|
| public Object |
ceiling(Object e)
| Throws | ClassCastException: if the specified element cannot be
compared with the elements currently in the set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
| since | 1.6 |
|
| public void |
clear()
Removes all of the elements from this set.
The set will be empty after this call returns.
|
| public Object |
clone()
Returns a shallow copy of this TreeSet instance. (The elements
themselves are not cloned.)
| return | a shallow copy of this set |
|
| public Comparator |
comparator()
|
| public boolean |
contains(Object o)
Returns true if this set contains the specified element.
More formally, returns true if and only if this set
contains an element e such that
(o==null ? e==null : o.equals(e)).
| o | object to be checked for containment in this set |
| return | true if this set contains the specified element |
| Throws | ClassCastException: if the specified object cannot be compared
with the elements currently in the set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
|
| public Iterator |
descendingIterator()
Returns an iterator over the elements in this set in descending order.
| return | an iterator over the elements in this set in descending order |
| since | 1.6 |
|
| public NavigableSet |
descendingSet()
|
| public Object |
first()
|
| public Object |
floor(Object e)
| Throws | ClassCastException: if the specified element cannot be
compared with the elements currently in the set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
| since | 1.6 |
|
| public NavigableSet |
headSet(Object toElement, boolean inclusive)
| Throws | ClassCastException: if toElement is not compatible
with this set's comparator (or, if the set has no comparator,
if toElement does not implement Comparable).
Implementations may, but are not required to, throw this
exception if toElement cannot be compared to elements
currently in the set. |
| Throws | NullPointerException: if toElement is null and
this set uses natural ordering, or its comparator does
not permit null elements |
| Throws | IllegalArgumentException: if this set itself has a
restricted range, and toElement lies outside the
bounds of the range |
| since | 1.6 |
|
| public SortedSet |
headSet(Object toElement)
| Throws | ClassCastException: if toElement is not compatible
with this set's comparator (or, if the set has no comparator,
if toElement does not implement Comparable).
Implementations may, but are not required to, throw this
exception if toElement cannot be compared to elements
currently in the set. |
| Throws | NullPointerException: if toElement is null
and this set uses natural ordering, or its comparator does
not permit null elements |
| Throws | IllegalArgumentException: if this set itself has a
restricted range, and toElement lies outside the
bounds of the range
na |
|
| public Object |
higher(Object e)
| Throws | ClassCastException: if the specified element cannot be
compared with the elements currently in the set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
| since | 1.6 |
|
| public Iterator |
iterator()
Returns an iterator over the elements in this set in ascending order.
| return | an iterator over the elements in this set in ascending order |
|
| public Object |
last()
|
| public Object |
lower(Object e)
| Throws | ClassCastException: if the specified element cannot be
compared with the elements currently in the set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
| since | 1.6 |
|
| public Object |
pollFirst()
|
| public Object |
pollLast()
|
| public boolean |
remove(Object o)
Removes the specified element from this set if it is present.
More formally, removes an element e such that
(o==null ? e==null : o.equals(e)),
if this set contains such an element. Returns true if
this set contained the element (or equivalently, if this set
changed as a result of the call). (This set will not contain the
element once the call returns.)
| o | object to be removed from this set, if present |
| return | true if this set contained the specified element |
| Throws | ClassCastException: if the specified object cannot be compared
with the elements currently in this set |
| Throws | NullPointerException: if the specified element is null
and this set uses natural ordering, or its comparator
does not permit null elements |
|
| public int |
size()
Returns the number of elements in this set (its cardinality).
| return | the number of elements in this set (its cardinality) |
|
| public NavigableSet |
subSet(Object fromElement, boolean fromInclusive, Object toElement, boolean toInclusive)
| Throws | ClassCastException: if fromElement and
toElement cannot be compared to one another using this
set's comparator (or, if the set has no comparator, using
natural ordering). Implementations may, but are not required
to, throw this exception if fromElement or
toElement cannot be compared to elements currently in
the set. |
| Throws | NullPointerException: if fromElement or toElement
is null and this set uses natural ordering, or its comparator
does not permit null elements |
| Throws | IllegalArgumentException: if fromElement is
greater than toElement; or if this set itself
has a restricted range, and fromElement or
toElement lies outside the bounds of the range. |
| since | 1.6 |
|
| public SortedSet |
subSet(Object fromElement, Object toElement)
| Throws | ClassCastException: if fromElement and
toElement cannot be compared to one another using this
set's comparator (or, if the set has no comparator, using
natural ordering). Implementations may, but are not required
to, throw this exception if fromElement or
toElement cannot be compared to elements currently in
the set. |
| Throws | NullPointerException: if fromElement or
toElement is null and this set uses natural ordering,
or its comparator does not permit null elements |
| Throws | IllegalArgumentException: if fromElement is
greater than toElement; or if this set itself
has a restricted range, and fromElement or
toElement lies outside the bounds of the range |
|
| public NavigableSet |
tailSet(Object fromElement, boolean inclusive)
| Throws | ClassCastException: if fromElement is not compatible
with this set's comparator (or, if the set has no comparator,
if fromElement does not implement Comparable).
Implementations may, but are not required to, throw this
exception if fromElement cannot be compared to elements
currently in the set. |
| Throws | NullPointerException: if fromElement is null and
this set uses natural ordering, or its comparator does
not permit null elements |
| Throws | IllegalArgumentException: if this set itself has a
restricted range, and fromElement lies outside the
bounds of the range |
| since | 1.6 |
|
| public SortedSet |
tailSet(Object fromElement)
| Throws | ClassCastException: if fromElement is not compatible
with this set's comparator (or, if the set has no comparator,
if fromElement does not implement Comparable).
Implementations may, but are not required to, throw this
exception if fromElement cannot be compared to elements
currently in the set. |
| Throws | NullPointerException: if fromElement is null
and this set uses natural ordering, or its comparator does
not permit null elements |
| Throws | IllegalArgumentException: if this set itself has a
restricted range, and fromElement lies outside the
bounds of the range |
|
