133 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
134 * Sorting and Information Theoretic Complexity", in Proceedings of the
135 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
136 * January 1993.
137 *
138 * <p>This implementation dumps the specified list into an array, sorts
139 * the array, and iterates over the list resetting each element
140 * from the corresponding position in the array. This avoids the
141 * n<sup>2</sup> log(n) performance that would result from attempting
142 * to sort a linked list in place.
143 *
144 * @param list the list to be sorted.
145 * @throws ClassCastException if the list contains elements that are not
146 * <i>mutually comparable</i> (for example, strings and integers).
147 * @throws UnsupportedOperationException if the specified list's
148 * list-iterator does not support the {@code set} operation.
149 * @throws IllegalArgumentException (optional) if the implementation
150 * detects that the natural ordering of the list elements is
151 * found to violate the {@link Comparable} contract
152 */
153 public static <T extends Comparable<? super T>> void sort(List<T> list) {
154 Object[] a = list.toArray();
155 Arrays.sort(a);
156 ListIterator<T> i = list.listIterator();
157 for (int j=0; j<a.length; j++) {
158 i.next();
159 i.set((T)a[j]);
160 }
161 }
162
163 /**
164 * Sorts the specified list according to the order induced by the
165 * specified comparator. All elements in the list must be <i>mutually
166 * comparable</i> using the specified comparator (that is,
167 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
168 * for any elements {@code e1} and {@code e2} in the list).
169 *
170 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
171 * not be reordered as a result of the sort.
172 *
195 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
196 * January 1993.
197 *
198 * <p>This implementation dumps the specified list into an array, sorts
199 * the array, and iterates over the list resetting each element
200 * from the corresponding position in the array. This avoids the
201 * n<sup>2</sup> log(n) performance that would result from attempting
202 * to sort a linked list in place.
203 *
204 * @param list the list to be sorted.
205 * @param c the comparator to determine the order of the list. A
206 * {@code null} value indicates that the elements' <i>natural
207 * ordering</i> should be used.
208 * @throws ClassCastException if the list contains elements that are not
209 * <i>mutually comparable</i> using the specified comparator.
210 * @throws UnsupportedOperationException if the specified list's
211 * list-iterator does not support the {@code set} operation.
212 * @throws IllegalArgumentException (optional) if the comparator is
213 * found to violate the {@link Comparator} contract
214 */
215 public static <T> void sort(List<T> list, Comparator<? super T> c) {
216 Object[] a = list.toArray();
217 Arrays.sort(a, (Comparator)c);
218 ListIterator i = list.listIterator();
219 for (int j=0; j<a.length; j++) {
220 i.next();
221 i.set(a[j]);
222 }
223 }
224
225
226 /**
227 * Searches the specified list for the specified object using the binary
228 * search algorithm. The list must be sorted into ascending order
229 * according to the {@linkplain Comparable natural ordering} of its
230 * elements (as by the {@link #sort(List)} method) prior to making this
231 * call. If it is not sorted, the results are undefined. If the list
232 * contains multiple elements equal to the specified object, there is no
233 * guarantee which one will be found.
234 *
235 * <p>This method runs in log(n) time for a "random access" list (which
236 * provides near-constant-time positional access). If the specified list
237 * does not implement the {@link RandomAccess} interface and is large,
238 * this method will do an iterator-based binary search that performs
239 * O(n) link traversals and O(log n) element comparisons.
240 *
241 * @param list the list to be searched.
340 * O(n) link traversals and O(log n) element comparisons.
341 *
342 * @param list the list to be searched.
343 * @param key the key to be searched for.
344 * @param c the comparator by which the list is ordered.
345 * A <tt>null</tt> value indicates that the elements'
346 * {@linkplain Comparable natural ordering} should be used.
347 * @return the index of the search key, if it is contained in the list;
348 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
349 * <i>insertion point</i> is defined as the point at which the
350 * key would be inserted into the list: the index of the first
351 * element greater than the key, or <tt>list.size()</tt> if all
352 * elements in the list are less than the specified key. Note
353 * that this guarantees that the return value will be >= 0 if
354 * and only if the key is found.
355 * @throws ClassCastException if the list contains elements that are not
356 * <i>mutually comparable</i> using the specified comparator,
357 * or the search key is not mutually comparable with the
358 * elements of the list using this comparator.
359 */
360 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
361 if (c==null)
362 return binarySearch((List) list, key);
363
364 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
365 return Collections.indexedBinarySearch(list, key, c);
366 else
367 return Collections.iteratorBinarySearch(list, key, c);
368 }
369
370 private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
371 int low = 0;
372 int high = l.size()-1;
373
374 while (low <= high) {
375 int mid = (low + high) >>> 1;
376 T midVal = l.get(mid);
377 int cmp = c.compare(midVal, key);
378
379 if (cmp < 0)
380 low = mid + 1;
381 else if (cmp > 0)
382 high = mid - 1;
389 private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
390 int low = 0;
391 int high = l.size()-1;
392 ListIterator<? extends T> i = l.listIterator();
393
394 while (low <= high) {
395 int mid = (low + high) >>> 1;
396 T midVal = get(i, mid);
397 int cmp = c.compare(midVal, key);
398
399 if (cmp < 0)
400 low = mid + 1;
401 else if (cmp > 0)
402 high = mid - 1;
403 else
404 return mid; // key found
405 }
406 return -(low + 1); // key not found
407 }
408
409 private interface SelfComparable extends Comparable<SelfComparable> {}
410
411
412 /**
413 * Reverses the order of the elements in the specified list.<p>
414 *
415 * This method runs in linear time.
416 *
417 * @param list the list whose elements are to be reversed.
418 * @throws UnsupportedOperationException if the specified list or
419 * its list-iterator does not support the <tt>set</tt> operation.
420 */
421 public static void reverse(List<?> list) {
422 int size = list.size();
423 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
424 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
425 swap(list, i, j);
426 } else {
427 ListIterator fwd = list.listIterator();
428 ListIterator rev = list.listIterator(size);
429 for (int i=0, mid=list.size()>>1; i<mid; i++) {
430 Object tmp = fwd.next();
431 fwd.set(rev.previous());
432 rev.set(tmp);
433 }
434 }
435 }
436
437 /**
438 * Randomly permutes the specified list using a default source of
439 * randomness. All permutations occur with approximately equal
440 * likelihood.<p>
441 *
442 * The hedge "approximately" is used in the foregoing description because
443 * default source of randomness is only approximately an unbiased source
444 * of independently chosen bits. If it were a perfect source of randomly
445 * chosen bits, then the algorithm would choose permutations with perfect
446 * uniformity.<p>
476 * assuming that the source of randomness is fair.<p>
477 *
478 * This implementation traverses the list backwards, from the last element
479 * up to the second, repeatedly swapping a randomly selected element into
480 * the "current position". Elements are randomly selected from the
481 * portion of the list that runs from the first element to the current
482 * position, inclusive.<p>
483 *
484 * This method runs in linear time. If the specified list does not
485 * implement the {@link RandomAccess} interface and is large, this
486 * implementation dumps the specified list into an array before shuffling
487 * it, and dumps the shuffled array back into the list. This avoids the
488 * quadratic behavior that would result from shuffling a "sequential
489 * access" list in place.
490 *
491 * @param list the list to be shuffled.
492 * @param rnd the source of randomness to use to shuffle the list.
493 * @throws UnsupportedOperationException if the specified list or its
494 * list-iterator does not support the <tt>set</tt> operation.
495 */
496 public static void shuffle(List<?> list, Random rnd) {
497 int size = list.size();
498 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
499 for (int i=size; i>1; i--)
500 swap(list, i-1, rnd.nextInt(i));
501 } else {
502 Object arr[] = list.toArray();
503
504 // Shuffle array
505 for (int i=size; i>1; i--)
506 swap(arr, i-1, rnd.nextInt(i));
507
508 // Dump array back into list
509 ListIterator it = list.listIterator();
510 for (int i=0; i<arr.length; i++) {
511 it.next();
512 it.set(arr[i]);
513 }
514 }
515 }
516
517 /**
518 * Swaps the elements at the specified positions in the specified list.
519 * (If the specified positions are equal, invoking this method leaves
520 * the list unchanged.)
521 *
522 * @param list The list in which to swap elements.
523 * @param i the index of one element to be swapped.
524 * @param j the index of the other element to be swapped.
525 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
526 * is out of range (i < 0 || i >= list.size()
527 * || j < 0 || j >= list.size()).
528 * @since 1.4
529 */
530 public static void swap(List<?> list, int i, int j) {
531 final List l = list;
532 l.set(i, l.set(j, l.get(i)));
533 }
534
535 /**
536 * Swaps the two specified elements in the specified array.
537 */
538 private static void swap(Object[] arr, int i, int j) {
539 Object tmp = arr[i];
540 arr[i] = arr[j];
541 arr[j] = tmp;
542 }
543
544 /**
545 * Replaces all of the elements of the specified list with the specified
546 * element. <p>
547 *
548 * This method runs in linear time.
549 *
550 * @param list the list to be filled with the specified element.
640 * order induced by the specified comparator. All elements in the
641 * collection must be <i>mutually comparable</i> by the specified
642 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
643 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
644 * <tt>e2</tt> in the collection).<p>
645 *
646 * This method iterates over the entire collection, hence it requires
647 * time proportional to the size of the collection.
648 *
649 * @param coll the collection whose minimum element is to be determined.
650 * @param comp the comparator with which to determine the minimum element.
651 * A <tt>null</tt> value indicates that the elements' <i>natural
652 * ordering</i> should be used.
653 * @return the minimum element of the given collection, according
654 * to the specified comparator.
655 * @throws ClassCastException if the collection contains elements that are
656 * not <i>mutually comparable</i> using the specified comparator.
657 * @throws NoSuchElementException if the collection is empty.
658 * @see Comparable
659 */
660 public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
661 if (comp==null)
662 return (T)min((Collection<SelfComparable>) (Collection) coll);
663
664 Iterator<? extends T> i = coll.iterator();
665 T candidate = i.next();
666
667 while (i.hasNext()) {
668 T next = i.next();
669 if (comp.compare(next, candidate) < 0)
670 candidate = next;
671 }
672 return candidate;
673 }
674
675 /**
676 * Returns the maximum element of the given collection, according to the
677 * <i>natural ordering</i> of its elements. All elements in the
678 * collection must implement the <tt>Comparable</tt> interface.
679 * Furthermore, all elements in the collection must be <i>mutually
680 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
681 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
682 * <tt>e2</tt> in the collection).<p>
710 * order induced by the specified comparator. All elements in the
711 * collection must be <i>mutually comparable</i> by the specified
712 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
713 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
714 * <tt>e2</tt> in the collection).<p>
715 *
716 * This method iterates over the entire collection, hence it requires
717 * time proportional to the size of the collection.
718 *
719 * @param coll the collection whose maximum element is to be determined.
720 * @param comp the comparator with which to determine the maximum element.
721 * A <tt>null</tt> value indicates that the elements' <i>natural
722 * ordering</i> should be used.
723 * @return the maximum element of the given collection, according
724 * to the specified comparator.
725 * @throws ClassCastException if the collection contains elements that are
726 * not <i>mutually comparable</i> using the specified comparator.
727 * @throws NoSuchElementException if the collection is empty.
728 * @see Comparable
729 */
730 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
731 if (comp==null)
732 return (T)max((Collection<SelfComparable>) (Collection) coll);
733
734 Iterator<? extends T> i = coll.iterator();
735 T candidate = i.next();
736
737 while (i.hasNext()) {
738 T next = i.next();
739 if (comp.compare(next, candidate) > 0)
740 candidate = next;
741 }
742 return candidate;
743 }
744
745 /**
746 * Rotates the elements in the specified list by the specified distance.
747 * After calling this method, the element at index <tt>i</tt> will be
748 * the element previously at index <tt>(i - distance)</tt> mod
749 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
750 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
751 * the size of the list.)
752 *
1372 values = unmodifiableCollection(m.values());
1373 return values;
1374 }
1375
1376 public boolean equals(Object o) {return o == this || m.equals(o);}
1377 public int hashCode() {return m.hashCode();}
1378 public String toString() {return m.toString();}
1379
1380 /**
1381 * We need this class in addition to UnmodifiableSet as
1382 * Map.Entries themselves permit modification of the backing Map
1383 * via their setValue operation. This class is subtle: there are
1384 * many possible attacks that must be thwarted.
1385 *
1386 * @serial include
1387 */
1388 static class UnmodifiableEntrySet<K,V>
1389 extends UnmodifiableSet<Map.Entry<K,V>> {
1390 private static final long serialVersionUID = 7854390611657943733L;
1391
1392 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1393 super((Set)s);
1394 }
1395 public Iterator<Map.Entry<K,V>> iterator() {
1396 return new Iterator<Map.Entry<K,V>>() {
1397 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1398
1399 public boolean hasNext() {
1400 return i.hasNext();
1401 }
1402 public Map.Entry<K,V> next() {
1403 return new UnmodifiableEntry<>(i.next());
1404 }
1405 public void remove() {
1406 throw new UnsupportedOperationException();
1407 }
1408 };
1409 }
1410
1411 public Object[] toArray() {
1412 Object[] a = c.toArray();
1413 for (int i=0; i<a.length; i++)
1414 a[i] = new UnmodifiableEntry<>((Map.Entry<K,V>)a[i]);
1415 return a;
1416 }
1417
1418 public <T> T[] toArray(T[] a) {
1419 // We don't pass a to c.toArray, to avoid window of
1420 // vulnerability wherein an unscrupulous multithreaded client
1421 // could get his hands on raw (unwrapped) Entries from c.
1422 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1423
1424 for (int i=0; i<arr.length; i++)
1425 arr[i] = new UnmodifiableEntry<>((Map.Entry<K,V>)arr[i]);
1426
1427 if (arr.length > a.length)
1428 return (T[])arr;
1429
1430 System.arraycopy(arr, 0, a, 0, arr.length);
1431 if (a.length > arr.length)
1432 a[arr.length] = null;
1433 return a;
1434 }
1435
1436 /**
1437 * This method is overridden to protect the backing set against
1438 * an object with a nefarious equals function that senses
1439 * that the equality-candidate is Map.Entry and calls its
1440 * setValue method.
1441 */
1442 public boolean contains(Object o) {
1443 if (!(o instanceof Map.Entry))
1444 return false;
1445 return c.contains(
1447 }
1448
1449 /**
1450 * The next two methods are overridden to protect against
1451 * an unscrupulous List whose contains(Object o) method senses
1452 * when o is a Map.Entry, and calls o.setValue.
1453 */
1454 public boolean containsAll(Collection<?> coll) {
1455 for (Object e : coll) {
1456 if (!contains(e)) // Invokes safe contains() above
1457 return false;
1458 }
1459 return true;
1460 }
1461 public boolean equals(Object o) {
1462 if (o == this)
1463 return true;
1464
1465 if (!(o instanceof Set))
1466 return false;
1467 Set s = (Set) o;
1468 if (s.size() != c.size())
1469 return false;
1470 return containsAll(s); // Invokes safe containsAll() above
1471 }
1472
1473 /**
1474 * This "wrapper class" serves two purposes: it prevents
1475 * the client from modifying the backing Map, by short-circuiting
1476 * the setValue method, and it protects the backing Map against
1477 * an ill-behaved Map.Entry that attempts to modify another
1478 * Map Entry when asked to perform an equality check.
1479 */
1480 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
1481 private Map.Entry<? extends K, ? extends V> e;
1482
1483 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1484
1485 public K getKey() {return e.getKey();}
1486 public V getValue() {return e.getValue();}
1487 public V setValue(V value) {
1488 throw new UnsupportedOperationException();
1489 }
1490 public int hashCode() {return e.hashCode();}
1491 public boolean equals(Object o) {
1492 if (!(o instanceof Map.Entry))
1493 return false;
1494 Map.Entry t = (Map.Entry)o;
1495 return eq(e.getKey(), t.getKey()) &&
1496 eq(e.getValue(), t.getValue());
1497 }
1498 public String toString() {return e.toString();}
1499 }
1500 }
1501 }
1502
1503 /**
1504 * Returns an unmodifiable view of the specified sorted map. This method
1505 * allows modules to provide users with "read-only" access to internal
1506 * sorted maps. Query operations on the returned sorted map "read through"
1507 * to the specified sorted map. Attempts to modify the returned
1508 * sorted map, whether direct, via its collection views, or via its
1509 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1510 * an <tt>UnsupportedOperationException</tt>.<p>
1511 *
1512 * The returned sorted map will be serializable if the specified sorted map
1513 * is serializable.
1514 *
|
133 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
134 * Sorting and Information Theoretic Complexity", in Proceedings of the
135 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
136 * January 1993.
137 *
138 * <p>This implementation dumps the specified list into an array, sorts
139 * the array, and iterates over the list resetting each element
140 * from the corresponding position in the array. This avoids the
141 * n<sup>2</sup> log(n) performance that would result from attempting
142 * to sort a linked list in place.
143 *
144 * @param list the list to be sorted.
145 * @throws ClassCastException if the list contains elements that are not
146 * <i>mutually comparable</i> (for example, strings and integers).
147 * @throws UnsupportedOperationException if the specified list's
148 * list-iterator does not support the {@code set} operation.
149 * @throws IllegalArgumentException (optional) if the implementation
150 * detects that the natural ordering of the list elements is
151 * found to violate the {@link Comparable} contract
152 */
153 @SuppressWarnings("unchecked")
154 public static <T extends Comparable<? super T>> void sort(List<T> list) {
155 Object[] a = list.toArray();
156 Arrays.sort(a);
157 ListIterator<T> i = list.listIterator();
158 for (int j=0; j<a.length; j++) {
159 i.next();
160 i.set((T)a[j]);
161 }
162 }
163
164 /**
165 * Sorts the specified list according to the order induced by the
166 * specified comparator. All elements in the list must be <i>mutually
167 * comparable</i> using the specified comparator (that is,
168 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
169 * for any elements {@code e1} and {@code e2} in the list).
170 *
171 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
172 * not be reordered as a result of the sort.
173 *
196 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
197 * January 1993.
198 *
199 * <p>This implementation dumps the specified list into an array, sorts
200 * the array, and iterates over the list resetting each element
201 * from the corresponding position in the array. This avoids the
202 * n<sup>2</sup> log(n) performance that would result from attempting
203 * to sort a linked list in place.
204 *
205 * @param list the list to be sorted.
206 * @param c the comparator to determine the order of the list. A
207 * {@code null} value indicates that the elements' <i>natural
208 * ordering</i> should be used.
209 * @throws ClassCastException if the list contains elements that are not
210 * <i>mutually comparable</i> using the specified comparator.
211 * @throws UnsupportedOperationException if the specified list's
212 * list-iterator does not support the {@code set} operation.
213 * @throws IllegalArgumentException (optional) if the comparator is
214 * found to violate the {@link Comparator} contract
215 */
216 @SuppressWarnings({ "unchecked", "rawtypes" })
217 public static <T> void sort(List<T> list, Comparator<? super T> c) {
218 Object[] a = list.toArray();
219 Arrays.sort(a, (Comparator)c);
220 ListIterator<T> i = list.listIterator();
221 for (int j=0; j<a.length; j++) {
222 i.next();
223 i.set((T)a[j]);
224 }
225 }
226
227
228 /**
229 * Searches the specified list for the specified object using the binary
230 * search algorithm. The list must be sorted into ascending order
231 * according to the {@linkplain Comparable natural ordering} of its
232 * elements (as by the {@link #sort(List)} method) prior to making this
233 * call. If it is not sorted, the results are undefined. If the list
234 * contains multiple elements equal to the specified object, there is no
235 * guarantee which one will be found.
236 *
237 * <p>This method runs in log(n) time for a "random access" list (which
238 * provides near-constant-time positional access). If the specified list
239 * does not implement the {@link RandomAccess} interface and is large,
240 * this method will do an iterator-based binary search that performs
241 * O(n) link traversals and O(log n) element comparisons.
242 *
243 * @param list the list to be searched.
342 * O(n) link traversals and O(log n) element comparisons.
343 *
344 * @param list the list to be searched.
345 * @param key the key to be searched for.
346 * @param c the comparator by which the list is ordered.
347 * A <tt>null</tt> value indicates that the elements'
348 * {@linkplain Comparable natural ordering} should be used.
349 * @return the index of the search key, if it is contained in the list;
350 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
351 * <i>insertion point</i> is defined as the point at which the
352 * key would be inserted into the list: the index of the first
353 * element greater than the key, or <tt>list.size()</tt> if all
354 * elements in the list are less than the specified key. Note
355 * that this guarantees that the return value will be >= 0 if
356 * and only if the key is found.
357 * @throws ClassCastException if the list contains elements that are not
358 * <i>mutually comparable</i> using the specified comparator,
359 * or the search key is not mutually comparable with the
360 * elements of the list using this comparator.
361 */
362 @SuppressWarnings("unchecked")
363 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
364 if (c==null)
365 return binarySearch((List<? extends Comparable<? super T>>) list, key);
366
367 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
368 return Collections.indexedBinarySearch(list, key, c);
369 else
370 return Collections.iteratorBinarySearch(list, key, c);
371 }
372
373 private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
374 int low = 0;
375 int high = l.size()-1;
376
377 while (low <= high) {
378 int mid = (low + high) >>> 1;
379 T midVal = l.get(mid);
380 int cmp = c.compare(midVal, key);
381
382 if (cmp < 0)
383 low = mid + 1;
384 else if (cmp > 0)
385 high = mid - 1;
392 private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
393 int low = 0;
394 int high = l.size()-1;
395 ListIterator<? extends T> i = l.listIterator();
396
397 while (low <= high) {
398 int mid = (low + high) >>> 1;
399 T midVal = get(i, mid);
400 int cmp = c.compare(midVal, key);
401
402 if (cmp < 0)
403 low = mid + 1;
404 else if (cmp > 0)
405 high = mid - 1;
406 else
407 return mid; // key found
408 }
409 return -(low + 1); // key not found
410 }
411
412 /**
413 * Reverses the order of the elements in the specified list.<p>
414 *
415 * This method runs in linear time.
416 *
417 * @param list the list whose elements are to be reversed.
418 * @throws UnsupportedOperationException if the specified list or
419 * its list-iterator does not support the <tt>set</tt> operation.
420 */
421 @SuppressWarnings({ "rawtypes", "unchecked" })
422 public static void reverse(List<?> list) {
423 int size = list.size();
424 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
425 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
426 swap(list, i, j);
427 } else {
428 // instead of using a raw type here, it's possible to capture
429 // the wildcard but it will require a call to a supplementary
430 // private method
431 ListIterator fwd = list.listIterator();
432 ListIterator rev = list.listIterator(size);
433 for (int i=0, mid=list.size()>>1; i<mid; i++) {
434 Object tmp = fwd.next();
435 fwd.set(rev.previous());
436 rev.set(tmp);
437 }
438 }
439 }
440
441 /**
442 * Randomly permutes the specified list using a default source of
443 * randomness. All permutations occur with approximately equal
444 * likelihood.<p>
445 *
446 * The hedge "approximately" is used in the foregoing description because
447 * default source of randomness is only approximately an unbiased source
448 * of independently chosen bits. If it were a perfect source of randomly
449 * chosen bits, then the algorithm would choose permutations with perfect
450 * uniformity.<p>
480 * assuming that the source of randomness is fair.<p>
481 *
482 * This implementation traverses the list backwards, from the last element
483 * up to the second, repeatedly swapping a randomly selected element into
484 * the "current position". Elements are randomly selected from the
485 * portion of the list that runs from the first element to the current
486 * position, inclusive.<p>
487 *
488 * This method runs in linear time. If the specified list does not
489 * implement the {@link RandomAccess} interface and is large, this
490 * implementation dumps the specified list into an array before shuffling
491 * it, and dumps the shuffled array back into the list. This avoids the
492 * quadratic behavior that would result from shuffling a "sequential
493 * access" list in place.
494 *
495 * @param list the list to be shuffled.
496 * @param rnd the source of randomness to use to shuffle the list.
497 * @throws UnsupportedOperationException if the specified list or its
498 * list-iterator does not support the <tt>set</tt> operation.
499 */
500 @SuppressWarnings({ "rawtypes", "unchecked" })
501 public static void shuffle(List<?> list, Random rnd) {
502 int size = list.size();
503 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
504 for (int i=size; i>1; i--)
505 swap(list, i-1, rnd.nextInt(i));
506 } else {
507 Object arr[] = list.toArray();
508
509 // Shuffle array
510 for (int i=size; i>1; i--)
511 swap(arr, i-1, rnd.nextInt(i));
512
513 // Dump array back into list
514 // instead of using a raw type here, it's possible to capture
515 // the wildcard but it will require a call to a supplementary
516 // private method
517 ListIterator it = list.listIterator();
518 for (int i=0; i<arr.length; i++) {
519 it.next();
520 it.set(arr[i]);
521 }
522 }
523 }
524
525 /**
526 * Swaps the elements at the specified positions in the specified list.
527 * (If the specified positions are equal, invoking this method leaves
528 * the list unchanged.)
529 *
530 * @param list The list in which to swap elements.
531 * @param i the index of one element to be swapped.
532 * @param j the index of the other element to be swapped.
533 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
534 * is out of range (i < 0 || i >= list.size()
535 * || j < 0 || j >= list.size()).
536 * @since 1.4
537 */
538 @SuppressWarnings({ "rawtypes", "unchecked" })
539 public static void swap(List<?> list, int i, int j) {
540 // instead of using a raw type here, it's possible to capture
541 // the wildcard but it will require a call to a supplementary
542 // private method
543 final List l = list;
544 l.set(i, l.set(j, l.get(i)));
545 }
546
547 /**
548 * Swaps the two specified elements in the specified array.
549 */
550 private static void swap(Object[] arr, int i, int j) {
551 Object tmp = arr[i];
552 arr[i] = arr[j];
553 arr[j] = tmp;
554 }
555
556 /**
557 * Replaces all of the elements of the specified list with the specified
558 * element. <p>
559 *
560 * This method runs in linear time.
561 *
562 * @param list the list to be filled with the specified element.
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 minimum element is to be determined.
662 * @param comp the comparator with which to determine the minimum element.
663 * A <tt>null</tt> value indicates that the elements' <i>natural
664 * ordering</i> should be used.
665 * @return the minimum 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 @SuppressWarnings({ "unchecked", "rawtypes" })
673 public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
674 if (comp==null)
675 return (T)min((Collection) coll);
676
677 Iterator<? extends T> i = coll.iterator();
678 T candidate = i.next();
679
680 while (i.hasNext()) {
681 T next = i.next();
682 if (comp.compare(next, candidate) < 0)
683 candidate = next;
684 }
685 return candidate;
686 }
687
688 /**
689 * Returns the maximum element of the given collection, according to the
690 * <i>natural ordering</i> of its elements. All elements in the
691 * collection must implement the <tt>Comparable</tt> interface.
692 * Furthermore, all elements in the collection must be <i>mutually
693 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
694 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
695 * <tt>e2</tt> in the collection).<p>
723 * order induced by the specified comparator. All elements in the
724 * collection must be <i>mutually comparable</i> by the specified
725 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
726 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
727 * <tt>e2</tt> in the collection).<p>
728 *
729 * This method iterates over the entire collection, hence it requires
730 * time proportional to the size of the collection.
731 *
732 * @param coll the collection whose maximum element is to be determined.
733 * @param comp the comparator with which to determine the maximum element.
734 * A <tt>null</tt> value indicates that the elements' <i>natural
735 * ordering</i> should be used.
736 * @return the maximum element of the given collection, according
737 * to the specified comparator.
738 * @throws ClassCastException if the collection contains elements that are
739 * not <i>mutually comparable</i> using the specified comparator.
740 * @throws NoSuchElementException if the collection is empty.
741 * @see Comparable
742 */
743 @SuppressWarnings({ "unchecked", "rawtypes" })
744 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
745 if (comp==null)
746 return (T)max((Collection) coll);
747
748 Iterator<? extends T> i = coll.iterator();
749 T candidate = i.next();
750
751 while (i.hasNext()) {
752 T next = i.next();
753 if (comp.compare(next, candidate) > 0)
754 candidate = next;
755 }
756 return candidate;
757 }
758
759 /**
760 * Rotates the elements in the specified list by the specified distance.
761 * After calling this method, the element at index <tt>i</tt> will be
762 * the element previously at index <tt>(i - distance)</tt> mod
763 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
764 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
765 * the size of the list.)
766 *
1386 values = unmodifiableCollection(m.values());
1387 return values;
1388 }
1389
1390 public boolean equals(Object o) {return o == this || m.equals(o);}
1391 public int hashCode() {return m.hashCode();}
1392 public String toString() {return m.toString();}
1393
1394 /**
1395 * We need this class in addition to UnmodifiableSet as
1396 * Map.Entries themselves permit modification of the backing Map
1397 * via their setValue operation. This class is subtle: there are
1398 * many possible attacks that must be thwarted.
1399 *
1400 * @serial include
1401 */
1402 static class UnmodifiableEntrySet<K,V>
1403 extends UnmodifiableSet<Map.Entry<K,V>> {
1404 private static final long serialVersionUID = 7854390611657943733L;
1405
1406 @SuppressWarnings({ "unchecked", "rawtypes" })
1407 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1408 super((Set)s);
1409 }
1410 public Iterator<Map.Entry<K,V>> iterator() {
1411 return new Iterator<Map.Entry<K,V>>() {
1412 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1413
1414 public boolean hasNext() {
1415 return i.hasNext();
1416 }
1417 public Map.Entry<K,V> next() {
1418 return new UnmodifiableEntry<>(i.next());
1419 }
1420 public void remove() {
1421 throw new UnsupportedOperationException();
1422 }
1423 };
1424 }
1425
1426 @SuppressWarnings("unchecked")
1427 public Object[] toArray() {
1428 Object[] a = c.toArray();
1429 for (int i=0; i<a.length; i++)
1430 a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]);
1431 return a;
1432 }
1433
1434 @SuppressWarnings("unchecked")
1435 public <T> T[] toArray(T[] a) {
1436 // We don't pass a to c.toArray, to avoid window of
1437 // vulnerability wherein an unscrupulous multithreaded client
1438 // could get his hands on raw (unwrapped) Entries from c.
1439 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1440
1441 for (int i=0; i<arr.length; i++)
1442 arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]);
1443
1444 if (arr.length > a.length)
1445 return (T[])arr;
1446
1447 System.arraycopy(arr, 0, a, 0, arr.length);
1448 if (a.length > arr.length)
1449 a[arr.length] = null;
1450 return a;
1451 }
1452
1453 /**
1454 * This method is overridden to protect the backing set against
1455 * an object with a nefarious equals function that senses
1456 * that the equality-candidate is Map.Entry and calls its
1457 * setValue method.
1458 */
1459 public boolean contains(Object o) {
1460 if (!(o instanceof Map.Entry))
1461 return false;
1462 return c.contains(
1464 }
1465
1466 /**
1467 * The next two methods are overridden to protect against
1468 * an unscrupulous List whose contains(Object o) method senses
1469 * when o is a Map.Entry, and calls o.setValue.
1470 */
1471 public boolean containsAll(Collection<?> coll) {
1472 for (Object e : coll) {
1473 if (!contains(e)) // Invokes safe contains() above
1474 return false;
1475 }
1476 return true;
1477 }
1478 public boolean equals(Object o) {
1479 if (o == this)
1480 return true;
1481
1482 if (!(o instanceof Set))
1483 return false;
1484 Set<?> s = (Set<?>) o;
1485 if (s.size() != c.size())
1486 return false;
1487 return containsAll(s); // Invokes safe containsAll() above
1488 }
1489
1490 /**
1491 * This "wrapper class" serves two purposes: it prevents
1492 * the client from modifying the backing Map, by short-circuiting
1493 * the setValue method, and it protects the backing Map against
1494 * an ill-behaved Map.Entry that attempts to modify another
1495 * Map Entry when asked to perform an equality check.
1496 */
1497 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
1498 private Map.Entry<? extends K, ? extends V> e;
1499
1500 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1501
1502 public K getKey() {return e.getKey();}
1503 public V getValue() {return e.getValue();}
1504 public V setValue(V value) {
1505 throw new UnsupportedOperationException();
1506 }
1507 public int hashCode() {return e.hashCode();}
1508 public boolean equals(Object o) {
1509 if (!(o instanceof Map.Entry))
1510 return false;
1511 Map.Entry<?,?> t = (Map.Entry<?,?>)o;
1512 return eq(e.getKey(), t.getKey()) &&
1513 eq(e.getValue(), t.getValue());
1514 }
1515 public String toString() {return e.toString();}
1516 }
1517 }
1518 }
1519
1520 /**
1521 * Returns an unmodifiable view of the specified sorted map. This method
1522 * allows modules to provide users with "read-only" access to internal
1523 * sorted maps. Query operations on the returned sorted map "read through"
1524 * to the specified sorted map. Attempts to modify the returned
1525 * sorted map, whether direct, via its collection views, or via its
1526 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1527 * an <tt>UnsupportedOperationException</tt>.<p>
1528 *
1529 * The returned sorted map will be serializable if the specified sorted map
1530 * is serializable.
1531 *
|