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

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.32 by jsr166, Tue Sep 11 15:18:34 2007 UTC vs.
Revision 1.43 by jsr166, Sat Oct 16 16:44:39 2010 UTC

#	Line 1 \| Line 1
1		/*
2	<	* Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
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		* This code is free software; you can redistribute it and/or modify it
#	Line 18 \| Line 18
18		* 2 along with this work; if not, write to the Free Software Foundation,
19		* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20		*
21	<	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	<	* CA 95054 USA or visit www.sun.com if you need additional information or
23	<	* have any questions.
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;
#	Line 61 \| Line 61 \| import java.lang.reflect.Array;
61		*
62		* @author Josh Bloch
63		* @author Neal Gafter
64	<	* @version %I%, %G%
65	<	* @see Collection
66	<	* @see Set
67	<	* @see List
68	<	* @see Map
64	>	* @see Collection
65	>	* @see Set
66	>	* @see List
67	>	* @see Map
68		* @since 1.2
69		*/
70
#	Line 101 \| 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 125 \| 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
151	<	* 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.
159	<	* 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 164 \| 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
#	Line 201 \| 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 is not mutually comparable
254	<	* with the elements of the 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 224 \| 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)
238	<	high = mid - 1;
239	<	else
240	<	return mid; // key found
241	<	}
242	<	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) {
#	Line 269 \| 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 303 \| Line 343 \| public class Collections {
343		* @param key the key to be searched for.
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.
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 is not mutually comparable with the
358	<	* elements of the list using this 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 328 \| 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	<	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
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	>	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) {
#	Line 387 \| 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 488 \| 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 510 \| 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 554 \| 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 578 \| 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 613 \| 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 621 \| 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 648 \| 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 683 \| 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 691 \| 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 783 \| 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 991 \| 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	<	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	<	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();
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 1069 \| 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 o == this \|\| 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 1101 \| 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 1127 \| 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 1147 \| 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 1156 \| Line 1196 \| public class Collections {
1196		* @serial include
1197		*/
1198		static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1199	<	implements List<E> {
1199	>	implements List<E> {
1200		private static final long serialVersionUID = -283967356065247728L;
1201	<	final List<? extends E> list;
1201	>	final List<? extends E> list;
1202	>
1203	>	UnmodifiableList(List<? extends E> list) {
1204	>	super(list);
1205	>	this.list = list;
1206	>	}
1207	>
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	<	UnmodifiableList(List<? extends E> list) {
1229	<	super(list);
1230	<	this.list = list;
1231	<	}
1232	<
1233	<	public boolean equals(Object o) {return o == this \|\| list.equals(o);}
1234	<	public int hashCode() {return list.hashCode();}
1235	<
1236	<	public E get(int index) {return list.get(index);}
1237	<	public E set(int index, E element) {
1238	<	throw new UnsupportedOperationException();
1174	<	}
1175	<	public void add(int index, E element) {
1176	<	throw new UnsupportedOperationException();
1177	<	}
1178	<	public E remove(int index) {
1179	<	throw new UnsupportedOperationException();
1180	<	}
1181	<	public int indexOf(Object o) {return list.indexOf(o);}
1182	<	public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1183	<	public boolean addAll(int index, Collection<? extends E> c) {
1184	<	throw new UnsupportedOperationException();
1185	<	}
1186	<	public ListIterator<E> listIterator() {return listIterator(0);}
1187	<
1188	<	public ListIterator<E> listIterator(final int index) {
1189	<	return new ListIterator<E>() {
1190	<	private final ListIterator<? extends E> i
1191	<	= list.listIterator(index);
1192	<
1193	<	public boolean hasNext() {return i.hasNext();}
1194	<	public E next() {return i.next();}
1195	<	public boolean hasPrevious() {return i.hasPrevious();}
1196	<	public E previous() {return i.previous();}
1197	<	public int nextIndex() {return i.nextIndex();}
1198	<	public int previousIndex() {return i.previousIndex();}
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();
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 1227 \| 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 1242 \| 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 1275 \| 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	<	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);}
1300	<
1301	<	public V put(K key, V value) {
1302	<	throw new UnsupportedOperationException();
1303	<	}
1304	<	public V remove(Object key) {
1305	<	throw new UnsupportedOperationException();
1306	<	}
1307	<	public void putAll(Map<? extends K, ? extends V> m) {
1308	<	throw new UnsupportedOperationException();
1309	<	}
1310	<	public void clear() {
1311	<	throw new UnsupportedOperationException();
1312	<	}
1313	<
1314	<	private transient Set<K> keySet = null;
1315	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1316	<	private transient Collection<V> values = null;
1317	<
1318	<	public Set<K> keySet() {
1319	<	if (keySet==null)
1320	<	keySet = unmodifiableSet(m.keySet());
1321	<	return keySet;
1322	<	}
1323	<
1324	<	public Set<Map.Entry<K,V>> entrySet() {
1325	<	if (entrySet==null)
1326	<	entrySet = new UnmodifiableEntrySet<K,V>(m.entrySet());
1327	<	return entrySet;
1328	<	}
1329	<
1330	<	public Collection<V> values() {
1331	<	if (values==null)
1332	<	values = unmodifiableCollection(m.values());
1333	<	return values;
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 boolean equals(Object o) {return o == this \|\| m.equals(o);}
1342	<	public int hashCode() {return m.hashCode();}
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 o == this \|\| m.equals(o);}
1377	>	public int hashCode() {return m.hashCode();}
1378		public String toString() {return m.toString();}
1379
1380		/**
#	Line 1346 \| 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	<	private final 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 1379 \| 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 1403 \| Line 1443 \| public class Collections {
1443		if (!(o instanceof Map.Entry))
1444		return false;
1445		return c.contains(
1446	<	new UnmodifiableEntry<Object,Object>((Map.Entry<?,?>) o));
1446	>	new UnmodifiableEntry<Object,Object>((Map.Entry<?,?>) o));
1447		}
1448
1449		/**
#	Line 1412 \| 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 1442 \| 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 1455 \| 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 1477 \| 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 1522 \| 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 1543 \| 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	<	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 1631 \| 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 1646 \| 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 1688 \| 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 1699 \| 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 1714 \| 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 1777 \| 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 1792 \| 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 1807 \| Line 1847 \| public class Collections {
1847		* @serial include
1848		*/
1849		static class SynchronizedList<E>
1850	<	extends SynchronizedCollection<E>
1851	<	implements List<E> {
1850	>	extends SynchronizedCollection<E>
1851	>	implements List<E> {
1852		private static final long serialVersionUID = -7754090372962971524L;
1853
1854	<	final List<E> list;
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) {
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 1882 \| 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 1891 \| 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		}
#	Line 1935 \| 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 1950 \| 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	<	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		}
2003	–	public void clear() {
2004	–	synchronized(mutex) {m.clear();}
2005	–	}
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 2061 \| 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 2074 \| 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 2089 \| 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 2097 \| 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
#	Line 2211 \| Line 2251 \| public class Collections {
2251
2252		@SuppressWarnings("unchecked")
2253		static <T> T[] zeroLengthArray(Class<T> type) {
2254	<	return (T[]) Array.newInstance(type, 0);
2254	>	return (T[]) Array.newInstance(type, 0);
2255		}
2256
2257		/**
#	Line 2228 \| Line 2268 \| public class Collections {
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	<	}
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) {
2277		if (c==null \|\| type == null)
#	Line 2249 \| Line 2289 \| public class Collections {
2289		public boolean remove(Object o) { return c.remove(o); }
2290		public void clear() { c.clear(); }
2291
2292	<	public boolean containsAll(Collection<?> coll) {
2292	>	public boolean containsAll(Collection<?> coll) {
2293		return c.containsAll(coll);
2294		}
2295		public boolean removeAll(Collection<?> coll) {
#	Line 2260 \| Line 2300 \| public class Collections {
2300		}
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	<	}
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		private E[] zeroLengthElementArray = null; // Lazily initialized
2316
2317	<	private E[] zeroLengthElementArray() {
2318	<	return zeroLengthElementArray != null ? zeroLengthElementArray :
2319	<	(zeroLengthElementArray = zeroLengthArray(type));
2320	<	}
2321	<
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	<	}
2317	>	private E[] zeroLengthElementArray() {
2318	>	return zeroLengthElementArray != null ? zeroLengthElementArray :
2319	>	(zeroLengthElementArray = zeroLengthArray(type));
2320	>	}
2321	>
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		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));
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
#	Line 2452 \| Line 2492 \| public class Collections {
2492		* @serial include
2493		*/
2494		static class CheckedList<E>
2495	<	extends CheckedCollection<E>
2496	<	implements List<E>
2495	>	extends CheckedCollection<E>
2496	>	implements List<E>
2497		{
2498		private static final long serialVersionUID = 65247728283967356L;
2499		final List<E> list;
#	Line 2486 \| Line 2526 \| public class Collections {
2526		public ListIterator<E> listIterator() { return listIterator(0); }
2527
2528		public ListIterator<E> listIterator(final int index) {
2529	<	final ListIterator<E> i = list.listIterator(index);
2529	>	final ListIterator<E> i = list.listIterator(index);
2530
2531	<	return new ListIterator<E>() {
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(); }
#	Line 2567 \| Line 2607 \| public class Collections {
2607		* @since 1.5
2608		*/
2609		public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
2610	<	Class<K> keyType,
2610	>	Class<K> keyType,
2611		Class<V> valueType) {
2612		return new CheckedMap<K,V>(m, keyType, valueType);
2613		}
#	Line 2577 \| Line 2617 \| public class Collections {
2617		* @serial include
2618		*/
2619		private static class CheckedMap<K,V>
2620	<	implements Map<K,V>, Serializable
2620	>	implements Map<K,V>, Serializable
2621		{
2622		private static final long serialVersionUID = 5742860141034234728L;
2623
#	Line 2593 \| Line 2633 \| public class Collections {
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	<	}
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) {
2647		if (m == null \|\| keyType == null \|\| valueType == null)
#	Line 2629 \| 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	<	// 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	<	for (Map.Entry<K,V> e : checked)
2691	<	m.put(e.getKey(), e.getValue());
2692	<	}
2672	>	@SuppressWarnings("unchecked")
2673	>	public void putAll(Map<? extends K, ? extends V> t) {
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	>	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;
2695
#	Line 2690 \| Line 2730 \| public class Collections {
2730		}
2731
2732		public Iterator<Map.Entry<K,V>> iterator() {
2733	<	final Iterator<Map.Entry<K, V>> i = s.iterator();
2734	<	final Class<V> valueType = this.valueType;
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>>() {
2736	>	return new Iterator<Map.Entry<K,V>>() {
2737		public boolean hasNext() { return i.hasNext(); }
2738		public void remove() { i.remove(); }
2739
#	Line 2703 \| Line 2743 \| public class Collections {
2743		};
2744		}
2745
2746	<	@SuppressWarnings("unchecked")
2746	>	@SuppressWarnings("unchecked")
2747		public Object[] toArray() {
2748		Object[] source = s.toArray();
2749
#	Line 2717 \| Line 2757 \| public class Collections {
2757
2758		for (int i = 0; i < source.length; i++)
2759		dest[i] = checkedEntry((Map.Entry<K,V>)source[i],
2760	<	valueType);
2760	>	valueType);
2761		return dest;
2762		}
2763
2764	<	@SuppressWarnings("unchecked")
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
#	Line 2730 \| Line 2770 \| public class Collections {
2770
2771		for (int i=0; i<arr.length; i++)
2772		arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i],
2773	<	valueType);
2773	>	valueType);
2774		if (arr.length > a.length)
2775		return arr;
2776
#	Line 2749 \| 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	<	(e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
2792	>	Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2793	>	return s.contains(
2794	>	(e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
2795		}
2796
2797		/**
#	Line 2760 \| Line 2800 \| public class Collections {
2800		* method senses when o is a Map.Entry, and calls o.setValue.
2801		*/
2802		public boolean containsAll(Collection<?> c) {
2803	<	for (Object o : 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) {
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	<	}
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)
#	Line 2798 \| Line 2838 \| public class Collections {
2838		return false;
2839		Set<?> that = (Set<?>) o;
2840		return that.size() == s.size()
2841	<	&& containsAll(that); // Invokes safe containsAll() above
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	<	}
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		/**
2850		* This "wrapper class" serves two purposes: it prevents
#	Line 2833 \| Line 2873 \| public class Collections {
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	<	}
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;
2882	>	if (o == this)
2883	>	return true;
2884		if (!(o instanceof Map.Entry))
2885		return false;
2886		return e.equals(new AbstractMap.SimpleImmutableEntry
2887	<	<Object, Object>((Map.Entry<?,?>)o));
2887	>	<Object, Object>((Map.Entry<?,?>)o));
2888		}
2889		}
2890		}
#	Line 2912 \| Line 2952 \| public class Collections {
2952
2953		public SortedMap<K,V> subMap(K fromKey, K toKey) {
2954		return checkedSortedMap(sm.subMap(fromKey, toKey),
2955	<	keyType, valueType);
2955	>	keyType, valueType);
2956		}
2957		public SortedMap<K,V> headMap(K toKey) {
2958		return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
#	Line 2948 \| Line 2988 \| public class Collections {
2988		*/
2989		@SuppressWarnings("unchecked")
2990		public static <T> Iterator<T> emptyIterator() {
2991	<	return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
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>();
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(); }
2998	>	public boolean hasNext() { return false; }
2999	>	public E next() { throw new NoSuchElementException(); }
3000	>	public void remove() { throw new IllegalStateException(); }
3001		}
3002
3003		/**
#	Line 2994 \| Line 3034 \| public class Collections {
3034		*/
3035		@SuppressWarnings("unchecked")
3036		public static <T> ListIterator<T> emptyListIterator() {
3037	<	return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
3037	>	return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
3038		}
3039
3040		private static class EmptyListIterator<E>
3041	<	extends EmptyIterator<E>
3042	<	implements ListIterator<E>
3041	>	extends EmptyIterator<E>
3042	>	implements ListIterator<E>
3043		{
3044	<	static final EmptyListIterator<Object> EMPTY_ITERATOR
3045	<	= new EmptyListIterator<Object>();
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(); }
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		/**
#	Line 3033 \| Line 3073 \| public class Collections {
3073		*/
3074		@SuppressWarnings("unchecked")
3075		public static <T> Enumeration<T> emptyEnumeration() {
3076	<	return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
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>();
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(); }
3083	>	public boolean hasMoreElements() { return false; }
3084	>	public E nextElement() { throw new NoSuchElementException(); }
3085		}
3086
3087		/**
#	Line 3070 \| Line 3110 \| public class Collections {
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<E>
3120	<	extends AbstractSet<E>
3121	<	implements Serializable
3120	>	extends AbstractSet<E>
3121	>	implements Serializable
3122		{
3123	<	private static final long serialVersionUID = 1582296315990362920L;
3123	>	private static final long serialVersionUID = 1582296315990362920L;
3124
3125	<	public Iterator<E> iterator() { return emptyIterator(); }
3125	>	public Iterator<E> iterator() { return emptyIterator(); }
3126
3127		public int size() {return 0;}
3128	<	public boolean isEmpty() {return true;}
3128	>	public boolean isEmpty() {return true;}
3129
3130		public boolean contains(Object obj) {return false;}
3131		public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
#	Line 3098 \| Line 3138 \| public class Collections {
3138		return a;
3139		}
3140
3141	<	// Preserves singleton property
3141	>	// Preserves singleton property
3142		private Object readResolve() {
3143		return EMPTY_SET;
3144		}
#	Line 3129 \| Line 3169 \| public class Collections {
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<E>
3179	<	extends AbstractList<E>
3180	<	implements RandomAccess, Serializable {
3181	<	private static final long serialVersionUID = 8842843931221139166L;
3142	<
3143	<	public Iterator<E> iterator() {
3144	<	return emptyIterator();
3145	<	}
3146	<	public ListIterator<E> listIterator() {
3147	<	return emptyListIterator();
3148	<	}
3179	>	extends AbstractList<E>
3180	>	implements RandomAccess, Serializable {
3181	>	private static final long serialVersionUID = 8842843931221139166L;
3182
3183	<	public int size() {return 0;}
3184	<	public boolean isEmpty() {return true;}
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(); }
#	Line 3203 \| Line 3243 \| public class Collections {
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		/**
3250		* @serial include
3251		*/
3252		private static class EmptyMap<K,V>
3253	<	extends AbstractMap<K,V>
3254	<	implements Serializable
3253	>	extends AbstractMap<K,V>
3254	>	implements Serializable
3255		{
3256		private static final long serialVersionUID = 6428348081105594320L;
3257
#	Line 3219 \| Line 3259 \| public class Collections {
3259		public boolean isEmpty() {return true;}
3260		public boolean containsKey(Object key) {return false;}
3261		public boolean containsValue(Object value) {return false;}
3262	<	public V get(Object key) {return null;}
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();}
#	Line 3246 \| 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	<	};
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	<	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 singletonIterator(element);
3325	>	return singletonIterator(element);
3326		}
3327
3328		public int size() {return 1;}
#	Line 3299 \| 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		private static final long serialVersionUID = 3093736618740652951L;
3353
#	Line 3316 \| Line 3356 \| public class Collections {
3356		SingletonList(E obj) {element = obj;}
3357
3358		public Iterator<E> iterator() {
3359	<	return singletonIterator(element);
3359	>	return singletonIterator(element);
3360		}
3361
3362		public int size() {return 1;}
#	Line 3341 \| 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 3374 \| 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
#	Line 3407 \| 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);
3456	>	if (n < 0)
3457	>	throw new IllegalArgumentException("List length = " + n);
3458		return new CopiesList<T>(n, o);
3459		}
3460
#	Line 3422 \| 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		private static final long serialVersionUID = 2739099268398711800L;
3469
#	Line 3431 \| Line 3471 \| public class Collections {
3471		final E element;
3472
3473		CopiesList(int n, E e) {
3474	<	assert n >= 0;
3474	>	assert n >= 0;
3475		this.n = n;
3476		element = e;
3477		}
#	Line 3444 \| 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	<	}
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)
#	Line 3459 \| Line 3499 \| public class Collections {
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	<	}
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 3502 \| 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() {
#	Line 3520 \| Line 3560 \| public class Collections {
3560		* @serial include
3561		*/
3562		private static class ReverseComparator
3563	<	implements Comparator<Comparable<Object>>, Serializable {
3563	>	implements Comparator<Comparable<Object>>, Serializable {
3564
3565	<	private static final long serialVersionUID = 7207038068494060240L;
3565	>	private static final long serialVersionUID = 7207038068494060240L;
3566
3567	<	static final ReverseComparator REVERSE_ORDER
3568	<	= new ReverseComparator();
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);
#	Line 3552 \| Line 3592 \| public class Collections {
3592		if (cmp == null)
3593		return reverseOrder();
3594
3595	<	if (cmp instanceof ReverseComparator2)
3596	<	return ((ReverseComparator2<T>)cmp).cmp;
3595	>	if (cmp instanceof ReverseComparator2)
3596	>	return ((ReverseComparator2<T>)cmp).cmp;
3597
3598		return new ReverseComparator2<T>(cmp);
3599		}
#	Line 3584 \| Line 3624 \| public class Collections {
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	<	}
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 3605 \| 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	<	private final 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 T nextElement() {
3656	<	return i.next();
3657	<	}
3651	>	public boolean hasMoreElements() {
3652	>	return i.hasNext();
3653	>	}
3654	>
3655	>	public T nextElement() {
3656	>	return i.next();
3657	>	}
3658		};
3659		}
3660
#	Line 3813 \| Line 3853 \| public class Collections {
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
3856	>	// addAll is the only inherited implementation
3857
3858		private static final long serialVersionUID = 2454657854757543876L;
3859
#	Line 3851 \| Line 3891 \| public class Collections {
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 add(E e) { q.addFirst(e); return true; }
#	Line 3869 \| Line 3909 \| public class Collections {
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
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.32 by jsr166, Tue Sep 11 15:18:34 2007 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.32 by jsr166, Tue Sep 11 15:18:34 2007 UTC vs.
Revision 1.43 by jsr166, Sat Oct 16 16:44:39 2010 UTC