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

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.17 by jsr166, Sat Sep 10 19:49:05 2005 UTC vs.
Revision 1.34 by jsr166, Sun May 18 23:59:57 2008 UTC

#	Line 1 \| Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation. Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
9	–	import java.util.*; // for javadoc (till 6280605 is fixed)
27		import java.io.Serializable;
28		import java.io.ObjectOutputStream;
29		import java.io.IOException;
#	Line 39 \| Line 56 \| import java.lang.reflect.Array;
56		* already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
57		*
58		* <p>This class is a member of the
59	<	* <a href="{@docRoot}/../guide/collections/index.html">
59	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
60		* Java Collections Framework</a>.
61		*
62		* @author Josh Bloch
63		* @author Neal Gafter
64	<	* @version %I%, %G%
65	<	* @see Collection
66	<	* @see Set
67	<	* @see List
51	<	* @see Map
64	>	* @see Collection
65	>	* @see Set
66	>	* @see List
67	>	* @see Map
68		* @since 1.2
69		*/
70
#	Line 108 \| Line 124 \| public class Collections {
124		*
125		* @param list the list to be sorted.
126		* @throws ClassCastException if the list contains elements that are not
127	<	* <i>mutually comparable</i> (for example, strings and integers).
127	>	* <i>mutually comparable</i> (for example, strings and integers).
128		* @throws UnsupportedOperationException if the specified list's
129	<	* list-iterator does not support the <tt>set</tt> operation.
129	>	* list-iterator does not support the <tt>set</tt> operation.
130		* @see Comparable
131		*/
132		public static <T extends Comparable<? super T>> void sort(List<T> list) {
133	<	Object[] a = list.toArray();
134	<	Arrays.sort(a);
135	<	ListIterator<T> i = list.listIterator();
136	<	for (int j=0; j<a.length; j++) {
137	<	i.next();
138	<	i.set((T)a[j]);
139	<	}
133	>	Object[] a = list.toArray();
134	>	Arrays.sort(a);
135	>	ListIterator<T> i = list.listIterator();
136	>	for (int j=0; j<a.length; j++) {
137	>	i.next();
138	>	i.set((T)a[j]);
139	>	}
140		}
141
142		/**
#	Line 150 \| Line 166 \| public class Collections {
166		* <tt>null</tt> value indicates that the elements' <i>natural
167		* ordering</i> should be used.
168		* @throws ClassCastException if the list contains elements that are not
169	<	* <i>mutually comparable</i> using the specified comparator.
169	>	* <i>mutually comparable</i> using the specified comparator.
170		* @throws UnsupportedOperationException if the specified list's
171	<	* list-iterator does not support the <tt>set</tt> operation.
171	>	* list-iterator does not support the <tt>set</tt> operation.
172		* @see Comparator
173		*/
174		public static <T> void sort(List<T> list, Comparator<? super T> c) {
175	<	Object[] a = list.toArray();
176	<	Arrays.sort(a, (Comparator)c);
177	<	ListIterator i = list.listIterator();
178	<	for (int j=0; j<a.length; j++) {
179	<	i.next();
180	<	i.set(a[j]);
181	<	}
175	>	Object[] a = list.toArray();
176	>	Arrays.sort(a, (Comparator)c);
177	>	ListIterator i = list.listIterator();
178	>	for (int j=0; j<a.length; j++) {
179	>	i.next();
180	>	i.set(a[j]);
181	>	}
182		}
183
184
185		/**
186		* Searches the specified list for the specified object using the binary
187		* search algorithm. The list must be sorted into ascending order
188	<	* according to the <i>natural ordering</i> of its elements (as by the
189	<	* <tt>sort(List)</tt> method, above) prior to making this call. If it is
190	<	* not sorted, the results are undefined. If the list contains multiple
191	<	* elements equal to the specified object, there is no guarantee which one
192	<	* will be found.<p>
188	>	* according to the {@linkplain Comparable natural ordering} of its
189	>	* elements (as by the {@link #sort(List)} method) prior to making this
190	>	* call. If it is not sorted, the results are undefined. If the list
191	>	* contains multiple elements equal to the specified object, there is no
192	>	* guarantee which one will be found.
193		*
194	<	* This method runs in log(n) time for a "random access" list (which
194	>	* <p>This method runs in log(n) time for a "random access" list (which
195		* provides near-constant-time positional access). If the specified list
196		* does not implement the {@link RandomAccess} interface and is large,
197		* this method will do an iterator-based binary search that performs
#	Line 184 \| Line 200 \| public class Collections {
200		* @param list the list to be searched.
201		* @param key the key to be searched for.
202		* @return the index of the search key, if it is contained in the list;
203	<	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
204	<	* <i>insertion point</i> is defined as the point at which the
205	<	* key would be inserted into the list: the index of the first
206	<	* element greater than the key, or <tt>list.size()</tt>, if all
207	<	* elements in the list are less than the specified key. Note
208	<	* that this guarantees that the return value will be >= 0 if
209	<	* and only if the key is found.
203	>	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
204	>	* <i>insertion point</i> is defined as the point at which the
205	>	* key would be inserted into the list: the index of the first
206	>	* element greater than the key, or <tt>list.size()</tt> if all
207	>	* elements in the list are less than the specified key. Note
208	>	* that this guarantees that the return value will be >= 0 if
209	>	* and only if the key is found.
210		* @throws ClassCastException if the list contains elements that are not
211	<	* <i>mutually comparable</i> (for example, strings and
212	<	* integers), or the search key in not mutually comparable
213	<	* with the elements of the list.
198	<	* @see Comparable
199	<	* @see #sort(List)
211	>	* <i>mutually comparable</i> (for example, strings and
212	>	* integers), or the search key is not mutually comparable
213	>	* with the elements of the list.
214		*/
215		public static <T>
216		int binarySearch(List<? extends Comparable<? super T>> list, T key) {
#	Line 209 \| Line 223 \| public class Collections {
223		private static <T>
224		int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
225		{
226	<	int low = 0;
227	<	int high = list.size()-1;
226	>	int low = 0;
227	>	int high = list.size()-1;
228	>
229	>	while (low <= high) {
230	>	int mid = (low + high) >>> 1;
231	>	Comparable<? super T> midVal = list.get(mid);
232	>	int cmp = midVal.compareTo(key);
233
234	<	while (low <= high) {
235	<	int mid = (low + high) >> 1;
236	<	Comparable<? super T> midVal = list.get(mid);
237	<	int cmp = midVal.compareTo(key);
238	<
239	<	if (cmp < 0)
240	<	low = mid + 1;
241	<	else if (cmp > 0)
223	<	high = mid - 1;
224	<	else
225	<	return mid; // key found
226	<	}
227	<	return -(low + 1); // key not found
234	>	if (cmp < 0)
235	>	low = mid + 1;
236	>	else if (cmp > 0)
237	>	high = mid - 1;
238	>	else
239	>	return mid; // key found
240	>	}
241	>	return -(low + 1); // key not found
242		}
243
244		private static <T>
245		int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
246		{
247	<	int low = 0;
248	<	int high = list.size()-1;
247	>	int low = 0;
248	>	int high = list.size()-1;
249		ListIterator<? extends Comparable<? super T>> i = list.listIterator();
250
251		while (low <= high) {
252	<	int mid = (low + high) >> 1;
252	>	int mid = (low + high) >>> 1;
253		Comparable<? super T> midVal = get(i, mid);
254		int cmp = midVal.compareTo(key);
255
#	Line 254 \| Line 268 \| public class Collections {
268		* list listIterator.
269		*/
270		private static <T> T get(ListIterator<? extends T> i, int index) {
271	<	T obj = null;
271	>	T obj = null;
272		int pos = i.nextIndex();
273		if (pos <= index) {
274		do {
#	Line 271 \| Line 285 \| public class Collections {
285		/**
286		* Searches the specified list for the specified object using the binary
287		* search algorithm. The list must be sorted into ascending order
288	<	* according to the specified comparator (as by the <tt>Sort(List,
289	<	* Comparator)</tt> method, above), prior to making this call. If it is
288	>	* according to the specified comparator (as by the
289	>	* {@link #sort(List, Comparator) sort(List, Comparator)}
290	>	* method), prior to making this call. If it is
291		* not sorted, the results are undefined. If the list contains multiple
292		* elements equal to the specified object, there is no guarantee which one
293	<	* will be found.<p>
293	>	* will be found.
294		*
295	<	* This method runs in log(n) time for a "random access" list (which
295	>	* <p>This method runs in log(n) time for a "random access" list (which
296		* provides near-constant-time positional access). If the specified list
297		* does not implement the {@link RandomAccess} interface and is large,
298		* this method will do an iterator-based binary search that performs
#	Line 285 \| Line 300 \| public class Collections {
300		*
301		* @param list the list to be searched.
302		* @param key the key to be searched for.
303	<	* @param c the comparator by which the list is ordered. A
304	<	* <tt>null</tt> value indicates that the elements' <i>natural
305	<	* ordering</i> should be used.
303	>	* @param c the comparator by which the list is ordered.
304	>	* A <tt>null</tt> value indicates that the elements'
305	>	* {@linkplain Comparable natural ordering} should be used.
306		* @return the index of the search key, if it is contained in the list;
307	<	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
308	<	* <i>insertion point</i> is defined as the point at which the
309	<	* key would be inserted into the list: the index of the first
310	<	* element greater than the key, or <tt>list.size()</tt>, if all
311	<	* elements in the list are less than the specified key. Note
312	<	* that this guarantees that the return value will be >= 0 if
313	<	* and only if the key is found.
307	>	* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
308	>	* <i>insertion point</i> is defined as the point at which the
309	>	* key would be inserted into the list: the index of the first
310	>	* element greater than the key, or <tt>list.size()</tt> if all
311	>	* elements in the list are less than the specified key. Note
312	>	* that this guarantees that the return value will be >= 0 if
313	>	* and only if the key is found.
314		* @throws ClassCastException if the list contains elements that are not
315	<	* <i>mutually comparable</i> using the specified comparator,
316	<	* or the search key in not mutually comparable with the
317	<	* elements of the list using this comparator.
303	<	* @see Comparable
304	<	* @see #sort(List, Comparator)
315	>	* <i>mutually comparable</i> using the specified comparator,
316	>	* or the search key is not mutually comparable with the
317	>	* elements of the list using this comparator.
318		*/
319		public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
320		if (c==null)
#	Line 314 \| Line 327 \| public class Collections {
327		}
328
329		private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
330	<	int low = 0;
331	<	int high = l.size()-1;
330	>	int low = 0;
331	>	int high = l.size()-1;
332	>
333	>	while (low <= high) {
334	>	int mid = (low + high) >>> 1;
335	>	T midVal = l.get(mid);
336	>	int cmp = c.compare(midVal, key);
337
338	<	while (low <= high) {
339	<	int mid = (low + high) >> 1;
340	<	T midVal = l.get(mid);
341	<	int cmp = c.compare(midVal, key);
342	<
343	<	if (cmp < 0)
344	<	low = mid + 1;
345	<	else if (cmp > 0)
328	<	high = mid - 1;
329	<	else
330	<	return mid; // key found
331	<	}
332	<	return -(low + 1); // key not found
338	>	if (cmp < 0)
339	>	low = mid + 1;
340	>	else if (cmp > 0)
341	>	high = mid - 1;
342	>	else
343	>	return mid; // key found
344	>	}
345	>	return -(low + 1); // key not found
346		}
347
348		private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
349	<	int low = 0;
350	<	int high = l.size()-1;
349	>	int low = 0;
350	>	int high = l.size()-1;
351		ListIterator<? extends T> i = l.listIterator();
352
353		while (low <= high) {
354	<	int mid = (low + high) >> 1;
354	>	int mid = (low + high) >>> 1;
355		T midVal = get(i, mid);
356		int cmp = c.compare(midVal, key);
357
#	Line 373 \| Line 386 \| public class Collections {
386		ListIterator fwd = list.listIterator();
387		ListIterator rev = list.listIterator(size);
388		for (int i=0, mid=list.size()>>1; i<mid; i++) {
389	<	Object tmp = fwd.next();
389	>	Object tmp = fwd.next();
390		fwd.set(rev.previous());
391		rev.set(tmp);
392		}
#	Line 474 \| Line 487 \| public class Collections {
487		* @since 1.4
488		*/
489		public static void swap(List<?> list, int i, int j) {
490	<	final List l = list;
491	<	l.set(i, l.set(j, l.get(i)));
490	>	final List l = list;
491	>	l.set(i, l.set(j, l.get(i)));
492		}
493
494		/**
#	Line 496 \| Line 509 \| public class Collections {
509		* @param list the list to be filled with the specified element.
510		* @param obj The element with which to fill the specified list.
511		* @throws UnsupportedOperationException if the specified list or its
512	<	* list-iterator does not support the <tt>set</tt> operation.
512	>	* list-iterator does not support the <tt>set</tt> operation.
513		*/
514		public static <T> void fill(List<? super T> list, T obj) {
515		int size = list.size();
#	Line 540 \| Line 553 \| public class Collections {
553		dest.set(i, src.get(i));
554		} else {
555		ListIterator<? super T> di=dest.listIterator();
556	<	ListIterator<? extends T> si=src.listIterator();
556	>	ListIterator<? extends T> si=src.listIterator();
557		for (int i=0; i<srcSize; i++) {
558		di.next();
559		di.set(si.next());
#	Line 564 \| Line 577 \| public class Collections {
577		* @return the minimum element of the given collection, according
578		* to the <i>natural ordering</i> of its elements.
579		* @throws ClassCastException if the collection contains elements that are
580	<	* not <i>mutually comparable</i> (for example, strings and
581	<	* integers).
580	>	* not <i>mutually comparable</i> (for example, strings and
581	>	* integers).
582		* @throws NoSuchElementException if the collection is empty.
583		* @see Comparable
584		*/
585		public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
586	<	Iterator<? extends T> i = coll.iterator();
587	<	T candidate = i.next();
586	>	Iterator<? extends T> i = coll.iterator();
587	>	T candidate = i.next();
588
589		while (i.hasNext()) {
590	<	T next = i.next();
591	<	if (next.compareTo(candidate) < 0)
592	<	candidate = next;
593	<	}
594	<	return candidate;
590	>	T next = i.next();
591	>	if (next.compareTo(candidate) < 0)
592	>	candidate = next;
593	>	}
594	>	return candidate;
595		}
596
597		/**
#	Line 599 \| Line 612 \| public class Collections {
612		* @return the minimum element of the given collection, according
613		* to the specified comparator.
614		* @throws ClassCastException if the collection contains elements that are
615	<	* not <i>mutually comparable</i> using the specified comparator.
615	>	* not <i>mutually comparable</i> using the specified comparator.
616		* @throws NoSuchElementException if the collection is empty.
617		* @see Comparable
618		*/
#	Line 607 \| Line 620 \| public class Collections {
620		if (comp==null)
621		return (T)min((Collection<SelfComparable>) (Collection) coll);
622
623	<	Iterator<? extends T> i = coll.iterator();
624	<	T candidate = i.next();
623	>	Iterator<? extends T> i = coll.iterator();
624	>	T candidate = i.next();
625
626		while (i.hasNext()) {
627	<	T next = i.next();
628	<	if (comp.compare(next, candidate) < 0)
629	<	candidate = next;
630	<	}
631	<	return candidate;
627	>	T next = i.next();
628	>	if (comp.compare(next, candidate) < 0)
629	>	candidate = next;
630	>	}
631	>	return candidate;
632		}
633
634		/**
#	Line 634 \| Line 647 \| public class Collections {
647		* @return the maximum element of the given collection, according
648		* to the <i>natural ordering</i> of its elements.
649		* @throws ClassCastException if the collection contains elements that are
650	<	* not <i>mutually comparable</i> (for example, strings and
650	>	* not <i>mutually comparable</i> (for example, strings and
651		* integers).
652		* @throws NoSuchElementException if the collection is empty.
653		* @see Comparable
654		*/
655		public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
656	<	Iterator<? extends T> i = coll.iterator();
657	<	T candidate = i.next();
656	>	Iterator<? extends T> i = coll.iterator();
657	>	T candidate = i.next();
658
659		while (i.hasNext()) {
660	<	T next = i.next();
661	<	if (next.compareTo(candidate) > 0)
662	<	candidate = next;
663	<	}
664	<	return candidate;
660	>	T next = i.next();
661	>	if (next.compareTo(candidate) > 0)
662	>	candidate = next;
663	>	}
664	>	return candidate;
665		}
666
667		/**
#	Line 669 \| Line 682 \| public class Collections {
682		* @return the maximum element of the given collection, according
683		* to the specified comparator.
684		* @throws ClassCastException if the collection contains elements that are
685	<	* not <i>mutually comparable</i> using the specified comparator.
685	>	* not <i>mutually comparable</i> using the specified comparator.
686		* @throws NoSuchElementException if the collection is empty.
687		* @see Comparable
688		*/
#	Line 677 \| Line 690 \| public class Collections {
690		if (comp==null)
691		return (T)max((Collection<SelfComparable>) (Collection) coll);
692
693	<	Iterator<? extends T> i = coll.iterator();
694	<	T candidate = i.next();
693	>	Iterator<? extends T> i = coll.iterator();
694	>	T candidate = i.next();
695
696		while (i.hasNext()) {
697	<	T next = i.next();
698	<	if (comp.compare(next, candidate) > 0)
699	<	candidate = next;
700	<	}
701	<	return candidate;
697	>	T next = i.next();
698	>	if (comp.compare(next, candidate) > 0)
699	>	candidate = next;
700	>	}
701	>	return candidate;
702		}
703
704		/**
#	Line 745 \| Line 758 \| public class Collections {
758		*/
759		public static void rotate(List<?> list, int distance) {
760		if (list instanceof RandomAccess \|\| list.size() < ROTATE_THRESHOLD)
761	<	rotate1((List)list, distance);
761	>	rotate1(list, distance);
762		else
763	<	rotate2((List)list, distance);
763	>	rotate2(list, distance);
764		}
765
766		private static <T> void rotate1(List<T> list, int distance) {
#	Line 977 \| Line 990 \| public class Collections {
990		* is serializable.
991		*
992		* @param c the collection for which an unmodifiable view is to be
993	<	* returned.
993	>	* returned.
994		* @return an unmodifiable view of the specified collection.
995		*/
996		public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
997	<	return new UnmodifiableCollection<T>(c);
997	>	return new UnmodifiableCollection<T>(c);
998		}
999
1000		/**
1001		* @serial include
1002		*/
1003		static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
1004	<	// use serialVersionUID from JDK 1.2.2 for interoperability
992	<	private static final long serialVersionUID = 1820017752578914078L;
1004	>	private static final long serialVersionUID = 1820017752578914078L;
1005
1006	<	final Collection<? extends E> c;
1006	>	final Collection<? extends E> c;
1007
1008	<	UnmodifiableCollection(Collection<? extends E> c) {
1008	>	UnmodifiableCollection(Collection<? extends E> c) {
1009		if (c==null)
1010		throw new NullPointerException();
1011		this.c = c;
1012		}
1013
1014	<	public int size() {return c.size();}
1015	<	public boolean isEmpty() {return c.isEmpty();}
1016	<	public boolean contains(Object o) {return c.contains(o);}
1017	<	public Object[] toArray() {return c.toArray();}
1018	<	public <T> T[] toArray(T[] a) {return c.toArray(a);}
1014	>	public int size() {return c.size();}
1015	>	public boolean isEmpty() {return c.isEmpty();}
1016	>	public boolean contains(Object o) {return c.contains(o);}
1017	>	public Object[] toArray() {return c.toArray();}
1018	>	public <T> T[] toArray(T[] a) {return c.toArray(a);}
1019		public String toString() {return c.toString();}
1020
1021	<	public Iterator<E> iterator() {
1022	<	return new Iterator<E>() {
1023	<	Iterator<? extends E> i = c.iterator();
1024	<
1025	<	public boolean hasNext() {return i.hasNext();}
1026	<	public E next() {return i.next();}
1027	<	public void remove() {
1028	<	throw new UnsupportedOperationException();
1021	>	public Iterator<E> iterator() {
1022	>	return new Iterator<E>() {
1023	>	private final Iterator<? extends E> i = c.iterator();
1024	>
1025	>	public boolean hasNext() {return i.hasNext();}
1026	>	public E next() {return i.next();}
1027	>	public void remove() {
1028	>	throw new UnsupportedOperationException();
1029		}
1030	<	};
1030	>	};
1031		}
1032
1033	<	public boolean add(E e){
1034	<	throw new UnsupportedOperationException();
1033	>	public boolean add(E e) {
1034	>	throw new UnsupportedOperationException();
1035		}
1036	<	public boolean remove(Object o) {
1037	<	throw new UnsupportedOperationException();
1036	>	public boolean remove(Object o) {
1037	>	throw new UnsupportedOperationException();
1038		}
1039
1040	<	public boolean containsAll(Collection<?> coll) {
1041	<	return c.containsAll(coll);
1040	>	public boolean containsAll(Collection<?> coll) {
1041	>	return c.containsAll(coll);
1042		}
1043	<	public boolean addAll(Collection<? extends E> coll) {
1044	<	throw new UnsupportedOperationException();
1043	>	public boolean addAll(Collection<? extends E> coll) {
1044	>	throw new UnsupportedOperationException();
1045		}
1046	<	public boolean removeAll(Collection<?> coll) {
1047	<	throw new UnsupportedOperationException();
1046	>	public boolean removeAll(Collection<?> coll) {
1047	>	throw new UnsupportedOperationException();
1048		}
1049	<	public boolean retainAll(Collection<?> coll) {
1050	<	throw new UnsupportedOperationException();
1049	>	public boolean retainAll(Collection<?> coll) {
1050	>	throw new UnsupportedOperationException();
1051		}
1052	<	public void clear() {
1053	<	throw new UnsupportedOperationException();
1052	>	public void clear() {
1053	>	throw new UnsupportedOperationException();
1054		}
1055		}
1056
#	Line 1056 \| Line 1068 \| public class Collections {
1068		* @return an unmodifiable view of the specified set.
1069		*/
1070		public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1071	<	return new UnmodifiableSet<T>(s);
1071	>	return new UnmodifiableSet<T>(s);
1072		}
1073
1074		/**
1075		* @serial include
1076		*/
1077		static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
1078	<	implements Set<E>, Serializable {
1079	<	private static final long serialVersionUID = -9215047833775013803L;
1078	>	implements Set<E>, Serializable {
1079	>	private static final long serialVersionUID = -9215047833775013803L;
1080
1081	<	UnmodifiableSet(Set<? extends E> s) {super(s);}
1082	<	public boolean equals(Object o) {return c.equals(o);}
1083	<	public int hashCode() {return c.hashCode();}
1081	>	UnmodifiableSet(Set<? extends E> s) {super(s);}
1082	>	public boolean equals(Object o) {return o == this \|\| c.equals(o);}
1083	>	public int hashCode() {return c.hashCode();}
1084		}
1085
1086		/**
#	Line 1088 \| Line 1100 \| public class Collections {
1100		* @return an unmodifiable view of the specified sorted set.
1101		*/
1102		public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
1103	<	return new UnmodifiableSortedSet<T>(s);
1103	>	return new UnmodifiableSortedSet<T>(s);
1104		}
1105
1106		/**
1107		* @serial include
1108		*/
1109		static class UnmodifiableSortedSet<E>
1110	<	extends UnmodifiableSet<E>
1111	<	implements SortedSet<E>, Serializable {
1112	<	private static final long serialVersionUID = -4929149591599911165L;
1110	>	extends UnmodifiableSet<E>
1111	>	implements SortedSet<E>, Serializable {
1112	>	private static final long serialVersionUID = -4929149591599911165L;
1113		private final SortedSet<E> ss;
1114
1115	<	UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1115	>	UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1116
1117		public Comparator<? super E> comparator() {return ss.comparator();}
1118
#	Line 1114 \| Line 1126 \| public class Collections {
1126		return new UnmodifiableSortedSet<E>(ss.tailSet(fromElement));
1127		}
1128
1129	<	public E first() {return ss.first();}
1130	<	public E last() {return ss.last();}
1129	>	public E first() {return ss.first();}
1130	>	public E last() {return ss.last();}
1131		}
1132
1133		/**
#	Line 1134 \| Line 1146 \| public class Collections {
1146		* @return an unmodifiable view of the specified list.
1147		*/
1148		public static <T> List<T> unmodifiableList(List<? extends T> list) {
1149	<	return (list instanceof RandomAccess ?
1149	>	return (list instanceof RandomAccess ?
1150		new UnmodifiableRandomAccessList<T>(list) :
1151		new UnmodifiableList<T>(list));
1152		}
#	Line 1143 \| Line 1155 \| public class Collections {
1155		* @serial include
1156		*/
1157		static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1158	<	implements List<E> {
1159	<	static final long serialVersionUID = -283967356065247728L;
1160	<	final List<? extends E> list;
1161	<
1162	<	UnmodifiableList(List<? extends E> list) {
1163	<	super(list);
1164	<	this.list = list;
1165	<	}
1154	<
1155	<	public boolean equals(Object o) {return list.equals(o);}
1156	<	public int hashCode() {return list.hashCode();}
1157	<
1158	<	public E get(int index) {return list.get(index);}
1159	<	public E set(int index, E element) {
1160	<	throw new UnsupportedOperationException();
1161	<	}
1162	<	public void add(int index, E element) {
1163	<	throw new UnsupportedOperationException();
1164	<	}
1165	<	public E remove(int index) {
1166	<	throw new UnsupportedOperationException();
1167	<	}
1168	<	public int indexOf(Object o) {return list.indexOf(o);}
1169	<	public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1170	<	public boolean addAll(int index, Collection<? extends E> c) {
1171	<	throw new UnsupportedOperationException();
1172	<	}
1173	<	public ListIterator<E> listIterator() {return listIterator(0);}
1174	<
1175	<	public ListIterator<E> listIterator(final int index) {
1176	<	return new ListIterator<E>() {
1177	<	ListIterator<? extends E> i = list.listIterator(index);
1178	<
1179	<	public boolean hasNext() {return i.hasNext();}
1180	<	public E next() {return i.next();}
1181	<	public boolean hasPrevious() {return i.hasPrevious();}
1182	<	public E previous() {return i.previous();}
1183	<	public int nextIndex() {return i.nextIndex();}
1184	<	public int previousIndex() {return i.previousIndex();}
1158	>	implements List<E> {
1159	>	private static final long serialVersionUID = -283967356065247728L;
1160	>	final List<? extends E> list;
1161	>
1162	>	UnmodifiableList(List<? extends E> list) {
1163	>	super(list);
1164	>	this.list = list;
1165	>	}
1166
1167	<	public void remove() {
1168	<	throw new UnsupportedOperationException();
1167	>	public boolean equals(Object o) {return o == this \|\| list.equals(o);}
1168	>	public int hashCode() {return list.hashCode();}
1169	>
1170	>	public E get(int index) {return list.get(index);}
1171	>	public E set(int index, E element) {
1172	>	throw new UnsupportedOperationException();
1173	>	}
1174	>	public void add(int index, E element) {
1175	>	throw new UnsupportedOperationException();
1176	>	}
1177	>	public E remove(int index) {
1178	>	throw new UnsupportedOperationException();
1179	>	}
1180	>	public int indexOf(Object o) {return list.indexOf(o);}
1181	>	public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1182	>	public boolean addAll(int index, Collection<? extends E> c) {
1183	>	throw new UnsupportedOperationException();
1184	>	}
1185	>	public ListIterator<E> listIterator() {return listIterator(0);}
1186	>
1187	>	public ListIterator<E> listIterator(final int index) {
1188	>	return new ListIterator<E>() {
1189	>	private final ListIterator<? extends E> i
1190	>	= list.listIterator(index);
1191	>
1192	>	public boolean hasNext() {return i.hasNext();}
1193	>	public E next() {return i.next();}
1194	>	public boolean hasPrevious() {return i.hasPrevious();}
1195	>	public E previous() {return i.previous();}
1196	>	public int nextIndex() {return i.nextIndex();}
1197	>	public int previousIndex() {return i.previousIndex();}
1198	>
1199	>	public void remove() {
1200	>	throw new UnsupportedOperationException();
1201		}
1202	<	public void set(E e) {
1203	<	throw new UnsupportedOperationException();
1202	>	public void set(E e) {
1203	>	throw new UnsupportedOperationException();
1204		}
1205	<	public void add(E e) {
1206	<	throw new UnsupportedOperationException();
1205	>	public void add(E e) {
1206	>	throw new UnsupportedOperationException();
1207		}
1208	<	};
1209	<	}
1208	>	};
1209	>	}
1210
1211	<	public List<E> subList(int fromIndex, int toIndex) {
1211	>	public List<E> subList(int fromIndex, int toIndex) {
1212		return new UnmodifiableList<E>(list.subList(fromIndex, toIndex));
1213		}
1214
#	Line 1213 \| Line 1226 \| public class Collections {
1226		*/
1227		private Object readResolve() {
1228		return (list instanceof RandomAccess
1229	<	? new UnmodifiableRandomAccessList<E>(list)
1230	<	: this);
1229	>	? new UnmodifiableRandomAccessList<E>(list)
1230	>	: this);
1231		}
1232		}
1233
#	Line 1228 \| Line 1241 \| public class Collections {
1241		super(list);
1242		}
1243
1244	<	public List<E> subList(int fromIndex, int toIndex) {
1244	>	public List<E> subList(int fromIndex, int toIndex) {
1245		return new UnmodifiableRandomAccessList<E>(
1246		list.subList(fromIndex, toIndex));
1247		}
#	Line 1261 \| Line 1274 \| public class Collections {
1274		* @return an unmodifiable view of the specified map.
1275		*/
1276		public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
1277	<	return new UnmodifiableMap<K,V>(m);
1277	>	return new UnmodifiableMap<K,V>(m);
1278		}
1279
1280		/**
1281		* @serial include
1282		*/
1283		private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
1284	<	// use serialVersionUID from JDK 1.2.2 for interoperability
1272	<	private static final long serialVersionUID = -1034234728574286014L;
1284	>	private static final long serialVersionUID = -1034234728574286014L;
1285
1286	<	private final Map<? extends K, ? extends V> m;
1286	>	private final Map<? extends K, ? extends V> m;
1287
1288	<	UnmodifiableMap(Map<? extends K, ? extends V> m) {
1288	>	UnmodifiableMap(Map<? extends K, ? extends V> m) {
1289		if (m==null)
1290		throw new NullPointerException();
1291		this.m = m;
1292		}
1293
1294	<	public int size() {return m.size();}
1295	<	public boolean isEmpty() {return m.isEmpty();}
1296	<	public boolean containsKey(Object key) {return m.containsKey(key);}
1297	<	public boolean containsValue(Object val) {return m.containsValue(val);}
1298	<	public V get(Object key) {return m.get(key);}
1299	<
1300	<	public V put(K key, V value) {
1301	<	throw new UnsupportedOperationException();
1302	<	}
1303	<	public V remove(Object key) {
1304	<	throw new UnsupportedOperationException();
1305	<	}
1306	<	public void putAll(Map<? extends K, ? extends V> m) {
1307	<	throw new UnsupportedOperationException();
1308	<	}
1309	<	public void clear() {
1310	<	throw new UnsupportedOperationException();
1311	<	}
1312	<
1313	<	private transient Set<K> keySet = null;
1314	<	private transient Set<Map.Entry<K,V>> entrySet = null;
1315	<	private transient Collection<V> values = null;
1316	<
1317	<	public Set<K> keySet() {
1318	<	if (keySet==null)
1319	<	keySet = unmodifiableSet(m.keySet());
1320	<	return keySet;
1321	<	}
1322	<
1323	<	public Set<Map.Entry<K,V>> entrySet() {
1324	<	if (entrySet==null)
1325	<	entrySet = new UnmodifiableEntrySet<K,V>(m.entrySet());
1326	<	return entrySet;
1327	<	}
1328	<
1329	<	public Collection<V> values() {
1330	<	if (values==null)
1331	<	values = unmodifiableCollection(m.values());
1332	<	return values;
1333	<	}
1294	>	public int size() {return m.size();}
1295	>	public boolean isEmpty() {return m.isEmpty();}
1296	>	public boolean containsKey(Object key) {return m.containsKey(key);}
1297	>	public boolean containsValue(Object val) {return m.containsValue(val);}
1298	>	public V get(Object key) {return m.get(key);}
1299	>
1300	>	public V put(K key, V value) {
1301	>	throw new UnsupportedOperationException();
1302	>	}
1303	>	public V remove(Object key) {
1304	>	throw new UnsupportedOperationException();
1305	>	}
1306	>	public void putAll(Map<? extends K, ? extends V> m) {
1307	>	throw new UnsupportedOperationException();
1308	>	}
1309	>	public void clear() {
1310	>	throw new UnsupportedOperationException();
1311	>	}
1312	>
1313	>	private transient Set<K> keySet = null;
1314	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1315	>	private transient Collection<V> values = null;
1316	>
1317	>	public Set<K> keySet() {
1318	>	if (keySet==null)
1319	>	keySet = unmodifiableSet(m.keySet());
1320	>	return keySet;
1321	>	}
1322	>
1323	>	public Set<Map.Entry<K,V>> entrySet() {
1324	>	if (entrySet==null)
1325	>	entrySet = new UnmodifiableEntrySet<K,V>(m.entrySet());
1326	>	return entrySet;
1327	>	}
1328	>
1329	>	public Collection<V> values() {
1330	>	if (values==null)
1331	>	values = unmodifiableCollection(m.values());
1332	>	return values;
1333	>	}
1334
1335	<	public boolean equals(Object o) {return m.equals(o);}
1336	<	public int hashCode() {return m.hashCode();}
1335	>	public boolean equals(Object o) {return o == this \|\| m.equals(o);}
1336	>	public int hashCode() {return m.hashCode();}
1337		public String toString() {return m.toString();}
1338
1339		/**
#	Line 1333 \| Line 1345 \| public class Collections {
1345		* @serial include
1346		*/
1347		static class UnmodifiableEntrySet<K,V>
1348	<	extends UnmodifiableSet<Map.Entry<K,V>> {
1349	<	private static final long serialVersionUID = 7854390611657943733L;
1348	>	extends UnmodifiableSet<Map.Entry<K,V>> {
1349	>	private static final long serialVersionUID = 7854390611657943733L;
1350
1351		UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1352		super((Set)s);
1353		}
1354		public Iterator<Map.Entry<K,V>> iterator() {
1355		return new Iterator<Map.Entry<K,V>>() {
1356	<	Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1356	>	private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1357
1358		public boolean hasNext() {
1359		return i.hasNext();
1360		}
1361	<	public Map.Entry<K,V> next() {
1362	<	return new UnmodifiableEntry<K,V>(i.next());
1361	>	public Map.Entry<K,V> next() {
1362	>	return new UnmodifiableEntry<K,V>(i.next());
1363		}
1364		public void remove() {
1365		throw new UnsupportedOperationException();
#	Line 1366 \| Line 1378 \| public class Collections {
1378		// We don't pass a to c.toArray, to avoid window of
1379		// vulnerability wherein an unscrupulous multithreaded client
1380		// could get his hands on raw (unwrapped) Entries from c.
1381	<	Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1381	>	Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1382
1383		for (int i=0; i<arr.length; i++)
1384		arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]);
#	Line 1389 \| Line 1401 \| public class Collections {
1401		public boolean contains(Object o) {
1402		if (!(o instanceof Map.Entry))
1403		return false;
1404	<	return c.contains(new UnmodifiableEntry<K,V>((Map.Entry<K,V>) o));
1404	>	return c.contains(
1405	>	new UnmodifiableEntry<Object,Object>((Map.Entry<?,?>) o));
1406		}
1407
1408		/**
#	Line 1428 \| Line 1441 \| public class Collections {
1441
1442		UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1443
1444	<	public K getKey() {return e.getKey();}
1444	>	public K getKey() {return e.getKey();}
1445		public V getValue() {return e.getValue();}
1446		public V setValue(V value) {
1447		throw new UnsupportedOperationException();
1448		}
1449	<	public int hashCode() {return e.hashCode();}
1449	>	public int hashCode() {return e.hashCode();}
1450		public boolean equals(Object o) {
1451		if (!(o instanceof Map.Entry))
1452		return false;
#	Line 1463 \| Line 1476 \| public class Collections {
1476		* @return an unmodifiable view of the specified sorted map.
1477		*/
1478		public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1479	<	return new UnmodifiableSortedMap<K,V>(m);
1479	>	return new UnmodifiableSortedMap<K,V>(m);
1480		}
1481
1482		/**
1483		* @serial include
1484		*/
1485		static class UnmodifiableSortedMap<K,V>
1486	<	extends UnmodifiableMap<K,V>
1487	<	implements SortedMap<K,V>, Serializable {
1488	<	private static final long serialVersionUID = -8806743815996713206L;
1486	>	extends UnmodifiableMap<K,V>
1487	>	implements SortedMap<K,V>, Serializable {
1488	>	private static final long serialVersionUID = -8806743815996713206L;
1489
1490		private final SortedMap<K, ? extends V> sm;
1491
1492	<	UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1492	>	UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1493
1494		public Comparator<? super K> comparator() {return sm.comparator();}
1495
#	Line 1529 \| Line 1542 \| public class Collections {
1542		* @return a synchronized view of the specified collection.
1543		*/
1544		public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1545	<	return new SynchronizedCollection<T>(c);
1545	>	return new SynchronizedCollection<T>(c);
1546		}
1547
1548		static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1549	<	return new SynchronizedCollection<T>(c, mutex);
1549	>	return new SynchronizedCollection<T>(c, mutex);
1550		}
1551
1552		/**
1553		* @serial include
1554		*/
1555		static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1556	<	// use serialVersionUID from JDK 1.2.2 for interoperability
1544	<	private static final long serialVersionUID = 3053995032091335093L;
1556	>	private static final long serialVersionUID = 3053995032091335093L;
1557
1558	<	final Collection<E> c; // Backing Collection
1559	<	final Object mutex; // Object on which to synchronize
1558	>	final Collection<E> c; // Backing Collection
1559	>	final Object mutex; // Object on which to synchronize
1560
1561	<	SynchronizedCollection(Collection<E> c) {
1561	>	SynchronizedCollection(Collection<E> c) {
1562		if (c==null)
1563		throw new NullPointerException();
1564	<	this.c = c;
1564	>	this.c = c;
1565		mutex = this;
1566		}
1567	<	SynchronizedCollection(Collection<E> c, Object mutex) {
1568	<	this.c = c;
1567	>	SynchronizedCollection(Collection<E> c, Object mutex) {
1568	>	this.c = c;
1569		this.mutex = mutex;
1570		}
1571
1572	<	public int size() {
1573	<	synchronized(mutex) {return c.size();}
1572	>	public int size() {
1573	>	synchronized(mutex) {return c.size();}
1574		}
1575	<	public boolean isEmpty() {
1576	<	synchronized(mutex) {return c.isEmpty();}
1575	>	public boolean isEmpty() {
1576	>	synchronized(mutex) {return c.isEmpty();}
1577		}
1578	<	public boolean contains(Object o) {
1579	<	synchronized(mutex) {return c.contains(o);}
1578	>	public boolean contains(Object o) {
1579	>	synchronized(mutex) {return c.contains(o);}
1580		}
1581	<	public Object[] toArray() {
1582	<	synchronized(mutex) {return c.toArray();}
1581	>	public Object[] toArray() {
1582	>	synchronized(mutex) {return c.toArray();}
1583		}
1584	<	public <T> T[] toArray(T[] a) {
1585	<	synchronized(mutex) {return c.toArray(a);}
1584	>	public <T> T[] toArray(T[] a) {
1585	>	synchronized(mutex) {return c.toArray(a);}
1586		}
1587
1588	<	public Iterator<E> iterator() {
1588	>	public Iterator<E> iterator() {
1589		return c.iterator(); // Must be manually synched by user!
1590		}
1591
1592	<	public boolean add(E e) {
1593	<	synchronized(mutex) {return c.add(e);}
1592	>	public boolean add(E e) {
1593	>	synchronized(mutex) {return c.add(e);}
1594		}
1595	<	public boolean remove(Object o) {
1596	<	synchronized(mutex) {return c.remove(o);}
1595	>	public boolean remove(Object o) {
1596	>	synchronized(mutex) {return c.remove(o);}
1597		}
1598
1599	<	public boolean containsAll(Collection<?> coll) {
1600	<	synchronized(mutex) {return c.containsAll(coll);}
1599	>	public boolean containsAll(Collection<?> coll) {
1600	>	synchronized(mutex) {return c.containsAll(coll);}
1601		}
1602	<	public boolean addAll(Collection<? extends E> coll) {
1603	<	synchronized(mutex) {return c.addAll(coll);}
1602	>	public boolean addAll(Collection<? extends E> coll) {
1603	>	synchronized(mutex) {return c.addAll(coll);}
1604		}
1605	<	public boolean removeAll(Collection<?> coll) {
1606	<	synchronized(mutex) {return c.removeAll(coll);}
1605	>	public boolean removeAll(Collection<?> coll) {
1606	>	synchronized(mutex) {return c.removeAll(coll);}
1607		}
1608	<	public boolean retainAll(Collection<?> coll) {
1609	<	synchronized(mutex) {return c.retainAll(coll);}
1608	>	public boolean retainAll(Collection<?> coll) {
1609	>	synchronized(mutex) {return c.retainAll(coll);}
1610		}
1611	<	public void clear() {
1612	<	synchronized(mutex) {c.clear();}
1611	>	public void clear() {
1612	>	synchronized(mutex) {c.clear();}
1613		}
1614	<	public String toString() {
1615	<	synchronized(mutex) {return c.toString();}
1614	>	public String toString() {
1615	>	synchronized(mutex) {return c.toString();}
1616		}
1617		private void writeObject(ObjectOutputStream s) throws IOException {
1618	<	synchronized(mutex) {s.defaultWriteObject();}
1618	>	synchronized(mutex) {s.defaultWriteObject();}
1619		}
1620		}
1621
#	Line 1633 \| Line 1645 \| public class Collections {
1645		* @return a synchronized view of the specified set.
1646		*/
1647		public static <T> Set<T> synchronizedSet(Set<T> s) {
1648	<	return new SynchronizedSet<T>(s);
1648	>	return new SynchronizedSet<T>(s);
1649		}
1650
1651		static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1652	<	return new SynchronizedSet<T>(s, mutex);
1652	>	return new SynchronizedSet<T>(s, mutex);
1653		}
1654
1655		/**
1656		* @serial include
1657		*/
1658		static class SynchronizedSet<E>
1659	<	extends SynchronizedCollection<E>
1660	<	implements Set<E> {
1661	<	private static final long serialVersionUID = 487447009682186044L;
1659	>	extends SynchronizedCollection<E>
1660	>	implements Set<E> {
1661	>	private static final long serialVersionUID = 487447009682186044L;
1662
1663	<	SynchronizedSet(Set<E> s) {
1663	>	SynchronizedSet(Set<E> s) {
1664		super(s);
1665		}
1666	<	SynchronizedSet(Set<E> s, Object mutex) {
1666	>	SynchronizedSet(Set<E> s, Object mutex) {
1667		super(s, mutex);
1668		}
1669
1670	<	public boolean equals(Object o) {
1671	<	synchronized(mutex) {return c.equals(o);}
1670	>	public boolean equals(Object o) {
1671	>	synchronized(mutex) {return c.equals(o);}
1672		}
1673	<	public int hashCode() {
1674	<	synchronized(mutex) {return c.hashCode();}
1673	>	public int hashCode() {
1674	>	synchronized(mutex) {return c.hashCode();}
1675		}
1676		}
1677
#	Line 1701 \| Line 1713 \| public class Collections {
1713		* @return a synchronized view of the specified sorted set.
1714		*/
1715		public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1716	<	return new SynchronizedSortedSet<T>(s);
1716	>	return new SynchronizedSortedSet<T>(s);
1717		}
1718
1719		/**
1720		* @serial include
1721		*/
1722		static class SynchronizedSortedSet<E>
1723	<	extends SynchronizedSet<E>
1724	<	implements SortedSet<E>
1723	>	extends SynchronizedSet<E>
1724	>	implements SortedSet<E>
1725		{
1726	<	private static final long serialVersionUID = 8695801310862127406L;
1726	>	private static final long serialVersionUID = 8695801310862127406L;
1727
1728		final private SortedSet<E> ss;
1729
1730	<	SynchronizedSortedSet(SortedSet<E> s) {
1730	>	SynchronizedSortedSet(SortedSet<E> s) {
1731		super(s);
1732		ss = s;
1733		}
1734	<	SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1734	>	SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1735		super(s, mutex);
1736		ss = s;
1737		}
1738
1739	<	public Comparator<? super E> comparator() {
1740	<	synchronized(mutex) {return ss.comparator();}
1739	>	public Comparator<? super E> comparator() {
1740	>	synchronized(mutex) {return ss.comparator();}
1741		}
1742
1743		public SortedSet<E> subSet(E fromElement, E toElement) {
1744	<	synchronized(mutex) {
1744	>	synchronized(mutex) {
1745		return new SynchronizedSortedSet<E>(
1746		ss.subSet(fromElement, toElement), mutex);
1747		}
1748		}
1749		public SortedSet<E> headSet(E toElement) {
1750	<	synchronized(mutex) {
1750	>	synchronized(mutex) {
1751		return new SynchronizedSortedSet<E>(ss.headSet(toElement), mutex);
1752		}
1753		}
1754		public SortedSet<E> tailSet(E fromElement) {
1755	<	synchronized(mutex) {
1755	>	synchronized(mutex) {
1756		return new SynchronizedSortedSet<E>(ss.tailSet(fromElement),mutex);
1757		}
1758		}
1759
1760		public E first() {
1761	<	synchronized(mutex) {return ss.first();}
1761	>	synchronized(mutex) {return ss.first();}
1762		}
1763		public E last() {
1764	<	synchronized(mutex) {return ss.last();}
1764	>	synchronized(mutex) {return ss.last();}
1765		}
1766		}
1767
#	Line 1779 \| Line 1791 \| public class Collections {
1791		* @return a synchronized view of the specified list.
1792		*/
1793		public static <T> List<T> synchronizedList(List<T> list) {
1794	<	return (list instanceof RandomAccess ?
1794	>	return (list instanceof RandomAccess ?
1795		new SynchronizedRandomAccessList<T>(list) :
1796		new SynchronizedList<T>(list));
1797		}
1798
1799		static <T> List<T> synchronizedList(List<T> list, Object mutex) {
1800	<	return (list instanceof RandomAccess ?
1800	>	return (list instanceof RandomAccess ?
1801		new SynchronizedRandomAccessList<T>(list, mutex) :
1802		new SynchronizedList<T>(list, mutex));
1803		}
#	Line 1794 \| Line 1806 \| public class Collections {
1806		* @serial include
1807		*/
1808		static class SynchronizedList<E>
1809	<	extends SynchronizedCollection<E>
1810	<	implements List<E> {
1811	<	static final long serialVersionUID = -7754090372962971524L;
1812	<
1813	<	final List<E> list;
1814	<
1815	<	SynchronizedList(List<E> list) {
1816	<	super(list);
1817	<	this.list = list;
1818	<	}
1819	<	SynchronizedList(List<E> list, Object mutex) {
1809	>	extends SynchronizedCollection<E>
1810	>	implements List<E> {
1811	>	private static final long serialVersionUID = -7754090372962971524L;
1812	>
1813	>	final List<E> list;
1814	>
1815	>	SynchronizedList(List<E> list) {
1816	>	super(list);
1817	>	this.list = list;
1818	>	}
1819	>	SynchronizedList(List<E> list, Object mutex) {
1820		super(list, mutex);
1821	<	this.list = list;
1821	>	this.list = list;
1822		}
1823
1824	<	public boolean equals(Object o) {
1825	<	synchronized(mutex) {return list.equals(o);}
1824	>	public boolean equals(Object o) {
1825	>	synchronized(mutex) {return list.equals(o);}
1826		}
1827	<	public int hashCode() {
1828	<	synchronized(mutex) {return list.hashCode();}
1827	>	public int hashCode() {
1828	>	synchronized(mutex) {return list.hashCode();}
1829		}
1830
1831	<	public E get(int index) {
1832	<	synchronized(mutex) {return list.get(index);}
1831	>	public E get(int index) {
1832	>	synchronized(mutex) {return list.get(index);}
1833		}
1834	<	public E set(int index, E element) {
1835	<	synchronized(mutex) {return list.set(index, element);}
1834	>	public E set(int index, E element) {
1835	>	synchronized(mutex) {return list.set(index, element);}
1836		}
1837	<	public void add(int index, E element) {
1838	<	synchronized(mutex) {list.add(index, element);}
1837	>	public void add(int index, E element) {
1838	>	synchronized(mutex) {list.add(index, element);}
1839		}
1840	<	public E remove(int index) {
1841	<	synchronized(mutex) {return list.remove(index);}
1840	>	public E remove(int index) {
1841	>	synchronized(mutex) {return list.remove(index);}
1842		}
1843
1844	<	public int indexOf(Object o) {
1845	<	synchronized(mutex) {return list.indexOf(o);}
1844	>	public int indexOf(Object o) {
1845	>	synchronized(mutex) {return list.indexOf(o);}
1846		}
1847	<	public int lastIndexOf(Object o) {
1848	<	synchronized(mutex) {return list.lastIndexOf(o);}
1847	>	public int lastIndexOf(Object o) {
1848	>	synchronized(mutex) {return list.lastIndexOf(o);}
1849		}
1850
1851	<	public boolean addAll(int index, Collection<? extends E> c) {
1852	<	synchronized(mutex) {return list.addAll(index, c);}
1851	>	public boolean addAll(int index, Collection<? extends E> c) {
1852	>	synchronized(mutex) {return list.addAll(index, c);}
1853		}
1854
1855	<	public ListIterator<E> listIterator() {
1856	<	return list.listIterator(); // Must be manually synched by user
1855	>	public ListIterator<E> listIterator() {
1856	>	return list.listIterator(); // Must be manually synched by user
1857		}
1858
1859	<	public ListIterator<E> listIterator(int index) {
1860	<	return list.listIterator(index); // Must be manually synched by user
1859	>	public ListIterator<E> listIterator(int index) {
1860	>	return list.listIterator(index); // Must be manually synched by user
1861		}
1862
1863	<	public List<E> subList(int fromIndex, int toIndex) {
1864	<	synchronized(mutex) {
1863	>	public List<E> subList(int fromIndex, int toIndex) {
1864	>	synchronized(mutex) {
1865		return new SynchronizedList<E>(list.subList(fromIndex, toIndex),
1866		mutex);
1867		}
#	Line 1869 \| Line 1881 \| public class Collections {
1881		*/
1882		private Object readResolve() {
1883		return (list instanceof RandomAccess
1884	<	? new SynchronizedRandomAccessList<E>(list)
1885	<	: this);
1884	>	? new SynchronizedRandomAccessList<E>(list)
1885	>	: this);
1886		}
1887		}
1888
#	Line 1878 \| Line 1890 \| public class Collections {
1890		* @serial include
1891		*/
1892		static class SynchronizedRandomAccessList<E>
1893	<	extends SynchronizedList<E>
1894	<	implements RandomAccess {
1893	>	extends SynchronizedList<E>
1894	>	implements RandomAccess {
1895
1896		SynchronizedRandomAccessList(List<E> list) {
1897		super(list);
1898		}
1899
1900	<	SynchronizedRandomAccessList(List<E> list, Object mutex) {
1900	>	SynchronizedRandomAccessList(List<E> list, Object mutex) {
1901		super(list, mutex);
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 SynchronizedRandomAccessList<E>(
1907		list.subList(fromIndex, toIndex), mutex);
1908		}
1909		}
1910
1911	<	static final long serialVersionUID = 1530674583602358482L;
1911	>	private static final long serialVersionUID = 1530674583602358482L;
1912
1913		/**
1914		* Allows instances to be deserialized in pre-1.4 JREs (which do
#	Line 1937 \| Line 1949 \| public class Collections {
1949		* @return a synchronized view of the specified map.
1950		*/
1951		public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
1952	<	return new SynchronizedMap<K,V>(m);
1952	>	return new SynchronizedMap<K,V>(m);
1953		}
1954
1955		/**
1956		* @serial include
1957		*/
1958		private static class SynchronizedMap<K,V>
1959	<	implements Map<K,V>, Serializable {
1960	<	// use serialVersionUID from JDK 1.2.2 for interoperability
1949	<	private static final long serialVersionUID = 1978198479659022715L;
1959	>	implements Map<K,V>, Serializable {
1960	>	private static final long serialVersionUID = 1978198479659022715L;
1961
1962	<	private final Map<K,V> m; // Backing Map
1963	<	final Object mutex; // Object on which to synchronize
1962	>	private final Map<K,V> m; // Backing Map
1963	>	final Object mutex; // Object on which to synchronize
1964
1965	<	SynchronizedMap(Map<K,V> m) {
1965	>	SynchronizedMap(Map<K,V> m) {
1966		if (m==null)
1967		throw new NullPointerException();
1968		this.m = m;
1969		mutex = this;
1970		}
1971
1972	<	SynchronizedMap(Map<K,V> m, Object mutex) {
1972	>	SynchronizedMap(Map<K,V> m, Object mutex) {
1973		this.m = m;
1974		this.mutex = mutex;
1975		}
1976
1977	<	public int size() {
1978	<	synchronized(mutex) {return m.size();}
1977	>	public int size() {
1978	>	synchronized(mutex) {return m.size();}
1979		}
1980	<	public boolean isEmpty(){
1981	<	synchronized(mutex) {return m.isEmpty();}
1980	>	public boolean isEmpty() {
1981	>	synchronized(mutex) {return m.isEmpty();}
1982		}
1983	<	public boolean containsKey(Object key) {
1984	<	synchronized(mutex) {return m.containsKey(key);}
1983	>	public boolean containsKey(Object key) {
1984	>	synchronized(mutex) {return m.containsKey(key);}
1985		}
1986	<	public boolean containsValue(Object value){
1987	<	synchronized(mutex) {return m.containsValue(value);}
1986	>	public boolean containsValue(Object value) {
1987	>	synchronized(mutex) {return m.containsValue(value);}
1988		}
1989	<	public V get(Object key) {
1990	<	synchronized(mutex) {return m.get(key);}
1989	>	public V get(Object key) {
1990	>	synchronized(mutex) {return m.get(key);}
1991		}
1992
1993	<	public V put(K key, V value) {
1994	<	synchronized(mutex) {return m.put(key, value);}
1993	>	public V put(K key, V value) {
1994	>	synchronized(mutex) {return m.put(key, value);}
1995		}
1996	<	public V remove(Object key) {
1997	<	synchronized(mutex) {return m.remove(key);}
1996	>	public V remove(Object key) {
1997	>	synchronized(mutex) {return m.remove(key);}
1998		}
1999	<	public void putAll(Map<? extends K, ? extends V> map) {
2000	<	synchronized(mutex) {m.putAll(map);}
1999	>	public void putAll(Map<? extends K, ? extends V> map) {
2000	>	synchronized(mutex) {m.putAll(map);}
2001	>	}
2002	>	public void clear() {
2003	>	synchronized(mutex) {m.clear();}
2004		}
1991	–	public void clear() {
1992	–	synchronized(mutex) {m.clear();}
1993	–	}
2005
2006	<	private transient Set<K> keySet = null;
2007	<	private transient Set<Map.Entry<K,V>> entrySet = null;
2008	<	private transient Collection<V> values = null;
2006	>	private transient Set<K> keySet = null;
2007	>	private transient Set<Map.Entry<K,V>> entrySet = null;
2008	>	private transient Collection<V> values = null;
2009
2010	<	public Set<K> keySet() {
2010	>	public Set<K> keySet() {
2011		synchronized(mutex) {
2012		if (keySet==null)
2013		keySet = new SynchronizedSet<K>(m.keySet(), mutex);
2014		return keySet;
2015		}
2016	<	}
2016	>	}
2017
2018	<	public Set<Map.Entry<K,V>> entrySet() {
2018	>	public Set<Map.Entry<K,V>> entrySet() {
2019		synchronized(mutex) {
2020		if (entrySet==null)
2021		entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2022		return entrySet;
2023		}
2024	<	}
2024	>	}
2025
2026	<	public Collection<V> values() {
2026	>	public Collection<V> values() {
2027		synchronized(mutex) {
2028		if (values==null)
2029		values = new SynchronizedCollection<V>(m.values(), mutex);
#	Line 2020 \| Line 2031 \| public class Collections {
2031		}
2032		}
2033
2034	<	public boolean equals(Object o) {
2034	>	public boolean equals(Object o) {
2035		synchronized(mutex) {return m.equals(o);}
2036		}
2037	<	public int hashCode() {
2037	>	public int hashCode() {
2038		synchronized(mutex) {return m.hashCode();}
2039		}
2040	<	public String toString() {
2041	<	synchronized(mutex) {return m.toString();}
2040	>	public String toString() {
2041	>	synchronized(mutex) {return m.toString();}
2042		}
2043		private void writeObject(ObjectOutputStream s) throws IOException {
2044	<	synchronized(mutex) {s.defaultWriteObject();}
2044	>	synchronized(mutex) {s.defaultWriteObject();}
2045		}
2046		}
2047
#	Line 2077 \| Line 2088 \| public class Collections {
2088		* @return a synchronized view of the specified sorted map.
2089		*/
2090		public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2091	<	return new SynchronizedSortedMap<K,V>(m);
2091	>	return new SynchronizedSortedMap<K,V>(m);
2092		}
2093
2094
#	Line 2085 \| Line 2096 \| public class Collections {
2096		* @serial include
2097		*/
2098		static class SynchronizedSortedMap<K,V>
2099	<	extends SynchronizedMap<K,V>
2100	<	implements SortedMap<K,V>
2099	>	extends SynchronizedMap<K,V>
2100	>	implements SortedMap<K,V>
2101		{
2102	<	private static final long serialVersionUID = -8798146769416483793L;
2102	>	private static final long serialVersionUID = -8798146769416483793L;
2103
2104		private final SortedMap<K,V> sm;
2105
2106	<	SynchronizedSortedMap(SortedMap<K,V> m) {
2106	>	SynchronizedSortedMap(SortedMap<K,V> m) {
2107		super(m);
2108		sm = m;
2109		}
2110	<	SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2110	>	SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2111		super(m, mutex);
2112		sm = m;
2113		}
2114
2115	<	public Comparator<? super K> comparator() {
2116	<	synchronized(mutex) {return sm.comparator();}
2115	>	public Comparator<? super K> comparator() {
2116	>	synchronized(mutex) {return sm.comparator();}
2117		}
2118
2119		public SortedMap<K,V> subMap(K fromKey, K toKey) {
2120	<	synchronized(mutex) {
2120	>	synchronized(mutex) {
2121		return new SynchronizedSortedMap<K,V>(
2122		sm.subMap(fromKey, toKey), mutex);
2123		}
2124		}
2125		public SortedMap<K,V> headMap(K toKey) {
2126	<	synchronized(mutex) {
2126	>	synchronized(mutex) {
2127		return new SynchronizedSortedMap<K,V>(sm.headMap(toKey), mutex);
2128		}
2129		}
2130		public SortedMap<K,V> tailMap(K fromKey) {
2131	<	synchronized(mutex) {
2131	>	synchronized(mutex) {
2132		return new SynchronizedSortedMap<K,V>(sm.tailMap(fromKey),mutex);
2133		}
2134		}
2135
2136		public K firstKey() {
2137	<	synchronized(mutex) {return sm.firstKey();}
2137	>	synchronized(mutex) {return sm.firstKey();}
2138		}
2139		public K lastKey() {
2140	<	synchronized(mutex) {return sm.lastKey();}
2140	>	synchronized(mutex) {return sm.lastKey();}
2141		}
2142		}
2143
2144		// Dynamically typesafe collection wrappers
2145
2146		/**
2147	<	* Returns a dynamically typesafe view of the specified collection. Any
2148	<	* attempt to insert an element of the wrong type will result in an
2149	<	* immediate <tt>ClassCastException</tt>. Assuming a collection contains
2150	<	* no incorrectly typed elements prior to the time a dynamically typesafe
2151	<	* view is generated, and that all subsequent access to the collection
2152	<	* takes place through the view, it is <i>guaranteed</i> that the
2153	<	* collection cannot contain an incorrectly typed element.
2147	>	* Returns a dynamically typesafe view of the specified collection.
2148	>	* Any attempt to insert an element of the wrong type will result in an
2149	>	* immediate {@link ClassCastException}. Assuming a collection
2150	>	* contains no incorrectly typed elements prior to the time a
2151	>	* dynamically typesafe view is generated, and that all subsequent
2152	>	* access to the collection takes place through the view, it is
2153	>	* <i>guaranteed</i> that the collection cannot contain an incorrectly
2154	>	* typed element.
2155		*
2156		* <p>The generics mechanism in the language provides compile-time
2157		* (static) type checking, but it is possible to defeat this mechanism
#	Line 2151 \| Line 2163 \| public class Collections {
2163		* inserting an element of the wrong type.
2164		*
2165		* <p>Another use of dynamically typesafe views is debugging. Suppose a
2166	<	* program fails with a <tt>ClassCastException</tt>, indicating that an
2166	>	* program fails with a {@code ClassCastException}, indicating that an
2167		* incorrectly typed element was put into a parameterized collection.
2168		* Unfortunately, the exception can occur at any time after the erroneous
2169		* element is inserted, so it typically provides little or no information
#	Line 2159 \| Line 2171 \| public class Collections {
2171		* one can quickly determine its source by temporarily modifying the
2172		* program to wrap the collection with a dynamically typesafe view.
2173		* For example, this declaration:
2174	<	* <pre>
2175	<	* Collection<String> c = new HashSet<String>();
2176	<	* </pre>
2174	>	* <pre> {@code
2175	>	* Collection<String> c = new HashSet<String>();
2176	>	* }</pre>
2177		* may be replaced temporarily by this one:
2178	<	* <pre>
2179	<	* Collection<String> c = Collections.checkedCollection(
2180	<	* new HashSet<String>(), String.class);
2181	<	* </pre>
2178	>	* <pre> {@code
2179	>	* Collection<String> c = Collections.checkedCollection(
2180	>	* new HashSet<String>(), String.class);
2181	>	* }</pre>
2182		* Running the program again will cause it to fail at the point where
2183		* an incorrectly typed element is inserted into the collection, clearly
2184		* identifying the source of the problem. Once the problem is fixed, the
#	Line 2174 \| Line 2186 \| public class Collections {
2186		*
2187		* <p>The returned collection does <i>not</i> pass the hashCode and equals
2188		* operations through to the backing collection, but relies on
2189	<	* <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
2189	>	* {@code Object}'s {@code equals} and {@code hashCode} methods. This
2190		* is necessary to preserve the contracts of these operations in the case
2191		* that the backing collection is a set or a list.
2192		*
2193		* <p>The returned collection will be serializable if the specified
2194		* collection is serializable.
2195		*
2196	+	* <p>Since {@code null} is considered to be a value of any reference
2197	+	* type, the returned collection permits insertion of null elements
2198	+	* whenever the backing collection does.
2199	+	*
2200		* @param c the collection for which a dynamically typesafe view is to be
2201	<	* returned
2202	<	* @param type the type of element that <tt>c</tt> is permitted to hold
2201	>	* returned
2202	>	* @param type the type of element that {@code c} is permitted to hold
2203		* @return a dynamically typesafe view of the specified collection
2204		* @since 1.5
2205		*/
#	Line 2192 \| Line 2208 \| public class Collections {
2208		return new CheckedCollection<E>(c, type);
2209		}
2210
2211	+	@SuppressWarnings("unchecked")
2212	+	static <T> T[] zeroLengthArray(Class<T> type) {
2213	+	return (T[]) Array.newInstance(type, 0);
2214	+	}
2215	+
2216		/**
2217		* @serial include
2218		*/
#	Line 2202 \| Line 2223 \| public class Collections {
2223		final Class<E> type;
2224
2225		void typeCheck(Object o) {
2226	<	if (!type.isInstance(o))
2227	<	throw new ClassCastException("Attempt to insert " +
2228	<	o.getClass() + " element into collection with element type "
2229	<	+ type);
2226	>	if (o != null && !type.isInstance(o))
2227	>	throw new ClassCastException(badElementMsg(o));
2228	>	}
2229	>
2230	>	private String badElementMsg(Object o) {
2231	>	return "Attempt to insert " + o.getClass() +
2232	>	" element into collection with element type " + type;
2233		}
2234
2235		CheckedCollection(Collection<E> c, Class<E> type) {
#	Line 2215 \| Line 2239 \| public class Collections {
2239		this.type = type;
2240		}
2241
2242	<	public int size() { return c.size(); }
2243	<	public boolean isEmpty() { return c.isEmpty(); }
2244	<	public boolean contains(Object o) { return c.contains(o); }
2245	<	public Object[] toArray() { return c.toArray(); }
2246	<	public <T> T[] toArray(T[] a) { return c.toArray(a); }
2247	<	public String toString() { return c.toString(); }
2248	<	public Iterator<E> iterator() { return c.iterator(); }
2249	<	public boolean remove(Object o) { return c.remove(o); }
2242	>	public int size() { return c.size(); }
2243	>	public boolean isEmpty() { return c.isEmpty(); }
2244	>	public boolean contains(Object o) { return c.contains(o); }
2245	>	public Object[] toArray() { return c.toArray(); }
2246	>	public <T> T[] toArray(T[] a) { return c.toArray(a); }
2247	>	public String toString() { return c.toString(); }
2248	>	public boolean remove(Object o) { return c.remove(o); }
2249	>	public void clear() { c.clear(); }
2250	>
2251		public boolean containsAll(Collection<?> coll) {
2252		return c.containsAll(coll);
2253		}
#	Line 2232 \| Line 2257 \| public class Collections {
2257		public boolean retainAll(Collection<?> coll) {
2258		return c.retainAll(coll);
2259		}
2260	<	public void clear() {
2261	<	c.clear();
2260	>
2261	>	public Iterator<E> iterator() {
2262	>	final Iterator<E> it = c.iterator();
2263	>	return new Iterator<E>() {
2264	>	public boolean hasNext() { return it.hasNext(); }
2265	>	public E next() { return it.next(); }
2266	>	public void remove() { it.remove(); }};
2267		}
2268
2269	<	public boolean add(E e){
2269	>	public boolean add(E e) {
2270		typeCheck(e);
2271		return c.add(e);
2272		}
2273
2274	<	public boolean addAll(Collection<? extends E> coll) {
2245	<	/*
2246	<	* Dump coll into an array of the required type. This serves
2247	<	* three purposes: it insulates us from concurrent changes in
2248	<	* the contents of coll, it type-checks all of the elements in
2249	<	* coll, and it provides all-or-nothing semantics (which we
2250	<	* wouldn't get if we type-checked each element as we added it).
2251	<	*/
2252	<	E[] a = null;
2253	<	try {
2254	<	a = coll.toArray(zeroLengthElementArray());
2255	<	} catch (ArrayStoreException e) {
2256	<	throw new ClassCastException();
2257	<	}
2274	>	private E[] zeroLengthElementArray = null; // Lazily initialized
2275
2276	<	boolean result = false;
2277	<	for (E e : a)
2278	<	result \|= c.add(e);
2262	<	return result;
2276	>	private E[] zeroLengthElementArray() {
2277	>	return zeroLengthElementArray != null ? zeroLengthElementArray :
2278	>	(zeroLengthElementArray = zeroLengthArray(type));
2279		}
2280
2281	<	private E[] zeroLengthElementArray = null; // Lazily initialized
2281	>	@SuppressWarnings("unchecked")
2282	>	Collection<E> checkedCopyOf(Collection<? extends E> coll) {
2283	>	Object[] a = null;
2284	>	try {
2285	>	E[] z = zeroLengthElementArray();
2286	>	a = coll.toArray(z);
2287	>	// Defend against coll violating the toArray contract
2288	>	if (a.getClass() != z.getClass())
2289	>	a = Arrays.copyOf(a, a.length, z.getClass());
2290	>	} catch (ArrayStoreException ignore) {
2291	>	// To get better and consistent diagnostics,
2292	>	// we call typeCheck explicitly on each element.
2293	>	// We call clone() to defend against coll retaining a
2294	>	// reference to the returned array and storing a bad
2295	>	// element into it after it has been type checked.
2296	>	a = coll.toArray().clone();
2297	>	for (Object o : a)
2298	>	typeCheck(o);
2299	>	}
2300	>	// A slight abuse of the type system, but safe here.
2301	>	return (Collection<E>) Arrays.asList(a);
2302	>	}
2303
2304	<	/*
2305	<	* We don't need locking or volatile, because it's OK if we create
2306	<	* several zeroLengthElementArrays, and they're immutable.
2307	<	*/
2308	<	E[] zeroLengthElementArray() {
2309	<	if (zeroLengthElementArray == null)
2273	<	zeroLengthElementArray = (E[]) Array.newInstance(type, 0);
2274	<	return zeroLengthElementArray;
2304	>	public boolean addAll(Collection<? extends E> coll) {
2305	>	// Doing things this way insulates us from concurrent changes
2306	>	// in the contents of coll and provides all-or-nothing
2307	>	// semantics (which we wouldn't get if we type-checked each
2308	>	// element as we added it)
2309	>	return c.addAll(checkedCopyOf(coll));
2310		}
2311		}
2312
2313		/**
2314		* Returns a dynamically typesafe view of the specified set.
2315		* Any attempt to insert an element of the wrong type will result in
2316	<	* an immediate <tt>ClassCastException</tt>. Assuming a set contains
2316	>	* an immediate {@link ClassCastException}. Assuming a set contains
2317		* no incorrectly typed elements prior to the time a dynamically typesafe
2318		* view is generated, and that all subsequent access to the set
2319		* takes place through the view, it is <i>guaranteed</i> that the
2320		* set cannot contain an incorrectly typed element.
2321		*
2322		* <p>A discussion of the use of dynamically typesafe views may be
2323	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2324	<	* method.
2323	>	* found in the documentation for the {@link #checkedCollection
2324	>	* checkedCollection} method.
2325		*
2326		* <p>The returned set will be serializable if the specified set is
2327		* serializable.
2328		*
2329	+	* <p>Since {@code null} is considered to be a value of any reference
2330	+	* type, the returned set permits insertion of null elements whenever
2331	+	* the backing set does.
2332	+	*
2333		* @param s the set for which a dynamically typesafe view is to be
2334	<	* returned
2335	<	* @param type the type of element that <tt>s</tt> is permitted to hold
2334	>	* returned
2335	>	* @param type the type of element that {@code s} is permitted to hold
2336		* @return a dynamically typesafe view of the specified set
2337		* @since 1.5
2338		*/
#	Line 2311 \| Line 2350 \| public class Collections {
2350
2351		CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2352
2353	<	public boolean equals(Object o) { return c.equals(o); }
2353	>	public boolean equals(Object o) { return o == this \|\| c.equals(o); }
2354		public int hashCode() { return c.hashCode(); }
2355		}
2356
2357		/**
2358	<	* Returns a dynamically typesafe view of the specified sorted set. Any
2359	<	* attempt to insert an element of the wrong type will result in an
2360	<	* immediate <tt>ClassCastException</tt>. Assuming a sorted set contains
2361	<	* no incorrectly typed elements prior to the time a dynamically typesafe
2362	<	* view is generated, and that all subsequent access to the sorted set
2363	<	* takes place through the view, it is <i>guaranteed</i> that the sorted
2364	<	* set cannot contain an incorrectly typed element.
2358	>	* Returns a dynamically typesafe view of the specified sorted set.
2359	>	* Any attempt to insert an element of the wrong type will result in an
2360	>	* immediate {@link ClassCastException}. Assuming a sorted set
2361	>	* contains no incorrectly typed elements prior to the time a
2362	>	* dynamically typesafe view is generated, and that all subsequent
2363	>	* access to the sorted set takes place through the view, it is
2364	>	* <i>guaranteed</i> that the sorted set cannot contain an incorrectly
2365	>	* typed element.
2366		*
2367		* <p>A discussion of the use of dynamically typesafe views may be
2368	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2369	<	* method.
2368	>	* found in the documentation for the {@link #checkedCollection
2369	>	* checkedCollection} method.
2370		*
2371		* <p>The returned sorted set will be serializable if the specified sorted
2372		* set is serializable.
2373		*
2374	+	* <p>Since {@code null} is considered to be a value of any reference
2375	+	* type, the returned sorted set permits insertion of null elements
2376	+	* whenever the backing sorted set does.
2377	+	*
2378		* @param s the sorted set for which a dynamically typesafe view is to be
2379	<	* returned
2380	<	* @param type the type of element that <tt>s</tt> is permitted to hold
2379	>	* returned
2380	>	* @param type the type of element that {@code s} is permitted to hold
2381		* @return a dynamically typesafe view of the specified sorted set
2382		* @since 1.5
2383		*/
#	Line 2361 \| Line 2405 \| public class Collections {
2405		public E last() { return ss.last(); }
2406
2407		public SortedSet<E> subSet(E fromElement, E toElement) {
2408	<	return new CheckedSortedSet<E>(ss.subSet(fromElement,toElement),
2365	<	type);
2408	>	return checkedSortedSet(ss.subSet(fromElement,toElement), type);
2409		}
2410		public SortedSet<E> headSet(E toElement) {
2411	<	return new CheckedSortedSet<E>(ss.headSet(toElement), type);
2411	>	return checkedSortedSet(ss.headSet(toElement), type);
2412		}
2413		public SortedSet<E> tailSet(E fromElement) {
2414	<	return new CheckedSortedSet<E>(ss.tailSet(fromElement), type);
2414	>	return checkedSortedSet(ss.tailSet(fromElement), type);
2415		}
2416		}
2417
2418		/**
2419		* Returns a dynamically typesafe view of the specified list.
2420		* Any attempt to insert an element of the wrong type will result in
2421	<	* an immediate <tt>ClassCastException</tt>. Assuming a list contains
2421	>	* an immediate {@link ClassCastException}. Assuming a list contains
2422		* no incorrectly typed elements prior to the time a dynamically typesafe
2423		* view is generated, and that all subsequent access to the list
2424		* takes place through the view, it is <i>guaranteed</i> that the
2425		* list cannot contain an incorrectly typed element.
2426		*
2427		* <p>A discussion of the use of dynamically typesafe views may be
2428	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2429	<	* method.
2428	>	* found in the documentation for the {@link #checkedCollection
2429	>	* checkedCollection} method.
2430		*
2431	<	* <p>The returned list will be serializable if the specified list is
2432	<	* serializable.
2431	>	* <p>The returned list will be serializable if the specified list
2432	>	* is serializable.
2433	>	*
2434	>	* <p>Since {@code null} is considered to be a value of any reference
2435	>	* type, the returned list permits insertion of null elements whenever
2436	>	* the backing list does.
2437		*
2438		* @param list the list for which a dynamically typesafe view is to be
2439		* returned
2440	<	* @param type the type of element that <tt>list</tt> is permitted to hold
2440	>	* @param type the type of element that {@code list} is permitted to hold
2441		* @return a dynamically typesafe view of the specified list
2442		* @since 1.5
2443		*/
#	Line 2403 \| Line 2450 \| public class Collections {
2450		/**
2451		* @serial include
2452		*/
2453	<	static class CheckedList<E> extends CheckedCollection<E>
2454	<	implements List<E>
2453	>	static class CheckedList<E>
2454	>	extends CheckedCollection<E>
2455	>	implements List<E>
2456		{
2457	<	static final long serialVersionUID = 65247728283967356L;
2457	>	private static final long serialVersionUID = 65247728283967356L;
2458		final List<E> list;
2459
2460		CheckedList(List<E> list, Class<E> type) {
#	Line 2414 \| Line 2462 \| public class Collections {
2462		this.list = list;
2463		}
2464
2465	<	public boolean equals(Object o) { return list.equals(o); }
2465	>	public boolean equals(Object o) { return o == this \|\| list.equals(o); }
2466		public int hashCode() { return list.hashCode(); }
2467		public E get(int index) { return list.get(index); }
2468		public E remove(int index) { return list.remove(index); }
#	Line 2432 \| Line 2480 \| public class Collections {
2480		}
2481
2482		public boolean addAll(int index, Collection<? extends E> c) {
2483	<	// See CheckCollection.addAll, above, for an explanation
2436	<	E[] a = null;
2437	<	try {
2438	<	a = c.toArray(zeroLengthElementArray());
2439	<	} catch (ArrayStoreException e) {
2440	<	throw new ClassCastException();
2441	<	}
2442	<
2443	<	return list.addAll(index, Arrays.asList(a));
2483	>	return list.addAll(index, checkedCopyOf(c));
2484		}
2485		public ListIterator<E> listIterator() { return listIterator(0); }
2486
2487		public ListIterator<E> listIterator(final int index) {
2488	<	return new ListIterator<E>() {
2449	<	ListIterator<E> i = list.listIterator(index);
2488	>	final ListIterator<E> i = list.listIterator(index);
2489
2490	+	return new ListIterator<E>() {
2491		public boolean hasNext() { return i.hasNext(); }
2492		public E next() { return i.next(); }
2493		public boolean hasPrevious() { return i.hasPrevious(); }
2494		public E previous() { return i.previous(); }
2495		public int nextIndex() { return i.nextIndex(); }
2496		public int previousIndex() { return i.previousIndex(); }
2497	<	public void remove() { i.remove(); }
2497	>	public void remove() { i.remove(); }
2498
2499		public void set(E e) {
2500		typeCheck(e);
#	Line 2492 \| Line 2532 \| public class Collections {
2532		}
2533
2534		/**
2535	<	* Returns a dynamically typesafe view of the specified map. Any attempt
2536	<	* to insert a mapping whose key or value have the wrong type will result
2537	<	* in an immediate <tt>ClassCastException</tt>. Similarly, any attempt to
2538	<	* modify the value currently associated with a key will result in an
2539	<	* immediate <tt>ClassCastException</tt>, whether the modification is
2540	<	* attempted directly through the map itself, or through a {@link
2541	<	* Map.Entry} instance obtained from the map's {@link Map#entrySet()
2542	<	* entry set} view.
2535	>	* Returns a dynamically typesafe view of the specified map.
2536	>	* Any attempt to insert a mapping whose key or value have the wrong
2537	>	* type will result in an immediate {@link ClassCastException}.
2538	>	* Similarly, any attempt to modify the value currently associated with
2539	>	* a key will result in an immediate {@link ClassCastException},
2540	>	* whether the modification is attempted directly through the map
2541	>	* itself, or through a {@link Map.Entry} instance obtained from the
2542	>	* map's {@link Map#entrySet() entry set} view.
2543		*
2544		* <p>Assuming a map contains no incorrectly typed keys or values
2545		* prior to the time a dynamically typesafe view is generated, and
#	Line 2508 \| Line 2548 \| public class Collections {
2548		* map cannot contain an incorrectly typed key or value.
2549		*
2550		* <p>A discussion of the use of dynamically typesafe views may be
2551	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2552	<	* method.
2551	>	* found in the documentation for the {@link #checkedCollection
2552	>	* checkedCollection} method.
2553		*
2554		* <p>The returned map will be serializable if the specified map is
2555		* serializable.
2556		*
2557	+	* <p>Since {@code null} is considered to be a value of any reference
2558	+	* type, the returned map permits insertion of null keys or values
2559	+	* whenever the backing map does.
2560	+	*
2561		* @param m the map for which a dynamically typesafe view is to be
2562	<	* returned
2563	<	* @param keyType the type of key that <tt>m</tt> is permitted to hold
2564	<	* @param valueType the type of value that <tt>m</tt> is permitted to hold
2562	>	* returned
2563	>	* @param keyType the type of key that {@code m} is permitted to hold
2564	>	* @param valueType the type of value that {@code m} is permitted to hold
2565		* @return a dynamically typesafe view of the specified map
2566		* @since 1.5
2567		*/
2568	<	public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType,
2568	>	public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
2569	>	Class<K> keyType,
2570		Class<V> valueType) {
2571		return new CheckedMap<K,V>(m, keyType, valueType);
2572		}
#	Line 2530 \| Line 2575 \| public class Collections {
2575		/**
2576		* @serial include
2577		*/
2578	<	private static class CheckedMap<K,V> implements Map<K,V>,
2579	<	Serializable
2578	>	private static class CheckedMap<K,V>
2579	>	implements Map<K,V>, Serializable
2580		{
2581		private static final long serialVersionUID = 5742860141034234728L;
2582
#	Line 2540 \| Line 2585 \| public class Collections {
2585		final Class<V> valueType;
2586
2587		private void typeCheck(Object key, Object value) {
2588	<	if (!keyType.isInstance(key))
2589	<	throw new ClassCastException("Attempt to insert " +
2590	<	key.getClass() + " key into collection with key type "
2591	<	+ keyType);
2592	<
2593	<	if (!valueType.isInstance(value))
2594	<	throw new ClassCastException("Attempt to insert " +
2595	<	value.getClass() +" value into collection with value type "
2596	<	+ valueType);
2588	>	if (key != null && !keyType.isInstance(key))
2589	>	throw new ClassCastException(badKeyMsg(key));
2590	>
2591	>	if (value != null && !valueType.isInstance(value))
2592	>	throw new ClassCastException(badValueMsg(value));
2593	>	}
2594	>
2595	>	private String badKeyMsg(Object key) {
2596	>	return "Attempt to insert " + key.getClass() +
2597	>	" key into map with key type " + keyType;
2598	>	}
2599	>
2600	>	private String badValueMsg(Object value) {
2601	>	return "Attempt to insert " + value.getClass() +
2602	>	" value into map with value type " + valueType;
2603		}
2604
2605		CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
#	Line 2568 \| Line 2619 \| public class Collections {
2619		public void clear() { m.clear(); }
2620		public Set<K> keySet() { return m.keySet(); }
2621		public Collection<V> values() { return m.values(); }
2622	<	public boolean equals(Object o) { return m.equals(o); }
2622	>	public boolean equals(Object o) { return o == this \|\| m.equals(o); }
2623		public int hashCode() { return m.hashCode(); }
2624		public String toString() { return m.toString(); }
2625
#	Line 2577 \| Line 2628 \| public class Collections {
2628		return m.put(key, value);
2629		}
2630
2631	+	@SuppressWarnings("unchecked")
2632		public void putAll(Map<? extends K, ? extends V> t) {
2633	<	// See CheckCollection.addAll, above, for an explanation
2634	<	K[] keys = null;
2635	<	try {
2636	<	keys = t.keySet().toArray(zeroLengthKeyArray());
2637	<	} catch (ArrayStoreException e) {
2638	<	throw new ClassCastException();
2639	<	}
2640	<	V[] values = null;
2641	<	try {
2642	<	values = t.values().toArray(zeroLengthValueArray());
2643	<	} catch (ArrayStoreException e) {
2644	<	throw new ClassCastException();
2633	>	// Satisfy the following goals:
2634	>	// - good diagnostics in case of type mismatch
2635	>	// - all-or-nothing semantics
2636	>	// - protection from malicious t
2637	>	// - correct behavior if t is a concurrent map
2638	>	Object[] entries = t.entrySet().toArray();
2639	>	List<Map.Entry<K,V>> checked =
2640	>	new ArrayList<Map.Entry<K,V>>(entries.length);
2641	>	for (Object o : entries) {
2642	>	Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2643	>	Object k = e.getKey();
2644	>	Object v = e.getValue();
2645	>	typeCheck(k, v);
2646	>	checked.add(
2647	>	new AbstractMap.SimpleImmutableEntry<K,V>((K) k, (V) v));
2648		}
2649	<
2650	<	if (keys.length != values.length)
2596	<	throw new ConcurrentModificationException();
2597	<
2598	<	for (int i = 0; i < keys.length; i++)
2599	<	m.put(keys[i], values[i]);
2600	<	}
2601	<
2602	<	// Lazily initialized
2603	<	private K[] zeroLengthKeyArray = null;
2604	<	private V[] zeroLengthValueArray = null;
2605	<
2606	<	/*
2607	<	* We don't need locking or volatile, because it's OK if we create
2608	<	* several zeroLengthValueArrays, and they're immutable.
2609	<	*/
2610	<	private K[] zeroLengthKeyArray() {
2611	<	if (zeroLengthKeyArray == null)
2612	<	zeroLengthKeyArray = (K[]) Array.newInstance(keyType, 0);
2613	<	return zeroLengthKeyArray;
2614	<	}
2615	<	private V[] zeroLengthValueArray() {
2616	<	if (zeroLengthValueArray == null)
2617	<	zeroLengthValueArray = (V[]) Array.newInstance(valueType, 0);
2618	<	return zeroLengthValueArray;
2649	>	for (Map.Entry<K,V> e : checked)
2650	>	m.put(e.getKey(), e.getValue());
2651		}
2652
2653		private transient Set<Map.Entry<K,V>> entrySet = null;
#	Line 2635 \| Line 2667 \| public class Collections {
2667		* @serial exclude
2668		*/
2669		static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> {
2670	<	Set<Map.Entry<K,V>> s;
2671	<	Class<V> valueType;
2670	>	private final Set<Map.Entry<K,V>> s;
2671	>	private final Class<V> valueType;
2672
2673		CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
2674		this.s = s;
2675		this.valueType = valueType;
2676		}
2677
2678	<	public int size() { return s.size(); }
2679	<	public boolean isEmpty() { return s.isEmpty(); }
2680	<	public String toString() { return s.toString(); }
2681	<	public int hashCode() { return s.hashCode(); }
2682	<	public boolean remove(Object o) { return s.remove(o); }
2651	<	public boolean removeAll(Collection<?> coll) {
2652	<	return s.removeAll(coll);
2653	<	}
2654	<	public boolean retainAll(Collection<?> coll) {
2655	<	return s.retainAll(coll);
2656	<	}
2657	<	public void clear() {
2658	<	s.clear();
2659	<	}
2678	>	public int size() { return s.size(); }
2679	>	public boolean isEmpty() { return s.isEmpty(); }
2680	>	public String toString() { return s.toString(); }
2681	>	public int hashCode() { return s.hashCode(); }
2682	>	public void clear() { s.clear(); }
2683
2684	<	public boolean add(Map.Entry<K, V> e){
2684	>	public boolean add(Map.Entry<K, V> e) {
2685		throw new UnsupportedOperationException();
2686		}
2687		public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
2688		throw new UnsupportedOperationException();
2689		}
2690
2668	–
2691		public Iterator<Map.Entry<K,V>> iterator() {
2692	<	return new Iterator<Map.Entry<K,V>>() {
2693	<	Iterator<Map.Entry<K, V>> i = s.iterator();
2692	>	final Iterator<Map.Entry<K, V>> i = s.iterator();
2693	>	final Class<V> valueType = this.valueType;
2694
2695	+	return new Iterator<Map.Entry<K,V>>() {
2696		public boolean hasNext() { return i.hasNext(); }
2697		public void remove() { i.remove(); }
2698
2699		public Map.Entry<K,V> next() {
2700	<	return new CheckedEntry<K,V>(i.next(), valueType);
2700	>	return checkedEntry(i.next(), valueType);
2701		}
2702		};
2703		}
2704
2705	+	@SuppressWarnings("unchecked")
2706		public Object[] toArray() {
2707		Object[] source = s.toArray();
2708
#	Line 2691 \| Line 2715 \| public class Collections {
2715		new Object[source.length]);
2716
2717		for (int i = 0; i < source.length; i++)
2718	<	dest[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)source[i],
2719	<	valueType);
2718	>	dest[i] = checkedEntry((Map.Entry<K,V>)source[i],
2719	>	valueType);
2720		return dest;
2721		}
2722
2723	+	@SuppressWarnings("unchecked")
2724		public <T> T[] toArray(T[] a) {
2725		// We don't pass a to s.toArray, to avoid window of
2726		// vulnerability wherein an unscrupulous multithreaded client
2727		// could get his hands on raw (unwrapped) Entries from s.
2728	<	Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2728	>	T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2729
2730		for (int i=0; i<arr.length; i++)
2731	<	arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i],
2732	<	valueType);
2731	>	arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i],
2732	>	valueType);
2733		if (arr.length > a.length)
2734	<	return (T[])arr;
2734	>	return arr;
2735
2736		System.arraycopy(arr, 0, a, 0, arr.length);
2737		if (a.length > arr.length)
#	Line 2723 \| Line 2748 \| public class Collections {
2748		public boolean contains(Object o) {
2749		if (!(o instanceof Map.Entry))
2750		return false;
2751	+	Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2752		return s.contains(
2753	<	new CheckedEntry<K,V>((Map.Entry<K,V>) o, valueType));
2753	>	(e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
2754		}
2755
2756		/**
2757	<	* The next two methods are overridden to protect against
2758	<	* an unscrupulous collection whose contains(Object o) method
2759	<	* senses when o is a Map.Entry, and calls o.setValue.
2757	>	* The bulk collection methods are overridden to protect
2758	>	* against an unscrupulous collection whose contains(Object o)
2759	>	* method senses when o is a Map.Entry, and calls o.setValue.
2760		*/
2761	<	public boolean containsAll(Collection<?> coll) {
2762	<	Iterator<?> e = coll.iterator();
2763	<	while (e.hasNext())
2738	<	if (!contains(e.next())) // Invokes safe contains() above
2761	>	public boolean containsAll(Collection<?> c) {
2762	>	for (Object o : c)
2763	>	if (!contains(o)) // Invokes safe contains() above
2764		return false;
2765		return true;
2766		}
2767
2768	+	public boolean remove(Object o) {
2769	+	if (!(o instanceof Map.Entry))
2770	+	return false;
2771	+	return s.remove(new AbstractMap.SimpleImmutableEntry
2772	+	<Object, Object>((Map.Entry<?,?>)o));
2773	+	}
2774	+
2775	+	public boolean removeAll(Collection<?> c) {
2776	+	return batchRemove(c, false);
2777	+	}
2778	+	public boolean retainAll(Collection<?> c) {
2779	+	return batchRemove(c, true);
2780	+	}
2781	+	private boolean batchRemove(Collection<?> c, boolean complement) {
2782	+	boolean modified = false;
2783	+	Iterator<Map.Entry<K,V>> it = iterator();
2784	+	while (it.hasNext()) {
2785	+	if (c.contains(it.next()) != complement) {
2786	+	it.remove();
2787	+	modified = true;
2788	+	}
2789	+	}
2790	+	return modified;
2791	+	}
2792	+
2793		public boolean equals(Object o) {
2794		if (o == this)
2795		return true;
2796		if (!(o instanceof Set))
2797		return false;
2798		Set<?> that = (Set<?>) o;
2799	<	if (that.size() != s.size())
2800	<	return false;
2801	<	return containsAll(that); // Invokes safe containsAll() above
2799	>	return that.size() == s.size()
2800	>	&& containsAll(that); // Invokes safe containsAll() above
2801	>	}
2802	>
2803	>	static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e,
2804	>	Class<T> valueType) {
2805	>	return new CheckedEntry<K,V,T>(e, valueType);
2806		}
2807
2808		/**
#	Line 2756 \| Line 2810 \| public class Collections {
2810		* the client from modifying the backing Map, by short-circuiting
2811		* the setValue method, and it protects the backing Map against
2812		* an ill-behaved Map.Entry that attempts to modify another
2813	<	* Map Entry when asked to perform an equality check.
2813	>	* Map.Entry when asked to perform an equality check.
2814		*/
2815	<	private static class CheckedEntry<K,V> implements Map.Entry<K,V> {
2816	<	private Map.Entry<K, V> e;
2817	<	private Class<V> valueType;
2815	>	private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> {
2816	>	private final Map.Entry<K, V> e;
2817	>	private final Class<T> valueType;
2818
2819	<	CheckedEntry(Map.Entry<K, V> e, Class<V> valueType) {
2819	>	CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) {
2820		this.e = e;
2821		this.valueType = valueType;
2822		}
#	Line 2772 \| Line 2826 \| public class Collections {
2826		public int hashCode() { return e.hashCode(); }
2827		public String toString() { return e.toString(); }
2828
2775	–
2829		public V setValue(V value) {
2830	<	if (!valueType.isInstance(value))
2831	<	throw new ClassCastException("Attempt to insert " +
2779	<	value.getClass() +
2780	<	" value into collection with value type " + valueType);
2830	>	if (value != null && !valueType.isInstance(value))
2831	>	throw new ClassCastException(badValueMsg(value));
2832		return e.setValue(value);
2833		}
2834
2835	+	private String badValueMsg(Object value) {
2836	+	return "Attempt to insert " + value.getClass() +
2837	+	" value into map with value type " + valueType;
2838	+	}
2839	+
2840		public boolean equals(Object o) {
2841	+	if (o == this)
2842	+	return true;
2843		if (!(o instanceof Map.Entry))
2844		return false;
2845	<	Map.Entry t = (Map.Entry)o;
2846	<	return eq(e.getKey(), t.getKey()) &&
2789	<	eq(e.getValue(), t.getValue());
2845	>	return e.equals(new AbstractMap.SimpleImmutableEntry
2846	>	<Object, Object>((Map.Entry<?,?>)o));
2847		}
2848		}
2849		}
2850		}
2851
2852		/**
2853	<	* Returns a dynamically typesafe view of the specified sorted map. Any
2854	<	* attempt to insert a mapping whose key or value have the wrong type will
2855	<	* result in an immediate <tt>ClassCastException</tt>. Similarly, any
2856	<	* attempt to modify the value currently associated with a key will result
2857	<	* in an immediate <tt>ClassCastException</tt>, whether the modification
2858	<	* is attempted directly through the map itself, or through a {@link
2859	<	* Map.Entry} instance obtained from the map's {@link Map#entrySet() entry
2860	<	* set} view.
2853	>	* Returns a dynamically typesafe view of the specified sorted map.
2854	>	* Any attempt to insert a mapping whose key or value have the wrong
2855	>	* type will result in an immediate {@link ClassCastException}.
2856	>	* Similarly, any attempt to modify the value currently associated with
2857	>	* a key will result in an immediate {@link ClassCastException},
2858	>	* whether the modification is attempted directly through the map
2859	>	* itself, or through a {@link Map.Entry} instance obtained from the
2860	>	* map's {@link Map#entrySet() entry set} view.
2861		*
2862		* <p>Assuming a map contains no incorrectly typed keys or values
2863		* prior to the time a dynamically typesafe view is generated, and
#	Line 2809 \| Line 2866 \| public class Collections {
2866		* map cannot contain an incorrectly typed key or value.
2867		*
2868		* <p>A discussion of the use of dynamically typesafe views may be
2869	<	* found in the documentation for the {@link #checkedCollection checkedCollection}
2870	<	* method.
2869	>	* found in the documentation for the {@link #checkedCollection
2870	>	* checkedCollection} method.
2871		*
2872		* <p>The returned map will be serializable if the specified map is
2873		* serializable.
2874		*
2875	+	* <p>Since {@code null} is considered to be a value of any reference
2876	+	* type, the returned map permits insertion of null keys or values
2877	+	* whenever the backing map does.
2878	+	*
2879		* @param m the map for which a dynamically typesafe view is to be
2880	<	* returned
2881	<	* @param keyType the type of key that <tt>m</tt> is permitted to hold
2882	<	* @param valueType the type of value that <tt>m</tt> is permitted to hold
2880	>	* returned
2881	>	* @param keyType the type of key that {@code m} is permitted to hold
2882	>	* @param valueType the type of value that {@code m} is permitted to hold
2883		* @return a dynamically typesafe view of the specified map
2884		* @since 1.5
2885		*/
#	Line 2849 \| Line 2910 \| public class Collections {
2910		public K lastKey() { return sm.lastKey(); }
2911
2912		public SortedMap<K,V> subMap(K fromKey, K toKey) {
2913	<	return new CheckedSortedMap<K,V>(sm.subMap(fromKey, toKey),
2914	<	keyType, valueType);
2913	>	return checkedSortedMap(sm.subMap(fromKey, toKey),
2914	>	keyType, valueType);
2915		}
2855	–
2916		public SortedMap<K,V> headMap(K toKey) {
2917	<	return new CheckedSortedMap<K,V>(sm.headMap(toKey),
2858	<	keyType, valueType);
2917	>	return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
2918		}
2860	–
2919		public SortedMap<K,V> tailMap(K fromKey) {
2920	<	return new CheckedSortedMap<K,V>(sm.tailMap(fromKey),
2863	<	keyType, valueType);
2920	>	return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
2921		}
2922		}
2923
2924	<	// Miscellaneous
2924	>	// Empty collections
2925	>
2926	>	/**
2927	>	* Returns an iterator that has no elements. More precisely,
2928	>	*
2929	>	* <ul compact>
2930	>	*
2931	>	* <li>{@link Iterator#hasNext hasNext} always returns {@code
2932	>	* false}.
2933	>	*
2934	>	* <li>{@link Iterator#next next} always throws {@link
2935	>	* NoSuchElementException}.
2936	>	*
2937	>	* <li>{@link Iterator#remove remove} always throws {@link
2938	>	* IllegalStateException}.
2939	>	*
2940	>	* </ul>
2941	>	*
2942	>	* <p>Implementations of this method are permitted, but not
2943	>	* required, to return the same object from multiple invocations.
2944	>	*
2945	>	* @return an empty iterator
2946	>	* @since 1.7
2947	>	*/
2948	>	@SuppressWarnings("unchecked")
2949	>	public static <T> Iterator<T> emptyIterator() {
2950	>	return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
2951	>	}
2952	>
2953	>	private static class EmptyIterator<E> implements Iterator<E> {
2954	>	static final EmptyIterator<Object> EMPTY_ITERATOR
2955	>	= new EmptyIterator<Object>();
2956	>
2957	>	public boolean hasNext() { return false; }
2958	>	public E next() { throw new NoSuchElementException(); }
2959	>	public void remove() { throw new IllegalStateException(); }
2960	>	}
2961	>
2962	>	/**
2963	>	* Returns a list iterator that has no elements. More precisely,
2964	>	*
2965	>	* <ul compact>
2966	>	*
2967	>	* <li>{@link Iterator#hasNext hasNext} and {@link
2968	>	* ListIterator#hasPrevious hasPrevious} always return {@code
2969	>	* false}.
2970	>	*
2971	>	* <li>{@link Iterator#next next} and {@link ListIterator#previous
2972	>	* previous} always throw {@link NoSuchElementException}.
2973	>	*
2974	>	* <li>{@link Iterator#remove remove} and {@link ListIterator#set
2975	>	* set} always throw {@link IllegalStateException}.
2976	>	*
2977	>	* <li>{@link ListIterator#add add} always throws {@link
2978	>	* UnsupportedOperationException}.
2979	>	*
2980	>	* <li>{@link ListIterator#nextIndex nextIndex} always returns
2981	>	* {@code 0} .
2982	>	*
2983	>	* <li>{@link ListIterator#previousIndex previousIndex} always
2984	>	* returns {@code -1}.
2985	>	*
2986	>	* </ul>
2987	>	*
2988	>	* <p>Implementations of this method are permitted, but not
2989	>	* required, to return the same object from multiple invocations.
2990	>	*
2991	>	* @return an empty list iterator
2992	>	* @since 1.7
2993	>	*/
2994	>	@SuppressWarnings("unchecked")
2995	>	public static <T> ListIterator<T> emptyListIterator() {
2996	>	return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
2997	>	}
2998	>
2999	>	private static class EmptyListIterator<E>
3000	>	extends EmptyIterator<E>
3001	>	implements ListIterator<E>
3002	>	{
3003	>	static final EmptyListIterator<Object> EMPTY_ITERATOR
3004	>	= new EmptyListIterator<Object>();
3005	>
3006	>	public boolean hasPrevious() { return false; }
3007	>	public E previous() { throw new NoSuchElementException(); }
3008	>	public int nextIndex() { return 0; }
3009	>	public int previousIndex() { return -1; }
3010	>	public void set(E e) { throw new IllegalStateException(); }
3011	>	public void add(E e) { throw new UnsupportedOperationException(); }
3012	>	}
3013	>
3014	>	/**
3015	>	* Returns an enumeration that has no elements. More precisely,
3016	>	*
3017	>	* <ul compact>
3018	>	*
3019	>	* <li>{@link Enumeration#hasMoreElements hasMoreElements} always
3020	>	* returns {@code false}.
3021	>	*
3022	>	* <li> {@link Enumeration#nextElement nextElement} always throws
3023	>	* {@link NoSuchElementException}.
3024	>	*
3025	>	* </ul>
3026	>	*
3027	>	* <p>Implementations of this method are permitted, but not
3028	>	* required, to return the same object from multiple invocations.
3029	>	*
3030	>	* @return an empty enumeration
3031	>	* @since 1.7
3032	>	*/
3033	>	@SuppressWarnings("unchecked")
3034	>	public static <T> Enumeration<T> emptyEnumeration() {
3035	>	return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
3036	>	}
3037	>
3038	>	private static class EmptyEnumeration<E> implements Enumeration<E> {
3039	>	static final EmptyEnumeration<Object> EMPTY_ENUMERATION
3040	>	= new EmptyEnumeration<Object>();
3041	>
3042	>	public boolean hasMoreElements() { return false; }
3043	>	public E nextElement() { throw new NoSuchElementException(); }
3044	>	}
3045
3046		/**
3047		* The empty set (immutable). This set is serializable.
3048		*
3049		* @see #emptySet()
3050		*/
3051	<	public static final Set EMPTY_SET = new EmptySet();
3051	>	@SuppressWarnings("unchecked")
3052	>	public static final Set EMPTY_SET = new EmptySet<Object>();
3053
3054		/**
3055		* Returns the empty set (immutable). This set is serializable.
#	Line 2889 \| Line 3067 \| public class Collections {
3067		* @see #EMPTY_SET
3068		* @since 1.5
3069		*/
3070	+	@SuppressWarnings("unchecked")
3071		public static final <T> Set<T> emptySet() {
3072	<	return (Set<T>) EMPTY_SET;
3072	>	return (Set<T>) EMPTY_SET;
3073		}
3074
3075		/**
3076		* @serial include
3077		*/
3078	<	private static class EmptySet extends AbstractSet<Object> implements Serializable {
3079	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3080	<	private static final long serialVersionUID = 1582296315990362920L;
3078	>	private static class EmptySet<E>
3079	>	extends AbstractSet<E>
3080	>	implements Serializable
3081	>	{
3082	>	private static final long serialVersionUID = 1582296315990362920L;
3083
3084	<	public Iterator<Object> iterator() {
2904	<	return new Iterator<Object>() {
2905	<	public boolean hasNext() {
2906	<	return false;
2907	<	}
2908	<	public Object next() {
2909	<	throw new NoSuchElementException();
2910	<	}
2911	<	public void remove() {
2912	<	throw new UnsupportedOperationException();
2913	<	}
2914	<	};
2915	<	}
3084	>	public Iterator<E> iterator() { return emptyIterator(); }
3085
3086		public int size() {return 0;}
3087	+	public boolean isEmpty() {return true;}
3088
3089		public boolean contains(Object obj) {return false;}
3090	+	public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3091	+
3092	+	public Object[] toArray() { return new Object[0]; }
3093	+
3094	+	public <T> T[] toArray(T[] a) {
3095	+	if (a.length > 0)
3096	+	a[0] = null;
3097	+	return a;
3098	+	}
3099
3100		// Preserves singleton property
3101		private Object readResolve() {
#	Line 2929 \| Line 3108 \| public class Collections {
3108		*
3109		* @see #emptyList()
3110		*/
3111	<	public static final List EMPTY_LIST = new EmptyList();
3111	>	@SuppressWarnings("unchecked")
3112	>	public static final List EMPTY_LIST = new EmptyList<Object>();
3113
3114		/**
3115		* Returns the empty list (immutable). This list is serializable.
#	Line 2946 \| Line 3126 \| public class Collections {
3126		* @see #EMPTY_LIST
3127		* @since 1.5
3128		*/
3129	+	@SuppressWarnings("unchecked")
3130		public static final <T> List<T> emptyList() {
3131	<	return (List<T>) EMPTY_LIST;
3131	>	return (List<T>) EMPTY_LIST;
3132		}
3133
3134		/**
3135		* @serial include
3136		*/
3137	<	private static class EmptyList
3138	<	extends AbstractList<Object>
3139	<	implements RandomAccess, Serializable {
3140	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3141	<	private static final long serialVersionUID = 8842843931221139166L;
3137	>	private static class EmptyList<E>
3138	>	extends AbstractList<E>
3139	>	implements RandomAccess, Serializable {
3140	>	private static final long serialVersionUID = 8842843931221139166L;
3141	>
3142	>	public Iterator<E> iterator() {
3143	>	return emptyIterator();
3144	>	}
3145	>	public ListIterator<E> listIterator() {
3146	>	return emptyListIterator();
3147	>	}
3148
3149		public int size() {return 0;}
3150	+	public boolean isEmpty() {return true;}
3151
3152		public boolean contains(Object obj) {return false;}
3153	+	public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3154	+
3155	+	public Object[] toArray() { return new Object[0]; }
3156	+
3157	+	public <T> T[] toArray(T[] a) {
3158	+	if (a.length > 0)
3159	+	a[0] = null;
3160	+	return a;
3161	+	}
3162
3163	<	public Object get(int index) {
3163	>	public E get(int index) {
3164		throw new IndexOutOfBoundsException("Index: "+index);
3165		}
3166
3167	+	public boolean equals(Object o) {
3168	+	return (o instanceof List) && ((List<?>)o).isEmpty();
3169	+	}
3170	+
3171	+	public int hashCode() { return 1; }
3172	+
3173		// Preserves singleton property
3174		private Object readResolve() {
3175		return EMPTY_LIST;
#	Line 2979 \| Line 3182 \| public class Collections {
3182		* @see #emptyMap()
3183		* @since 1.3
3184		*/
3185	<	public static final Map EMPTY_MAP = new EmptyMap();
3185	>	@SuppressWarnings("unchecked")
3186	>	public static final Map EMPTY_MAP = new EmptyMap<Object,Object>();
3187
3188		/**
3189		* Returns the empty map (immutable). This map is serializable.
#	Line 2996 \| Line 3200 \| public class Collections {
3200		* @see #EMPTY_MAP
3201		* @since 1.5
3202		*/
3203	+	@SuppressWarnings("unchecked")
3204		public static final <K,V> Map<K,V> emptyMap() {
3205	<	return (Map<K,V>) EMPTY_MAP;
3205	>	return (Map<K,V>) EMPTY_MAP;
3206		}
3207
3208	<	private static class EmptyMap
3209	<	extends AbstractMap<Object,Object>
3210	<	implements Serializable {
3211	<
3208	>	/**
3209	>	* @serial include
3210	>	*/
3211	>	private static class EmptyMap<K,V>
3212	>	extends AbstractMap<K,V>
3213	>	implements Serializable
3214	>	{
3215		private static final long serialVersionUID = 6428348081105594320L;
3216
3217		public int size() {return 0;}
3010	–
3218		public boolean isEmpty() {return true;}
3012	–
3219		public boolean containsKey(Object key) {return false;}
3014	–
3220		public boolean containsValue(Object value) {return false;}
3221	<
3222	<	public Object get(Object key) {return null;}
3223	<
3224	<	public Set<Object> keySet() {return Collections.<Object>emptySet();}
3020	<
3021	<	public Collection<Object> values() {return Collections.<Object>emptySet();}
3022	<
3023	<	public Set<Map.Entry<Object,Object>> entrySet() {
3024	<	return Collections.emptySet();
3025	<	}
3221	>	public V get(Object key) {return null;}
3222	>	public Set<K> keySet() {return emptySet();}
3223	>	public Collection<V> values() {return emptySet();}
3224	>	public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
3225
3226		public boolean equals(Object o) {
3227	<	return (o instanceof Map) && ((Map)o).size()==0;
3227	>	return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
3228		}
3229
3230		public int hashCode() {return 0;}
#	Line 3036 \| Line 3235 \| public class Collections {
3235		}
3236		}
3237
3238	+	// Singleton collections
3239	+
3240		/**
3241		* Returns an immutable set containing only the specified object.
3242		* The returned set is serializable.
#	Line 3044 \| Line 3245 \| public class Collections {
3245		* @return an immutable set containing only the specified object.
3246		*/
3247		public static <T> Set<T> singleton(T o) {
3248	<	return new SingletonSet<T>(o);
3248	>	return new SingletonSet<T>(o);
3249	>	}
3250	>
3251	>	static <E> Iterator<E> singletonIterator(final E e) {
3252	>	return new Iterator<E>() {
3253	>	private boolean hasNext = true;
3254	>	public boolean hasNext() {
3255	>	return hasNext;
3256	>	}
3257	>	public E next() {
3258	>	if (hasNext) {
3259	>	hasNext = false;
3260	>	return e;
3261	>	}
3262	>	throw new NoSuchElementException();
3263	>	}
3264	>	public void remove() {
3265	>	throw new UnsupportedOperationException();
3266	>	}
3267	>	};
3268		}
3269
3270		/**
3271		* @serial include
3272		*/
3273		private static class SingletonSet<E>
3274	<	extends AbstractSet<E>
3275	<	implements Serializable
3274	>	extends AbstractSet<E>
3275	>	implements Serializable
3276		{
3277	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3058	<	private static final long serialVersionUID = 3193687207550431679L;
3277	>	private static final long serialVersionUID = 3193687207550431679L;
3278
3279		final private E element;
3280
3281		SingletonSet(E e) {element = e;}
3282
3283		public Iterator<E> iterator() {
3284	<	return new Iterator<E>() {
3066	<	private boolean hasNext = true;
3067	<	public boolean hasNext() {
3068	<	return hasNext;
3069	<	}
3070	<	public E next() {
3071	<	if (hasNext) {
3072	<	hasNext = false;
3073	<	return element;
3074	<	}
3075	<	throw new NoSuchElementException();
3076	<	}
3077	<	public void remove() {
3078	<	throw new UnsupportedOperationException();
3079	<	}
3080	<	};
3284	>	return singletonIterator(element);
3285		}
3286
3287		public int size() {return 1;}
#	Line 3094 \| Line 3298 \| public class Collections {
3298		* @since 1.3
3299		*/
3300		public static <T> List<T> singletonList(T o) {
3301	<	return new SingletonList<T>(o);
3301	>	return new SingletonList<T>(o);
3302		}
3303
3304	+	/**
3305	+	* @serial include
3306	+	*/
3307		private static class SingletonList<E>
3308	<	extends AbstractList<E>
3309	<	implements RandomAccess, Serializable {
3308	>	extends AbstractList<E>
3309	>	implements RandomAccess, Serializable {
3310
3311	<	static final long serialVersionUID = 3093736618740652951L;
3311	>	private static final long serialVersionUID = 3093736618740652951L;
3312
3313		private final E element;
3314
3315		SingletonList(E obj) {element = obj;}
3316
3317	+	public Iterator<E> iterator() {
3318	+	return singletonIterator(element);
3319	+	}
3320	+
3321		public int size() {return 1;}
3322
3323		public boolean contains(Object obj) {return eq(obj, element);}
#	Line 3129 \| Line 3340 \| public class Collections {
3340		* @since 1.3
3341		*/
3342		public static <K,V> Map<K,V> singletonMap(K key, V value) {
3343	<	return new SingletonMap<K,V>(key, value);
3343	>	return new SingletonMap<K,V>(key, value);
3344		}
3345
3346	+	/**
3347	+	* @serial include
3348	+	*/
3349		private static class SingletonMap<K,V>
3350	<	extends AbstractMap<K,V>
3351	<	implements Serializable {
3352	<	private static final long serialVersionUID = -6979724477215052911L;
3350	>	extends AbstractMap<K,V>
3351	>	implements Serializable {
3352	>	private static final long serialVersionUID = -6979724477215052911L;
3353
3354		private final K k;
3355	<	private final V v;
3355	>	private final V v;
3356
3357		SingletonMap(K key, V value) {
3358		k = key;
#	Line 3159 \| Line 3373 \| public class Collections {
3373		private transient Set<Map.Entry<K,V>> entrySet = null;
3374		private transient Collection<V> values = null;
3375
3376	<	public Set<K> keySet() {
3377	<	if (keySet==null)
3378	<	keySet = singleton(k);
3379	<	return keySet;
3380	<	}
3381	<
3382	<	public Set<Map.Entry<K,V>> entrySet() {
3383	<	if (entrySet==null)
3384	<	entrySet = Collections.<Map.Entry<K,V>>singleton(
3385	<	new SimpleImmutableEntry<K,V>(k, v));
3386	<	return entrySet;
3387	<	}
3388	<
3389	<	public Collection<V> values() {
3390	<	if (values==null)
3391	<	values = singleton(v);
3392	<	return values;
3393	<	}
3376	>	public Set<K> keySet() {
3377	>	if (keySet==null)
3378	>	keySet = singleton(k);
3379	>	return keySet;
3380	>	}
3381	>
3382	>	public Set<Map.Entry<K,V>> entrySet() {
3383	>	if (entrySet==null)
3384	>	entrySet = Collections.<Map.Entry<K,V>>singleton(
3385	>	new SimpleImmutableEntry<K,V>(k, v));
3386	>	return entrySet;
3387	>	}
3388	>
3389	>	public Collection<V> values() {
3390	>	if (values==null)
3391	>	values = singleton(v);
3392	>	return values;
3393	>	}
3394
3395		}
3396
3397	+	// Miscellaneous
3398	+
3399		/**
3400		* Returns an immutable list consisting of <tt>n</tt> copies of the
3401		* specified object. The newly allocated data object is tiny (it contains
#	Line 3190 \| Line 3406 \| public class Collections {
3406		* @param n the number of elements in the returned list.
3407		* @param o the element to appear repeatedly in the returned list.
3408		* @return an immutable list consisting of <tt>n</tt> copies of the
3409	<	* specified object.
3409	>	* specified object.
3410		* @throws IllegalArgumentException if n < 0.
3411		* @see List#addAll(Collection)
3412		* @see List#addAll(int, Collection)
3413		*/
3414		public static <T> List<T> nCopies(int n, T o) {
3415	<	if (n < 0)
3416	<	throw new IllegalArgumentException("List length = " + n);
3415	>	if (n < 0)
3416	>	throw new IllegalArgumentException("List length = " + n);
3417		return new CopiesList<T>(n, o);
3418		}
3419
#	Line 3205 \| Line 3421 \| public class Collections {
3421		* @serial include
3422		*/
3423		private static class CopiesList<E>
3424	<	extends AbstractList<E>
3425	<	implements RandomAccess, Serializable
3424	>	extends AbstractList<E>
3425	>	implements RandomAccess, Serializable
3426		{
3427	<	static final long serialVersionUID = 2739099268398711800L;
3427	>	private static final long serialVersionUID = 2739099268398711800L;
3428
3429		final int n;
3430		final E element;
3431
3432		CopiesList(int n, E e) {
3433	<	assert n >= 0;
3433	>	assert n >= 0;
3434		this.n = n;
3435		element = e;
3436		}
#	Line 3227 \| Line 3443 \| public class Collections {
3443		return n != 0 && eq(obj, element);
3444		}
3445
3446	<	public int indexOf(Object o) {
3447	<	return contains(o) ? 0 : -1;
3448	<	}
3449	<
3450	<	public int lastIndexOf(Object o) {
3451	<	return contains(o) ? n - 1 : -1;
3452	<	}
3446	>	public int indexOf(Object o) {
3447	>	return contains(o) ? 0 : -1;
3448	>	}
3449	>
3450	>	public int lastIndexOf(Object o) {
3451	>	return contains(o) ? n - 1 : -1;
3452	>	}
3453
3454		public E get(int index) {
3455		if (index < 0 \|\| index >= n)
#	Line 3242 \| Line 3458 \| public class Collections {
3458		return element;
3459		}
3460
3461	<	public Object[] toArray() {
3462	<	final Object[] a = new Object[n];
3463	<	if (element != null)
3464	<	Arrays.fill(a, 0, n, element);
3465	<	return a;
3466	<	}
3467	<
3468	<	public <T> T[] toArray(T[] a) {
3469	<	final int n = this.n;
3470	<	if (a.length < n) {
3471	<	a = (T[])java.lang.reflect.Array
3472	<	.newInstance(a.getClass().getComponentType(), n);
3473	<	if (element != null)
3474	<	Arrays.fill(a, 0, n, element);
3475	<	} else {
3476	<	Arrays.fill(a, 0, n, element);
3477	<	if (a.length > n)
3478	<	a[n] = null;
3479	<	}
3480	<	return a;
3481	<	}
3482	<
3483	<	public List<E> subList(int fromIndex, int toIndex) {
3484	<	if (fromIndex < 0)
3485	<	throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3486	<	if (toIndex > n)
3487	<	throw new IndexOutOfBoundsException("toIndex = " + toIndex);
3488	<	if (fromIndex > toIndex)
3489	<	throw new IllegalArgumentException("fromIndex(" + fromIndex +
3490	<	") > toIndex(" + toIndex + ")");
3491	<	return new CopiesList(toIndex - fromIndex, element);
3492	<	}
3461	>	public Object[] toArray() {
3462	>	final Object[] a = new Object[n];
3463	>	if (element != null)
3464	>	Arrays.fill(a, 0, n, element);
3465	>	return a;
3466	>	}
3467	>
3468	>	public <T> T[] toArray(T[] a) {
3469	>	final int n = this.n;
3470	>	if (a.length < n) {
3471	>	a = (T[])java.lang.reflect.Array
3472	>	.newInstance(a.getClass().getComponentType(), n);
3473	>	if (element != null)
3474	>	Arrays.fill(a, 0, n, element);
3475	>	} else {
3476	>	Arrays.fill(a, 0, n, element);
3477	>	if (a.length > n)
3478	>	a[n] = null;
3479	>	}
3480	>	return a;
3481	>	}
3482	>
3483	>	public List<E> subList(int fromIndex, int toIndex) {
3484	>	if (fromIndex < 0)
3485	>	throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3486	>	if (toIndex > n)
3487	>	throw new IndexOutOfBoundsException("toIndex = " + toIndex);
3488	>	if (fromIndex > toIndex)
3489	>	throw new IllegalArgumentException("fromIndex(" + fromIndex +
3490	>	") > toIndex(" + toIndex + ")");
3491	>	return new CopiesList<E>(toIndex - fromIndex, element);
3492	>	}
3493		}
3494
3495		/**
#	Line 3285 \| Line 3501 \| public class Collections {
3501		* objects that implement the <tt>Comparable</tt> interface in
3502		* reverse-natural-order. For example, suppose a is an array of
3503		* strings. Then: <pre>
3504	<	* Arrays.sort(a, Collections.reverseOrder());
3504	>	* Arrays.sort(a, Collections.reverseOrder());
3505		* </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
3506		*
3507		* The returned comparator is serializable.
3508		*
3509		* @return a comparator that imposes the reverse of the <i>natural
3510	<	* ordering</i> on a collection of objects that implement
3511	<	* the <tt>Comparable</tt> interface.
3510	>	* ordering</i> on a collection of objects that implement
3511	>	* the <tt>Comparable</tt> interface.
3512		* @see Comparable
3513		*/
3514		public static <T> Comparator<T> reverseOrder() {
3515	<	return (Comparator<T>) REVERSE_ORDER;
3515	>	return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3516		}
3517
3302	–	private static final Comparator REVERSE_ORDER = new ReverseComparator();
3303	–
3518		/**
3519		* @serial include
3520		*/
3521	<	private static class ReverseComparator<T>
3522	<	implements Comparator<Comparable<Object>>, Serializable {
3521	>	private static class ReverseComparator
3522	>	implements Comparator<Comparable<Object>>, Serializable {
3523	>
3524	>	private static final long serialVersionUID = 7207038068494060240L;
3525
3526	<	// use serialVersionUID from JDK 1.2.2 for interoperability
3527	<	private static final long serialVersionUID = 7207038068494060240L;
3526	>	static final ReverseComparator REVERSE_ORDER
3527	>	= new ReverseComparator();
3528
3529		public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3530		return c2.compareTo(c1);
3531		}
3532	+
3533	+	private Object readResolve() { return reverseOrder(); }
3534		}
3535
3536		/**
#	Line 3326 \| Line 3544 \| public class Collections {
3544		* comparator is also serializable or null).
3545		*
3546		* @return a comparator that imposes the reverse ordering of the
3547	<	* specified comparator.
3547	>	* specified comparator
3548		* @since 1.5
3549		*/
3550		public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3551		if (cmp == null)
3552	<	return new ReverseComparator(); // Unchecked warning!!
3552	>	return reverseOrder();
3553	>
3554	>	if (cmp instanceof ReverseComparator2)
3555	>	return ((ReverseComparator2<T>)cmp).cmp;
3556
3557		return new ReverseComparator2<T>(cmp);
3558		}
#	Line 3351 \| Line 3572 \| public class Collections {
3572		*
3573		* @serial
3574		*/
3575	<	private Comparator<T> cmp;
3575	>	final Comparator<T> cmp;
3576
3577		ReverseComparator2(Comparator<T> cmp) {
3578		assert cmp != null;
#	Line 3361 \| Line 3582 \| public class Collections {
3582		public int compare(T t1, T t2) {
3583		return cmp.compare(t2, t1);
3584		}
3585	+
3586	+	public boolean equals(Object o) {
3587	+	return (o == this) \|\|
3588	+	(o instanceof ReverseComparator2 &&
3589	+	cmp.equals(((ReverseComparator2)o).cmp));
3590	+	}
3591	+
3592	+	public int hashCode() {
3593	+	return cmp.hashCode() ^ Integer.MIN_VALUE;
3594	+	}
3595		}
3596
3597		/**
#	Line 3373 \| Line 3604 \| public class Collections {
3604		* @see Enumeration
3605		*/
3606		public static <T> Enumeration<T> enumeration(final Collection<T> c) {
3607	<	return new Enumeration<T>() {
3608	<	Iterator<T> i = c.iterator();
3607	>	return new Enumeration<T>() {
3608	>	private final Iterator<T> i = c.iterator();
3609
3610	<	public boolean hasMoreElements() {
3611	<	return i.hasNext();
3612	<	}
3613	<
3614	<	public T nextElement() {
3615	<	return i.next();
3616	<	}
3610	>	public boolean hasMoreElements() {
3611	>	return i.hasNext();
3612	>	}
3613	>
3614	>	public T nextElement() {
3615	>	return i.next();
3616	>	}
3617		};
3618		}
3619
#	Line 3411 \| Line 3642 \| public class Collections {
3642		/**
3643		* Returns true if the specified arguments are equal, or both null.
3644		*/
3645	<	private static boolean eq(Object o1, Object o2) {
3646	<	return (o1==null ? o2==null : o1.equals(o2));
3645	>	static boolean eq(Object o1, Object o2) {
3646	>	return o1==null ? o2==null : o1.equals(o2);
3647		}
3648
3649		/**
#	Line 3498 \| Line 3729 \| public class Collections {
3729		* </pre>
3730		*
3731		* @param c the collection into which <tt>elements</tt> are to be inserted
3732	<	* @param a the elements to insert into <tt>c</tt>
3732	>	* @param elements the elements to insert into <tt>c</tt>
3733		* @return <tt>true</tt> if the collection changed as a result of the call
3734		* @throws UnsupportedOperationException if <tt>c</tt> does not support
3735	<	* the <tt>add</tt> operation.
3735	>	* the <tt>add</tt> operation
3736		* @throws NullPointerException if <tt>elements</tt> contains one or more
3737		* null values and <tt>c</tt> does not permit null elements, or
3738		* if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
#	Line 3510 \| Line 3741 \| public class Collections {
3741		* @see Collection#addAll(Collection)
3742		* @since 1.5
3743		*/
3744	<	public static <T> boolean addAll(Collection<? super T> c, T... a) {
3744	>	public static <T> boolean addAll(Collection<? super T> c, T... elements) {
3745		boolean result = false;
3746	<	for (T e : a)
3747	<	result \|= c.add(e);
3746	>	for (T element : elements)
3747	>	result \|= c.add(element);
3748		return result;
3749		}
3750
#	Line 3550 \| Line 3781 \| public class Collections {
3781		return new SetFromMap<E>(map);
3782		}
3783
3784	+	/**
3785	+	* @serial include
3786	+	*/
3787		private static class SetFromMap<E> extends AbstractSet<E>
3788		implements Set<E>, Serializable
3789		{
3790		private final Map<E, Boolean> m; // The backing map
3791	<	private transient Set<E> keySet; // Its keySet
3791	>	private transient Set<E> s; // Its keySet
3792
3793		SetFromMap(Map<E, Boolean> map) {
3794		if (!map.isEmpty())
3795		throw new IllegalArgumentException("Map is non-empty");
3796		m = map;
3797	<	keySet = map.keySet();
3797	>	s = map.keySet();
3798		}
3799
3800	+	public void clear() { m.clear(); }
3801		public int size() { return m.size(); }
3802		public boolean isEmpty() { return m.isEmpty(); }
3803		public boolean contains(Object o) { return m.containsKey(o); }
3569	–	public Iterator<E> iterator() { return keySet.iterator(); }
3570	–	public Object[] toArray() { return keySet.toArray(); }
3571	–	public <T> T[] toArray(T[] a) { return keySet.toArray(a); }
3572	–	public boolean add(E e) {
3573	–	return m.put(e, Boolean.TRUE) == null;
3574	–	}
3804		public boolean remove(Object o) { return m.remove(o) != null; }
3805	<
3806	<	public boolean removeAll(Collection<?> c) {
3807	<	return keySet.removeAll(c);
3808	<	}
3809	<	public boolean retainAll(Collection<?> c) {
3810	<	return keySet.retainAll(c);
3811	<	}
3812	<	public void clear() { m.clear(); }
3813	<	public boolean equals(Object o) { return keySet.equals(o); }
3814	<	public int hashCode() { return keySet.hashCode(); }
3805	>	public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3806	>	public Iterator<E> iterator() { return s.iterator(); }
3807	>	public Object[] toArray() { return s.toArray(); }
3808	>	public <T> T[] toArray(T[] a) { return s.toArray(a); }
3809	>	public String toString() { return s.toString(); }
3810	>	public int hashCode() { return s.hashCode(); }
3811	>	public boolean equals(Object o) { return o == this \|\| s.equals(o); }
3812	>	public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3813	>	public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
3814	>	public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
3815	>	// addAll is the only inherited implementation
3816
3817		private static final long serialVersionUID = 2454657854757543876L;
3818
3819	<	private void readObject(java.io.ObjectInputStream s)
3819	>	private void readObject(java.io.ObjectInputStream stream)
3820		throws IOException, ClassNotFoundException
3821		{
3822	<	s.defaultReadObject();
3823	<	keySet = m.keySet();
3822	>	stream.defaultReadObject();
3823	>	s = m.keySet();
3824		}
3825		}
3826
#	Line 3601 \| Line 3831 \| public class Collections {
3831		* view can be useful when you would like to use a method
3832		* requiring a <tt>Queue</tt> but you need Lifo ordering.
3833		*
3834	+	* <p>Each method invocation on the queue returned by this method
3835	+	* results in exactly one method invocation on the backing deque, with
3836	+	* one exception. The {@link Queue#addAll addAll} method is
3837	+	* implemented as a sequence of {@link Deque#addFirst addFirst}
3838	+	* invocations on the backing deque.
3839	+	*
3840		* @param deque the deque
3841		* @return the queue
3842		* @since 1.6
#	Line 3609 \| Line 3845 \| public class Collections {
3845		return new AsLIFOQueue<T>(deque);
3846		}
3847
3848	+	/**
3849	+	* @serial include
3850	+	*/
3851		static class AsLIFOQueue<E> extends AbstractQueue<E>
3852		implements Queue<E>, Serializable {
3853	<	private static final long serialVersionUID = 1802017725587941708L;
3853	>	private static final long serialVersionUID = 1802017725587941708L;
3854		private final Deque<E> q;
3855	<	AsLIFOQueue(Deque<E> q) { this.q = q; }
3856	<	public boolean offer(E e) { return q.offerFirst(e); }
3857	<	public E poll() { return q.pollFirst(); }
3858	<	public E remove() { return q.removeFirst(); }
3859	<	public E peek() { return q.peekFirst(); }
3860	<	public E element() { return q.getFirst(); }
3861	<	public int size() { return q.size(); }
3862	<	public boolean isEmpty() { return q.isEmpty(); }
3863	<	public boolean contains(Object o) { return q.contains(o); }
3864	<	public Iterator<E> iterator() { return q.iterator(); }
3865	<	public Object[] toArray() { return q.toArray(); }
3866	<	public <T> T[] toArray(T[] a) { return q.toArray(a); }
3867	<	public boolean add(E e) { return q.offerFirst(e); }
3868	<	public boolean remove(Object o) { return q.remove(o); }
3869	<	public void clear() { q.clear(); }
3855	>	AsLIFOQueue(Deque<E> q) { this.q = q; }
3856	>	public boolean add(E e) { q.addFirst(e); return true; }
3857	>	public boolean offer(E e) { return q.offerFirst(e); }
3858	>	public E poll() { return q.pollFirst(); }
3859	>	public E remove() { return q.removeFirst(); }
3860	>	public E peek() { return q.peekFirst(); }
3861	>	public E element() { return q.getFirst(); }
3862	>	public void clear() { q.clear(); }
3863	>	public int size() { return q.size(); }
3864	>	public boolean isEmpty() { return q.isEmpty(); }
3865	>	public boolean contains(Object o) { return q.contains(o); }
3866	>	public boolean remove(Object o) { return q.remove(o); }
3867	>	public Iterator<E> iterator() { return q.iterator(); }
3868	>	public Object[] toArray() { return q.toArray(); }
3869	>	public <T> T[] toArray(T[] a) { return q.toArray(a); }
3870	>	public String toString() { return q.toString(); }
3871	>	public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3872	>	public boolean removeAll(Collection<?> c) {return q.removeAll(c);}
3873	>	public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
3874	>	// We use inherited addAll; forwarding addAll would be wrong
3875		}
3876		}

Diff Legend

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

Comparing jsr166/src/main/java/util/Collections.java (file contents): Revision 1.17 by jsr166, Sat Sep 10 19:49:05 2005 UTC vs. Revision 1.34 by jsr166, Sun May 18 23:59:57 2008 UTC

Diff Legend

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.17 by jsr166, Sat Sep 10 19:49:05 2005 UTC vs.
Revision 1.34 by jsr166, Sun May 18 23:59:57 2008 UTC