| Collections.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9 import java.io.Serializable;
10 import java.io.ObjectOutputStream;
11 import java.io.IOException;
12 import java.lang.reflect.Array;
13
14 /**
15 * This class consists exclusively of static methods that operate on or return
16 * collections. It contains polymorphic algorithms that operate on
17 * collections, "wrappers", which return a new collection backed by a
18 * specified collection, and a few other odds and ends.
19 *
20 * <p>The methods of this class all throw a <tt>NullPointerException</tt>
21 * if the collections or class objects provided to them are null.
22 *
23 * <p>The documentation for the polymorphic algorithms contained in this class
24 * generally includes a brief description of the <i>implementation</i>. Such
25 * descriptions should be regarded as <i>implementation notes</i>, rather than
26 * parts of the <i>specification</i>. Implementors should feel free to
27 * substitute other algorithms, so long as the specification itself is adhered
28 * to. (For example, the algorithm used by <tt>sort</tt> does not have to be
29 * a mergesort, but it does have to be <i>stable</i>.)
30 *
31 * <p>The "destructive" algorithms contained in this class, that is, the
32 * algorithms that modify the collection on which they operate, are specified
33 * to throw <tt>UnsupportedOperationException</tt> if the collection does not
34 * support the appropriate mutation primitive(s), such as the <tt>set</tt>
35 * method. These algorithms may, but are not required to, throw this
36 * exception if an invocation would have no effect on the collection. For
37 * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
38 * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
39 *
40 * <p>This class is a member of the
41 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
42 * Java Collections Framework</a>.
43 *
44 * @author Josh Bloch
45 * @author Neal Gafter
46 * @version %I%, %G%
47 * @see Collection
48 * @see Set
49 * @see List
50 * @see Map
51 * @since 1.2
52 */
53
54 public class Collections {
55 // Suppresses default constructor, ensuring non-instantiability.
56 private Collections() {
57 }
58
59 // Algorithms
60
61 /*
62 * Tuning parameters for algorithms - Many of the List algorithms have
63 * two implementations, one of which is appropriate for RandomAccess
64 * lists, the other for "sequential." Often, the random access variant
65 * yields better performance on small sequential access lists. The
66 * tuning parameters below determine the cutoff point for what constitutes
67 * a "small" sequential access list for each algorithm. The values below
68 * were empirically determined to work well for LinkedList. Hopefully
69 * they should be reasonable for other sequential access List
70 * implementations. Those doing performance work on this code would
71 * do well to validate the values of these parameters from time to time.
72 * (The first word of each tuning parameter name is the algorithm to which
73 * it applies.)
74 */
75 private static final int BINARYSEARCH_THRESHOLD = 5000;
76 private static final int REVERSE_THRESHOLD = 18;
77 private static final int SHUFFLE_THRESHOLD = 5;
78 private static final int FILL_THRESHOLD = 25;
79 private static final int ROTATE_THRESHOLD = 100;
80 private static final int COPY_THRESHOLD = 10;
81 private static final int REPLACEALL_THRESHOLD = 11;
82 private static final int INDEXOFSUBLIST_THRESHOLD = 35;
83
84 /**
85 * Sorts the specified list into ascending order, according to the
86 * <i>natural ordering</i> of its elements. All elements in the list must
87 * implement the <tt>Comparable</tt> interface. Furthermore, all elements
88 * in the list must be <i>mutually comparable</i> (that is,
89 * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
90 * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
91 *
92 * This sort is guaranteed to be <i>stable</i>: equal elements will
93 * not be reordered as a result of the sort.<p>
94 *
95 * The specified list must be modifiable, but need not be resizable.<p>
96 *
97 * The sorting algorithm is a modified mergesort (in which the merge is
98 * omitted if the highest element in the low sublist is less than the
99 * lowest element in the high sublist). This algorithm offers guaranteed
100 * n log(n) performance.
101 *
102 * This implementation dumps the specified list into an array, sorts
103 * the array, and iterates over the list resetting each element
104 * from the corresponding position in the array. This avoids the
105 * n<sup>2</sup> log(n) performance that would result from attempting
106 * to sort a linked list in place.
107 *
108 * @param list the list to be sorted.
109 * @throws ClassCastException if the list contains elements that are not
110 * <i>mutually comparable</i> (for example, strings and integers).
111 * @throws UnsupportedOperationException if the specified list's
112 * list-iterator does not support the <tt>set</tt> operation.
113 * @see Comparable
114 */
115 public static <T extends Comparable<? super T>> void sort(List<T> list) {
116 Object[] a = list.toArray();
117 Arrays.sort(a);
118 ListIterator<T> i = list.listIterator();
119 for (int j=0; j<a.length; j++) {
120 i.next();
121 i.set((T)a[j]);
122 }
123 }
124
125 /**
126 * Sorts the specified list according to the order induced by the
127 * specified comparator. All elements in the list must be <i>mutually
128 * comparable</i> using the specified comparator (that is,
129 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
130 * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
131 *
132 * This sort is guaranteed to be <i>stable</i>: equal elements will
133 * not be reordered as a result of the sort.<p>
134 *
135 * The sorting algorithm is a modified mergesort (in which the merge is
136 * omitted if the highest element in the low sublist is less than the
137 * lowest element in the high sublist). This algorithm offers guaranteed
138 * n log(n) performance.
139 *
140 * The specified list must be modifiable, but need not be resizable.
141 * This implementation dumps the specified list into an array, sorts
142 * the array, and iterates over the list resetting each element
143 * from the corresponding position in the array. This avoids the
144 * n<sup>2</sup> log(n) performance that would result from attempting
145 * to sort a linked list in place.
146 *
147 * @param list the list to be sorted.
148 * @param c the comparator to determine the order of the list. A
149 * <tt>null</tt> value indicates that the elements' <i>natural
150 * ordering</i> should be used.
151 * @throws ClassCastException if the list contains elements that are not
152 * <i>mutually comparable</i> using the specified comparator.
153 * @throws UnsupportedOperationException if the specified list's
154 * list-iterator does not support the <tt>set</tt> operation.
155 * @see Comparator
156 */
157 public static <T> void sort(List<T> list, Comparator<? super T> c) {
158 Object[] a = list.toArray();
159 Arrays.sort(a, (Comparator)c);
160 ListIterator i = list.listIterator();
161 for (int j=0; j<a.length; j++) {
162 i.next();
163 i.set(a[j]);
164 }
165 }
166
167
168 /**
169 * Searches the specified list for the specified object using the binary
170 * search algorithm. The list must be sorted into ascending order
171 * according to the {@linkplain Comparable natural ordering} of its
172 * elements (as by the {@link #sort(List)} method) prior to making this
173 * call. If it is not sorted, the results are undefined. If the list
174 * contains multiple elements equal to the specified object, there is no
175 * guarantee which one will be found.
176 *
177 * <p>This method runs in log(n) time for a "random access" list (which
178 * provides near-constant-time positional access). If the specified list
179 * does not implement the {@link RandomAccess} interface and is large,
180 * this method will do an iterator-based binary search that performs
181 * O(n) link traversals and O(log n) element comparisons.
182 *
183 * @param list the list to be searched.
184 * @param key the key to be searched for.
185 * @return the index of the search key, if it is contained in the list;
186 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
187 * <i>insertion point</i> is defined as the point at which the
188 * key would be inserted into the list: the index of the first
189 * element greater than the key, or <tt>list.size()</tt> if all
190 * elements in the list are less than the specified key. Note
191 * that this guarantees that the return value will be >= 0 if
192 * and only if the key is found.
193 * @throws ClassCastException if the list contains elements that are not
194 * <i>mutually comparable</i> (for example, strings and
195 * integers), or the search key is not mutually comparable
196 * with the elements of the list.
197 */
198 public static <T>
199 int binarySearch(List<? extends Comparable<? super T>> list, T key) {
200 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
201 return Collections.indexedBinarySearch(list, key);
202 else
203 return Collections.iteratorBinarySearch(list, key);
204 }
205
206 private static <T>
207 int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
208 {
209 int low = 0;
210 int high = list.size()-1;
211
212 while (low <= high) {
213 int mid = (low + high) >>> 1;
214 Comparable<? super T> midVal = list.get(mid);
215 int cmp = midVal.compareTo(key);
216
217 if (cmp < 0)
218 low = mid + 1;
219 else if (cmp > 0)
220 high = mid - 1;
221 else
222 return mid; // key found
223 }
224 return -(low + 1); // key not found
225 }
226
227 private static <T>
228 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
229 {
230 int low = 0;
231 int high = list.size()-1;
232 ListIterator<? extends Comparable<? super T>> i = list.listIterator();
233
234 while (low <= high) {
235 int mid = (low + high) >>> 1;
236 Comparable<? super T> midVal = get(i, mid);
237 int cmp = midVal.compareTo(key);
238
239 if (cmp < 0)
240 low = mid + 1;
241 else if (cmp > 0)
242 high = mid - 1;
243 else
244 return mid; // key found
245 }
246 return -(low + 1); // key not found
247 }
248
249 /**
250 * Gets the ith element from the given list by repositioning the specified
251 * list listIterator.
252 */
253 private static <T> T get(ListIterator<? extends T> i, int index) {
254 T obj = null;
255 int pos = i.nextIndex();
256 if (pos <= index) {
257 do {
258 obj = i.next();
259 } while (pos++ < index);
260 } else {
261 do {
262 obj = i.previous();
263 } while (--pos > index);
264 }
265 return obj;
266 }
267
268 /**
269 * Searches the specified list for the specified object using the binary
270 * search algorithm. The list must be sorted into ascending order
271 * according to the specified comparator (as by the
272 * {@link #sort(List, Comparator) sort(List, Comparator)}
273 * method), prior to making this call. If it is
274 * not sorted, the results are undefined. If the list contains multiple
275 * elements equal to the specified object, there is no guarantee which one
276 * will be found.
277 *
278 * <p>This method runs in log(n) time for a "random access" list (which
279 * provides near-constant-time positional access). If the specified list
280 * does not implement the {@link RandomAccess} interface and is large,
281 * this method will do an iterator-based binary search that performs
282 * O(n) link traversals and O(log n) element comparisons.
283 *
284 * @param list the list to be searched.
285 * @param key the key to be searched for.
286 * @param c the comparator by which the list is ordered.
287 * A <tt>null</tt> value indicates that the elements'
288 * {@linkplain Comparable natural ordering} should be used.
289 * @return the index of the search key, if it is contained in the list;
290 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
291 * <i>insertion point</i> is defined as the point at which the
292 * key would be inserted into the list: the index of the first
293 * element greater than the key, or <tt>list.size()</tt> if all
294 * elements in the list are less than the specified key. Note
295 * that this guarantees that the return value will be >= 0 if
296 * and only if the key is found.
297 * @throws ClassCastException if the list contains elements that are not
298 * <i>mutually comparable</i> using the specified comparator,
299 * or the search key is not mutually comparable with the
300 * elements of the list using this comparator.
301 */
302 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
303 if (c==null)
304 return binarySearch((List) list, key);
305
306 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
307 return Collections.indexedBinarySearch(list, key, c);
308 else
309 return Collections.iteratorBinarySearch(list, key, c);
310 }
311
312 private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
313 int low = 0;
314 int high = l.size()-1;
315
316 while (low <= high) {
317 int mid = (low + high) >>> 1;
318 T midVal = l.get(mid);
319 int cmp = c.compare(midVal, key);
320
321 if (cmp < 0)
322 low = mid + 1;
323 else if (cmp > 0)
324 high = mid - 1;
325 else
326 return mid; // key found
327 }
328 return -(low + 1); // key not found
329 }
330
331 private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
332 int low = 0;
333 int high = l.size()-1;
334 ListIterator<? extends T> i = l.listIterator();
335
336 while (low <= high) {
337 int mid = (low + high) >>> 1;
338 T midVal = get(i, mid);
339 int cmp = c.compare(midVal, key);
340
341 if (cmp < 0)
342 low = mid + 1;
343 else if (cmp > 0)
344 high = mid - 1;
345 else
346 return mid; // key found
347 }
348 return -(low + 1); // key not found
349 }
350
351 private interface SelfComparable extends Comparable<SelfComparable> {}
352
353
354 /**
355 * Reverses the order of the elements in the specified list.<p>
356 *
357 * This method runs in linear time.
358 *
359 * @param list the list whose elements are to be reversed.
360 * @throws UnsupportedOperationException if the specified list or
361 * its list-iterator does not support the <tt>set</tt> operation.
362 */
363 public static void reverse(List<?> list) {
364 int size = list.size();
365 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
366 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
367 swap(list, i, j);
368 } else {
369 ListIterator fwd = list.listIterator();
370 ListIterator rev = list.listIterator(size);
371 for (int i=0, mid=list.size()>>1; i<mid; i++) {
372 Object tmp = fwd.next();
373 fwd.set(rev.previous());
374 rev.set(tmp);
375 }
376 }
377 }
378
379 /**
380 * Randomly permutes the specified list using a default source of
381 * randomness. All permutations occur with approximately equal
382 * likelihood.<p>
383 *
384 * The hedge "approximately" is used in the foregoing description because
385 * default source of randomness is only approximately an unbiased source
386 * of independently chosen bits. If it were a perfect source of randomly
387 * chosen bits, then the algorithm would choose permutations with perfect
388 * uniformity.<p>
389 *
390 * This implementation traverses the list backwards, from the last element
391 * up to the second, repeatedly swapping a randomly selected element into
392 * the "current position". Elements are randomly selected from the
393 * portion of the list that runs from the first element to the current
394 * position, inclusive.<p>
395 *
396 * This method runs in linear time. If the specified list does not
397 * implement the {@link RandomAccess} interface and is large, this
398 * implementation dumps the specified list into an array before shuffling
399 * it, and dumps the shuffled array back into the list. This avoids the
400 * quadratic behavior that would result from shuffling a "sequential
401 * access" list in place.
402 *
403 * @param list the list to be shuffled.
404 * @throws UnsupportedOperationException if the specified list or
405 * its list-iterator does not support the <tt>set</tt> operation.
406 */
407 public static void shuffle(List<?> list) {
408 if (r == null) {
409 r = new Random();
410 }
411 shuffle(list, r);
412 }
413 private static Random r;
414
415 /**
416 * Randomly permute the specified list using the specified source of
417 * randomness. All permutations occur with equal likelihood
418 * assuming that the source of randomness is fair.<p>
419 *
420 * This implementation traverses the list backwards, from the last element
421 * up to the second, repeatedly swapping a randomly selected element into
422 * the "current position". Elements are randomly selected from the
423 * portion of the list that runs from the first element to the current
424 * position, inclusive.<p>
425 *
426 * This method runs in linear time. If the specified list does not
427 * implement the {@link RandomAccess} interface and is large, this
428 * implementation dumps the specified list into an array before shuffling
429 * it, and dumps the shuffled array back into the list. This avoids the
430 * quadratic behavior that would result from shuffling a "sequential
431 * access" list in place.
432 *
433 * @param list the list to be shuffled.
434 * @param rnd the source of randomness to use to shuffle the list.
435 * @throws UnsupportedOperationException if the specified list or its
436 * list-iterator does not support the <tt>set</tt> operation.
437 */
438 public static void shuffle(List<?> list, Random rnd) {
439 int size = list.size();
440 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
441 for (int i=size; i>1; i--)
442 swap(list, i-1, rnd.nextInt(i));
443 } else {
444 Object arr[] = list.toArray();
445
446 // Shuffle array
447 for (int i=size; i>1; i--)
448 swap(arr, i-1, rnd.nextInt(i));
449
450 // Dump array back into list
451 ListIterator it = list.listIterator();
452 for (int i=0; i<arr.length; i++) {
453 it.next();
454 it.set(arr[i]);
455 }
456 }
457 }
458
459 /**
460 * Swaps the elements at the specified positions in the specified list.
461 * (If the specified positions are equal, invoking this method leaves
462 * the list unchanged.)
463 *
464 * @param list The list in which to swap elements.
465 * @param i the index of one element to be swapped.
466 * @param j the index of the other element to be swapped.
467 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
468 * is out of range (i < 0 || i >= list.size()
469 * || j < 0 || j >= list.size()).
470 * @since 1.4
471 */
472 public static void swap(List<?> list, int i, int j) {
473 final List l = list;
474 l.set(i, l.set(j, l.get(i)));
475 }
476
477 /**
478 * Swaps the two specified elements in the specified array.
479 */
480 private static void swap(Object[] arr, int i, int j) {
481 Object tmp = arr[i];
482 arr[i] = arr[j];
483 arr[j] = tmp;
484 }
485
486 /**
487 * Replaces all of the elements of the specified list with the specified
488 * element. <p>
489 *
490 * This method runs in linear time.
491 *
492 * @param list the list to be filled with the specified element.
493 * @param obj The element with which to fill the specified list.
494 * @throws UnsupportedOperationException if the specified list or its
495 * list-iterator does not support the <tt>set</tt> operation.
496 */
497 public static <T> void fill(List<? super T> list, T obj) {
498 int size = list.size();
499
500 if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
501 for (int i=0; i<size; i++)
502 list.set(i, obj);
503 } else {
504 ListIterator<? super T> itr = list.listIterator();
505 for (int i=0; i<size; i++) {
506 itr.next();
507 itr.set(obj);
508 }
509 }
510 }
511
512 /**
513 * Copies all of the elements from one list into another. After the
514 * operation, the index of each copied element in the destination list
515 * will be identical to its index in the source list. The destination
516 * list must be at least as long as the source list. If it is longer, the
517 * remaining elements in the destination list are unaffected. <p>
518 *
519 * This method runs in linear time.
520 *
521 * @param dest The destination list.
522 * @param src The source list.
523 * @throws IndexOutOfBoundsException if the destination list is too small
524 * to contain the entire source List.
525 * @throws UnsupportedOperationException if the destination list's
526 * list-iterator does not support the <tt>set</tt> operation.
527 */
528 public static <T> void copy(List<? super T> dest, List<? extends T> src) {
529 int srcSize = src.size();
530 if (srcSize > dest.size())
531 throw new IndexOutOfBoundsException("Source does not fit in dest");
532
533 if (srcSize < COPY_THRESHOLD ||
534 (src instanceof RandomAccess && dest instanceof RandomAccess)) {
535 for (int i=0; i<srcSize; i++)
536 dest.set(i, src.get(i));
537 } else {
538 ListIterator<? super T> di=dest.listIterator();
539 ListIterator<? extends T> si=src.listIterator();
540 for (int i=0; i<srcSize; i++) {
541 di.next();
542 di.set(si.next());
543 }
544 }
545 }
546
547 /**
548 * Returns the minimum element of the given collection, according to the
549 * <i>natural ordering</i> of its elements. All elements in the
550 * collection must implement the <tt>Comparable</tt> interface.
551 * Furthermore, all elements in the collection must be <i>mutually
552 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
553 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
554 * <tt>e2</tt> in the collection).<p>
555 *
556 * This method iterates over the entire collection, hence it requires
557 * time proportional to the size of the collection.
558 *
559 * @param coll the collection whose minimum element is to be determined.
560 * @return the minimum element of the given collection, according
561 * to the <i>natural ordering</i> of its elements.
562 * @throws ClassCastException if the collection contains elements that are
563 * not <i>mutually comparable</i> (for example, strings and
564 * integers).
565 * @throws NoSuchElementException if the collection is empty.
566 * @see Comparable
567 */
568 public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
569 Iterator<? extends T> i = coll.iterator();
570 T candidate = i.next();
571
572 while (i.hasNext()) {
573 T next = i.next();
574 if (next.compareTo(candidate) < 0)
575 candidate = next;
576 }
577 return candidate;
578 }
579
580 /**
581 * Returns the minimum element of the given collection, according to the
582 * order induced by the specified comparator. All elements in the
583 * collection must be <i>mutually comparable</i> by the specified
584 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
585 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
586 * <tt>e2</tt> in the collection).<p>
587 *
588 * This method iterates over the entire collection, hence it requires
589 * time proportional to the size of the collection.
590 *
591 * @param coll the collection whose minimum element is to be determined.
592 * @param comp the comparator with which to determine the minimum element.
593 * A <tt>null</tt> value indicates that the elements' <i>natural
594 * ordering</i> should be used.
595 * @return the minimum element of the given collection, according
596 * to the specified comparator.
597 * @throws ClassCastException if the collection contains elements that are
598 * not <i>mutually comparable</i> using the specified comparator.
599 * @throws NoSuchElementException if the collection is empty.
600 * @see Comparable
601 */
602 public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
603 if (comp==null)
604 return (T)min((Collection<SelfComparable>) (Collection) coll);
605
606 Iterator<? extends T> i = coll.iterator();
607 T candidate = i.next();
608
609 while (i.hasNext()) {
610 T next = i.next();
611 if (comp.compare(next, candidate) < 0)
612 candidate = next;
613 }
614 return candidate;
615 }
616
617 /**
618 * Returns the maximum element of the given collection, according to the
619 * <i>natural ordering</i> of its elements. All elements in the
620 * collection must implement the <tt>Comparable</tt> interface.
621 * Furthermore, all elements in the collection must be <i>mutually
622 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
623 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
624 * <tt>e2</tt> in the collection).<p>
625 *
626 * This method iterates over the entire collection, hence it requires
627 * time proportional to the size of the collection.
628 *
629 * @param coll the collection whose maximum element is to be determined.
630 * @return the maximum element of the given collection, according
631 * to the <i>natural ordering</i> of its elements.
632 * @throws ClassCastException if the collection contains elements that are
633 * not <i>mutually comparable</i> (for example, strings and
634 * integers).
635 * @throws NoSuchElementException if the collection is empty.
636 * @see Comparable
637 */
638 public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
639 Iterator<? extends T> i = coll.iterator();
640 T candidate = i.next();
641
642 while (i.hasNext()) {
643 T next = i.next();
644 if (next.compareTo(candidate) > 0)
645 candidate = next;
646 }
647 return candidate;
648 }
649
650 /**
651 * Returns the maximum element of the given collection, according to the
652 * order induced by the specified comparator. All elements in the
653 * collection must be <i>mutually comparable</i> by the specified
654 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
655 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
656 * <tt>e2</tt> in the collection).<p>
657 *
658 * This method iterates over the entire collection, hence it requires
659 * time proportional to the size of the collection.
660 *
661 * @param coll the collection whose maximum element is to be determined.
662 * @param comp the comparator with which to determine the maximum element.
663 * A <tt>null</tt> value indicates that the elements' <i>natural
664 * ordering</i> should be used.
665 * @return the maximum element of the given collection, according
666 * to the specified comparator.
667 * @throws ClassCastException if the collection contains elements that are
668 * not <i>mutually comparable</i> using the specified comparator.
669 * @throws NoSuchElementException if the collection is empty.
670 * @see Comparable
671 */
672 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
673 if (comp==null)
674 return (T)max((Collection<SelfComparable>) (Collection) coll);
675
676 Iterator<? extends T> i = coll.iterator();
677 T candidate = i.next();
678
679 while (i.hasNext()) {
680 T next = i.next();
681 if (comp.compare(next, candidate) > 0)
682 candidate = next;
683 }
684 return candidate;
685 }
686
687 /**
688 * Rotates the elements in the specified list by the specified distance.
689 * After calling this method, the element at index <tt>i</tt> will be
690 * the element previously at index <tt>(i - distance)</tt> mod
691 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
692 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
693 * the size of the list.)
694 *
695 * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
696 * After invoking <tt>Collections.rotate(list, 1)</tt> (or
697 * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
698 * <tt>[s, t, a, n, k]</tt>.
699 *
700 * <p>Note that this method can usefully be applied to sublists to
701 * move one or more elements within a list while preserving the
702 * order of the remaining elements. For example, the following idiom
703 * moves the element at index <tt>j</tt> forward to position
704 * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
705 * <pre>
706 * Collections.rotate(list.subList(j, k+1), -1);
707 * </pre>
708 * To make this concrete, suppose <tt>list</tt> comprises
709 * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt>
710 * (<tt>b</tt>) forward two positions, perform the following invocation:
711 * <pre>
712 * Collections.rotate(l.subList(1, 4), -1);
713 * </pre>
714 * The resulting list is <tt>[a, c, d, b, e]</tt>.
715 *
716 * <p>To move more than one element forward, increase the absolute value
717 * of the rotation distance. To move elements backward, use a positive
718 * shift distance.
719 *
720 * <p>If the specified list is small or implements the {@link
721 * RandomAccess} interface, this implementation exchanges the first
722 * element into the location it should go, and then repeatedly exchanges
723 * the displaced element into the location it should go until a displaced
724 * element is swapped into the first element. If necessary, the process
725 * is repeated on the second and successive elements, until the rotation
726 * is complete. If the specified list is large and doesn't implement the
727 * <tt>RandomAccess</tt> interface, this implementation breaks the
728 * list into two sublist views around index <tt>-distance mod size</tt>.
729 * Then the {@link #reverse(List)} method is invoked on each sublist view,
730 * and finally it is invoked on the entire list. For a more complete
731 * description of both algorithms, see Section 2.3 of Jon Bentley's
732 * <i>Programming Pearls</i> (Addison-Wesley, 1986).
733 *
734 * @param list the list to be rotated.
735 * @param distance the distance to rotate the list. There are no
736 * constraints on this value; it may be zero, negative, or
737 * greater than <tt>list.size()</tt>.
738 * @throws UnsupportedOperationException if the specified list or
739 * its list-iterator does not support the <tt>set</tt> operation.
740 * @since 1.4
741 */
742 public static void rotate(List<?> list, int distance) {
743 if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
744 rotate1((List)list, distance);
745 else
746 rotate2((List)list, distance);
747 }
748
749 private static <T> void rotate1(List<T> list, int distance) {
750 int size = list.size();
751 if (size == 0)
752 return;
753 distance = distance % size;
754 if (distance < 0)
755 distance += size;
756 if (distance == 0)
757 return;
758
759 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
760 T displaced = list.get(cycleStart);
761 int i = cycleStart;
762 do {
763 i += distance;
764 if (i >= size)
765 i -= size;
766 displaced = list.set(i, displaced);
767 nMoved ++;
768 } while(i != cycleStart);
769 }
770 }
771
772 private static void rotate2(List<?> list, int distance) {
773 int size = list.size();
774 if (size == 0)
775 return;
776 int mid = -distance % size;
777 if (mid < 0)
778 mid += size;
779 if (mid == 0)
780 return;
781
782 reverse(list.subList(0, mid));
783 reverse(list.subList(mid, size));
784 reverse(list);
785 }
786
787 /**
788 * Replaces all occurrences of one specified value in a list with another.
789 * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
790 * in <tt>list</tt> such that
791 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
792 * (This method has no effect on the size of the list.)
793 *
794 * @param list the list in which replacement is to occur.
795 * @param oldVal the old value to be replaced.
796 * @param newVal the new value with which <tt>oldVal</tt> is to be
797 * replaced.
798 * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
799 * <tt>e</tt> such that
800 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
801 * @throws UnsupportedOperationException if the specified list or
802 * its list-iterator does not support the <tt>set</tt> operation.
803 * @since 1.4
804 */
805 public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
806 boolean result = false;
807 int size = list.size();
808 if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
809 if (oldVal==null) {
810 for (int i=0; i<size; i++) {
811 if (list.get(i)==null) {
812 list.set(i, newVal);
813 result = true;
814 }
815 }
816 } else {
817 for (int i=0; i<size; i++) {
818 if (oldVal.equals(list.get(i))) {
819 list.set(i, newVal);
820 result = true;
821 }
822 }
823 }
824 } else {
825 ListIterator<T> itr=list.listIterator();
826 if (oldVal==null) {
827 for (int i=0; i<size; i++) {
828 if (itr.next()==null) {
829 itr.set(newVal);
830 result = true;
831 }
832 }
833 } else {
834 for (int i=0; i<size; i++) {
835 if (oldVal.equals(itr.next())) {
836 itr.set(newVal);
837 result = true;
838 }
839 }
840 }
841 }
842 return result;
843 }
844
845 /**
846 * Returns the starting position of the first occurrence of the specified
847 * target list within the specified source list, or -1 if there is no
848 * such occurrence. More formally, returns the lowest index <tt>i</tt>
849 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
850 * or -1 if there is no such index. (Returns -1 if
851 * <tt>target.size() > source.size()</tt>.)
852 *
853 * <p>This implementation uses the "brute force" technique of scanning
854 * over the source list, looking for a match with the target at each
855 * location in turn.
856 *
857 * @param source the list in which to search for the first occurrence
858 * of <tt>target</tt>.
859 * @param target the list to search for as a subList of <tt>source</tt>.
860 * @return the starting position of the first occurrence of the specified
861 * target list within the specified source list, or -1 if there
862 * is no such occurrence.
863 * @since 1.4
864 */
865 public static int indexOfSubList(List<?> source, List<?> target) {
866 int sourceSize = source.size();
867 int targetSize = target.size();
868 int maxCandidate = sourceSize - targetSize;
869
870 if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
871 (source instanceof RandomAccess&&target instanceof RandomAccess)) {
872 nextCand:
873 for (int candidate = 0; candidate <= maxCandidate; candidate++) {
874 for (int i=0, j=candidate; i<targetSize; i++, j++)
875 if (!eq(target.get(i), source.get(j)))
876 continue nextCand; // Element mismatch, try next cand
877 return candidate; // All elements of candidate matched target
878 }
879 } else { // Iterator version of above algorithm
880 ListIterator<?> si = source.listIterator();
881 nextCand:
882 for (int candidate = 0; candidate <= maxCandidate; candidate++) {
883 ListIterator<?> ti = target.listIterator();
884 for (int i=0; i<targetSize; i++) {
885 if (!eq(ti.next(), si.next())) {
886 // Back up source iterator to next candidate
887 for (int j=0; j<i; j++)
888 si.previous();
889 continue nextCand;
890 }
891 }
892 return candidate;
893 }
894 }
895 return -1; // No candidate matched the target
896 }
897
898 /**
899 * Returns the starting position of the last occurrence of the specified
900 * target list within the specified source list, or -1 if there is no such
901 * occurrence. More formally, returns the highest index <tt>i</tt>
902 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
903 * or -1 if there is no such index. (Returns -1 if
904 * <tt>target.size() > source.size()</tt>.)
905 *
906 * <p>This implementation uses the "brute force" technique of iterating
907 * over the source list, looking for a match with the target at each
908 * location in turn.
909 *
910 * @param source the list in which to search for the last occurrence
911 * of <tt>target</tt>.
912 * @param target the list to search for as a subList of <tt>source</tt>.
913 * @return the starting position of the last occurrence of the specified
914 * target list within the specified source list, or -1 if there
915 * is no such occurrence.
916 * @since 1.4
917 */
918 public static int lastIndexOfSubList(List<?> source, List<?> target) {
919 int sourceSize = source.size();
920 int targetSize = target.size();
921 int maxCandidate = sourceSize - targetSize;
922
923 if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
924 source instanceof RandomAccess) { // Index access version
925 nextCand:
926 for (int candidate = maxCandidate; candidate >= 0; candidate--) {
927 for (int i=0, j=candidate; i<targetSize; i++, j++)
928 if (!eq(target.get(i), source.get(j)))
929 continue nextCand; // Element mismatch, try next cand
930 return candidate; // All elements of candidate matched target
931 }
932 } else { // Iterator version of above algorithm
933 if (maxCandidate < 0)
934 return -1;
935 ListIterator<?> si = source.listIterator(maxCandidate);
936 nextCand:
937 for (int candidate = maxCandidate; candidate >= 0; candidate--) {
938 ListIterator<?> ti = target.listIterator();
939 for (int i=0; i<targetSize; i++) {
940 if (!eq(ti.next(), si.next())) {
941 if (candidate != 0) {
942 // Back up source iterator to next candidate
943 for (int j=0; j<=i+1; j++)
944 si.previous();
945 }
946 continue nextCand;
947 }
948 }
949 return candidate;
950 }
951 }
952 return -1; // No candidate matched the target
953 }
954
955
956 // Unmodifiable Wrappers
957
958 /**
959 * Returns an unmodifiable view of the specified collection. This method
960 * allows modules to provide users with "read-only" access to internal
961 * collections. Query operations on the returned collection "read through"
962 * to the specified collection, and attempts to modify the returned
963 * collection, whether direct or via its iterator, result in an
964 * <tt>UnsupportedOperationException</tt>.<p>
965 *
966 * The returned collection does <i>not</i> pass the hashCode and equals
967 * operations through to the backing collection, but relies on
968 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
969 * is necessary to preserve the contracts of these operations in the case
970 * that the backing collection is a set or a list.<p>
971 *
972 * The returned collection will be serializable if the specified collection
973 * is serializable.
974 *
975 * @param c the collection for which an unmodifiable view is to be
976 * returned.
977 * @return an unmodifiable view of the specified collection.
978 */
979 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
980 return new UnmodifiableCollection<T>(c);
981 }
982
983 /**
984 * @serial include
985 */
986 static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
987 // use serialVersionUID from JDK 1.2.2 for interoperability
988 private static final long serialVersionUID = 1820017752578914078L;
989
990 final Collection<? extends E> c;
991
992 UnmodifiableCollection(Collection<? extends E> c) {
993 if (c==null)
994 throw new NullPointerException();
995 this.c = c;
996 }
997
998 public int size() {return c.size();}
999 public boolean isEmpty() {return c.isEmpty();}
1000 public boolean contains(Object o) {return c.contains(o);}
1001 public Object[] toArray() {return c.toArray();}
1002 public <T> T[] toArray(T[] a) {return c.toArray(a);}
1003 public String toString() {return c.toString();}
1004
1005 public Iterator<E> iterator() {
1006 return new Iterator<E>() {
1007 Iterator<? extends E> i = c.iterator();
1008
1009 public boolean hasNext() {return i.hasNext();}
1010 public E next() {return i.next();}
1011 public void remove() {
1012 throw new UnsupportedOperationException();
1013 }
1014 };
1015 }
1016
1017 public boolean add(E e){
1018 throw new UnsupportedOperationException();
1019 }
1020 public boolean remove(Object o) {
1021 throw new UnsupportedOperationException();
1022 }
1023
1024 public boolean containsAll(Collection<?> coll) {
1025 return c.containsAll(coll);
1026 }
1027 public boolean addAll(Collection<? extends E> coll) {
1028 throw new UnsupportedOperationException();
1029 }
1030 public boolean removeAll(Collection<?> coll) {
1031 throw new UnsupportedOperationException();
1032 }
1033 public boolean retainAll(Collection<?> coll) {
1034 throw new UnsupportedOperationException();
1035 }
1036 public void clear() {
1037 throw new UnsupportedOperationException();
1038 }
1039 }
1040
1041 /**
1042 * Returns an unmodifiable view of the specified set. This method allows
1043 * modules to provide users with "read-only" access to internal sets.
1044 * Query operations on the returned set "read through" to the specified
1045 * set, and attempts to modify the returned set, whether direct or via its
1046 * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1047 *
1048 * The returned set will be serializable if the specified set
1049 * is serializable.
1050 *
1051 * @param s the set for which an unmodifiable view is to be returned.
1052 * @return an unmodifiable view of the specified set.
1053 */
1054 public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1055 return new UnmodifiableSet<T>(s);
1056 }
1057
1058 /**
1059 * @serial include
1060 */
1061 static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
1062 implements Set<E>, Serializable {
1063 private static final long serialVersionUID = -9215047833775013803L;
1064
1065 UnmodifiableSet(Set<? extends E> s) {super(s);}
1066 public boolean equals(Object o) {return o == this || c.equals(o);}
1067 public int hashCode() {return c.hashCode();}
1068 }
1069
1070 /**
1071 * Returns an unmodifiable view of the specified sorted set. This method
1072 * allows modules to provide users with "read-only" access to internal
1073 * sorted sets. Query operations on the returned sorted set "read
1074 * through" to the specified sorted set. Attempts to modify the returned
1075 * sorted set, whether direct, via its iterator, or via its
1076 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1077 * an <tt>UnsupportedOperationException</tt>.<p>
1078 *
1079 * The returned sorted set will be serializable if the specified sorted set
1080 * is serializable.
1081 *
1082 * @param s the sorted set for which an unmodifiable view is to be
1083 * returned.
1084 * @return an unmodifiable view of the specified sorted set.
1085 */
1086 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
1087 return new UnmodifiableSortedSet<T>(s);
1088 }
1089
1090 /**
1091 * @serial include
1092 */
1093 static class UnmodifiableSortedSet<E>
1094 extends UnmodifiableSet<E>
1095 implements SortedSet<E>, Serializable {
1096 private static final long serialVersionUID = -4929149591599911165L;
1097 private final SortedSet<E> ss;
1098
1099 UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1100
1101 public Comparator<? super E> comparator() {return ss.comparator();}
1102
1103 public SortedSet<E> subSet(E fromElement, E toElement) {
1104 return new UnmodifiableSortedSet<E>(ss.subSet(fromElement,toElement));
1105 }
1106 public SortedSet<E> headSet(E toElement) {
1107 return new UnmodifiableSortedSet<E>(ss.headSet(toElement));
1108 }
1109 public SortedSet<E> tailSet(E fromElement) {
1110 return new UnmodifiableSortedSet<E>(ss.tailSet(fromElement));
1111 }
1112
1113 public E first() {return ss.first();}
1114 public E last() {return ss.last();}
1115 }
1116
1117 /**
1118 * Returns an unmodifiable view of the specified list. This method allows
1119 * modules to provide users with "read-only" access to internal
1120 * lists. Query operations on the returned list "read through" to the
1121 * specified list, and attempts to modify the returned list, whether
1122 * direct or via its iterator, result in an
1123 * <tt>UnsupportedOperationException</tt>.<p>
1124 *
1125 * The returned list will be serializable if the specified list
1126 * is serializable. Similarly, the returned list will implement
1127 * {@link RandomAccess} if the specified list does.
1128 *
1129 * @param list the list for which an unmodifiable view is to be returned.
1130 * @return an unmodifiable view of the specified list.
1131 */
1132 public static <T> List<T> unmodifiableList(List<? extends T> list) {
1133 return (list instanceof RandomAccess ?
1134 new UnmodifiableRandomAccessList<T>(list) :
1135 new UnmodifiableList<T>(list));
1136 }
1137
1138 /**
1139 * @serial include
1140 */
1141 static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1142 implements List<E> {
1143 static final long serialVersionUID = -283967356065247728L;
1144 final List<? extends E> list;
1145
1146 UnmodifiableList(List<? extends E> list) {
1147 super(list);
1148 this.list = list;
1149 }
1150
1151 public boolean equals(Object o) {return o == this || list.equals(o);}
1152 public int hashCode() {return list.hashCode();}
1153
1154 public E get(int index) {return list.get(index);}
1155 public E set(int index, E element) {
1156 throw new UnsupportedOperationException();
1157 }
1158 public void add(int index, E element) {
1159 throw new UnsupportedOperationException();
1160 }
1161 public E remove(int index) {
1162 throw new UnsupportedOperationException();
1163 }
1164 public int indexOf(Object o) {return list.indexOf(o);}
1165 public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1166 public boolean addAll(int index, Collection<? extends E> c) {
1167 throw new UnsupportedOperationException();
1168 }
1169 public ListIterator<E> listIterator() {return listIterator(0);}
1170
1171 public ListIterator<E> listIterator(final int index) {
1172 return new ListIterator<E>() {
1173 ListIterator<? extends E> i = list.listIterator(index);
1174
1175 public boolean hasNext() {return i.hasNext();}
1176 public E next() {return i.next();}
1177 public boolean hasPrevious() {return i.hasPrevious();}
1178 public E previous() {return i.previous();}
1179 public int nextIndex() {return i.nextIndex();}
1180 public int previousIndex() {return i.previousIndex();}
1181
1182 public void remove() {
1183 throw new UnsupportedOperationException();
1184 }
1185 public void set(E e) {
1186 throw new UnsupportedOperationException();
1187 }
1188 public void add(E e) {
1189 throw new UnsupportedOperationException();
1190 }
1191 };
1192 }
1193
1194 public List<E> subList(int fromIndex, int toIndex) {
1195 return new UnmodifiableList<E>(list.subList(fromIndex, toIndex));
1196 }
1197
1198 /**
1199 * UnmodifiableRandomAccessList instances are serialized as
1200 * UnmodifiableList instances to allow them to be deserialized
1201 * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
1202 * This method inverts the transformation. As a beneficial
1203 * side-effect, it also grafts the RandomAccess marker onto
1204 * UnmodifiableList instances that were serialized in pre-1.4 JREs.
1205 *
1206 * Note: Unfortunately, UnmodifiableRandomAccessList instances
1207 * serialized in 1.4.1 and deserialized in 1.4 will become
1208 * UnmodifiableList instances, as this method was missing in 1.4.
1209 */
1210 private Object readResolve() {
1211 return (list instanceof RandomAccess
1212 ? new UnmodifiableRandomAccessList<E>(list)
1213 : this);
1214 }
1215 }
1216
1217 /**
1218 * @serial include
1219 */
1220 static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E>
1221 implements RandomAccess
1222 {
1223 UnmodifiableRandomAccessList(List<? extends E> list) {
1224 super(list);
1225 }
1226
1227 public List<E> subList(int fromIndex, int toIndex) {
1228 return new UnmodifiableRandomAccessList<E>(
1229 list.subList(fromIndex, toIndex));
1230 }
1231
1232 private static final long serialVersionUID = -2542308836966382001L;
1233
1234 /**
1235 * Allows instances to be deserialized in pre-1.4 JREs (which do
1236 * not have UnmodifiableRandomAccessList). UnmodifiableList has
1237 * a readResolve method that inverts this transformation upon
1238 * deserialization.
1239 */
1240 private Object writeReplace() {
1241 return new UnmodifiableList<E>(list);
1242 }
1243 }
1244
1245 /**
1246 * Returns an unmodifiable view of the specified map. This method
1247 * allows modules to provide users with "read-only" access to internal
1248 * maps. Query operations on the returned map "read through"
1249 * to the specified map, and attempts to modify the returned
1250 * map, whether direct or via its collection views, result in an
1251 * <tt>UnsupportedOperationException</tt>.<p>
1252 *
1253 * The returned map will be serializable if the specified map
1254 * is serializable.
1255 *
1256 * @param m the map for which an unmodifiable view is to be returned.
1257 * @return an unmodifiable view of the specified map.
1258 */
1259 public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
1260 return new UnmodifiableMap<K,V>(m);
1261 }
1262
1263 /**
1264 * @serial include
1265 */
1266 private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
1267 // use serialVersionUID from JDK 1.2.2 for interoperability
1268 private static final long serialVersionUID = -1034234728574286014L;
1269
1270 private final Map<? extends K, ? extends V> m;
1271
1272 UnmodifiableMap(Map<? extends K, ? extends V> m) {
1273 if (m==null)
1274 throw new NullPointerException();
1275 this.m = m;
1276 }
1277
1278 public int size() {return m.size();}
1279 public boolean isEmpty() {return m.isEmpty();}
1280 public boolean containsKey(Object key) {return m.containsKey(key);}
1281 public boolean containsValue(Object val) {return m.containsValue(val);}
1282 public V get(Object key) {return m.get(key);}
1283
1284 public V put(K key, V value) {
1285 throw new UnsupportedOperationException();
1286 }
1287 public V remove(Object key) {
1288 throw new UnsupportedOperationException();
1289 }
1290 public void putAll(Map<? extends K, ? extends V> m) {
1291 throw new UnsupportedOperationException();
1292 }
1293 public void clear() {
1294 throw new UnsupportedOperationException();
1295 }
1296
1297 private transient Set<K> keySet = null;
1298 private transient Set<Map.Entry<K,V>> entrySet = null;
1299 private transient Collection<V> values = null;
1300
1301 public Set<K> keySet() {
1302 if (keySet==null)
1303 keySet = unmodifiableSet(m.keySet());
1304 return keySet;
1305 }
1306
1307 public Set<Map.Entry<K,V>> entrySet() {
1308 if (entrySet==null)
1309 entrySet = new UnmodifiableEntrySet<K,V>(m.entrySet());
1310 return entrySet;
1311 }
1312
1313 public Collection<V> values() {
1314 if (values==null)
1315 values = unmodifiableCollection(m.values());
1316 return values;
1317 }
1318
1319 public boolean equals(Object o) {return o == this || m.equals(o);}
1320 public int hashCode() {return m.hashCode();}
1321 public String toString() {return m.toString();}
1322
1323 /**
1324 * We need this class in addition to UnmodifiableSet as
1325 * Map.Entries themselves permit modification of the backing Map
1326 * via their setValue operation. This class is subtle: there are
1327 * many possible attacks that must be thwarted.
1328 *
1329 * @serial include
1330 */
1331 static class UnmodifiableEntrySet<K,V>
1332 extends UnmodifiableSet<Map.Entry<K,V>> {
1333 private static final long serialVersionUID = 7854390611657943733L;
1334
1335 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1336 super((Set)s);
1337 }
1338 public Iterator<Map.Entry<K,V>> iterator() {
1339 return new Iterator<Map.Entry<K,V>>() {
1340 Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1341
1342 public boolean hasNext() {
1343 return i.hasNext();
1344 }
1345 public Map.Entry<K,V> next() {
1346 return new UnmodifiableEntry<K,V>(i.next());
1347 }
1348 public void remove() {
1349 throw new UnsupportedOperationException();
1350 }
1351 };
1352 }
1353
1354 public Object[] toArray() {
1355 Object[] a = c.toArray();
1356 for (int i=0; i<a.length; i++)
1357 a[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)a[i]);
1358 return a;
1359 }
1360
1361 public <T> T[] toArray(T[] a) {
1362 // We don't pass a to c.toArray, to avoid window of
1363 // vulnerability wherein an unscrupulous multithreaded client
1364 // could get his hands on raw (unwrapped) Entries from c.
1365 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1366
1367 for (int i=0; i<arr.length; i++)
1368 arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]);
1369
1370 if (arr.length > a.length)
1371 return (T[])arr;
1372
1373 System.arraycopy(arr, 0, a, 0, arr.length);
1374 if (a.length > arr.length)
1375 a[arr.length] = null;
1376 return a;
1377 }
1378
1379 /**
1380 * This method is overridden to protect the backing set against
1381 * an object with a nefarious equals function that senses
1382 * that the equality-candidate is Map.Entry and calls its
1383 * setValue method.
1384 */
1385 public boolean contains(Object o) {
1386 if (!(o instanceof Map.Entry))
1387 return false;
1388 return c.contains(new UnmodifiableEntry<K,V>((Map.Entry<K,V>) o));
1389 }
1390
1391 /**
1392 * The next two methods are overridden to protect against
1393 * an unscrupulous List whose contains(Object o) method senses
1394 * when o is a Map.Entry, and calls o.setValue.
1395 */
1396 public boolean containsAll(Collection<?> coll) {
1397 Iterator<?> e = coll.iterator();
1398 while (e.hasNext())
1399 if (!contains(e.next())) // Invokes safe contains() above
1400 return false;
1401 return true;
1402 }
1403 public boolean equals(Object o) {
1404 if (o == this)
1405 return true;
1406
1407 if (!(o instanceof Set))
1408 return false;
1409 Set s = (Set) o;
1410 if (s.size() != c.size())
1411 return false;
1412 return containsAll(s); // Invokes safe containsAll() above
1413 }
1414
1415 /**
1416 * This "wrapper class" serves two purposes: it prevents
1417 * the client from modifying the backing Map, by short-circuiting
1418 * the setValue method, and it protects the backing Map against
1419 * an ill-behaved Map.Entry that attempts to modify another
1420 * Map Entry when asked to perform an equality check.
1421 */
1422 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
1423 private Map.Entry<? extends K, ? extends V> e;
1424
1425 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1426
1427 public K getKey() {return e.getKey();}
1428 public V getValue() {return e.getValue();}
1429 public V setValue(V value) {
1430 throw new UnsupportedOperationException();
1431 }
1432 public int hashCode() {return e.hashCode();}
1433 public boolean equals(Object o) {
1434 if (!(o instanceof Map.Entry))
1435 return false;
1436 Map.Entry t = (Map.Entry)o;
1437 return eq(e.getKey(), t.getKey()) &&
1438 eq(e.getValue(), t.getValue());
1439 }
1440 public String toString() {return e.toString();}
1441 }
1442 }
1443 }
1444
1445 /**
1446 * Returns an unmodifiable view of the specified sorted map. This method
1447 * allows modules to provide users with "read-only" access to internal
1448 * sorted maps. Query operations on the returned sorted map "read through"
1449 * to the specified sorted map. Attempts to modify the returned
1450 * sorted map, whether direct, via its collection views, or via its
1451 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1452 * an <tt>UnsupportedOperationException</tt>.<p>
1453 *
1454 * The returned sorted map will be serializable if the specified sorted map
1455 * is serializable.
1456 *
1457 * @param m the sorted map for which an unmodifiable view is to be
1458 * returned.
1459 * @return an unmodifiable view of the specified sorted map.
1460 */
1461 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1462 return new UnmodifiableSortedMap<K,V>(m);
1463 }
1464
1465 /**
1466 * @serial include
1467 */
1468 static class UnmodifiableSortedMap<K,V>
1469 extends UnmodifiableMap<K,V>
1470 implements SortedMap<K,V>, Serializable {
1471 private static final long serialVersionUID = -8806743815996713206L;
1472
1473 private final SortedMap<K, ? extends V> sm;
1474
1475 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1476
1477 public Comparator<? super K> comparator() {return sm.comparator();}
1478
1479 public SortedMap<K,V> subMap(K fromKey, K toKey) {
1480 return new UnmodifiableSortedMap<K,V>(sm.subMap(fromKey, toKey));
1481 }
1482 public SortedMap<K,V> headMap(K toKey) {
1483 return new UnmodifiableSortedMap<K,V>(sm.headMap(toKey));
1484 }
1485 public SortedMap<K,V> tailMap(K fromKey) {
1486 return new UnmodifiableSortedMap<K,V>(sm.tailMap(fromKey));
1487 }
1488
1489 public K firstKey() {return sm.firstKey();}
1490 public K lastKey() {return sm.lastKey();}
1491 }
1492
1493
1494 // Synch Wrappers
1495
1496 /**
1497 * Returns a synchronized (thread-safe) collection backed by the specified
1498 * collection. In order to guarantee serial access, it is critical that
1499 * <strong>all</strong> access to the backing collection is accomplished
1500 * through the returned collection.<p>
1501 *
1502 * It is imperative that the user manually synchronize on the returned
1503 * collection when iterating over it:
1504 * <pre>
1505 * Collection c = Collections.synchronizedCollection(myCollection);
1506 * ...
1507 * synchronized(c) {
1508 * Iterator i = c.iterator(); // Must be in the synchronized block
1509 * while (i.hasNext())
1510 * foo(i.next());
1511 * }
1512 * </pre>
1513 * Failure to follow this advice may result in non-deterministic behavior.
1514 *
1515 * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1516 * and <tt>equals</tt> operations through to the backing collection, but
1517 * relies on <tt>Object</tt>'s equals and hashCode methods. This is
1518 * necessary to preserve the contracts of these operations in the case
1519 * that the backing collection is a set or a list.<p>
1520 *
1521 * The returned collection will be serializable if the specified collection
1522 * is serializable.
1523 *
1524 * @param c the collection to be "wrapped" in a synchronized collection.
1525 * @return a synchronized view of the specified collection.
1526 */
1527 public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1528 return new SynchronizedCollection<T>(c);
1529 }
1530
1531 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1532 return new SynchronizedCollection<T>(c, mutex);
1533 }
1534
1535 /**
1536 * @serial include
1537 */
1538 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1539 // use serialVersionUID from JDK 1.2.2 for interoperability
1540 private static final long serialVersionUID = 3053995032091335093L;
1541
1542 final Collection<E> c; // Backing Collection
1543 final Object mutex; // Object on which to synchronize
1544
1545 SynchronizedCollection(Collection<E> c) {
1546 if (c==null)
1547 throw new NullPointerException();
1548 this.c = c;
1549 mutex = this;
1550 }
1551 SynchronizedCollection(Collection<E> c, Object mutex) {
1552 this.c = c;
1553 this.mutex = mutex;
1554 }
1555
1556 public int size() {
1557 synchronized(mutex) {return c.size();}
1558 }
1559 public boolean isEmpty() {
1560 synchronized(mutex) {return c.isEmpty();}
1561 }
1562 public boolean contains(Object o) {
1563 synchronized(mutex) {return c.contains(o);}
1564 }
1565 public Object[] toArray() {
1566 synchronized(mutex) {return c.toArray();}
1567 }
1568 public <T> T[] toArray(T[] a) {
1569 synchronized(mutex) {return c.toArray(a);}
1570 }
1571
1572 public Iterator<E> iterator() {
1573 return c.iterator(); // Must be manually synched by user!
1574 }
1575
1576 public boolean add(E e) {
1577 synchronized(mutex) {return c.add(e);}
1578 }
1579 public boolean remove(Object o) {
1580 synchronized(mutex) {return c.remove(o);}
1581 }
1582
1583 public boolean containsAll(Collection<?> coll) {
1584 synchronized(mutex) {return c.containsAll(coll);}
1585 }
1586 public boolean addAll(Collection<? extends E> coll) {
1587 synchronized(mutex) {return c.addAll(coll);}
1588 }
1589 public boolean removeAll(Collection<?> coll) {
1590 synchronized(mutex) {return c.removeAll(coll);}
1591 }
1592 public boolean retainAll(Collection<?> coll) {
1593 synchronized(mutex) {return c.retainAll(coll);}
1594 }
1595 public void clear() {
1596 synchronized(mutex) {c.clear();}
1597 }
1598 public String toString() {
1599 synchronized(mutex) {return c.toString();}
1600 }
1601 private void writeObject(ObjectOutputStream s) throws IOException {
1602 synchronized(mutex) {s.defaultWriteObject();}
1603 }
1604 }
1605
1606 /**
1607 * Returns a synchronized (thread-safe) set backed by the specified
1608 * set. In order to guarantee serial access, it is critical that
1609 * <strong>all</strong> access to the backing set is accomplished
1610 * through the returned set.<p>
1611 *
1612 * It is imperative that the user manually synchronize on the returned
1613 * set when iterating over it:
1614 * <pre>
1615 * Set s = Collections.synchronizedSet(new HashSet());
1616 * ...
1617 * synchronized(s) {
1618 * Iterator i = s.iterator(); // Must be in the synchronized block
1619 * while (i.hasNext())
1620 * foo(i.next());
1621 * }
1622 * </pre>
1623 * Failure to follow this advice may result in non-deterministic behavior.
1624 *
1625 * <p>The returned set will be serializable if the specified set is
1626 * serializable.
1627 *
1628 * @param s the set to be "wrapped" in a synchronized set.
1629 * @return a synchronized view of the specified set.
1630 */
1631 public static <T> Set<T> synchronizedSet(Set<T> s) {
1632 return new SynchronizedSet<T>(s);
1633 }
1634
1635 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1636 return new SynchronizedSet<T>(s, mutex);
1637 }
1638
1639 /**
1640 * @serial include
1641 */
1642 static class SynchronizedSet<E>
1643 extends SynchronizedCollection<E>
1644 implements Set<E> {
1645 private static final long serialVersionUID = 487447009682186044L;
1646
1647 SynchronizedSet(Set<E> s) {
1648 super(s);
1649 }
1650 SynchronizedSet(Set<E> s, Object mutex) {
1651 super(s, mutex);
1652 }
1653
1654 public boolean equals(Object o) {
1655 synchronized(mutex) {return c.equals(o);}
1656 }
1657 public int hashCode() {
1658 synchronized(mutex) {return c.hashCode();}
1659 }
1660 }
1661
1662 /**
1663 * Returns a synchronized (thread-safe) sorted set backed by the specified
1664 * sorted set. In order to guarantee serial access, it is critical that
1665 * <strong>all</strong> access to the backing sorted set is accomplished
1666 * through the returned sorted set (or its views).<p>
1667 *
1668 * It is imperative that the user manually synchronize on the returned
1669 * sorted set when iterating over it or any of its <tt>subSet</tt>,
1670 * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1671 * <pre>
1672 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1673 * ...
1674 * synchronized(s) {
1675 * Iterator i = s.iterator(); // Must be in the synchronized block
1676 * while (i.hasNext())
1677 * foo(i.next());
1678 * }
1679 * </pre>
1680 * or:
1681 * <pre>
1682 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1683 * SortedSet s2 = s.headSet(foo);
1684 * ...
1685 * synchronized(s) { // Note: s, not s2!!!
1686 * Iterator i = s2.iterator(); // Must be in the synchronized block
1687 * while (i.hasNext())
1688 * foo(i.next());
1689 * }
1690 * </pre>
1691 * Failure to follow this advice may result in non-deterministic behavior.
1692 *
1693 * <p>The returned sorted set will be serializable if the specified
1694 * sorted set is serializable.
1695 *
1696 * @param s the sorted set to be "wrapped" in a synchronized sorted set.
1697 * @return a synchronized view of the specified sorted set.
1698 */
1699 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1700 return new SynchronizedSortedSet<T>(s);
1701 }
1702
1703 /**
1704 * @serial include
1705 */
1706 static class SynchronizedSortedSet<E>
1707 extends SynchronizedSet<E>
1708 implements SortedSet<E>
1709 {
1710 private static final long serialVersionUID = 8695801310862127406L;
1711
1712 final private SortedSet<E> ss;
1713
1714 SynchronizedSortedSet(SortedSet<E> s) {
1715 super(s);
1716 ss = s;
1717 }
1718 SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1719 super(s, mutex);
1720 ss = s;
1721 }
1722
1723 public Comparator<? super E> comparator() {
1724 synchronized(mutex) {return ss.comparator();}
1725 }
1726
1727 public SortedSet<E> subSet(E fromElement, E toElement) {
1728 synchronized(mutex) {
1729 return new SynchronizedSortedSet<E>(
1730 ss.subSet(fromElement, toElement), mutex);
1731 }
1732 }
1733 public SortedSet<E> headSet(E toElement) {
1734 synchronized(mutex) {
1735 return new SynchronizedSortedSet<E>(ss.headSet(toElement), mutex);
1736 }
1737 }
1738 public SortedSet<E> tailSet(E fromElement) {
1739 synchronized(mutex) {
1740 return new SynchronizedSortedSet<E>(ss.tailSet(fromElement),mutex);
1741 }
1742 }
1743
1744 public E first() {
1745 synchronized(mutex) {return ss.first();}
1746 }
1747 public E last() {
1748 synchronized(mutex) {return ss.last();}
1749 }
1750 }
1751
1752 /**
1753 * Returns a synchronized (thread-safe) list backed by the specified
1754 * list. In order to guarantee serial access, it is critical that
1755 * <strong>all</strong> access to the backing list is accomplished
1756 * through the returned list.<p>
1757 *
1758 * It is imperative that the user manually synchronize on the returned
1759 * list when iterating over it:
1760 * <pre>
1761 * List list = Collections.synchronizedList(new ArrayList());
1762 * ...
1763 * synchronized(list) {
1764 * Iterator i = list.iterator(); // Must be in synchronized block
1765 * while (i.hasNext())
1766 * foo(i.next());
1767 * }
1768 * </pre>
1769 * Failure to follow this advice may result in non-deterministic behavior.
1770 *
1771 * <p>The returned list will be serializable if the specified list is
1772 * serializable.
1773 *
1774 * @param list the list to be "wrapped" in a synchronized list.
1775 * @return a synchronized view of the specified list.
1776 */
1777 public static <T> List<T> synchronizedList(List<T> list) {
1778 return (list instanceof RandomAccess ?
1779 new SynchronizedRandomAccessList<T>(list) :
1780 new SynchronizedList<T>(list));
1781 }
1782
1783 static <T> List<T> synchronizedList(List<T> list, Object mutex) {
1784 return (list instanceof RandomAccess ?
1785 new SynchronizedRandomAccessList<T>(list, mutex) :
1786 new SynchronizedList<T>(list, mutex));
1787 }
1788
1789 /**
1790 * @serial include
1791 */
1792 static class SynchronizedList<E>
1793 extends SynchronizedCollection<E>
1794 implements List<E> {
1795 static final long serialVersionUID = -7754090372962971524L;
1796
1797 final List<E> list;
1798
1799 SynchronizedList(List<E> list) {
1800 super(list);
1801 this.list = list;
1802 }
1803 SynchronizedList(List<E> list, Object mutex) {
1804 super(list, mutex);
1805 this.list = list;
1806 }
1807
1808 public boolean equals(Object o) {
1809 synchronized(mutex) {return list.equals(o);}
1810 }
1811 public int hashCode() {
1812 synchronized(mutex) {return list.hashCode();}
1813 }
1814
1815 public E get(int index) {
1816 synchronized(mutex) {return list.get(index);}
1817 }
1818 public E set(int index, E element) {
1819 synchronized(mutex) {return list.set(index, element);}
1820 }
1821 public void add(int index, E element) {
1822 synchronized(mutex) {list.add(index, element);}
1823 }
1824 public E remove(int index) {
1825 synchronized(mutex) {return list.remove(index);}
1826 }
1827
1828 public int indexOf(Object o) {
1829 synchronized(mutex) {return list.indexOf(o);}
1830 }
1831 public int lastIndexOf(Object o) {
1832 synchronized(mutex) {return list.lastIndexOf(o);}
1833 }
1834
1835 public boolean addAll(int index, Collection<? extends E> c) {
1836 synchronized(mutex) {return list.addAll(index, c);}
1837 }
1838
1839 public ListIterator<E> listIterator() {
1840 return list.listIterator(); // Must be manually synched by user
1841 }
1842
1843 public ListIterator<E> listIterator(int index) {
1844 return list.listIterator(index); // Must be manually synched by user
1845 }
1846
1847 public List<E> subList(int fromIndex, int toIndex) {
1848 synchronized(mutex) {
1849 return new SynchronizedList<E>(list.subList(fromIndex, toIndex),
1850 mutex);
1851 }
1852 }
1853
1854 /**
1855 * SynchronizedRandomAccessList instances are serialized as
1856 * SynchronizedList instances to allow them to be deserialized
1857 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
1858 * This method inverts the transformation. As a beneficial
1859 * side-effect, it also grafts the RandomAccess marker onto
1860 * SynchronizedList instances that were serialized in pre-1.4 JREs.
1861 *
1862 * Note: Unfortunately, SynchronizedRandomAccessList instances
1863 * serialized in 1.4.1 and deserialized in 1.4 will become
1864 * SynchronizedList instances, as this method was missing in 1.4.
1865 */
1866 private Object readResolve() {
1867 return (list instanceof RandomAccess
1868 ? new SynchronizedRandomAccessList<E>(list)
1869 : this);
1870 }
1871 }
1872
1873 /**
1874 * @serial include
1875 */
1876 static class SynchronizedRandomAccessList<E>
1877 extends SynchronizedList<E>
1878 implements RandomAccess {
1879
1880 SynchronizedRandomAccessList(List<E> list) {
1881 super(list);
1882 }
1883
1884 SynchronizedRandomAccessList(List<E> list, Object mutex) {
1885 super(list, mutex);
1886 }
1887
1888 public List<E> subList(int fromIndex, int toIndex) {
1889 synchronized(mutex) {
1890 return new SynchronizedRandomAccessList<E>(
1891 list.subList(fromIndex, toIndex), mutex);
1892 }
1893 }
1894
1895 static final long serialVersionUID = 1530674583602358482L;
1896
1897 /**
1898 * Allows instances to be deserialized in pre-1.4 JREs (which do
1899 * not have SynchronizedRandomAccessList). SynchronizedList has
1900 * a readResolve method that inverts this transformation upon
1901 * deserialization.
1902 */
1903 private Object writeReplace() {
1904 return new SynchronizedList<E>(list);
1905 }
1906 }
1907
1908 /**
1909 * Returns a synchronized (thread-safe) map backed by the specified
1910 * map. In order to guarantee serial access, it is critical that
1911 * <strong>all</strong> access to the backing map is accomplished
1912 * through the returned map.<p>
1913 *
1914 * It is imperative that the user manually synchronize on the returned
1915 * map when iterating over any of its collection views:
1916 * <pre>
1917 * Map m = Collections.synchronizedMap(new HashMap());
1918 * ...
1919 * Set s = m.keySet(); // Needn't be in synchronized block
1920 * ...
1921 * synchronized(m) { // Synchronizing on m, not s!
1922 * Iterator i = s.iterator(); // Must be in synchronized block
1923 * while (i.hasNext())
1924 * foo(i.next());
1925 * }
1926 * </pre>
1927 * Failure to follow this advice may result in non-deterministic behavior.
1928 *
1929 * <p>The returned map will be serializable if the specified map is
1930 * serializable.
1931 *
1932 * @param m the map to be "wrapped" in a synchronized map.
1933 * @return a synchronized view of the specified map.
1934 */
1935 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
1936 return new SynchronizedMap<K,V>(m);
1937 }
1938
1939 /**
1940 * @serial include
1941 */
1942 private static class SynchronizedMap<K,V>
1943 implements Map<K,V>, Serializable {
1944 // use serialVersionUID from JDK 1.2.2 for interoperability
1945 private static final long serialVersionUID = 1978198479659022715L;
1946
1947 private final Map<K,V> m; // Backing Map
1948 final Object mutex; // Object on which to synchronize
1949
1950 SynchronizedMap(Map<K,V> m) {
1951 if (m==null)
1952 throw new NullPointerException();
1953 this.m = m;
1954 mutex = this;
1955 }
1956
1957 SynchronizedMap(Map<K,V> m, Object mutex) {
1958 this.m = m;
1959 this.mutex = mutex;
1960 }
1961
1962 public int size() {
1963 synchronized(mutex) {return m.size();}
1964 }
1965 public boolean isEmpty(){
1966 synchronized(mutex) {return m.isEmpty();}
1967 }
1968 public boolean containsKey(Object key) {
1969 synchronized(mutex) {return m.containsKey(key);}
1970 }
1971 public boolean containsValue(Object value){
1972 synchronized(mutex) {return m.containsValue(value);}
1973 }
1974 public V get(Object key) {
1975 synchronized(mutex) {return m.get(key);}
1976 }
1977
1978 public V put(K key, V value) {
1979 synchronized(mutex) {return m.put(key, value);}
1980 }
1981 public V remove(Object key) {
1982 synchronized(mutex) {return m.remove(key);}
1983 }
1984 public void putAll(Map<? extends K, ? extends V> map) {
1985 synchronized(mutex) {m.putAll(map);}
1986 }
1987 public void clear() {
1988 synchronized(mutex) {m.clear();}
1989 }
1990
1991 private transient Set<K> keySet = null;
1992 private transient Set<Map.Entry<K,V>> entrySet = null;
1993 private transient Collection<V> values = null;
1994
1995 public Set<K> keySet() {
1996 synchronized(mutex) {
1997 if (keySet==null)
1998 keySet = new SynchronizedSet<K>(m.keySet(), mutex);
1999 return keySet;
2000 }
2001 }
2002
2003 public Set<Map.Entry<K,V>> entrySet() {
2004 synchronized(mutex) {
2005 if (entrySet==null)
2006 entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2007 return entrySet;
2008 }
2009 }
2010
2011 public Collection<V> values() {
2012 synchronized(mutex) {
2013 if (values==null)
2014 values = new SynchronizedCollection<V>(m.values(), mutex);
2015 return values;
2016 }
2017 }
2018
2019 public boolean equals(Object o) {
2020 synchronized(mutex) {return m.equals(o);}
2021 }
2022 public int hashCode() {
2023 synchronized(mutex) {return m.hashCode();}
2024 }
2025 public String toString() {
2026 synchronized(mutex) {return m.toString();}
2027 }
2028 private void writeObject(ObjectOutputStream s) throws IOException {
2029 synchronized(mutex) {s.defaultWriteObject();}
2030 }
2031 }
2032
2033 /**
2034 * Returns a synchronized (thread-safe) sorted map backed by the specified
2035 * sorted map. In order to guarantee serial access, it is critical that
2036 * <strong>all</strong> access to the backing sorted map is accomplished
2037 * through the returned sorted map (or its views).<p>
2038 *
2039 * It is imperative that the user manually synchronize on the returned
2040 * sorted map when iterating over any of its collection views, or the
2041 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2042 * <tt>tailMap</tt> views.
2043 * <pre>
2044 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2045 * ...
2046 * Set s = m.keySet(); // Needn't be in synchronized block
2047 * ...
2048 * synchronized(m) { // Synchronizing on m, not s!
2049 * Iterator i = s.iterator(); // Must be in synchronized block
2050 * while (i.hasNext())
2051 * foo(i.next());
2052 * }
2053 * </pre>
2054 * or:
2055 * <pre>
2056 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2057 * SortedMap m2 = m.subMap(foo, bar);
2058 * ...
2059 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2060 * ...
2061 * synchronized(m) { // Synchronizing on m, not m2 or s2!
2062 * Iterator i = s.iterator(); // Must be in synchronized block
2063 * while (i.hasNext())
2064 * foo(i.next());
2065 * }
2066 * </pre>
2067 * Failure to follow this advice may result in non-deterministic behavior.
2068 *
2069 * <p>The returned sorted map will be serializable if the specified
2070 * sorted map is serializable.
2071 *
2072 * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2073 * @return a synchronized view of the specified sorted map.
2074 */
2075 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2076 return new SynchronizedSortedMap<K,V>(m);
2077 }
2078
2079
2080 /**
2081 * @serial include
2082 */
2083 static class SynchronizedSortedMap<K,V>
2084 extends SynchronizedMap<K,V>
2085 implements SortedMap<K,V>
2086 {
2087 private static final long serialVersionUID = -8798146769416483793L;
2088
2089 private final SortedMap<K,V> sm;
2090
2091 SynchronizedSortedMap(SortedMap<K,V> m) {
2092 super(m);
2093 sm = m;
2094 }
2095 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2096 super(m, mutex);
2097 sm = m;
2098 }
2099
2100 public Comparator<? super K> comparator() {
2101 synchronized(mutex) {return sm.comparator();}
2102 }
2103
2104 public SortedMap<K,V> subMap(K fromKey, K toKey) {
2105 synchronized(mutex) {
2106 return new SynchronizedSortedMap<K,V>(
2107 sm.subMap(fromKey, toKey), mutex);
2108 }
2109 }
2110 public SortedMap<K,V> headMap(K toKey) {
2111 synchronized(mutex) {
2112 return new SynchronizedSortedMap<K,V>(sm.headMap(toKey), mutex);
2113 }
2114 }
2115 public SortedMap<K,V> tailMap(K fromKey) {
2116 synchronized(mutex) {
2117 return new SynchronizedSortedMap<K,V>(sm.tailMap(fromKey),mutex);
2118 }
2119 }
2120
2121 public K firstKey() {
2122 synchronized(mutex) {return sm.firstKey();}
2123 }
2124 public K lastKey() {
2125 synchronized(mutex) {return sm.lastKey();}
2126 }
2127 }
2128
2129 // Dynamically typesafe collection wrappers
2130
2131 /**
2132 * Returns a dynamically typesafe view of the specified collection. Any
2133 * attempt to insert an element of the wrong type will result in an
2134 * immediate <tt>ClassCastException</tt>. Assuming a collection contains
2135 * no incorrectly typed elements prior to the time a dynamically typesafe
2136 * view is generated, and that all subsequent access to the collection
2137 * takes place through the view, it is <i>guaranteed</i> that the
2138 * collection cannot contain an incorrectly typed element.
2139 *
2140 * <p>The generics mechanism in the language provides compile-time
2141 * (static) type checking, but it is possible to defeat this mechanism
2142 * with unchecked casts. Usually this is not a problem, as the compiler
2143 * issues warnings on all such unchecked operations. There are, however,
2144 * times when static type checking alone is not sufficient. For example,
2145 * suppose a collection is passed to a third-party library and it is
2146 * imperative that the library code not corrupt the collection by
2147 * inserting an element of the wrong type.
2148 *
2149 * <p>Another use of dynamically typesafe views is debugging. Suppose a
2150 * program fails with a <tt>ClassCastException</tt>, indicating that an
2151 * incorrectly typed element was put into a parameterized collection.
2152 * Unfortunately, the exception can occur at any time after the erroneous
2153 * element is inserted, so it typically provides little or no information
2154 * as to the real source of the problem. If the problem is reproducible,
2155 * one can quickly determine its source by temporarily modifying the
2156 * program to wrap the collection with a dynamically typesafe view.
2157 * For example, this declaration:
2158 * <pre>
2159 * Collection<String> c = new HashSet<String>();
2160 * </pre>
2161 * may be replaced temporarily by this one:
2162 * <pre>
2163 * Collection<String> c = Collections.checkedCollection(
2164 * new HashSet<String>(), String.class);
2165 * </pre>
2166 * Running the program again will cause it to fail at the point where
2167 * an incorrectly typed element is inserted into the collection, clearly
2168 * identifying the source of the problem. Once the problem is fixed, the
2169 * modified declaration may be reverted back to the original.
2170 *
2171 * <p>The returned collection does <i>not</i> pass the hashCode and equals
2172 * operations through to the backing collection, but relies on
2173 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
2174 * is necessary to preserve the contracts of these operations in the case
2175 * that the backing collection is a set or a list.
2176 *
2177 * <p>The returned collection will be serializable if the specified
2178 * collection is serializable.
2179 *
2180 * @param c the collection for which a dynamically typesafe view is to be
2181 * returned
2182 * @param type the type of element that <tt>c</tt> is permitted to hold
2183 * @return a dynamically typesafe view of the specified collection
2184 * @since 1.5
2185 */
2186 public static <E> Collection<E> checkedCollection(Collection<E> c,
2187 Class<E> type) {
2188 return new CheckedCollection<E>(c, type);
2189 }
2190
2191 /**
2192 * @serial include
2193 */
2194 static class CheckedCollection<E> implements Collection<E>, Serializable {
2195 private static final long serialVersionUID = 1578914078182001775L;
2196
2197 final Collection<E> c;
2198 final Class<E> type;
2199
2200 void typeCheck(Object o) {
2201 if (!type.isInstance(o))
2202 throw new ClassCastException("Attempt to insert " +
2203 o.getClass() + " element into collection with element type "
2204 + type);
2205 }
2206
2207 CheckedCollection(Collection<E> c, Class<E> type) {
2208 if (c==null || type == null)
2209 throw new NullPointerException();
2210 this.c = c;
2211 this.type = type;
2212 }
2213
2214 public int size() { return c.size(); }
2215 public boolean isEmpty() { return c.isEmpty(); }
2216 public boolean contains(Object o) { return c.contains(o); }
2217 public Object[] toArray() { return c.toArray(); }
2218 public <T> T[] toArray(T[] a) { return c.toArray(a); }
2219 public String toString() { return c.toString(); }
2220 public boolean remove(Object o) { return c.remove(o); }
2221 public boolean containsAll(Collection<?> coll) {
2222 return c.containsAll(coll);
2223 }
2224 public boolean removeAll(Collection<?> coll) {
2225 return c.removeAll(coll);
2226 }
2227 public boolean retainAll(Collection<?> coll) {
2228 return c.retainAll(coll);
2229 }
2230 public void clear() {
2231 c.clear();
2232 }
2233
2234 public Iterator<E> iterator() {
2235 return new Iterator<E>() {
2236 private final Iterator<E> it = c.iterator();
2237 public boolean hasNext() { return it.hasNext(); }
2238 public E next() { return it.next(); }
2239 public void remove() { it.remove(); }};
2240 }
2241
2242 public boolean add(E e){
2243 typeCheck(e);
2244 return c.add(e);
2245 }
2246
2247 public boolean addAll(Collection<? extends E> coll) {
2248 /*
2249 * Dump coll into an array of the required type. This serves
2250 * three purposes: it insulates us from concurrent changes in
2251 * the contents of coll, it type-checks all of the elements in
2252 * coll, and it provides all-or-nothing semantics (which we
2253 * wouldn't get if we type-checked each element as we added it).
2254 */
2255 E[] a = null;
2256 try {
2257 a = coll.toArray(zeroLengthElementArray());
2258 } catch (ArrayStoreException e) {
2259 throw new ClassCastException();
2260 }
2261
2262 boolean result = false;
2263 for (E e : a)
2264 result |= c.add(e);
2265 return result;
2266 }
2267
2268 private E[] zeroLengthElementArray = null; // Lazily initialized
2269
2270 /*
2271 * We don't need locking or volatile, because it's OK if we create
2272 * several zeroLengthElementArrays, and they're immutable.
2273 */
2274 E[] zeroLengthElementArray() {
2275 if (zeroLengthElementArray == null)
2276 zeroLengthElementArray = (E[]) Array.newInstance(type, 0);
2277 return zeroLengthElementArray;
2278 }
2279 }
2280
2281 /**
2282 * Returns a dynamically typesafe view of the specified set.
2283 * Any attempt to insert an element of the wrong type will result in
2284 * an immediate <tt>ClassCastException</tt>. Assuming a set contains
2285 * no incorrectly typed elements prior to the time a dynamically typesafe
2286 * view is generated, and that all subsequent access to the set
2287 * takes place through the view, it is <i>guaranteed</i> that the
2288 * set cannot contain an incorrectly typed element.
2289 *
2290 * <p>A discussion of the use of dynamically typesafe views may be
2291 * found in the documentation for the {@link #checkedCollection checkedCollection}
2292 * method.
2293 *
2294 * <p>The returned set will be serializable if the specified set is
2295 * serializable.
2296 *
2297 * @param s the set for which a dynamically typesafe view is to be
2298 * returned
2299 * @param type the type of element that <tt>s</tt> is permitted to hold
2300 * @return a dynamically typesafe view of the specified set
2301 * @since 1.5
2302 */
2303 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2304 return new CheckedSet<E>(s, type);
2305 }
2306
2307 /**
2308 * @serial include
2309 */
2310 static class CheckedSet<E> extends CheckedCollection<E>
2311 implements Set<E>, Serializable
2312 {
2313 private static final long serialVersionUID = 4694047833775013803L;
2314
2315 CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2316
2317 public boolean equals(Object o) { return o == this || c.equals(o); }
2318 public int hashCode() { return c.hashCode(); }
2319 }
2320
2321 /**
2322 * Returns a dynamically typesafe view of the specified sorted set. Any
2323 * attempt to insert an element of the wrong type will result in an
2324 * immediate <tt>ClassCastException</tt>. Assuming a sorted set contains
2325 * no incorrectly typed elements prior to the time a dynamically typesafe
2326 * view is generated, and that all subsequent access to the sorted set
2327 * takes place through the view, it is <i>guaranteed</i> that the sorted
2328 * set cannot contain an incorrectly typed element.
2329 *
2330 * <p>A discussion of the use of dynamically typesafe views may be
2331 * found in the documentation for the {@link #checkedCollection checkedCollection}
2332 * method.
2333 *
2334 * <p>The returned sorted set will be serializable if the specified sorted
2335 * set is serializable.
2336 *
2337 * @param s the sorted set for which a dynamically typesafe view is to be
2338 * returned
2339 * @param type the type of element that <tt>s</tt> is permitted to hold
2340 * @return a dynamically typesafe view of the specified sorted set
2341 * @since 1.5
2342 */
2343 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
2344 Class<E> type) {
2345 return new CheckedSortedSet<E>(s, type);
2346 }
2347
2348 /**
2349 * @serial include
2350 */
2351 static class CheckedSortedSet<E> extends CheckedSet<E>
2352 implements SortedSet<E>, Serializable
2353 {
2354 private static final long serialVersionUID = 1599911165492914959L;
2355 private final SortedSet<E> ss;
2356
2357 CheckedSortedSet(SortedSet<E> s, Class<E> type) {
2358 super(s, type);
2359 ss = s;
2360 }
2361
2362 public Comparator<? super E> comparator() { return ss.comparator(); }
2363 public E first() { return ss.first(); }
2364 public E last() { return ss.last(); }
2365
2366 public SortedSet<E> subSet(E fromElement, E toElement) {
2367 return new CheckedSortedSet<E>(ss.subSet(fromElement,toElement),
2368 type);
2369 }
2370 public SortedSet<E> headSet(E toElement) {
2371 return new CheckedSortedSet<E>(ss.headSet(toElement), type);
2372 }
2373 public SortedSet<E> tailSet(E fromElement) {
2374 return new CheckedSortedSet<E>(ss.tailSet(fromElement), type);
2375 }
2376 }
2377
2378 /**
2379 * Returns a dynamically typesafe view of the specified list.
2380 * Any attempt to insert an element of the wrong type will result in
2381 * an immediate <tt>ClassCastException</tt>. Assuming a list contains
2382 * no incorrectly typed elements prior to the time a dynamically typesafe
2383 * view is generated, and that all subsequent access to the list
2384 * takes place through the view, it is <i>guaranteed</i> that the
2385 * list cannot contain an incorrectly typed element.
2386 *
2387 * <p>A discussion of the use of dynamically typesafe views may be
2388 * found in the documentation for the {@link #checkedCollection checkedCollection}
2389 * method.
2390 *
2391 * <p>The returned list will be serializable if the specified list is
2392 * serializable.
2393 *
2394 * @param list the list for which a dynamically typesafe view is to be
2395 * returned
2396 * @param type the type of element that <tt>list</tt> is permitted to hold
2397 * @return a dynamically typesafe view of the specified list
2398 * @since 1.5
2399 */
2400 public static <E> List<E> checkedList(List<E> list, Class<E> type) {
2401 return (list instanceof RandomAccess ?
2402 new CheckedRandomAccessList<E>(list, type) :
2403 new CheckedList<E>(list, type));
2404 }
2405
2406 /**
2407 * @serial include
2408 */
2409 static class CheckedList<E> extends CheckedCollection<E>
2410 implements List<E>
2411 {
2412 static final long serialVersionUID = 65247728283967356L;
2413 final List<E> list;
2414
2415 CheckedList(List<E> list, Class<E> type) {
2416 super(list, type);
2417 this.list = list;
2418 }
2419
2420 public boolean equals(Object o) { return o == this || list.equals(o); }
2421 public int hashCode() { return list.hashCode(); }
2422 public E get(int index) { return list.get(index); }
2423 public E remove(int index) { return list.remove(index); }
2424 public int indexOf(Object o) { return list.indexOf(o); }
2425 public int lastIndexOf(Object o) { return list.lastIndexOf(o); }
2426
2427 public E set(int index, E element) {
2428 typeCheck(element);
2429 return list.set(index, element);
2430 }
2431
2432 public void add(int index, E element) {
2433 typeCheck(element);
2434 list.add(index, element);
2435 }
2436
2437 public boolean addAll(int index, Collection<? extends E> c) {
2438 // See CheckCollection.addAll, above, for an explanation
2439 E[] a = null;
2440 try {
2441 a = c.toArray(zeroLengthElementArray());
2442 } catch (ArrayStoreException e) {
2443 throw new ClassCastException();
2444 }
2445
2446 return list.addAll(index, Arrays.asList(a));
2447 }
2448 public ListIterator<E> listIterator() { return listIterator(0); }
2449
2450 public ListIterator<E> listIterator(final int index) {
2451 return new ListIterator<E>() {
2452 ListIterator<E> i = list.listIterator(index);
2453
2454 public boolean hasNext() { return i.hasNext(); }
2455 public E next() { return i.next(); }
2456 public boolean hasPrevious() { return i.hasPrevious(); }
2457 public E previous() { return i.previous(); }
2458 public int nextIndex() { return i.nextIndex(); }
2459 public int previousIndex() { return i.previousIndex(); }
2460 public void remove() { i.remove(); }
2461
2462 public void set(E e) {
2463 typeCheck(e);
2464 i.set(e);
2465 }
2466
2467 public void add(E e) {
2468 typeCheck(e);
2469 i.add(e);
2470 }
2471 };
2472 }
2473
2474 public List<E> subList(int fromIndex, int toIndex) {
2475 return new CheckedList<E>(list.subList(fromIndex, toIndex), type);
2476 }
2477 }
2478
2479 /**
2480 * @serial include
2481 */
2482 static class CheckedRandomAccessList<E> extends CheckedList<E>
2483 implements RandomAccess
2484 {
2485 private static final long serialVersionUID = 1638200125423088369L;
2486
2487 CheckedRandomAccessList(List<E> list, Class<E> type) {
2488 super(list, type);
2489 }
2490
2491 public List<E> subList(int fromIndex, int toIndex) {
2492 return new CheckedRandomAccessList<E>(
2493 list.subList(fromIndex, toIndex), type);
2494 }
2495 }
2496
2497 /**
2498 * Returns a dynamically typesafe view of the specified map. Any attempt
2499 * to insert a mapping whose key or value have the wrong type will result
2500 * in an immediate <tt>ClassCastException</tt>. Similarly, any attempt to
2501 * modify the value currently associated with a key will result in an
2502 * immediate <tt>ClassCastException</tt>, whether the modification is
2503 * attempted directly through the map itself, or through a {@link
2504 * Map.Entry} instance obtained from the map's {@link Map#entrySet()
2505 * entry set} view.
2506 *
2507 * <p>Assuming a map contains no incorrectly typed keys or values
2508 * prior to the time a dynamically typesafe view is generated, and
2509 * that all subsequent access to the map takes place through the view
2510 * (or one of its collection views), it is <i>guaranteed</i> that the
2511 * map cannot contain an incorrectly typed key or value.
2512 *
2513 * <p>A discussion of the use of dynamically typesafe views may be
2514 * found in the documentation for the {@link #checkedCollection checkedCollection}
2515 * method.
2516 *
2517 * <p>The returned map will be serializable if the specified map is
2518 * serializable.
2519 *
2520 * @param m the map for which a dynamically typesafe view is to be
2521 * returned
2522 * @param keyType the type of key that <tt>m</tt> is permitted to hold
2523 * @param valueType the type of value that <tt>m</tt> is permitted to hold
2524 * @return a dynamically typesafe view of the specified map
2525 * @since 1.5
2526 */
2527 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType,
2528 Class<V> valueType) {
2529 return new CheckedMap<K,V>(m, keyType, valueType);
2530 }
2531
2532
2533 /**
2534 * @serial include
2535 */
2536 private static class CheckedMap<K,V> implements Map<K,V>,
2537 Serializable
2538 {
2539 private static final long serialVersionUID = 5742860141034234728L;
2540
2541 private final Map<K, V> m;
2542 final Class<K> keyType;
2543 final Class<V> valueType;
2544
2545 private void typeCheck(Object key, Object value) {
2546 if (!keyType.isInstance(key))
2547 throw new ClassCastException("Attempt to insert " +
2548 key.getClass() + " key into collection with key type "
2549 + keyType);
2550
2551 if (!valueType.isInstance(value))
2552 throw new ClassCastException("Attempt to insert " +
2553 value.getClass() +" value into collection with value type "
2554 + valueType);
2555 }
2556
2557 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
2558 if (m == null || keyType == null || valueType == null)
2559 throw new NullPointerException();
2560 this.m = m;
2561 this.keyType = keyType;
2562 this.valueType = valueType;
2563 }
2564
2565 public int size() { return m.size(); }
2566 public boolean isEmpty() { return m.isEmpty(); }
2567 public boolean containsKey(Object key) { return m.containsKey(key); }
2568 public boolean containsValue(Object v) { return m.containsValue(v); }
2569 public V get(Object key) { return m.get(key); }
2570 public V remove(Object key) { return m.remove(key); }
2571 public void clear() { m.clear(); }
2572 public Set<K> keySet() { return m.keySet(); }
2573 public Collection<V> values() { return m.values(); }
2574 public boolean equals(Object o) { return o == this || m.equals(o); }
2575 public int hashCode() { return m.hashCode(); }
2576 public String toString() { return m.toString(); }
2577
2578 public V put(K key, V value) {
2579 typeCheck(key, value);
2580 return m.put(key, value);
2581 }
2582
2583 public void putAll(Map<? extends K, ? extends V> t) {
2584 // See CheckCollection.addAll, above, for an explanation
2585 K[] keys = null;
2586 try {
2587 keys = t.keySet().toArray(zeroLengthKeyArray());
2588 } catch (ArrayStoreException e) {
2589 throw new ClassCastException();
2590 }
2591 V[] values = null;
2592 try {
2593 values = t.values().toArray(zeroLengthValueArray());
2594 } catch (ArrayStoreException e) {
2595 throw new ClassCastException();
2596 }
2597
2598 if (keys.length != values.length)
2599 throw new ConcurrentModificationException();
2600
2601 for (int i = 0; i < keys.length; i++)
2602 m.put(keys[i], values[i]);
2603 }
2604
2605 // Lazily initialized
2606 private K[] zeroLengthKeyArray = null;
2607 private V[] zeroLengthValueArray = null;
2608
2609 /*
2610 * We don't need locking or volatile, because it's OK if we create
2611 * several zeroLengthValueArrays, and they're immutable.
2612 */
2613 private K[] zeroLengthKeyArray() {
2614 if (zeroLengthKeyArray == null)
2615 zeroLengthKeyArray = (K[]) Array.newInstance(keyType, 0);
2616 return zeroLengthKeyArray;
2617 }
2618 private V[] zeroLengthValueArray() {
2619 if (zeroLengthValueArray == null)
2620 zeroLengthValueArray = (V[]) Array.newInstance(valueType, 0);
2621 return zeroLengthValueArray;
2622 }
2623
2624 private transient Set<Map.Entry<K,V>> entrySet = null;
2625
2626 public Set<Map.Entry<K,V>> entrySet() {
2627 if (entrySet==null)
2628 entrySet = new CheckedEntrySet<K,V>(m.entrySet(), valueType);
2629 return entrySet;
2630 }
2631
2632 /**
2633 * We need this class in addition to CheckedSet as Map.Entry permits
2634 * modification of the backing Map via the setValue operation. This
2635 * class is subtle: there are many possible attacks that must be
2636 * thwarted.
2637 *
2638 * @serial exclude
2639 */
2640 static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> {
2641 Set<Map.Entry<K,V>> s;
2642 Class<V> valueType;
2643
2644 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
2645 this.s = s;
2646 this.valueType = valueType;
2647 }
2648
2649 public int size() { return s.size(); }
2650 public boolean isEmpty() { return s.isEmpty(); }
2651 public String toString() { return s.toString(); }
2652 public int hashCode() { return s.hashCode(); }
2653 public boolean remove(Object o) { return s.remove(o); }
2654 public boolean removeAll(Collection<?> coll) {
2655 return s.removeAll(coll);
2656 }
2657 public boolean retainAll(Collection<?> coll) {
2658 return s.retainAll(coll);
2659 }
2660 public void clear() {
2661 s.clear();
2662 }
2663
2664 public boolean add(Map.Entry<K, V> e){
2665 throw new UnsupportedOperationException();
2666 }
2667 public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
2668 throw new UnsupportedOperationException();
2669 }
2670
2671
2672 public Iterator<Map.Entry<K,V>> iterator() {
2673 return new Iterator<Map.Entry<K,V>>() {
2674 Iterator<Map.Entry<K, V>> i = s.iterator();
2675
2676 public boolean hasNext() { return i.hasNext(); }
2677 public void remove() { i.remove(); }
2678
2679 public Map.Entry<K,V> next() {
2680 return new CheckedEntry<K,V>(i.next(), valueType);
2681 }
2682 };
2683 }
2684
2685 public Object[] toArray() {
2686 Object[] source = s.toArray();
2687
2688 /*
2689 * Ensure that we don't get an ArrayStoreException even if
2690 * s.toArray returns an array of something other than Object
2691 */
2692 Object[] dest = (CheckedEntry.class.isInstance(
2693 source.getClass().getComponentType()) ? source :
2694 new Object[source.length]);
2695
2696 for (int i = 0; i < source.length; i++)
2697 dest[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)source[i],
2698 valueType);
2699 return dest;
2700 }
2701
2702 public <T> T[] toArray(T[] a) {
2703 // We don't pass a to s.toArray, to avoid window of
2704 // vulnerability wherein an unscrupulous multithreaded client
2705 // could get his hands on raw (unwrapped) Entries from s.
2706 Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
2707
2708 for (int i=0; i<arr.length; i++)
2709 arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i],
2710 valueType);
2711 if (arr.length > a.length)
2712 return (T[])arr;
2713
2714 System.arraycopy(arr, 0, a, 0, arr.length);
2715 if (a.length > arr.length)
2716 a[arr.length] = null;
2717 return a;
2718 }
2719
2720 /**
2721 * This method is overridden to protect the backing set against
2722 * an object with a nefarious equals function that senses
2723 * that the equality-candidate is Map.Entry and calls its
2724 * setValue method.
2725 */
2726 public boolean contains(Object o) {
2727 if (!(o instanceof Map.Entry))
2728 return false;
2729 return s.contains(
2730 new CheckedEntry<K,V>((Map.Entry<K,V>) o, valueType));
2731 }
2732
2733 /**
2734 * The next two methods are overridden to protect against
2735 * an unscrupulous collection whose contains(Object o) method
2736 * senses when o is a Map.Entry, and calls o.setValue.
2737 */
2738 public boolean containsAll(Collection<?> coll) {
2739 Iterator<?> e = coll.iterator();
2740 while (e.hasNext())
2741 if (!contains(e.next())) // Invokes safe contains() above
2742 return false;
2743 return true;
2744 }
2745
2746 public boolean equals(Object o) {
2747 if (o == this)
2748 return true;
2749 if (!(o instanceof Set))
2750 return false;
2751 Set<?> that = (Set<?>) o;
2752 if (that.size() != s.size())
2753 return false;
2754 return containsAll(that); // Invokes safe containsAll() above
2755 }
2756
2757 /**
2758 * This "wrapper class" serves two purposes: it prevents
2759 * the client from modifying the backing Map, by short-circuiting
2760 * the setValue method, and it protects the backing Map against
2761 * an ill-behaved Map.Entry that attempts to modify another
2762 * Map Entry when asked to perform an equality check.
2763 */
2764 private static class CheckedEntry<K,V> implements Map.Entry<K,V> {
2765 private Map.Entry<K, V> e;
2766 private Class<V> valueType;
2767
2768 CheckedEntry(Map.Entry<K, V> e, Class<V> valueType) {
2769 this.e = e;
2770 this.valueType = valueType;
2771 }
2772
2773 public K getKey() { return e.getKey(); }
2774 public V getValue() { return e.getValue(); }
2775 public int hashCode() { return e.hashCode(); }
2776 public String toString() { return e.toString(); }
2777
2778
2779 public V setValue(V value) {
2780 if (!valueType.isInstance(value))
2781 throw new ClassCastException("Attempt to insert " +
2782 value.getClass() +
2783 " value into collection with value type " + valueType);
2784 return e.setValue(value);
2785 }
2786
2787 public boolean equals(Object o) {
2788 if (!(o instanceof Map.Entry))
2789 return false;
2790 Map.Entry t = (Map.Entry)o;
2791 return eq(e.getKey(), t.getKey()) &&
2792 eq(e.getValue(), t.getValue());
2793 }
2794 }
2795 }
2796 }
2797
2798 /**
2799 * Returns a dynamically typesafe view of the specified sorted map. Any
2800 * attempt to insert a mapping whose key or value have the wrong type will
2801 * result in an immediate <tt>ClassCastException</tt>. Similarly, any
2802 * attempt to modify the value currently associated with a key will result
2803 * in an immediate <tt>ClassCastException</tt>, whether the modification
2804 * is attempted directly through the map itself, or through a {@link
2805 * Map.Entry} instance obtained from the map's {@link Map#entrySet() entry
2806 * set} view.
2807 *
2808 * <p>Assuming a map contains no incorrectly typed keys or values
2809 * prior to the time a dynamically typesafe view is generated, and
2810 * that all subsequent access to the map takes place through the view
2811 * (or one of its collection views), it is <i>guaranteed</i> that the
2812 * map cannot contain an incorrectly typed key or value.
2813 *
2814 * <p>A discussion of the use of dynamically typesafe views may be
2815 * found in the documentation for the {@link #checkedCollection checkedCollection}
2816 * method.
2817 *
2818 * <p>The returned map will be serializable if the specified map is
2819 * serializable.
2820 *
2821 * @param m the map for which a dynamically typesafe view is to be
2822 * returned
2823 * @param keyType the type of key that <tt>m</tt> is permitted to hold
2824 * @param valueType the type of value that <tt>m</tt> is permitted to hold
2825 * @return a dynamically typesafe view of the specified map
2826 * @since 1.5
2827 */
2828 public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m,
2829 Class<K> keyType,
2830 Class<V> valueType) {
2831 return new CheckedSortedMap<K,V>(m, keyType, valueType);
2832 }
2833
2834 /**
2835 * @serial include
2836 */
2837 static class CheckedSortedMap<K,V> extends CheckedMap<K,V>
2838 implements SortedMap<K,V>, Serializable
2839 {
2840 private static final long serialVersionUID = 1599671320688067438L;
2841
2842 private final SortedMap<K, V> sm;
2843
2844 CheckedSortedMap(SortedMap<K, V> m,
2845 Class<K> keyType, Class<V> valueType) {
2846 super(m, keyType, valueType);
2847 sm = m;
2848 }
2849
2850 public Comparator<? super K> comparator() { return sm.comparator(); }
2851 public K firstKey() { return sm.firstKey(); }
2852 public K lastKey() { return sm.lastKey(); }
2853
2854 public SortedMap<K,V> subMap(K fromKey, K toKey) {
2855 return new CheckedSortedMap<K,V>(sm.subMap(fromKey, toKey),
2856 keyType, valueType);
2857 }
2858
2859 public SortedMap<K,V> headMap(K toKey) {
2860 return new CheckedSortedMap<K,V>(sm.headMap(toKey),
2861 keyType, valueType);
2862 }
2863
2864 public SortedMap<K,V> tailMap(K fromKey) {
2865 return new CheckedSortedMap<K,V>(sm.tailMap(fromKey),
2866 keyType, valueType);
2867 }
2868 }
2869
2870 // Miscellaneous
2871
2872 /**
2873 * The empty set (immutable). This set is serializable.
2874 *
2875 * @see #emptySet()
2876 */
2877 public static final Set EMPTY_SET = new EmptySet();
2878
2879 /**
2880 * Returns the empty set (immutable). This set is serializable.
2881 * Unlike the like-named field, this method is parameterized.
2882 *
2883 * <p>This example illustrates the type-safe way to obtain an empty set:
2884 * <pre>
2885 * Set<String> s = Collections.emptySet();
2886 * </pre>
2887 * Implementation note: Implementations of this method need not
2888 * create a separate <tt>Set</tt> object for each call. Using this
2889 * method is likely to have comparable cost to using the like-named
2890 * field. (Unlike this method, the field does not provide type safety.)
2891 *
2892 * @see #EMPTY_SET
2893 * @since 1.5
2894 */
2895 public static final <T> Set<T> emptySet() {
2896 return (Set<T>) EMPTY_SET;
2897 }
2898
2899 /**
2900 * @serial include
2901 */
2902 private static class EmptySet extends AbstractSet<Object> implements Serializable {
2903 // use serialVersionUID from JDK 1.2.2 for interoperability
2904 private static final long serialVersionUID = 1582296315990362920L;
2905
2906 public Iterator<Object> iterator() {
2907 return new Iterator<Object>() {
2908 public boolean hasNext() {
2909 return false;
2910 }
2911 public Object next() {
2912 throw new NoSuchElementException();
2913 }
2914 public void remove() {
2915 throw new UnsupportedOperationException();
2916 }
2917 };
2918 }
2919
2920 public int size() {return 0;}
2921
2922 public boolean contains(Object obj) {return false;}
2923
2924 // Preserves singleton property
2925 private Object readResolve() {
2926 return EMPTY_SET;
2927 }
2928 }
2929
2930 /**
2931 * The empty list (immutable). This list is serializable.
2932 *
2933 * @see #emptyList()
2934 */
2935 public static final List EMPTY_LIST = new EmptyList();
2936
2937 /**
2938 * Returns the empty list (immutable). This list is serializable.
2939 *
2940 * <p>This example illustrates the type-safe way to obtain an empty list:
2941 * <pre>
2942 * List<String> s = Collections.emptyList();
2943 * </pre>
2944 * Implementation note: Implementations of this method need not
2945 * create a separate <tt>List</tt> object for each call. Using this
2946 * method is likely to have comparable cost to using the like-named
2947 * field. (Unlike this method, the field does not provide type safety.)
2948 *
2949 * @see #EMPTY_LIST
2950 * @since 1.5
2951 */
2952 public static final <T> List<T> emptyList() {
2953 return (List<T>) EMPTY_LIST;
2954 }
2955
2956 /**
2957 * @serial include
2958 */
2959 private static class EmptyList
2960 extends AbstractList<Object>
2961 implements RandomAccess, Serializable {
2962 // use serialVersionUID from JDK 1.2.2 for interoperability
2963 private static final long serialVersionUID = 8842843931221139166L;
2964
2965 public int size() {return 0;}
2966
2967 public boolean contains(Object obj) {return false;}
2968
2969 public Object get(int index) {
2970 throw new IndexOutOfBoundsException("Index: "+index);
2971 }
2972
2973 // Preserves singleton property
2974 private Object readResolve() {
2975 return EMPTY_LIST;
2976 }
2977 }
2978
2979 /**
2980 * The empty map (immutable). This map is serializable.
2981 *
2982 * @see #emptyMap()
2983 * @since 1.3
2984 */
2985 public static final Map EMPTY_MAP = new EmptyMap();
2986
2987 /**
2988 * Returns the empty map (immutable). This map is serializable.
2989 *
2990 * <p>This example illustrates the type-safe way to obtain an empty set:
2991 * <pre>
2992 * Map<String, Date> s = Collections.emptyMap();
2993 * </pre>
2994 * Implementation note: Implementations of this method need not
2995 * create a separate <tt>Map</tt> object for each call. Using this
2996 * method is likely to have comparable cost to using the like-named
2997 * field. (Unlike this method, the field does not provide type safety.)
2998 *
2999 * @see #EMPTY_MAP
3000 * @since 1.5
3001 */
3002 public static final <K,V> Map<K,V> emptyMap() {
3003 return (Map<K,V>) EMPTY_MAP;
3004 }
3005
3006 private static class EmptyMap
3007 extends AbstractMap<Object,Object>
3008 implements Serializable {
3009
3010 private static final long serialVersionUID = 6428348081105594320L;
3011
3012 public int size() {return 0;}
3013
3014 public boolean isEmpty() {return true;}
3015
3016 public boolean containsKey(Object key) {return false;}
3017
3018 public boolean containsValue(Object value) {return false;}
3019
3020 public Object get(Object key) {return null;}
3021
3022 public Set<Object> keySet() {return Collections.<Object>emptySet();}
3023
3024 public Collection<Object> values() {return Collections.<Object>emptySet();}
3025
3026 public Set<Map.Entry<Object,Object>> entrySet() {
3027 return Collections.emptySet();
3028 }
3029
3030 public boolean equals(Object o) {
3031 return (o instanceof Map) && ((Map)o).size()==0;
3032 }
3033
3034 public int hashCode() {return 0;}
3035
3036 // Preserves singleton property
3037 private Object readResolve() {
3038 return EMPTY_MAP;
3039 }
3040 }
3041
3042 /**
3043 * Returns an immutable set containing only the specified object.
3044 * The returned set is serializable.
3045 *
3046 * @param o the sole object to be stored in the returned set.
3047 * @return an immutable set containing only the specified object.
3048 */
3049 public static <T> Set<T> singleton(T o) {
3050 return new SingletonSet<T>(o);
3051 }
3052
3053 /**
3054 * @serial include
3055 */
3056 private static class SingletonSet<E>
3057 extends AbstractSet<E>
3058 implements Serializable
3059 {
3060 // use serialVersionUID from JDK 1.2.2 for interoperability
3061 private static final long serialVersionUID = 3193687207550431679L;
3062
3063 final private E element;
3064
3065 SingletonSet(E e) {element = e;}
3066
3067 public Iterator<E> iterator() {
3068 return new Iterator<E>() {
3069 private boolean hasNext = true;
3070 public boolean hasNext() {
3071 return hasNext;
3072 }
3073 public E next() {
3074 if (hasNext) {
3075 hasNext = false;
3076 return element;
3077 }
3078 throw new NoSuchElementException();
3079 }
3080 public void remove() {
3081 throw new UnsupportedOperationException();
3082 }
3083 };
3084 }
3085
3086 public int size() {return 1;}
3087
3088 public boolean contains(Object o) {return eq(o, element);}
3089 }
3090
3091 /**
3092 * Returns an immutable list containing only the specified object.
3093 * The returned list is serializable.
3094 *
3095 * @param o the sole object to be stored in the returned list.
3096 * @return an immutable list containing only the specified object.
3097 * @since 1.3
3098 */
3099 public static <T> List<T> singletonList(T o) {
3100 return new SingletonList<T>(o);
3101 }
3102
3103 private static class SingletonList<E>
3104 extends AbstractList<E>
3105 implements RandomAccess, Serializable {
3106
3107 static final long serialVersionUID = 3093736618740652951L;
3108
3109 private final E element;
3110
3111 SingletonList(E obj) {element = obj;}
3112
3113 public int size() {return 1;}
3114
3115 public boolean contains(Object obj) {return eq(obj, element);}
3116
3117 public E get(int index) {
3118 if (index != 0)
3119 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
3120 return element;
3121 }
3122 }
3123
3124 /**
3125 * Returns an immutable map, mapping only the specified key to the
3126 * specified value. The returned map is serializable.
3127 *
3128 * @param key the sole key to be stored in the returned map.
3129 * @param value the value to which the returned map maps <tt>key</tt>.
3130 * @return an immutable map containing only the specified key-value
3131 * mapping.
3132 * @since 1.3
3133 */
3134 public static <K,V> Map<K,V> singletonMap(K key, V value) {
3135 return new SingletonMap<K,V>(key, value);
3136 }
3137
3138 private static class SingletonMap<K,V>
3139 extends AbstractMap<K,V>
3140 implements Serializable {
3141 private static final long serialVersionUID = -6979724477215052911L;
3142
3143 private final K k;
3144 private final V v;
3145
3146 SingletonMap(K key, V value) {
3147 k = key;
3148 v = value;
3149 }
3150
3151 public int size() {return 1;}
3152
3153 public boolean isEmpty() {return false;}
3154
3155 public boolean containsKey(Object key) {return eq(key, k);}
3156
3157 public boolean containsValue(Object value) {return eq(value, v);}
3158
3159 public V get(Object key) {return (eq(key, k) ? v : null);}
3160
3161 private transient Set<K> keySet = null;
3162 private transient Set<Map.Entry<K,V>> entrySet = null;
3163 private transient Collection<V> values = null;
3164
3165 public Set<K> keySet() {
3166 if (keySet==null)
3167 keySet = singleton(k);
3168 return keySet;
3169 }
3170
3171 public Set<Map.Entry<K,V>> entrySet() {
3172 if (entrySet==null)
3173 entrySet = Collections.<Map.Entry<K,V>>singleton(
3174 new SimpleImmutableEntry<K,V>(k, v));
3175 return entrySet;
3176 }
3177
3178 public Collection<V> values() {
3179 if (values==null)
3180 values = singleton(v);
3181 return values;
3182 }
3183
3184 }
3185
3186 /**
3187 * Returns an immutable list consisting of <tt>n</tt> copies of the
3188 * specified object. The newly allocated data object is tiny (it contains
3189 * a single reference to the data object). This method is useful in
3190 * combination with the <tt>List.addAll</tt> method to grow lists.
3191 * The returned list is serializable.
3192 *
3193 * @param n the number of elements in the returned list.
3194 * @param o the element to appear repeatedly in the returned list.
3195 * @return an immutable list consisting of <tt>n</tt> copies of the
3196 * specified object.
3197 * @throws IllegalArgumentException if n < 0.
3198 * @see List#addAll(Collection)
3199 * @see List#addAll(int, Collection)
3200 */
3201 public static <T> List<T> nCopies(int n, T o) {
3202 if (n < 0)
3203 throw new IllegalArgumentException("List length = " + n);
3204 return new CopiesList<T>(n, o);
3205 }
3206
3207 /**
3208 * @serial include
3209 */
3210 private static class CopiesList<E>
3211 extends AbstractList<E>
3212 implements RandomAccess, Serializable
3213 {
3214 static final long serialVersionUID = 2739099268398711800L;
3215
3216 final int n;
3217 final E element;
3218
3219 CopiesList(int n, E e) {
3220 assert n >= 0;
3221 this.n = n;
3222 element = e;
3223 }
3224
3225 public int size() {
3226 return n;
3227 }
3228
3229 public boolean contains(Object obj) {
3230 return n != 0 && eq(obj, element);
3231 }
3232
3233 public int indexOf(Object o) {
3234 return contains(o) ? 0 : -1;
3235 }
3236
3237 public int lastIndexOf(Object o) {
3238 return contains(o) ? n - 1 : -1;
3239 }
3240
3241 public E get(int index) {
3242 if (index < 0 || index >= n)
3243 throw new IndexOutOfBoundsException("Index: "+index+
3244 ", Size: "+n);
3245 return element;
3246 }
3247
3248 public Object[] toArray() {
3249 final Object[] a = new Object[n];
3250 if (element != null)
3251 Arrays.fill(a, 0, n, element);
3252 return a;
3253 }
3254
3255 public <T> T[] toArray(T[] a) {
3256 final int n = this.n;
3257 if (a.length < n) {
3258 a = (T[])java.lang.reflect.Array
3259 .newInstance(a.getClass().getComponentType(), n);
3260 if (element != null)
3261 Arrays.fill(a, 0, n, element);
3262 } else {
3263 Arrays.fill(a, 0, n, element);
3264 if (a.length > n)
3265 a[n] = null;
3266 }
3267 return a;
3268 }
3269
3270 public List<E> subList(int fromIndex, int toIndex) {
3271 if (fromIndex < 0)
3272 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3273 if (toIndex > n)
3274 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
3275 if (fromIndex > toIndex)
3276 throw new IllegalArgumentException("fromIndex(" + fromIndex +
3277 ") > toIndex(" + toIndex + ")");
3278 return new CopiesList(toIndex - fromIndex, element);
3279 }
3280 }
3281
3282 /**
3283 * Returns a comparator that imposes the reverse of the <i>natural
3284 * ordering</i> on a collection of objects that implement the
3285 * <tt>Comparable</tt> interface. (The natural ordering is the ordering
3286 * imposed by the objects' own <tt>compareTo</tt> method.) This enables a
3287 * simple idiom for sorting (or maintaining) collections (or arrays) of
3288 * objects that implement the <tt>Comparable</tt> interface in
3289 * reverse-natural-order. For example, suppose a is an array of
3290 * strings. Then: <pre>
3291 * Arrays.sort(a, Collections.reverseOrder());
3292 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
3293 *
3294 * The returned comparator is serializable.
3295 *
3296 * @return a comparator that imposes the reverse of the <i>natural
3297 * ordering</i> on a collection of objects that implement
3298 * the <tt>Comparable</tt> interface.
3299 * @see Comparable
3300 */
3301 public static <T> Comparator<T> reverseOrder() {
3302 return (Comparator<T>) REVERSE_ORDER;
3303 }
3304
3305 private static final Comparator REVERSE_ORDER = new ReverseComparator();
3306
3307 /**
3308 * @serial include
3309 */
3310 private static class ReverseComparator<T>
3311 implements Comparator<Comparable<Object>>, Serializable {
3312
3313 // use serialVersionUID from JDK 1.2.2 for interoperability
3314 private static final long serialVersionUID = 7207038068494060240L;
3315
3316 public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3317 return c2.compareTo(c1);
3318 }
3319
3320 private Object readResolve() { return reverseOrder(); }
3321 }
3322
3323 /**
3324 * Returns a comparator that imposes the reverse ordering of the specified
3325 * comparator. If the specified comparator is null, this method is
3326 * equivalent to {@link #reverseOrder()} (in other words, it returns a
3327 * comparator that imposes the reverse of the <i>natural ordering</i> on a
3328 * collection of objects that implement the Comparable interface).
3329 *
3330 * <p>The returned comparator is serializable (assuming the specified
3331 * comparator is also serializable or null).
3332 *
3333 * @return a comparator that imposes the reverse ordering of the
3334 * specified comparator.
3335 * @since 1.5
3336 */
3337 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3338 if (cmp == null)
3339 return reverseOrder();
3340
3341 return new ReverseComparator2<T>(cmp);
3342 }
3343
3344 /**
3345 * @serial include
3346 */
3347 private static class ReverseComparator2<T> implements Comparator<T>,
3348 Serializable
3349 {
3350 private static final long serialVersionUID = 4374092139857L;
3351
3352 /**
3353 * The comparator specified in the static factory. This will never
3354 * be null, as the static factory returns a ReverseComparator
3355 * instance if its argument is null.
3356 *
3357 * @serial
3358 */
3359 private Comparator<T> cmp;
3360
3361 ReverseComparator2(Comparator<T> cmp) {
3362 assert cmp != null;
3363 this.cmp = cmp;
3364 }
3365
3366 public int compare(T t1, T t2) {
3367 return cmp.compare(t2, t1);
3368 }
3369 }
3370
3371 /**
3372 * Returns an enumeration over the specified collection. This provides
3373 * interoperability with legacy APIs that require an enumeration
3374 * as input.
3375 *
3376 * @param c the collection for which an enumeration is to be returned.
3377 * @return an enumeration over the specified collection.
3378 * @see Enumeration
3379 */
3380 public static <T> Enumeration<T> enumeration(final Collection<T> c) {
3381 return new Enumeration<T>() {
3382 Iterator<T> i = c.iterator();
3383
3384 public boolean hasMoreElements() {
3385 return i.hasNext();
3386 }
3387
3388 public T nextElement() {
3389 return i.next();
3390 }
3391 };
3392 }
3393
3394 /**
3395 * Returns an array list containing the elements returned by the
3396 * specified enumeration in the order they are returned by the
3397 * enumeration. This method provides interoperability between
3398 * legacy APIs that return enumerations and new APIs that require
3399 * collections.
3400 *
3401 * @param e enumeration providing elements for the returned
3402 * array list
3403 * @return an array list containing the elements returned
3404 * by the specified enumeration.
3405 * @since 1.4
3406 * @see Enumeration
3407 * @see ArrayList
3408 */
3409 public static <T> ArrayList<T> list(Enumeration<T> e) {
3410 ArrayList<T> l = new ArrayList<T>();
3411 while (e.hasMoreElements())
3412 l.add(e.nextElement());
3413 return l;
3414 }
3415
3416 /**
3417 * Returns true if the specified arguments are equal, or both null.
3418 */
3419 private static boolean eq(Object o1, Object o2) {
3420 return (o1==null ? o2==null : o1.equals(o2));
3421 }
3422
3423 /**
3424 * Returns the number of elements in the specified collection equal to the
3425 * specified object. More formally, returns the number of elements
3426 * <tt>e</tt> in the collection such that
3427 * <tt>(o == null ? e == null : o.equals(e))</tt>.
3428 *
3429 * @param c the collection in which to determine the frequency
3430 * of <tt>o</tt>
3431 * @param o the object whose frequency is to be determined
3432 * @throws NullPointerException if <tt>c</tt> is null
3433 * @since 1.5
3434 */
3435 public static int frequency(Collection<?> c, Object o) {
3436 int result = 0;
3437 if (o == null) {
3438 for (Object e : c)
3439 if (e == null)
3440 result++;
3441 } else {
3442 for (Object e : c)
3443 if (o.equals(e))
3444 result++;
3445 }
3446 return result;
3447 }
3448
3449 /**
3450 * Returns <tt>true</tt> if the two specified collections have no
3451 * elements in common.
3452 *
3453 * <p>Care must be exercised if this method is used on collections that
3454 * do not comply with the general contract for <tt>Collection</tt>.
3455 * Implementations may elect to iterate over either collection and test
3456 * for containment in the other collection (or to perform any equivalent
3457 * computation). If either collection uses a nonstandard equality test
3458 * (as does a {@link SortedSet} whose ordering is not <i>compatible with
3459 * equals</i>, or the key set of an {@link IdentityHashMap}), both
3460 * collections must use the same nonstandard equality test, or the
3461 * result of this method is undefined.
3462 *
3463 * <p>Note that it is permissible to pass the same collection in both
3464 * parameters, in which case the method will return true if and only if
3465 * the collection is empty.
3466 *
3467 * @param c1 a collection
3468 * @param c2 a collection
3469 * @throws NullPointerException if either collection is null
3470 * @since 1.5
3471 */
3472 public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
3473 /*
3474 * We're going to iterate through c1 and test for inclusion in c2.
3475 * If c1 is a Set and c2 isn't, swap the collections. Otherwise,
3476 * place the shorter collection in c1. Hopefully this heuristic
3477 * will minimize the cost of the operation.
3478 */
3479 if ((c1 instanceof Set) && !(c2 instanceof Set) ||
3480 (c1.size() > c2.size())) {
3481 Collection<?> tmp = c1;
3482 c1 = c2;
3483 c2 = tmp;
3484 }
3485
3486 for (Object e : c1)
3487 if (c2.contains(e))
3488 return false;
3489 return true;
3490 }
3491
3492 /**
3493 * Adds all of the specified elements to the specified collection.
3494 * Elements to be added may be specified individually or as an array.
3495 * The behavior of this convenience method is identical to that of
3496 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely
3497 * to run significantly faster under most implementations.
3498 *
3499 * <p>When elements are specified individually, this method provides a
3500 * convenient way to add a few elements to an existing collection:
3501 * <pre>
3502 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
3503 * </pre>
3504 *
3505 * @param c the collection into which <tt>elements</tt> are to be inserted
3506 * @param elements the elements to insert into <tt>c</tt>
3507 * @return <tt>true</tt> if the collection changed as a result of the call
3508 * @throws UnsupportedOperationException if <tt>c</tt> does not support
3509 * the <tt>add</tt> operation
3510 * @throws NullPointerException if <tt>elements</tt> contains one or more
3511 * null values and <tt>c</tt> does not permit null elements, or
3512 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
3513 * @throws IllegalArgumentException if some property of a value in
3514 * <tt>elements</tt> prevents it from being added to <tt>c</tt>
3515 * @see Collection#addAll(Collection)
3516 * @since 1.5
3517 */
3518 public static <T> boolean addAll(Collection<? super T> c, T... elements) {
3519 boolean result = false;
3520 for (T element : elements)
3521 result |= c.add(element);
3522 return result;
3523 }
3524
3525 /**
3526 * Returns a set backed by the specified map. The resulting set displays
3527 * the same ordering, concurrency, and performance characteristics as the
3528 * backing map. In essence, this factory method provides a {@link Set}
3529 * implementation corresponding to any {@link Map} implementation. There
3530 * is no need to use this method on a {@link Map} implementation that
3531 * already has a corresponding {@link Set} implementation (such as {@link
3532 * HashMap} or {@link TreeMap}).
3533 *
3534 * <p>Each method invocation on the set returned by this method results in
3535 * exactly one method invocation on the backing map or its <tt>keySet</tt>
3536 * view, with one exception. The <tt>addAll</tt> method is implemented
3537 * as a sequence of <tt>put</tt> invocations on the backing map.
3538 *
3539 * <p>The specified map must be empty at the time this method is invoked,
3540 * and should not be accessed directly after this method returns. These
3541 * conditions are ensured if the map is created empty, passed directly
3542 * to this method, and no reference to the map is retained, as illustrated
3543 * in the following code fragment:
3544 * <pre>
3545 * Set<Object> weakHashSet = Collections.newSetFromMap(
3546 * new WeakHashMap<Object, Boolean>());
3547 * </pre>
3548 *
3549 * @param map the backing map
3550 * @return the set backed by the map
3551 * @throws IllegalArgumentException if <tt>map</tt> is not empty
3552 * @since 1.6
3553 */
3554 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
3555 return new SetFromMap<E>(map);
3556 }
3557
3558 private static class SetFromMap<E> extends AbstractSet<E>
3559 implements Set<E>, Serializable
3560 {
3561 private final Map<E, Boolean> m; // The backing map
3562 private transient Set<E> s; // Its keySet
3563
3564 SetFromMap(Map<E, Boolean> map) {
3565 if (!map.isEmpty())
3566 throw new IllegalArgumentException("Map is non-empty");
3567 m = map;
3568 s = map.keySet();
3569 }
3570
3571 public void clear() { m.clear(); }
3572 public int size() { return m.size(); }
3573 public boolean isEmpty() { return m.isEmpty(); }
3574 public boolean contains(Object o) { return m.containsKey(o); }
3575 public boolean remove(Object o) { return m.remove(o) != null; }
3576 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3577 public Iterator<E> iterator() { return s.iterator(); }
3578 public Object[] toArray() { return s.toArray(); }
3579 public <T> T[] toArray(T[] a) { return s.toArray(a); }
3580 public String toString() { return s.toString(); }
3581 public int hashCode() { return s.hashCode(); }
3582 public boolean equals(Object o) { return o == this || s.equals(o); }
3583 public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3584 public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
3585 public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
3586 // addAll is the only inherited implementation
3587
3588 private static final long serialVersionUID = 2454657854757543876L;
3589
3590 private void readObject(java.io.ObjectInputStream stream)
3591 throws IOException, ClassNotFoundException
3592 {
3593 stream.defaultReadObject();
3594 s = m.keySet();
3595 }
3596 }
3597
3598 /**
3599 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
3600 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
3601 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
3602 * view can be useful when you would like to use a method
3603 * requiring a <tt>Queue</tt> but you need Lifo ordering.
3604 *
3605 * <p>Each method invocation on the queue returned by this method
3606 * results in exactly one method invocation on the backing deque, with
3607 * one exception. The {@link Queue#addAll addAll} method is
3608 * implemented as a sequence of {@link Deque#addFirst addFirst}
3609 * invocations on the backing deque.
3610 *
3611 * @param deque the deque
3612 * @return the queue
3613 * @since 1.6
3614 */
3615 public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
3616 return new AsLIFOQueue<T>(deque);
3617 }
3618
3619 static class AsLIFOQueue<E> extends AbstractQueue<E>
3620 implements Queue<E>, Serializable {
3621 private static final long serialVersionUID = 1802017725587941708L;
3622 private final Deque<E> q;
3623 AsLIFOQueue(Deque<E> q) { this.q = q; }
3624 public boolean add(E e) { q.addFirst(e); return true; }
3625 public boolean offer(E e) { return q.offerFirst(e); }
3626 public E poll() { return q.pollFirst(); }
3627 public E remove() { return q.removeFirst(); }
3628 public E peek() { return q.peekFirst(); }
3629 public E element() { return q.getFirst(); }
3630 public void clear() { q.clear(); }
3631 public int size() { return q.size(); }
3632 public boolean isEmpty() { return q.isEmpty(); }
3633 public boolean contains(Object o) { return q.contains(o); }
3634 public boolean remove(Object o) { return q.remove(o); }
3635 public Iterator<E> iterator() { return q.iterator(); }
3636 public Object[] toArray() { return q.toArray(); }
3637 public <T> T[] toArray(T[] a) { return q.toArray(a); }
3638 public String toString() { return q.toString(); }
3639 public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3640 public boolean removeAll(Collection<?> c) {return q.removeAll(c);}
3641 public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
3642 // We use inherited addAll; forwarding addAll would be wrong
3643 }
3644}
3645