TreeSetpublic class TreeSet extends AbstractSet implements Cloneable, SortedSet, Serializable| This class implements the Set interface, backed by a
TreeMap 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 (or
compare) 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 the
Collections.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. |
| Fields Summary |
|---|
| private transient SortedMap | m | | private transient Set | keySet | | private static final Object | PRESENT | | private static final long | serialVersionUID |
| Constructors Summary |
|---|
private TreeSet(SortedMap m)Constructs a set backed by the specified sorted map.
this.m = m;
keySet = m.keySet();
| public TreeSet()Constructs a new, empty set, sorted according to the elements' natural
order. 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(Object) call will throw a ClassCastException.
this(new TreeMap<E,Object>());
| public TreeSet(Comparator 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 elements
e1 and e2 in the set. If the user attempts to add
an element to the set that violates this constraint, the
add(Object) call will throw a ClassCastException.
this(new TreeMap<E,Object>(c));
| public TreeSet(Collection 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 a
ClassCastException for any elements k1 and
k2 in the set.
this();
addAll(c);
| public TreeSet(SortedSet s)Constructs a new set containing the same elements as the specified
sorted set, sorted according to the same ordering.
this(s.comparator());
addAll(s);
|
| Methods Summary |
|---|
| public boolean | add(E o)Adds the specified element to this set if it is not already present.
return m.put(o, PRESENT)==null;
| | public boolean | addAll(java.util.Collection c)Adds all of the elements in the specified collection to this set.
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
// FIXME(VFORCE) Work-around for bug in compiler
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet<Map.Entry<E, Object>> set = (SortedSet<Map.Entry<E, Object>>) (SortedSet) c;
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<? super E> cc = (Comparator<E>) set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
| | public void | clear()Removes all of the elements from this set.
m.clear();
| | public java.lang.Object | clone()Returns a shallow copy of this TreeSet instance. (The elements
themselves are not cloned.)
TreeSet<E> clone = null;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
clone.m = new TreeMap<E,Object>(m);
clone.keySet = clone.m.keySet();
return clone;
| | public java.util.Comparator | comparator()Returns the comparator used to order this sorted set, or null
if this tree set uses its elements natural ordering.
return m.comparator();
| | public boolean | contains(java.lang.Object o)Returns true if this set contains the specified element.
return m.containsKey(o);
| | public E | first()Returns the first (lowest) element currently in this sorted set.
return m.firstKey();
| | public java.util.SortedSet | 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 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 of a
specified value, merely request a headSet bounded by
successor(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");
return new TreeSet<E>(m.headMap(toElement));
| | public boolean | isEmpty()Returns true if this set contains no elements.
return m.isEmpty();
| | public java.util.Iterator | iterator()Returns an iterator over the elements in this set. The elements
are returned in ascending order.
return keySet.iterator();
| | public E | last()Returns the last (highest) element currently in this sorted set.
return m.lastKey();
| | private void | readObject(java.io.ObjectInputStream s)Reconstitute the TreeSet instance from a stream (that is,
deserialize it).
// Read in any hidden stuff
s.defaultReadObject();
// Read in Comparator
Comparator<E> c = (Comparator<E>) s.readObject();
// Create backing TreeMap and keySet view
TreeMap<E,Object> tm;
if (c==null)
tm = new TreeMap<E,Object>();
else
tm = new TreeMap<E,Object>(c);
m = tm;
keySet = m.keySet();
// Read in size
int size = s.readInt();
tm.readTreeSet(size, s, PRESENT);
| | public boolean | remove(java.lang.Object o)Removes the specified element from this set if it is present.
return m.remove(o)==PRESENT;
| | public int | size()Returns the number of elements in this set (its cardinality).
return m.size();
| | public java.util.SortedSet | subSet(E fromElement, E toElement)Returns a view of the portion of this set whose elements range from
fromElement, inclusive, to toElement, exclusive. (If
fromElement 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 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 of a specified value,
merely request the subrange from lowEndpoint to
successor(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 to
high, 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 to
high, exclusive:
SortedSet sub = s.subSet(low+"\0", high);
return new TreeSet<E>(m.subMap(fromElement, toElement));
| | public java.util.SortedSet | 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 an
IllegalArgumentException 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 by
successor(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");
return new TreeSet<E>(m.tailMap(fromElement));
| | private void | writeObject(java.io.ObjectOutputStream s)Save the state of the TreeSet instance to a stream (that is,
serialize it).
// Write out any hidden stuff
s.defaultWriteObject();
// Write out Comparator
s.writeObject(m.comparator());
// Write out size
s.writeInt(m.size());
// Write out all elements in the proper order.
for (Iterator i=m.keySet().iterator(); i.hasNext(); )
s.writeObject(i.next());
|
|
