/*
* %W% %E%
*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/
package java.util;
/**
* 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.
*
* @author Josh Bloch
* @version %I%, %G%
* @see Collection
* @see Set
* @see HashSet
* @see Comparable
* @see Comparator
* @see Collections#synchronizedSortedSet(SortedSet)
* @see TreeMap
* @since 1.2
*/
public class TreeSet
extends AbstractSet
implements NavigableSet, Cloneable, java.io.Serializable
{
private transient NavigableMap m; // The backing Map
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a set backed by the specified sorted map.
*/
private TreeSet(NavigableMap m) {
this.m = m;
}
/**
* 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.
*
* @see Comparable
*/
public TreeSet() {
this(new TreeMap());
}
/**
* 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.
*
* @param c the comparator that will be used to sort this set. A
* null value indicates that the elements' natural
* ordering should be used.
*/
public TreeSet(Comparator c) {
this(new TreeMap(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.
*
* @param c The elements that will comprise the new set.
*
* @throws ClassCastException if the keys in the specified collection are
* not comparable, or are not mutually comparable.
* @throws NullPointerException if the specified collection is null.
*/
public TreeSet(Collection c) {
this();
addAll(c);
}
/**
* Constructs a new set containing the same elements as the specified
* sorted set, sorted according to the same ordering.
*
* @param s sorted set whose elements will comprise the new set.
* @throws NullPointerException if the specified sorted set is null.
*/
public TreeSet(SortedSet s) {
this(s.comparator());
addAll(s);
}
/**
* Returns an iterator over the elements in this set. The elements
* are returned in ascending order.
*
* @return an iterator over the elements in this set.
*/
public Iterator iterator() {
return m.keySet().iterator();
}
/**
* Returns an iterator over the elements in this set. The elements
* are returned in descending order.
*
* @return an iterator over the elements in this set.
*/
public Iterator descendingIterator() {
return m.descendingKeySet().iterator();
}
/**
* Returns the number of elements in this set (its cardinality).
*
* @return the number of elements in this set (its cardinality).
*/
public int size() {
return m.size();
}
/**
* Returns true if this set contains no elements.
*
* @return true if this set contains no elements.
*/
public boolean isEmpty() {
return m.isEmpty();
}
/**
* Returns true if this set contains the specified element.
*
* @param o the 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 o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public boolean contains(Object o) {
return m.containsKey(o);
}
/**
* Adds the specified element to this set if it is not already present.
*
* @param o element to be added to this set.
* @return true if the set did not already contain the specified
* element.
*
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in the set.
* @throws NullPointerException if o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public boolean add(E o) {
return m.put(o, PRESENT)==null;
}
/**
* Removes the specified element from this set if it is present.
*
* @param o object to be removed from this set, if present.
* @return true if the set contained the specified element.
*
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in the set.
* @throws NullPointerException if o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
/**
* Removes all of the elements from this set.
*/
public void clear() {
m.clear();
}
/**
* Adds all of the elements in the specified collection to this set.
*
* @param c elements to be added
* @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 map
* uses natural ordering, or its comparator does not tolerate
* null keys.
*/
public boolean addAll(Collection c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet> set = (SortedSet>) (SortedSet) c;
TreeMap map = (TreeMap) m;
Comparator cc = (Comparator) set.comparator();
Comparator mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
/**
* 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 navigable set is empty.) The returned
* navigable set is backed by this set, so changes in the returned
* navigable set are reflected in this set, and vice-versa. The
* returned navigable set supports all optional Set operations.
*
* The navigable 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 navigable set of
* strings. The following idiom obtains a view containing all of
* the strings in s from low to high,
* inclusive:
*
NavigableSet sub = s.navigableSubSet(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:
* NavigableSet sub = s.navigableSubSet(low+"\0", high);
*
*
* @param fromElement low endpoint (inclusive) of the range.
* @param toElement high endpoint (exclusive) of the range.
* @return a view of the portion of this set whose elements range from
* fromElement, inclusive, to toElement,
* exclusive.
* @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).
* @throws IllegalArgumentException if fromElement is greater than
* toElement.
* @throws NullPointerException if fromElement or
* toElement is null and this set uses natural
* order, or its comparator does not tolerate null
* elements.
*/
public NavigableSet navigableSubSet(E fromElement, E toElement) {
return new TreeSet(m.navigableSubMap(fromElement, toElement));
}
/**
* Returns a view of the portion of this set whose elements are
* strictly less than toElement. The returned navigable
* set is backed by this set, so changes in the returned navigable
* set are reflected in this set, and vice-versa. The returned
* navigable set supports all optional set operations.
*
* The navigable 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 navigable set of strings. The
* following idiom obtains a view containing all of the strings in
* s that are less than or equal to high:
*
NavigableSet head = s.navigableHeadSet(high+"\0");
*
* @param toElement high endpoint (exclusive) of the headSet.
* @return a view of the portion of this set whose elements are strictly
* less than 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).
* @throws IllegalArgumentException if this set is itself a subset,
* and toElement is not within the
* specified range of the subset.
* @throws NullPointerException if toElement is null and
* this set uses natural ordering, or its comparator does
* not tolerate null elements.
*/
public NavigableSet navigableHeadSet(E toElement) {
return new TreeSet(m.navigableHeadMap(toElement));
}
/**
* Returns a view of the portion of this set whose elements are
* greater than or equal to fromElement. The returned
* navigable set is backed by this set, so changes in the returned
* navigable set are reflected in this set, and vice-versa. The
* returned navigable set supports all optional set operations.
*
* The navigable 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 navigable set of strings. The
* following idiom obtains a view containing all of the strings in
* s that are strictly greater than low:
*
NavigableSet tail = s.navigableTailSet(low+"\0");
*
*
* @param fromElement low endpoint (inclusive) of the tailSet.
* @return a view of the portion of this set whose elements are
* greater than or equal to 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).
* @throws IllegalArgumentException if this set is itself a subset,
* and fromElement is not within the
* specified range of the subset.
* @throws NullPointerException if fromElement is null
* and this set uses natural ordering, or its comparator does
* not tolerate null elements.
*/
public NavigableSet navigableTailSet(E fromElement) {
return new TreeSet(m.navigableTailMap(fromElement));
}
/**
* Equivalent to navigableSubSet but with a return
* type conforming to the SortedSet interface.
* @param fromElement low endpoint (inclusive) of the range.
* @param toElement high endpoint (exclusive) of the range.
* @return a view of the portion of this set whose elements range from
* fromElement, inclusive, to toElement,
* exclusive.
* @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).
* @throws IllegalArgumentException if fromElement is greater than
* toElement.
* @throws NullPointerException if fromElement or
* toElement is null and this set uses natural
* order, or its comparator does not tolerate null
* elements.
*/
public SortedSet subSet(E fromElement, E toElement) {
return new TreeSet(m.navigableSubMap(fromElement, toElement));
}
/**
* Equivalent to navigableHeadSet but with a return
* type conforming to the SortedSet interface.
*
* @param toElement high endpoint (exclusive) of the headSet.
* @return a view of the portion of this set whose elements are strictly
* less than 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).
* @throws IllegalArgumentException if this set is itself a subset,
* and toElement is not within the
* specified range of the subset.
* @throws NullPointerException if toElement is null and
* this set uses natural ordering, or its comparator does
* not tolerate null elements.
*/
public SortedSet headSet(E toElement) {
return new TreeSet(m.navigableHeadMap(toElement));
}
/**
* Equivalent to navigableTailSet but with a return
* type conforming to the SortedSet interface.
* @param fromElement low endpoint (inclusive) of the tailSet.
* @return a view of the portion of this set whose elements are
* greater than or equal to 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).
* @throws IllegalArgumentException if this set is itself a subset,
* and fromElement is not within the
* specified range of the subset.
* @throws NullPointerException if fromElement is null
* and this set uses natural ordering, or its comparator does
* not tolerate null elements.
*/
public SortedSet tailSet(E fromElement) {
return new TreeSet(m.navigableTailMap(fromElement));
}
/**
* Returns the comparator used to order this sorted set, or null
* if this tree set uses its elements natural ordering.
*
* @return the comparator used to order this sorted set, or null
* if this tree set uses its elements natural ordering.
*/
public Comparator comparator() {
return m.comparator();
}
/**
* Returns the first (lowest) element currently in this sorted set.
*
* @return the first (lowest) element currently in this sorted set.
* @throws NoSuchElementException sorted set is empty.
*/
public E first() {
return m.firstKey();
}
/**
* Returns the last (highest) element currently in this sorted set.
*
* @return the last (highest) element currently in this sorted set.
* @throws NoSuchElementException sorted set is empty.
*/
public E last() {
return m.lastKey();
}
// NavigableSet API methods
/**
* Returns an element greater than or equal to the given element, or
* null if there is no such element.
*
* @param o the value to match
* @return an element greater than or equal to given element, or
* null if there is no such element.
* @throws ClassCastException if o cannot be compared with the elements
* currently in the set.
* @throws NullPointerException if o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public E ceiling(E o) {
return m.ceilingKey(o);
}
/**
* Returns an element strictly less than the given element, or
* null if there is no such element.
*
* @param o the value to match
* @return the greatest element less than the given element, or
* null if there is no such element.
* @throws ClassCastException if o cannot be compared with the elements
* currently in the set.
* @throws NullPointerException if o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public E lower(E o) {
return m.lowerKey(o);
}
/**
* Returns an element less than or equal to the given element, or
* null if there is no such element.
*
* @param o the value to match
* @return the greatest element less than or equal to given
* element, or null if there is no such element.
* @throws ClassCastException if o cannot be compared with the elements
* currently in the set.
* @throws NullPointerException if o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public E floor(E o) {
return m.floorKey(o);
}
/**
* Returns an element strictly greater than the given element, or
* null if there is no such element.
*
* @param o the value to match
* @return the least element greater than the given element, or
* null if there is no such element.
* @throws ClassCastException if o cannot be compared with the elements
* currently in the set.
* @throws NullPointerException if o is null and this map
* uses natural ordering and is non-empty, or its comparator does
* not tolerate null keys.
*/
public E higher(E o) {
return m.higherKey(o);
}
/**
* Retrieves and removes the first (lowest) element.
*
* @return the least element, or null if empty.
*/
public E pollFirst() {
Map.Entry e = m.pollFirstEntry();
return (e == null)? null : e.getKey();
}
/**
* Retrieves and removes the last (highest) element.
*
* @return the last element, or null if empty.
*/
public E pollLast() {
Map.Entry e = m.pollLastEntry();
return (e == null)? null : e.getKey();
}
/**
* Returns a shallow copy of this TreeSet instance. (The elements
* themselves are not cloned.)
*
* @return a shallow copy of this set.
*/
public Object clone() {
TreeSet clone = null;
try {
clone = (TreeSet) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
clone.m = new TreeMap(m);
return clone;
}
/**
* Save the state of the TreeSet instance to a stream (that is,
* serialize it).
*
* @serialData Emits the comparator used to order this set, or
* null if it obeys its elements' natural ordering
* (Object), followed by the size of the set (the number of
* elements it contains) (int), followed by all of its
* elements (each an Object) in order (as determined by the
* set's Comparator, or by the elements' natural ordering if
* the set has no Comparator).
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// 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());
}
/**
* Reconstitute the TreeSet instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// Read in Comparator
Comparator c = (Comparator) s.readObject();
// Create backing TreeMap
TreeMap tm;
if (c==null)
tm = new TreeMap();
else
tm = new TreeMap(c);
m = tm;
// Read in size
int size = s.readInt();
tm.readTreeSet(size, s, PRESENT);
}
private static final long serialVersionUID = -2479143000061671589L;
}