util/concurrent/ConcurrentSkipListSet.java

/*
 * 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
 */

package java.util.concurrent;
import java.util.*;

/**
 * A scalable concurrent {@link NavigableSet} implementation based on
 * a {@link ConcurrentSkipListMap}.  The elements of the set are kept
 * sorted according to their {@linkplain Comparable natural ordering},
 * or by a {@link Comparator} provided at set creation time, depending
 * on which constructor is used.
 *
 * <p>This implementation provides expected average <i>log(n)</i> time
 * cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
 * operations and their variants.  Insertion, removal, and access
 * operations safely execute concurrently by multiple threads.
 * Iterators are <i>weakly consistent</i>, returning elements
 * reflecting the state of the set at some point at or since the
 * creation of the iterator.  They do <em>not</em> throw {@link
 * ConcurrentModificationException}, and may proceed concurrently with
 * other operations.  Ascending ordered views and their iterators are
 * faster than descending ones.
 *
 * <p>Beware that, unlike in most collections, the <tt>size</tt>
 * method is <em>not</em> a constant-time operation. Because of the
 * asynchronous nature of these sets, determining the current number
 * of elements requires a traversal of the elements. Additionally, the
 * bulk operations <tt>addAll</tt>, <tt>removeAll</tt>,
 * <tt>retainAll</tt>, and <tt>containsAll</tt> are <em>not</em>
 * guaranteed to be performed atomically. For example, an iterator
 * operating concurrently with an <tt>addAll</tt> operation might view
 * only some of the added elements.
 *
 * <p>This class and its iterators implement all of the
 * <em>optional</em> methods of the {@link Set} and {@link Iterator}
 * interfaces. Like most other concurrent collection implementations,
 * this class does not permit the use of <tt>null</tt> elements,
 * because <tt>null</tt> arguments and return values cannot be reliably
 * distinguished from the absence of elements.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author Doug Lea
 * @param <E> the type of elements maintained by this set
 * @since 1.6
 */
