ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166x/ConcurrentSkipListSet.java

Comparing jsr166/src/jsr166x/ConcurrentSkipListSet.java (file contents):
Revision 1.1 by dl, Wed Aug 11 10:58:15 2004 UTC vs.
Revision 1.4 by dl, Sat Oct 16 14:49:45 2004 UTC

#	Line 10 | Line 10 | import java.util.*;
10		import java.util.concurrent.*;
11
12		/**
13	<	* A scalable concurrent {@link SortedSet} and (priority) {@link
14	<	* Queue} implementation based on a {@link ConcurrentSkipListMap}.
15	<	* This class maintains a set in ascending order, sorted according to
16	<	* the <i>natural order</i> for the element's class (see {@link
17	<	* Comparable}), or by the comparator provided at creation time,
18	<	* depending on which constructor is used.<p>
13	>	* A scalable concurrent {@link NavigableSet} implementation based on
14	>	* a {@link ConcurrentSkipListMap}.  This class maintains a set in
15	>	* ascending order, sorted according to the <i>natural order</i> for
16	>	* the element's class (see {@link Comparable}), or by the comparator
17	>	* provided at creation time, depending on which constructor is
18	>	* used.<p>
19		*
20		* This implementation provides expected average <i>log(n)</i> time
21		* cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
#	Line 27 | Line 27 | import java.util.concurrent.*;
27		* ConcurrentModificationException}, and may procede concurrently with
28		* other operations.
29		*
30	–	* <p>This class provides extended <tt>SortedSet</tt> methods
31	–	* searching for closest matches. Methods <tt>lower</tt>,
32	–	* <tt>floor</tt>, <tt>ceiling</tt>, and <tt>higher</tt> return
33	–	* elements respectively less, less than or equal, greater than or
34	–	* equal, and greater than a given value, returning null if there is
35	–	* no such element.  These methods are designed for locating, not
36	–	* traversing entries. To traverse, use iterators and/or
37	–	* <tt>subset</tt>.
38	–	*
39	–	* <p>The class additionally supports {@link Queue} methods such as
40	–	* <tt>poll</tt> that atomically returns and removes the first
41	–	* element, if one exists. Thus, this class can serve as a priority
42	–	* queue in which there are no duplicate elements.
43	–	*
44	–	* <p>The {@link ConcurrentSkipListSubSet} objects returned by methods
45	–	* <tt>subset</tt>, <tt>headSet</tt>, and <tt>tailSet</tt> support the
46	–	* same extended set of operations as this class, but operate on their
47	–	* designated subrange of elements.
48	–	*
30		* <p>Beware that, unlike in most collections, the <tt>size</tt>
31	<	* method is <em>NOT</em> a constant-time operation. Because of the
31	>	* method is <em>not</em> a constant-time operation. Because of the
32		* asynchronous nature of these sets, determining the current number
33	<	* of elements requires a traversal of the elements.
33	>	* of elements requires a traversal of the elements. Additionally, the
34	>	* bulk operations <tt>addAll</tt>, <tt>removeAll</tt>,
35	>	* <<tt>retainAll</tt>, and tt>containsAll</tt> are <em>not</em>
36	>	* guaranteed to be performed atomically. For example, an iterator
37	>	* operating concurrently with an <tt>addAll</tt> operation might view
38	>	* only some of the added elements.
39		*
40		* <p>This class and its iterators implement all of the
41		* <em>optional</em> methods of the {@link Set} and {@link Iterator}
42		* interfaces. Like most other concurrent collection implementations,
43		* this class does not permit the use of <tt>null</tt> elements.
44	<	* because null arguments and return values cannot be reliably
44	>	* because <tt>null</tt> arguments and return values cannot be reliably
45		* distinguished from the absence of elements.
46		*
47		* @author Doug Lea
#	Line 63 | Line 49 | import java.util.concurrent.*;
49		*/
50		public class ConcurrentSkipListSet<E>
51		extends AbstractSet<E>
52	<	implements SortedSet<E>, Queue<E>, Cloneable, java.io.Serializable {
52	>	implements NavigableSet<E>, Cloneable, java.io.Serializable {
53
54		private static final long serialVersionUID = -2479143111061671589L;
55
#	Line 104 | Line 90 | public class ConcurrentSkipListSet<E>
90		*
91		* @throws ClassCastException if the elements in the specified
92		* collection are not comparable, or are not mutually comparable.
93	<	* @throws NullPointerException if the specified collection is null.
93	>	* @throws NullPointerException if the specified collection is
94	>	* <tt>null</tt>.
95		*/
96		public ConcurrentSkipListSet(Collection<? extends E> c) {
97		m = new ConcurrentSkipListMap<E,Object>();
#	Line 116 | Line 103 | public class ConcurrentSkipListSet<E>
103		* sorted set, sorted according to the same ordering.
104		*
105		* @param s sorted set whose elements will comprise the new set.
106	<	* @throws NullPointerException if the specified sorted set is null.
106	>	* @throws NullPointerException if the specified sorted set is
107	>	* <tt>null</tt>.
108		*/
109		public ConcurrentSkipListSet(SortedSet<E> s) {
110		m = new ConcurrentSkipListMap<E,Object>(s.comparator());
#	Line 231 | Line 219 | public class ConcurrentSkipListSet<E>
219		public Iterator<E> iterator() {
220		return m.keyIterator();
221		}
234	–
235	–	/* ---------------- Queue operations -------------- */
236	–
237	–	/**
238	–	* Adds the specified element, or fails if this element is already
239	–	* present.
240	–	* @param o the element to insert.
241	–	* @return <tt>true</tt> if it was possible to add the element,
242	–	* else <tt>false</tt>
243	–	*/
244	–	public boolean offer(E o) {
245	–	return add(o);
246	–	}
222
223	<	/**
249	<	* Retrieves and removes the first (lowest) element.
250	<	*
251	<	* @return the least element, or <tt>null</tt> if empty.
252	<	*/
253	<	public E poll() {
254	<	return m.removeFirstKey();
255	<	}
223	>	/* ---------------- AbstractSet Overrides -------------- */
224
225		/**
226	<	* Retrieves and removes the first (lowest) element.  This method
227	<	* differs from the <tt>poll</tt> method in that it throws an
228	<	* exception if empty.
229	<	*
230	<	* @return the first (lowest) element.
231	<	* @throws NoSuchElementException if empty.
232	<	*/
233	<	public E remove() {
234	<	E x = m.removeFirstKey();
235	<	if (x == null)
236	<	throw new NoSuchElementException();
237	<	return x;
226	>	* Compares the specified object with this set for equality.  Returns
227	>	* <tt>true</tt> if the specified object is also a set, the two sets
228	>	* have the same size, and every member of the specified set is
229	>	* contained in this set (or equivalently, every member of this set is
230	>	* contained in the specified set).  This definition ensures that the
231	>	* equals method works properly across different implementations of the
232	>	* set interface.
233	>	*
234	>	* @param o Object to be compared for equality with this set.
235	>	* @return <tt>true</tt> if the specified Object is equal to this set.
236	>	*/
237	>	public boolean equals(Object o) {
238	>	// Override AbstractSet version to avoid calling size()
239	>	if (o == this)
240	>	return true;
241	>	if (!(o instanceof Set))
242	>	return false;
243	>	Collection c = (Collection) o;
244	>	try {
245	>	return containsAll(c) && c.containsAll(this);
246	>	} catch(ClassCastException unused)   {
247	>	return false;
248	>	} catch(NullPointerException unused) {
249	>	return false;
250	>	}
251		}
252	<
252	>
253		/**
254	<	* Retrieves, but does not remove, the first (lowest) element,
255	<	* returning <tt>null</tt> if empty.
256	<	*
257	<	* @return the first (lowest) element, or <tt>null</tt> if empty.
258	<	*/
259	<	public E peek() {
260	<	return m.lowestKey();
254	>	* Removes from this set all of its elements that are contained in
255	>	* the specified collection.  If the specified collection is also
256	>	* a set, this operation effectively modifies this set so that its
257	>	* value is the <i>asymmetric set difference</i> of the two sets.
258	>	*
259	>	* @param  c collection that defines which elements will be removed from
260	>	*           this set.
261	>	* @return <tt>true</tt> if this set changed as a result of the call.
262	>	*
263	>	* @throws ClassCastException if the types of one or more elements in this
264	>	*            set are incompatible with the specified collection
265	>	* @throws NullPointerException if the specified collection, or any
266	>	* of its elements are <tt>null</tt>.
267	>	*/
268	>	public boolean removeAll(Collection<?> c) {
269	>	// Override AbstractSet version to avoid unnecessary call to size()
270	>	boolean modified = false;
271	>	for (Iterator<?> i = c.iterator(); i.hasNext(); )
272	>	if (remove(i.next()))
273	>	modified = true;
274	>	return modified;
275		}
276	<
282	<	/**
283	<	* Retrieves, but does not remove, the first (lowest) element.
284	<	* This method differs from the <tt>peek</tt> method only in that
285	<	* it throws an exception if empty.
286	<	*
287	<	* @return the first (lowest) element.
288	<	* @throws NoSuchElementException if empty.
289	<	*/
290	<	public E element() {
291	<	return m.firstKey();
292	<	}
293	<
276	>
277		/* ---------------- Relational operations -------------- */
278
279		/**
280		* Returns an element greater than or equal to the given element, or
281	<	* null if there is no such element.
281	>	* <tt>null</tt> if there is no such element.
282		*
283		* @param o the value to match
284	<	* @return an element greater than or equal to given element, or null
285	<	* if there is no such element.
284	>	* @return an element greater than or equal to given element, or
285	>	* <tt>null</tt> if there is no such element.
286		* @throws ClassCastException if o cannot be compared with the elements
287		*            currently in the set.
288		* @throws NullPointerException if o is <tt>null</tt>
#	Line 309 | Line 292 | public class ConcurrentSkipListSet<E>
292		}
293
294		/**
295	<	* Returns an element strictly less than the given element, or null if
296	<	* there is no such element.
295	>	* Returns an element strictly less than the given element, or
296	>	* <tt>null</tt> if there is no such element.
297		*
298		* @param o the value to match
299		* @return the greatest element less than the given element, or
300	<	* null if there is no such element.
300	>	* <tt>null</tt> if there is no such element.
301		* @throws ClassCastException if o cannot be compared with the elements
302		*            currently in the set.
303		* @throws NullPointerException if o is <tt>null</tt>.
#	Line 324 | Line 307 | public class ConcurrentSkipListSet<E>
307		}
308
309		/**
310	<	* Returns an element less than or equal to the given element, or null
311	<	* if there is no such element.
310	>	* Returns an element less than or equal to the given element, or
311	>	* <tt>null</tt> if there is no such element.
312		*
313		* @param o the value to match
314		* @return the greatest element less than or equal to given
315	<	* element, or null if there is no such element.
315	>	* element, or <tt>null</tt> if there is no such element.
316		* @throws ClassCastException if o cannot be compared with the elements
317		*            currently in the set.
318		* @throws NullPointerException if o is <tt>null</tt>.
#	Line 339 | Line 322 | public class ConcurrentSkipListSet<E>
322		}
323
324		/**
325	<	* Returns an element strictly greater than the given element, or null
326	<	* if there is no such element.
325	>	* Returns an element strictly greater than the given element, or
326	>	* <tt>null</tt> if there is no such element.
327		*
328		* @param o the value to match
329		* @return the least element greater than the given element, or
330	<	* null if there is no such element.
330	>	* <tt>null</tt> if there is no such element.
331		* @throws ClassCastException if o cannot be compared with the elements
332		*            currently in the set.
333		* @throws NullPointerException if o is <tt>null</tt>.
#	Line 353 | Line 336 | public class ConcurrentSkipListSet<E>
336		return m.higherKey(o);
337		}
338
339	+	/**
340	+	* Retrieves and removes the first (lowest) element.
341	+	*
342	+	* @return the least element, or <tt>null</tt> if empty.
343	+	*/
344	+	public E pollFirst() {
345	+	return m.removeFirstKey();
346	+	}
347	+
348	+	/**
349	+	* Retrieves and removes the last (highest) element.
350	+	*
351	+	* @return the last element, or <tt>null</tt> if empty.
352	+	*/
353	+	public E pollLast() {
354	+	return m.removeLastKey();
355	+	}
356	+
357	+
358		/* ---------------- SortedSet operations -------------- */
359
360
#	Line 387 | Line 389 | public class ConcurrentSkipListSet<E>
389		return m.lastKey();
390		}
391
392	+
393	+
394		/**
395		* Returns a view of the portion of this set whose elements range from
396		* <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive.  (If
#	Line 408 | Line 412 | public class ConcurrentSkipListSet<E>
412		* @throws NullPointerException if <tt>fromElement</tt> or
413		*         <tt>toElement</tt> is <tt>null</tt>.
414		*/
415	<	public ConcurrentSkipListSubSet<E> subSet(E fromElement, E toElement) {
415	>	public NavigableSet<E> subSet(E fromElement, E toElement) {
416		return new ConcurrentSkipListSubSet<E>(m, fromElement, toElement);
417		}
418
#	Line 425 | Line 429 | public class ConcurrentSkipListSet<E>
429		*         if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
430		* @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt>.
431		*/
432	<	public ConcurrentSkipListSubSet<E> headSet(E toElement) {
432	>	public NavigableSet<E> headSet(E toElement) {
433		return new ConcurrentSkipListSubSet<E>(m, null, toElement);
434		}
435
#	Line 444 | Line 448 | public class ConcurrentSkipListSet<E>
448		* <tt>Comparable</tt>).
449		* @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>.
450		*/
451	<	public ConcurrentSkipListSubSet<E> tailSet(E fromElement) {
451	>	public NavigableSet<E> tailSet(E fromElement) {
452		return new ConcurrentSkipListSubSet<E>(m, fromElement, null);
453		}
454	+
455	+	/**
456	+	* Subsets returned by {@link ConcurrentSkipListSet} subset operations
457	+	* represent a subrange of elements of their underlying
458	+	* sets. Instances of this class support all methods of their
459	+	* underlying sets, differing in that elements outside their range are
460	+	* ignored, and attempts to add elements outside their ranges result
461	+	* in {@link IllegalArgumentException}.  Instances of this class are
462	+	* constructed only using the <tt>subSet</tt>, <tt>headSet</tt>, and
463	+	* <tt>tailSet</tt> methods of their underlying sets.
464	+	*
465	+	*/
466	+	static class ConcurrentSkipListSubSet<E>
467	+	extends AbstractSet<E>
468	+	implements NavigableSet<E>, java.io.Serializable {
469	+
470	+	private static final long serialVersionUID = -7647078645896651609L;
471	+
472	+	/** The underlying submap   */
473	+	private final ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object> s;
474	+
475	+	/**
476	+	* Creates a new submap.
477	+	* @param fromElement inclusive least value, or <tt>null</tt> if from start
478	+	* @param toElement exclusive upper bound or <tt>null</tt> if to end
479	+	* @throws IllegalArgumentException if fromElement and toElement
480	+	* nonnull and fromElement greater than toElement
481	+	*/
482	+	ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
483	+	E fromElement, E toElement) {
484	+	s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>(map, fromElement,
485	+	toElement);
486	+	}
487	+
488	+	/**
489	+	* Returns the number of elements in this set.  If this set
490	+	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
491	+	* returns <tt>Integer.MAX_VALUE</tt>.
492	+	*
493	+	* <p>Beware that, unlike in most collections, this method is
494	+	* <em>NOT</em> a constant-time operation. Because of the
495	+	* asynchronous nature of these sets, determining the current
496	+	* number of elements requires traversing them all to count them.
497	+	* Additionally, it is possible for the size to change during
498	+	* execution of this method, in which case the returned result
499	+	* will be inaccurate. Thus, this method is typically not very
500	+	* useful in concurrent applications.
501	+	*
502	+	* @return  the number of elements in this set.
503	+	*/
504	+	public int size() {
505	+	return s.size();
506	+	}
507	+
508	+	/**
509	+	* Returns <tt>true</tt> if this set contains no elements.
510	+	* @return <tt>true</tt> if this set contains no elements.
511	+	*/
512	+	public boolean isEmpty() {
513	+	return s.isEmpty();
514	+	}
515	+
516	+	/**
517	+	* Returns <tt>true</tt> if this set contains the specified
518	+	* element.
519	+	*
520	+	* @param o the object to be checked for containment in this
521	+	* set.
522	+	* @return <tt>true</tt> if this set contains the specified
523	+	* element.
524	+	*
525	+	* @throws ClassCastException if the specified object cannot
526	+	* be compared with the elements currently in the set.
527	+	* @throws NullPointerException if o is <tt>null</tt>.
528	+	*/
529	+	public boolean contains(Object o) {
530	+	return s.containsKey(o);
531	+	}
532	+
533	+
534	+	/**
535	+	* Adds the specified element to this set if it is not already
536	+	* present.
537	+	*
538	+	* @param o element to be added to this set.
539	+	* @return <tt>true</tt> if the set did not already contain
540	+	* the specified element.
541	+	*
542	+	* @throws ClassCastException if the specified object cannot
543	+	* be compared with the elements currently in the set.
544	+	* @throws IllegalArgumentException if o is outside the range
545	+	* of this subset.
546	+	* @throws NullPointerException if o is <tt>null</tt>.
547	+	*/
548	+	public boolean add(E o) {
549	+	return s.put(o, Boolean.TRUE) == null;
550	+	}
551	+
552	+	/**
553	+	* Removes the specified element from this set if it is
554	+	* present.
555	+	*
556	+	* @param o object to be removed from this set, if present.
557	+	* @return <tt>true</tt> if the set contained the specified element.
558	+	*
559	+	* @throws ClassCastException if the specified object cannot
560	+	* be compared with the elements currently in the set.
561	+	* @throws NullPointerException if o is <tt>null</tt>.
562	+	*/
563	+	public boolean remove(Object o) {
564	+	return s.remove(o) != null;
565	+	}
566	+
567	+	/**
568	+	* Removes all of the elements from this set.
569	+	*/
570	+	public void clear() {
571	+	s.clear();
572	+	}
573	+
574	+	/**
575	+	* Returns an iterator over the elements in this set.  The elements
576	+	* are returned in ascending order.
577	+	*
578	+	* @return an iterator over the elements in this set.
579	+	*/
580	+	public Iterator<E> iterator() {
581	+	return s.keySet().iterator();
582	+	}
583	+
584	+	/**
585	+	* Returns an element greater than or equal to the given
586	+	* element, or <tt>null</tt> if there is no such element.
587	+	*
588	+	* @param o the value to match
589	+	* @return an element greater than or equal to given element, or <tt>null</tt>
590	+	* if there is no such element.
591	+	* @throws ClassCastException if o cannot be compared with the
592	+	* elements currently in the set.
593	+	* @throws NullPointerException if o is <tt>null</tt>
594	+	*/
595	+	public E ceiling(E o) {
596	+	E key = o;
597	+	E least = s.getLeast();
598	+	if (least != null && s.getMap().compare(o, least) < 0)
599	+	key = least;
600	+	E k = s.getMap().ceilingKey(key);
601	+	return (k != null && s.inHalfOpenRange(k))? k : null;
602	+	}
603	+
604	+	/**
605	+	* Returns an element strictly less than the given element, or <tt>null</tt> if
606	+	* there is no such element.
607	+	*
608	+	* @param o the value to match
609	+	* @return the greatest element less than the given element, or
610	+	* <tt>null</tt> if there is no such element.
611	+	* @throws ClassCastException if o cannot be compared with the
612	+	* elements currently in the set.
613	+	* @throws NullPointerException if o is <tt>null</tt>.
614	+	*/
615	+	public E lower(E o) {
616	+	E k = s.getMap().lowerKey(o);
617	+	return (k != null && s.inHalfOpenRange(k))? k : null;
618	+	}
619	+
620	+	/**
621	+	* Returns an element less than or equal to the given element, or <tt>null</tt>
622	+	* if there is no such element.
623	+	*
624	+	* @param o the value to match
625	+	* @return the greatest element less than or equal to given
626	+	* element, or <tt>null</tt> if there is no such element.
627	+	* @throws ClassCastException if o cannot be compared with the
628	+	* elements currently in the set.
629	+	* @throws NullPointerException if o is <tt>null</tt>.
630	+	*/
631	+	public E floor(E o) {
632	+	E k = s.getMap().floorKey(o);
633	+	return (k != null && s.inHalfOpenRange(k))? k : null;
634	+	}
635	+
636	+	/**
637	+	* Returns an element strictly greater than the given element, or <tt>null</tt>
638	+	* if there is no such element.
639	+	*
640	+	* @param o the value to match
641	+	* @return the least element greater than the given element, or
642	+	* <tt>null</tt> if there is no such element.
643	+	* @throws ClassCastException if o cannot be compared with the
644	+	* elements currently in the set.
645	+	* @throws NullPointerException if o is <tt>null</tt>.
646	+	*/
647	+	public E higher(E o) {
648	+	E k;
649	+	E least = s.getLeast();
650	+	if (least != null && s.getMap().compare(o, least) < 0)
651	+	k = s.getMap().ceilingKey(least);
652	+	else
653	+	k = s.getMap().higherKey(o);
654	+	return (k != null && s.inHalfOpenRange(k))? k : null;
655	+	}
656	+
657	+	/**
658	+	* Retrieves and removes the first (lowest) element.
659	+	*
660	+	* @return the first element, or <tt>null</tt> if empty.
661	+	*/
662	+	public E pollFirst() {
663	+	for (;;) {
664	+	E k = s.lowestKey();
665	+	if (k == null)
666	+	return null;
667	+	if (remove(k))
668	+	return k;
669	+	}
670	+	}
671	+
672	+	/**
673	+	* Retrieves and removes the last (highest) element.
674	+	*
675	+	* @return the last element, or <tt>null</tt> if empty.
676	+	*/
677	+	public E pollLast() {
678	+	for (;;) {
679	+	E k = s.highestKey();
680	+	if (k == null)
681	+	return null;
682	+	if (remove(k))
683	+	return k;
684	+	}
685	+	}
686	+
687	+	/**
688	+	* Returns the comparator used to order this set, or <tt>null</tt>
689	+	* if this set uses its elements natural ordering.
690	+	*
691	+	* @return the comparator used to order this set, or <tt>null</tt>
692	+	* if this set uses its elements natural ordering.
693	+	*/
694	+	public Comparator<? super E> comparator() {
695	+	return s.comparator();
696	+	}
697	+
698	+	/**
699	+	* Returns the first (lowest) element currently in this set.
700	+	*
701	+	* @return the first (lowest) element currently in this set.
702	+	* @throws    NoSuchElementException sorted set is empty.
703	+	*/
704	+	public E first() {
705	+	return s.firstKey();
706	+	}
707	+
708	+	/**
709	+	* Returns the last (highest) element currently in this set.
710	+	*
711	+	* @return the last (highest) element currently in this set.
712	+	* @throws    NoSuchElementException sorted set is empty.
713	+	*/
714	+	public E last() {
715	+	return s.lastKey();
716	+	}
717	+
718	+	/**
719	+	* Returns a view of the portion of this set whose elements
720	+	* range from <tt>fromElement</tt>, inclusive, to
721	+	* <tt>toElement</tt>, exclusive.  (If <tt>fromElement</tt>
722	+	* and <tt>toElement</tt> are equal, the returned sorted set
723	+	* is empty.)  The returned sorted set is backed by this set,
724	+	* so changes in the returned sorted set are reflected in this
725	+	* set, and vice-versa.
726	+	* @param fromElement low endpoint (inclusive) of the subSet.
727	+	* @param toElement high endpoint (exclusive) of the subSet.
728	+	* @return a view of the portion of this set whose elements
729	+	* range from <tt>fromElement</tt>, inclusive, to
730	+	* <tt>toElement</tt>, exclusive.
731	+	* @throws ClassCastException if <tt>fromElement</tt> and
732	+	* <tt>toElement</tt> cannot be compared to one another using
733	+	* this set's comparator (or, if the set has no comparator,
734	+	* using natural ordering).
735	+	* @throws IllegalArgumentException if <tt>fromElement</tt> is
736	+	* greater than <tt>toElement</tt> or either key is outside
737	+	* the range of this set.
738	+	* @throws NullPointerException if <tt>fromElement</tt> or
739	+	*             <tt>toElement</tt> is <tt>null</tt>.
740	+	*/
741	+	public NavigableSet<E> subSet(E fromElement,
742	+	E toElement) {
743	+	if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
744	+	throw new IllegalArgumentException("element out of range");
745	+	return new ConcurrentSkipListSubSet<E>(s.getMap(),
746	+	fromElement, toElement);
747	+	}
748	+
749	+	/**
750	+	* Returns a view of the portion of this set whose elements are
751	+	* strictly less than <tt>toElement</tt>.  The returned sorted set
752	+	* is backed by this set, so changes in the returned sorted set
753	+	* are reflected in this set, and vice-versa.
754	+	* @param toElement high endpoint (exclusive) of the headSet.
755	+	* @return a view of the portion of this set whose elements
756	+	* are strictly less than toElement.
757	+	* @throws ClassCastException if <tt>toElement</tt> is not
758	+	* compatible with this set's comparator (or, if the set has
759	+	* no comparator, if <tt>toElement</tt> does not implement
760	+	* <tt>Comparable</tt>).
761	+	* @throws IllegalArgumentException if <tt>toElement</tt> is
762	+	* outside the range of this set.
763	+	* @throws NullPointerException if <tt>toElement</tt> is
764	+	* <tt>null</tt>.
765	+	*/
766	+	public NavigableSet<E> headSet(E toElement) {
767	+	E least = s.getLeast();
768	+	if (!s.inOpenRange(toElement))
769	+	throw new IllegalArgumentException("element out of range");
770	+	return new ConcurrentSkipListSubSet<E>(s.getMap(),
771	+	least, toElement);
772	+	}
773	+
774	+	/**
775	+	* Returns a view of the portion of this set whose elements
776	+	* are greater than or equal to <tt>fromElement</tt>.  The
777	+	* returned sorted set is backed by this set, so changes in
778	+	* the returned sorted set are reflected in this set, and
779	+	* vice-versa.
780	+	* @param fromElement low endpoint (inclusive) of the tailSet.
781	+	* @return a view of the portion of this set whose elements
782	+	* are greater than or equal to <tt>fromElement</tt>.
783	+	* @throws ClassCastException if <tt>fromElement</tt> is not
784	+	* compatible with this set's comparator (or, if the set has
785	+	* no comparator, if <tt>fromElement</tt> does not implement
786	+	* <tt>Comparable</tt>).
787	+	* @throws IllegalArgumentException if <tt>fromElement</tt> is
788	+	* outside the range of this set.
789	+	* @throws NullPointerException if <tt>fromElement</tt> is
790	+	* <tt>null</tt>.
791	+	*/
792	+	public NavigableSet<E> tailSet(E fromElement) {
793	+	E fence = s.getFence();
794	+	if (!s.inOpenRange(fromElement))
795	+	throw new IllegalArgumentException("element out of range");
796	+	return new ConcurrentSkipListSubSet<E>(s.getMap(),
797	+	fromElement, fence);
798	+	}
799	+	}
800		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines