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.2 by dl, Mon Sep 6 17:01:54 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
32		* asynchronous nature of these sets, determining the current number
#	Line 63 | Line 44 | import java.util.concurrent.*;
44		*/
45		public class ConcurrentSkipListSet<E>
46		extends AbstractSet<E>
47	<	implements SortedSet<E>, Queue<E>, Cloneable, java.io.Serializable {
47	>	implements NavigableSet<E>, Cloneable, java.io.Serializable {
48
49		private static final long serialVersionUID = -2479143111061671589L;
50
#	Line 232 | Line 213 | public class ConcurrentSkipListSet<E>
213		return m.keyIterator();
214		}
215
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	–	}
247	–
248	–	/**
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	–	}
256	–
257	–	/**
258	–	* Retrieves and removes the first (lowest) element.  This method
259	–	* differs from the <tt>poll</tt> method in that it throws an
260	–	* exception if empty.
261	–	*
262	–	* @return the first (lowest) element.
263	–	* @throws NoSuchElementException if empty.
264	–	*/
265	–	public E remove() {
266	–	E x = m.removeFirstKey();
267	–	if (x == null)
268	–	throw new NoSuchElementException();
269	–	return x;
270	–	}
271	–
272	–	/**
273	–	* Retrieves, but does not remove, the first (lowest) element,
274	–	* returning <tt>null</tt> if empty.
275	–	*
276	–	* @return the first (lowest) element, or <tt>null</tt> if empty.
277	–	*/
278	–	public E peek() {
279	–	return m.lowestKey();
280	–	}
281	–
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	–
216		/* ---------------- Relational operations -------------- */
217
218		/**
#	Line 353 | Line 275 | public class ConcurrentSkipListSet<E>
275		return m.higherKey(o);
276		}
277
278	+	/**
279	+	* Retrieves and removes the first (lowest) element.
280	+	*
281	+	* @return the least element, or <tt>null</tt> if empty.
282	+	*/
283	+	public E pollFirst() {
284	+	return m.removeFirstKey();
285	+	}
286	+
287	+	/**
288	+	* Retrieves and removes the last (highest) element.
289	+	*
290	+	* @return the last element, or <tt>null</tt> if empty.
291	+	*/
292	+	public E pollLast() {
293	+	return m.removeLastKey();
294	+	}
295	+
296	+
297		/* ---------------- SortedSet operations -------------- */
298
299
#	Line 408 | Line 349 | public class ConcurrentSkipListSet<E>
349		* @throws NullPointerException if <tt>fromElement</tt> or
350		*         <tt>toElement</tt> is <tt>null</tt>.
351		*/
352	<	public ConcurrentSkipListSubSet<E> subSet(E fromElement, E toElement) {
352	>	public NavigableSet<E> subSet(E fromElement, E toElement) {
353		return new ConcurrentSkipListSubSet<E>(m, fromElement, toElement);
354		}
355
#	Line 425 | Line 366 | public class ConcurrentSkipListSet<E>
366		*         if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
367		* @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt>.
368		*/
369	<	public ConcurrentSkipListSubSet<E> headSet(E toElement) {
369	>	public NavigableSet<E> headSet(E toElement) {
370		return new ConcurrentSkipListSubSet<E>(m, null, toElement);
371		}
372
#	Line 444 | Line 385 | public class ConcurrentSkipListSet<E>
385		* <tt>Comparable</tt>).
386		* @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>.
387		*/
388	<	public ConcurrentSkipListSubSet<E> tailSet(E fromElement) {
388	>	public NavigableSet<E> tailSet(E fromElement) {
389		return new ConcurrentSkipListSubSet<E>(m, fromElement, null);
390		}
391	+
392	+	/**
393	+	* Subsets returned by {@link ConcurrentSkipListSet} subset operations
394	+	* represent a subrange of elements of their underlying
395	+	* sets. Instances of this class support all methods of their
396	+	* underlying sets, differing in that elements outside their range are
397	+	* ignored, and attempts to add elements outside their ranges result
398	+	* in {@link IllegalArgumentException}.  Instances of this class are
399	+	* constructed only using the <tt>subSet</tt>, <tt>headSet</tt>, and
400	+	* <tt>tailSet</tt> methods of their underlying sets.
401	+	*
402	+	*/
403	+	static class ConcurrentSkipListSubSet<E>
404	+	extends AbstractSet<E>
405	+	implements NavigableSet<E>, java.io.Serializable {
406	+
407	+	private static final long serialVersionUID = -7647078645896651609L;
408	+
409	+	/** The underlying submap   */
410	+	private final ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object> s;
411	+
412	+	/**
413	+	* Creates a new submap.
414	+	* @param fromElement inclusive least value, or null if from start
415	+	* @param toElement exclusive upper bound or null if to end
416	+	* @throws IllegalArgumentException if fromElement and toElement
417	+	* nonnull and fromElement greater than toElement
418	+	*/
419	+	ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
420	+	E fromElement, E toElement) {
421	+	s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>(map, fromElement,
422	+	toElement);
423	+	}
424	+
425	+	/**
426	+	* Returns the number of elements in this set.  If this set
427	+	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
428	+	* returns <tt>Integer.MAX_VALUE</tt>.
429	+	*
430	+	* <p>Beware that, unlike in most collections, this method is
431	+	* <em>NOT</em> a constant-time operation. Because of the
432	+	* asynchronous nature of these sets, determining the current
433	+	* number of elements requires traversing them all to count them.
434	+	* Additionally, it is possible for the size to change during
435	+	* execution of this method, in which case the returned result
436	+	* will be inaccurate. Thus, this method is typically not very
437	+	* useful in concurrent applications.
438	+	*
439	+	* @return  the number of elements in this set.
440	+	*/
441	+	public int size() {
442	+	return s.size();
443	+	}
444	+
445	+	/**
446	+	* Returns <tt>true</tt> if this set contains no elements.
447	+	* @return <tt>true</tt> if this set contains no elements.
448	+	*/
449	+	public boolean isEmpty() {
450	+	return s.isEmpty();
451	+	}
452	+
453	+	/**
454	+	* Returns <tt>true</tt> if this set contains the specified
455	+	* element.
456	+	*
457	+	* @param o the object to be checked for containment in this
458	+	* set.
459	+	* @return <tt>true</tt> if this set contains the specified
460	+	* element.
461	+	*
462	+	* @throws ClassCastException if the specified object cannot
463	+	* be compared with the elements currently in the set.
464	+	* @throws NullPointerException if o is <tt>null</tt>.
465	+	*/
466	+	public boolean contains(Object o) {
467	+	return s.containsKey(o);
468	+	}
469	+
470	+
471	+	/**
472	+	* Adds the specified element to this set if it is not already
473	+	* present.
474	+	*
475	+	* @param o element to be added to this set.
476	+	* @return <tt>true</tt> if the set did not already contain
477	+	* the specified element.
478	+	*
479	+	* @throws ClassCastException if the specified object cannot
480	+	* be compared with the elements currently in the set.
481	+	* @throws IllegalArgumentException if o is outside the range
482	+	* of this subset.
483	+	* @throws NullPointerException if o is <tt>null</tt>.
484	+	*/
485	+	public boolean add(E o) {
486	+	return s.put(o, Boolean.TRUE) == null;
487	+	}
488	+
489	+	/**
490	+	* Removes the specified element from this set if it is
491	+	* present.
492	+	*
493	+	* @param o object to be removed from this set, if present.
494	+	* @return <tt>true</tt> if the set contained the specified element.
495	+	*
496	+	* @throws ClassCastException if the specified object cannot
497	+	* be compared with the elements currently in the set.
498	+	* @throws NullPointerException if o is <tt>null</tt>.
499	+	*/
500	+	public boolean remove(Object o) {
501	+	return s.remove(o) != null;
502	+	}
503	+
504	+	/**
505	+	* Removes all of the elements from this set.
506	+	*/
507	+	public void clear() {
508	+	s.clear();
509	+	}
510	+
511	+	/**
512	+	* Returns an iterator over the elements in this set.  The elements
513	+	* are returned in ascending order.
514	+	*
515	+	* @return an iterator over the elements in this set.
516	+	*/
517	+	public Iterator<E> iterator() {
518	+	return s.keySet().iterator();
519	+	}
520	+
521	+	/**
522	+	* Returns an element greater than or equal to the given
523	+	* element, or null if there is no such element.
524	+	*
525	+	* @param o the value to match
526	+	* @return an element greater than or equal to given element, or null
527	+	* if there is no such element.
528	+	* @throws ClassCastException if o cannot be compared with the
529	+	* elements currently in the set.
530	+	* @throws NullPointerException if o is <tt>null</tt>
531	+	*/
532	+	public E ceiling(E o) {
533	+	E key = o;
534	+	E least = s.getLeast();
535	+	if (least != null && s.getMap().compare(o, least) < 0)
536	+	key = least;
537	+	E k = s.getMap().ceilingKey(key);
538	+	return (k != null && s.inHalfOpenRange(k))? k : null;
539	+	}
540	+
541	+	/**
542	+	* Returns an element strictly less than the given element, or null if
543	+	* there is no such element.
544	+	*
545	+	* @param o the value to match
546	+	* @return the greatest element less than the given element, or
547	+	* null if there is no such element.
548	+	* @throws ClassCastException if o cannot be compared with the
549	+	* elements currently in the set.
550	+	* @throws NullPointerException if o is <tt>null</tt>.
551	+	*/
552	+	public E lower(E o) {
553	+	E k = s.getMap().lowerKey(o);
554	+	return (k != null && s.inHalfOpenRange(k))? k : null;
555	+	}
556	+
557	+	/**
558	+	* Returns an element less than or equal to the given element, or null
559	+	* if there is no such element.
560	+	*
561	+	* @param o the value to match
562	+	* @return the greatest element less than or equal to given
563	+	* element, or null if there is no such element.
564	+	* @throws ClassCastException if o cannot be compared with the
565	+	* elements currently in the set.
566	+	* @throws NullPointerException if o is <tt>null</tt>.
567	+	*/
568	+	public E floor(E o) {
569	+	E k = s.getMap().floorKey(o);
570	+	return (k != null && s.inHalfOpenRange(k))? k : null;
571	+	}
572	+
573	+	/**
574	+	* Returns an element strictly greater than the given element, or null
575	+	* if there is no such element.
576	+	*
577	+	* @param o the value to match
578	+	* @return the least element greater than the given element, or
579	+	* null if there is no such element.
580	+	* @throws ClassCastException if o cannot be compared with the
581	+	* elements currently in the set.
582	+	* @throws NullPointerException if o is <tt>null</tt>.
583	+	*/
584	+	public E higher(E o) {
585	+	E k;
586	+	E least = s.getLeast();
587	+	if (least != null && s.getMap().compare(o, least) < 0)
588	+	k = s.getMap().ceilingKey(least);
589	+	else
590	+	k = s.getMap().higherKey(o);
591	+	return (k != null && s.inHalfOpenRange(k))? k : null;
592	+	}
593	+
594	+	/**
595	+	* Retrieves and removes the first (lowest) element.
596	+	*
597	+	* @return the first element, or <tt>null</tt> if empty.
598	+	*/
599	+	public E pollFirst() {
600	+	for (;;) {
601	+	E k = s.lowestKey();
602	+	if (k == null)
603	+	return null;
604	+	if (remove(k))
605	+	return k;
606	+	}
607	+	}
608	+
609	+	/**
610	+	* Retrieves and removes the last (highest) element.
611	+	*
612	+	* @return the last element, or <tt>null</tt> if empty.
613	+	*/
614	+	public E pollLast() {
615	+	for (;;) {
616	+	E k = s.highestKey();
617	+	if (k == null)
618	+	return null;
619	+	if (remove(k))
620	+	return k;
621	+	}
622	+	}
623	+
624	+	/**
625	+	* Returns the comparator used to order this set, or <tt>null</tt>
626	+	* if this set uses its elements natural ordering.
627	+	*
628	+	* @return the comparator used to order this set, or <tt>null</tt>
629	+	* if this set uses its elements natural ordering.
630	+	*/
631	+	public Comparator<? super E> comparator() {
632	+	return s.comparator();
633	+	}
634	+
635	+	/**
636	+	* Returns the first (lowest) element currently in this set.
637	+	*
638	+	* @return the first (lowest) element currently in this set.
639	+	* @throws    NoSuchElementException sorted set is empty.
640	+	*/
641	+	public E first() {
642	+	return s.firstKey();
643	+	}
644	+
645	+	/**
646	+	* Returns the last (highest) element currently in this set.
647	+	*
648	+	* @return the last (highest) element currently in this set.
649	+	* @throws    NoSuchElementException sorted set is empty.
650	+	*/
651	+	public E last() {
652	+	return s.lastKey();
653	+	}
654	+
655	+	/**
656	+	* Returns a view of the portion of this set whose elements
657	+	* range from <tt>fromElement</tt>, inclusive, to
658	+	* <tt>toElement</tt>, exclusive.  (If <tt>fromElement</tt>
659	+	* and <tt>toElement</tt> are equal, the returned sorted set
660	+	* is empty.)  The returned sorted set is backed by this set,
661	+	* so changes in the returned sorted set are reflected in this
662	+	* set, and vice-versa.
663	+	* @param fromElement low endpoint (inclusive) of the subSet.
664	+	* @param toElement high endpoint (exclusive) of the subSet.
665	+	* @return a view of the portion of this set whose elements
666	+	* range from <tt>fromElement</tt>, inclusive, to
667	+	* <tt>toElement</tt>, exclusive.
668	+	* @throws ClassCastException if <tt>fromElement</tt> and
669	+	* <tt>toElement</tt> cannot be compared to one another using
670	+	* this set's comparator (or, if the set has no comparator,
671	+	* using natural ordering).
672	+	* @throws IllegalArgumentException if <tt>fromElement</tt> is
673	+	* greater than <tt>toElement</tt> or either key is outside
674	+	* the range of this set.
675	+	* @throws NullPointerException if <tt>fromElement</tt> or
676	+	*             <tt>toElement</tt> is <tt>null</tt>.
677	+	*/
678	+	public NavigableSet<E> subSet(E fromElement,
679	+	E toElement) {
680	+	if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
681	+	throw new IllegalArgumentException("element out of range");
682	+	return new ConcurrentSkipListSubSet<E>(s.getMap(),
683	+	fromElement, toElement);
684	+	}
685	+
686	+	/**
687	+	* Returns a view of the portion of this set whose elements are
688	+	* strictly less than <tt>toElement</tt>.  The returned sorted set
689	+	* is backed by this set, so changes in the returned sorted set
690	+	* are reflected in this set, and vice-versa.
691	+	* @param toElement high endpoint (exclusive) of the headSet.
692	+	* @return a view of the portion of this set whose elements
693	+	* are strictly less than toElement.
694	+	* @throws ClassCastException if <tt>toElement</tt> is not
695	+	* compatible with this set's comparator (or, if the set has
696	+	* no comparator, if <tt>toElement</tt> does not implement
697	+	* <tt>Comparable</tt>).
698	+	* @throws IllegalArgumentException if <tt>toElement</tt> is
699	+	* outside the range of this set.
700	+	* @throws NullPointerException if <tt>toElement</tt> is
701	+	* <tt>null</tt>.
702	+	*/
703	+	public NavigableSet<E> headSet(E toElement) {
704	+	E least = s.getLeast();
705	+	if (!s.inOpenRange(toElement))
706	+	throw new IllegalArgumentException("element out of range");
707	+	return new ConcurrentSkipListSubSet<E>(s.getMap(),
708	+	least, toElement);
709	+	}
710	+
711	+	/**
712	+	* Returns a view of the portion of this set whose elements
713	+	* are greater than or equal to <tt>fromElement</tt>.  The
714	+	* returned sorted set is backed by this set, so changes in
715	+	* the returned sorted set are reflected in this set, and
716	+	* vice-versa.
717	+	* @param fromElement low endpoint (inclusive) of the tailSet.
718	+	* @return a view of the portion of this set whose elements
719	+	* are greater than or equal to <tt>fromElement</tt>.
720	+	* @throws ClassCastException if <tt>fromElement</tt> is not
721	+	* compatible with this set's comparator (or, if the set has
722	+	* no comparator, if <tt>fromElement</tt> does not implement
723	+	* <tt>Comparable</tt>).
724	+	* @throws IllegalArgumentException if <tt>fromElement</tt> is
725	+	* outside the range of this set.
726	+	* @throws NullPointerException if <tt>fromElement</tt> is
727	+	* <tt>null</tt>.
728	+	*/
729	+	public NavigableSet<E> tailSet(E fromElement) {
730	+	E fence = s.getFence();
731	+	if (!s.inOpenRange(fromElement))
732	+	throw new IllegalArgumentException("element out of range");
733	+	return new ConcurrentSkipListSubSet<E>(s.getMap(),
734	+	fromElement, fence);
735	+	}
736	+	}
737	+
738	+
739		}

Diff Legend

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