public class ConcurrentSkipListSet<E>
    extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2479143111061671589L;

    /**
     * The underlying map. Uses Boolean.TRUE as value for each
     * element.  Note that this class relies on default serialization,
     * which is a little wasteful in saving all of the useless value
     * fields of the underlying map, but enables this field to be
     * declared final, which is necessary for thread safety.
     */
    private final ConcurrentSkipListMap<E,Object> m;

    /**
     * Constructs a new, empty set that orders its elements according to
     * their {@linkplain Comparable natural ordering}.
     */
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E,Object>();
    }

    /**
     * Constructs a new, empty set that orders its elements according to
     * the specified comparator.
     *
     * @param comparator the comparator that will be used to order this set.
     *        If <tt>null</tt>, the {@linkplain Comparable natural
     *        ordering} of the elements will be used.
     */
    public ConcurrentSkipListSet(Comparator<? super E> comparator) {
        m = new ConcurrentSkipListMap<E,Object>(comparator);
    }

    /**
     * Constructs a new set containing the elements in the specified
     * collection, that orders its elements according to their
     * {@linkplain Comparable natural ordering}.
     *
     * @param c The elements that will comprise the new set
     * @throws ClassCastException if the elements in <tt>c</tt> are
     *         not {@link Comparable}, or are not mutually comparable
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     */
    public ConcurrentSkipListSet(Collection<? extends E> c) {
        m = new ConcurrentSkipListMap<E,Object>();
        addAll(c);
    }

    /**
     * Constructs a new set containing the same elements and using the
     * same ordering as the specified sorted set.
     *
     * @param s sorted set whose elements will comprise the new set
     * @throws NullPointerException if the specified sorted set or any
     *         of its elements are null
     */
    public ConcurrentSkipListSet(SortedSet<E> s) {
        m = new ConcurrentSkipListMap<E,Object>(s.comparator());
        addAll(s);
    }

    /**
     * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
     * instance. (The elements themselves are not cloned.)
     *
     * @return a shallow copy of this set
     */
    public ConcurrentSkipListSet<E> clone() {
        ConcurrentSkipListSet<E> clone = null;
        try {
            clone = (ConcurrentSkipListSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }

        clone.m.initialize();
        clone.addAll(this);
        return clone;
    }

    /* ---------------- Set operations -------------- */

    /**
     * Returns the number of elements in this set.  If this set
     * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
     * returns <tt>Integer.MAX_VALUE</tt>.
     *
     * <p>Beware that, unlike in most collections, this method is
     * <em>NOT</em> 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 m.size();
    }

    /**
     * Returns <tt>true</tt> if this set contains no elements.
     * @return <tt>true</tt> if this set contains no elements
     */
    public boolean isEmpty() {
        return m.isEmpty();
    }

    /**
     * Returns <tt>true</tt> if this set contains the specified element.
     *
     * @param o the object to be checked for containment in this set
     * @return <tt>true</tt> if this set contains the specified element
     * @throws ClassCastException if the specified element cannot be
     *         compared with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     */
    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    /**
     * Adds the specified element to this set if it is not already present.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if the set did not already contain the
     *         specified element
     * @throws ClassCastException if <tt>e</tt> cannot be compared
     *         with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        return m.putIfAbsent(e, 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 <tt>true</tt> if the set contained the specified element
     * @throws ClassCastException if <tt>o</tt> cannot be compared
     *         with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     */
    public boolean remove(Object o) {
        return m.removep(o);
    }

    /**
     * Removes all of the elements from this set.
     */
    public void clear() {
        m.clear();
    }

    /**
     * Returns an iterator over the elements in this set in ascending order.
     *
     * @return an iterator over the elements in this set in ascending order
     */
    public Iterator<E> iterator() {
        return m.keyIterator();
    }

    /**
     * Returns an iterator over the elements in this set in descending order.
     *
     * @return an iterator over the elements in this set in descending order
     */
    public Iterator<E> descendingIterator() {
        return m.descendingKeyIterator();
    }

    /* ---------------- AbstractSet Overrides -------------- */

    /**
     * Compares the specified object with this set for equality.  Returns
     * <tt>true</tt> 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 the object to be compared for equality with this set
     * @return <tt>true</tt> 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 <i>asymmetric set difference</i> of the two sets.
     *
     * @param  c collection containing elements to be removed from this set
     * @return <tt>true</tt> 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 -------------- */

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     */
    public E lower(E e) {
        return m.lowerKey(e);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     */
    public E floor(E e) {
        return m.floorKey(e);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     */
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified element is null
     */
    public E higher(E e) {
        return m.higherKey(e);
    }

    public E pollFirst() {
        return m.pollFirstKey();
    }

    public E pollLast() {
        return m.pollLastKey();
    }


    /* ---------------- SortedSet operations -------------- */


    public Comparator<? super E> comparator() {
        return m.comparator();
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E first() {
        return m.firstKey();
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E last() {
        return m.lastKey();
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if <tt>fromElement</tt> or
     *         <tt>toElement</tt> is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
        return new ConcurrentSkipListSubSet<E>(m, fromElement, toElement);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if <tt>toElement</tt> is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public NavigableSet<E> navigableHeadSet(E toElement) {
        return new ConcurrentSkipListSubSet<E>(m, null, toElement);
    }

    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if <tt>fromElement</tt> is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public NavigableSet<E> navigableTailSet(E fromElement) {
        return new ConcurrentSkipListSubSet<E>(m, fromElement, null);
    }

    /**
     * Equivalent to {@link #navigableSubSet} but with a return type
     * conforming to the <tt>SortedSet</tt> interface.
     *
     * <p>{@inheritDoc}
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException if <tt>fromElement</tt> or
     *         <tt>toElement</tt> is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return navigableSubSet(fromElement, toElement);
    }

    /**
     * Equivalent to {@link #navigableHeadSet} but with a return type
     * conforming to the <tt>SortedSet</tt> interface.
     *
     * <p>{@inheritDoc}
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException if <tt>toElement</tt> is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public SortedSet<E> headSet(E toElement) {
        return navigableHeadSet(toElement);
    }


    /**
     * Equivalent to {@link #navigableTailSet} but with a return type
     * conforming to the <tt>SortedSet</tt> interface.
     *
     * <p>{@inheritDoc}
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException if <tt>fromElement</tt> is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public SortedSet<E> tailSet(E fromElement) {
        return navigableTailSet(fromElement);
    }

    /**
     * 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 <tt>subSet</tt>, <tt>headSet</tt>, and
     * <tt>tailSet</tt> methods of their underlying sets.
     */
    static class ConcurrentSkipListSubSet<E>
        extends AbstractSet<E>
        implements NavigableSet<E>, java.io.Serializable {

        private static final long serialVersionUID = -7647078645896651609L;

        /** The underlying submap  */
        private final ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object> s;

        /**
         * Creates a new submap.
         * @param fromElement inclusive least value, or <tt>null</tt> if from start
         * @param toElement exclusive upper bound or <tt>null</tt> if to end
         * @throws IllegalArgumentException if fromElement and toElement
         * nonnull and fromElement greater than toElement
         */
        ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
                                 E fromElement, E toElement) {
            s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>
                (map, fromElement, toElement);
        }

        // subsubset construction

        public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
            if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
                throw new IllegalArgumentException("element out of range");
            return new ConcurrentSkipListSubSet<E>(s.getMap(),
                                                   fromElement, toElement);
        }

        public NavigableSet<E> navigableHeadSet(E toElement) {
            E least = s.getLeast();
            if (!s.inOpenRange(toElement))
                throw new IllegalArgumentException("element out of range");
            return new ConcurrentSkipListSubSet<E>(s.getMap(),
                                                   least, toElement);
        }

        public NavigableSet<E> navigableTailSet(E fromElement) {
            E fence = s.getFence();
            if (!s.inOpenRange(fromElement))
                throw new IllegalArgumentException("element out of range");
            return new ConcurrentSkipListSubSet<E>(s.getMap(),
                                                   fromElement, fence);
        }

        public SortedSet<E> subSet(E fromElement, E toElement) {
            return navigableSubSet(fromElement, toElement);
        }

        public SortedSet<E> headSet(E toElement) {
            return navigableHeadSet(toElement);
        }

        public SortedSet<E> tailSet(E fromElement) {
            return navigableTailSet(fromElement);
        }

        // 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 e)             { return s.ceilingKey(e); }
        public E lower(E e)               { return s.lowerKey(e); }
        public E floor(E e)               { return s.floorKey(e); }
        public E higher(E e)              { return s.higherKey(e); }
        public boolean remove(Object o) { return s.remove(o)==Boolean.TRUE; }
        public boolean add(E e)       { return s.put(e, Boolean.TRUE)==null; }
        public Comparator<? super E> comparator() { return s.comparator(); }
        public Iterator<E> iterator()     { return s.keySet().iterator(); }
        public Iterator<E> descendingIterator() {
            return s.descendingKeySet().iterator();
        }
        public E pollFirst() {
            Map.Entry<E,?> e = s.pollFirstEntry();
            return (e == null)? null : e.getKey();
        }
        public E pollLast() {
            Map.Entry<E,?> e = s.pollLastEntry();
            return (e == null)? null : e.getKey();
        }

    }
}
Revision:	1.13
Committed:	Thu May 26 12:07:14 2005 UTC (19 years ago) by dl
Branch:	MAIN
Changes since 1.12:	+1 -1 lines
Log Message:	Avoid some generics cast warnings
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5			*/
6
7			package java.util.concurrent;
8			import java.util.*;
9
10			/**
11			* A scalable concurrent {@link NavigableSet} implementation based on
12	jsr166	1.11	* a {@link ConcurrentSkipListMap}. The elements of the set are kept
13			* sorted according to their {@linkplain Comparable natural ordering},
14			* or by a {@link Comparator} provided at set creation time, depending
15			* on which constructor is used.
16	dl	1.1	*
17	jsr166	1.11	* <p>This implementation provides expected average <i>log(n)</i> time
18	dl	1.1	* cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
19			* operations and their variants. Insertion, removal, and access
20	jsr166	1.11	* operations safely execute concurrently by multiple threads.
21			* Iterators are <i>weakly consistent</i>, returning elements
22	dl	1.1	* reflecting the state of the set at some point at or since the
23			* creation of the iterator. They do <em>not</em> throw {@link
24	dl	1.2	* ConcurrentModificationException}, and may proceed concurrently with
25	jsr166	1.11	* other operations. Ascending ordered views and their iterators are
26			* faster than descending ones.
27	dl	1.1	*
28			* <p>Beware that, unlike in most collections, the <tt>size</tt>
29			* method is <em>not</em> a constant-time operation. Because of the
30			* asynchronous nature of these sets, determining the current number
31			* of elements requires a traversal of the elements. Additionally, the
32			* bulk operations <tt>addAll</tt>, <tt>removeAll</tt>,
33	dl	1.3	* <tt>retainAll</tt>, and <tt>containsAll</tt> are <em>not</em>
34	dl	1.1	* guaranteed to be performed atomically. For example, an iterator
35			* operating concurrently with an <tt>addAll</tt> operation might view
36			* only some of the added elements.
37			*
38			* <p>This class and its iterators implement all of the
39			* <em>optional</em> methods of the {@link Set} and {@link Iterator}
40			* interfaces. Like most other concurrent collection implementations,
41	jsr166	1.11	* this class does not permit the use of <tt>null</tt> elements,
42	dl	1.1	* because <tt>null</tt> arguments and return values cannot be reliably
43			* distinguished from the absence of elements.
44			*
45	jsr166	1.10	* <p>This class is a member of the
46			* <a href="{@docRoot}/../guide/collections/index.html">
47			* Java Collections Framework</a>.
48			*
49	dl	1.1	* @author Doug Lea
50			* @param <E> the type of elements maintained by this set
51	jsr166	1.9	* @since 1.6
52	dl	1.1	*/
53			public class ConcurrentSkipListSet<E>
54			extends AbstractSet<E>
55			implements NavigableSet<E>, Cloneable, java.io.Serializable {
56
57			private static final long serialVersionUID = -2479143111061671589L;
58
59			/**
60			* The underlying map. Uses Boolean.TRUE as value for each
61			* element. Note that this class relies on default serialization,
62			* which is a little wasteful in saving all of the useless value
63	jsr166	1.11	* fields of the underlying map, but enables this field to be
64			* declared final, which is necessary for thread safety.
65	dl	1.1	*/
66	jsr166	1.8	private final ConcurrentSkipListMap<E,Object> m;
67	dl	1.1
68			/**
69	jsr166	1.11	* Constructs a new, empty set that orders its elements according to
70			* their {@linkplain Comparable natural ordering}.
71	dl	1.1	*/
72			public ConcurrentSkipListSet() {
73			m = new ConcurrentSkipListMap<E,Object>();
74			}
75
76			/**
77	jsr166	1.11	* Constructs a new, empty set that orders its elements according to
78			* the specified comparator.
79	dl	1.1	*
80	jsr166	1.11	* @param comparator the comparator that will be used to order this set.
81			* If <tt>null</tt>, the {@linkplain Comparable natural
82			* ordering} of the elements will be used.
83	dl	1.1	*/
84	jsr166	1.11	public ConcurrentSkipListSet(Comparator<? super E> comparator) {
85			m = new ConcurrentSkipListMap<E,Object>(comparator);
86	dl	1.1	}
87
88			/**
89			* Constructs a new set containing the elements in the specified
90	jsr166	1.11	* collection, that orders its elements according to their
91			* {@linkplain Comparable natural ordering}.
92	dl	1.1	*
93	jsr166	1.11	* @param c The elements that will comprise the new set
94			* @throws ClassCastException if the elements in <tt>c</tt> are
95			* not {@link Comparable}, or are not mutually comparable
96			* @throws NullPointerException if the specified collection or any
97			* of its elements are null
98	dl	1.1	*/
99			public ConcurrentSkipListSet(Collection<? extends E> c) {
100			m = new ConcurrentSkipListMap<E,Object>();
101			addAll(c);
102			}
103
104			/**
105	jsr166	1.11	* Constructs a new set containing the same elements and using the
106			* same ordering as the specified sorted set.
107	dl	1.1	*
108	jsr166	1.11	* @param s sorted set whose elements will comprise the new set
109			* @throws NullPointerException if the specified sorted set or any
110			* of its elements are null
111	dl	1.1	*/
112			public ConcurrentSkipListSet(SortedSet<E> s) {
113			m = new ConcurrentSkipListMap<E,Object>(s.comparator());
114			addAll(s);
115			}
116
117			/**
118	jsr166	1.11	* Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
119			* instance. (The elements themselves are not cloned.)
120	dl	1.1	*
121	jsr166	1.11	* @return a shallow copy of this set
122	dl	1.1	*/
123	jsr166	1.7	public ConcurrentSkipListSet<E> clone() {
124	dl	1.1	ConcurrentSkipListSet<E> clone = null;
125			try {
126			clone = (ConcurrentSkipListSet<E>) super.clone();
127			} catch (CloneNotSupportedException e) {
128			throw new InternalError();
129			}
130
131			clone.m.initialize();
132			clone.addAll(this);
133			return clone;
134			}
135
136			/* ---------------- Set operations -------------- */
137
138			/**
139			* Returns the number of elements in this set. If this set
140			* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
141			* returns <tt>Integer.MAX_VALUE</tt>.
142			*
143			* <p>Beware that, unlike in most collections, this method is
144			* <em>NOT</em> a constant-time operation. Because of the
145			* asynchronous nature of these sets, determining the current
146			* number of elements requires traversing them all to count them.
147			* Additionally, it is possible for the size to change during
148			* execution of this method, in which case the returned result
149			* will be inaccurate. Thus, this method is typically not very
150			* useful in concurrent applications.
151			*
152	jsr166	1.12	* @return the number of elements in this set
153	dl	1.1	*/
154			public int size() {
155			return m.size();
156			}
157
158			/**
159			* Returns <tt>true</tt> if this set contains no elements.
160	jsr166	1.11	* @return <tt>true</tt> if this set contains no elements
161	dl	1.1	*/
162			public boolean isEmpty() {
163			return m.isEmpty();
164			}
165
166			/**
167			* Returns <tt>true</tt> if this set contains the specified element.
168			*
169	jsr166	1.11	* @param o the object to be checked for containment in this set
170			* @return <tt>true</tt> if this set contains the specified element
171			* @throws ClassCastException if the specified element cannot be
172			* compared with the elements currently in the set
173			* @throws NullPointerException if the specified element is null
174	dl	1.1	*/
175			public boolean contains(Object o) {
176			return m.containsKey(o);
177			}
178
179			/**
180			* Adds the specified element to this set if it is not already present.
181			*
182	jsr166	1.11	* @param e element to be added to this set
183			* @return <tt>true</tt> if the set did not already contain the
184			* specified element
185			* @throws ClassCastException if <tt>e</tt> cannot be compared
186			* with the elements currently in the set
187			* @throws NullPointerException if the specified element is null
188	dl	1.1	*/
189	jsr166	1.5	public boolean add(E e) {
190			return m.putIfAbsent(e, Boolean.TRUE) == null;
191	dl	1.1	}
192
193			/**
194			* Removes the specified element from this set if it is present.
195			*
196	jsr166	1.11	* @param o object to be removed from this set, if present
197			* @return <tt>true</tt> if the set contained the specified element
198			* @throws ClassCastException if <tt>o</tt> cannot be compared
199			* with the elements currently in the set
200			* @throws NullPointerException if the specified element is null
201	dl	1.1	*/
202			public boolean remove(Object o) {
203			return m.removep(o);
204			}
205
206			/**
207			* Removes all of the elements from this set.
208			*/
209			public void clear() {
210			m.clear();
211			}
212
213			/**
214	jsr166	1.11	* Returns an iterator over the elements in this set in ascending order.
215	dl	1.1	*
216	jsr166	1.11	* @return an iterator over the elements in this set in ascending order
217	dl	1.1	*/
218			public Iterator<E> iterator() {
219			return m.keyIterator();
220			}
221
222			/**
223	jsr166	1.11	* Returns an iterator over the elements in this set in descending order.
224	dl	1.1	*
225	jsr166	1.11	* @return an iterator over the elements in this set in descending order
226	dl	1.1	*/
227			public Iterator<E> descendingIterator() {
228			return m.descendingKeyIterator();
229			}
230
231			/* ---------------- AbstractSet Overrides -------------- */
232
233			/**
234			* Compares the specified object with this set for equality. Returns
235			* <tt>true</tt> if the specified object is also a set, the two sets
236			* have the same size, and every member of the specified set is
237			* contained in this set (or equivalently, every member of this set is
238			* contained in the specified set). This definition ensures that the
239			* equals method works properly across different implementations of the
240			* set interface.
241			*
242	jsr166	1.11	* @param o the object to be compared for equality with this set
243			* @return <tt>true</tt> if the specified object is equal to this set
244	dl	1.1	*/
245			public boolean equals(Object o) {
246			// Override AbstractSet version to avoid calling size()
247			if (o == this)
248			return true;
249			if (!(o instanceof Set))
250			return false;
251	dl	1.13	Collection<?> c = (Collection<?>) o;
252	dl	1.1	try {
253			return containsAll(c) && c.containsAll(this);
254	jsr166	1.6	} catch (ClassCastException unused) {
255	dl	1.1	return false;
256	jsr166	1.6	} catch (NullPointerException unused) {
257	dl	1.1	return false;
258			}
259			}
260	jsr166	1.8
261	dl	1.1	/**
262			* Removes from this set all of its elements that are contained in
263			* the specified collection. If the specified collection is also
264			* a set, this operation effectively modifies this set so that its
265			* value is the <i>asymmetric set difference</i> of the two sets.
266			*
267	jsr166	1.11	* @param c collection containing elements to be removed from this set
268			* @return <tt>true</tt> if this set changed as a result of the call
269	dl	1.1	* @throws ClassCastException if the types of one or more elements in this
270	jsr166	1.11	* set are incompatible with the specified collection
271			* @throws NullPointerException if the specified collection or any
272			* of its elements are null
273	dl	1.1	*/
274			public boolean removeAll(Collection<?> c) {
275			// Override AbstractSet version to avoid unnecessary call to size()
276			boolean modified = false;
277			for (Iterator<?> i = c.iterator(); i.hasNext(); )
278			if (remove(i.next()))
279			modified = true;
280			return modified;
281			}
282	jsr166	1.8
283	dl	1.1	/* ---------------- Relational operations -------------- */
284
285			/**
286	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
287			* @throws NullPointerException if the specified element is null
288	dl	1.1	*/
289	jsr166	1.11	public E lower(E e) {
290			return m.lowerKey(e);
291	dl	1.1	}
292
293			/**
294	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
295			* @throws NullPointerException if the specified element is null
296	dl	1.1	*/
297	jsr166	1.11	public E floor(E e) {
298			return m.floorKey(e);
299	dl	1.1	}
300
301			/**
302	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
303			* @throws NullPointerException if the specified element is null
304	dl	1.1	*/
305	jsr166	1.11	public E ceiling(E e) {
306			return m.ceilingKey(e);
307	dl	1.1	}
308
309			/**
310	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
311			* @throws NullPointerException if the specified element is null
312	dl	1.1	*/
313	jsr166	1.5	public E higher(E e) {
314			return m.higherKey(e);
315	dl	1.1	}
316
317			public E pollFirst() {
318			return m.pollFirstKey();
319			}
320
321			public E pollLast() {
322			return m.pollLastKey();
323			}
324
325
326			/* ---------------- SortedSet operations -------------- */
327
328
329			public Comparator<? super E> comparator() {
330			return m.comparator();
331			}
332
333			/**
334	jsr166	1.11	* @throws NoSuchElementException {@inheritDoc}
335	dl	1.1	*/
336			public E first() {
337			return m.firstKey();
338			}
339
340			/**
341	jsr166	1.11	* @throws NoSuchElementException {@inheritDoc}
342	dl	1.1	*/
343			public E last() {
344			return m.lastKey();
345			}
346
347			/**
348	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
349	dl	1.1	* @throws NullPointerException if <tt>fromElement</tt> or
350	jsr166	1.11	* <tt>toElement</tt> is null
351			* @throws IllegalArgumentException {@inheritDoc}
352	dl	1.1	*/
353	dl	1.3	public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
354	dl	1.1	return new ConcurrentSkipListSubSet<E>(m, fromElement, toElement);
355			}
356
357			/**
358	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
359			* @throws NullPointerException if <tt>toElement</tt> is null
360			* @throws IllegalArgumentException {@inheritDoc}
361	dl	1.1	*/
362	dl	1.3	public NavigableSet<E> navigableHeadSet(E toElement) {
363	dl	1.1	return new ConcurrentSkipListSubSet<E>(m, null, toElement);
364			}
365
366			/**
367	jsr166	1.11	* @throws ClassCastException {@inheritDoc}
368			* @throws NullPointerException if <tt>fromElement</tt> is null
369			* @throws IllegalArgumentException {@inheritDoc}
370	dl	1.1	*/
371	dl	1.3	public NavigableSet<E> navigableTailSet(E fromElement) {
372			return new ConcurrentSkipListSubSet<E>(m, fromElement, null);
373			}
374
375			/**
376	jsr166	1.11	* Equivalent to {@link #navigableSubSet} but with a return type
377			* conforming to the <tt>SortedSet</tt> interface.
378			*
379			* <p>{@inheritDoc}
380			*
381			* @throws ClassCastException {@inheritDoc}
382	dl	1.3	* @throws NullPointerException if <tt>fromElement</tt> or
383	jsr166	1.11	* <tt>toElement</tt> is null
384			* @throws IllegalArgumentException {@inheritDoc}
385	dl	1.3	*/
386			public SortedSet<E> subSet(E fromElement, E toElement) {
387	dl	1.4	return navigableSubSet(fromElement, toElement);
388	dl	1.3	}
389
390			/**
391	jsr166	1.11	* Equivalent to {@link #navigableHeadSet} but with a return type
392			* conforming to the <tt>SortedSet</tt> interface.
393			*
394			* <p>{@inheritDoc}
395			*
396			* @throws ClassCastException {@inheritDoc}
397			* @throws NullPointerException if <tt>toElement</tt> is null
398			* @throws IllegalArgumentException {@inheritDoc}
399	dl	1.3	*/
400			public SortedSet<E> headSet(E toElement) {
401	dl	1.4	return navigableHeadSet(toElement);
402	dl	1.3	}
403
404
405			/**
406	jsr166	1.11	* Equivalent to {@link #navigableTailSet} but with a return type
407			* conforming to the <tt>SortedSet</tt> interface.
408			*
409			* <p>{@inheritDoc}
410			*
411			* @throws ClassCastException {@inheritDoc}
412			* @throws NullPointerException if <tt>fromElement</tt> is null
413			* @throws IllegalArgumentException {@inheritDoc}
414	dl	1.3	*/
415			public SortedSet<E> tailSet(E fromElement) {
416	dl	1.4	return navigableTailSet(fromElement);
417	dl	1.1	}
418
419			/**
420			* Subsets returned by {@link ConcurrentSkipListSet} subset operations
421			* represent a subrange of elements of their underlying
422			* sets. Instances of this class support all methods of their
423			* underlying sets, differing in that elements outside their range are
424			* ignored, and attempts to add elements outside their ranges result
425			* in {@link IllegalArgumentException}. Instances of this class are
426			* constructed only using the <tt>subSet</tt>, <tt>headSet</tt>, and
427			* <tt>tailSet</tt> methods of their underlying sets.
428			*/
429	jsr166	1.8	static class ConcurrentSkipListSubSet<E>
430			extends AbstractSet<E>
431	dl	1.1	implements NavigableSet<E>, java.io.Serializable {
432
433			private static final long serialVersionUID = -7647078645896651609L;
434
435			/** The underlying submap */
436			private final ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object> s;
437	jsr166	1.8
438	dl	1.1	/**
439	jsr166	1.8	* Creates a new submap.
440	dl	1.1	* @param fromElement inclusive least value, or <tt>null</tt> if from start
441			* @param toElement exclusive upper bound or <tt>null</tt> if to end
442			* @throws IllegalArgumentException if fromElement and toElement
443			* nonnull and fromElement greater than toElement
444			*/
445	jsr166	1.8	ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
446	dl	1.1	E fromElement, E toElement) {
447			s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>
448			(map, fromElement, toElement);
449			}
450
451			// subsubset construction
452
453	dl	1.3	public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
454	dl	1.1	if (!s.inOpenRange(fromElement) \|\| !s.inOpenRange(toElement))
455			throw new IllegalArgumentException("element out of range");
456	jsr166	1.8	return new ConcurrentSkipListSubSet<E>(s.getMap(),
457	dl	1.1	fromElement, toElement);
458			}
459
460	dl	1.3	public NavigableSet<E> navigableHeadSet(E toElement) {
461	dl	1.1	E least = s.getLeast();
462			if (!s.inOpenRange(toElement))
463			throw new IllegalArgumentException("element out of range");
464	jsr166	1.8	return new ConcurrentSkipListSubSet<E>(s.getMap(),
465	dl	1.1	least, toElement);
466			}
467	jsr166	1.8
468	dl	1.3	public NavigableSet<E> navigableTailSet(E fromElement) {
469	dl	1.1	E fence = s.getFence();
470			if (!s.inOpenRange(fromElement))
471			throw new IllegalArgumentException("element out of range");
472	jsr166	1.8	return new ConcurrentSkipListSubSet<E>(s.getMap(),
473	dl	1.1	fromElement, fence);
474			}
475
476	dl	1.3	public SortedSet<E> subSet(E fromElement, E toElement) {
477	jsr166	1.11	return navigableSubSet(fromElement, toElement);
478	dl	1.3	}
479
480			public SortedSet<E> headSet(E toElement) {
481			return navigableHeadSet(toElement);
482			}
483	jsr166	1.8
484	dl	1.3	public SortedSet<E> tailSet(E fromElement) {
485			return navigableTailSet(fromElement);
486			}
487
488	dl	1.1	// relays to submap methods
489
490			public int size() { return s.size(); }
491			public boolean isEmpty() { return s.isEmpty(); }
492			public boolean contains(Object o) { return s.containsKey(o); }
493			public void clear() { s.clear(); }
494			public E first() { return s.firstKey(); }
495			public E last() { return s.lastKey(); }
496	jsr166	1.5	public E ceiling(E e) { return s.ceilingKey(e); }
497			public E lower(E e) { return s.lowerKey(e); }
498			public E floor(E e) { return s.floorKey(e); }
499			public E higher(E e) { return s.higherKey(e); }
500	dl	1.1	public boolean remove(Object o) { return s.remove(o)==Boolean.TRUE; }
501	jsr166	1.5	public boolean add(E e) { return s.put(e, Boolean.TRUE)==null; }
502	dl	1.1	public Comparator<? super E> comparator() { return s.comparator(); }
503			public Iterator<E> iterator() { return s.keySet().iterator(); }
504			public Iterator<E> descendingIterator() {
505			return s.descendingKeySet().iterator();
506			}
507	jsr166	1.8	public E pollFirst() {
508	dl	1.1	Map.Entry<E,?> e = s.pollFirstEntry();
509			return (e == null)? null : e.getKey();
510			}
511			public E pollLast() {
512			Map.Entry<E,?> e = s.pollLastEntry();
513			return (e == null)? null : e.getKey();
514			}
515
516			}
517	jsr166	1.8	}