All Packages Class Hierarchy This Package Previous Next Index
Class com.sun.java.util.collections.TreeSet
java.lang.Object
|
+----com.sun.java.util.collections.AbstractCollection
|
+----com.sun.java.util.collections.AbstractSet
|
+----com.sun.java.util.collections.TreeSet
- public class TreeSet
- extends AbstractSet
- implements SortedSet, Cloneable, Serializable
This class implements the TreeSet interface, backed by a TreeMap. This
class guarantees that the Set will be in ascending element order, sorted
according to the natural order of the elements (see Comparable), or
by the Comparator provided at TreeSet 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 TreeSet (whether or not an
explicit Comparator is provided) must be total if the TreeSet is
to correctly implement the Set interface. (See Comparable or Comparator
for a definition of total ordering.) This is so because the Set
interface is defined in terms of the equals operation, but a TreeSet
performs all key comparisons using its compareTo (or compare) method, so
two keys that are deemed equal by this method are, from the standpoint of
the TreeSet, equal. The behavior of a TreeSet is well-defined
even if its ordering is strictly partial; it just fails to obey the
general contract of the Set interface.
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.
- See Also:
- Collection, Set, HashSet, Comparable, Comparator, synchronizedSet, TreeMap
-
TreeSet()
- Constructs a new, empty TreeSet, sorted according to the elements'
natural order.
-
TreeSet(Collection)
- Constructs a new TreeSet containing the elements in the specified
Collection, sorted according to the elements' natural order.
-
TreeSet(Comparator)
- Constructs a new, empty TreeSet, sorted according to the given
comparator.
-
TreeSet(SortedSet)
- Constructs a new TreeSet containing the same elements as the given
SortedSet, sorted according to the same ordering.
-
add(Object)
- Adds the specified element to this Set if it is not already present.
-
addAll(Collection)
- Adds all of the elements in the specified Collection to this TreeSet.
-
clear()
- Removes all of the elements from this Set.
-
clone()
- Returns a shallow copy of this TreeSet.
-
comparator()
- Returns the comparator used to order this TreeMap, or null if this
TreeMap uses its keys natural ordering.
-
contains(Object)
- Returns true if this TreeSet contains the specified element.
-
first()
- Returns the first (lowest) element currently in this TreeSet.
-
headSet(Object)
- Returns a view of the portion of this TreeSet whose elements are
strictly less than toElement.
-
isEmpty()
- Returns true if this TreeSet contains no elements.
-
iterator()
- Returns an Iterator over the elements in this TreeSet.
-
last()
- Returns the last (highest) element currently in this TreeSet.
-
remove(Object)
- Removes the given element from this Set if it is present.
-
size()
- Returns the number of elements in this TreeSet (its cardinality).
-
subSet(Object, Object)
- Returns a view of the portion of this TreeSet whose elements range
from fromElement, inclusive, to toElement, exclusive.
-
tailSet(Object)
- Returns a view of the portion of this TreeSet whose elements are
strictly less than toElement.
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.
iterator
public Iterator iterator()
- Returns an Iterator over the elements in this TreeSet. The elements
are returned in ascending order.
- Returns:
- an Iterator over the elements in this TreeSet.
- Overrides:
- iterator in class AbstractCollection
size
public int size()
- Returns the number of elements in this TreeSet (its cardinality).
- 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.
- 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.
- Returns:
- true if this TreeSet contains the specified element.
- Throws: ClassCastException
- o cannot be compared with the elements
currently in the TreeSet.
- 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.
- Throws: ClassCastException
- o cannot be compared with the elements
currently in the TreeSet.
- 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.
- Throws: ClassCastException
- o cannot be compared with the elements
currently in the TreeSet.
- Overrides:
- remove in class AbstractCollection
clear
public void clear()
- Removes all of the elements from this Set.
- Overrides:
- clear in class AbstractCollection
addAll
public boolean addAll(Collection c)
- Adds all of the elements in the specified Collection to this TreeSet.
- Parameters:
- c - elements to be added
- Throws: ClassCastException
- elements of c cannot be compared with the
elements currently in the TreeSet.
- Overrides:
- addAll 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.
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 a given value, merely
request the subrange from lowEndpoint to successor(highEndpoint). For
example, suppose that s is a Set of Strings. The following
idiom obtains a view containing all of the Strings in s
from low to high, inclusive:
Set sub = s.subSet(low, high+"\0");
A similarly 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 to
high, exclusive:
Set sub = s.subSet(low+"\0", high);
- Parameters:
- fromElement - low endpoint (inclusive) of the subSet.
- toElement - high endpoint (exclusive) of the subSet.
- Returns:
- a view of the portion of this TreeSet whose elements range
from fromElement, inclusive, to toElement, exclusive.
- Throws: NullPointerException
- fromElement or toElement is null and
this TreeSet uses natural ordering, or its comparator
does not tolerate null elements.
- Throws: 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.
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 a given
value, merely request a headSet bounded by successor(highEndpoint).
For example, suppose that s is a Set of Strings. The following
idiom obtains a view containing all of the Strings in s
that are less than or equal to high:
Set head = s.headSet(high+"\0");
- Parameters:
- toElement - high endpoint (exclusive) of the headSet.
- Returns:
- a view of the portion of this TreeSet whose elements are
strictly less than toElement.
- Throws: 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.
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 a given value,
merely request a tailSet bounded by successor(lowEndpoint). For
example, suppose that s is a Set of Strings. The following
idiom obtains a view containing all of the Strings in s
that are strictly greater than low:
Set tail = s.tailSet(low+"\0");
- Parameters:
- fromElement - low endpoint (inclusive) of the tailSet.
- Returns:
- a view of the portion of this TreeSet whose elements are
strictly less than toElement.
- Throws: NullPointerException
- fromElement 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.
- Returns:
- the comparator used to order this TreeMap, or null if this
TreeMap uses its keys natural ordering.
first
public Object first()
- Returns the first (lowest) element currently in this TreeSet.
- 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.
- 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.)
- Returns:
- a shallow copy of this TreeSet.
- Overrides:
- clone in class Object
All Packages Class Hierarchy This Package Previous Next Index