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.31 by jsr166, Sun May 20 07:54:01 2007 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
#	Line 37 | Line 55 | import java.lang.reflect.Array;
55		* example, invoking the <tt>sort</tt> method on an unmodifiable list that is
56		* already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
57		*
58	<	* <p>This class is a member of the
59	<	* <a href="{@docRoot}/../guide/collections/index.html">
58	>	* <p>This class is a member of the
59	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
60		* Java Collections Framework</a>.
61		*
62		* @author  Josh Bloch
#	Line 63 | Line 81 | public class Collections {
81		* two implementations, one of which is appropriate for RandomAccess
82		* lists, the other for "sequential."  Often, the random access variant
83		* yields better performance on small sequential access lists.  The
84	<	* tuning  parameters below determine the cutoff point for what constitutes
84	>	* tuning parameters below determine the cutoff point for what constitutes
85		* a "small" sequential access list for each algorithm.  The values below
86		* were empirically determined to work well for LinkedList. Hopefully
87		* they should be reasonable for other sequential access List
#	Line 97 | Line 115 | public class Collections {
115		* The sorting algorithm is a modified mergesort (in which the merge is
116		* omitted if the highest element in the low sublist is less than the
117		* lowest element in the high sublist).  This algorithm offers guaranteed
118	<	* n log(n) performance.
118	>	* n log(n) performance.
119		*
120		* This implementation dumps the specified list into an array, sorts
121		* the array, and iterates over the list resetting each element
#	Line 135 | Line 153 | public class Collections {
153		* The sorting algorithm is a modified mergesort (in which the merge is
154		* omitted if the highest element in the low sublist is less than the
155		* lowest element in the high sublist).  This algorithm offers guaranteed
156	<	* n log(n) performance.
156	>	* n log(n) performance.
157		*
158		* The specified list must be modifiable, but need not be resizable.
159		* This implementation dumps the specified list into an array, sorts
#	Line 168 | Line 186 | public class Collections {
186		/**
187		* Searches the specified list for the specified object using the binary
188		* search algorithm.  The list must be sorted into ascending order
189	<	* according to the <i>natural ordering</i> of its elements (as by the
190	<	* <tt>sort(List)</tt> method, above) prior to making this call.  If it is
191	<	* not sorted, the results are undefined.  If the list contains multiple
192	<	* elements equal to the specified object, there is no guarantee which one
193	<	* will be found.<p>
189	>	* according to the {@linkplain Comparable natural ordering} of its
190	>	* elements (as by the {@link #sort(List)} method) prior to making this
191	>	* call.  If it is not sorted, the results are undefined.  If the list
192	>	* contains multiple elements equal to the specified object, there is no
193	>	* guarantee which one will be found.
194		*
195	<	* This method runs in log(n) time for a "random access" list (which
195	>	* <p>This method runs in log(n) time for a "random access" list (which
196		* provides near-constant-time positional access).  If the specified list
197		* does not implement the {@link RandomAccess} interface and is large,
198		* this method will do an iterator-based binary search that performs
#	Line 182 | Line 200 | public class Collections {
200		*
201		* @param  list the list to be searched.
202		* @param  key the key to be searched for.
203	<	* @return index of the search key, if it is contained in the list;
203	>	* @return the index of the search key, if it is contained in the list;
204		*         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
205		*         <i>insertion point</i> is defined as the point at which the
206		*         key would be inserted into the list: the index of the first
207	<	*         element greater than the key, or <tt>list.size()</tt>, if all
207	>	*         element greater than the key, or <tt>list.size()</tt> if all
208		*         elements in the list are less than the specified key.  Note
209		*         that this guarantees that the return value will be &gt;= 0 if
210		*         and only if the key is found.
211		* @throws ClassCastException if the list contains elements that are not
212		*         <i>mutually comparable</i> (for example, strings and
213	<	*         integers), or the search key in not mutually comparable
213	>	*         integers), or the search key is not mutually comparable
214		*         with the elements of the list.
197	–	* @see    Comparable
198	–	* @see #sort(List)
215		*/
216		public static <T>
217		int binarySearch(List<? extends Comparable<? super T>> list, T key) {
#	Line 212 | Line 228 | public class Collections {
228		int high = list.size()-1;
229
230		while (low <= high) {
231	<	int mid = (low + high) >> 1;
231	>	int mid = (low + high) >>> 1;
232		Comparable<? super T> midVal = list.get(mid);
233		int cmp = midVal.compareTo(key);
234
#	Line 234 | Line 250 | public class Collections {
250		ListIterator<? extends Comparable<? super T>> i = list.listIterator();
251
252		while (low <= high) {
253	<	int mid = (low + high) >> 1;
253	>	int mid = (low + high) >>> 1;
254		Comparable<? super T> midVal = get(i, mid);
255		int cmp = midVal.compareTo(key);
256
#	Line 270 | Line 286 | public class Collections {
286		/**
287		* Searches the specified list for the specified object using the binary
288		* search algorithm.  The list must be sorted into ascending order
289	<	* according to the specified comparator (as by the <tt>Sort(List,
290	<	* Comparator)</tt> method, above), prior to making this call.  If it is
289	>	* according to the specified comparator (as by the
290	>	* {@link #sort(List, Comparator) sort(List, Comparator)}
291	>	* method), prior to making this call.  If it is
292		* not sorted, the results are undefined.  If the list contains multiple
293		* elements equal to the specified object, there is no guarantee which one
294	<	* will be found.<p>
294	>	* will be found.
295		*
296	<	* This method runs in log(n) time for a "random access" list (which
296	>	* <p>This method runs in log(n) time for a "random access" list (which
297		* provides near-constant-time positional access).  If the specified list
298		* does not implement the {@link RandomAccess} interface and is large,
299		* this method will do an iterator-based binary search that performs
#	Line 284 | Line 301 | public class Collections {
301		*
302		* @param  list the list to be searched.
303		* @param  key the key to be searched for.
304	<	* @param  c the comparator by which the list is ordered.  A
305	<	*        <tt>null</tt> value indicates that the elements' <i>natural
306	<	*        ordering</i> should be used.
307	<	* @return index of the search key, if it is contained in the list;
304	>	* @param  c the comparator by which the list is ordered.
305	>	*         A <tt>null</tt> value indicates that the elements'
306	>	*         {@linkplain Comparable natural ordering} should be used.
307	>	* @return the index of the search key, if it is contained in the list;
308		*         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
309		*         <i>insertion point</i> is defined as the point at which the
310		*         key would be inserted into the list: the index of the first
311	<	*         element greater than the key, or <tt>list.size()</tt>, if all
311	>	*         element greater than the key, or <tt>list.size()</tt> if all
312		*         elements in the list are less than the specified key.  Note
313		*         that this guarantees that the return value will be &gt;= 0 if
314		*         and only if the key is found.
315		* @throws ClassCastException if the list contains elements that are not
316		*         <i>mutually comparable</i> using the specified comparator,
317	<	*         or the search key in not mutually comparable with the
317	>	*         or the search key is not mutually comparable with the
318		*         elements of the list using this comparator.
302	–	* @see    Comparable
303	–	* @see #sort(List, Comparator)
319		*/
320		public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
321		if (c==null)
#	Line 317 | Line 332 | public class Collections {
332		int high = l.size()-1;
333
334		while (low <= high) {
335	<	int mid = (low + high) >> 1;
335	>	int mid = (low + high) >>> 1;
336		T midVal = l.get(mid);
337		int cmp = c.compare(midVal, key);
338
#	Line 337 | Line 352 | public class Collections {
352		ListIterator<? extends T> i = l.listIterator();
353
354		while (low <= high) {
355	<	int mid = (low + high) >> 1;
355	>	int mid = (low + high) >>> 1;
356		T midVal = get(i, mid);
357		int cmp = c.compare(midVal, key);
358
#	Line 361 | Line 376 | public class Collections {
376		*
377		* @param  list the list whose elements are to be reversed.
378		* @throws UnsupportedOperationException if the specified list or
379	<	*         its list-iterator does not support the <tt>set</tt> method.
379	>	*         its list-iterator does not support the <tt>set</tt> operation.
380		*/
381		public static void reverse(List<?> list) {
382		int size = list.size();
#	Line 405 | Line 420 | public class Collections {
420		*
421		* @param  list the list to be shuffled.
422		* @throws UnsupportedOperationException if the specified list or
423	<	*         its list-iterator does not support the <tt>set</tt> method.
423	>	*         its list-iterator does not support the <tt>set</tt> operation.
424		*/
425		public static void shuffle(List<?> list) {
426	+	if (r == null) {
427	+	r = new Random();
428	+	}
429		shuffle(list, r);
430		}
431	<	private static Random r = new Random();
431	>	private static Random r;
432
433		/**
434		* Randomly permute the specified list using the specified source of
#	Line 569 | Line 587 | public class Collections {
587		Iterator<? extends T> i = coll.iterator();
588		T candidate = i.next();
589
590	<	while(i.hasNext()) {
590	>	while (i.hasNext()) {
591		T next = i.next();
592		if (next.compareTo(candidate) < 0)
593		candidate = next;
#	Line 606 | Line 624 | public class Collections {
624		Iterator<? extends T> i = coll.iterator();
625		T candidate = i.next();
626
627	<	while(i.hasNext()) {
627	>	while (i.hasNext()) {
628		T next = i.next();
629		if (comp.compare(next, candidate) < 0)
630		candidate = next;
#	Line 639 | Line 657 | public class Collections {
657		Iterator<? extends T> i = coll.iterator();
658		T candidate = i.next();
659
660	<	while(i.hasNext()) {
660	>	while (i.hasNext()) {
661		T next = i.next();
662		if (next.compareTo(candidate) > 0)
663		candidate = next;
#	Line 676 | Line 694 | public class Collections {
694		Iterator<? extends T> i = coll.iterator();
695		T candidate = i.next();
696
697	<	while(i.hasNext()) {
697	>	while (i.hasNext()) {
698		T next = i.next();
699		if (comp.compare(next, candidate) > 0)
700		candidate = next;
#	Line 712 | Line 730 | public class Collections {
730		*     Collections.rotate(l.subList(1, 4), -1);
731		* </pre>
732		* The resulting list is <tt>[a, c, d, b, e]</tt>.
733	<	*
733	>	*
734		* <p>To move more than one element forward, increase the absolute value
735		* of the rotation distance.  To move elements backward, use a positive
736		* shift distance.
#	Line 736 | Line 754 | public class Collections {
754		*        constraints on this value; it may be zero, negative, or
755		*        greater than <tt>list.size()</tt>.
756		* @throws UnsupportedOperationException if the specified list or
757	<	*         its list-iterator does not support the <tt>set</tt> method.
757	>	*         its list-iterator does not support the <tt>set</tt> operation.
758		* @since 1.4
759		*/
760		public static void rotate(List<?> list, int distance) {
#	Line 772 | Line 790 | public class Collections {
790		private static void rotate2(List<?> list, int distance) {
791		int size = list.size();
792		if (size == 0)
793	<	return;
793	>	return;
794		int mid =  -distance % size;
795		if (mid < 0)
796		mid += size;
#	Line 799 | Line 817 | public class Collections {
817		*         <tt>e</tt> such that
818		*         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
819		* @throws UnsupportedOperationException if the specified list or
820	<	*         its list-iterator does not support the <tt>set</tt> method.
820	>	*         its list-iterator does not support the <tt>set</tt> operation.
821		* @since  1.4
822		*/
823		public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
#	Line 970 | Line 988 | public class Collections {
988		* that the backing collection is a set or a list.<p>
989		*
990		* The returned collection will be serializable if the specified collection
991	<	* is serializable.
991	>	* is serializable.
992		*
993		* @param  c the collection for which an unmodifiable view is to be
994		*         returned.
#	Line 1014 | Line 1032 | public class Collections {
1032		};
1033		}
1034
1035	<	public boolean add(E o){
1035	>	public boolean add(E e){
1036		throw new UnsupportedOperationException();
1037		}
1038		public boolean remove(Object o) {
#	Line 1046 | Line 1064 | public class Collections {
1064		* iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1065		*
1066		* The returned set will be serializable if the specified set
1067	<	* is serializable.
1067	>	* is serializable.
1068		*
1069		* @param  s the set for which an unmodifiable view is to be returned.
1070		* @return an unmodifiable view of the specified set.
1071		*/
1054	–
1072		public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1073		return new UnmodifiableSet<T>(s);
1074		}
#	Line 1064 | Line 1081 | public class Collections {
1081		private static final long serialVersionUID = -9215047833775013803L;
1082
1083		UnmodifiableSet(Set<? extends E> s)     {super(s);}
1084	<	public boolean equals(Object o) {return c.equals(o);}
1084	>	public boolean equals(Object o) {return o == this || c.equals(o);}
1085		public int hashCode()           {return c.hashCode();}
1086		}
1087
#	Line 1078 | Line 1095 | public class Collections {
1095		* an <tt>UnsupportedOperationException</tt>.<p>
1096		*
1097		* The returned sorted set will be serializable if the specified sorted set
1098	<	* is serializable.
1098	>	* is serializable.
1099		*
1100		* @param s the sorted set for which an unmodifiable view is to be
1101	<	*        returned.
1101	>	*        returned.
1102		* @return an unmodifiable view of the specified sorted set.
1103		*/
1104		public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
#	Line 1149 | Line 1166 | public class Collections {
1166		this.list = list;
1167		}
1168
1169	<	public boolean equals(Object o) {return list.equals(o);}
1169	>	public boolean equals(Object o) {return o == this || list.equals(o);}
1170		public int hashCode()           {return list.hashCode();}
1171
1172		public E get(int index) {return list.get(index);}
#	Line 1183 | Line 1200 | public class Collections {
1200		public void remove() {
1201		throw new UnsupportedOperationException();
1202		}
1203	<	public void set(E o) {
1203	>	public void set(E e) {
1204		throw new UnsupportedOperationException();
1205		}
1206	<	public void add(E o) {
1206	>	public void add(E e) {
1207		throw new UnsupportedOperationException();
1208		}
1209		};
#	Line 1252 | Line 1269 | public class Collections {
1269		* <tt>UnsupportedOperationException</tt>.<p>
1270		*
1271		* The returned map will be serializable if the specified map
1272	<	* is serializable.
1272	>	* is serializable.
1273		*
1274		* @param  m the map for which an unmodifiable view is to be returned.
1275		* @return an unmodifiable view of the specified map.
#	Line 1288 | Line 1305 | public class Collections {
1305		public V remove(Object key) {
1306		throw new UnsupportedOperationException();
1307		}
1308	<	public void putAll(Map<? extends K, ? extends V> t) {
1308	>	public void putAll(Map<? extends K, ? extends V> m) {
1309		throw new UnsupportedOperationException();
1310		}
1311		public void clear() {
#	Line 1317 | Line 1334 | public class Collections {
1334		return values;
1335		}
1336
1337	<	public boolean equals(Object o) {return m.equals(o);}
1337	>	public boolean equals(Object o) {return o == this || m.equals(o);}
1338		public int hashCode()           {return m.hashCode();}
1339		public String toString()        {return m.toString();}
1340
#	Line 1334 | Line 1351 | public class Collections {
1351		private static final long serialVersionUID = 7854390611657943733L;
1352
1353		UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1354	<	super((Set<Map.Entry<K,V>>)(Set)s);
1354	>	super((Set)s);
1355		}
1356		public Iterator<Map.Entry<K,V>> iterator() {
1357		return new Iterator<Map.Entry<K,V>>() {
#	Line 1363 | Line 1380 | public class Collections {
1380		// We don't pass a to c.toArray, to avoid window of
1381		// vulnerability wherein an unscrupulous multithreaded client
1382		// could get his hands on raw (unwrapped) Entries from c.
1383	<	Object[] arr =
1367	<	c.toArray(
1368	<	a.length==0 ? a :
1369	<	(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), 0));
1383	>	Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1384
1385		for (int i=0; i<arr.length; i++)
1386		arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]);
#	Line 1456 | Line 1470 | public class Collections {
1470		* an <tt>UnsupportedOperationException</tt>.<p>
1471		*
1472		* The returned sorted map will be serializable if the specified sorted map
1473	<	* is serializable.
1473	>	* is serializable.
1474		*
1475		* @param m the sorted map for which an unmodifiable view is to be
1476	<	*        returned.
1476	>	*        returned.
1477		* @return an unmodifiable view of the specified sorted map.
1478		*/
1479		public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
#	Line 1523 | Line 1537 | public class Collections {
1537		* that the backing collection is a set or a list.<p>
1538		*
1539		* The returned collection will be serializable if the specified collection
1540	<	* is serializable.
1540	>	* is serializable.
1541		*
1542		* @param  c the collection to be "wrapped" in a synchronized collection.
1543		* @return a synchronized view of the specified collection.
#	Line 1543 | Line 1557 | public class Collections {
1557		// use serialVersionUID from JDK 1.2.2 for interoperability
1558		private static final long serialVersionUID = 3053995032091335093L;
1559
1560	<	final Collection<E> c;     // Backing Collection
1561	<	final Object       mutex;  // Object on which to synchronize
1560	>	final Collection<E> c;  // Backing Collection
1561	>	final Object mutex;     // Object on which to synchronize
1562
1563		SynchronizedCollection(Collection<E> c) {
1564		if (c==null)
#	Line 1577 | Line 1591 | public class Collections {
1591		return c.iterator(); // Must be manually synched by user!
1592		}
1593
1594	<	public boolean add(E o) {
1595	<	synchronized(mutex) {return c.add(o);}
1594	>	public boolean add(E e) {
1595	>	synchronized(mutex) {return c.add(e);}
1596		}
1597		public boolean remove(Object o) {
1598		synchronized(mutex) {return c.remove(o);}
#	Line 1673 | Line 1687 | public class Collections {
1687		* sorted set when iterating over it or any of its <tt>subSet</tt>,
1688		* <tt>headSet</tt>, or <tt>tailSet</tt> views.
1689		* <pre>
1690	<	*  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1690	>	*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1691		*      ...
1692		*  synchronized(s) {
1693		*      Iterator i = s.iterator(); // Must be in the synchronized block
#	Line 1683 | Line 1697 | public class Collections {
1697		* </pre>
1698		* or:
1699		* <pre>
1700	<	*  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1700	>	*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1701		*  SortedSet s2 = s.headSet(foo);
1702		*      ...
1703		*  synchronized(s) {  // Note: s, not s2!!!
#	Line 2007 | Line 2021 | public class Collections {
2021		public Set<Map.Entry<K,V>> entrySet() {
2022		synchronized(mutex) {
2023		if (entrySet==null)
2024	<	entrySet = new SynchronizedSet<Map.Entry<K,V>>((Set<Map.Entry<K,V>>)m.entrySet(), mutex);
2024	>	entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2025		return entrySet;
2026		}
2027		}
#	Line 2045 | Line 2059 | public class Collections {
2059		* collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2060		* <tt>tailMap</tt> views.
2061		* <pre>
2062	<	*  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2062	>	*  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2063		*      ...
2064		*  Set s = m.keySet();  // Needn't be in synchronized block
2065		*      ...
#	Line 2057 | Line 2071 | public class Collections {
2071		* </pre>
2072		* or:
2073		* <pre>
2074	<	*  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2074	>	*  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2075		*  SortedMap m2 = m.subMap(foo, bar);
2076		*      ...
2077		*  Set s2 = m2.keySet();  // Needn't be in synchronized block
#	Line 2191 | Line 2205 | public class Collections {
2205		Class<E> type) {
2206		return new CheckedCollection<E>(c, type);
2207		}
2208	<
2208	>
2209		/**
2210		* @serial include
2211		*/
#	Line 2221 | Line 2235 | public class Collections {
2235		public Object[] toArray()           { return c.toArray(); }
2236		public <T> T[] toArray(T[] a)       { return c.toArray(a); }
2237		public String toString()            { return c.toString(); }
2224	–	public Iterator<E> iterator()       { return c.iterator(); }
2238		public boolean remove(Object o)     { return c.remove(o); }
2239		public boolean containsAll(Collection<?> coll) {
2240		return c.containsAll(coll);
#	Line 2236 | Line 2249 | public class Collections {
2249		c.clear();
2250		}
2251
2252	<	public boolean add(E o){
2253	<	typeCheck(o);
2254	<	return c.add(o);
2252	>	public Iterator<E> iterator() {
2253	>	return new Iterator<E>() {
2254	>	private final Iterator<E> it = c.iterator();
2255	>	public boolean hasNext() { return it.hasNext(); }
2256	>	public E next()          { return it.next(); }
2257	>	public void remove()     {        it.remove(); }};
2258	>	}
2259	>
2260	>	public boolean add(E e){
2261	>	typeCheck(e);
2262	>	return c.add(e);
2263		}
2264
2265		public boolean addAll(Collection<? extends E> coll) {
#	Line 2246 | Line 2267 | public class Collections {
2267		* Dump coll into an array of the required type.  This serves
2268		* three purposes: it insulates us from concurrent changes in
2269		* the contents of coll, it type-checks all of the elements in
2270	<	* coll, and it provides all-or-nothing semantics(which we
2270	>	* coll, and it provides all-or-nothing semantics (which we
2271		* wouldn't get if we type-checked each element as we added it).
2272		*/
2273		E[] a = null;
2274		try {
2275		a = coll.toArray(zeroLengthElementArray());
2276	<	} catch(ArrayStoreException e) {
2276	>	} catch (ArrayStoreException e) {
2277		throw new ClassCastException();
2278		}
2279
#	Line 2265 | Line 2286 | public class Collections {
2286		private E[] zeroLengthElementArray = null; // Lazily initialized
2287
2288		/*
2289	<	* We don't need locking or volatile, because it's OK if we create
2289	>	* We don't need locking or volatile, because it's OK if we create
2290		* several zeroLengthElementArrays, and they're immutable.
2291		*/
2292		E[] zeroLengthElementArray() {
#	Line 2300 | Line 2321 | public class Collections {
2321		public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2322		return new CheckedSet<E>(s, type);
2323		}
2324	<
2324	>
2325		/**
2326		* @serial include
2327		*/
#	Line 2311 | Line 2332 | public class Collections {
2332
2333		CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2334
2335	<	public boolean equals(Object o) { return c.equals(o); }
2335	>	public boolean equals(Object o) { return o == this || c.equals(o); }
2336		public int hashCode()           { return c.hashCode(); }
2337		}
2338
#	Line 2414 | Line 2435 | public class Collections {
2435		this.list = list;
2436		}
2437
2438	<	public boolean equals(Object o)  { return list.equals(o); }
2438	>	public boolean equals(Object o)  { return o == this || list.equals(o); }
2439		public int hashCode()            { return list.hashCode(); }
2440		public E get(int index)          { return list.get(index); }
2441		public E remove(int index)       { return list.remove(index); }
#	Line 2436 | Line 2457 | public class Collections {
2457		E[] a = null;
2458		try {
2459		a = c.toArray(zeroLengthElementArray());
2460	<	} catch(ArrayStoreException e) {
2460	>	} catch (ArrayStoreException e) {
2461		throw new ClassCastException();
2462		}
2463
#	Line 2456 | Line 2477 | public class Collections {
2477		public int previousIndex()   { return i.previousIndex(); }
2478		public void remove()         { i.remove(); }
2479
2480	<	public void set(E o) {
2481	<	typeCheck(o);
2482	<	i.set(o);
2480	>	public void set(E e) {
2481	>	typeCheck(e);
2482	>	i.set(e);
2483		}
2484
2485	<	public void add(E o) {
2486	<	typeCheck(o);
2487	<	i.add(o);
2485	>	public void add(E e) {
2486	>	typeCheck(e);
2487	>	i.add(e);
2488		}
2489		};
2490		}
#	Line 2568 | Line 2589 | public class Collections {
2589		public void clear()                    { m.clear(); }
2590		public Set<K> keySet()                 { return m.keySet(); }
2591		public Collection<V> values()          { return m.values(); }
2592	<	public boolean equals(Object o)        { return m.equals(o);  }
2592	>	public boolean equals(Object o)        { return o == this || m.equals(o); }
2593		public int hashCode()                  { return m.hashCode(); }
2594		public String toString()               { return m.toString(); }
2595
#	Line 2582 | Line 2603 | public class Collections {
2603		K[] keys = null;
2604		try {
2605		keys = t.keySet().toArray(zeroLengthKeyArray());
2606	<	} catch(ArrayStoreException e) {
2606	>	} catch (ArrayStoreException e) {
2607		throw new ClassCastException();
2608		}
2609		V[] values = null;
2610		try {
2611		values = t.values().toArray(zeroLengthValueArray());
2612	<	} catch(ArrayStoreException e) {
2612	>	} catch (ArrayStoreException e) {
2613		throw new ClassCastException();
2614		}
2615
#	Line 2604 | Line 2625 | public class Collections {
2625		private V[] zeroLengthValueArray = null;
2626
2627		/*
2628	<	* We don't need locking or volatile, because it's OK if we create
2628	>	* We don't need locking or volatile, because it's OK if we create
2629		* several zeroLengthValueArrays, and they're immutable.
2630		*/
2631		private K[] zeroLengthKeyArray() {
#	Line 2658 | Line 2679 | public class Collections {
2679		s.clear();
2680		}
2681
2682	<	public boolean add(Map.Entry<K, V> o){
2682	>	public boolean add(Map.Entry<K, V> e){
2683		throw new UnsupportedOperationException();
2684		}
2685		public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
#	Line 2700 | Line 2721 | public class Collections {
2721		// We don't pass a to s.toArray, to avoid window of
2722		// vulnerability wherein an unscrupulous multithreaded client
2723		// could get his hands on raw (unwrapped) Entries from s.
2724	<	Object[] arr = s.toArray(a.length==0 ? a :
2704	<	(T[])Array.newInstance(a.getClass().getComponentType(), 0));
2724	>	Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2725
2726		for (int i=0; i<arr.length; i++)
2727		arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i],
#	Line 3060 | Line 3080 | public class Collections {
3080
3081		final private E element;
3082
3083	<	SingletonSet(E o) {element = o;}
3083	>	SingletonSet(E e) {element = e;}
3084
3085		public Iterator<E> iterator() {
3086		return new Iterator<E>() {
#	Line 3168 | Line 3188 | public class Collections {
3188
3189		public Set<Map.Entry<K,V>> entrySet() {
3190		if (entrySet==null)
3191	<	entrySet = singleton((Map.Entry<K,V>)new ImmutableEntry<K,V>(k, v));
3191	>	entrySet = Collections.<Map.Entry<K,V>>singleton(
3192	>	new SimpleImmutableEntry<K,V>(k, v));
3193		return entrySet;
3194		}
3195
#	Line 3178 | Line 3199 | public class Collections {
3199		return values;
3200		}
3201
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	–	}
3202		}
3203
3204		/**
#	Line 3230 | Line 3217 | public class Collections {
3217		* @see    List#addAll(int, Collection)
3218		*/
3219		public static <T> List<T> nCopies(int n, T o) {
3220	+	if (n < 0)
3221	+	throw new IllegalArgumentException("List length = " + n);
3222		return new CopiesList<T>(n, o);
3223		}
3224
#	Line 3242 | Line 3231 | public class Collections {
3231		{
3232		static final long serialVersionUID = 2739099268398711800L;
3233
3234	<	int n;
3235	<	E element;
3234	>	final int n;
3235	>	final E element;
3236
3237	<	CopiesList(int n, E o) {
3238	<	if (n < 0)
3250	<	throw new IllegalArgumentException("List length = " + n);
3237	>	CopiesList(int n, E e) {
3238	>	assert n >= 0;
3239		this.n = n;
3240	<	element = o;
3240	>	element = e;
3241		}
3242
3243		public int size() {
#	Line 3260 | Line 3248 | public class Collections {
3248		return n != 0 && eq(obj, element);
3249		}
3250
3251	+	public int indexOf(Object o) {
3252	+	return contains(o) ? 0 : -1;
3253	+	}
3254	+
3255	+	public int lastIndexOf(Object o) {
3256	+	return contains(o) ? n - 1 : -1;
3257	+	}
3258	+
3259		public E get(int index) {
3260	<	if (index<0 || index>=n)
3260	>	if (index < 0 || index >= n)
3261		throw new IndexOutOfBoundsException("Index: "+index+
3262		", Size: "+n);
3263		return element;
3264		}
3265	+
3266	+	public Object[] toArray() {
3267	+	final Object[] a = new Object[n];
3268	+	if (element != null)
3269	+	Arrays.fill(a, 0, n, element);
3270	+	return a;
3271	+	}
3272	+
3273	+	public <T> T[] toArray(T[] a) {
3274	+	final int n = this.n;
3275	+	if (a.length < n) {
3276	+	a = (T[])java.lang.reflect.Array
3277	+	.newInstance(a.getClass().getComponentType(), n);
3278	+	if (element != null)
3279	+	Arrays.fill(a, 0, n, element);
3280	+	} else {
3281	+	Arrays.fill(a, 0, n, element);
3282	+	if (a.length > n)
3283	+	a[n] = null;
3284	+	}
3285	+	return a;
3286	+	}
3287	+
3288	+	public List<E> subList(int fromIndex, int toIndex) {
3289	+	if (fromIndex < 0)
3290	+	throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3291	+	if (toIndex > n)
3292	+	throw new IndexOutOfBoundsException("toIndex = " + toIndex);
3293	+	if (fromIndex > toIndex)
3294	+	throw new IllegalArgumentException("fromIndex(" + fromIndex +
3295	+	") > toIndex(" + toIndex + ")");
3296	+	return new CopiesList(toIndex - fromIndex, element);
3297	+	}
3298		}
3299
3300		/**
#	Line 3288 | Line 3317 | public class Collections {
3317		* @see Comparable
3318		*/
3319		public static <T> Comparator<T> reverseOrder() {
3320	<	return (Comparator<T>) REVERSE_ORDER;
3320	>	return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3321		}
3322
3294	–	private static final Comparator REVERSE_ORDER = new ReverseComparator();
3295	–
3323		/**
3324		* @serial include
3325		*/
3326	<	private static class ReverseComparator<T>
3326	>	private static class ReverseComparator
3327		implements Comparator<Comparable<Object>>, Serializable {
3328
3329		// use serialVersionUID from JDK 1.2.2 for interoperability
3330		private static final long serialVersionUID = 7207038068494060240L;
3331
3332	+	private static final ReverseComparator REVERSE_ORDER
3333	+	= new ReverseComparator();
3334	+
3335		public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3336		return c2.compareTo(c1);
3337		}
3338	+
3339	+	private Object readResolve() { return reverseOrder(); }
3340		}
3341
3342		/**
#	Line 3318 | Line 3350 | public class Collections {
3350		* comparator is also serializable or null).
3351		*
3352		* @return a comparator that imposes the reverse ordering of the
3353	<	*     specified comparator.
3353	>	*         specified comparator
3354		* @since 1.5
3355		*/
3356		public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3357		if (cmp == null)
3358	<	return new ReverseComparator();  // Unchecked warning!!
3359	<
3358	>	return reverseOrder();
3359	>
3360	>	if (cmp instanceof ReverseComparator2)
3361	>	return ((ReverseComparator2<T>)cmp).cmp;
3362	>
3363		return new ReverseComparator2<T>(cmp);
3364		}
3365	<
3365	>
3366		/**
3367		* @serial include
3368		*/
#	Line 3335 | Line 3370 | public class Collections {
3370		Serializable
3371		{
3372		private static final long serialVersionUID = 4374092139857L;
3373	<
3373	>
3374		/**
3375		* The comparator specified in the static factory.  This will never
3376		* be null, as the static factory returns a ReverseComparator
#	Line 3343 | Line 3378 | public class Collections {
3378		*
3379		* @serial
3380		*/
3381	<	private Comparator<T> cmp;
3382	<
3381	>	private final Comparator<T> cmp;
3382	>
3383		ReverseComparator2(Comparator<T> cmp) {
3384		assert cmp != null;
3385		this.cmp = cmp;
3386		}
3387	<
3387	>
3388		public int compare(T t1, T t2) {
3389		return cmp.compare(t2, t1);
3390		}
3391	+
3392	+	public boolean equals(Object o) {
3393	+	return (o == this) ||
3394	+	(o instanceof ReverseComparator2 &&
3395	+	cmp.equals(((ReverseComparator2)o).cmp));
3396	+	}
3397	+
3398	+	public int hashCode() {
3399	+	return cmp.hashCode() ^ Integer.MIN_VALUE;
3400	+	}
3401		}
3402
3403		/**
#	Line 3469 | Line 3514 | public class Collections {
3514		c1 = c2;
3515		c2 = tmp;
3516		}
3517	<
3517	>
3518		for (Object e : c1)
3519		if (c2.contains(e))
3520		return false;
#	Line 3490 | Line 3535 | public class Collections {
3535		* </pre>
3536		*
3537		* @param c the collection into which <tt>elements</tt> are to be inserted
3538	<	* @param a the elements to insert into <tt>c</tt>
3538	>	* @param elements the elements to insert into <tt>c</tt>
3539		* @return <tt>true</tt> if the collection changed as a result of the call
3540		* @throws UnsupportedOperationException if <tt>c</tt> does not support
3541	<	*         the <tt>add</tt> method
3541	>	*         the <tt>add</tt> operation
3542		* @throws NullPointerException if <tt>elements</tt> contains one or more
3543	<	*         null values and <tt>c</tt> does not support null elements, or
3543	>	*         null values and <tt>c</tt> does not permit null elements, or
3544		*         if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
3545	<	* @throws IllegalArgumentException if some aspect of a value in
3545	>	* @throws IllegalArgumentException if some property of a value in
3546		*         <tt>elements</tt> prevents it from being added to <tt>c</tt>
3547		* @see Collection#addAll(Collection)
3548		* @since 1.5
3549		*/
3550	<	public static <T> boolean addAll(Collection<? super T> c, T... a) {
3550	>	public static <T> boolean addAll(Collection<? super T> c, T... elements) {
3551		boolean result = false;
3552	<	for (T e : a)
3553	<	result |= c.add(e);
3552	>	for (T element : elements)
3553	>	result |= c.add(element);
3554		return result;
3555		}
3556
#	Line 3529 | Line 3574 | public class Collections {
3574		* to this method, and no reference to the map is retained, as illustrated
3575		* in the following code fragment:
3576		* <pre>
3577	<	*    Set&lt;Object&gt; weakHashSet = Collections.asSet(
3577	>	*    Set&lt;Object&gt; weakHashSet = Collections.newSetFromMap(
3578		*        new WeakHashMap&lt;Object, Boolean&gt;());
3579		* </pre>
3580		*
3581		* @param map the backing map
3582		* @return the set backed by the map
3583		* @throws IllegalArgumentException if <tt>map</tt> is not empty
3584	+	* @since 1.6
3585		*/
3586	<	public static <E> Set<E> asSet(Map<E, Boolean> map) {
3587	<	return new MapAsSet<E>(map);
3586	>	public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
3587	>	return new SetFromMap<E>(map);
3588		}
3589
3590	<	private static class MapAsSet<E> extends AbstractSet<E>
3590	>	private static class SetFromMap<E> extends AbstractSet<E>
3591		implements Set<E>, Serializable
3592		{
3593		private final Map<E, Boolean> m;  // The backing map
3594	<	private transient Set<E> keySet;  // Its keySet
3594	>	private transient Set<E> s;       // Its keySet
3595
3596	<	MapAsSet(Map<E, Boolean> map) {
3596	>	SetFromMap(Map<E, Boolean> map) {
3597		if (!map.isEmpty())
3598		throw new IllegalArgumentException("Map is non-empty");
3599		m = map;
3600	<	keySet = map.keySet();
3600	>	s = map.keySet();
3601		}
3602
3603	+	public void clear()               {        m.clear(); }
3604		public int size()                 { return m.size(); }
3605		public boolean isEmpty()          { return m.isEmpty(); }
3606		public boolean contains(Object o) { return m.containsKey(o); }
3560	–	public Iterator<E> iterator()     { return keySet.iterator(); }
3561	–	public Object[] toArray()         { return keySet.toArray(); }
3562	–	public <T> T[] toArray(T[] a)     { return keySet.toArray(a); }
3563	–	public boolean add(E e) {
3564	–	return m.put(e, Boolean.TRUE) == null;
3565	–	}
3607		public boolean remove(Object o)   { return m.remove(o) != null; }
3608	<
3609	<	public boolean removeAll(Collection<?> c) {
3610	<	return keySet.removeAll(c);
3611	<	}
3612	<	public boolean retainAll(Collection<?> c) {
3613	<	return keySet.retainAll(c);
3614	<	}
3615	<	public void clear()               { m.clear(); }
3616	<	public boolean equals(Object o)   { return keySet.equals(o); }
3617	<	public int hashCode()             { return keySet.hashCode(); }
3608	>	public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3609	>	public Iterator<E> iterator()     { return s.iterator(); }
3610	>	public Object[] toArray()         { return s.toArray(); }
3611	>	public <T> T[] toArray(T[] a)     { return s.toArray(a); }
3612	>	public String toString()          { return s.toString(); }
3613	>	public int hashCode()             { return s.hashCode(); }
3614	>	public boolean equals(Object o)   { return o == this || s.equals(o); }
3615	>	public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3616	>	public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
3617	>	public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
3618	>	// addAll is the only inherited implementation
3619
3620		private static final long serialVersionUID = 2454657854757543876L;
3621
3622	<	private void readObject(java.io.ObjectInputStream s)
3622	>	private void readObject(java.io.ObjectInputStream stream)
3623		throws IOException, ClassNotFoundException
3624		{
3625	<	s.defaultReadObject();
3626	<	keySet = m.keySet();
3625	>	stream.defaultReadObject();
3626	>	s = m.keySet();
3627		}
3628		}
3629
#	Line 3591 | Line 3633 | public class Collections {
3633		* <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
3634		* view can be useful when you would like to use a method
3635		* requiring a <tt>Queue</tt> but you need Lifo ordering.
3636	<	* @param deque the Deque
3636	>	*
3637	>	* <p>Each method invocation on the queue returned by this method
3638	>	* results in exactly one method invocation on the backing deque, with
3639	>	* one exception.  The {@link Queue#addAll addAll} method is
3640	>	* implemented as a sequence of {@link Deque#addFirst addFirst}
3641	>	* invocations on the backing deque.
3642	>	*
3643	>	* @param deque the deque
3644		* @return the queue
3645		* @since  1.6
3646		*/
#	Line 3599 | Line 3648 | public class Collections {
3648		return new AsLIFOQueue<T>(deque);
3649		}
3650
3651	<	static class AsLIFOQueue<E> extends AbstractQueue<E>
3651	>	static class AsLIFOQueue<E> extends AbstractQueue<E>
3652		implements Queue<E>, Serializable {
3653	+	private static final long serialVersionUID = 1802017725587941708L;
3654		private final Deque<E> q;
3655	<	AsLIFOQueue(Deque<E> q)            { this.q = q; }
3656	<	public boolean offer(E o)          { return q.offerFirst(o); }
3657	<	public E poll()                    { return q.pollFirst(); }
3658	<	public E remove()                  { return q.removeFirst(); }
3659	<	public E peek()                    { return q.peekFirst(); }
3660	<	public E element()                 { return q.getFirst(); }
3661	<	public int size()                  { return q.size(); }
3662	<	public boolean isEmpty()           { return q.isEmpty(); }
3663	<	public boolean contains(Object o)  { return q.contains(o); }
3664	<	public Iterator<E> iterator()      { return q.iterator(); }
3665	<	public Object[] toArray()          { return q.toArray(); }
3666	<	public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3667	<	public boolean add(E o)            { return q.offerFirst(o); }
3668	<	public boolean remove(Object o)    { return q.remove(o); }
3669	<	public void clear()                { q.clear(); }
3655	>	AsLIFOQueue(Deque<E> q)           { this.q = q; }
3656	>	public boolean add(E e)           { q.addFirst(e); return true; }
3657	>	public boolean offer(E e)         { return q.offerFirst(e); }
3658	>	public E poll()                   { return q.pollFirst(); }
3659	>	public E remove()                 { return q.removeFirst(); }
3660	>	public E peek()                   { return q.peekFirst(); }
3661	>	public E element()                { return q.getFirst(); }
3662	>	public void clear()               {        q.clear(); }
3663	>	public int size()                 { return q.size(); }
3664	>	public boolean isEmpty()          { return q.isEmpty(); }
3665	>	public boolean contains(Object o) { return q.contains(o); }
3666	>	public boolean remove(Object o)   { return q.remove(o); }
3667	>	public Iterator<E> iterator()     { return q.iterator(); }
3668	>	public Object[] toArray()         { return q.toArray(); }
3669	>	public <T> T[] toArray(T[] a)     { return q.toArray(a); }
3670	>	public String toString()          { return q.toString(); }
3671	>	public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3672	>	public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
3673	>	public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
3674	>	// We use inherited addAll; forwarding addAll would be wrong
3675		}
3676		}

Diff Legend

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