ViewVC Help

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

root/jsr166/jsr166/src/main/java/util/Collections.java

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.1 by dl, Tue Dec 28 12:14:07 2004 UTC vs.
Revision 1.9 by jsr166, Fri May 27 03:44:18 2005 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
#	Line 37 | Line 37 | import java.lang.reflect.Array;
37		* example, invoking the <tt>sort</tt> method on an unmodifiable list that is
38		* already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
39		*
40	<	* <p>This class is a member of the
40	>	* <p>This class is a member of the
41		* <a href="{@docRoot}/../guide/collections/index.html">
42		* Java Collections Framework</a>.
43		*
#	Line 63 | Line 63 | public class Collections {
63		* two implementations, one of which is appropriate for RandomAccess
64		* lists, the other for "sequential."  Often, the random access variant
65		* yields better performance on small sequential access lists.  The
66	<	* tuning  parameters below determine the cutoff point for what constitutes
66	>	* tuning parameters below determine the cutoff point for what constitutes
67		* a "small" sequential access list for each algorithm.  The values below
68		* were empirically determined to work well for LinkedList. Hopefully
69		* they should be reasonable for other sequential access List
#	Line 97 | Line 97 | public class Collections {
97		* The sorting algorithm is a modified mergesort (in which the merge is
98		* omitted if the highest element in the low sublist is less than the
99		* lowest element in the high sublist).  This algorithm offers guaranteed
100	<	* n log(n) performance.
100	>	* n log(n) performance.
101		*
102		* This implementation dumps the specified list into an array, sorts
103		* the array, and iterates over the list resetting each element
#	Line 135 | Line 135 | public class Collections {
135		* The sorting algorithm is a modified mergesort (in which the merge is
136		* omitted if the highest element in the low sublist is less than the
137		* lowest element in the high sublist).  This algorithm offers guaranteed
138	<	* n log(n) performance.
138	>	* n log(n) performance.
139		*
140		* The specified list must be modifiable, but need not be resizable.
141		* This implementation dumps the specified list into an array, sorts
#	Line 182 | Line 182 | public class Collections {
182		*
183		* @param  list the list to be searched.
184		* @param  key the key to be searched for.
185	<	* @return index of the search key, if it is contained in the list;
185	>	* @return the index of the search key, if it is contained in the list;
186		*         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
187		*         <i>insertion point</i> is defined as the point at which the
188		*         key would be inserted into the list: the index of the first
#	Line 287 | Line 287 | public class Collections {
287		* @param  c the comparator by which the list is ordered.  A
288		*        <tt>null</tt> value indicates that the elements' <i>natural
289		*        ordering</i> should be used.
290	<	* @return index of the search key, if it is contained in the list;
290	>	* @return the index of the search key, if it is contained in the list;
291		*         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
292		*         <i>insertion point</i> is defined as the point at which the
293		*         key would be inserted into the list: the index of the first
#	Line 361 | Line 361 | public class Collections {
361		*
362		* @param  list the list whose elements are to be reversed.
363		* @throws UnsupportedOperationException if the specified list or
364	<	*         its list-iterator does not support the <tt>set</tt> method.
364	>	*         its list-iterator does not support the <tt>set</tt> operation.
365		*/
366		public static void reverse(List<?> list) {
367		int size = list.size();
#	Line 405 | Line 405 | public class Collections {
405		*
406		* @param  list the list to be shuffled.
407		* @throws UnsupportedOperationException if the specified list or
408	<	*         its list-iterator does not support the <tt>set</tt> method.
408	>	*         its list-iterator does not support the <tt>set</tt> operation.
409		*/
410		public static void shuffle(List<?> list) {
411	+	if (r == null) {
412	+	r = new Random();
413	+	}
414		shuffle(list, r);
415		}
416	<	private static Random r = new Random();
416	>	private static Random r;
417
418		/**
419		* Randomly permute the specified list using the specified source of
#	Line 569 | Line 572 | public class Collections {
572		Iterator<? extends T> i = coll.iterator();
573		T candidate = i.next();
574
575	<	while(i.hasNext()) {
575	>	while (i.hasNext()) {
576		T next = i.next();
577		if (next.compareTo(candidate) < 0)
578		candidate = next;
#	Line 606 | Line 609 | public class Collections {
609		Iterator<? extends T> i = coll.iterator();
610		T candidate = i.next();
611
612	<	while(i.hasNext()) {
612	>	while (i.hasNext()) {
613		T next = i.next();
614		if (comp.compare(next, candidate) < 0)
615		candidate = next;
#	Line 639 | Line 642 | public class Collections {
642		Iterator<? extends T> i = coll.iterator();
643		T candidate = i.next();
644
645	<	while(i.hasNext()) {
645	>	while (i.hasNext()) {
646		T next = i.next();
647		if (next.compareTo(candidate) > 0)
648		candidate = next;
#	Line 676 | Line 679 | public class Collections {
679		Iterator<? extends T> i = coll.iterator();
680		T candidate = i.next();
681
682	<	while(i.hasNext()) {
682	>	while (i.hasNext()) {
683		T next = i.next();
684		if (comp.compare(next, candidate) > 0)
685		candidate = next;
#	Line 712 | Line 715 | public class Collections {
715		*     Collections.rotate(l.subList(1, 4), -1);
716		* </pre>
717		* The resulting list is <tt>[a, c, d, b, e]</tt>.
718	<	*
718	>	*
719		* <p>To move more than one element forward, increase the absolute value
720		* of the rotation distance.  To move elements backward, use a positive
721		* shift distance.
#	Line 736 | Line 739 | public class Collections {
739		*        constraints on this value; it may be zero, negative, or
740		*        greater than <tt>list.size()</tt>.
741		* @throws UnsupportedOperationException if the specified list or
742	<	*         its list-iterator does not support the <tt>set</tt> method.
742	>	*         its list-iterator does not support the <tt>set</tt> operation.
743		* @since 1.4
744		*/
745		public static void rotate(List<?> list, int distance) {
#	Line 772 | Line 775 | public class Collections {
775		private static void rotate2(List<?> list, int distance) {
776		int size = list.size();
777		if (size == 0)
778	<	return;
778	>	return;
779		int mid =  -distance % size;
780		if (mid < 0)
781		mid += size;
#	Line 799 | Line 802 | public class Collections {
802		*         <tt>e</tt> such that
803		*         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
804		* @throws UnsupportedOperationException if the specified list or
805	<	*         its list-iterator does not support the <tt>set</tt> method.
805	>	*         its list-iterator does not support the <tt>set</tt> operation.
806		* @since  1.4
807		*/
808		public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
#	Line 970 | Line 973 | public class Collections {
973		* that the backing collection is a set or a list.<p>
974		*
975		* The returned collection will be serializable if the specified collection
976	<	* is serializable.
976	>	* is serializable.
977		*
978		* @param  c the collection for which an unmodifiable view is to be
979		*         returned.
#	Line 1014 | Line 1017 | public class Collections {
1017		};
1018		}
1019
1020	<	public boolean add(E o){
1020	>	public boolean add(E e){
1021		throw new UnsupportedOperationException();
1022		}
1023		public boolean remove(Object o) {
#	Line 1046 | Line 1049 | public class Collections {
1049		* iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1050		*
1051		* The returned set will be serializable if the specified set
1052	<	* is serializable.
1052	>	* is serializable.
1053		*
1054		* @param  s the set for which an unmodifiable view is to be returned.
1055		* @return an unmodifiable view of the specified set.
1056		*/
1054	–
1057		public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1058		return new UnmodifiableSet<T>(s);
1059		}
#	Line 1078 | Line 1080 | public class Collections {
1080		* an <tt>UnsupportedOperationException</tt>.<p>
1081		*
1082		* The returned sorted set will be serializable if the specified sorted set
1083	<	* is serializable.
1083	>	* is serializable.
1084		*
1085		* @param s the sorted set for which an unmodifiable view is to be
1086	<	*        returned.
1086	>	*        returned.
1087		* @return an unmodifiable view of the specified sorted set.
1088		*/
1089		public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
#	Line 1183 | Line 1185 | public class Collections {
1185		public void remove() {
1186		throw new UnsupportedOperationException();
1187		}
1188	<	public void set(E o) {
1188	>	public void set(E e) {
1189		throw new UnsupportedOperationException();
1190		}
1191	<	public void add(E o) {
1191	>	public void add(E e) {
1192		throw new UnsupportedOperationException();
1193		}
1194		};
#	Line 1252 | Line 1254 | public class Collections {
1254		* <tt>UnsupportedOperationException</tt>.<p>
1255		*
1256		* The returned map will be serializable if the specified map
1257	<	* is serializable.
1257	>	* is serializable.
1258		*
1259		* @param  m the map for which an unmodifiable view is to be returned.
1260		* @return an unmodifiable view of the specified map.
#	Line 1334 | Line 1336 | public class Collections {
1336		private static final long serialVersionUID = 7854390611657943733L;
1337
1338		UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1339	<	super((Set<Map.Entry<K,V>>)(Set)s);
1339	>	super((Set)s);
1340		}
1341		public Iterator<Map.Entry<K,V>> iterator() {
1342		return new Iterator<Map.Entry<K,V>>() {
#	Line 1456 | Line 1458 | public class Collections {
1458		* an <tt>UnsupportedOperationException</tt>.<p>
1459		*
1460		* The returned sorted map will be serializable if the specified sorted map
1461	<	* is serializable.
1461	>	* is serializable.
1462		*
1463		* @param m the sorted map for which an unmodifiable view is to be
1464	<	*        returned.
1464	>	*        returned.
1465		* @return an unmodifiable view of the specified sorted map.
1466		*/
1467		public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
#	Line 1523 | Line 1525 | public class Collections {
1525		* that the backing collection is a set or a list.<p>
1526		*
1527		* The returned collection will be serializable if the specified collection
1528	<	* is serializable.
1528	>	* is serializable.
1529		*
1530		* @param  c the collection to be "wrapped" in a synchronized collection.
1531		* @return a synchronized view of the specified collection.
#	Line 1577 | Line 1579 | public class Collections {
1579		return c.iterator(); // Must be manually synched by user!
1580		}
1581
1582	<	public boolean add(E o) {
1583	<	synchronized(mutex) {return c.add(o);}
1582	>	public boolean add(E e) {
1583	>	synchronized(mutex) {return c.add(e);}
1584		}
1585		public boolean remove(Object o) {
1586		synchronized(mutex) {return c.remove(o);}
#	Line 1673 | Line 1675 | public class Collections {
1675		* sorted set when iterating over it or any of its <tt>subSet</tt>,
1676		* <tt>headSet</tt>, or <tt>tailSet</tt> views.
1677		* <pre>
1678	<	*  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1678	>	*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1679		*      ...
1680		*  synchronized(s) {
1681		*      Iterator i = s.iterator(); // Must be in the synchronized block
#	Line 1683 | Line 1685 | public class Collections {
1685		* </pre>
1686		* or:
1687		* <pre>
1688	<	*  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1688	>	*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1689		*  SortedSet s2 = s.headSet(foo);
1690		*      ...
1691		*  synchronized(s) {  // Note: s, not s2!!!
#	Line 2007 | Line 2009 | public class Collections {
2009		public Set<Map.Entry<K,V>> entrySet() {
2010		synchronized(mutex) {
2011		if (entrySet==null)
2012	<	entrySet = new SynchronizedSet<Map.Entry<K,V>>((Set<Map.Entry<K,V>>)m.entrySet(), mutex);
2012	>	entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2013		return entrySet;
2014		}
2015		}
#	Line 2045 | Line 2047 | public class Collections {
2047		* collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2048		* <tt>tailMap</tt> views.
2049		* <pre>
2050	<	*  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2050	>	*  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2051		*      ...
2052		*  Set s = m.keySet();  // Needn't be in synchronized block
2053		*      ...
#	Line 2057 | Line 2059 | public class Collections {
2059		* </pre>
2060		* or:
2061		* <pre>
2062	<	*  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2062	>	*  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2063		*  SortedMap m2 = m.subMap(foo, bar);
2064		*      ...
2065		*  Set s2 = m2.keySet();  // Needn't be in synchronized block
#	Line 2191 | Line 2193 | public class Collections {
2193		Class<E> type) {
2194		return new CheckedCollection<E>(c, type);
2195		}
2196	<
2196	>
2197		/**
2198		* @serial include
2199		*/
#	Line 2236 | Line 2238 | public class Collections {
2238		c.clear();
2239		}
2240
2241	<	public boolean add(E o){
2242	<	typeCheck(o);
2243	<	return c.add(o);
2241	>	public boolean add(E e){
2242	>	typeCheck(e);
2243	>	return c.add(e);
2244		}
2245
2246		public boolean addAll(Collection<? extends E> coll) {
#	Line 2246 | Line 2248 | public class Collections {
2248		* Dump coll into an array of the required type.  This serves
2249		* three purposes: it insulates us from concurrent changes in
2250		* the contents of coll, it type-checks all of the elements in
2251	<	* coll, and it provides all-or-nothing semantics(which we
2251	>	* coll, and it provides all-or-nothing semantics (which we
2252		* wouldn't get if we type-checked each element as we added it).
2253		*/
2254		E[] a = null;
2255		try {
2256		a = coll.toArray(zeroLengthElementArray());
2257	<	} catch(ArrayStoreException e) {
2257	>	} catch (ArrayStoreException e) {
2258		throw new ClassCastException();
2259		}
2260
#	Line 2265 | Line 2267 | public class Collections {
2267		private E[] zeroLengthElementArray = null; // Lazily initialized
2268
2269		/*
2270	<	* We don't need locking or volatile, because it's OK if we create
2270	>	* We don't need locking or volatile, because it's OK if we create
2271		* several zeroLengthElementArrays, and they're immutable.
2272		*/
2273		E[] zeroLengthElementArray() {
#	Line 2300 | Line 2302 | public class Collections {
2302		public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2303		return new CheckedSet<E>(s, type);
2304		}
2305	<
2305	>
2306		/**
2307		* @serial include
2308		*/
#	Line 2436 | Line 2438 | public class Collections {
2438		E[] a = null;
2439		try {
2440		a = c.toArray(zeroLengthElementArray());
2441	<	} catch(ArrayStoreException e) {
2441	>	} catch (ArrayStoreException e) {
2442		throw new ClassCastException();
2443		}
2444
#	Line 2456 | Line 2458 | public class Collections {
2458		public int previousIndex()   { return i.previousIndex(); }
2459		public void remove()         { i.remove(); }
2460
2461	<	public void set(E o) {
2462	<	typeCheck(o);
2463	<	i.set(o);
2461	>	public void set(E e) {
2462	>	typeCheck(e);
2463	>	i.set(e);
2464		}
2465
2466	<	public void add(E o) {
2467	<	typeCheck(o);
2468	<	i.add(o);
2466	>	public void add(E e) {
2467	>	typeCheck(e);
2468	>	i.add(e);
2469		}
2470		};
2471		}
#	Line 2582 | Line 2584 | public class Collections {
2584		K[] keys = null;
2585		try {
2586		keys = t.keySet().toArray(zeroLengthKeyArray());
2587	<	} catch(ArrayStoreException e) {
2587	>	} catch (ArrayStoreException e) {
2588		throw new ClassCastException();
2589		}
2590		V[] values = null;
2591		try {
2592		values = t.values().toArray(zeroLengthValueArray());
2593	<	} catch(ArrayStoreException e) {
2593	>	} catch (ArrayStoreException e) {
2594		throw new ClassCastException();
2595		}
2596
#	Line 2604 | Line 2606 | public class Collections {
2606		private V[] zeroLengthValueArray = null;
2607
2608		/*
2609	<	* We don't need locking or volatile, because it's OK if we create
2609	>	* We don't need locking or volatile, because it's OK if we create
2610		* several zeroLengthValueArrays, and they're immutable.
2611		*/
2612		private K[] zeroLengthKeyArray() {
#	Line 2658 | Line 2660 | public class Collections {
2660		s.clear();
2661		}
2662
2663	<	public boolean add(Map.Entry<K, V> o){
2663	>	public boolean add(Map.Entry<K, V> e){
2664		throw new UnsupportedOperationException();
2665		}
2666		public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
#	Line 3060 | Line 3062 | public class Collections {
3062
3063		final private E element;
3064
3065	<	SingletonSet(E o) {element = o;}
3065	>	SingletonSet(E e) {element = e;}
3066
3067		public Iterator<E> iterator() {
3068		return new Iterator<E>() {
#	Line 3168 | Line 3170 | public class Collections {
3170
3171		public Set<Map.Entry<K,V>> entrySet() {
3172		if (entrySet==null)
3173	<	entrySet = singleton((Map.Entry<K,V>)new ImmutableEntry<K,V>(k, v));
3173	>	entrySet = Collections.<Map.Entry<K,V>>singleton(
3174	>	new SimpleImmutableEntry<K,V>(k, v));
3175		return entrySet;
3176		}
3177
#	Line 3178 | Line 3181 | public class Collections {
3181		return values;
3182		}
3183
3181	–	private static class ImmutableEntry<K,V>
3182	–	implements Map.Entry<K,V> {
3183	–	final K k;
3184	–	final V v;
3185	–
3186	–	ImmutableEntry(K key, V value) {
3187	–	k = key;
3188	–	v = value;
3189	–	}
3190	–
3191	–	public K getKey()   {return k;}
3192	–
3193	–	public V getValue() {return v;}
3194	–
3195	–	public V setValue(V value) {
3196	–	throw new UnsupportedOperationException();
3197	–	}
3198	–
3199	–	public boolean equals(Object o) {
3200	–	if (!(o instanceof Map.Entry))
3201	–	return false;
3202	–	Map.Entry e = (Map.Entry)o;
3203	–	return eq(e.getKey(), k) && eq(e.getValue(), v);
3204	–	}
3205	–
3206	–	public int hashCode() {
3207	–	return ((k==null ? 0 : k.hashCode()) ^
3208	–	(v==null ? 0 : v.hashCode()));
3209	–	}
3210	–
3211	–	public String toString() {
3212	–	return k+"="+v;
3213	–	}
3214	–	}
3184		}
3185
3186		/**
#	Line 3245 | Line 3214 | public class Collections {
3214		int n;
3215		E element;
3216
3217	<	CopiesList(int n, E o) {
3217	>	CopiesList(int n, E e) {
3218		if (n < 0)
3219		throw new IllegalArgumentException("List length = " + n);
3220		this.n = n;
3221	<	element = o;
3221	>	element = e;
3222		}
3223
3224		public int size() {
#	Line 3324 | Line 3293 | public class Collections {
3293		public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3294		if (cmp == null)
3295		return new ReverseComparator();  // Unchecked warning!!
3296	<
3296	>
3297		return new ReverseComparator2<T>(cmp);
3298		}
3299	<
3299	>
3300		/**
3301		* @serial include
3302		*/
#	Line 3335 | Line 3304 | public class Collections {
3304		Serializable
3305		{
3306		private static final long serialVersionUID = 4374092139857L;
3307	<
3307	>
3308		/**
3309		* The comparator specified in the static factory.  This will never
3310		* be null, as the static factory returns a ReverseComparator
#	Line 3344 | Line 3313 | public class Collections {
3313		* @serial
3314		*/
3315		private Comparator<T> cmp;
3316	<
3316	>
3317		ReverseComparator2(Comparator<T> cmp) {
3318		assert cmp != null;
3319		this.cmp = cmp;
3320		}
3321	<
3321	>
3322		public int compare(T t1, T t2) {
3323		return cmp.compare(t2, t1);
3324		}
#	Line 3469 | Line 3438 | public class Collections {
3438		c1 = c2;
3439		c2 = tmp;
3440		}
3441	<
3441	>
3442		for (Object e : c1)
3443		if (c2.contains(e))
3444		return false;
#	Line 3493 | Line 3462 | public class Collections {
3462		* @param a the elements to insert into <tt>c</tt>
3463		* @return <tt>true</tt> if the collection changed as a result of the call
3464		* @throws UnsupportedOperationException if <tt>c</tt> does not support
3465	<	*         the <tt>add</tt> method
3465	>	*         the <tt>add</tt> operation.
3466		* @throws NullPointerException if <tt>elements</tt> contains one or more
3467	<	*         null values and <tt>c</tt> does not support null elements, or
3467	>	*         null values and <tt>c</tt> does not permit null elements, or
3468		*         if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
3469	<	* @throws IllegalArgumentException if some aspect of a value in
3469	>	* @throws IllegalArgumentException if some property of a value in
3470		*         <tt>elements</tt> prevents it from being added to <tt>c</tt>
3471		* @see Collection#addAll(Collection)
3472		* @since 1.5
#	Line 3599 | Line 3568 | public class Collections {
3568		return new AsLIFOQueue<T>(deque);
3569		}
3570
3571	<	static class AsLIFOQueue<E> extends AbstractQueue<E>
3571	>	static class AsLIFOQueue<E> extends AbstractQueue<E>
3572		implements Queue<E>, Serializable {
3573	+	private static final long serialVersionUID = 1802017725587941708L;
3574		private final Deque<E> q;
3575		AsLIFOQueue(Deque<E> q)            { this.q = q; }
3576	<	public boolean offer(E o)          { return q.offerFirst(o); }
3576	>	public boolean offer(E e)          { return q.offerFirst(e); }
3577		public E poll()                    { return q.pollFirst(); }
3578		public E remove()                  { return q.removeFirst(); }
3579		public E peek()                    { return q.peekFirst(); }
#	Line 3614 | Line 3584 | public class Collections {
3584		public Iterator<E> iterator()      { return q.iterator(); }
3585		public Object[] toArray()          { return q.toArray(); }
3586		public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3587	<	public boolean add(E o)            { return q.offerFirst(o); }
3587	>	public boolean add(E e)            { return q.offerFirst(e); }
3588		public boolean remove(Object o)    { return q.remove(o); }
3589		public void clear()                { q.clear(); }
3590		}

Diff Legend

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