--- jsr166/src/jsr166x/ConcurrentSkipListSet.java 2004/09/07 11:37:57 1.3
+++ jsr166/src/jsr166x/ConcurrentSkipListSet.java 2013/01/16 00:53:17 1.18
@@ -1,10 +1,10 @@
/*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
+ * http://creativecommons.org/publicdomain/zero/1.0/
*/
-package jsr166x;
+package jsr166x;
import java.util.*;
import java.util.concurrent.*;
@@ -15,28 +15,33 @@ import java.util.concurrent.*;
* ascending order, sorted according to the natural order for
* the element's class (see {@link Comparable}), or by the comparator
* provided at creation time, depending on which constructor is
- * used.
+ * used.
*
- * This implementation provides expected average log(n) time
- * cost for the contains, add, and remove
+ *
This implementation provides expected average log(n) time
+ * cost for the {@code contains}, {@code add}, and {@code remove}
* operations and their variants. Insertion, removal, and access
* operations safely execute concurrently by multiple
* threads. Iterators are weakly consistent, returning elements
* reflecting the state of the set at some point at or since the
* creation of the iterator. They do not throw {@link
- * ConcurrentModificationException}, and may procede concurrently with
+ * ConcurrentModificationException}, and may proceed concurrently with
* other operations.
*
- *
Beware that, unlike in most collections, the size
- * method is NOT a constant-time operation. Because of the
+ *
Beware that, unlike in most collections, the {@code size}
+ * method is not a constant-time operation. Because of the
* asynchronous nature of these sets, determining the current number
- * of elements requires a traversal of the elements.
+ * of elements requires a traversal of the elements. Additionally, the
+ * bulk operations {@code addAll}, {@code removeAll},
+ * {@code retainAll}, and {@code containsAll} are not
+ * guaranteed to be performed atomically. For example, an iterator
+ * operating concurrently with an {@code addAll} operation might view
+ * only some of the added elements.
*
*
This class and its iterators implement all of the
* optional methods of the {@link Set} and {@link Iterator}
* interfaces. Like most other concurrent collection implementations,
- * this class does not permit the use of null elements.
- * because null arguments and return values cannot be reliably
+ * this class does not permit the use of {@code null} elements.
+ * because {@code null} arguments and return values cannot be reliably
* distinguished from the absence of elements.
*
* @author Doug Lea
@@ -55,11 +60,11 @@ public class ConcurrentSkipListSet
* fields of underlying map, but enables this field to be declared
* final, which is necessary for thread safety.
*/
- private final ConcurrentSkipListMap m;
+ private final ConcurrentSkipListMap m;
/**
* Constructs a new, empty set, sorted according to the elements' natural
- * order.
+ * order.
*/
public ConcurrentSkipListSet() {
m = new ConcurrentSkipListMap();
@@ -67,10 +72,10 @@ public class ConcurrentSkipListSet
/**
* Constructs a new, empty set, sorted according to the specified
- * comparator.
+ * comparator.
*
* @param c the comparator that will be used to sort this set. A
- * null value indicates that the elements' natural
+ * {@code null} value indicates that the elements' natural
* ordering should be used.
*/
public ConcurrentSkipListSet(Comparator super E> c) {
@@ -81,11 +86,12 @@ public class ConcurrentSkipListSet
* Constructs a new set containing the elements in the specified
* collection, sorted according to the elements' natural order.
*
- * @param c The elements that will comprise the new set.
+ * @param c The elements that will comprise the new set
*
* @throws ClassCastException if the elements in the specified
- * collection are not comparable, or are not mutually comparable.
- * @throws NullPointerException if the specified collection is null.
+ * collection are not comparable, or are not mutually comparable
+ * @throws NullPointerException if the specified collection is
+ * {@code null}
*/
public ConcurrentSkipListSet(Collection extends E> c) {
m = new ConcurrentSkipListMap();
@@ -96,8 +102,9 @@ public class ConcurrentSkipListSet
* 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.
+ * @param s sorted set whose elements will comprise the new set
+ * @throws NullPointerException if the specified sorted set is
+ * {@code null}
*/
public ConcurrentSkipListSet(SortedSet s) {
m = new ConcurrentSkipListMap(s.comparator());
@@ -108,15 +115,15 @@ public class ConcurrentSkipListSet
* Returns a shallow copy of this set. (The elements themselves
* are not cloned.)
*
- * @return a shallow copy of this set.
+ * @return a shallow copy of this set
*/
public Object clone() {
ConcurrentSkipListSet clone = null;
- try {
- clone = (ConcurrentSkipListSet) super.clone();
- } catch (CloneNotSupportedException e) {
- throw new InternalError();
- }
+ try {
+ clone = (ConcurrentSkipListSet) super.clone();
+ } catch (CloneNotSupportedException e) {
+ throw new InternalError();
+ }
clone.m.initialize();
clone.addAll(this);
@@ -127,8 +134,8 @@ public class ConcurrentSkipListSet
/**
* Returns the number of elements in this set. If this set
- * contains more than Integer.MAX_VALUE elements, it
- * returns Integer.MAX_VALUE.
+ * contains more than {@code Integer.MAX_VALUE} elements, it
+ * returns {@code Integer.MAX_VALUE}.
*
* Beware that, unlike in most collections, this method is
* NOT a constant-time operation. Because of the
@@ -139,137 +146,201 @@ public class ConcurrentSkipListSet
* will be inaccurate. Thus, this method is typically not very
* useful in concurrent applications.
*
- * @return the number of elements in this set.
+ * @return the number of elements in this set
*/
public int size() {
- return m.size();
+ return m.size();
}
/**
- * Returns true if this set contains no elements.
- * @return true if this set contains no elements.
+ * Returns {@code true} if this set contains no elements.
+ * @return {@code true} if this set contains no elements
*/
public boolean isEmpty() {
- return m.isEmpty();
+ return m.isEmpty();
}
/**
- * Returns true if this set contains the specified element.
+ * Returns {@code 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.
+ * @param o the object to be checked for containment in this set
+ * @return {@code 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.
+ * with the elements currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
public boolean contains(Object o) {
- return m.containsKey(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.
+ * @param o element to be added to this set
+ * @return {@code 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.
+ * with the elements currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
public boolean add(E o) {
- return m.putIfAbsent(o, Boolean.TRUE) == null;
+ return m.putIfAbsent(o, Boolean.TRUE) == 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.
+ * @param o object to be removed from this set, if present
+ * @return {@code 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.
+ * with the elements currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
public boolean remove(Object o) {
- return m.removep(o);
+ return m.removep(o);
}
/**
* Removes all of the elements from this set.
*/
public void clear() {
- m.clear();
+ m.clear();
}
/**
* 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.
+ * @return an iterator over the elements in this set
*/
public Iterator iterator() {
- return m.keyIterator();
+ return m.keyIterator();
+ }
+
+ /**
+ * 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.descendingKeyIterator();
+ }
+
+ /* ---------------- AbstractSet Overrides -------------- */
+
+ /**
+ * Compares the specified object with this set for equality. Returns
+ * {@code true} if the specified object is also a set, the two sets
+ * have the same size, and every member of the specified set is
+ * contained in this set (or equivalently, every member of this set is
+ * contained in the specified set). This definition ensures that the
+ * equals method works properly across different implementations of the
+ * set interface.
+ *
+ * @param o Object to be compared for equality with this set
+ * @return {@code true} if the specified Object is equal to this set
+ */
+ public boolean equals(Object o) {
+ // Override AbstractSet version to avoid calling size()
+ if (o == this)
+ return true;
+ if (!(o instanceof Set))
+ return false;
+ Collection c = (Collection) o;
+ try {
+ return containsAll(c) && c.containsAll(this);
+ } catch (ClassCastException unused) {
+ return false;
+ } catch (NullPointerException unused) {
+ return false;
+ }
+ }
+
+ /**
+ * Removes from this set all of its elements that are contained in
+ * the specified collection. If the specified collection is also
+ * a set, this operation effectively modifies this set so that its
+ * value is the asymmetric set difference of the two sets.
+ *
+ * @param c collection that defines which elements will be removed from
+ * this set
+ * @return {@code true} if this set changed as a result of the call
+ *
+ * @throws ClassCastException if the types of one or more elements in this
+ * set are incompatible with the specified collection
+ * @throws NullPointerException if the specified collection, or any
+ * of its elements are {@code null}
+ */
+ public boolean removeAll(Collection> c) {
+ // Override AbstractSet version to avoid unnecessary call to size()
+ boolean modified = false;
+ for (Iterator> i = c.iterator(); i.hasNext(); )
+ if (remove(i.next()))
+ modified = true;
+ return modified;
}
-
+
/* ---------------- Relational operations -------------- */
/**
* Returns an element greater than or equal to the given element, or
- * null if there is no such element.
- *
+ * {@code 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.
+ * @return an element greater than or equal to given element, or
+ * {@code 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
+ * currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
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.
- *
+ * Returns an element strictly less than the given element, or
+ * {@code 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.
+ * {@code 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.
+ * currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
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.
- *
+ * Returns an element less than or equal to the given element, or
+ * {@code 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.
+ * element, or {@code 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.
+ * currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
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.
- *
+ * Returns an element strictly greater than the given element, or
+ * {@code 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.
+ * {@code 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.
+ * currently in the set
+ * @throws NullPointerException if o is {@code null}
*/
public E higher(E o) {
return m.higherKey(o);
@@ -278,19 +349,19 @@ public class ConcurrentSkipListSet
/**
* Retrieves and removes the first (lowest) element.
*
- * @return the least element, or null if empty.
+ * @return the least element, or {@code null} if empty
*/
public E pollFirst() {
- return m.removeFirstKey();
+ return m.pollFirstKey();
}
/**
* Retrieves and removes the last (highest) element.
*
- * @return the last element, or null if empty.
+ * @return the last element, or {@code null} if empty
*/
public E pollLast() {
- return m.removeLastKey();
+ return m.pollLastKey();
}
@@ -298,11 +369,11 @@ public class ConcurrentSkipListSet
/**
- * Returns the comparator used to order this set, or null
+ * Returns the comparator used to order this set, or {@code null}
* if this set uses its elements natural ordering.
*
- * @return the comparator used to order this set, or null
- * if this set uses its elements natural ordering.
+ * @return the comparator used to order this set, or {@code null}
+ * if this set uses its elements natural ordering
*/
public Comparator super E> comparator() {
return m.comparator();
@@ -311,8 +382,8 @@ public class ConcurrentSkipListSet
/**
* Returns the first (lowest) element currently in this set.
*
- * @return the first (lowest) element currently in this set.
- * @throws NoSuchElementException sorted set is empty.
+ * @return the first (lowest) element currently in this set
+ * @throws NoSuchElementException sorted set is empty
*/
public E first() {
return m.firstKey();
@@ -321,72 +392,74 @@ public class ConcurrentSkipListSet
/**
* Returns the last (highest) element currently in this set.
*
- * @return the last (highest) element currently in this set.
- * @throws NoSuchElementException sorted set is empty.
+ * @return the last (highest) element currently in this set
+ * @throws NoSuchElementException sorted set is empty
*/
public E last() {
return m.lastKey();
}
+
+
/**
* 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
+ * {@code fromElement}, inclusive, to {@code toElement}, exclusive. (If
+ * {@code fromElement} and {@code 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.
- * @param fromElement low endpoint (inclusive) of the subSet.
- * @param toElement high endpoint (exclusive) of the subSet.
+ * vice-versa.
+ * @param fromElement low endpoint (inclusive) of the subSet
+ * @param toElement high endpoint (exclusive) of the subSet
* @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
+ * {@code fromElement}, inclusive, to {@code toElement},
+ * exclusive
+ * @throws ClassCastException if {@code fromElement} and
+ * {@code 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.
+ * using natural ordering)
+ * @throws IllegalArgumentException if {@code fromElement} is
+ * greater than {@code toElement}
+ * @throws NullPointerException if {@code fromElement} or
+ * {@code toElement} is {@code null}
*/
public NavigableSet subSet(E fromElement, E toElement) {
- return new ConcurrentSkipListSubSet(m, fromElement, toElement);
+ return new ConcurrentSkipListSubSet(m, fromElement, toElement);
}
/**
* Returns a view of the portion of this set whose elements are strictly
- * less than toElement. The returned sorted set is backed by
+ * less than {@code 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.
- * @param toElement high endpoint (exclusive) of the headSet.
+ * set, and vice-versa.
+ * @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
+ * less than toElement
+ * @throws ClassCastException if {@code toElement} is not compatible
* with this set's comparator (or, if the set has no comparator,
- * if toElement does not implement Comparable).
- * @throws NullPointerException if toElement is null.
+ * if {@code toElement} does not implement {@code Comparable})
+ * @throws NullPointerException if {@code toElement} is {@code null}
*/
public NavigableSet headSet(E toElement) {
- return new ConcurrentSkipListSubSet(m, null, toElement);
+ return new ConcurrentSkipListSubSet(m, null, toElement);
}
/**
* Returns a view of the portion of this set whose elements are
- * greater than or equal to fromElement. The returned
+ * greater than or equal to {@code 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.
- * @param fromElement low endpoint (inclusive) of the tailSet.
+ * @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
+ * greater than or equal to {@code fromElement}
+ * @throws ClassCastException if {@code fromElement} is not
* compatible with this set's comparator (or, if the set has no
- * comparator, if fromElement does not implement
- * Comparable).
- * @throws NullPointerException if fromElement is null.
+ * comparator, if {@code fromElement} does not implement
+ * {@code Comparable})
+ * @throws NullPointerException if {@code fromElement} is {@code null}
*/
public NavigableSet tailSet(E fromElement) {
- return new ConcurrentSkipListSubSet(m, fromElement, null);
+ return new ConcurrentSkipListSubSet(m, fromElement, null);
}
/**
@@ -396,344 +469,83 @@ public class ConcurrentSkipListSet
* underlying sets, differing in that elements outside their range are
* ignored, and attempts to add elements outside their ranges result
* in {@link IllegalArgumentException}. Instances of this class are
- * constructed only using the subSet, headSet, and
- * tailSet methods of their underlying sets.
- *
+ * constructed only using the {@code subSet}, {@code headSet}, and
+ * {@code tailSet} methods of their underlying sets.
*/
- static class ConcurrentSkipListSubSet
- extends AbstractSet
+ static class ConcurrentSkipListSubSet
+ extends AbstractSet
implements NavigableSet, java.io.Serializable {
private static final long serialVersionUID = -7647078645896651609L;
- /** The underlying submap */
+ /** The underlying submap */
private final ConcurrentSkipListMap.ConcurrentSkipListSubMap s;
-
+
/**
- * Creates a new submap.
- * @param fromElement inclusive least value, or null if from start
- * @param toElement exclusive upper bound or null if to end
+ * Creates a new submap.
+ * @param fromElement inclusive least value, or {@code null} if from start
+ * @param toElement exclusive upper bound or {@code null} if to end
* @throws IllegalArgumentException if fromElement and toElement
- * nonnull and fromElement greater than toElement
+ * non-null and fromElement greater than toElement
*/
- ConcurrentSkipListSubSet(ConcurrentSkipListMap map,
+ ConcurrentSkipListSubSet(ConcurrentSkipListMap map,
E fromElement, E toElement) {
- s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap(map, fromElement,
- toElement);
- }
-
- /**
- * Returns the number of elements in this set. If this set
- * contains more than Integer.MAX_VALUE elements, it
- * returns Integer.MAX_VALUE.
- *
- * Beware that, unlike in most collections, this method is
- * NOT a constant-time operation. Because of the
- * asynchronous nature of these sets, determining the current
- * number of elements requires traversing them all to count them.
- * Additionally, it is possible for the size to change during
- * execution of this method, in which case the returned result
- * will be inaccurate. Thus, this method is typically not very
- * useful in concurrent applications.
- *
- * @return the number of elements in this set.
- */
- public int size() {
- return s.size();
- }
-
- /**
- * Returns true if this set contains no elements.
- * @return true if this set contains no elements.
- */
- public boolean isEmpty() {
- return s.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.
- */
- public boolean contains(Object o) {
- return s.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 IllegalArgumentException if o is outside the range
- * of this subset.
- * @throws NullPointerException if o is null.
- */
- public boolean add(E o) {
- return s.put(o, Boolean.TRUE) == 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.
- */
- public boolean remove(Object o) {
- return s.remove(o) != null;
- }
-
- /**
- * Removes all of the elements from this set.
- */
- public void clear() {
- s.clear();
- }
-
- /**
- * 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 s.keySet().iterator();
- }
-
- /**
- * 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
- */
- public E ceiling(E o) {
- E key = o;
- E least = s.getLeast();
- if (least != null && s.getMap().compare(o, least) < 0)
- key = least;
- E k = s.getMap().ceilingKey(key);
- return (k != null && s.inHalfOpenRange(k))? k : null;
- }
-
- /**
- * 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.
- */
- public E lower(E o) {
- E k = s.getMap().lowerKey(o);
- return (k != null && s.inHalfOpenRange(k))? k : null;
- }
-
- /**
- * 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.
- */
- public E floor(E o) {
- E k = s.getMap().floorKey(o);
- return (k != null && s.inHalfOpenRange(k))? k : null;
- }
-
- /**
- * 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.
- */
- public E higher(E o) {
- E k;
- E least = s.getLeast();
- if (least != null && s.getMap().compare(o, least) < 0)
- k = s.getMap().ceilingKey(least);
- else
- k = s.getMap().higherKey(o);
- return (k != null && s.inHalfOpenRange(k))? k : null;
- }
-
- /**
- * Retrieves and removes the first (lowest) element.
- *
- * @return the first element, or null if empty.
- */
- public E pollFirst() {
- for (;;) {
- E k = s.lowestKey();
- if (k == null)
- return null;
- if (remove(k))
- return k;
- }
- }
-
- /**
- * Retrieves and removes the last (highest) element.
- *
- * @return the last element, or null if empty.
- */
- public E pollLast() {
- for (;;) {
- E k = s.highestKey();
- if (k == null)
- return null;
- if (remove(k))
- return k;
- }
+ s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap
+ (map, fromElement, toElement);
}
- /**
- * Returns the comparator used to order this set, or null
- * if this set uses its elements natural ordering.
- *
- * @return the comparator used to order this set, or null
- * if this set uses its elements natural ordering.
- */
- public Comparator super E> comparator() {
- return s.comparator();
- }
-
- /**
- * Returns the first (lowest) element currently in this set.
- *
- * @return the first (lowest) element currently in this set.
- * @throws NoSuchElementException sorted set is empty.
- */
- public E first() {
- return s.firstKey();
- }
+ // subsubset construction
- /**
- * Returns the last (highest) element currently in this set.
- *
- * @return the last (highest) element currently in this set.
- * @throws NoSuchElementException sorted set is empty.
- */
- public E last() {
- return s.lastKey();
- }
-
- /**
- * 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.
- * @param fromElement low endpoint (inclusive) of the subSet.
- * @param toElement high endpoint (exclusive) of the subSet.
- * @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 or either key is outside
- * the range of this set.
- * @throws NullPointerException if fromElement or
- * toElement is null.
- */
- public NavigableSet subSet(E fromElement,
- E toElement) {
+ public NavigableSet subSet(E fromElement, E toElement) {
if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
throw new IllegalArgumentException("element out of range");
- return new ConcurrentSkipListSubSet(s.getMap(),
+ return new ConcurrentSkipListSubSet(s.getMap(),
fromElement, 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.
- * @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 toElement is
- * outside the range of this set.
- * @throws NullPointerException if toElement is
- * null.
- */
public NavigableSet headSet(E toElement) {
E least = s.getLeast();
if (!s.inOpenRange(toElement))
throw new IllegalArgumentException("element out of range");
- return new ConcurrentSkipListSubSet(s.getMap(),
+ return new ConcurrentSkipListSubSet(s.getMap(),
least, toElement);
}
-
- /**
- * 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.
- * @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 fromElement is
- * outside the range of this set.
- * @throws NullPointerException if fromElement is
- * null.
- */
+
public NavigableSet tailSet(E fromElement) {
E fence = s.getFence();
if (!s.inOpenRange(fromElement))
throw new IllegalArgumentException("element out of range");
- return new ConcurrentSkipListSubSet(s.getMap(),
+ return new ConcurrentSkipListSubSet(s.getMap(),
fromElement, fence);
}
- }
+ // relays to submap methods
-}
+ public int size() { return s.size(); }
+ public boolean isEmpty() { return s.isEmpty(); }
+ public boolean contains(Object o) { return s.containsKey(o); }
+ public void clear() { s.clear(); }
+ public E first() { return s.firstKey(); }
+ public E last() { return s.lastKey(); }
+ public E ceiling(E o) { return s.ceilingKey(o); }
+ public E lower(E o) { return s.lowerKey(o); }
+ public E floor(E o) { return s.floorKey(o); }
+ public E higher(E o) { return s.higherKey(o); }
+ public boolean remove(Object o) { return s.remove(o)==Boolean.TRUE; }
+ public boolean add(E o) { return s.put(o, Boolean.TRUE)==null; }
+ public Comparator super E> comparator() { return s.comparator(); }
+ public Iterator iterator() { return s.keySet().iterator(); }
+ public Iterator descendingIterator() {
+ return s.descendingKeySet().iterator();
+ }
+ public E pollFirst() {
+ Map.Entry e = s.pollFirstEntry();
+ return (e == null) ? null : e.getKey();
+ }
+ public E pollLast() {
+ Map.Entry e = s.pollLastEntry();
+ return (e == null) ? null : e.getKey();
+ }
+
+ }
+}