[ViewVC] Diff of: jsr166/jsr166/src/main/java/util/Collections.java

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.11 by jsr166, Mon Jun 20 18:03:08 2005 UTC vs.
Revision 1.43 by jsr166, Sat Oct 16 16:44:39 2010 UTC

#	Line 1 \| Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright (c) 1997, 2007, Oracle and/or its affiliates. All rights reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22	>	* or visit www.oracle.com if you need additional information or have any
23	>	* questions.
24		*/
25
26		package java.util;
9	–	import java.util.*; // for javadoc (till 6280605 is fixed)
27		import java.io.Serializable;
28		import java.io.ObjectOutputStream;
29		import java.io.IOException;
#	Line 39 \| Line 56 \| import java.lang.reflect.Array;
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">
59	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
60		* Java Collections Framework</a>.
61		*
62		* @author Josh Bloch
63		* @author Neal Gafter
64	<	* @version %I%, %G%
65	<	* @see Collection
66	<	* @see Set
67	<	* @see List
51	<	* @see Map
64	>	* @see Collection
65	>	* @see Set
66	>	* @see List
67	>	* @see Map
68		* @since 1.2
69		*/
70
#	Line 84 \| Line 100 \| public class Collections {
100
101		/**
102		* Sorts the specified list into ascending order, according to the
103	<	* <i>natural ordering</i> of its elements. All elements in the list must
104	<	* implement the <tt>Comparable</tt> interface. Furthermore, all elements
105	<	* in the list must be <i>mutually comparable</i> (that is,
106	<	* <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
107	<	* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
108	<	*
109	<	* This sort is guaranteed to be <i>stable</i>: equal elements will
110	<	* not be reordered as a result of the sort.<p>
111	<	*
112	<	* The specified list must be modifiable, but need not be resizable.<p>
113	<	*
114	<	* The sorting algorithm is a modified mergesort (in which the merge is
115	<	* omitted if the highest element in the low sublist is less than the
116	<	* lowest element in the high sublist). This algorithm offers guaranteed
117	<	* n log(n) performance.
103	>	* {@linkplain Comparable natural ordering} of its elements.
104	>	* All elements in the list must implement the {@link Comparable}
105	>	* interface. Furthermore, all elements in the list must be
106	>	* <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)}
107	>	* must not throw a {@code ClassCastException} for any elements
108	>	* {@code e1} and {@code e2} in the list).
109	>	*
110	>	* <p>This sort is guaranteed to be <i>stable</i>: equal elements will
111	>	* not be reordered as a result of the sort.
112	>	*
113	>	* <p>The specified list must be modifiable, but need not be resizable.
114	>	*
115	>	* <p>Implementation note: This implementation is a stable, adaptive,
116	>	* iterative mergesort that requires far fewer than n lg(n) comparisons
117	>	* when the input array is partially sorted, while offering the
118	>	* performance of a traditional mergesort when the input array is
119	>	* randomly ordered. If the input array is nearly sorted, the
120	>	* implementation requires approximately n comparisons. Temporary
121	>	* storage requirements vary from a small constant for nearly sorted
122	>	* input arrays to n/2 object references for randomly ordered input
123	>	* arrays.
124	>	*
125	>	* <p>The implementation takes equal advantage of ascending and
126	>	* descending order in its input array, and can take advantage of
127	>	* ascending and descending order in different parts of the same
128	>	* input array. It is well-suited to merging two or more sorted arrays:
129	>	* simply concatenate the arrays and sort the resulting array.
130	>	*
131	>	* <p>The implementation was adapted from Tim Peters's list sort for Python
132	>	* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
133	>	* TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
134	>	* Sorting and Information Theoretic Complexity", in Proceedings of the
135	>	* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
136	>	* January 1993.
137		*
138	<	* This implementation dumps the specified list into an array, sorts
138	>	* <p>This implementation dumps the specified list into an array, sorts
139		* the array, and iterates over the list resetting each element
140		* from the corresponding position in the array. This avoids the
141		* n<sup>2</sup> log(n) performance that would result from attempting
#	Line 108 \| Line 143 \| public class Collections {
143		*
144		* @param list the list to be sorted.
145		* @throws ClassCastException if the list contains elements that are not
146	<	* <i>mutually comparable</i> (for example, strings and integers).
146	>	* <i>mutually comparable</i> (for example, strings and integers).
147		* @throws UnsupportedOperationException if the specified list's
148	<	* list-iterator does not support the <tt>set</tt> operation.
149	<	* @see Comparable
148	>	* list-iterator does not support the {@code set} operation.
149	>	* @throws IllegalArgumentException (optional) if the implementation
150	>	* detects that the natural ordering of the list elements is
151	>	* found to violate the {@link Comparable} contract
152		*/
153		public static <T extends Comparable<? super T>> void sort(List<T> list) {
154	<	Object[] a = list.toArray();
155	<	Arrays.sort(a);
156	<	ListIterator<T> i = list.listIterator();
157	<	for (int j=0; j<a.length; j++) {
158	<	i.next();
159	<	i.set((T)a[j]);
160	<	}
154	>	Object[] a = list.toArray();
155	>	Arrays.sort(a);
156	>	ListIterator<T> i = list.listIterator();
157	>	for (int j=0; j<a.length; j++) {
158	>	i.next();
159	>	i.set((T)a[j]);
160	>	}
161		}
162
163		/**
164		* Sorts the specified list according to the order induced by the
165		* specified comparator. All elements in the list must be <i>mutually
166		* comparable</i> using the specified comparator (that is,
167	<	* <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
168	<	* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
167	>	* {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
168	>	* for any elements {@code e1} and {@code e2} in the list).
169	>	*
170	>	* <p>This sort is guaranteed to be <i>stable</i>: equal elements will
171	>	* not be reordered as a result of the sort.
172		*
173	<	* This sort is guaranteed to be <i>stable</i>: equal elements will
134	<	* not be reordered as a result of the sort.<p>
173	>	* <p>The specified list must be modifiable, but need not be resizable.
174		*
175	<	* The sorting algorithm is a modified mergesort (in which the merge is
176	<	* omitted if the highest element in the low sublist is less than the
177	<	* lowest element in the high sublist). This algorithm offers guaranteed
178	<	* n log(n) performance.
175	>	* <p>Implementation note: This implementation is a stable, adaptive,
176	>	* iterative mergesort that requires far fewer than n lg(n) comparisons
177	>	* when the input array is partially sorted, while offering the
178	>	* performance of a traditional mergesort when the input array is
179	>	* randomly ordered. If the input array is nearly sorted, the
180	>	* implementation requires approximately n comparisons. Temporary
181	>	* storage requirements vary from a small constant for nearly sorted
182	>	* input arrays to n/2 object references for randomly ordered input
183	>	* arrays.
184	>	*
185	>	* <p>The implementation takes equal advantage of ascending and
186	>	* descending order in its input array, and can take advantage of
187	>	* ascending and descending order in different parts of the same
188	>	* input array. It is well-suited to merging two or more sorted arrays:
189	>	* simply concatenate the arrays and sort the resulting array.
190	>	*
191	>	* <p>The implementation was adapted from Tim Peters's list sort for Python
192	>	* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
193	>	* TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
194	>	* Sorting and Information Theoretic Complexity", in Proceedings of the
195	>	* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
196	>	* January 1993.
197		*
198	<	* The specified list must be modifiable, but need not be resizable.
142	<	* This implementation dumps the specified list into an array, sorts
198	>	* <p>This implementation dumps the specified list into an array, sorts
199		* the array, and iterates over the list resetting each element
200		* from the corresponding position in the array. This avoids the
201		* n<sup>2</sup> log(n) performance that would result from attempting
#	Line 147 \| Line 203 \| public class Collections {
203		*
204		* @param list the list to be sorted.
205		* @param c the comparator to determine the order of the list. A
206	<	* <tt>null</tt> value indicates that the elements' <i>natural
206	>	* {@code null} value indicates that the elements' <i>natural
207		* ordering</i> should be used.
208		* @throws ClassCastException if the list contains elements that are not
209	<	* <i>mutually comparable</i> using the specified comparator.
209	>	* <i>mutually comparable</i> using the specified comparator.
210		* @throws UnsupportedOperationException if the specified list's
211	<	* list-iterator does not support the <tt>set</tt> operation.
212	<	* @see Comparator
211	>	* list-iterator does not support the {@code set} operation.
212	>	* @throws IllegalArgumentException (optional) if the comparator is
213	>	* found to violate the {@link Comparator} contract
214		*/
215		public static <T> void sort(List<T> list, Comparator<? super T> c) {
216	<	Object[] a = list.toArray();
217	<	Arrays.sort(a, (Comparator)c);
218	<	ListIterator i = list.listIterator();
219	<	for (int j=0; j<a.length; j++) {
220	<	i.next();
221	<	i.set(a[j]);
222	<	}
216	>	Object[] a = list.toArray();
217	>	Arrays.sort(a, (Comparator)c);
218	>	ListIterator i = list.listIterator();
219	>	for (int j=0; j<a.length; j++) {
220	>	i.next();
221	>	i.set(a[j]);
222	>	}
223		}
224
225
226		/**
227		* Searches the specified list for the specified object using the binary
228		* search algorithm. The list must be sorted into ascending order
229	<	* according to the <i>natural ordering</i> of its elements (as by the
230	<	* <tt>sort(List)</tt> method, above) prior to making this call. If it is
231	<	* not sorted, the results are undefined. If the list contains multiple
232	<	* elements equal to the specified object, there is no guarantee which one
233	<	* will be found.<p>
229	>	* according to the {@linkplain Comparable natural ordering} of its
230	>	* elements (as by the {@link #sort(List)} method) prior to making this
231	>	* call. If it is not sorted, the results are undefined. If the list
232	>	* contains multiple elements equal to the specified object, there is no
233	>	* guarantee which one will be found.
234		*
235	<	* This method runs in log(n) time for a "random access" list (which
235	>	* <p>This method runs in log(n) time for a "random access" list (which
236		* provides near-constant-time positional access). If the specified list
237		* does not implement the {@link RandomAccess} interface and is large,
238		* this method will do an iterator-based binary search that performs
#	Line 184 \| Line 241 \| public class Collections {
241		* @param list the list to be searched.
242		* @param key the key to be searched for.
243		* @return the index of the search key, if it is contained in the list;
244	<	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
245	<	* <i>insertion point</i> is defined as the point at which the
246	<	* key would be inserted into the list: the index of the first
247	<	* element greater than the key, or <tt>list.size()</tt>, if all
248	<	* elements in the list are less than the specified key. Note
249	<	* that this guarantees that the return value will be >= 0 if
250	<	* and only if the key is found.
244	>	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
245	>	* <i>insertion point</i> is defined as the point at which the
246	>	* key would be inserted into the list: the index of the first
247	>	* element greater than the key, or <tt>list.size()</tt> if all
248	>	* elements in the list are less than the specified key. Note
249	>	* that this guarantees that the return value will be >= 0 if
250	>	* and only if the key is found.
251		* @throws ClassCastException if the list contains elements that are not
252	<	* <i>mutually comparable</i> (for example, strings and
253	<	* integers), or the search key in not mutually comparable
254	<	* with the elements of the list.
198	<	* @see Comparable
199	<	* @see #sort(List)
252	>	* <i>mutually comparable</i> (for example, strings and
253	>	* integers), or the search key is not mutually comparable
254	>	* with the elements of the list.
255		*/
256		public static <T>
257		int binarySearch(List<? extends Comparable<? super T>> list, T key) {
#	Line 209 \| Line 264 \| public class Collections {
264		private static <T>
265		int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
266		{
267	<	int low = 0;
268	<	int high = list.size()-1;
267	>	int low = 0;
268	>	int high = list.size()-1;
269	>
270	>	while (low <= high) {
271	>	int mid = (low + high) >>> 1;
272	>	Comparable<? super T> midVal = list.get(mid);
273	>	int cmp = midVal.compareTo(key);
274
275	<	while (low <= high) {
276	<	int mid = (low + high) >> 1;
277	<	Comparable<? super T> midVal = list.get(mid);
278	<	int cmp = midVal.compareTo(key);
279	<
280	<	if (cmp < 0)
281	<	low = mid + 1;
282	<	else if (cmp > 0)
223	<	high = mid - 1;
224	<	else
225	<	return mid; // key found
226	<	}
227	<	return -(low + 1); // key not found
275	>	if (cmp < 0)
276	>	low = mid + 1;
277	>	else if (cmp > 0)
278	>	high = mid - 1;
279	>	else
280	>	return mid; // key found
281	>	}
282	>	return -(low + 1); // key not found
283		}
284
285		private static <T>
286		int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
287		{
288	<	int low = 0;
289	<	int high = list.size()-1;
288	>	int low = 0;
289	>	int high = list.size()-1;
290		ListIterator<? extends Comparable<? super T>> i = list.listIterator();
291
292		while (low <= high) {
293	<	int mid = (low + high) >> 1;
293	>	int mid = (low + high) >>> 1;
294		Comparable<? super T> midVal = get(i, mid);
295		int cmp = midVal.compareTo(key);
296
#	Line 254 \| Line 309 \| public class Collections {
309		* list listIterator.
310		*/
311		private static <T> T get(ListIterator<? extends T> i, int index) {
312	<	T obj = null;
312	>	T obj = null;
313		int pos = i.nextIndex();
314		if (pos <= index) {
315		do {
#	Line 271 \| Line 326 \| public class Collections {
326		/**
327		* Searches the specified list for the specified object using the binary
328		* search algorithm. The list must be sorted into ascending order
329	<	* according to the specified comparator (as by the <tt>Sort(List,
330	<	* Comparator)</tt> method, above), prior to making this call. If it is
329	>	* according to the specified comparator (as by the
330	>	* {@link #sort(List, Comparator) sort(List, Comparator)}
331	>	* method), prior to making this call. If it is
332		* not sorted, the results are undefined. If the list contains multiple
333		* elements equal to the specified object, there is no guarantee which one
334	<	* will be found.<p>
334	>	* will be found.
335		*
336	<	* This method runs in log(n) time for a "random access" list (which
336	>	* <p>This method runs in log(n) time for a "random access" list (which
337		* provides near-constant-time positional access). If the specified list
338		* does not implement the {@link RandomAccess} interface and is large,
339		* this method will do an iterator-based binary search that performs
#	Line 285 \| Line 341 \| public class Collections {
341		*
342		* @param list the list to be searched.
343		* @param key the key to be searched for.
344	<	* @param c the comparator by which the list is ordered. A
345	<	* <tt>null</tt> value indicates that the elements' <i>natural
346	<	* ordering</i> should be used.
344	>	* @param c the comparator by which the list is ordered.
345	>	* A <tt>null</tt> value indicates that the elements'
346	>	* {@linkplain Comparable natural ordering} should be used.
347		* @return the index of the search key, if it is contained in the list;
348	<	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
349	<	* <i>insertion point</i> is defined as the point at which the
350	<	* key would be inserted into the list: the index of the first
351	<	* element greater than the key, or <tt>list.size()</tt>, if all
352	<	* elements in the list are less than the specified key. Note
353	<	* that this guarantees that the return value will be >= 0 if
354	<	* and only if the key is found.
348	>	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
349	>	* <i>insertion point</i> is defined as the point at which the
350	>	* key would be inserted into the list: the index of the first
351	>	* element greater than the key, or <tt>list.size()</tt> if all
352	>	* elements in the list are less than the specified key. Note
353	>	* that this guarantees that the return value will be >= 0 if
354	>	* and only if the key is found.
355		* @throws ClassCastException if the list contains elements that are not
356	<	* <i>mutually comparable</i> using the specified comparator,
357	<	* or the search key in not mutually comparable with the
358	<	* elements of the list using this comparator.
303	<	* @see Comparable
304	<	* @see #sort(List, Comparator)
356	>	* <i>mutually comparable</i> using the specified comparator,
357	>	* or the search key is not mutually comparable with the
358	>	* elements of the list using this comparator.
359		*/
360		public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
361		if (c==null)
#	Line 314 \| Line 368 \| public class Collections {
368		}
369
370		private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
371	<	int low = 0;
372	<	int high = l.size()-1;
371	>	int low = 0;
372	>	int high = l.size()-1;
373	>
374	>	while (low <= high) {
375	>	int mid = (low + high) >>> 1;
376	>	T midVal = l.get(mid);
377	>	int cmp = c.compare(midVal, key);
378
379	<	while (low <= high) {
380	<	int mid = (low + high) >> 1;
381	<	T midVal = l.get(mid);
382	<	int cmp = c.compare(midVal, key);
383	<
384	<	if (cmp < 0)
385	<	low = mid + 1;
386	<	else if (cmp > 0)
328	<	high = mid - 1;
329	<	else
330	<	return mid; // key found
331	<	}
332	<	return -(low + 1); // key not found
379	>	if (cmp < 0)
380	>	low = mid + 1;
381	>	else if (cmp > 0)
382	>	high = mid - 1;
383	>	else
384	>	return mid; // key found
385	>	}
386	>	return -(low + 1); // key not found
387		}
388
389		private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
390	<	int low = 0;
391	<	int high = l.size()-1;
390	>	int low = 0;
391	>	int high = l.size()-1;
392		ListIterator<? extends T> i = l.listIterator();
393
394		while (low <= high) {
395	<	int mid = (low + high) >> 1;
395	>	int mid = (low + high) >>> 1;
396		T midVal = get(i, mid);
397		int cmp = c.compare(midVal, key);
398
#	Line 373 \| Line 427 \| public class Collections {
427		ListIterator fwd = list.listIterator();
428		ListIterator rev = list.listIterator(size);
429		for (int i=0, mid=list.size()>>1; i<mid; i++) {
430	<	Object tmp = fwd.next();
430	>	Object tmp = fwd.next();
431		fwd.set(rev.previous());
432		rev.set(tmp);
433		}
#	Line 474 \| Line 528 \| public class Collections {
528		* @since 1.4
529		*/
530		public static void swap(List<?> list, int i, int j) {
531	<	final List l = list;
532	<	l.set(i, l.set(j, l.get(i)));
531	>	final List l = list;
532	>	l.set(i, l.set(j, l.get(i)));
533		}
534
535		/**
#	Line 496 \| Line 550 \| public class Collections {
550		* @param list the list to be filled with the specified element.
551		* @param obj The element with which to fill the specified list.
552		* @throws UnsupportedOperationException if the specified list or its
553	<	* list-iterator does not support the <tt>set</tt> operation.
553	>	* list-iterator does not support the <tt>set</tt> operation.
554		*/
555		public static <T> void fill(List<? super T> list, T obj) {
556		int size = list.size();
#	Line 540 \| Line 594 \| public class Collections {
594		dest.set(i, src.get(i));
595		} else {
596		ListIterator<? super T> di=dest.listIterator();
597	<	ListIterator<? extends T> si=src.listIterator();
597	>	ListIterator<? extends T> si=src.listIterator();
598		for (int i=0; i<srcSize; i++) {
599		di.next();
600		di.set(si.next());
#	Line 564 \| Line 618 \| public class Collections {
618		* @return the minimum element of the given collection, according
619		* to the <i>natural ordering</i> of its elements.
620		* @throws ClassCastException if the collection contains elements that are
621	<	* not <i>mutually comparable</i> (for example, strings and
622	<	* integers).
621	>	* not <i>mutually comparable</i> (for example, strings and
622	>	* integers).
623		* @throws NoSuchElementException if the collection is empty.
624		* @see Comparable
625		*/
626		public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
627	<	Iterator<? extends T> i = coll.iterator();
628	<	T candidate = i.next();
627	>	Iterator<? extends T> i = coll.iterator();
628	>	T candidate = i.next();
629
630		while (i.hasNext()) {
631	<	T next = i.next();
632	<	if (next.compareTo(candidate) < 0)
633	<	candidate = next;
634	<	}
635	<	return candidate;
631	>	T next = i.next();
632	>	if (next.compareTo(candidate) < 0)
633	>	candidate = next;
634	>	}
635	>	return candidate;
636		}
637
638		/**
#	Line 599 \| Line 653 \| public class Collections {
653		* @return the minimum element of the given collection, according
654		* to the specified comparator.
655		* @throws ClassCastException if the collection contains elements that are
656	<	* not <i>mutually comparable</i> using the specified comparator.
656	>	* not <i>mutually comparable</i> using the specified comparator.
657		* @throws NoSuchElementException if the collection is empty.
658		* @see Comparable
659		*/
#	Line 607 \| Line 661 \| public class Collections {
661		if (comp==null)
662		return (T)min((Collection<SelfComparable>) (Collection) coll);
663
664	<	Iterator<? extends T> i = coll.iterator();
665	<	T candidate = i.next();
664	>	Iterator<? extends T> i = coll.iterator();
665	>	T candidate = i.next();
666
667		while (i.hasNext()) {
668	<	T next = i.next();
669	<	if (comp.compare(next, candidate) < 0)
670	<	candidate = next;
671	<	}
672	<	return candidate;
668	>	T next = i.next();
669	>	if (comp.compare(next, candidate) < 0)
670	>	candidate = next;
671	>	}
672	>	return candidate;
673		}
674
675		/**
#	Line 634 \| Line 688 \| public class Collections {
688		* @return the maximum element of the given collection, according
689		* to the <i>natural ordering</i> of its elements.
690		* @throws ClassCastException if the collection contains elements that are
691	<	* not <i>mutually comparable</i> (for example, strings and
691	>	* not <i>mutually comparable</i> (for example, strings and
692		* integers).
693		* @throws NoSuchElementException if the collection is empty.
694		* @see Comparable
695		*/
696		public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
697	<	Iterator<? extends T> i = coll.iterator();
698	<	T candidate = i.next();
697	>	Iterator<? extends T> i = coll.iterator();
698	>	T candidate = i.next();
699
700		while (i.hasNext()) {
701	<	T next = i.next();
702	<	if (next.compareTo(candidate) > 0)
703	<	candidate = next;
704	<	}
705	<	return candidate;
701	>	T next = i.next();
702	>	if (next.compareTo(candidate) > 0)
703	>	candidate = next;
704	>	}
705	>	return candidate;
706		}
707
708		/**
#	Line 669 \| Line 723 \| public class Collections {
723		* @return the maximum element of the given collection, according
724		* to the specified comparator.
725		* @throws ClassCastException if the collection contains elements that are
726	<	* not <i>mutually comparable</i> using the specified comparator.
726	>	* not <i>mutually comparable</i> using the specified comparator.
727		* @throws NoSuchElementException if the collection is empty.
728		* @see Comparable
729		*/
#	Line 677 \| Line 731 \| public class Collections {
731		if (comp==null)
732		return (T)max((Collection<SelfComparable>) (Collection) coll);
733
734	<	Iterator<? extends T> i = coll.iterator();
735	<	T candidate = i.next();
734	>	Iterator<? extends T> i = coll.iterator();
735	>	T candidate = i.next();
736
737		while (i.hasNext()) {
738	<	T next = i.next();
739	<	if (comp.compare(next, candidate) > 0)
740	<	candidate = next;
741	<	}
742	<	return candidate;
738	>	T next = i.next();
739	>	if (comp.compare(next, candidate) > 0)
740	>	candidate = next;
741	>	}
742	>	return candidate;
743		}
744
745		/**
#	Line 745 \| Line 799 \| public class Collections {
799		*/
800		public static void rotate(List<?> list, int distance) {
801		if (list instanceof RandomAccess \|\| list.size() < ROTATE_THRESHOLD)
802	<	rotate1((List)list, distance);
802	>	rotate1(list, distance);
803		else
804	<	rotate2((List)list, distance);
804	>	rotate2(list, distance);
805		}
806
807		private static <T> void rotate1(List<T> list, int distance) {
#	Line 769 \| Line 823 \| public class Collections {
823		i -= size;
824		displaced = list.set(i, displaced);
825		nMoved ++;
826	<	} while(i != cycleStart);
826	>	} while (i != cycleStart);
827		}
828		}
829
#	Line 977 \| Line 1031 \| public class Collections {
1031		* is serializable.
1032		*
1033		* @param c the collection for which an unmodifiable view is to be
1034	<	* returned.
1034	>	* returned.
1035		* @return an unmodifiable view of the specified collection.
1036		*/
1037		public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
1038	<	return new UnmodifiableCollection<T>(c);
1038	>	return new UnmodifiableCollection<T>(c);
1039		}
1040
1041		/**
1042		* @serial include
1043		*/
1044		static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
1045	<	// use serialVersionUID from JDK 1.2.2 for interoperability
992	<	private static final long serialVersionUID = 1820017752578914078L;
1045	>	private static final long serialVersionUID = 1820017752578914078L;
1046
1047	<	final Collection<? extends E> c;
1047	>	final Collection<? extends E> c;
1048
1049	<	UnmodifiableCollection(Collection<? extends E> c) {
1049	>	UnmodifiableCollection(Collection<? extends E> c) {
1050		if (c==null)
1051		throw new NullPointerException();
1052		this.c = c;
1053		}
1054
1055	<	public int size() {return c.size();}
1056	<	public boolean isEmpty() {return c.isEmpty();}
1057	<	public boolean contains(Object o) {return c.contains(o);}
1058	<	public Object[] toArray() {return c.toArray();}
1059	<	public <T> T[] toArray(T[] a) {return c.toArray(a);}
1055	>	public int size() {return c.size();}
1056	>	public boolean isEmpty() {return c.isEmpty();}
1057	>	public boolean contains(Object o) {return c.contains(o);}
1058	>	public Object[] toArray() {return c.toArray();}
1059	>	public <T> T[] toArray(T[] a) {return c.toArray(a);}
1060		public String toString() {return c.toString();}
1061
1062	<	public Iterator<E> iterator() {
1063	<	return new Iterator<E>() {
1064	<	Iterator<? extends E> i = c.iterator();
1065	<
1066	<	public boolean hasNext() {return i.hasNext();}
1067	<	public E next() {return i.next();}
1068	<	public void remove() {
1069	<	throw new UnsupportedOperationException();
1062	>	public Iterator<E> iterator() {
1063	>	return new Iterator<E>() {
1064	>	private final Iterator<? extends E> i = c.iterator();
1065	>
1066	>	public boolean hasNext() {return i.hasNext();}
1067	>	public E next() {return i.next();}
1068	>	public void remove() {
1069	>	throw new UnsupportedOperationException();
1070		}
1071	<	};
1071	>	};
1072		}
1073
1074	<	public boolean add(E e){
1075	<	throw new UnsupportedOperationException();
1074	>	public boolean add(E e) {
1075	>	throw new UnsupportedOperationException();
1076		}
1077	<	public boolean remove(Object o) {
1078	<	throw new UnsupportedOperationException();
1077	>	public boolean remove(Object o) {
1078	>	throw new UnsupportedOperationException();
1079		}
1080
1081	<	public boolean containsAll(Collection<?> coll) {
1082	<	return c.containsAll(coll);
1081	>	public boolean containsAll(Collection<?> coll) {
1082	>	return c.containsAll(coll);
1083		}
1084	<	public boolean addAll(Collection<? extends E> coll) {
1085	<	throw new UnsupportedOperationException();
1084	>	public boolean addAll(Collection<? extends E> coll) {
1085	>	throw new UnsupportedOperationException();
1086		}
1087	<	public boolean removeAll(Collection<?> coll) {
1088	<	throw new UnsupportedOperationException();
1087	>	public boolean removeAll(Collection<?> coll) {
1088	>	throw new UnsupportedOperationException();
1089		}
1090	<	public boolean retainAll(Collection<?> coll) {
1091	<	throw new UnsupportedOperationException();
1090	>	public boolean retainAll(Collection<?> coll) {
1091	>	throw new UnsupportedOperationException();
1092		}
1093	<	public void clear() {
1094	<	throw new UnsupportedOperationException();
1093	>	public void clear() {
1094	>	throw new UnsupportedOperationException();
1095		}
1096		}
1097
#	Line 1056 \| Line 1109 \| public class Collections {
1109		* @return an unmodifiable view of the specified set.
1110		*/
1111		public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1112	<	return new UnmodifiableSet<T>(s);
1112	>	return new UnmodifiableSet<T>(s);
1113		}
1114
1115		/**
1116		* @serial include
1117		*/
1118		static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
1119	<	implements Set<E>, Serializable {
1120	<	private static final long serialVersionUID = -9215047833775013803L;
1119	>	implements Set<E>, Serializable {
1120	>	private static final long serialVersionUID = -9215047833775013803L;
1121
1122	<	UnmodifiableSet(Set<? extends E> s) {super(s);}
1123	<	public boolean equals(Object o) {return c.equals(o);}
1124	<	public int hashCode() {return c.hashCode();}
1122	>	UnmodifiableSet(Set<? extends E> s) {super(s);}
1123	>	public boolean equals(Object o) {return o == this \|\| c.equals(o);}
1124	>	public int hashCode() {return c.hashCode();}
1125		}
1126
1127		/**
#	Line 1088 \| Line 1141 \| public class Collections {
1141		* @return an unmodifiable view of the specified sorted set.
1142		*/
1143		public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
1144	<	return new UnmodifiableSortedSet<T>(s);
1144	>	return new UnmodifiableSortedSet<T>(s);
1145		}
1146
1147		/**
1148		* @serial include
1149		*/
1150		static class UnmodifiableSortedSet<E>
1151	<	extends UnmodifiableSet<E>
1152	<	implements SortedSet<E>, Serializable {
1153	<	private static final long serialVersionUID = -4929149591599911165L;
1151	>	extends UnmodifiableSet<E>
1152	>	implements SortedSet<E>, Serializable {
1153	>	private static final long serialVersionUID = -4929149591599911165L;
1154		private final SortedSet<E> ss;
1155
1156	<	UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1156	>	UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1157
1158		public Comparator<? super E> comparator() {return ss.comparator();}
1159
#	Line 1114 \| Line 1167 \| public class Collections {
1167		return new UnmodifiableSortedSet<E>(ss.tailSet(fromElement));
1168		}
1169
1170	<	public E first() {return ss.first();}
1171	<	public E last() {return ss.last();}
1170	>	public E first() {return ss.first();}
1171	>	public E last() {return ss.last();}
1172		}
1173
1174		/**
#	Line 1134 \| Line 1187 \| public class Collections {
1187		* @return an unmodifiable view of the specified list.
1188		*/
1189		public static <T> List<T> unmodifiableList(List<? extends T> list) {
1190	<	return (list instanceof RandomAccess ?
1190	>	return (list instanceof RandomAccess ?
1191		new UnmodifiableRandomAccessList<T>(list) :
1192		new UnmodifiableList<T>(list));
1193		}
#	Line 1143 \| Line 1196 \| public class Collections {
1196		* @serial include
1197		*/
1198		static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1199	<	implements List<E> {
1200	<	static final long serialVersionUID = -283967356065247728L;
1201	<	final List<? extends E> list;
1202	<
1203	<	UnmodifiableList(List<? extends E> list) {
1204	<	super(list);
1205	<	this.list = list;
1206	<	}
1154	<
1155	<	public boolean equals(Object o) {return list.equals(o);}
1156	<	public int hashCode() {return list.hashCode();}
1157	<
1158	<	public E get(int index) {return list.get(index);}
1159	<	public E set(int index, E element) {
1160	<	throw new UnsupportedOperationException();
1161	<	}
1162	<	public void add(int index, E element) {
1163	<	throw new UnsupportedOperationException();
1164	<	}
1165	<	public E remove(int index) {
1166	<	throw new UnsupportedOperationException();
1167	<	}
1168	<	public int indexOf(Object o) {return list.indexOf(o);}
1169	<	public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1170	<	public boolean addAll(int index, Collection<? extends E> c) {
1171	<	throw new UnsupportedOperationException();
1172	<	}
1173	<	public ListIterator<E> listIterator() {return listIterator(0);}
1174	<
1175	<	public ListIterator<E> listIterator(final int index) {
1176	<	return new ListIterator<E>() {
1177	<	ListIterator<? extends E> i = list.listIterator(index);
1178	<
1179	<	public boolean hasNext() {return i.hasNext();}
1180	<	public E next() {return i.next();}
1181	<	public boolean hasPrevious() {return i.hasPrevious();}
1182	<	public E previous() {return i.previous();}
1183	<	public int nextIndex() {return i.nextIndex();}
1184	<	public int previousIndex() {return i.previousIndex();}
1199	>	implements List<E> {
1200	>	private static final long serialVersionUID = -283967356065247728L;
1201	>	final List<? extends E> list;
1202	>
1203	>	UnmodifiableList(List<? extends E> list) {
1204	>	super(list);
1205	>	this.list = list;
1206	>	}
1207
1208	<	public void remove() {
1209	<	throw new UnsupportedOperationException();
1208	>	public boolean equals(Object o) {return o == this \|\| list.equals(o);}
1209	>	public int hashCode() {return list.hashCode();}
1210	>
1211	>	public E get(int index) {return list.get(index);}
1212	>	public E set(int index, E element) {
1213	>	throw new UnsupportedOperationException();
1214	>	}
1215	>	public void add(int index, E element) {
1216	>	throw new UnsupportedOperationException();
1217	>	}
1218	>	public E remove(int index) {
1219	>	throw new UnsupportedOperationException();
1220	>	}
1221	>	public int indexOf(Object o) {return list.indexOf(o);}
1222	>	public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1223	>	public boolean addAll(int index, Collection<? extends E> c) {
1224	>	throw new UnsupportedOperationException();
1225	>	}
1226	>	public ListIterator<E> listIterator() {return listIterator(0);}
1227	>
1228	>	public ListIterator<E> listIterator(final int index) {
1229	>	return new ListIterator<E>() {
1230	>	private final ListIterator<? extends E> i
1231	>	= list.listIterator(index);
1232	>
1233	>	public boolean hasNext() {return i.hasNext();}
1234	>	public E next() {return i.next();}
1235	>	public boolean hasPrevious() {return i.hasPrevious();}
1236	>	public E previous() {return i.previous();}
1237	>	public int nextIndex() {return i.nextIndex();}
1238	>	public int previousIndex() {return i.previousIndex();}
1239	>
1240	>	public void remove() {
1241	>	throw new UnsupportedOperationException();
1242		}
1243	<	public void set(E e) {
1244	<	throw new UnsupportedOperationException();
1243	>	public void set(E e) {
1244	>	throw new UnsupportedOperationException();
1245		}
1246	<	public void add(E e) {
1247	<	throw new UnsupportedOperationException();
1246	>	public void add(E e) {
1247	>	throw new UnsupportedOperationException();
1248		}
1249	<	};
1250	<	}
1249	>	};
1250	>	}
1251
1252	<	public List<E> subList(int fromIndex, int toIndex) {
1252	>	public List<E> subList(int fromIndex, int toIndex) {
1253		return new UnmodifiableList<E>(list.subList(fromIndex, toIndex));
1254		}
1255
#	Line 1213 \| Line 1267 \| public class Collections {
1267		*/
1268		private Object readResolve() {
1269		return (list instanceof RandomAccess
1270	<	? new UnmodifiableRandomAccessList<E>(list)
1271	<	: this);
1270	>	? new UnmodifiableRandomAccessList<E>(list)
1271	>	: this);
1272		}
1273		}
1274
#	Line 1228 \| Line 1282 \| public class Collections {
1282		super(list);
1283		}
1284
1285	<	public List<E> subList(int fromIndex, int toIndex) {
1285	>	public List<E> subList(int fromIndex, int toIndex) {
1286		return new UnmodifiableRandomAccessList<E>(
1287		list.subList(fromIndex, toIndex));
1288		}
#	Line 1261 \| Line 1315 \| public class Collections {
1315		* @return an unmodifiable view of the specified map.
1316		*/
1317		public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
1318	<	return new UnmodifiableMap<K,V>(m);
1318	>	return new UnmodifiableMap<K,V>(m);
1319		}
1320
1321		/**
1322		* @serial include
1323		*/
1324		private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
1325	<	// use serialVersionUID from JDK 1.2.2 for interoperability
1272	<	private static final long serialVersionUID = -1034234728574286014L;
1325	>	private static final long serialVersionUID = -1034234728574286014L;
1326
1327	<	private final Map<? extends K, ? extends V> m;
1327	>	private final Map<? extends K, ? extends V> m;
1328
1329	<	UnmodifiableMap(Map<? extends K, ? extends V> m) {
1329	>	UnmodifiableMap(Map<? extends K, ? extends V> m) {
1330		if (m==null)
1331		throw new NullPointerException();
1332		this.m = m;
1333		}
1334
1335	<	public int size() {return m.size();}
1336	<	public boolean isEmpty() {return m.isEmpty();}
1337	<	public boolean containsKey(Object key) {return m.containsKey(key);}
1338	<	public boolean containsValue(Object val) {return m.containsValue(val);}
1339	<	public V get(Object key) {return m.get(key);}
1340	<
1341	<	public V put(K key, V value) {
1342	<	throw new UnsupportedOperationException();
1343	<	}
1344	<	public V remove(Object key) {
1345	<	throw new UnsupportedOperationException();
1346	<	}
1347	<	public void putAll(Map<? extends K, ? extends V> m) {
1348	<	throw new UnsupportedOperationException();
1349	<	}
1350	<	public void clear() {
1351	<	throw new UnsupportedOperationException();
1352	<	}
1353	<
1354	<	private transient Set<K> keySet = null;
1355	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1356	<	private transient Collection<V> values = null;
1357	<
1358	<	public Set<K> keySet() {
1359	<	if (keySet==null)
1360	<	keySet = unmodifiableSet(m.keySet());
1361	<	return keySet;
1362	<	}
1363	<
1364	<	public Set<Map.Entry<K,V>> entrySet() {
1365	<	if (entrySet==null)
1366	<	entrySet = new UnmodifiableEntrySet<K,V>(m.entrySet());
1367	<	return entrySet;
1368	<	}
1369	<
1370	<	public Collection<V> values() {
1371	<	if (values==null)
1372	<	values = unmodifiableCollection(m.values());
1373	<	return values;
1374	<	}
1335	>	public int size() {return m.size();}
1336	>	public boolean isEmpty() {return m.isEmpty();}
1337	>	public boolean containsKey(Object key) {return m.containsKey(key);}
1338	>	public boolean containsValue(Object val) {return m.containsValue(val);}
1339	>	public V get(Object key) {return m.get(key);}
1340	>
1341	>	public V put(K key, V value) {
1342	>	throw new UnsupportedOperationException();
1343	>	}
1344	>	public V remove(Object key) {
1345	>	throw new UnsupportedOperationException();
1346	>	}
1347	>	public void putAll(Map<? extends K, ? extends V> m) {
1348	>	throw new UnsupportedOperationException();
1349	>	}
1350	>	public void clear() {
1351	>	throw new UnsupportedOperationException();
1352	>	}
1353	>
1354	>	private transient Set<K> keySet = null;
1355	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1356	>	private transient Collection<V> values = null;
1357	>
1358	>	public Set<K> keySet() {
1359	>	if (keySet==null)
1360	>	keySet = unmodifiableSet(m.keySet());
1361	>	return keySet;
1362	>	}
1363	>
1364	>	public Set<Map.Entry<K,V>> entrySet() {
1365	>	if (entrySet==null)
1366	>	entrySet = new UnmodifiableEntrySet<K,V>(m.entrySet());
1367	>	return entrySet;
1368	>	}
1369	>
1370	>	public Collection<V> values() {
1371	>	if (values==null)
1372	>	values = unmodifiableCollection(m.values());
1373	>	return values;
1374	>	}
1375
1376	<	public boolean equals(Object o) {return m.equals(o);}
1377	<	public int hashCode() {return m.hashCode();}
1376	>	public boolean equals(Object o) {return o == this \|\| m.equals(o);}
1377	>	public int hashCode() {return m.hashCode();}
1378		public String toString() {return m.toString();}
1379
1380		/**
#	Line 1333 \| Line 1386 \| public class Collections {
1386		* @serial include
1387		*/
1388		static class UnmodifiableEntrySet<K,V>
1389	<	extends UnmodifiableSet<Map.Entry<K,V>> {
1390	<	private static final long serialVersionUID = 7854390611657943733L;
1389	>	extends UnmodifiableSet<Map.Entry<K,V>> {
1390	>	private static final long serialVersionUID = 7854390611657943733L;
1391
1392		UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1393		super((Set)s);
1394		}
1395		public Iterator<Map.Entry<K,V>> iterator() {
1396		return new Iterator<Map.Entry<K,V>>() {
1397	<	Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1397	>	private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1398
1399		public boolean hasNext() {
1400		return i.hasNext();
1401		}
1402	<	public Map.Entry<K,V> next() {
1403	<	return new UnmodifiableEntry<K,V>(i.next());
1402	>	public Map.Entry<K,V> next() {
1403	>	return new UnmodifiableEntry<K,V>(i.next());
1404		}
1405		public void remove() {
1406		throw new UnsupportedOperationException();
#	Line 1366 \| Line 1419 \| public class Collections {
1419		// We don't pass a to c.toArray, to avoid window of
1420		// vulnerability wherein an unscrupulous multithreaded client
1421		// could get his hands on raw (unwrapped) Entries from c.
1422	<	Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1422	>	Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1423
1424		for (int i=0; i<arr.length; i++)
1425		arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]);
#	Line 1389 \| Line 1442 \| public class Collections {
1442		public boolean contains(Object o) {
1443		if (!(o instanceof Map.Entry))
1444		return false;
1445	<	return c.contains(new UnmodifiableEntry<K,V>((Map.Entry<K,V>) o));
1445	>	return c.contains(
1446	>	new UnmodifiableEntry<Object,Object>((Map.Entry<?,?>) o));
1447		}
1448
1449		/**
#	Line 1398 \| Line 1452 \| public class Collections {
1452		* when o is a Map.Entry, and calls o.setValue.
1453		*/
1454		public boolean containsAll(Collection<?> coll) {
1455	<	Iterator<?> e = coll.iterator();
1456	<	while (e.hasNext())
1457	<	if (!contains(e.next())) // Invokes safe contains() above
1455	>	Iterator<?> it = coll.iterator();
1456	>	while (it.hasNext())
1457	>	if (!contains(it.next())) // Invokes safe contains() above
1458		return false;
1459		return true;
1460		}
#	Line 1428 \| Line 1482 \| public class Collections {
1482
1483		UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1484
1485	<	public K getKey() {return e.getKey();}
1486	<	public V getValue() {return e.getValue();}
1485	>	public K getKey() {return e.getKey();}
1486	>	public V getValue() {return e.getValue();}
1487		public V setValue(V value) {
1488		throw new UnsupportedOperationException();
1489		}
1490	<	public int hashCode() {return e.hashCode();}
1490	>	public int hashCode() {return e.hashCode();}
1491		public boolean equals(Object o) {
1492		if (!(o instanceof Map.Entry))
1493		return false;
#	Line 1441 \| Line 1495 \| public class Collections {
1495		return eq(e.getKey(), t.getKey()) &&
1496		eq(e.getValue(), t.getValue());
1497		}
1498	<	public String toString() {return e.toString();}
1498	>	public String toString() {return e.toString();}
1499		}
1500		}
1501		}
#	Line 1463 \| Line 1517 \| public class Collections {
1517		* @return an unmodifiable view of the specified sorted map.
1518		*/
1519		public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1520	<	return new UnmodifiableSortedMap<K,V>(m);
1520	>	return new UnmodifiableSortedMap<K,V>(m);
1521		}
1522
1523		/**
1524		* @serial include
1525		*/
1526		static class UnmodifiableSortedMap<K,V>
1527	<	extends UnmodifiableMap<K,V>
1528	<	implements SortedMap<K,V>, Serializable {
1529	<	private static final long serialVersionUID = -8806743815996713206L;
1527	>	extends UnmodifiableMap<K,V>
1528	>	implements SortedMap<K,V>, Serializable {
1529	>	private static final long serialVersionUID = -8806743815996713206L;
1530
1531		private final SortedMap<K, ? extends V> sm;
1532
1533	<	UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1533	>	UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1534
1535		public Comparator<? super K> comparator() {return sm.comparator();}
1536
#	Line 1508 \| Line 1562 \| public class Collections {
1562		* <pre>
1563		* Collection c = Collections.synchronizedCollection(myCollection);
1564		* ...
1565	<	* synchronized(c) {
1565	>	* synchronized (c) {
1566		* Iterator i = c.iterator(); // Must be in the synchronized block
1567		* while (i.hasNext())
1568		* foo(i.next());
#	Line 1529 \| Line 1583 \| public class Collections {
1583		* @return a synchronized view of the specified collection.
1584		*/
1585		public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1586	<	return new SynchronizedCollection<T>(c);
1586	>	return new SynchronizedCollection<T>(c);
1587		}
1588
1589		static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1590	<	return new SynchronizedCollection<T>(c, mutex);
1590	>	return new SynchronizedCollection<T>(c, mutex);
1591		}
1592
1593		/**
1594		* @serial include
1595		*/
1596		static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1597	<	// use serialVersionUID from JDK 1.2.2 for interoperability
1544	<	private static final long serialVersionUID = 3053995032091335093L;
1597	>	private static final long serialVersionUID = 3053995032091335093L;
1598
1599	<	final Collection<E> c; // Backing Collection
1600	<	final Object mutex; // Object on which to synchronize
1599	>	final Collection<E> c; // Backing Collection
1600	>	final Object mutex; // Object on which to synchronize
1601
1602	<	SynchronizedCollection(Collection<E> c) {
1602	>	SynchronizedCollection(Collection<E> c) {
1603		if (c==null)
1604		throw new NullPointerException();
1605	<	this.c = c;
1605	>	this.c = c;
1606		mutex = this;
1607		}
1608	<	SynchronizedCollection(Collection<E> c, Object mutex) {
1609	<	this.c = c;
1608	>	SynchronizedCollection(Collection<E> c, Object mutex) {
1609	>	this.c = c;
1610		this.mutex = mutex;
1611		}
1612
1613	<	public int size() {
1614	<	synchronized(mutex) {return c.size();}
1613	>	public int size() {
1614	>	synchronized (mutex) {return c.size();}
1615		}
1616	<	public boolean isEmpty() {
1617	<	synchronized(mutex) {return c.isEmpty();}
1616	>	public boolean isEmpty() {
1617	>	synchronized (mutex) {return c.isEmpty();}
1618		}
1619	<	public boolean contains(Object o) {
1620	<	synchronized(mutex) {return c.contains(o);}
1619	>	public boolean contains(Object o) {
1620	>	synchronized (mutex) {return c.contains(o);}
1621		}
1622	<	public Object[] toArray() {
1623	<	synchronized(mutex) {return c.toArray();}
1622	>	public Object[] toArray() {
1623	>	synchronized (mutex) {return c.toArray();}
1624		}
1625	<	public <T> T[] toArray(T[] a) {
1626	<	synchronized(mutex) {return c.toArray(a);}
1625	>	public <T> T[] toArray(T[] a) {
1626	>	synchronized (mutex) {return c.toArray(a);}
1627		}
1628
1629	<	public Iterator<E> iterator() {
1629	>	public Iterator<E> iterator() {
1630		return c.iterator(); // Must be manually synched by user!
1631		}
1632
1633	<	public boolean add(E e) {
1634	<	synchronized(mutex) {return c.add(e);}
1633	>	public boolean add(E e) {
1634	>	synchronized (mutex) {return c.add(e);}
1635		}
1636	<	public boolean remove(Object o) {
1637	<	synchronized(mutex) {return c.remove(o);}
1636	>	public boolean remove(Object o) {
1637	>	synchronized (mutex) {return c.remove(o);}
1638		}
1639
1640	<	public boolean containsAll(Collection<?> coll) {
1641	<	synchronized(mutex) {return c.containsAll(coll);}
1640	>	public boolean containsAll(Collection<?> coll) {
1641	>	synchronized (mutex) {return c.containsAll(coll);}
1642		}
1643	<	public boolean addAll(Collection<? extends E> coll) {
1644	<	synchronized(mutex) {return c.addAll(coll);}
1643	>	public boolean addAll(Collection<? extends E> coll) {
1644	>	synchronized (mutex) {return c.addAll(coll);}
1645		}
1646	<	public boolean removeAll(Collection<?> coll) {
1647	<	synchronized(mutex) {return c.removeAll(coll);}
1646	>	public boolean removeAll(Collection<?> coll) {
1647	>	synchronized (mutex) {return c.removeAll(coll);}
1648		}
1649	<	public boolean retainAll(Collection<?> coll) {
1650	<	synchronized(mutex) {return c.retainAll(coll);}
1649	>	public boolean retainAll(Collection<?> coll) {
1650	>	synchronized (mutex) {return c.retainAll(coll);}
1651		}
1652	<	public void clear() {
1653	<	synchronized(mutex) {c.clear();}
1652	>	public void clear() {
1653	>	synchronized (mutex) {c.clear();}
1654		}
1655	<	public String toString() {
1656	<	synchronized(mutex) {return c.toString();}
1655	>	public String toString() {
1656	>	synchronized (mutex) {return c.toString();}
1657		}
1658		private void writeObject(ObjectOutputStream s) throws IOException {
1659	<	synchronized(mutex) {s.defaultWriteObject();}
1659	>	synchronized (mutex) {s.defaultWriteObject();}
1660		}
1661		}
1662
#	Line 1618 \| Line 1671 \| public class Collections {
1671		* <pre>
1672		* Set s = Collections.synchronizedSet(new HashSet());
1673		* ...
1674	<	* synchronized(s) {
1674	>	* synchronized (s) {
1675		* Iterator i = s.iterator(); // Must be in the synchronized block
1676		* while (i.hasNext())
1677		* foo(i.next());
#	Line 1633 \| Line 1686 \| public class Collections {
1686		* @return a synchronized view of the specified set.
1687		*/
1688		public static <T> Set<T> synchronizedSet(Set<T> s) {
1689	<	return new SynchronizedSet<T>(s);
1689	>	return new SynchronizedSet<T>(s);
1690		}
1691
1692		static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1693	<	return new SynchronizedSet<T>(s, mutex);
1693	>	return new SynchronizedSet<T>(s, mutex);
1694		}
1695
1696		/**
1697		* @serial include
1698		*/
1699		static class SynchronizedSet<E>
1700	<	extends SynchronizedCollection<E>
1701	<	implements Set<E> {
1702	<	private static final long serialVersionUID = 487447009682186044L;
1700	>	extends SynchronizedCollection<E>
1701	>	implements Set<E> {
1702	>	private static final long serialVersionUID = 487447009682186044L;
1703
1704	<	SynchronizedSet(Set<E> s) {
1704	>	SynchronizedSet(Set<E> s) {
1705		super(s);
1706		}
1707	<	SynchronizedSet(Set<E> s, Object mutex) {
1707	>	SynchronizedSet(Set<E> s, Object mutex) {
1708		super(s, mutex);
1709		}
1710
1711	<	public boolean equals(Object o) {
1712	<	synchronized(mutex) {return c.equals(o);}
1711	>	public boolean equals(Object o) {
1712	>	synchronized (mutex) {return c.equals(o);}
1713		}
1714	<	public int hashCode() {
1715	<	synchronized(mutex) {return c.hashCode();}
1714	>	public int hashCode() {
1715	>	synchronized (mutex) {return c.hashCode();}
1716		}
1717		}
1718
#	Line 1675 \| Line 1728 \| public class Collections {
1728		* <pre>
1729		* SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1730		* ...
1731	<	* synchronized(s) {
1731	>	* synchronized (s) {
1732		* Iterator i = s.iterator(); // Must be in the synchronized block
1733		* while (i.hasNext())
1734		* foo(i.next());
#	Line 1686 \| Line 1739 \| public class Collections {
1739		* SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1740		* SortedSet s2 = s.headSet(foo);
1741		* ...
1742	<	* synchronized(s) { // Note: s, not s2!!!
1742	>	* synchronized (s) { // Note: s, not s2!!!
1743		* Iterator i = s2.iterator(); // Must be in the synchronized block
1744		* while (i.hasNext())
1745		* foo(i.next());
#	Line 1701 \| Line 1754 \| public class Collections {
1754		* @return a synchronized view of the specified sorted set.
1755		*/
1756		public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1757	<	return new SynchronizedSortedSet<T>(s);
1757	>	return new SynchronizedSortedSet<T>(s);
1758		}
1759
1760		/**
1761		* @serial include
1762		*/
1763		static class SynchronizedSortedSet<E>
1764	<	extends SynchronizedSet<E>
1765	<	implements SortedSet<E>
1764	>	extends SynchronizedSet<E>
1765	>	implements SortedSet<E>
1766		{
1767	<	private static final long serialVersionUID = 8695801310862127406L;
1767	>	private static final long serialVersionUID = 8695801310862127406L;
1768
1769	<	final private SortedSet<E> ss;
1769	>	private final SortedSet<E> ss;
1770
1771	<	SynchronizedSortedSet(SortedSet<E> s) {
1771	>	SynchronizedSortedSet(SortedSet<E> s) {
1772		super(s);
1773		ss = s;
1774		}
1775	<	SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1775	>	SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1776		super(s, mutex);
1777		ss = s;
1778		}
1779
1780	<	public Comparator<? super E> comparator() {
1781	<	synchronized(mutex) {return ss.comparator();}
1780	>	public Comparator<? super E> comparator() {
1781	>	synchronized (mutex) {return ss.comparator();}
1782		}
1783
1784		public SortedSet<E> subSet(E fromElement, E toElement) {
1785	<	synchronized(mutex) {
1785	>	synchronized (mutex) {
1786		return new SynchronizedSortedSet<E>(
1787		ss.subSet(fromElement, toElement), mutex);
1788		}
1789		}
1790		public SortedSet<E> headSet(E toElement) {
1791	<	synchronized(mutex) {
1791	>	synchronized (mutex) {
1792		return new SynchronizedSortedSet<E>(ss.headSet(toElement), mutex);
1793		}
1794		}
1795		public SortedSet<E> tailSet(E fromElement) {
1796	<	synchronized(mutex) {
1796	>	synchronized (mutex) {
1797		return new SynchronizedSortedSet<E>(ss.tailSet(fromElement),mutex);
1798		}
1799		}
1800
1801		public E first() {
1802	<	synchronized(mutex) {return ss.first();}
1802	>	synchronized (mutex) {return ss.first();}
1803		}
1804		public E last() {
1805	<	synchronized(mutex) {return ss.last();}
1805	>	synchronized (mutex) {return ss.last();}
1806		}
1807		}
1808
#	Line 1764 \| Line 1817 \| public class Collections {
1817		* <pre>
1818		* List list = Collections.synchronizedList(new ArrayList());
1819		* ...
1820	<	* synchronized(list) {
1820	>	* synchronized (list) {
1821		* Iterator i = list.iterator(); // Must be in synchronized block
1822		* while (i.hasNext())
1823		* foo(i.next());
#	Line 1779 \| Line 1832 \| public class Collections {
1832		* @return a synchronized view of the specified list.
1833		*/
1834		public static <T> List<T> synchronizedList(List<T> list) {
1835	<	return (list instanceof RandomAccess ?
1835	>	return (list instanceof RandomAccess ?
1836		new SynchronizedRandomAccessList<T>(list) :
1837		new SynchronizedList<T>(list));
1838		}
1839
1840		static <T> List<T> synchronizedList(List<T> list, Object mutex) {
1841	<	return (list instanceof RandomAccess ?
1841	>	return (list instanceof RandomAccess ?
1842		new SynchronizedRandomAccessList<T>(list, mutex) :
1843		new SynchronizedList<T>(list, mutex));
1844		}
#	Line 1794 \| Line 1847 \| public class Collections {
1847		* @serial include
1848		*/
1849		static class SynchronizedList<E>
1850	<	extends SynchronizedCollection<E>
1851	<	implements List<E> {
1852	<	static final long serialVersionUID = -7754090372962971524L;
1853	<
1854	<	final List<E> list;
1855	<
1856	<	SynchronizedList(List<E> list) {
1857	<	super(list);
1858	<	this.list = list;
1859	<	}
1860	<	SynchronizedList(List<E> list, Object mutex) {
1850	>	extends SynchronizedCollection<E>
1851	>	implements List<E> {
1852	>	private static final long serialVersionUID = -7754090372962971524L;
1853	>
1854	>	final List<E> list;
1855	>
1856	>	SynchronizedList(List<E> list) {
1857	>	super(list);
1858	>	this.list = list;
1859	>	}
1860	>	SynchronizedList(List<E> list, Object mutex) {
1861		super(list, mutex);
1862	<	this.list = list;
1862	>	this.list = list;
1863		}
1864
1865	<	public boolean equals(Object o) {
1866	<	synchronized(mutex) {return list.equals(o);}
1865	>	public boolean equals(Object o) {
1866	>	synchronized (mutex) {return list.equals(o);}
1867		}
1868	<	public int hashCode() {
1869	<	synchronized(mutex) {return list.hashCode();}
1868	>	public int hashCode() {
1869	>	synchronized (mutex) {return list.hashCode();}
1870		}
1871
1872	<	public E get(int index) {
1873	<	synchronized(mutex) {return list.get(index);}
1872	>	public E get(int index) {
1873	>	synchronized (mutex) {return list.get(index);}
1874		}
1875	<	public E set(int index, E element) {
1876	<	synchronized(mutex) {return list.set(index, element);}
1875	>	public E set(int index, E element) {
1876	>	synchronized (mutex) {return list.set(index, element);}
1877		}
1878	<	public void add(int index, E element) {
1879	<	synchronized(mutex) {list.add(index, element);}
1878	>	public void add(int index, E element) {
1879	>	synchronized (mutex) {list.add(index, element);}
1880		}
1881	<	public E remove(int index) {
1882	<	synchronized(mutex) {return list.remove(index);}
1881	>	public E remove(int index) {
1882	>	synchronized (mutex) {return list.remove(index);}
1883		}
1884
1885	<	public int indexOf(Object o) {
1886	<	synchronized(mutex) {return list.indexOf(o);}
1885	>	public int indexOf(Object o) {
1886	>	synchronized (mutex) {return list.indexOf(o);}
1887		}
1888	<	public int lastIndexOf(Object o) {
1889	<	synchronized(mutex) {return list.lastIndexOf(o);}
1888	>	public int lastIndexOf(Object o) {
1889	>	synchronized (mutex) {return list.lastIndexOf(o);}
1890		}
1891
1892	<	public boolean addAll(int index, Collection<? extends E> c) {
1893	<	synchronized(mutex) {return list.addAll(index, c);}
1892	>	public boolean addAll(int index, Collection<? extends E> c) {
1893	>	synchronized (mutex) {return list.addAll(index, c);}
1894		}
1895
1896	<	public ListIterator<E> listIterator() {
1897	<	return list.listIterator(); // Must be manually synched by user
1896	>	public ListIterator<E> listIterator() {
1897	>	return list.listIterator(); // Must be manually synched by user
1898		}
1899
1900	<	public ListIterator<E> listIterator(int index) {
1901	<	return list.listIterator(index); // Must be manually synched by user
1900	>	public ListIterator<E> listIterator(int index) {
1901	>	return list.listIterator(index); // Must be manually synched by user
1902		}
1903
1904	<	public List<E> subList(int fromIndex, int toIndex) {
1905	<	synchronized(mutex) {
1904	>	public List<E> subList(int fromIndex, int toIndex) {
1905	>	synchronized (mutex) {
1906		return new SynchronizedList<E>(list.subList(fromIndex, toIndex),
1907		mutex);
1908		}
#	Line 1869 \| Line 1922 \| public class Collections {
1922		*/
1923		private Object readResolve() {
1924		return (list instanceof RandomAccess
1925	<	? new SynchronizedRandomAccessList<E>(list)
1926	<	: this);
1925	>	? new SynchronizedRandomAccessList<E>(list)
1926	>	: this);
1927		}
1928		}
1929
#	Line 1878 \| Line 1931 \| public class Collections {
1931		* @serial include
1932		*/
1933		static class SynchronizedRandomAccessList<E>
1934	<	extends SynchronizedList<E>
1935	<	implements RandomAccess {
1934	>	extends SynchronizedList<E>
1935	>	implements RandomAccess {
1936
1937		SynchronizedRandomAccessList(List<E> list) {
1938		super(list);
1939		}
1940
1941	<	SynchronizedRandomAccessList(List<E> list, Object mutex) {
1941	>	SynchronizedRandomAccessList(List<E> list, Object mutex) {
1942		super(list, mutex);
1943		}
1944
1945	<	public List<E> subList(int fromIndex, int toIndex) {
1946	<	synchronized(mutex) {
1945	>	public List<E> subList(int fromIndex, int toIndex) {
1946	>	synchronized (mutex) {
1947		return new SynchronizedRandomAccessList<E>(
1948		list.subList(fromIndex, toIndex), mutex);
1949		}
1950		}
1951
1952	<	static final long serialVersionUID = 1530674583602358482L;
1952	>	private static final long serialVersionUID = 1530674583602358482L;
1953
1954		/**
1955		* Allows instances to be deserialized in pre-1.4 JREs (which do
#	Line 1922 \| Line 1975 \| public class Collections {
1975		* ...
1976		* Set s = m.keySet(); // Needn't be in synchronized block
1977		* ...
1978	<	* synchronized(m) { // Synchronizing on m, not s!
1978	>	* synchronized (m) { // Synchronizing on m, not s!
1979		* Iterator i = s.iterator(); // Must be in synchronized block
1980		* while (i.hasNext())
1981		* foo(i.next());
#	Line 1937 \| Line 1990 \| public class Collections {
1990		* @return a synchronized view of the specified map.
1991		*/
1992		public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
1993	<	return new SynchronizedMap<K,V>(m);
1993	>	return new SynchronizedMap<K,V>(m);
1994		}
1995
1996		/**
1997		* @serial include
1998		*/
1999		private static class SynchronizedMap<K,V>
2000	<	implements Map<K,V>, Serializable {
2001	<	// use serialVersionUID from JDK 1.2.2 for interoperability
1949	<	private static final long serialVersionUID = 1978198479659022715L;
2000	>	implements Map<K,V>, Serializable {
2001	>	private static final long serialVersionUID = 1978198479659022715L;
2002
2003	<	private final Map<K,V> m; // Backing Map
2004	<	final Object mutex; // Object on which to synchronize
2003	>	private final Map<K,V> m; // Backing Map
2004	>	final Object mutex; // Object on which to synchronize
2005
2006	<	SynchronizedMap(Map<K,V> m) {
2006	>	SynchronizedMap(Map<K,V> m) {
2007		if (m==null)
2008		throw new NullPointerException();
2009		this.m = m;
2010		mutex = this;
2011		}
2012
2013	<	SynchronizedMap(Map<K,V> m, Object mutex) {
2013	>	SynchronizedMap(Map<K,V> m, Object mutex) {
2014		this.m = m;
2015		this.mutex = mutex;
2016		}
2017
2018	<	public int size() {
2019	<	synchronized(mutex) {return m.size();}
2018	>	public int size() {
2019	>	synchronized (mutex) {return m.size();}
2020		}
2021	<	public boolean isEmpty(){
2022	<	synchronized(mutex) {return m.isEmpty();}
2021	>	public boolean isEmpty() {
2022	>	synchronized (mutex) {return m.isEmpty();}
2023		}
2024	<	public boolean containsKey(Object key) {
2025	<	synchronized(mutex) {return m.containsKey(key);}
2024	>	public boolean containsKey(Object key) {
2025	>	synchronized (mutex) {return m.containsKey(key);}
2026		}
2027	<	public boolean containsValue(Object value){
2028	<	synchronized(mutex) {return m.containsValue(value);}
2027	>	public boolean containsValue(Object value) {
2028	>	synchronized (mutex) {return m.containsValue(value);}
2029		}
2030	<	public V get(Object key) {
2031	<	synchronized(mutex) {return m.get(key);}
2030	>	public V get(Object key) {
2031	>	synchronized (mutex) {return m.get(key);}
2032		}
2033
2034	<	public V put(K key, V value) {
2035	<	synchronized(mutex) {return m.put(key, value);}
2034	>	public V put(K key, V value) {
2035	>	synchronized (mutex) {return m.put(key, value);}
2036	>	}
2037	>	public V remove(Object key) {
2038	>	synchronized (mutex) {return m.remove(key);}
2039		}
2040	<	public V remove(Object key) {
2041	<	synchronized(mutex) {return m.remove(key);}
2040	>	public void putAll(Map<? extends K, ? extends V> map) {
2041	>	synchronized (mutex) {m.putAll(map);}
2042		}
2043	<	public void putAll(Map<? extends K, ? extends V> map) {
2044	<	synchronized(mutex) {m.putAll(map);}
2043	>	public void clear() {
2044	>	synchronized (mutex) {m.clear();}
2045		}
1991	–	public void clear() {
1992	–	synchronized(mutex) {m.clear();}
1993	–	}
2046
2047	<	private transient Set<K> keySet = null;
2048	<	private transient Set<Map.Entry<K,V>> entrySet = null;
2049	<	private transient Collection<V> values = null;
2047	>	private transient Set<K> keySet = null;
2048	>	private transient Set<Map.Entry<K,V>> entrySet = null;
2049	>	private transient Collection<V> values = null;
2050
2051	<	public Set<K> keySet() {
2052	<	synchronized(mutex) {
2051	>	public Set<K> keySet() {
2052	>	synchronized (mutex) {
2053		if (keySet==null)
2054		keySet = new SynchronizedSet<K>(m.keySet(), mutex);
2055		return keySet;
2056		}
2057	<	}
2057	>	}
2058
2059	<	public Set<Map.Entry<K,V>> entrySet() {
2060	<	synchronized(mutex) {
2059	>	public Set<Map.Entry<K,V>> entrySet() {
2060	>	synchronized (mutex) {
2061		if (entrySet==null)
2062		entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2063		return entrySet;
2064		}
2065	<	}
2065	>	}
2066
2067	<	public Collection<V> values() {
2068	<	synchronized(mutex) {
2067	>	public Collection<V> values() {
2068	>	synchronized (mutex) {
2069		if (values==null)
2070		values = new SynchronizedCollection<V>(m.values(), mutex);
2071		return values;
2072		}
2073		}
2074
2075	<	public boolean equals(Object o) {
2076	<	synchronized(mutex) {return m.equals(o);}
2075	>	public boolean equals(Object o) {
2076	>	synchronized (mutex) {return m.equals(o);}
2077		}
2078	<	public int hashCode() {
2079	<	synchronized(mutex) {return m.hashCode();}
2078	>	public int hashCode() {
2079	>	synchronized (mutex) {return m.hashCode();}
2080		}
2081	<	public String toString() {
2082	<	synchronized(mutex) {return m.toString();}
2081	>	public String toString() {
2082	>	synchronized (mutex) {return m.toString();}
2083		}
2084		private void writeObject(ObjectOutputStream s) throws IOException {
2085	<	synchronized(mutex) {s.defaultWriteObject();}
2085	>	synchronized (mutex) {s.defaultWriteObject();}
2086		}
2087		}
2088
#	Line 2049 \| Line 2101 \| public class Collections {
2101		* ...
2102		* Set s = m.keySet(); // Needn't be in synchronized block
2103		* ...
2104	<	* synchronized(m) { // Synchronizing on m, not s!
2104	>	* synchronized (m) { // Synchronizing on m, not s!
2105		* Iterator i = s.iterator(); // Must be in synchronized block
2106		* while (i.hasNext())
2107		* foo(i.next());
#	Line 2062 \| Line 2114 \| public class Collections {
2114		* ...
2115		* Set s2 = m2.keySet(); // Needn't be in synchronized block
2116		* ...
2117	<	* synchronized(m) { // Synchronizing on m, not m2 or s2!
2117	>	* synchronized (m) { // Synchronizing on m, not m2 or s2!
2118		* Iterator i = s.iterator(); // Must be in synchronized block
2119		* while (i.hasNext())
2120		* foo(i.next());
#	Line 2077 \| Line 2129 \| public class Collections {
2129		* @return a synchronized view of the specified sorted map.
2130		*/
2131		public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2132	<	return new SynchronizedSortedMap<K,V>(m);
2132	>	return new SynchronizedSortedMap<K,V>(m);
2133		}
2134
2135
#	Line 2085 \| Line 2137 \| public class Collections {
2137		* @serial include
2138		*/
2139		static class SynchronizedSortedMap<K,V>
2140	<	extends SynchronizedMap<K,V>
2141	<	implements SortedMap<K,V>
2140	>	extends SynchronizedMap<K,V>
2141	>	implements SortedMap<K,V>
2142		{
2143	<	private static final long serialVersionUID = -8798146769416483793L;
2143	>	private static final long serialVersionUID = -8798146769416483793L;
2144
2145		private final SortedMap<K,V> sm;
2146
2147	<	SynchronizedSortedMap(SortedMap<K,V> m) {
2147	>	SynchronizedSortedMap(SortedMap<K,V> m) {
2148		super(m);
2149		sm = m;
2150		}
2151	<	SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2151	>	SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2152		super(m, mutex);
2153		sm = m;
2154		}
2155
2156	<	public Comparator<? super K> comparator() {
2157	<	synchronized(mutex) {return sm.comparator();}
2156	>	public Comparator<? super K> comparator() {
2157	>	synchronized (mutex) {return sm.comparator();}
2158		}
2159
2160		public SortedMap<K,V> subMap(K fromKey, K toKey) {
2161	<	synchronized(mutex) {
2161	>	synchronized (mutex) {
2162		return new SynchronizedSortedMap<K,V>(
2163		sm.subMap(fromKey, toKey), mutex);
2164		}
2165		}
2166		public SortedMap<K,V> headMap(K toKey) {
2167	<	synchronized(mutex) {
2167	>	synchronized (mutex) {
2168		return new SynchronizedSortedMap<K,V>(sm.headMap(toKey), mutex);
2169		}
2170		}
2171		public SortedMap<K,V> tailMap(K fromKey) {
2172	<	synchronized(mutex) {
2172	>	synchronized (mutex) {
2173		return new SynchronizedSortedMap<K,V>(sm.tailMap(fromKey),mutex);
2174		}
2175		}
2176
2177		public K firstKey() {
2178	<	synchronized(mutex) {return sm.firstKey();}
2178	>	synchronized (mutex) {return sm.firstKey();}
2179		}
2180		public K lastKey() {
2181	<	synchronized(mutex) {return sm.lastKey();}
2181	>	synchronized (mutex) {return sm.lastKey();}
2182		}
2183		}
2184
2185		// Dynamically typesafe collection wrappers
2186
2187		/**
2188	<	* Returns a dynamically typesafe view of the specified collection. Any
2189	<	* attempt to insert an element of the wrong type will result in an
2190	<	* immediate <tt>ClassCastException</tt>. Assuming a collection contains
2191	<	* no incorrectly typed elements prior to the time a dynamically typesafe
2192	<	* view is generated, and that all subsequent access to the collection
2193	<	* takes place through the view, it is <i>guaranteed</i> that the
2194	<	* collection cannot contain an incorrectly typed element.
2188	>	* Returns a dynamically typesafe view of the specified collection.
2189	>	* Any attempt to insert an element of the wrong type will result in an
2190	>	* immediate {@link ClassCastException}. Assuming a collection
2191	>	* contains no incorrectly typed elements prior to the time a
2192	>	* dynamically typesafe view is generated, and that all subsequent
2193	>	* access to the collection takes place through the view, it is
2194	>	* <i>guaranteed</i> that the collection cannot contain an incorrectly
2195	>	* typed element.
2196		*
2197		* <p>The generics mechanism in the language provides compile-time
2198		* (static) type checking, but it is possible to defeat this mechanism
#	Line 2151 \| Line 2204 \| public class Collections {
2204		* inserting an element of the wrong type.
2205		*
2206		* <p>Another use of dynamically typesafe views is debugging. Suppose a
2207	<	* program fails with a <tt>ClassCastException</tt>, indicating that an
2207	>	* program fails with a {@code ClassCastException}, indicating that an
2208		* incorrectly typed element was put into a parameterized collection.
2209		* Unfortunately, the exception can occur at any time after the erroneous
2210		* element is inserted, so it typically provides little or no information
#	Line 2159 \| Line 2212 \| public class Collections {
2212		* one can quickly determine its source by temporarily modifying the
2213		* program to wrap the collection with a dynamically typesafe view.
2214		* For example, this declaration:
2215	<	* <pre>
2216	<	* Collection<String> c = new HashSet<String>();
2217	<	* </pre>
2215	>	* <pre> {@code
2216	>	* Collection<String> c = new HashSet<String>();
2217	>	* }</pre>
2218		* may be replaced temporarily by this one:
2219	<	* <pre>
2220	<	* Collection<String> c = Collections.checkedCollection(
2221	<	* new HashSet<String>(), String.class);
2222	<	* </pre>
2219	>	* <pre> {@code
2220	>	* Collection<String> c = Collections.checkedCollection(
2221	>	* new HashSet<String>(), String.class);
2222	>	* }</pre>
2223		* Running the program again will cause it to fail at the point where
2224		* an incorrectly typed element is inserted into the collection, clearly
2225		* identifying the source of the problem. Once the problem is fixed, the
#	Line 2174 \| Line 2227 \| public class Collections {
2227		*
2228		* <p>The returned collection does <i>not</i> pass the hashCode and equals
2229		* operations through to the backing collection, but relies on
2230	<	* <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
2230	>	* {@code Object}'s {@code equals} and {@code hashCode} methods. This
2231		* is necessary to preserve the contracts of these operations in the case
2232		* that the backing collection is a set or a list.
2233		*
2234		* <p>The returned collection will be serializable if the specified
2235		* collection is serializable.
2236		*
2237	+	* <p>Since {@code null} is considered to be a value of any reference
2238	+	* type, the returned collection permits insertion of null elements
2239	+	* whenever the backing collection does.
2240	+	*
2241		* @param c the collection for which a dynamically typesafe view is to be
2242	<	* returned
2243	<	* @param type the type of element that <tt>c</tt> is permitted to hold
2242	>	* returned
2243	>	* @param type the type of element that {@code c} is permitted to hold
2244		* @return a dynamically typesafe view of the specified collection
2245		* @since 1.5
2246		*/
#	Line 2192 \| Line 2249 \| public class Collections {
2249		return new CheckedCollection<E>(c, type);
2250		}
2251
2252	+	@SuppressWarnings("unchecked")
2253	+	static <T> T[] zeroLengthArray(Class<T> type) {
2254	+	return (T[]) Array.newInstance(type, 0);
2255	+	}
2256	+
2257		/**
2258		* @serial include
2259		*/
#	Line 2202 \| Line 2264 \| public class Collections {
2264		final Class<E> type;
2265
2266		void typeCheck(Object o) {
2267	<	if (!type.isInstance(o))
2268	<	throw new ClassCastException("Attempt to insert " +
2269	<	o.getClass() + " element into collection with element type "
2270	<	+ type);
2267	>	if (o != null && !type.isInstance(o))
2268	>	throw new ClassCastException(badElementMsg(o));
2269	>	}
2270	>
2271	>	private String badElementMsg(Object o) {
2272	>	return "Attempt to insert " + o.getClass() +
2273	>	" element into collection with element type " + type;
2274		}
2275
2276		CheckedCollection(Collection<E> c, Class<E> type) {
#	Line 2215 \| Line 2280 \| public class Collections {
2280		this.type = type;
2281		}
2282
2283	<	public int size() { return c.size(); }
2284	<	public boolean isEmpty() { return c.isEmpty(); }
2285	<	public boolean contains(Object o) { return c.contains(o); }
2286	<	public Object[] toArray() { return c.toArray(); }
2287	<	public <T> T[] toArray(T[] a) { return c.toArray(a); }
2288	<	public String toString() { return c.toString(); }
2289	<	public Iterator<E> iterator() { return c.iterator(); }
2290	<	public boolean remove(Object o) { return c.remove(o); }
2283	>	public int size() { return c.size(); }
2284	>	public boolean isEmpty() { return c.isEmpty(); }
2285	>	public boolean contains(Object o) { return c.contains(o); }
2286	>	public Object[] toArray() { return c.toArray(); }
2287	>	public <T> T[] toArray(T[] a) { return c.toArray(a); }
2288	>	public String toString() { return c.toString(); }
2289	>	public boolean remove(Object o) { return c.remove(o); }
2290	>	public void clear() { c.clear(); }
2291	>
2292		public boolean containsAll(Collection<?> coll) {
2293		return c.containsAll(coll);
2294		}
#	Line 2232 \| Line 2298 \| public class Collections {
2298		public boolean retainAll(Collection<?> coll) {
2299		return c.retainAll(coll);
2300		}
2301	<	public void clear() {
2302	<	c.clear();
2301	>
2302	>	public Iterator<E> iterator() {
2303	>	final Iterator<E> it = c.iterator();
2304	>	return new Iterator<E>() {
2305	>	public boolean hasNext() { return it.hasNext(); }
2306	>	public E next() { return it.next(); }
2307	>	public void remove() { it.remove(); }};
2308		}
2309
2310	<	public boolean add(E e){
2310	>	public boolean add(E e) {
2311		typeCheck(e);
2312		return c.add(e);
2313		}
2314
2315	<	public boolean addAll(Collection<? extends E> coll) {
2245	<	/*
2246	<	* Dump coll into an array of the required type. This serves
2247	<	* three purposes: it insulates us from concurrent changes in
2248	<	* the contents of coll, it type-checks all of the elements in
2249	<	* coll, and it provides all-or-nothing semantics (which we
2250	<	* wouldn't get if we type-checked each element as we added it).
2251	<	*/
2252	<	E[] a = null;
2253	<	try {
2254	<	a = coll.toArray(zeroLengthElementArray());
2255	<	} catch (ArrayStoreException e) {
2256	<	throw new ClassCastException();
2257	<	}
2315	>	private E[] zeroLengthElementArray = null; // Lazily initialized
2316
2317	<	boolean result = false;
2318	<	for (E e : a)
2319	<	result \|= c.add(e);
2262	<	return result;
2317	>	private E[] zeroLengthElementArray() {
2318	>	return zeroLengthElementArray != null ? zeroLengthElementArray :
2319	>	(zeroLengthElementArray = zeroLengthArray(type));
2320		}
2321
2322	<	private E[] zeroLengthElementArray = null; // Lazily initialized
2322	>	@SuppressWarnings("unchecked")
2323	>	Collection<E> checkedCopyOf(Collection<? extends E> coll) {
2324	>	Object[] a = null;
2325	>	try {
2326	>	E[] z = zeroLengthElementArray();
2327	>	a = coll.toArray(z);
2328	>	// Defend against coll violating the toArray contract
2329	>	if (a.getClass() != z.getClass())
2330	>	a = Arrays.copyOf(a, a.length, z.getClass());
2331	>	} catch (ArrayStoreException ignore) {
2332	>	// To get better and consistent diagnostics,
2333	>	// we call typeCheck explicitly on each element.
2334	>	// We call clone() to defend against coll retaining a
2335	>	// reference to the returned array and storing a bad
2336	>	// element into it after it has been type checked.
2337	>	a = coll.toArray().clone();
2338	>	for (Object o : a)
2339	>	typeCheck(o);
2340	>	}
2341	>	// A slight abuse of the type system, but safe here.
2342	>	return (Collection<E>) Arrays.asList(a);
2343	>	}
2344
2345	<	/*
2346	<	* We don't need locking or volatile, because it's OK if we create
2347	<	* several zeroLengthElementArrays, and they're immutable.
2348	<	*/
2349	<	E[] zeroLengthElementArray() {
2350	<	if (zeroLengthElementArray == null)
2273	<	zeroLengthElementArray = (E[]) Array.newInstance(type, 0);
2274	<	return zeroLengthElementArray;
2345	>	public boolean addAll(Collection<? extends E> coll) {
2346	>	// Doing things this way insulates us from concurrent changes
2347	>	// in the contents of coll and provides all-or-nothing
2348	>	// semantics (which we wouldn't get if we type-checked each
2349	>	// element as we added it)
2350	>	return c.addAll(checkedCopyOf(coll));
2351		}
2352		}
2353
2354		/**
2355		* Returns a dynamically typesafe view of the specified set.
2356		* Any attempt to insert an element of the wrong type will result in
2357	<	* an immediate <tt>ClassCastException</tt>. Assuming a set contains
2357	>	* an immediate {@link ClassCastException}. Assuming a set contains
2358		* no incorrectly typed elements prior to the time a dynamically typesafe
2359		* view is generated, and that all subsequent access to the set
2360		* takes place through the view, it is <i>guaranteed</i> that the
2361		* set cannot contain an incorrectly typed element.
2362		*
2363		* <p>A discussion of the use of dynamically typesafe views may be
2364	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2365	<	* method.
2364	>	* found in the documentation for the {@link #checkedCollection
2365	>	* checkedCollection} method.
2366		*
2367		* <p>The returned set will be serializable if the specified set is
2368		* serializable.
2369		*
2370	+	* <p>Since {@code null} is considered to be a value of any reference
2371	+	* type, the returned set permits insertion of null elements whenever
2372	+	* the backing set does.
2373	+	*
2374		* @param s the set for which a dynamically typesafe view is to be
2375	<	* returned
2376	<	* @param type the type of element that <tt>s</tt> is permitted to hold
2375	>	* returned
2376	>	* @param type the type of element that {@code s} is permitted to hold
2377		* @return a dynamically typesafe view of the specified set
2378		* @since 1.5
2379		*/
#	Line 2311 \| Line 2391 \| public class Collections {
2391
2392		CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2393
2394	<	public boolean equals(Object o) { return c.equals(o); }
2394	>	public boolean equals(Object o) { return o == this \|\| c.equals(o); }
2395		public int hashCode() { return c.hashCode(); }
2396		}
2397
2398		/**
2399	<	* Returns a dynamically typesafe view of the specified sorted set. Any
2400	<	* attempt to insert an element of the wrong type will result in an
2401	<	* immediate <tt>ClassCastException</tt>. Assuming a sorted set contains
2402	<	* no incorrectly typed elements prior to the time a dynamically typesafe
2403	<	* view is generated, and that all subsequent access to the sorted set
2404	<	* takes place through the view, it is <i>guaranteed</i> that the sorted
2405	<	* set cannot contain an incorrectly typed element.
2399	>	* Returns a dynamically typesafe view of the specified sorted set.
2400	>	* Any attempt to insert an element of the wrong type will result in an
2401	>	* immediate {@link ClassCastException}. Assuming a sorted set
2402	>	* contains no incorrectly typed elements prior to the time a
2403	>	* dynamically typesafe view is generated, and that all subsequent
2404	>	* access to the sorted set takes place through the view, it is
2405	>	* <i>guaranteed</i> that the sorted set cannot contain an incorrectly
2406	>	* typed element.
2407		*
2408		* <p>A discussion of the use of dynamically typesafe views may be
2409	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2410	<	* method.
2409	>	* found in the documentation for the {@link #checkedCollection
2410	>	* checkedCollection} method.
2411		*
2412		* <p>The returned sorted set will be serializable if the specified sorted
2413		* set is serializable.
2414		*
2415	+	* <p>Since {@code null} is considered to be a value of any reference
2416	+	* type, the returned sorted set permits insertion of null elements
2417	+	* whenever the backing sorted set does.
2418	+	*
2419		* @param s the sorted set for which a dynamically typesafe view is to be
2420	<	* returned
2421	<	* @param type the type of element that <tt>s</tt> is permitted to hold
2420	>	* returned
2421	>	* @param type the type of element that {@code s} is permitted to hold
2422		* @return a dynamically typesafe view of the specified sorted set
2423		* @since 1.5
2424		*/
#	Line 2361 \| Line 2446 \| public class Collections {
2446		public E last() { return ss.last(); }
2447
2448		public SortedSet<E> subSet(E fromElement, E toElement) {
2449	<	return new CheckedSortedSet<E>(ss.subSet(fromElement,toElement),
2365	<	type);
2449	>	return checkedSortedSet(ss.subSet(fromElement,toElement), type);
2450		}
2451		public SortedSet<E> headSet(E toElement) {
2452	<	return new CheckedSortedSet<E>(ss.headSet(toElement), type);
2452	>	return checkedSortedSet(ss.headSet(toElement), type);
2453		}
2454		public SortedSet<E> tailSet(E fromElement) {
2455	<	return new CheckedSortedSet<E>(ss.tailSet(fromElement), type);
2455	>	return checkedSortedSet(ss.tailSet(fromElement), type);
2456		}
2457		}
2458
2459		/**
2460		* Returns a dynamically typesafe view of the specified list.
2461		* Any attempt to insert an element of the wrong type will result in
2462	<	* an immediate <tt>ClassCastException</tt>. Assuming a list contains
2462	>	* an immediate {@link ClassCastException}. Assuming a list contains
2463		* no incorrectly typed elements prior to the time a dynamically typesafe
2464		* view is generated, and that all subsequent access to the list
2465		* takes place through the view, it is <i>guaranteed</i> that the
2466		* list cannot contain an incorrectly typed element.
2467		*
2468		* <p>A discussion of the use of dynamically typesafe views may be
2469	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2470	<	* method.
2469	>	* found in the documentation for the {@link #checkedCollection
2470	>	* checkedCollection} method.
2471		*
2472	<	* <p>The returned list will be serializable if the specified list is
2473	<	* serializable.
2472	>	* <p>The returned list will be serializable if the specified list
2473	>	* is serializable.
2474	>	*
2475	>	* <p>Since {@code null} is considered to be a value of any reference
2476	>	* type, the returned list permits insertion of null elements whenever
2477	>	* the backing list does.
2478		*
2479		* @param list the list for which a dynamically typesafe view is to be
2480		* returned
2481	<	* @param type the type of element that <tt>list</tt> is permitted to hold
2481	>	* @param type the type of element that {@code list} is permitted to hold
2482		* @return a dynamically typesafe view of the specified list
2483		* @since 1.5
2484		*/
#	Line 2403 \| Line 2491 \| public class Collections {
2491		/**
2492		* @serial include
2493		*/
2494	<	static class CheckedList<E> extends CheckedCollection<E>
2495	<	implements List<E>
2494	>	static class CheckedList<E>
2495	>	extends CheckedCollection<E>
2496	>	implements List<E>
2497		{
2498	<	static final long serialVersionUID = 65247728283967356L;
2498	>	private static final long serialVersionUID = 65247728283967356L;
2499		final List<E> list;
2500
2501		CheckedList(List<E> list, Class<E> type) {
#	Line 2414 \| Line 2503 \| public class Collections {
2503		this.list = list;
2504		}
2505
2506	<	public boolean equals(Object o) { return list.equals(o); }
2506	>	public boolean equals(Object o) { return o == this \|\| list.equals(o); }
2507		public int hashCode() { return list.hashCode(); }
2508		public E get(int index) { return list.get(index); }
2509		public E remove(int index) { return list.remove(index); }
#	Line 2432 \| Line 2521 \| public class Collections {
2521		}
2522
2523		public boolean addAll(int index, Collection<? extends E> c) {
2524	<	// See CheckCollection.addAll, above, for an explanation
2436	<	E[] a = null;
2437	<	try {
2438	<	a = c.toArray(zeroLengthElementArray());
2439	<	} catch (ArrayStoreException e) {
2440	<	throw new ClassCastException();
2441	<	}
2442	<
2443	<	return list.addAll(index, Arrays.asList(a));
2524	>	return list.addAll(index, checkedCopyOf(c));
2525		}
2526		public ListIterator<E> listIterator() { return listIterator(0); }
2527
2528		public ListIterator<E> listIterator(final int index) {
2529	<	return new ListIterator<E>() {
2449	<	ListIterator<E> i = list.listIterator(index);
2529	>	final ListIterator<E> i = list.listIterator(index);
2530
2531	+	return new ListIterator<E>() {
2532		public boolean hasNext() { return i.hasNext(); }
2533		public E next() { return i.next(); }
2534		public boolean hasPrevious() { return i.hasPrevious(); }
2535		public E previous() { return i.previous(); }
2536		public int nextIndex() { return i.nextIndex(); }
2537		public int previousIndex() { return i.previousIndex(); }
2538	<	public void remove() { i.remove(); }
2538	>	public void remove() { i.remove(); }
2539
2540		public void set(E e) {
2541		typeCheck(e);
#	Line 2492 \| Line 2573 \| public class Collections {
2573		}
2574
2575		/**
2576	<	* Returns a dynamically typesafe view of the specified map. Any attempt
2577	<	* to insert a mapping whose key or value have the wrong type will result
2578	<	* in an immediate <tt>ClassCastException</tt>. Similarly, any attempt to
2579	<	* modify the value currently associated with a key will result in an
2580	<	* immediate <tt>ClassCastException</tt>, whether the modification is
2581	<	* attempted directly through the map itself, or through a {@link
2582	<	* Map.Entry} instance obtained from the map's {@link Map#entrySet()
2583	<	* entry set} view.
2576	>	* Returns a dynamically typesafe view of the specified map.
2577	>	* Any attempt to insert a mapping whose key or value have the wrong
2578	>	* type will result in an immediate {@link ClassCastException}.
2579	>	* Similarly, any attempt to modify the value currently associated with
2580	>	* a key will result in an immediate {@link ClassCastException},
2581	>	* whether the modification is attempted directly through the map
2582	>	* itself, or through a {@link Map.Entry} instance obtained from the
2583	>	* map's {@link Map#entrySet() entry set} view.
2584		*
2585		* <p>Assuming a map contains no incorrectly typed keys or values
2586		* prior to the time a dynamically typesafe view is generated, and
#	Line 2508 \| Line 2589 \| public class Collections {
2589		* map cannot contain an incorrectly typed key or value.
2590		*
2591		* <p>A discussion of the use of dynamically typesafe views may be
2592	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2593	<	* method.
2592	>	* found in the documentation for the {@link #checkedCollection
2593	>	* checkedCollection} method.
2594		*
2595		* <p>The returned map will be serializable if the specified map is
2596		* serializable.
2597		*
2598	+	* <p>Since {@code null} is considered to be a value of any reference
2599	+	* type, the returned map permits insertion of null keys or values
2600	+	* whenever the backing map does.
2601	+	*
2602		* @param m the map for which a dynamically typesafe view is to be
2603	<	* returned
2604	<	* @param keyType the type of key that <tt>m</tt> is permitted to hold
2605	<	* @param valueType the type of value that <tt>m</tt> is permitted to hold
2603	>	* returned
2604	>	* @param keyType the type of key that {@code m} is permitted to hold
2605	>	* @param valueType the type of value that {@code m} is permitted to hold
2606		* @return a dynamically typesafe view of the specified map
2607		* @since 1.5
2608		*/
2609	<	public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType,
2609	>	public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
2610	>	Class<K> keyType,
2611		Class<V> valueType) {
2612		return new CheckedMap<K,V>(m, keyType, valueType);
2613		}
#	Line 2530 \| Line 2616 \| public class Collections {
2616		/**
2617		* @serial include
2618		*/
2619	<	private static class CheckedMap<K,V> implements Map<K,V>,
2620	<	Serializable
2619	>	private static class CheckedMap<K,V>
2620	>	implements Map<K,V>, Serializable
2621		{
2622		private static final long serialVersionUID = 5742860141034234728L;
2623
#	Line 2540 \| Line 2626 \| public class Collections {
2626		final Class<V> valueType;
2627
2628		private void typeCheck(Object key, Object value) {
2629	<	if (!keyType.isInstance(key))
2630	<	throw new ClassCastException("Attempt to insert " +
2631	<	key.getClass() + " key into collection with key type "
2632	<	+ keyType);
2633	<
2634	<	if (!valueType.isInstance(value))
2635	<	throw new ClassCastException("Attempt to insert " +
2636	<	value.getClass() +" value into collection with value type "
2637	<	+ valueType);
2629	>	if (key != null && !keyType.isInstance(key))
2630	>	throw new ClassCastException(badKeyMsg(key));
2631	>
2632	>	if (value != null && !valueType.isInstance(value))
2633	>	throw new ClassCastException(badValueMsg(value));
2634	>	}
2635	>
2636	>	private String badKeyMsg(Object key) {
2637	>	return "Attempt to insert " + key.getClass() +
2638	>	" key into map with key type " + keyType;
2639	>	}
2640	>
2641	>	private String badValueMsg(Object value) {
2642	>	return "Attempt to insert " + value.getClass() +
2643	>	" value into map with value type " + valueType;
2644		}
2645
2646		CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
#	Line 2568 \| Line 2660 \| public class Collections {
2660		public void clear() { m.clear(); }
2661		public Set<K> keySet() { return m.keySet(); }
2662		public Collection<V> values() { return m.values(); }
2663	<	public boolean equals(Object o) { return m.equals(o); }
2663	>	public boolean equals(Object o) { return o == this \|\| m.equals(o); }
2664		public int hashCode() { return m.hashCode(); }
2665		public String toString() { return m.toString(); }
2666
#	Line 2577 \| Line 2669 \| public class Collections {
2669		return m.put(key, value);
2670		}
2671
2672	+	@SuppressWarnings("unchecked")
2673		public void putAll(Map<? extends K, ? extends V> t) {
2674	<	// See CheckCollection.addAll, above, for an explanation
2675	<	K[] keys = null;
2676	<	try {
2677	<	keys = t.keySet().toArray(zeroLengthKeyArray());
2678	<	} catch (ArrayStoreException e) {
2679	<	throw new ClassCastException();
2674	>	// Satisfy the following goals:
2675	>	// - good diagnostics in case of type mismatch
2676	>	// - all-or-nothing semantics
2677	>	// - protection from malicious t
2678	>	// - correct behavior if t is a concurrent map
2679	>	Object[] entries = t.entrySet().toArray();
2680	>	List<Map.Entry<K,V>> checked =
2681	>	new ArrayList<Map.Entry<K,V>>(entries.length);
2682	>	for (Object o : entries) {
2683	>	Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2684	>	Object k = e.getKey();
2685	>	Object v = e.getValue();
2686	>	typeCheck(k, v);
2687	>	checked.add(
2688	>	new AbstractMap.SimpleImmutableEntry<K,V>((K) k, (V) v));
2689		}
2690	<	V[] values = null;
2691	<	try {
2590	<	values = t.values().toArray(zeroLengthValueArray());
2591	<	} catch (ArrayStoreException e) {
2592	<	throw new ClassCastException();
2593	<	}
2594	<
2595	<	if (keys.length != values.length)
2596	<	throw new ConcurrentModificationException();
2597	<
2598	<	for (int i = 0; i < keys.length; i++)
2599	<	m.put(keys[i], values[i]);
2600	<	}
2601	<
2602	<	// Lazily initialized
2603	<	private K[] zeroLengthKeyArray = null;
2604	<	private V[] zeroLengthValueArray = null;
2605	<
2606	<	/*
2607	<	* We don't need locking or volatile, because it's OK if we create
2608	<	* several zeroLengthValueArrays, and they're immutable.
2609	<	*/
2610	<	private K[] zeroLengthKeyArray() {
2611	<	if (zeroLengthKeyArray == null)
2612	<	zeroLengthKeyArray = (K[]) Array.newInstance(keyType, 0);
2613	<	return zeroLengthKeyArray;
2614	<	}
2615	<	private V[] zeroLengthValueArray() {
2616	<	if (zeroLengthValueArray == null)
2617	<	zeroLengthValueArray = (V[]) Array.newInstance(valueType, 0);
2618	<	return zeroLengthValueArray;
2690	>	for (Map.Entry<K,V> e : checked)
2691	>	m.put(e.getKey(), e.getValue());
2692		}
2693
2694		private transient Set<Map.Entry<K,V>> entrySet = null;
#	Line 2635 \| Line 2708 \| public class Collections {
2708		* @serial exclude
2709		*/
2710		static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> {
2711	<	Set<Map.Entry<K,V>> s;
2712	<	Class<V> valueType;
2711	>	private final Set<Map.Entry<K,V>> s;
2712	>	private final Class<V> valueType;
2713
2714		CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
2715		this.s = s;
2716		this.valueType = valueType;
2717		}
2718
2719	<	public int size() { return s.size(); }
2720	<	public boolean isEmpty() { return s.isEmpty(); }
2721	<	public String toString() { return s.toString(); }
2722	<	public int hashCode() { return s.hashCode(); }
2723	<	public boolean remove(Object o) { return s.remove(o); }
2651	<	public boolean removeAll(Collection<?> coll) {
2652	<	return s.removeAll(coll);
2653	<	}
2654	<	public boolean retainAll(Collection<?> coll) {
2655	<	return s.retainAll(coll);
2656	<	}
2657	<	public void clear() {
2658	<	s.clear();
2659	<	}
2719	>	public int size() { return s.size(); }
2720	>	public boolean isEmpty() { return s.isEmpty(); }
2721	>	public String toString() { return s.toString(); }
2722	>	public int hashCode() { return s.hashCode(); }
2723	>	public void clear() { s.clear(); }
2724
2725	<	public boolean add(Map.Entry<K, V> e){
2725	>	public boolean add(Map.Entry<K, V> e) {
2726		throw new UnsupportedOperationException();
2727		}
2728		public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
2729		throw new UnsupportedOperationException();
2730		}
2731
2668	–
2732		public Iterator<Map.Entry<K,V>> iterator() {
2733	<	return new Iterator<Map.Entry<K,V>>() {
2734	<	Iterator<Map.Entry<K, V>> i = s.iterator();
2733	>	final Iterator<Map.Entry<K, V>> i = s.iterator();
2734	>	final Class<V> valueType = this.valueType;
2735
2736	+	return new Iterator<Map.Entry<K,V>>() {
2737		public boolean hasNext() { return i.hasNext(); }
2738		public void remove() { i.remove(); }
2739
2740		public Map.Entry<K,V> next() {
2741	<	return new CheckedEntry<K,V>(i.next(), valueType);
2741	>	return checkedEntry(i.next(), valueType);
2742		}
2743		};
2744		}
2745
2746	+	@SuppressWarnings("unchecked")
2747		public Object[] toArray() {
2748		Object[] source = s.toArray();
2749
#	Line 2691 \| Line 2756 \| public class Collections {
2756		new Object[source.length]);
2757
2758		for (int i = 0; i < source.length; i++)
2759	<	dest[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)source[i],
2760	<	valueType);
2759	>	dest[i] = checkedEntry((Map.Entry<K,V>)source[i],
2760	>	valueType);
2761		return dest;
2762		}
2763
2764	+	@SuppressWarnings("unchecked")
2765		public <T> T[] toArray(T[] a) {
2766		// We don't pass a to s.toArray, to avoid window of
2767		// vulnerability wherein an unscrupulous multithreaded client
2768		// could get his hands on raw (unwrapped) Entries from s.
2769	<	Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2769	>	T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2770
2771		for (int i=0; i<arr.length; i++)
2772	<	arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i],
2773	<	valueType);
2772	>	arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i],
2773	>	valueType);
2774		if (arr.length > a.length)
2775	<	return (T[])arr;
2775	>	return arr;
2776
2777		System.arraycopy(arr, 0, a, 0, arr.length);
2778		if (a.length > arr.length)
#	Line 2723 \| Line 2789 \| public class Collections {
2789		public boolean contains(Object o) {
2790		if (!(o instanceof Map.Entry))
2791		return false;
2792	+	Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2793		return s.contains(
2794	<	new CheckedEntry<K,V>((Map.Entry<K,V>) o, valueType));
2794	>	(e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
2795		}
2796
2797		/**
2798	<	* The next two methods are overridden to protect against
2799	<	* an unscrupulous collection whose contains(Object o) method
2800	<	* senses when o is a Map.Entry, and calls o.setValue.
2798	>	* The bulk collection methods are overridden to protect
2799	>	* against an unscrupulous collection whose contains(Object o)
2800	>	* method senses when o is a Map.Entry, and calls o.setValue.
2801		*/
2802	<	public boolean containsAll(Collection<?> coll) {
2803	<	Iterator<?> e = coll.iterator();
2804	<	while (e.hasNext())
2738	<	if (!contains(e.next())) // Invokes safe contains() above
2802	>	public boolean containsAll(Collection<?> c) {
2803	>	for (Object o : c)
2804	>	if (!contains(o)) // Invokes safe contains() above
2805		return false;
2806		return true;
2807		}
2808
2809	+	public boolean remove(Object o) {
2810	+	if (!(o instanceof Map.Entry))
2811	+	return false;
2812	+	return s.remove(new AbstractMap.SimpleImmutableEntry
2813	+	<Object, Object>((Map.Entry<?,?>)o));
2814	+	}
2815	+
2816	+	public boolean removeAll(Collection<?> c) {
2817	+	return batchRemove(c, false);
2818	+	}
2819	+	public boolean retainAll(Collection<?> c) {
2820	+	return batchRemove(c, true);
2821	+	}
2822	+	private boolean batchRemove(Collection<?> c, boolean complement) {
2823	+	boolean modified = false;
2824	+	Iterator<Map.Entry<K,V>> it = iterator();
2825	+	while (it.hasNext()) {
2826	+	if (c.contains(it.next()) != complement) {
2827	+	it.remove();
2828	+	modified = true;
2829	+	}
2830	+	}
2831	+	return modified;
2832	+	}
2833	+
2834		public boolean equals(Object o) {
2835		if (o == this)
2836		return true;
2837		if (!(o instanceof Set))
2838		return false;
2839		Set<?> that = (Set<?>) o;
2840	<	if (that.size() != s.size())
2841	<	return false;
2842	<	return containsAll(that); // Invokes safe containsAll() above
2840	>	return that.size() == s.size()
2841	>	&& containsAll(that); // Invokes safe containsAll() above
2842	>	}
2843	>
2844	>	static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e,
2845	>	Class<T> valueType) {
2846	>	return new CheckedEntry<K,V,T>(e, valueType);
2847		}
2848
2849		/**
#	Line 2756 \| Line 2851 \| public class Collections {
2851		* the client from modifying the backing Map, by short-circuiting
2852		* the setValue method, and it protects the backing Map against
2853		* an ill-behaved Map.Entry that attempts to modify another
2854	<	* Map Entry when asked to perform an equality check.
2854	>	* Map.Entry when asked to perform an equality check.
2855		*/
2856	<	private static class CheckedEntry<K,V> implements Map.Entry<K,V> {
2857	<	private Map.Entry<K, V> e;
2858	<	private Class<V> valueType;
2856	>	private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> {
2857	>	private final Map.Entry<K, V> e;
2858	>	private final Class<T> valueType;
2859
2860	<	CheckedEntry(Map.Entry<K, V> e, Class<V> valueType) {
2860	>	CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) {
2861		this.e = e;
2862		this.valueType = valueType;
2863		}
#	Line 2772 \| Line 2867 \| public class Collections {
2867		public int hashCode() { return e.hashCode(); }
2868		public String toString() { return e.toString(); }
2869
2775	–
2870		public V setValue(V value) {
2871	<	if (!valueType.isInstance(value))
2872	<	throw new ClassCastException("Attempt to insert " +
2779	<	value.getClass() +
2780	<	" value into collection with value type " + valueType);
2871	>	if (value != null && !valueType.isInstance(value))
2872	>	throw new ClassCastException(badValueMsg(value));
2873		return e.setValue(value);
2874		}
2875
2876	+	private String badValueMsg(Object value) {
2877	+	return "Attempt to insert " + value.getClass() +
2878	+	" value into map with value type " + valueType;
2879	+	}
2880	+
2881		public boolean equals(Object o) {
2882	+	if (o == this)
2883	+	return true;
2884		if (!(o instanceof Map.Entry))
2885		return false;
2886	<	Map.Entry t = (Map.Entry)o;
2887	<	return eq(e.getKey(), t.getKey()) &&
2789	<	eq(e.getValue(), t.getValue());
2886	>	return e.equals(new AbstractMap.SimpleImmutableEntry
2887	>	<Object, Object>((Map.Entry<?,?>)o));
2888		}
2889		}
2890		}
2891		}
2892
2893		/**
2894	<	* Returns a dynamically typesafe view of the specified sorted map. Any
2895	<	* attempt to insert a mapping whose key or value have the wrong type will
2896	<	* result in an immediate <tt>ClassCastException</tt>. Similarly, any
2897	<	* attempt to modify the value currently associated with a key will result
2898	<	* in an immediate <tt>ClassCastException</tt>, whether the modification
2899	<	* is attempted directly through the map itself, or through a {@link
2900	<	* Map.Entry} instance obtained from the map's {@link Map#entrySet() entry
2901	<	* set} view.
2894	>	* Returns a dynamically typesafe view of the specified sorted map.
2895	>	* Any attempt to insert a mapping whose key or value have the wrong
2896	>	* type will result in an immediate {@link ClassCastException}.
2897	>	* Similarly, any attempt to modify the value currently associated with
2898	>	* a key will result in an immediate {@link ClassCastException},
2899	>	* whether the modification is attempted directly through the map
2900	>	* itself, or through a {@link Map.Entry} instance obtained from the
2901	>	* map's {@link Map#entrySet() entry set} view.
2902		*
2903		* <p>Assuming a map contains no incorrectly typed keys or values
2904		* prior to the time a dynamically typesafe view is generated, and
#	Line 2809 \| Line 2907 \| public class Collections {
2907		* map cannot contain an incorrectly typed key or value.
2908		*
2909		* <p>A discussion of the use of dynamically typesafe views may be
2910	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2911	<	* method.
2910	>	* found in the documentation for the {@link #checkedCollection
2911	>	* checkedCollection} method.
2912		*
2913		* <p>The returned map will be serializable if the specified map is
2914		* serializable.
2915		*
2916	+	* <p>Since {@code null} is considered to be a value of any reference
2917	+	* type, the returned map permits insertion of null keys or values
2918	+	* whenever the backing map does.
2919	+	*
2920		* @param m the map for which a dynamically typesafe view is to be
2921	<	* returned
2922	<	* @param keyType the type of key that <tt>m</tt> is permitted to hold
2923	<	* @param valueType the type of value that <tt>m</tt> is permitted to hold
2921	>	* returned
2922	>	* @param keyType the type of key that {@code m} is permitted to hold
2923	>	* @param valueType the type of value that {@code m} is permitted to hold
2924		* @return a dynamically typesafe view of the specified map
2925		* @since 1.5
2926		*/
#	Line 2849 \| Line 2951 \| public class Collections {
2951		public K lastKey() { return sm.lastKey(); }
2952
2953		public SortedMap<K,V> subMap(K fromKey, K toKey) {
2954	<	return new CheckedSortedMap<K,V>(sm.subMap(fromKey, toKey),
2955	<	keyType, valueType);
2954	>	return checkedSortedMap(sm.subMap(fromKey, toKey),
2955	>	keyType, valueType);
2956		}
2855	–
2957		public SortedMap<K,V> headMap(K toKey) {
2958	<	return new CheckedSortedMap<K,V>(sm.headMap(toKey),
2858	<	keyType, valueType);
2958	>	return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
2959		}
2860	–
2960		public SortedMap<K,V> tailMap(K fromKey) {
2961	<	return new CheckedSortedMap<K,V>(sm.tailMap(fromKey),
2863	<	keyType, valueType);
2961	>	return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
2962		}
2963		}
2964
2965	<	// Miscellaneous
2965	>	// Empty collections
2966	>
2967	>	/**
2968	>	* Returns an iterator that has no elements. More precisely,
2969	>	*
2970	>	* <ul compact>
2971	>	*
2972	>	* <li>{@link Iterator#hasNext hasNext} always returns {@code
2973	>	* false}.
2974	>	*
2975	>	* <li>{@link Iterator#next next} always throws {@link
2976	>	* NoSuchElementException}.
2977	>	*
2978	>	* <li>{@link Iterator#remove remove} always throws {@link
2979	>	* IllegalStateException}.
2980	>	*
2981	>	* </ul>
2982	>	*
2983	>	* <p>Implementations of this method are permitted, but not
2984	>	* required, to return the same object from multiple invocations.
2985	>	*
2986	>	* @return an empty iterator
2987	>	* @since 1.7
2988	>	*/
2989	>	@SuppressWarnings("unchecked")
2990	>	public static <T> Iterator<T> emptyIterator() {
2991	>	return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
2992	>	}
2993	>
2994	>	private static class EmptyIterator<E> implements Iterator<E> {
2995	>	static final EmptyIterator<Object> EMPTY_ITERATOR
2996	>	= new EmptyIterator<Object>();
2997	>
2998	>	public boolean hasNext() { return false; }
2999	>	public E next() { throw new NoSuchElementException(); }
3000	>	public void remove() { throw new IllegalStateException(); }
3001	>	}
3002	>
3003	>	/**
3004	>	* Returns a list iterator that has no elements. More precisely,
3005	>	*
3006	>	* <ul compact>
3007	>	*
3008	>	* <li>{@link Iterator#hasNext hasNext} and {@link
3009	>	* ListIterator#hasPrevious hasPrevious} always return {@code
3010	>	* false}.
3011	>	*
3012	>	* <li>{@link Iterator#next next} and {@link ListIterator#previous
3013	>	* previous} always throw {@link NoSuchElementException}.
3014	>	*
3015	>	* <li>{@link Iterator#remove remove} and {@link ListIterator#set
3016	>	* set} always throw {@link IllegalStateException}.
3017	>	*
3018	>	* <li>{@link ListIterator#add add} always throws {@link
3019	>	* UnsupportedOperationException}.
3020	>	*
3021	>	* <li>{@link ListIterator#nextIndex nextIndex} always returns
3022	>	* {@code 0} .
3023	>	*
3024	>	* <li>{@link ListIterator#previousIndex previousIndex} always
3025	>	* returns {@code -1}.
3026	>	*
3027	>	* </ul>
3028	>	*
3029	>	* <p>Implementations of this method are permitted, but not
3030	>	* required, to return the same object from multiple invocations.
3031	>	*
3032	>	* @return an empty list iterator
3033	>	* @since 1.7
3034	>	*/
3035	>	@SuppressWarnings("unchecked")
3036	>	public static <T> ListIterator<T> emptyListIterator() {
3037	>	return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
3038	>	}
3039	>
3040	>	private static class EmptyListIterator<E>
3041	>	extends EmptyIterator<E>
3042	>	implements ListIterator<E>
3043	>	{
3044	>	static final EmptyListIterator<Object> EMPTY_ITERATOR
3045	>	= new EmptyListIterator<Object>();
3046	>
3047	>	public boolean hasPrevious() { return false; }
3048	>	public E previous() { throw new NoSuchElementException(); }
3049	>	public int nextIndex() { return 0; }
3050	>	public int previousIndex() { return -1; }
3051	>	public void set(E e) { throw new IllegalStateException(); }
3052	>	public void add(E e) { throw new UnsupportedOperationException(); }
3053	>	}
3054	>
3055	>	/**
3056	>	* Returns an enumeration that has no elements. More precisely,
3057	>	*
3058	>	* <ul compact>
3059	>	*
3060	>	* <li>{@link Enumeration#hasMoreElements hasMoreElements} always
3061	>	* returns {@code false}.
3062	>	*
3063	>	* <li> {@link Enumeration#nextElement nextElement} always throws
3064	>	* {@link NoSuchElementException}.
3065	>	*
3066	>	* </ul>
3067	>	*
3068	>	* <p>Implementations of this method are permitted, but not
3069	>	* required, to return the same object from multiple invocations.
3070	>	*
3071	>	* @return an empty enumeration
3072	>	* @since 1.7
3073	>	*/
3074	>	@SuppressWarnings("unchecked")
3075	>	public static <T> Enumeration<T> emptyEnumeration() {
3076	>	return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
3077	>	}
3078	>
3079	>	private static class EmptyEnumeration<E> implements Enumeration<E> {
3080	>	static final EmptyEnumeration<Object> EMPTY_ENUMERATION
3081	>	= new EmptyEnumeration<Object>();
3082	>
3083	>	public boolean hasMoreElements() { return false; }
3084	>	public E nextElement() { throw new NoSuchElementException(); }
3085	>	}
3086
3087		/**
3088		* The empty set (immutable). This set is serializable.
3089		*
3090		* @see #emptySet()
3091		*/
3092	<	public static final Set EMPTY_SET = new EmptySet();
3092	>	@SuppressWarnings("unchecked")
3093	>	public static final Set EMPTY_SET = new EmptySet<Object>();
3094
3095		/**
3096		* Returns the empty set (immutable). This set is serializable.
#	Line 2889 \| Line 3108 \| public class Collections {
3108		* @see #EMPTY_SET
3109		* @since 1.5
3110		*/
3111	+	@SuppressWarnings("unchecked")
3112		public static final <T> Set<T> emptySet() {
3113	<	return (Set<T>) EMPTY_SET;
3113	>	return (Set<T>) EMPTY_SET;
3114		}
3115
3116		/**
3117		* @serial include
3118		*/
3119	<	private static class EmptySet extends AbstractSet<Object> implements Serializable {
3120	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3121	<	private static final long serialVersionUID = 1582296315990362920L;
3119	>	private static class EmptySet<E>
3120	>	extends AbstractSet<E>
3121	>	implements Serializable
3122	>	{
3123	>	private static final long serialVersionUID = 1582296315990362920L;
3124
3125	<	public Iterator<Object> iterator() {
2904	<	return new Iterator<Object>() {
2905	<	public boolean hasNext() {
2906	<	return false;
2907	<	}
2908	<	public Object next() {
2909	<	throw new NoSuchElementException();
2910	<	}
2911	<	public void remove() {
2912	<	throw new UnsupportedOperationException();
2913	<	}
2914	<	};
2915	<	}
3125	>	public Iterator<E> iterator() { return emptyIterator(); }
3126
3127		public int size() {return 0;}
3128	+	public boolean isEmpty() {return true;}
3129
3130		public boolean contains(Object obj) {return false;}
3131	+	public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3132	+
3133	+	public Object[] toArray() { return new Object[0]; }
3134	+
3135	+	public <T> T[] toArray(T[] a) {
3136	+	if (a.length > 0)
3137	+	a[0] = null;
3138	+	return a;
3139	+	}
3140
3141		// Preserves singleton property
3142		private Object readResolve() {
#	Line 2929 \| Line 3149 \| public class Collections {
3149		*
3150		* @see #emptyList()
3151		*/
3152	<	public static final List EMPTY_LIST = new EmptyList();
3152	>	@SuppressWarnings("unchecked")
3153	>	public static final List EMPTY_LIST = new EmptyList<Object>();
3154
3155		/**
3156		* Returns the empty list (immutable). This list is serializable.
#	Line 2946 \| Line 3167 \| public class Collections {
3167		* @see #EMPTY_LIST
3168		* @since 1.5
3169		*/
3170	+	@SuppressWarnings("unchecked")
3171		public static final <T> List<T> emptyList() {
3172	<	return (List<T>) EMPTY_LIST;
3172	>	return (List<T>) EMPTY_LIST;
3173		}
3174
3175		/**
3176		* @serial include
3177		*/
3178	<	private static class EmptyList
3179	<	extends AbstractList<Object>
3180	<	implements RandomAccess, Serializable {
3181	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3182	<	private static final long serialVersionUID = 8842843931221139166L;
3178	>	private static class EmptyList<E>
3179	>	extends AbstractList<E>
3180	>	implements RandomAccess, Serializable {
3181	>	private static final long serialVersionUID = 8842843931221139166L;
3182	>
3183	>	public Iterator<E> iterator() {
3184	>	return emptyIterator();
3185	>	}
3186	>	public ListIterator<E> listIterator() {
3187	>	return emptyListIterator();
3188	>	}
3189
3190		public int size() {return 0;}
3191	+	public boolean isEmpty() {return true;}
3192
3193		public boolean contains(Object obj) {return false;}
3194	+	public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3195
3196	<	public Object get(int index) {
3196	>	public Object[] toArray() { return new Object[0]; }
3197	>
3198	>	public <T> T[] toArray(T[] a) {
3199	>	if (a.length > 0)
3200	>	a[0] = null;
3201	>	return a;
3202	>	}
3203	>
3204	>	public E get(int index) {
3205		throw new IndexOutOfBoundsException("Index: "+index);
3206		}
3207
3208	+	public boolean equals(Object o) {
3209	+	return (o instanceof List) && ((List<?>)o).isEmpty();
3210	+	}
3211	+
3212	+	public int hashCode() { return 1; }
3213	+
3214		// Preserves singleton property
3215		private Object readResolve() {
3216		return EMPTY_LIST;
#	Line 2979 \| Line 3223 \| public class Collections {
3223		* @see #emptyMap()
3224		* @since 1.3
3225		*/
3226	<	public static final Map EMPTY_MAP = new EmptyMap();
3226	>	@SuppressWarnings("unchecked")
3227	>	public static final Map EMPTY_MAP = new EmptyMap<Object,Object>();
3228
3229		/**
3230		* Returns the empty map (immutable). This map is serializable.
#	Line 2996 \| Line 3241 \| public class Collections {
3241		* @see #EMPTY_MAP
3242		* @since 1.5
3243		*/
3244	+	@SuppressWarnings("unchecked")
3245		public static final <K,V> Map<K,V> emptyMap() {
3246	<	return (Map<K,V>) EMPTY_MAP;
3246	>	return (Map<K,V>) EMPTY_MAP;
3247		}
3248
3249	<	private static class EmptyMap
3250	<	extends AbstractMap<Object,Object>
3251	<	implements Serializable {
3252	<
3249	>	/**
3250	>	* @serial include
3251	>	*/
3252	>	private static class EmptyMap<K,V>
3253	>	extends AbstractMap<K,V>
3254	>	implements Serializable
3255	>	{
3256		private static final long serialVersionUID = 6428348081105594320L;
3257
3258		public int size() {return 0;}
3010	–
3259		public boolean isEmpty() {return true;}
3012	–
3260		public boolean containsKey(Object key) {return false;}
3014	–
3261		public boolean containsValue(Object value) {return false;}
3262	<
3263	<	public Object get(Object key) {return null;}
3264	<
3265	<	public Set<Object> keySet() {return Collections.<Object>emptySet();}
3020	<
3021	<	public Collection<Object> values() {return Collections.<Object>emptySet();}
3022	<
3023	<	public Set<Map.Entry<Object,Object>> entrySet() {
3024	<	return Collections.emptySet();
3025	<	}
3262	>	public V get(Object key) {return null;}
3263	>	public Set<K> keySet() {return emptySet();}
3264	>	public Collection<V> values() {return emptySet();}
3265	>	public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
3266
3267		public boolean equals(Object o) {
3268	<	return (o instanceof Map) && ((Map)o).size()==0;
3268	>	return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
3269		}
3270
3271		public int hashCode() {return 0;}
#	Line 3036 \| Line 3276 \| public class Collections {
3276		}
3277		}
3278
3279	+	// Singleton collections
3280	+
3281		/**
3282		* Returns an immutable set containing only the specified object.
3283		* The returned set is serializable.
#	Line 3044 \| Line 3286 \| public class Collections {
3286		* @return an immutable set containing only the specified object.
3287		*/
3288		public static <T> Set<T> singleton(T o) {
3289	<	return new SingletonSet<T>(o);
3289	>	return new SingletonSet<T>(o);
3290	>	}
3291	>
3292	>	static <E> Iterator<E> singletonIterator(final E e) {
3293	>	return new Iterator<E>() {
3294	>	private boolean hasNext = true;
3295	>	public boolean hasNext() {
3296	>	return hasNext;
3297	>	}
3298	>	public E next() {
3299	>	if (hasNext) {
3300	>	hasNext = false;
3301	>	return e;
3302	>	}
3303	>	throw new NoSuchElementException();
3304	>	}
3305	>	public void remove() {
3306	>	throw new UnsupportedOperationException();
3307	>	}
3308	>	};
3309		}
3310
3311		/**
3312		* @serial include
3313		*/
3314		private static class SingletonSet<E>
3315	<	extends AbstractSet<E>
3316	<	implements Serializable
3315	>	extends AbstractSet<E>
3316	>	implements Serializable
3317		{
3318	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3058	<	private static final long serialVersionUID = 3193687207550431679L;
3318	>	private static final long serialVersionUID = 3193687207550431679L;
3319
3320	<	final private E element;
3320	>	private final E element;
3321
3322		SingletonSet(E e) {element = e;}
3323
3324		public Iterator<E> iterator() {
3325	<	return new Iterator<E>() {
3066	<	private boolean hasNext = true;
3067	<	public boolean hasNext() {
3068	<	return hasNext;
3069	<	}
3070	<	public E next() {
3071	<	if (hasNext) {
3072	<	hasNext = false;
3073	<	return element;
3074	<	}
3075	<	throw new NoSuchElementException();
3076	<	}
3077	<	public void remove() {
3078	<	throw new UnsupportedOperationException();
3079	<	}
3080	<	};
3325	>	return singletonIterator(element);
3326		}
3327
3328		public int size() {return 1;}
#	Line 3094 \| Line 3339 \| public class Collections {
3339		* @since 1.3
3340		*/
3341		public static <T> List<T> singletonList(T o) {
3342	<	return new SingletonList<T>(o);
3342	>	return new SingletonList<T>(o);
3343		}
3344
3345	+	/**
3346	+	* @serial include
3347	+	*/
3348		private static class SingletonList<E>
3349	<	extends AbstractList<E>
3350	<	implements RandomAccess, Serializable {
3349	>	extends AbstractList<E>
3350	>	implements RandomAccess, Serializable {
3351
3352	<	static final long serialVersionUID = 3093736618740652951L;
3352	>	private static final long serialVersionUID = 3093736618740652951L;
3353
3354		private final E element;
3355
3356		SingletonList(E obj) {element = obj;}
3357
3358	+	public Iterator<E> iterator() {
3359	+	return singletonIterator(element);
3360	+	}
3361	+
3362		public int size() {return 1;}
3363
3364		public boolean contains(Object obj) {return eq(obj, element);}
#	Line 3129 \| Line 3381 \| public class Collections {
3381		* @since 1.3
3382		*/
3383		public static <K,V> Map<K,V> singletonMap(K key, V value) {
3384	<	return new SingletonMap<K,V>(key, value);
3384	>	return new SingletonMap<K,V>(key, value);
3385		}
3386
3387	+	/**
3388	+	* @serial include
3389	+	*/
3390		private static class SingletonMap<K,V>
3391	<	extends AbstractMap<K,V>
3392	<	implements Serializable {
3393	<	private static final long serialVersionUID = -6979724477215052911L;
3391	>	extends AbstractMap<K,V>
3392	>	implements Serializable {
3393	>	private static final long serialVersionUID = -6979724477215052911L;
3394
3395		private final K k;
3396	<	private final V v;
3396	>	private final V v;
3397
3398		SingletonMap(K key, V value) {
3399		k = key;
#	Line 3159 \| Line 3414 \| public class Collections {
3414		private transient Set<Map.Entry<K,V>> entrySet = null;
3415		private transient Collection<V> values = null;
3416
3417	<	public Set<K> keySet() {
3418	<	if (keySet==null)
3419	<	keySet = singleton(k);
3420	<	return keySet;
3421	<	}
3422	<
3423	<	public Set<Map.Entry<K,V>> entrySet() {
3424	<	if (entrySet==null)
3425	<	entrySet = Collections.<Map.Entry<K,V>>singleton(
3426	<	new SimpleImmutableEntry<K,V>(k, v));
3427	<	return entrySet;
3428	<	}
3429	<
3430	<	public Collection<V> values() {
3431	<	if (values==null)
3432	<	values = singleton(v);
3433	<	return values;
3434	<	}
3417	>	public Set<K> keySet() {
3418	>	if (keySet==null)
3419	>	keySet = singleton(k);
3420	>	return keySet;
3421	>	}
3422	>
3423	>	public Set<Map.Entry<K,V>> entrySet() {
3424	>	if (entrySet==null)
3425	>	entrySet = Collections.<Map.Entry<K,V>>singleton(
3426	>	new SimpleImmutableEntry<K,V>(k, v));
3427	>	return entrySet;
3428	>	}
3429	>
3430	>	public Collection<V> values() {
3431	>	if (values==null)
3432	>	values = singleton(v);
3433	>	return values;
3434	>	}
3435
3436		}
3437
3438	+	// Miscellaneous
3439	+
3440		/**
3441		* Returns an immutable list consisting of <tt>n</tt> copies of the
3442		* specified object. The newly allocated data object is tiny (it contains
#	Line 3190 \| Line 3447 \| public class Collections {
3447		* @param n the number of elements in the returned list.
3448		* @param o the element to appear repeatedly in the returned list.
3449		* @return an immutable list consisting of <tt>n</tt> copies of the
3450	<	* specified object.
3451	<	* @throws IllegalArgumentException if n < 0.
3450	>	* specified object.
3451	>	* @throws IllegalArgumentException if {@code n < 0}
3452		* @see List#addAll(Collection)
3453		* @see List#addAll(int, Collection)
3454		*/
3455		public static <T> List<T> nCopies(int n, T o) {
3456	+	if (n < 0)
3457	+	throw new IllegalArgumentException("List length = " + n);
3458		return new CopiesList<T>(n, o);
3459		}
3460
#	Line 3203 \| Line 3462 \| public class Collections {
3462		* @serial include
3463		*/
3464		private static class CopiesList<E>
3465	<	extends AbstractList<E>
3466	<	implements RandomAccess, Serializable
3465	>	extends AbstractList<E>
3466	>	implements RandomAccess, Serializable
3467		{
3468	<	static final long serialVersionUID = 2739099268398711800L;
3468	>	private static final long serialVersionUID = 2739099268398711800L;
3469
3470	<	int n;
3471	<	E element;
3470	>	final int n;
3471	>	final E element;
3472
3473		CopiesList(int n, E e) {
3474	<	if (n < 0)
3216	<	throw new IllegalArgumentException("List length = " + n);
3474	>	assert n >= 0;
3475		this.n = n;
3476		element = e;
3477		}
#	Line 3226 \| Line 3484 \| public class Collections {
3484		return n != 0 && eq(obj, element);
3485		}
3486
3487	+	public int indexOf(Object o) {
3488	+	return contains(o) ? 0 : -1;
3489	+	}
3490	+
3491	+	public int lastIndexOf(Object o) {
3492	+	return contains(o) ? n - 1 : -1;
3493	+	}
3494	+
3495		public E get(int index) {
3496	<	if (index<0 \|\| index>=n)
3496	>	if (index < 0 \|\| index >= n)
3497		throw new IndexOutOfBoundsException("Index: "+index+
3498		", Size: "+n);
3499		return element;
3500		}
3501	+
3502	+	public Object[] toArray() {
3503	+	final Object[] a = new Object[n];
3504	+	if (element != null)
3505	+	Arrays.fill(a, 0, n, element);
3506	+	return a;
3507	+	}
3508	+
3509	+	public <T> T[] toArray(T[] a) {
3510	+	final int n = this.n;
3511	+	if (a.length < n) {
3512	+	a = (T[])java.lang.reflect.Array
3513	+	.newInstance(a.getClass().getComponentType(), n);
3514	+	if (element != null)
3515	+	Arrays.fill(a, 0, n, element);
3516	+	} else {
3517	+	Arrays.fill(a, 0, n, element);
3518	+	if (a.length > n)
3519	+	a[n] = null;
3520	+	}
3521	+	return a;
3522	+	}
3523	+
3524	+	public List<E> subList(int fromIndex, int toIndex) {
3525	+	if (fromIndex < 0)
3526	+	throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3527	+	if (toIndex > n)
3528	+	throw new IndexOutOfBoundsException("toIndex = " + toIndex);
3529	+	if (fromIndex > toIndex)
3530	+	throw new IllegalArgumentException("fromIndex(" + fromIndex +
3531	+	") > toIndex(" + toIndex + ")");
3532	+	return new CopiesList<E>(toIndex - fromIndex, element);
3533	+	}
3534		}
3535
3536		/**
#	Line 3243 \| Line 3542 \| public class Collections {
3542		* objects that implement the <tt>Comparable</tt> interface in
3543		* reverse-natural-order. For example, suppose a is an array of
3544		* strings. Then: <pre>
3545	<	* Arrays.sort(a, Collections.reverseOrder());
3545	>	* Arrays.sort(a, Collections.reverseOrder());
3546		* </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
3547		*
3548		* The returned comparator is serializable.
3549		*
3550		* @return a comparator that imposes the reverse of the <i>natural
3551	<	* ordering</i> on a collection of objects that implement
3552	<	* the <tt>Comparable</tt> interface.
3551	>	* ordering</i> on a collection of objects that implement
3552	>	* the <tt>Comparable</tt> interface.
3553		* @see Comparable
3554		*/
3555		public static <T> Comparator<T> reverseOrder() {
3556	<	return (Comparator<T>) REVERSE_ORDER;
3556	>	return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3557		}
3558
3260	–	private static final Comparator REVERSE_ORDER = new ReverseComparator();
3261	–
3559		/**
3560		* @serial include
3561		*/
3562	<	private static class ReverseComparator<T>
3563	<	implements Comparator<Comparable<Object>>, Serializable {
3562	>	private static class ReverseComparator
3563	>	implements Comparator<Comparable<Object>>, Serializable {
3564
3565	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3566	<	private static final long serialVersionUID = 7207038068494060240L;
3565	>	private static final long serialVersionUID = 7207038068494060240L;
3566	>
3567	>	static final ReverseComparator REVERSE_ORDER
3568	>	= new ReverseComparator();
3569
3570		public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3571		return c2.compareTo(c1);
3572		}
3573	+
3574	+	private Object readResolve() { return reverseOrder(); }
3575		}
3576
3577		/**
#	Line 3284 \| Line 3585 \| public class Collections {
3585		* comparator is also serializable or null).
3586		*
3587		* @return a comparator that imposes the reverse ordering of the
3588	<	* specified comparator.
3588	>	* specified comparator
3589		* @since 1.5
3590		*/
3591		public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3592		if (cmp == null)
3593	<	return new ReverseComparator(); // Unchecked warning!!
3593	>	return reverseOrder();
3594	>
3595	>	if (cmp instanceof ReverseComparator2)
3596	>	return ((ReverseComparator2<T>)cmp).cmp;
3597
3598		return new ReverseComparator2<T>(cmp);
3599		}
#	Line 3309 \| Line 3613 \| public class Collections {
3613		*
3614		* @serial
3615		*/
3616	<	private Comparator<T> cmp;
3616	>	final Comparator<T> cmp;
3617
3618		ReverseComparator2(Comparator<T> cmp) {
3619		assert cmp != null;
#	Line 3319 \| Line 3623 \| public class Collections {
3623		public int compare(T t1, T t2) {
3624		return cmp.compare(t2, t1);
3625		}
3626	+
3627	+	public boolean equals(Object o) {
3628	+	return (o == this) \|\|
3629	+	(o instanceof ReverseComparator2 &&
3630	+	cmp.equals(((ReverseComparator2)o).cmp));
3631	+	}
3632	+
3633	+	public int hashCode() {
3634	+	return cmp.hashCode() ^ Integer.MIN_VALUE;
3635	+	}
3636		}
3637
3638		/**
#	Line 3331 \| Line 3645 \| public class Collections {
3645		* @see Enumeration
3646		*/
3647		public static <T> Enumeration<T> enumeration(final Collection<T> c) {
3648	<	return new Enumeration<T>() {
3649	<	Iterator<T> i = c.iterator();
3648	>	return new Enumeration<T>() {
3649	>	private final Iterator<T> i = c.iterator();
3650	>
3651	>	public boolean hasMoreElements() {
3652	>	return i.hasNext();
3653	>	}
3654
3655	<	public boolean hasMoreElements() {
3656	<	return i.hasNext();
3657	<	}
3340	<
3341	<	public T nextElement() {
3342	<	return i.next();
3343	<	}
3655	>	public T nextElement() {
3656	>	return i.next();
3657	>	}
3658		};
3659		}
3660
#	Line 3369 \| Line 3683 \| public class Collections {
3683		/**
3684		* Returns true if the specified arguments are equal, or both null.
3685		*/
3686	<	private static boolean eq(Object o1, Object o2) {
3687	<	return (o1==null ? o2==null : o1.equals(o2));
3686	>	static boolean eq(Object o1, Object o2) {
3687	>	return o1==null ? o2==null : o1.equals(o2);
3688		}
3689
3690		/**
#	Line 3456 \| Line 3770 \| public class Collections {
3770		* </pre>
3771		*
3772		* @param c the collection into which <tt>elements</tt> are to be inserted
3773	<	* @param a the elements to insert into <tt>c</tt>
3773	>	* @param elements the elements to insert into <tt>c</tt>
3774		* @return <tt>true</tt> if the collection changed as a result of the call
3775		* @throws UnsupportedOperationException if <tt>c</tt> does not support
3776	<	* the <tt>add</tt> operation.
3776	>	* the <tt>add</tt> operation
3777		* @throws NullPointerException if <tt>elements</tt> contains one or more
3778		* null values and <tt>c</tt> does not permit null elements, or
3779		* if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
#	Line 3468 \| Line 3782 \| public class Collections {
3782		* @see Collection#addAll(Collection)
3783		* @since 1.5
3784		*/
3785	<	public static <T> boolean addAll(Collection<? super T> c, T... a) {
3785	>	public static <T> boolean addAll(Collection<? super T> c, T... elements) {
3786		boolean result = false;
3787	<	for (T e : a)
3788	<	result \|= c.add(e);
3787	>	for (T element : elements)
3788	>	result \|= c.add(element);
3789		return result;
3790		}
3791
#	Line 3495 \| Line 3809 \| public class Collections {
3809		* to this method, and no reference to the map is retained, as illustrated
3810		* in the following code fragment:
3811		* <pre>
3812	<	* Set<Object> weakHashSet = Collections.asSet(
3812	>	* Set<Object> weakHashSet = Collections.newSetFromMap(
3813		* new WeakHashMap<Object, Boolean>());
3814		* </pre>
3815		*
3816		* @param map the backing map
3817		* @return the set backed by the map
3818		* @throws IllegalArgumentException if <tt>map</tt> is not empty
3819	+	* @since 1.6
3820		*/
3821	<	public static <E> Set<E> asSet(Map<E, Boolean> map) {
3822	<	return new MapAsSet<E>(map);
3821	>	public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
3822	>	return new SetFromMap<E>(map);
3823		}
3824
3825	<	private static class MapAsSet<E> extends AbstractSet<E>
3825	>	/**
3826	>	* @serial include
3827	>	*/
3828	>	private static class SetFromMap<E> extends AbstractSet<E>
3829		implements Set<E>, Serializable
3830		{
3831		private final Map<E, Boolean> m; // The backing map
3832	<	private transient Set<E> keySet; // Its keySet
3832	>	private transient Set<E> s; // Its keySet
3833
3834	<	MapAsSet(Map<E, Boolean> map) {
3834	>	SetFromMap(Map<E, Boolean> map) {
3835		if (!map.isEmpty())
3836		throw new IllegalArgumentException("Map is non-empty");
3837		m = map;
3838	<	keySet = map.keySet();
3838	>	s = map.keySet();
3839		}
3840
3841	+	public void clear() { m.clear(); }
3842		public int size() { return m.size(); }
3843		public boolean isEmpty() { return m.isEmpty(); }
3844		public boolean contains(Object o) { return m.containsKey(o); }
3526	–	public Iterator<E> iterator() { return keySet.iterator(); }
3527	–	public Object[] toArray() { return keySet.toArray(); }
3528	–	public <T> T[] toArray(T[] a) { return keySet.toArray(a); }
3529	–	public boolean add(E e) {
3530	–	return m.put(e, Boolean.TRUE) == null;
3531	–	}
3845		public boolean remove(Object o) { return m.remove(o) != null; }
3846	<
3847	<	public boolean removeAll(Collection<?> c) {
3848	<	return keySet.removeAll(c);
3849	<	}
3850	<	public boolean retainAll(Collection<?> c) {
3851	<	return keySet.retainAll(c);
3852	<	}
3853	<	public void clear() { m.clear(); }
3854	<	public boolean equals(Object o) { return keySet.equals(o); }
3855	<	public int hashCode() { return keySet.hashCode(); }
3846	>	public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3847	>	public Iterator<E> iterator() { return s.iterator(); }
3848	>	public Object[] toArray() { return s.toArray(); }
3849	>	public <T> T[] toArray(T[] a) { return s.toArray(a); }
3850	>	public String toString() { return s.toString(); }
3851	>	public int hashCode() { return s.hashCode(); }
3852	>	public boolean equals(Object o) { return o == this \|\| s.equals(o); }
3853	>	public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3854	>	public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
3855	>	public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
3856	>	// addAll is the only inherited implementation
3857
3858		private static final long serialVersionUID = 2454657854757543876L;
3859
3860	<	private void readObject(java.io.ObjectInputStream s)
3860	>	private void readObject(java.io.ObjectInputStream stream)
3861		throws IOException, ClassNotFoundException
3862		{
3863	<	s.defaultReadObject();
3864	<	keySet = m.keySet();
3863	>	stream.defaultReadObject();
3864	>	s = m.keySet();
3865		}
3866		}
3867
#	Line 3557 \| Line 3871 \| public class Collections {
3871		* <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
3872		* view can be useful when you would like to use a method
3873		* requiring a <tt>Queue</tt> but you need Lifo ordering.
3874	<	* @param deque the Deque
3874	>	*
3875	>	* <p>Each method invocation on the queue returned by this method
3876	>	* results in exactly one method invocation on the backing deque, with
3877	>	* one exception. The {@link Queue#addAll addAll} method is
3878	>	* implemented as a sequence of {@link Deque#addFirst addFirst}
3879	>	* invocations on the backing deque.
3880	>	*
3881	>	* @param deque the deque
3882		* @return the queue
3883		* @since 1.6
3884		*/
#	Line 3565 \| Line 3886 \| public class Collections {
3886		return new AsLIFOQueue<T>(deque);
3887		}
3888
3889	+	/**
3890	+	* @serial include
3891	+	*/
3892		static class AsLIFOQueue<E> extends AbstractQueue<E>
3893		implements Queue<E>, Serializable {
3894	<	private static final long serialVersionUID = 1802017725587941708L;
3894	>	private static final long serialVersionUID = 1802017725587941708L;
3895		private final Deque<E> q;
3896	<	AsLIFOQueue(Deque<E> q) { this.q = q; }
3897	<	public boolean offer(E e) { return q.offerFirst(e); }
3898	<	public E poll() { return q.pollFirst(); }
3899	<	public E remove() { return q.removeFirst(); }
3900	<	public E peek() { return q.peekFirst(); }
3901	<	public E element() { return q.getFirst(); }
3902	<	public int size() { return q.size(); }
3903	<	public boolean isEmpty() { return q.isEmpty(); }
3904	<	public boolean contains(Object o) { return q.contains(o); }
3905	<	public Iterator<E> iterator() { return q.iterator(); }
3906	<	public Object[] toArray() { return q.toArray(); }
3907	<	public <T> T[] toArray(T[] a) { return q.toArray(a); }
3908	<	public boolean add(E e) { return q.offerFirst(e); }
3909	<	public boolean remove(Object o) { return q.remove(o); }
3910	<	public void clear() { q.clear(); }
3896	>	AsLIFOQueue(Deque<E> q) { this.q = q; }
3897	>	public boolean add(E e) { q.addFirst(e); return true; }
3898	>	public boolean offer(E e) { return q.offerFirst(e); }
3899	>	public E poll() { return q.pollFirst(); }
3900	>	public E remove() { return q.removeFirst(); }
3901	>	public E peek() { return q.peekFirst(); }
3902	>	public E element() { return q.getFirst(); }
3903	>	public void clear() { q.clear(); }
3904	>	public int size() { return q.size(); }
3905	>	public boolean isEmpty() { return q.isEmpty(); }
3906	>	public boolean contains(Object o) { return q.contains(o); }
3907	>	public boolean remove(Object o) { return q.remove(o); }
3908	>	public Iterator<E> iterator() { return q.iterator(); }
3909	>	public Object[] toArray() { return q.toArray(); }
3910	>	public <T> T[] toArray(T[] a) { return q.toArray(a); }
3911	>	public String toString() { return q.toString(); }
3912	>	public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3913	>	public boolean removeAll(Collection<?> c) {return q.removeAll(c);}
3914	>	public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
3915	>	// We use inherited addAll; forwarding addAll would be wrong
3916		}
3917		}

Diff Legend

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

Comparing jsr166/src/main/java/util/Collections.java (file contents): Revision 1.11 by jsr166, Mon Jun 20 18:03:08 2005 UTC vs. Revision 1.43 by jsr166, Sat Oct 16 16:44:39 2010 UTC

Diff Legend

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.11 by jsr166, Mon Jun 20 18:03:08 2005 UTC vs.
Revision 1.43 by jsr166, Sat Oct 16 16:44:39 2010 UTC