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.2 by dl, Mon Sep 6 17:01:54 2004 UTC vs.
Revision 1.5 by dl, Tue Dec 21 17:27:44 2004 UTC

#	Line 28 | Line 28 | import java.util.concurrent.*;
28		* other operations.
29		*
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 85 | 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 97 | 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 212 | Line 219 | public class ConcurrentSkipListSet<E>
219		public Iterator<E> iterator() {
220		return m.keyIterator();
221		}
222	+
223	+	/**
224	+	* Returns an iterator over the elements in this set.  The elements
225	+	* are returned in descending order.
226	+	*
227	+	* @return an iterator over the elements in this set.
228	+	*/
229	+	public Iterator<E> descendingIterator() {
230	+	return m.descendingKeyIterator();
231	+	}
232	+
233	+	/* ---------------- AbstractSet Overrides -------------- */
234	+
235	+	/**
236	+	* Compares the specified object with this set for equality.  Returns
237	+	* <tt>true</tt> if the specified object is also a set, the two sets
238	+	* have the same size, and every member of the specified set is
239	+	* contained in this set (or equivalently, every member of this set is
240	+	* contained in the specified set).  This definition ensures that the
241	+	* equals method works properly across different implementations of the
242	+	* set interface.
243	+	*
244	+	* @param o Object to be compared for equality with this set.
245	+	* @return <tt>true</tt> if the specified Object is equal to this set.
246	+	*/
247	+	public boolean equals(Object o) {
248	+	// Override AbstractSet version to avoid calling size()
249	+	if (o == this)
250	+	return true;
251	+	if (!(o instanceof Set))
252	+	return false;
253	+	Collection c = (Collection) o;
254	+	try {
255	+	return containsAll(c) && c.containsAll(this);
256	+	} catch(ClassCastException unused)   {
257	+	return false;
258	+	} catch(NullPointerException unused) {
259	+	return false;
260	+	}
261	+	}
262	+
263	+	/**
264	+	* Removes from this set all of its elements that are contained in
265	+	* the specified collection.  If the specified collection is also
266	+	* a set, this operation effectively modifies this set so that its
267	+	* value is the <i>asymmetric set difference</i> of the two sets.
268	+	*
269	+	* @param  c collection that defines which elements will be removed from
270	+	*           this set.
271	+	* @return <tt>true</tt> if this set changed as a result of the call.
272	+	*
273	+	* @throws ClassCastException if the types of one or more elements in this
274	+	*            set are incompatible with the specified collection
275	+	* @throws NullPointerException if the specified collection, or any
276	+	* of its elements are <tt>null</tt>.
277	+	*/
278	+	public boolean removeAll(Collection<?> c) {
279	+	// Override AbstractSet version to avoid unnecessary call to size()
280	+	boolean modified = false;
281	+	for (Iterator<?> i = c.iterator(); i.hasNext(); )
282	+	if (remove(i.next()))
283	+	modified = true;
284	+	return modified;
285	+	}
286
287		/* ---------------- Relational operations -------------- */
288
289		/**
290		* Returns an element greater than or equal to the given element, or
291	<	* null if there is no such element.
291	>	* <tt>null</tt> if there is no such element.
292		*
293		* @param o the value to match
294	<	* @return an element greater than or equal to given element, or null
295	<	* if there is no such element.
294	>	* @return an element greater than or equal to given element, or
295	>	* <tt>null</tt> if there is no such element.
296		* @throws ClassCastException if o cannot be compared with the elements
297		*            currently in the set.
298		* @throws NullPointerException if o is <tt>null</tt>
#	Line 231 | Line 302 | public class ConcurrentSkipListSet<E>
302		}
303
304		/**
305	<	* Returns an element strictly less than the given element, or null if
306	<	* there is no such element.
305	>	* Returns an element strictly less than the given element, or
306	>	* <tt>null</tt> if there is no such element.
307		*
308		* @param o the value to match
309		* @return the greatest element less than the given element, or
310	<	* null if there is no such element.
310	>	* <tt>null</tt> if there is no such element.
311		* @throws ClassCastException if o cannot be compared with the elements
312		*            currently in the set.
313		* @throws NullPointerException if o is <tt>null</tt>.
#	Line 246 | Line 317 | public class ConcurrentSkipListSet<E>
317		}
318
319		/**
320	<	* Returns an element less than or equal to the given element, or null
321	<	* if there is no such element.
320	>	* Returns an element less than or equal to the given element, or
321	>	* <tt>null</tt> if there is no such element.
322		*
323		* @param o the value to match
324		* @return the greatest element less than or equal to given
325	<	* element, or null if there is no such element.
325	>	* element, or <tt>null</tt> if there is no such element.
326		* @throws ClassCastException if o cannot be compared with the elements
327		*            currently in the set.
328		* @throws NullPointerException if o is <tt>null</tt>.
#	Line 261 | Line 332 | public class ConcurrentSkipListSet<E>
332		}
333
334		/**
335	<	* Returns an element strictly greater than the given element, or null
336	<	* if there is no such element.
335	>	* Returns an element strictly greater than the given element, or
336	>	* <tt>null</tt> if there is no such element.
337		*
338		* @param o the value to match
339		* @return the least element greater than the given element, or
340	<	* null if there is no such element.
340	>	* <tt>null</tt> if there is no such element.
341		* @throws ClassCastException if o cannot be compared with the elements
342		*            currently in the set.
343		* @throws NullPointerException if o is <tt>null</tt>.
#	Line 281 | Line 352 | public class ConcurrentSkipListSet<E>
352		* @return the least element, or <tt>null</tt> if empty.
353		*/
354		public E pollFirst() {
355	<	return m.removeFirstKey();
355	>	return m.pollFirstKey();
356		}
357
358		/**
#	Line 290 | Line 361 | public class ConcurrentSkipListSet<E>
361		* @return the last element, or <tt>null</tt> if empty.
362		*/
363		public E pollLast() {
364	<	return m.removeLastKey();
364	>	return m.pollLastKey();
365		}
366
367
#	Line 328 | Line 399 | public class ConcurrentSkipListSet<E>
399		return m.lastKey();
400		}
401
402	+
403	+
404		/**
405		* Returns a view of the portion of this set whose elements range from
406		* <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive.  (If
#	Line 406 | Line 479 | public class ConcurrentSkipListSet<E>
479
480		private static final long serialVersionUID = -7647078645896651609L;
481
482	<	/** The underlying submap   */
482	>	/** The underlying submap  */
483		private final ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object> s;
484
485		/**
486		* Creates a new submap.
487	<	* @param fromElement inclusive least value, or null if from start
488	<	* @param toElement exclusive upper bound or null if to end
487	>	* @param fromElement inclusive least value, or <tt>null</tt> if from start
488	>	* @param toElement exclusive upper bound or <tt>null</tt> if to end
489		* @throws IllegalArgumentException if fromElement and toElement
490		* nonnull and fromElement greater than toElement
491		*/
492		ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
493		E fromElement, E toElement) {
494	<	s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>(map, fromElement,
495	<	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();
494	>	s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>
495	>	(map, fromElement, toElement);
496		}
497
498	<	/**
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	<	}
498	>	// subsubset construction
499
500	<	/**
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) {
500	>	public NavigableSet<E> subSet(E fromElement, E toElement) {
501		if (!s.inOpenRange(fromElement) || !s.inOpenRange(toElement))
502		throw new IllegalArgumentException("element out of range");
503		return new ConcurrentSkipListSubSet<E>(s.getMap(),
504		fromElement, toElement);
505		}
506
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	–	*/
507		public NavigableSet<E> headSet(E toElement) {
508		E least = s.getLeast();
509		if (!s.inOpenRange(toElement))
#	Line 708 | Line 512 | public class ConcurrentSkipListSet<E>
512		least, toElement);
513		}
514
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	–	*/
515		public NavigableSet<E> tailSet(E fromElement) {
516		E fence = s.getFence();
517		if (!s.inOpenRange(fromElement))
#	Line 733 | Line 519 | public class ConcurrentSkipListSet<E>
519		return new ConcurrentSkipListSubSet<E>(s.getMap(),
520		fromElement, fence);
521		}
736	–	}
522
523	+	// relays to submap methods
524	+
525	+	public int size()                 { return s.size(); }
526	+	public boolean isEmpty()          { return s.isEmpty(); }
527	+	public boolean contains(Object o) { return s.containsKey(o); }
528	+	public void clear()               { s.clear(); }
529	+	public E first()                  { return s.firstKey(); }
530	+	public E last()                   { return s.lastKey(); }
531	+	public E ceiling(E o)             { return s.ceilingKey(o); }
532	+	public E lower(E o)               { return s.lowerKey(o); }
533	+	public E floor(E o)               { return s.floorKey(o); }
534	+	public E higher(E o)              { return s.higherKey(o); }
535	+	public boolean remove(Object o) { return s.remove(o)==Boolean.TRUE; }
536	+	public boolean add(E o)       { return s.put(o, Boolean.TRUE)==null; }
537	+	public Comparator<? super E> comparator() { return s.comparator(); }
538	+	public Iterator<E> iterator()     { return s.keySet().iterator(); }
539	+	public Iterator<E> descendingIterator() {
540	+	return s.descendingKeySet().iterator();
541	+	}
542	+	public E pollFirst() {
543	+	Map.Entry<E,?> e = s.pollFirstEntry();
544	+	return (e == null)? null : e.getKey();
545	+	}
546	+	public E pollLast() {
547	+	Map.Entry<E,?> e = s.pollLastEntry();
548	+	return (e == null)? null : e.getKey();
549	+	}
550
551	+	}
552		}

Diff Legend

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