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.4 by dl, Sat Oct 16 14:49:45 2004 UTC vs.
Revision 1.5 by dl, Tue Dec 21 17:27:44 2004 UTC

#	Line 220 | Line 220 | public class ConcurrentSkipListSet<E>
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		/**
#	Line 342 | 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 351 | 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 469 | 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		/**
#	Line 481 | Line 491 | public class ConcurrentSkipListSet<E>
491		*/
492		ConcurrentSkipListSubSet(ConcurrentSkipListMap<E,Object> map,
493		E fromElement, E toElement) {
494	<	s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>(map, fromElement,
495	<	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;
494	>	s = new ConcurrentSkipListMap.ConcurrentSkipListSubMap<E,Object>
495	>	(map, fromElement, toElement);
496		}
497
498	<	/**
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	<	}
498	>	// subsubset construction
499
500	<	/**
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) {
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
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	–	*/
507		public NavigableSet<E> headSet(E toElement) {
508		E least = s.getLeast();
509		if (!s.inOpenRange(toElement))
#	Line 771 | Line 512 | public class ConcurrentSkipListSet<E>
512		least, toElement);
513		}
514
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	–	*/
515		public NavigableSet<E> tailSet(E fromElement) {
516		E fence = s.getFence();
517		if (!s.inOpenRange(fromElement))
#	Line 796 | Line 519 | public class ConcurrentSkipListSet<E>
519		return new ConcurrentSkipListSubSet<E>(s.getMap(),
520		fromElement, fence);
521		}
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