--- jsr166/src/jsr166x/ConcurrentSkipListSet.java 2004/08/11 10:58:15 1.1
+++ jsr166/src/jsr166x/ConcurrentSkipListSet.java 2004/09/06 17:01:54 1.2
@@ -10,12 +10,12 @@ 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
@@ -27,25 +27,6 @@ import java.util.concurrent.*;
* ConcurrentModificationException}, and may procede 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
* asynchronous nature of these sets, determining the current number
@@ -63,7 +44,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;
@@ -232,65 +213,6 @@ public class ConcurrentSkipListSet
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.
- *
- * @return the least element, or null if empty.
- */
- public E poll() {
- return m.removeFirstKey();
- }
-
- /**
- * 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;
- }
-
- /**
- * 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();
- }
-
- /**
- * 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();
- }
-
/* ---------------- Relational operations -------------- */
/**
@@ -353,6 +275,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.removeFirstKey();
+ }
+
+ /**
+ * Retrieves and removes the last (highest) element.
+ *
+ * @return the last element, or null if empty.
+ */
+ public E pollLast() {
+ return m.removeLastKey();
+ }
+
+
/* ---------------- SortedSet operations -------------- */
@@ -408,7 +349,7 @@ public class ConcurrentSkipListSet
* @throws NullPointerException if fromElement or
* toElement is null.
*/
- public ConcurrentSkipListSubSet subSet(E fromElement, E toElement) {
+ public NavigableSet subSet(E fromElement, E toElement) {
return new ConcurrentSkipListSubSet(m, fromElement, toElement);
}
@@ -425,7 +366,7 @@ public class ConcurrentSkipListSet
* if toElement does not implement Comparable).
* @throws NullPointerException if toElement is null.
*/
- public ConcurrentSkipListSubSet headSet(E toElement) {
+ public NavigableSet headSet(E toElement) {
return new ConcurrentSkipListSubSet(m, null, toElement);
}
@@ -444,7 +385,355 @@ public class ConcurrentSkipListSet
* Comparable).
* @throws NullPointerException if fromElement is null.
*/
- public ConcurrentSkipListSubSet tailSet(E fromElement) {
+ 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
+ * nonnull and fromElement greater than toElement
+ */
+ 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;
+ }
+ }
+
+ /**
+ * 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 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();
+ }
+
+ /**
+ * 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) {
+ if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
+ throw new IllegalArgumentException("element out of range");
+ 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(),
+ 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(),
+ fromElement, fence);
+ }
+ }
+
+
}