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.28 by jsr166, Sun May 28 23:36:29 2006 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2006 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
41	<	* <a href="{@docRoot}/../guide/collections/index.html">
40	>	* <p>This class is a member of the
41	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
42		* Java Collections Framework</a>.
43		*
44		* @author  Josh Bloch
#	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 168 | Line 168 | public class Collections {
168		/**
169		* Searches the specified list for the specified object using the binary
170		* search algorithm.  The list must be sorted into ascending order
171	<	* according to the <i>natural ordering</i> of its elements (as by the
172	<	* <tt>sort(List)</tt> method, above) prior to making this call.  If it is
173	<	* not sorted, the results are undefined.  If the list contains multiple
174	<	* elements equal to the specified object, there is no guarantee which one
175	<	* will be found.<p>
171	>	* according to the {@linkplain Comparable natural ordering} of its
172	>	* elements (as by the {@link #sort(List)} method) prior to making this
173	>	* call.  If it is not sorted, the results are undefined.  If the list
174	>	* contains multiple elements equal to the specified object, there is no
175	>	* guarantee which one will be found.
176		*
177	<	* This method runs in log(n) time for a "random access" list (which
177	>	* <p>This method runs in log(n) time for a "random access" list (which
178		* provides near-constant-time positional access).  If the specified list
179		* does not implement the {@link RandomAccess} interface and is large,
180		* this method will do an iterator-based binary search that performs
#	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
189	<	*         element greater than the key, or <tt>list.size()</tt>, if all
189	>	*         element greater than the key, or <tt>list.size()</tt> if all
190		*         elements in the list are less than the specified key.  Note
191		*         that this guarantees that the return value will be &gt;= 0 if
192		*         and only if the key is found.
193		* @throws ClassCastException if the list contains elements that are not
194		*         <i>mutually comparable</i> (for example, strings and
195	<	*         integers), or the search key in not mutually comparable
195	>	*         integers), or the search key is not mutually comparable
196		*         with the elements of the list.
197	–	* @see    Comparable
198	–	* @see #sort(List)
197		*/
198		public static <T>
199		int binarySearch(List<? extends Comparable<? super T>> list, T key) {
#	Line 212 | Line 210 | public class Collections {
210		int high = list.size()-1;
211
212		while (low <= high) {
213	<	int mid = (low + high) >> 1;
213	>	int mid = (low + high) >>> 1;
214		Comparable<? super T> midVal = list.get(mid);
215		int cmp = midVal.compareTo(key);
216
#	Line 234 | Line 232 | public class Collections {
232		ListIterator<? extends Comparable<? super T>> i = list.listIterator();
233
234		while (low <= high) {
235	<	int mid = (low + high) >> 1;
235	>	int mid = (low + high) >>> 1;
236		Comparable<? super T> midVal = get(i, mid);
237		int cmp = midVal.compareTo(key);
238
#	Line 270 | Line 268 | public class Collections {
268		/**
269		* Searches the specified list for the specified object using the binary
270		* search algorithm.  The list must be sorted into ascending order
271	<	* according to the specified comparator (as by the <tt>Sort(List,
272	<	* Comparator)</tt> method, above), prior to making this call.  If it is
271	>	* according to the specified comparator (as by the
272	>	* {@link #sort(List, Comparator) sort(List, Comparator)}
273	>	* method), prior to making this call.  If it is
274		* not sorted, the results are undefined.  If the list contains multiple
275		* elements equal to the specified object, there is no guarantee which one
276	<	* will be found.<p>
276	>	* will be found.
277		*
278	<	* This method runs in log(n) time for a "random access" list (which
278	>	* <p>This method runs in log(n) time for a "random access" list (which
279		* provides near-constant-time positional access).  If the specified list
280		* does not implement the {@link RandomAccess} interface and is large,
281		* this method will do an iterator-based binary search that performs
#	Line 284 | Line 283 | public class Collections {
283		*
284		* @param  list the list to be searched.
285		* @param  key the key to be searched for.
286	<	* @param  c the comparator by which the list is ordered.  A
287	<	*        <tt>null</tt> value indicates that the elements' <i>natural
288	<	*        ordering</i> should be used.
289	<	* @return index of the search key, if it is contained in the list;
286	>	* @param  c the comparator by which the list is ordered.
287	>	*         A <tt>null</tt> value indicates that the elements'
288	>	*         {@linkplain Comparable natural ordering} should be used.
289	>	* @return the index of the search key, if it is contained in the list;
290		*         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
291		*         <i>insertion point</i> is defined as the point at which the
292		*         key would be inserted into the list: the index of the first
293	<	*         element greater than the key, or <tt>list.size()</tt>, if all
293	>	*         element greater than the key, or <tt>list.size()</tt> if all
294		*         elements in the list are less than the specified key.  Note
295		*         that this guarantees that the return value will be &gt;= 0 if
296		*         and only if the key is found.
297		* @throws ClassCastException if the list contains elements that are not
298		*         <i>mutually comparable</i> using the specified comparator,
299	<	*         or the search key in not mutually comparable with the
299	>	*         or the search key is not mutually comparable with the
300		*         elements of the list using this comparator.
302	–	* @see    Comparable
303	–	* @see #sort(List, Comparator)
301		*/
302		public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
303		if (c==null)
#	Line 317 | Line 314 | public class Collections {
314		int high = l.size()-1;
315
316		while (low <= high) {
317	<	int mid = (low + high) >> 1;
317	>	int mid = (low + high) >>> 1;
318		T midVal = l.get(mid);
319		int cmp = c.compare(midVal, key);
320
#	Line 337 | Line 334 | public class Collections {
334		ListIterator<? extends T> i = l.listIterator();
335
336		while (low <= high) {
337	<	int mid = (low + high) >> 1;
337	>	int mid = (low + high) >>> 1;
338		T midVal = get(i, mid);
339		int cmp = c.compare(midVal, key);
340
#	Line 361 | Line 358 | public class Collections {
358		*
359		* @param  list the list whose elements are to be reversed.
360		* @throws UnsupportedOperationException if the specified list or
361	<	*         its list-iterator does not support the <tt>set</tt> method.
361	>	*         its list-iterator does not support the <tt>set</tt> operation.
362		*/
363		public static void reverse(List<?> list) {
364		int size = list.size();
#	Line 405 | Line 402 | public class Collections {
402		*
403		* @param  list the list to be shuffled.
404		* @throws UnsupportedOperationException if the specified list or
405	<	*         its list-iterator does not support the <tt>set</tt> method.
405	>	*         its list-iterator does not support the <tt>set</tt> operation.
406		*/
407		public static void shuffle(List<?> list) {
408	+	if (r == null) {
409	+	r = new Random();
410	+	}
411		shuffle(list, r);
412		}
413	<	private static Random r = new Random();
413	>	private static Random r;
414
415		/**
416		* Randomly permute the specified list using the specified source of
#	Line 569 | Line 569 | public class Collections {
569		Iterator<? extends T> i = coll.iterator();
570		T candidate = i.next();
571
572	<	while(i.hasNext()) {
572	>	while (i.hasNext()) {
573		T next = i.next();
574		if (next.compareTo(candidate) < 0)
575		candidate = next;
#	Line 606 | Line 606 | public class Collections {
606		Iterator<? extends T> i = coll.iterator();
607		T candidate = i.next();
608
609	<	while(i.hasNext()) {
609	>	while (i.hasNext()) {
610		T next = i.next();
611		if (comp.compare(next, candidate) < 0)
612		candidate = next;
#	Line 639 | Line 639 | public class Collections {
639		Iterator<? extends T> i = coll.iterator();
640		T candidate = i.next();
641
642	<	while(i.hasNext()) {
642	>	while (i.hasNext()) {
643		T next = i.next();
644		if (next.compareTo(candidate) > 0)
645		candidate = next;
#	Line 676 | Line 676 | public class Collections {
676		Iterator<? extends T> i = coll.iterator();
677		T candidate = i.next();
678
679	<	while(i.hasNext()) {
679	>	while (i.hasNext()) {
680		T next = i.next();
681		if (comp.compare(next, candidate) > 0)
682		candidate = next;
#	Line 712 | Line 712 | public class Collections {
712		*     Collections.rotate(l.subList(1, 4), -1);
713		* </pre>
714		* The resulting list is <tt>[a, c, d, b, e]</tt>.
715	<	*
715	>	*
716		* <p>To move more than one element forward, increase the absolute value
717		* of the rotation distance.  To move elements backward, use a positive
718		* shift distance.
#	Line 736 | Line 736 | public class Collections {
736		*        constraints on this value; it may be zero, negative, or
737		*        greater than <tt>list.size()</tt>.
738		* @throws UnsupportedOperationException if the specified list or
739	<	*         its list-iterator does not support the <tt>set</tt> method.
739	>	*         its list-iterator does not support the <tt>set</tt> operation.
740		* @since 1.4
741		*/
742		public static void rotate(List<?> list, int distance) {
#	Line 772 | Line 772 | public class Collections {
772		private static void rotate2(List<?> list, int distance) {
773		int size = list.size();
774		if (size == 0)
775	<	return;
775	>	return;
776		int mid =  -distance % size;
777		if (mid < 0)
778		mid += size;
#	Line 799 | Line 799 | public class Collections {
799		*         <tt>e</tt> such that
800		*         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
801		* @throws UnsupportedOperationException if the specified list or
802	<	*         its list-iterator does not support the <tt>set</tt> method.
802	>	*         its list-iterator does not support the <tt>set</tt> operation.
803		* @since  1.4
804		*/
805		public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
#	Line 970 | Line 970 | public class Collections {
970		* that the backing collection is a set or a list.<p>
971		*
972		* The returned collection will be serializable if the specified collection
973	<	* is serializable.
973	>	* is serializable.
974		*
975		* @param  c the collection for which an unmodifiable view is to be
976		*         returned.
#	Line 1014 | Line 1014 | public class Collections {
1014		};
1015		}
1016
1017	<	public boolean add(E o){
1017	>	public boolean add(E e){
1018		throw new UnsupportedOperationException();
1019		}
1020		public boolean remove(Object o) {
#	Line 1046 | Line 1046 | public class Collections {
1046		* iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1047		*
1048		* The returned set will be serializable if the specified set
1049	<	* is serializable.
1049	>	* is serializable.
1050		*
1051		* @param  s the set for which an unmodifiable view is to be returned.
1052		* @return an unmodifiable view of the specified set.
1053		*/
1054	–
1054		public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1055		return new UnmodifiableSet<T>(s);
1056		}
#	Line 1064 | Line 1063 | public class Collections {
1063		private static final long serialVersionUID = -9215047833775013803L;
1064
1065		UnmodifiableSet(Set<? extends E> s)     {super(s);}
1066	<	public boolean equals(Object o) {return c.equals(o);}
1066	>	public boolean equals(Object o) {return o == this || c.equals(o);}
1067		public int hashCode()           {return c.hashCode();}
1068		}
1069
#	Line 1078 | Line 1077 | public class Collections {
1077		* an <tt>UnsupportedOperationException</tt>.<p>
1078		*
1079		* The returned sorted set will be serializable if the specified sorted set
1080	<	* is serializable.
1080	>	* is serializable.
1081		*
1082		* @param s the sorted set for which an unmodifiable view is to be
1083	<	*        returned.
1083	>	*        returned.
1084		* @return an unmodifiable view of the specified sorted set.
1085		*/
1086		public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
#	Line 1149 | Line 1148 | public class Collections {
1148		this.list = list;
1149		}
1150
1151	<	public boolean equals(Object o) {return list.equals(o);}
1151	>	public boolean equals(Object o) {return o == this || list.equals(o);}
1152		public int hashCode()           {return list.hashCode();}
1153
1154		public E get(int index) {return list.get(index);}
#	Line 1183 | Line 1182 | public class Collections {
1182		public void remove() {
1183		throw new UnsupportedOperationException();
1184		}
1185	<	public void set(E o) {
1185	>	public void set(E e) {
1186		throw new UnsupportedOperationException();
1187		}
1188	<	public void add(E o) {
1188	>	public void add(E e) {
1189		throw new UnsupportedOperationException();
1190		}
1191		};
#	Line 1252 | Line 1251 | public class Collections {
1251		* <tt>UnsupportedOperationException</tt>.<p>
1252		*
1253		* The returned map will be serializable if the specified map
1254	<	* is serializable.
1254	>	* is serializable.
1255		*
1256		* @param  m the map for which an unmodifiable view is to be returned.
1257		* @return an unmodifiable view of the specified map.
#	Line 1288 | Line 1287 | public class Collections {
1287		public V remove(Object key) {
1288		throw new UnsupportedOperationException();
1289		}
1290	<	public void putAll(Map<? extends K, ? extends V> t) {
1290	>	public void putAll(Map<? extends K, ? extends V> m) {
1291		throw new UnsupportedOperationException();
1292		}
1293		public void clear() {
#	Line 1317 | Line 1316 | public class Collections {
1316		return values;
1317		}
1318
1319	<	public boolean equals(Object o) {return m.equals(o);}
1319	>	public boolean equals(Object o) {return o == this || m.equals(o);}
1320		public int hashCode()           {return m.hashCode();}
1321		public String toString()        {return m.toString();}
1322
#	Line 1334 | Line 1333 | public class Collections {
1333		private static final long serialVersionUID = 7854390611657943733L;
1334
1335		UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1336	<	super((Set<Map.Entry<K,V>>)(Set)s);
1336	>	super((Set)s);
1337		}
1338		public Iterator<Map.Entry<K,V>> iterator() {
1339		return new Iterator<Map.Entry<K,V>>() {
#	Line 1363 | Line 1362 | public class Collections {
1362		// We don't pass a to c.toArray, to avoid window of
1363		// vulnerability wherein an unscrupulous multithreaded client
1364		// could get his hands on raw (unwrapped) Entries from c.
1365	<	Object[] arr =
1367	<	c.toArray(
1368	<	a.length==0 ? a :
1369	<	(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), 0));
1365	>	Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1366
1367		for (int i=0; i<arr.length; i++)
1368		arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]);
#	Line 1456 | Line 1452 | public class Collections {
1452		* an <tt>UnsupportedOperationException</tt>.<p>
1453		*
1454		* The returned sorted map will be serializable if the specified sorted map
1455	<	* is serializable.
1455	>	* is serializable.
1456		*
1457		* @param m the sorted map for which an unmodifiable view is to be
1458	<	*        returned.
1458	>	*        returned.
1459		* @return an unmodifiable view of the specified sorted map.
1460		*/
1461		public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
#	Line 1523 | Line 1519 | public class Collections {
1519		* that the backing collection is a set or a list.<p>
1520		*
1521		* The returned collection will be serializable if the specified collection
1522	<	* is serializable.
1522	>	* is serializable.
1523		*
1524		* @param  c the collection to be "wrapped" in a synchronized collection.
1525		* @return a synchronized view of the specified collection.
#	Line 1543 | Line 1539 | public class Collections {
1539		// use serialVersionUID from JDK 1.2.2 for interoperability
1540		private static final long serialVersionUID = 3053995032091335093L;
1541
1542	<	final Collection<E> c;     // Backing Collection
1543	<	final Object       mutex;  // Object on which to synchronize
1542	>	final Collection<E> c;  // Backing Collection
1543	>	final Object mutex;     // Object on which to synchronize
1544
1545		SynchronizedCollection(Collection<E> c) {
1546		if (c==null)
#	Line 1577 | Line 1573 | public class Collections {
1573		return c.iterator(); // Must be manually synched by user!
1574		}
1575
1576	<	public boolean add(E o) {
1577	<	synchronized(mutex) {return c.add(o);}
1576	>	public boolean add(E e) {
1577	>	synchronized(mutex) {return c.add(e);}
1578		}
1579		public boolean remove(Object o) {
1580		synchronized(mutex) {return c.remove(o);}
#	Line 1673 | Line 1669 | public class Collections {
1669		* sorted set when iterating over it or any of its <tt>subSet</tt>,
1670		* <tt>headSet</tt>, or <tt>tailSet</tt> views.
1671		* <pre>
1672	<	*  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1672	>	*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1673		*      ...
1674		*  synchronized(s) {
1675		*      Iterator i = s.iterator(); // Must be in the synchronized block
#	Line 1683 | Line 1679 | public class Collections {
1679		* </pre>
1680		* or:
1681		* <pre>
1682	<	*  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1682	>	*  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1683		*  SortedSet s2 = s.headSet(foo);
1684		*      ...
1685		*  synchronized(s) {  // Note: s, not s2!!!
#	Line 2007 | Line 2003 | public class Collections {
2003		public Set<Map.Entry<K,V>> entrySet() {
2004		synchronized(mutex) {
2005		if (entrySet==null)
2006	<	entrySet = new SynchronizedSet<Map.Entry<K,V>>((Set<Map.Entry<K,V>>)m.entrySet(), mutex);
2006	>	entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2007		return entrySet;
2008		}
2009		}
#	Line 2045 | Line 2041 | public class Collections {
2041		* collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2042		* <tt>tailMap</tt> views.
2043		* <pre>
2044	<	*  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2044	>	*  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2045		*      ...
2046		*  Set s = m.keySet();  // Needn't be in synchronized block
2047		*      ...
#	Line 2057 | Line 2053 | public class Collections {
2053		* </pre>
2054		* or:
2055		* <pre>
2056	<	*  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2056	>	*  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2057		*  SortedMap m2 = m.subMap(foo, bar);
2058		*      ...
2059		*  Set s2 = m2.keySet();  // Needn't be in synchronized block
#	Line 2191 | Line 2187 | public class Collections {
2187		Class<E> type) {
2188		return new CheckedCollection<E>(c, type);
2189		}
2190	<
2190	>
2191		/**
2192		* @serial include
2193		*/
#	Line 2221 | Line 2217 | public class Collections {
2217		public Object[] toArray()           { return c.toArray(); }
2218		public <T> T[] toArray(T[] a)       { return c.toArray(a); }
2219		public String toString()            { return c.toString(); }
2224	–	public Iterator<E> iterator()       { return c.iterator(); }
2220		public boolean remove(Object o)     { return c.remove(o); }
2221		public boolean containsAll(Collection<?> coll) {
2222		return c.containsAll(coll);
#	Line 2236 | Line 2231 | public class Collections {
2231		c.clear();
2232		}
2233
2234	<	public boolean add(E o){
2235	<	typeCheck(o);
2236	<	return c.add(o);
2234	>	public Iterator<E> iterator() {
2235	>	return new Iterator<E>() {
2236	>	private final Iterator<E> it = c.iterator();
2237	>	public boolean hasNext() { return it.hasNext(); }
2238	>	public E next()          { return it.next(); }
2239	>	public void remove()     {        it.remove(); }};
2240	>	}
2241	>
2242	>	public boolean add(E e){
2243	>	typeCheck(e);
2244	>	return c.add(e);
2245		}
2246
2247		public boolean addAll(Collection<? extends E> coll) {
#	Line 2246 | Line 2249 | public class Collections {
2249		* Dump coll into an array of the required type.  This serves
2250		* three purposes: it insulates us from concurrent changes in
2251		* the contents of coll, it type-checks all of the elements in
2252	<	* coll, and it provides all-or-nothing semantics(which we
2252	>	* coll, and it provides all-or-nothing semantics (which we
2253		* wouldn't get if we type-checked each element as we added it).
2254		*/
2255		E[] a = null;
2256		try {
2257		a = coll.toArray(zeroLengthElementArray());
2258	<	} catch(ArrayStoreException e) {
2258	>	} catch (ArrayStoreException e) {
2259		throw new ClassCastException();
2260		}
2261
#	Line 2265 | Line 2268 | public class Collections {
2268		private E[] zeroLengthElementArray = null; // Lazily initialized
2269
2270		/*
2271	<	* We don't need locking or volatile, because it's OK if we create
2271	>	* We don't need locking or volatile, because it's OK if we create
2272		* several zeroLengthElementArrays, and they're immutable.
2273		*/
2274		E[] zeroLengthElementArray() {
#	Line 2300 | Line 2303 | public class Collections {
2303		public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2304		return new CheckedSet<E>(s, type);
2305		}
2306	<
2306	>
2307		/**
2308		* @serial include
2309		*/
#	Line 2311 | Line 2314 | public class Collections {
2314
2315		CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2316
2317	<	public boolean equals(Object o) { return c.equals(o); }
2317	>	public boolean equals(Object o) { return o == this || c.equals(o); }
2318		public int hashCode()           { return c.hashCode(); }
2319		}
2320
#	Line 2414 | Line 2417 | public class Collections {
2417		this.list = list;
2418		}
2419
2420	<	public boolean equals(Object o)  { return list.equals(o); }
2420	>	public boolean equals(Object o)  { return o == this || list.equals(o); }
2421		public int hashCode()            { return list.hashCode(); }
2422		public E get(int index)          { return list.get(index); }
2423		public E remove(int index)       { return list.remove(index); }
#	Line 2436 | Line 2439 | public class Collections {
2439		E[] a = null;
2440		try {
2441		a = c.toArray(zeroLengthElementArray());
2442	<	} catch(ArrayStoreException e) {
2442	>	} catch (ArrayStoreException e) {
2443		throw new ClassCastException();
2444		}
2445
#	Line 2456 | Line 2459 | public class Collections {
2459		public int previousIndex()   { return i.previousIndex(); }
2460		public void remove()         { i.remove(); }
2461
2462	<	public void set(E o) {
2463	<	typeCheck(o);
2464	<	i.set(o);
2462	>	public void set(E e) {
2463	>	typeCheck(e);
2464	>	i.set(e);
2465		}
2466
2467	<	public void add(E o) {
2468	<	typeCheck(o);
2469	<	i.add(o);
2467	>	public void add(E e) {
2468	>	typeCheck(e);
2469	>	i.add(e);
2470		}
2471		};
2472		}
#	Line 2568 | Line 2571 | public class Collections {
2571		public void clear()                    { m.clear(); }
2572		public Set<K> keySet()                 { return m.keySet(); }
2573		public Collection<V> values()          { return m.values(); }
2574	<	public boolean equals(Object o)        { return m.equals(o);  }
2574	>	public boolean equals(Object o)        { return o == this || m.equals(o); }
2575		public int hashCode()                  { return m.hashCode(); }
2576		public String toString()               { return m.toString(); }
2577
#	Line 2582 | Line 2585 | public class Collections {
2585		K[] keys = null;
2586		try {
2587		keys = t.keySet().toArray(zeroLengthKeyArray());
2588	<	} catch(ArrayStoreException e) {
2588	>	} catch (ArrayStoreException e) {
2589		throw new ClassCastException();
2590		}
2591		V[] values = null;
2592		try {
2593		values = t.values().toArray(zeroLengthValueArray());
2594	<	} catch(ArrayStoreException e) {
2594	>	} catch (ArrayStoreException e) {
2595		throw new ClassCastException();
2596		}
2597
#	Line 2604 | Line 2607 | public class Collections {
2607		private V[] zeroLengthValueArray = null;
2608
2609		/*
2610	<	* We don't need locking or volatile, because it's OK if we create
2610	>	* We don't need locking or volatile, because it's OK if we create
2611		* several zeroLengthValueArrays, and they're immutable.
2612		*/
2613		private K[] zeroLengthKeyArray() {
#	Line 2658 | Line 2661 | public class Collections {
2661		s.clear();
2662		}
2663
2664	<	public boolean add(Map.Entry<K, V> o){
2664	>	public boolean add(Map.Entry<K, V> e){
2665		throw new UnsupportedOperationException();
2666		}
2667		public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
#	Line 2700 | Line 2703 | public class Collections {
2703		// We don't pass a to s.toArray, to avoid window of
2704		// vulnerability wherein an unscrupulous multithreaded client
2705		// could get his hands on raw (unwrapped) Entries from s.
2706	<	Object[] arr = s.toArray(a.length==0 ? a :
2704	<	(T[])Array.newInstance(a.getClass().getComponentType(), 0));
2706	>	Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2707
2708		for (int i=0; i<arr.length; i++)
2709		arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i],
#	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 3230 | Line 3199 | public class Collections {
3199		* @see    List#addAll(int, Collection)
3200		*/
3201		public static <T> List<T> nCopies(int n, T o) {
3202	+	if (n < 0)
3203	+	throw new IllegalArgumentException("List length = " + n);
3204		return new CopiesList<T>(n, o);
3205		}
3206
#	Line 3242 | Line 3213 | public class Collections {
3213		{
3214		static final long serialVersionUID = 2739099268398711800L;
3215
3216	<	int n;
3217	<	E element;
3216	>	final int n;
3217	>	final E element;
3218
3219	<	CopiesList(int n, E o) {
3220	<	if (n < 0)
3250	<	throw new IllegalArgumentException("List length = " + n);
3219	>	CopiesList(int n, E e) {
3220	>	assert n >= 0;
3221		this.n = n;
3222	<	element = o;
3222	>	element = e;
3223		}
3224
3225		public int size() {
#	Line 3260 | Line 3230 | public class Collections {
3230		return n != 0 && eq(obj, element);
3231		}
3232
3233	+	public int indexOf(Object o) {
3234	+	return contains(o) ? 0 : -1;
3235	+	}
3236	+
3237	+	public int lastIndexOf(Object o) {
3238	+	return contains(o) ? n - 1 : -1;
3239	+	}
3240	+
3241		public E get(int index) {
3242	<	if (index<0 || index>=n)
3242	>	if (index < 0 || index >= n)
3243		throw new IndexOutOfBoundsException("Index: "+index+
3244		", Size: "+n);
3245		return element;
3246		}
3247	+
3248	+	public Object[] toArray() {
3249	+	final Object[] a = new Object[n];
3250	+	if (element != null)
3251	+	Arrays.fill(a, 0, n, element);
3252	+	return a;
3253	+	}
3254	+
3255	+	public <T> T[] toArray(T[] a) {
3256	+	final int n = this.n;
3257	+	if (a.length < n) {
3258	+	a = (T[])java.lang.reflect.Array
3259	+	.newInstance(a.getClass().getComponentType(), n);
3260	+	if (element != null)
3261	+	Arrays.fill(a, 0, n, element);
3262	+	} else {
3263	+	Arrays.fill(a, 0, n, element);
3264	+	if (a.length > n)
3265	+	a[n] = null;
3266	+	}
3267	+	return a;
3268	+	}
3269	+
3270	+	public List<E> subList(int fromIndex, int toIndex) {
3271	+	if (fromIndex < 0)
3272	+	throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3273	+	if (toIndex > n)
3274	+	throw new IndexOutOfBoundsException("toIndex = " + toIndex);
3275	+	if (fromIndex > toIndex)
3276	+	throw new IllegalArgumentException("fromIndex(" + fromIndex +
3277	+	") > toIndex(" + toIndex + ")");
3278	+	return new CopiesList(toIndex - fromIndex, element);
3279	+	}
3280		}
3281
3282		/**
#	Line 3305 | Line 3316 | public class Collections {
3316		public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3317		return c2.compareTo(c1);
3318		}
3319	+
3320	+	private Object readResolve() { return reverseOrder(); }
3321		}
3322
3323		/**
#	Line 3323 | Line 3336 | public class Collections {
3336		*/
3337		public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3338		if (cmp == null)
3339	<	return new ReverseComparator();  // Unchecked warning!!
3340	<
3339	>	return reverseOrder();
3340	>
3341		return new ReverseComparator2<T>(cmp);
3342		}
3343	<
3343	>
3344		/**
3345		* @serial include
3346		*/
#	Line 3335 | Line 3348 | public class Collections {
3348		Serializable
3349		{
3350		private static final long serialVersionUID = 4374092139857L;
3351	<
3351	>
3352		/**
3353		* The comparator specified in the static factory.  This will never
3354		* be null, as the static factory returns a ReverseComparator
#	Line 3344 | Line 3357 | public class Collections {
3357		* @serial
3358		*/
3359		private Comparator<T> cmp;
3360	<
3360	>
3361		ReverseComparator2(Comparator<T> cmp) {
3362		assert cmp != null;
3363		this.cmp = cmp;
3364		}
3365	<
3365	>
3366		public int compare(T t1, T t2) {
3367		return cmp.compare(t2, t1);
3368		}
#	Line 3469 | Line 3482 | public class Collections {
3482		c1 = c2;
3483		c2 = tmp;
3484		}
3485	<
3485	>
3486		for (Object e : c1)
3487		if (c2.contains(e))
3488		return false;
#	Line 3490 | Line 3503 | public class Collections {
3503		* </pre>
3504		*
3505		* @param c the collection into which <tt>elements</tt> are to be inserted
3506	<	* @param a the elements to insert into <tt>c</tt>
3506	>	* @param elements the elements to insert into <tt>c</tt>
3507		* @return <tt>true</tt> if the collection changed as a result of the call
3508		* @throws UnsupportedOperationException if <tt>c</tt> does not support
3509	<	*         the <tt>add</tt> method
3509	>	*         the <tt>add</tt> operation
3510		* @throws NullPointerException if <tt>elements</tt> contains one or more
3511	<	*         null values and <tt>c</tt> does not support null elements, or
3511	>	*         null values and <tt>c</tt> does not permit null elements, or
3512		*         if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
3513	<	* @throws IllegalArgumentException if some aspect of a value in
3513	>	* @throws IllegalArgumentException if some property of a value in
3514		*         <tt>elements</tt> prevents it from being added to <tt>c</tt>
3515		* @see Collection#addAll(Collection)
3516		* @since 1.5
3517		*/
3518	<	public static <T> boolean addAll(Collection<? super T> c, T... a) {
3518	>	public static <T> boolean addAll(Collection<? super T> c, T... elements) {
3519		boolean result = false;
3520	<	for (T e : a)
3521	<	result |= c.add(e);
3520	>	for (T element : elements)
3521	>	result |= c.add(element);
3522		return result;
3523		}
3524
#	Line 3529 | Line 3542 | public class Collections {
3542		* to this method, and no reference to the map is retained, as illustrated
3543		* in the following code fragment:
3544		* <pre>
3545	<	*    Set&lt;Object&gt; weakHashSet = Collections.asSet(
3545	>	*    Set&lt;Object&gt; weakHashSet = Collections.newSetFromMap(
3546		*        new WeakHashMap&lt;Object, Boolean&gt;());
3547		* </pre>
3548		*
3549		* @param map the backing map
3550		* @return the set backed by the map
3551		* @throws IllegalArgumentException if <tt>map</tt> is not empty
3552	+	* @since 1.6
3553		*/
3554	<	public static <E> Set<E> asSet(Map<E, Boolean> map) {
3555	<	return new MapAsSet<E>(map);
3554	>	public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
3555	>	return new SetFromMap<E>(map);
3556		}
3557
3558	<	private static class MapAsSet<E> extends AbstractSet<E>
3558	>	private static class SetFromMap<E> extends AbstractSet<E>
3559		implements Set<E>, Serializable
3560		{
3561		private final Map<E, Boolean> m;  // The backing map
3562	<	private transient Set<E> keySet;  // Its keySet
3562	>	private transient Set<E> s;       // Its keySet
3563
3564	<	MapAsSet(Map<E, Boolean> map) {
3564	>	SetFromMap(Map<E, Boolean> map) {
3565		if (!map.isEmpty())
3566		throw new IllegalArgumentException("Map is non-empty");
3567		m = map;
3568	<	keySet = map.keySet();
3568	>	s = map.keySet();
3569		}
3570
3571	+	public void clear()               {        m.clear(); }
3572		public int size()                 { return m.size(); }
3573		public boolean isEmpty()          { return m.isEmpty(); }
3574		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	–	}
3575		public boolean remove(Object o)   { return m.remove(o) != null; }
3576	<
3577	<	public boolean removeAll(Collection<?> c) {
3578	<	return keySet.removeAll(c);
3579	<	}
3580	<	public boolean retainAll(Collection<?> c) {
3581	<	return keySet.retainAll(c);
3582	<	}
3583	<	public void clear()               { m.clear(); }
3584	<	public boolean equals(Object o)   { return keySet.equals(o); }
3585	<	public int hashCode()             { return keySet.hashCode(); }
3576	>	public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3577	>	public Iterator<E> iterator()     { return s.iterator(); }
3578	>	public Object[] toArray()         { return s.toArray(); }
3579	>	public <T> T[] toArray(T[] a)     { return s.toArray(a); }
3580	>	public String toString()          { return s.toString(); }
3581	>	public int hashCode()             { return s.hashCode(); }
3582	>	public boolean equals(Object o)   { return o == this || s.equals(o); }
3583	>	public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3584	>	public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
3585	>	public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
3586	>	// addAll is the only inherited implementation
3587
3588		private static final long serialVersionUID = 2454657854757543876L;
3589
3590	<	private void readObject(java.io.ObjectInputStream s)
3590	>	private void readObject(java.io.ObjectInputStream stream)
3591		throws IOException, ClassNotFoundException
3592		{
3593	<	s.defaultReadObject();
3594	<	keySet = m.keySet();
3593	>	stream.defaultReadObject();
3594	>	s = m.keySet();
3595		}
3596		}
3597
#	Line 3591 | Line 3601 | public class Collections {
3601		* <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
3602		* view can be useful when you would like to use a method
3603		* requiring a <tt>Queue</tt> but you need Lifo ordering.
3604	<	* @param deque the Deque
3604	>	*
3605	>	* <p>Each method invocation on the queue returned by this method
3606	>	* results in exactly one method invocation on the backing deque, with
3607	>	* one exception.  The {@link Queue#addAll addAll} method is
3608	>	* implemented as a sequence of {@link Deque#addFirst addFirst}
3609	>	* invocations on the backing deque.
3610	>	*
3611	>	* @param deque the deque
3612		* @return the queue
3613		* @since  1.6
3614		*/
#	Line 3599 | Line 3616 | public class Collections {
3616		return new AsLIFOQueue<T>(deque);
3617		}
3618
3619	<	static class AsLIFOQueue<E> extends AbstractQueue<E>
3619	>	static class AsLIFOQueue<E> extends AbstractQueue<E>
3620		implements Queue<E>, Serializable {
3621	+	private static final long serialVersionUID = 1802017725587941708L;
3622		private final Deque<E> q;
3623	<	AsLIFOQueue(Deque<E> q)            { this.q = q; }
3624	<	public boolean offer(E o)          { return q.offerFirst(o); }
3625	<	public E poll()                    { return q.pollFirst(); }
3626	<	public E remove()                  { return q.removeFirst(); }
3627	<	public E peek()                    { return q.peekFirst(); }
3628	<	public E element()                 { return q.getFirst(); }
3629	<	public int size()                  { return q.size(); }
3630	<	public boolean isEmpty()           { return q.isEmpty(); }
3631	<	public boolean contains(Object o)  { return q.contains(o); }
3632	<	public Iterator<E> iterator()      { return q.iterator(); }
3633	<	public Object[] toArray()          { return q.toArray(); }
3634	<	public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3635	<	public boolean add(E o)            { return q.offerFirst(o); }
3636	<	public boolean remove(Object o)    { return q.remove(o); }
3637	<	public void clear()                { q.clear(); }
3623	>	AsLIFOQueue(Deque<E> q)           { this.q = q; }
3624	>	public boolean add(E e)           { q.addFirst(e); return true; }
3625	>	public boolean offer(E e)         { return q.offerFirst(e); }
3626	>	public E poll()                   { return q.pollFirst(); }
3627	>	public E remove()                 { return q.removeFirst(); }
3628	>	public E peek()                   { return q.peekFirst(); }
3629	>	public E element()                { return q.getFirst(); }
3630	>	public void clear()               {        q.clear(); }
3631	>	public int size()                 { return q.size(); }
3632	>	public boolean isEmpty()          { return q.isEmpty(); }
3633	>	public boolean contains(Object o) { return q.contains(o); }
3634	>	public boolean remove(Object o)   { return q.remove(o); }
3635	>	public Iterator<E> iterator()     { return q.iterator(); }
3636	>	public Object[] toArray()         { return q.toArray(); }
3637	>	public <T> T[] toArray(T[] a)     { return q.toArray(a); }
3638	>	public String toString()          { return q.toString(); }
3639	>	public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3640	>	public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
3641	>	public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
3642	>	// We use inherited addAll; forwarding addAll would be wrong
3643		}
3644		}

Diff Legend

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