--- jsr166/src/jsr166x/ConcurrentSkipListSet.java 2004/08/11 10:58:15 1.1
+++ jsr166/src/jsr166x/ConcurrentSkipListSet.java 2010/11/13 05:59:25 1.10
@@ -4,18 +4,18 @@
* http://creativecommons.org/licenses/publicdomain
*/
-package jsr166x;
+package jsr166x;
import java.util.*;
import java.util.concurrent.*;
/**
- * A scalable concurrent {@link SortedSet} and (priority) {@link
- * Queue} implementation based on a {@link ConcurrentSkipListMap}.
- * This class maintains a set in 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.
+ * A scalable concurrent {@link NavigableSet} implementation based on
+ * a {@link ConcurrentSkipListMap}. This class maintains a set in
+ * 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.
*
* This implementation provides expected average log(n) time
* cost for the contains, add, and remove
@@ -24,38 +24,24 @@ import java.util.concurrent.*;
* 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.
*
- *
This class provides extended SortedSet methods
- * searching for closest matches. Methods lower,
- * floor, ceiling, and higher return
- * elements respectively less, less than or equal, greater than or
- * equal, and greater than a given value, returning null if there is
- * no such element. These methods are designed for locating, not
- * traversing entries. To traverse, use iterators and/or
- * subset.
- *
- *
The class additionally supports {@link Queue} methods such as
- * poll that atomically returns and removes the first
- * element, if one exists. Thus, this class can serve as a priority
- * queue in which there are no duplicate elements.
- *
- *
The {@link ConcurrentSkipListSubSet} objects returned by methods
- * subset, headSet, and tailSet support the
- * same extended set of operations as this class, but operate on their
- * designated subrange of elements.
- *
*
Beware that, unlike in most collections, the size
- * method is NOT a constant-time operation. Because of the
+ * 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 addAll, removeAll,
+ * <retainAll, and tt>containsAll are not
+ * guaranteed to be performed atomically. For example, an iterator
+ * operating concurrently with an 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
+ * because null arguments and return values cannot be reliably
* distinguished from the absence of elements.
*
* @author Doug Lea
@@ -63,7 +49,7 @@ import java.util.concurrent.*;
*/
public class ConcurrentSkipListSet
extends AbstractSet
- implements SortedSet, Queue, Cloneable, java.io.Serializable {
+ implements NavigableSet, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2479143111061671589L;
@@ -74,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();
@@ -86,7 +72,7 @@ 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
@@ -104,7 +90,8 @@ public class ConcurrentSkipListSet
*
* @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.
+ * @throws NullPointerException if the specified collection is
+ * null.
*/
public ConcurrentSkipListSet(Collection extends E> c) {
m = new ConcurrentSkipListMap();
@@ -116,7 +103,8 @@ public class ConcurrentSkipListSet
* 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.
+ * @throws NullPointerException if the specified sorted set is
+ * null.
*/
public ConcurrentSkipListSet(SortedSet s) {
m = new ConcurrentSkipListMap(s.comparator());
@@ -131,11 +119,11 @@ public class ConcurrentSkipListSet
*/
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);
@@ -161,7 +149,7 @@ public class ConcurrentSkipListSet
* @return the number of elements in this set.
*/
public int size() {
- return m.size();
+ return m.size();
}
/**
@@ -169,7 +157,7 @@ public class ConcurrentSkipListSet
* @return true if this set contains no elements.
*/
public boolean isEmpty() {
- return m.isEmpty();
+ return m.isEmpty();
}
/**
@@ -179,11 +167,11 @@ public class ConcurrentSkipListSet
* @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.
+ * with the elements currently in the set.
* @throws NullPointerException if o is null.
*/
public boolean contains(Object o) {
- return m.containsKey(o);
+ return m.containsKey(o);
}
/**
@@ -194,11 +182,11 @@ public class ConcurrentSkipListSet
* element.
*
* @throws ClassCastException if the specified object cannot be compared
- * with the elements currently in the set.
+ * with the elements currently in the set.
* @throws NullPointerException if o is null.
*/
public boolean add(E o) {
- return m.putIfAbsent(o, Boolean.TRUE) == null;
+ return m.putIfAbsent(o, Boolean.TRUE) == null;
}
/**
@@ -208,18 +196,18 @@ public class ConcurrentSkipListSet
* @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.
+ * with the elements currently in the set.
* @throws NullPointerException if o is 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();
}
/**
@@ -229,77 +217,82 @@ public class ConcurrentSkipListSet
* @return an iterator over the elements in this set.
*/
public Iterator iterator() {
- return m.keyIterator();
+ return m.keyIterator();
}
-
- /* ---------------- Queue operations -------------- */
/**
- * Adds the specified element, or fails if this element is already
- * present.
- * @param o the element to insert.
- * @return true if it was possible to add the element,
- * else false
- */
- public boolean offer(E o) {
- return add(o);
- }
-
- /**
- * Retrieves and removes the first (lowest) element.
+ * Returns an iterator over the elements in this set. The elements
+ * are returned in descending order.
*
- * @return the least element, or null if empty.
+ * @return an iterator over the elements in this set.
*/
- public E poll() {
- return m.removeFirstKey();
+ public Iterator descendingIterator() {
+ return m.descendingKeyIterator();
}
- /**
- * Retrieves and removes the first (lowest) element. This method
- * differs from the poll method in that it throws an
- * exception if empty.
- *
- * @return the first (lowest) element.
- * @throws NoSuchElementException if empty.
- */
- public E remove() {
- E x = m.removeFirstKey();
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
+ /* ---------------- AbstractSet Overrides -------------- */
/**
- * Retrieves, but does not remove, the first (lowest) element,
- * returning null if empty.
- *
- * @return the first (lowest) element, or null if empty.
- */
- public E peek() {
- return m.lowestKey();
+ * Compares the specified object with this set for equality. Returns
+ * 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 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;
+ }
}
/**
- * Retrieves, but does not remove, the first (lowest) element.
- * This method differs from the peek method only in that
- * it throws an exception if empty.
- *
- * @return the first (lowest) element.
- * @throws NoSuchElementException if empty.
- */
- public E element() {
- return m.firstKey();
- }
+ * 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 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 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.
- *
+ * 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
+ * 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
@@ -309,12 +302,12 @@ public class ConcurrentSkipListSet
}
/**
- * 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
+ * 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.
+ * 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.
@@ -324,12 +317,12 @@ public class ConcurrentSkipListSet
}
/**
- * 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
+ * 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 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.
@@ -339,12 +332,12 @@ public class ConcurrentSkipListSet
}
/**
- * 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
+ * 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.
+ * 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.
@@ -353,6 +346,25 @@ public class ConcurrentSkipListSet
return m.higherKey(o);
}
+ /**
+ * Retrieves and removes the first (lowest) element.
+ *
+ * @return the least element, or null if empty.
+ */
+ public E pollFirst() {
+ return m.pollFirstKey();
+ }
+
+ /**
+ * Retrieves and removes the last (highest) element.
+ *
+ * @return the last element, or null if empty.
+ */
+ public E pollLast() {
+ return m.pollLastKey();
+ }
+
+
/* ---------------- SortedSet operations -------------- */
@@ -387,18 +399,20 @@ public class ConcurrentSkipListSet
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
* 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.
+ * 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.
+ * 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,
@@ -406,27 +420,27 @@ public class ConcurrentSkipListSet
* @throws IllegalArgumentException if fromElement is
* greater than toElement.
* @throws NullPointerException if fromElement or
- * toElement is null.
+ * toElement is null.
*/
- public ConcurrentSkipListSubSet subSet(E fromElement, E toElement) {
- return new ConcurrentSkipListSubSet(m, fromElement, toElement);
+ public NavigableSet subSet(E fromElement, E 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
* this set, so changes in the returned sorted set are reflected in this
- * set, and vice-versa.
+ * 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.
+ * 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 NullPointerException if toElement is null.
*/
- public ConcurrentSkipListSubSet headSet(E toElement) {
- return new ConcurrentSkipListSubSet(m, null, toElement);
+ public NavigableSet headSet(E toElement) {
+ return new ConcurrentSkipListSubSet(m, null, toElement);
}
@@ -444,7 +458,95 @@ public class ConcurrentSkipListSet
* Comparable).
* @throws NullPointerException if fromElement is null.
*/
- public ConcurrentSkipListSubSet tailSet(E fromElement) {
- return new ConcurrentSkipListSubSet(m, fromElement, null);
+ public NavigableSet tailSet(E fromElement) {
+ return new ConcurrentSkipListSubSet(m, fromElement, null);
+ }
+
+ /**
+ * Subsets returned by {@link ConcurrentSkipListSet} subset operations
+ * represent a subrange of elements of their underlying
+ * sets. Instances of this class support all methods of their
+ * 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.
+ *
+ */
+ static class ConcurrentSkipListSubSet
+ extends AbstractSet
+ implements NavigableSet, java.io.Serializable {
+
+ private static final long serialVersionUID = -7647078645896651609L;
+
+ /** 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
+ * @throws IllegalArgumentException if fromElement and toElement
+ * non-null and fromElement greater than toElement
+ */
+ ConcurrentSkipListSubSet(ConcurrentSkipListMap map,
+ E fromElement, E toElement) {
+ s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap
+ (map, fromElement, toElement);
+ }
+
+ // subsubset construction
+
+ 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(),
+ fromElement, toElement);
+ }
+
+ 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(),
+ least, toElement);
+ }
+
+ 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(),
+ 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();
+ }
+
}
-}
+}