1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package java.util; 19 20 import java.io.IOException; 21 import java.io.ObjectInputStream; 22 import java.io.ObjectOutputStream; 23 import java.io.ObjectStreamException; 24 import java.io.Serializable; 25 import java.lang.reflect.Array; 26 27 /** 28 * {@code Collections} contains static methods which operate on 29 * {@code Collection} classes. 30 * 31 * @since 1.2 32 */ 33 public class Collections { 34 35 private static final Iterator<?> EMPTY_ITERATOR = new Iterator<Object>() { 36 @Override public boolean hasNext() { 37 return false; 38 } 39 40 @Override public Object next() { 41 throw new NoSuchElementException(); 42 } 43 44 @Override public void remove() { 45 throw new IllegalStateException(); 46 } 47 }; 48 49 private static final Enumeration<?> EMPTY_ENUMERATION = new Enumeration<Object>() { 50 @Override public boolean hasMoreElements() { 51 return false; 52 } 53 54 @Override public Object nextElement() { 55 throw new NoSuchElementException(); 56 } 57 }; 58 59 private static final class CopiesList<E> extends AbstractList<E> implements Serializable { 60 private static final long serialVersionUID = 2739099268398711800L; 61 private final int n; 62 private final E element; 63 64 CopiesList(int length, E object) { 65 if (length < 0) { 66 throw new IllegalArgumentException("length < 0: " + length); 67 } 68 n = length; 69 element = object; 70 } 71 72 @Override public boolean contains(Object object) { 73 return element == null ? object == null : element.equals(object); 74 } 75 76 @Override public int size() { 77 return n; 78 } 79 80 @Override public E get(int location) { 81 if (location >= 0 && location < n) { 82 return element; 83 } 84 throw new IndexOutOfBoundsException(); 85 } 86 } 87 88 @SuppressWarnings("unchecked") 89 private static final class EmptyList extends AbstractList 90 implements RandomAccess, Serializable { 91 private static final long serialVersionUID = 8842843931221139166L; 92 93 @Override public boolean contains(Object object) { 94 return false; 95 } 96 97 @Override public int size() { 98 return 0; 99 } 100 101 @Override public Object get(int location) { 102 throw new IndexOutOfBoundsException(); 103 } 104 105 private Object readResolve() { 106 return Collections.EMPTY_LIST; 107 } 108 } 109 110 @SuppressWarnings("unchecked") 111 private static final class EmptySet extends AbstractSet implements Serializable { 112 private static final long serialVersionUID = 1582296315990362920L; 113 114 @Override public boolean contains(Object object) { 115 return false; 116 } 117 118 @Override public int size() { 119 return 0; 120 } 121 122 @Override public Iterator iterator() { 123 return EMPTY_ITERATOR; 124 } 125 126 private Object readResolve() { 127 return Collections.EMPTY_SET; 128 } 129 } 130 131 @SuppressWarnings("unchecked") 132 private static final class EmptyMap extends AbstractMap implements Serializable { 133 private static final long serialVersionUID = 6428348081105594320L; 134 135 @Override public boolean containsKey(Object key) { 136 return false; 137 } 138 139 @Override public boolean containsValue(Object value) { 140 return false; 141 } 142 143 @Override public Set entrySet() { 144 return EMPTY_SET; 145 } 146 147 @Override public Object get(Object key) { 148 return null; 149 } 150 151 @Override public Set keySet() { 152 return EMPTY_SET; 153 } 154 155 @Override public Collection values() { 156 return EMPTY_LIST; 157 } 158 159 private Object readResolve() { 160 return Collections.EMPTY_MAP; 161 } 162 } 163 164 /** 165 * An empty immutable instance of {@link List}. 166 */ 167 @SuppressWarnings("unchecked") 168 public static final List EMPTY_LIST = new EmptyList(); 169 170 /** 171 * An empty immutable instance of {@link Set}. 172 */ 173 @SuppressWarnings("unchecked") 174 public static final Set EMPTY_SET = new EmptySet(); 175 176 /** 177 * An empty immutable instance of {@link Map}. 178 */ 179 @SuppressWarnings("unchecked") 180 public static final Map EMPTY_MAP = new EmptyMap(); 181 182 /** 183 * This class is a singleton so that equals() and hashCode() work properly. 184 */ 185 private static final class ReverseComparator<T> implements Comparator<T>, Serializable { 186 private static final ReverseComparator<Object> INSTANCE = new ReverseComparator<Object>(); 187 188 private static final long serialVersionUID = 7207038068494060240L; 189 190 @SuppressWarnings("unchecked") 191 @Override public int compare(T o1, T o2) { 192 Comparable<T> c2 = (Comparable<T>) o2; 193 return c2.compareTo(o1); 194 } 195 196 private Object readResolve() throws ObjectStreamException { 197 return INSTANCE; 198 } 199 } 200 201 private static final class ReverseComparator2<T> implements Comparator<T>, Serializable { 202 private static final long serialVersionUID = 4374092139857L; 203 private final Comparator<T> cmp; 204 205 ReverseComparator2(Comparator<T> comparator) { 206 this.cmp = comparator; 207 } 208 209 @Override public int compare(T o1, T o2) { 210 return cmp.compare(o2, o1); 211 } 212 213 @Override public boolean equals(Object o) { 214 return o instanceof ReverseComparator2 215 && ((ReverseComparator2) o).cmp.equals(cmp); 216 } 217 218 @Override public int hashCode() { 219 return ~cmp.hashCode(); 220 } 221 } 222 223 private static final class SingletonSet<E> extends AbstractSet<E> implements Serializable { 224 private static final long serialVersionUID = 3193687207550431679L; 225 final E element; 226 227 SingletonSet(E object) { 228 element = object; 229 } 230 231 @Override public boolean contains(Object object) { 232 return element == null ? object == null : element.equals(object); 233 } 234 235 @Override public int size() { 236 return 1; 237 } 238 239 @Override public Iterator<E> iterator() { 240 return new Iterator<E>() { 241 boolean hasNext = true; 242 243 @Override public boolean hasNext() { 244 return hasNext; 245 } 246 247 @Override public E next() { 248 if (hasNext) { 249 hasNext = false; 250 return element; 251 } 252 throw new NoSuchElementException(); 253 } 254 255 @Override public void remove() { 256 throw new UnsupportedOperationException(); 257 } 258 }; 259 } 260 } 261 262 private static final class SingletonList<E> extends AbstractList<E> implements Serializable { 263 private static final long serialVersionUID = 3093736618740652951L; 264 265 final E element; 266 267 SingletonList(E object) { 268 element = object; 269 } 270 271 @Override public boolean contains(Object object) { 272 return element == null ? object == null : element.equals(object); 273 } 274 275 @Override public E get(int location) { 276 if (location == 0) { 277 return element; 278 } 279 throw new IndexOutOfBoundsException(); 280 } 281 282 @Override public int size() { 283 return 1; 284 } 285 } 286 287 private static final class SingletonMap<K, V> extends AbstractMap<K, V> 288 implements Serializable { 289 private static final long serialVersionUID = -6979724477215052911L; 290 291 final K k; 292 final V v; 293 294 SingletonMap(K key, V value) { 295 k = key; 296 v = value; 297 } 298 299 @Override public boolean containsKey(Object key) { 300 return k == null ? key == null : k.equals(key); 301 } 302 303 @Override public boolean containsValue(Object value) { 304 return v == null ? value == null : v.equals(value); 305 } 306 307 @Override public V get(Object key) { 308 if (containsKey(key)) { 309 return v; 310 } 311 return null; 312 } 313 314 @Override public int size() { 315 return 1; 316 } 317 318 @Override public Set<Map.Entry<K, V>> entrySet() { 319 return new AbstractSet<Map.Entry<K, V>>() { 320 @Override public boolean contains(Object object) { 321 if (object instanceof Map.Entry) { 322 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object; 323 return containsKey(entry.getKey()) 324 && containsValue(entry.getValue()); 325 } 326 return false; 327 } 328 329 @Override public int size() { 330 return 1; 331 } 332 333 @Override public Iterator<Map.Entry<K, V>> iterator() { 334 return new Iterator<Map.Entry<K, V>>() { 335 boolean hasNext = true; 336 337 @Override public boolean hasNext() { 338 return hasNext; 339 } 340 341 @Override public Map.Entry<K, V> next() { 342 if (!hasNext) { 343 throw new NoSuchElementException(); 344 } 345 346 hasNext = false; 347 return new MapEntry<K, V>(k, v) { 348 @Override public V setValue(V value) { 349 throw new UnsupportedOperationException(); 350 } 351 }; 352 } 353 354 @Override public void remove() { 355 throw new UnsupportedOperationException(); 356 } 357 }; 358 } 359 }; 360 } 361 } 362 363 static class SynchronizedCollection<E> implements Collection<E>, Serializable { 364 private static final long serialVersionUID = 3053995032091335093L; 365 final Collection<E> c; 366 final Object mutex; 367 368 SynchronizedCollection(Collection<E> collection) { 369 c = collection; 370 mutex = this; 371 } 372 373 SynchronizedCollection(Collection<E> collection, Object mutex) { 374 c = collection; 375 this.mutex = mutex; 376 } 377 378 @Override public boolean add(E object) { 379 synchronized (mutex) { 380 return c.add(object); 381 } 382 } 383 384 @Override public boolean addAll(Collection<? extends E> collection) { 385 synchronized (mutex) { 386 return c.addAll(collection); 387 } 388 } 389 390 @Override public void clear() { 391 synchronized (mutex) { 392 c.clear(); 393 } 394 } 395 396 @Override public boolean contains(Object object) { 397 synchronized (mutex) { 398 return c.contains(object); 399 } 400 } 401 402 @Override public boolean containsAll(Collection<?> collection) { 403 synchronized (mutex) { 404 return c.containsAll(collection); 405 } 406 } 407 408 @Override public boolean isEmpty() { 409 synchronized (mutex) { 410 return c.isEmpty(); 411 } 412 } 413 414 @Override public Iterator<E> iterator() { 415 synchronized (mutex) { 416 return c.iterator(); 417 } 418 } 419 420 @Override public boolean remove(Object object) { 421 synchronized (mutex) { 422 return c.remove(object); 423 } 424 } 425 426 @Override public boolean removeAll(Collection<?> collection) { 427 synchronized (mutex) { 428 return c.removeAll(collection); 429 } 430 } 431 432 @Override public boolean retainAll(Collection<?> collection) { 433 synchronized (mutex) { 434 return c.retainAll(collection); 435 } 436 } 437 438 @Override public int size() { 439 synchronized (mutex) { 440 return c.size(); 441 } 442 } 443 444 @Override public java.lang.Object[] toArray() { 445 synchronized (mutex) { 446 return c.toArray(); 447 } 448 } 449 450 @Override public String toString() { 451 synchronized (mutex) { 452 return c.toString(); 453 } 454 } 455 456 @Override public <T> T[] toArray(T[] array) { 457 synchronized (mutex) { 458 return c.toArray(array); 459 } 460 } 461 462 private void writeObject(ObjectOutputStream stream) throws IOException { 463 synchronized (mutex) { 464 stream.defaultWriteObject(); 465 } 466 } 467 } 468 469 static class SynchronizedRandomAccessList<E> extends SynchronizedList<E> 470 implements RandomAccess { 471 private static final long serialVersionUID = 1530674583602358482L; 472 473 SynchronizedRandomAccessList(List<E> l) { 474 super(l); 475 } 476 477 SynchronizedRandomAccessList(List<E> l, Object mutex) { 478 super(l, mutex); 479 } 480 481 @Override public List<E> subList(int start, int end) { 482 synchronized (mutex) { 483 return new SynchronizedRandomAccessList<E>(list.subList(start, end), mutex); 484 } 485 } 486 487 /** 488 * Replaces this SynchronizedRandomAccessList with a SynchronizedList so 489 * that JREs before 1.4 can deserialize this object without any 490 * problems. This is necessary since RandomAccess API was introduced 491 * only in 1.4. 492 * <p> 493 * 494 * @return SynchronizedList 495 * 496 * @see SynchronizedList#readResolve() 497 */ 498 private Object writeReplace() { 499 return new SynchronizedList<E>(list); 500 } 501 } 502 503 static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> { 504 private static final long serialVersionUID = -7754090372962971524L; 505 final List<E> list; 506 507 SynchronizedList(List<E> l) { 508 super(l); 509 list = l; 510 } 511 512 SynchronizedList(List<E> l, Object mutex) { 513 super(l, mutex); 514 list = l; 515 } 516 517 @Override public void add(int location, E object) { 518 synchronized (mutex) { 519 list.add(location, object); 520 } 521 } 522 523 @Override public boolean addAll(int location, Collection<? extends E> collection) { 524 synchronized (mutex) { 525 return list.addAll(location, collection); 526 } 527 } 528 529 @Override public boolean equals(Object object) { 530 synchronized (mutex) { 531 return list.equals(object); 532 } 533 } 534 535 @Override public E get(int location) { 536 synchronized (mutex) { 537 return list.get(location); 538 } 539 } 540 541 @Override public int hashCode() { 542 synchronized (mutex) { 543 return list.hashCode(); 544 } 545 } 546 547 @Override public int indexOf(Object object) { 548 final int size; 549 final Object[] array; 550 synchronized (mutex) { 551 size = list.size(); 552 array = new Object[size]; 553 list.toArray(array); 554 } 555 if (object != null) { 556 for (int i = 0; i < size; i++) { 557 if (object.equals(array[i])) { 558 return i; 559 } 560 } 561 } else { 562 for (int i = 0; i < size; i++) { 563 if (array[i] == null) { 564 return i; 565 } 566 } 567 } 568 return -1; 569 } 570 571 @Override public int lastIndexOf(Object object) { 572 final int size; 573 final Object[] array; 574 synchronized (mutex) { 575 size = list.size(); 576 array = new Object[size]; 577 list.toArray(array); 578 } 579 if (object != null) { 580 for (int i = size - 1; i >= 0; i--) { 581 if (object.equals(array[i])) { 582 return i; 583 } 584 } 585 } else { 586 for (int i = size - 1; i >= 0; i--) { 587 if (array[i] == null) { 588 return i; 589 } 590 } 591 } 592 return -1; 593 } 594 595 @Override public ListIterator<E> listIterator() { 596 synchronized (mutex) { 597 return list.listIterator(); 598 } 599 } 600 601 @Override public ListIterator<E> listIterator(int location) { 602 synchronized (mutex) { 603 return list.listIterator(location); 604 } 605 } 606 607 @Override public E remove(int location) { 608 synchronized (mutex) { 609 return list.remove(location); 610 } 611 } 612 613 @Override public E set(int location, E object) { 614 synchronized (mutex) { 615 return list.set(location, object); 616 } 617 } 618 619 @Override public List<E> subList(int start, int end) { 620 synchronized (mutex) { 621 return new SynchronizedList<E>(list.subList(start, end), mutex); 622 } 623 } 624 625 private void writeObject(ObjectOutputStream stream) throws IOException { 626 synchronized (mutex) { 627 stream.defaultWriteObject(); 628 } 629 } 630 631 /** 632 * Resolves SynchronizedList instances to SynchronizedRandomAccessList 633 * instances if the underlying list is a Random Access list. 634 * <p> 635 * This is necessary since SynchronizedRandomAccessList instances are 636 * replaced with SynchronizedList instances during serialization for 637 * compliance with JREs before 1.4. 638 * <p> 639 * 640 * @return a SynchronizedList instance if the underlying list implements 641 * RandomAccess interface, or this same object if not. 642 * 643 * @see SynchronizedRandomAccessList#writeReplace() 644 */ 645 private Object readResolve() { 646 if (list instanceof RandomAccess) { 647 return new SynchronizedRandomAccessList<E>(list, mutex); 648 } 649 return this; 650 } 651 } 652 653 static class SynchronizedMap<K, V> implements Map<K, V>, Serializable { 654 private static final long serialVersionUID = 1978198479659022715L; 655 656 private final Map<K, V> m; 657 658 final Object mutex; 659 660 SynchronizedMap(Map<K, V> map) { 661 m = map; 662 mutex = this; 663 } 664 665 SynchronizedMap(Map<K, V> map, Object mutex) { 666 m = map; 667 this.mutex = mutex; 668 } 669 670 @Override public void clear() { 671 synchronized (mutex) { 672 m.clear(); 673 } 674 } 675 676 @Override public boolean containsKey(Object key) { 677 synchronized (mutex) { 678 return m.containsKey(key); 679 } 680 } 681 682 @Override public boolean containsValue(Object value) { 683 synchronized (mutex) { 684 return m.containsValue(value); 685 } 686 } 687 688 @Override public Set<Map.Entry<K, V>> entrySet() { 689 synchronized (mutex) { 690 return new SynchronizedSet<Map.Entry<K, V>>(m.entrySet(), mutex); 691 } 692 } 693 694 @Override public boolean equals(Object object) { 695 synchronized (mutex) { 696 return m.equals(object); 697 } 698 } 699 700 @Override public V get(Object key) { 701 synchronized (mutex) { 702 return m.get(key); 703 } 704 } 705 706 @Override public int hashCode() { 707 synchronized (mutex) { 708 return m.hashCode(); 709 } 710 } 711 712 @Override public boolean isEmpty() { 713 synchronized (mutex) { 714 return m.isEmpty(); 715 } 716 } 717 718 @Override public Set<K> keySet() { 719 synchronized (mutex) { 720 return new SynchronizedSet<K>(m.keySet(), mutex); 721 } 722 } 723 724 @Override public V put(K key, V value) { 725 synchronized (mutex) { 726 return m.put(key, value); 727 } 728 } 729 730 @Override public void putAll(Map<? extends K, ? extends V> map) { 731 synchronized (mutex) { 732 m.putAll(map); 733 } 734 } 735 736 @Override public V remove(Object key) { 737 synchronized (mutex) { 738 return m.remove(key); 739 } 740 } 741 742 @Override public int size() { 743 synchronized (mutex) { 744 return m.size(); 745 } 746 } 747 748 @Override public Collection<V> values() { 749 synchronized (mutex) { 750 return new SynchronizedCollection<V>(m.values(), mutex); 751 } 752 } 753 754 @Override public String toString() { 755 synchronized (mutex) { 756 return m.toString(); 757 } 758 } 759 760 private void writeObject(ObjectOutputStream stream) throws IOException { 761 synchronized (mutex) { 762 stream.defaultWriteObject(); 763 } 764 } 765 } 766 767 static class SynchronizedSet<E> extends SynchronizedCollection<E> implements Set<E> { 768 private static final long serialVersionUID = 487447009682186044L; 769 770 SynchronizedSet(Set<E> set) { 771 super(set); 772 } 773 774 SynchronizedSet(Set<E> set, Object mutex) { 775 super(set, mutex); 776 } 777 778 @Override public boolean equals(Object object) { 779 synchronized (mutex) { 780 return c.equals(object); 781 } 782 } 783 784 @Override public int hashCode() { 785 synchronized (mutex) { 786 return c.hashCode(); 787 } 788 } 789 790 private void writeObject(ObjectOutputStream stream) throws IOException { 791 synchronized (mutex) { 792 stream.defaultWriteObject(); 793 } 794 } 795 } 796 797 static class SynchronizedSortedMap<K, V> extends SynchronizedMap<K, V> 798 implements SortedMap<K, V> { 799 private static final long serialVersionUID = -8798146769416483793L; 800 801 private final SortedMap<K, V> sm; 802 803 SynchronizedSortedMap(SortedMap<K, V> map) { 804 super(map); 805 sm = map; 806 } 807 808 SynchronizedSortedMap(SortedMap<K, V> map, Object mutex) { 809 super(map, mutex); 810 sm = map; 811 } 812 813 @Override public Comparator<? super K> comparator() { 814 synchronized (mutex) { 815 return sm.comparator(); 816 } 817 } 818 819 @Override public K firstKey() { 820 synchronized (mutex) { 821 return sm.firstKey(); 822 } 823 } 824 825 @Override public SortedMap<K, V> headMap(K endKey) { 826 synchronized (mutex) { 827 return new SynchronizedSortedMap<K, V>(sm.headMap(endKey), 828 mutex); 829 } 830 } 831 832 @Override public K lastKey() { 833 synchronized (mutex) { 834 return sm.lastKey(); 835 } 836 } 837 838 @Override public SortedMap<K, V> subMap(K startKey, K endKey) { 839 synchronized (mutex) { 840 return new SynchronizedSortedMap<K, V>(sm.subMap(startKey, 841 endKey), mutex); 842 } 843 } 844 845 @Override public SortedMap<K, V> tailMap(K startKey) { 846 synchronized (mutex) { 847 return new SynchronizedSortedMap<K, V>(sm.tailMap(startKey), 848 mutex); 849 } 850 } 851 852 private void writeObject(ObjectOutputStream stream) throws IOException { 853 synchronized (mutex) { 854 stream.defaultWriteObject(); 855 } 856 } 857 } 858 859 static class SynchronizedSortedSet<E> extends SynchronizedSet<E> implements SortedSet<E> { 860 private static final long serialVersionUID = 8695801310862127406L; 861 862 private final SortedSet<E> ss; 863 864 SynchronizedSortedSet(SortedSet<E> set) { 865 super(set); 866 ss = set; 867 } 868 869 SynchronizedSortedSet(SortedSet<E> set, Object mutex) { 870 super(set, mutex); 871 ss = set; 872 } 873 874 @Override public Comparator<? super E> comparator() { 875 synchronized (mutex) { 876 return ss.comparator(); 877 } 878 } 879 880 @Override public E first() { 881 synchronized (mutex) { 882 return ss.first(); 883 } 884 } 885 886 @Override public SortedSet<E> headSet(E end) { 887 synchronized (mutex) { 888 return new SynchronizedSortedSet<E>(ss.headSet(end), mutex); 889 } 890 } 891 892 @Override public E last() { 893 synchronized (mutex) { 894 return ss.last(); 895 } 896 } 897 898 @Override public SortedSet<E> subSet(E start, E end) { 899 synchronized (mutex) { 900 return new SynchronizedSortedSet<E>(ss.subSet(start, end), 901 mutex); 902 } 903 } 904 905 @Override public SortedSet<E> tailSet(E start) { 906 synchronized (mutex) { 907 return new SynchronizedSortedSet<E>(ss.tailSet(start), mutex); 908 } 909 } 910 911 private void writeObject(ObjectOutputStream stream) throws IOException { 912 synchronized (mutex) { 913 stream.defaultWriteObject(); 914 } 915 } 916 } 917 918 private static class UnmodifiableCollection<E> implements Collection<E>, Serializable { 919 private static final long serialVersionUID = 1820017752578914078L; 920 921 final Collection<E> c; 922 923 UnmodifiableCollection(Collection<E> collection) { 924 c = collection; 925 } 926 927 @Override public boolean add(E object) { 928 throw new UnsupportedOperationException(); 929 } 930 931 @Override public boolean addAll(Collection<? extends E> collection) { 932 throw new UnsupportedOperationException(); 933 } 934 935 @Override public void clear() { 936 throw new UnsupportedOperationException(); 937 } 938 939 @Override public boolean contains(Object object) { 940 return c.contains(object); 941 } 942 943 @Override public boolean containsAll(Collection<?> collection) { 944 return c.containsAll(collection); 945 } 946 947 @Override public boolean isEmpty() { 948 return c.isEmpty(); 949 } 950 951 @Override public Iterator<E> iterator() { 952 return new Iterator<E>() { 953 Iterator<E> iterator = c.iterator(); 954 955 @Override public boolean hasNext() { 956 return iterator.hasNext(); 957 } 958 959 @Override public E next() { 960 return iterator.next(); 961 } 962 963 @Override public void remove() { 964 throw new UnsupportedOperationException(); 965 } 966 }; 967 } 968 969 @Override public boolean remove(Object object) { 970 throw new UnsupportedOperationException(); 971 } 972 973 @Override public boolean removeAll(Collection<?> collection) { 974 throw new UnsupportedOperationException(); 975 } 976 977 @Override public boolean retainAll(Collection<?> collection) { 978 throw new UnsupportedOperationException(); 979 } 980 981 @Override public int size() { 982 return c.size(); 983 } 984 985 @Override public Object[] toArray() { 986 return c.toArray(); 987 } 988 989 @Override public <T> T[] toArray(T[] array) { 990 return c.toArray(array); 991 } 992 993 @Override public String toString() { 994 return c.toString(); 995 } 996 } 997 998 private static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E> 999 implements RandomAccess { 1000 private static final long serialVersionUID = -2542308836966382001L; 1001 1002 UnmodifiableRandomAccessList(List<E> l) { 1003 super(l); 1004 } 1005 1006 @Override public List<E> subList(int start, int end) { 1007 return new UnmodifiableRandomAccessList<E>(list.subList(start, end)); 1008 } 1009 1010 /** 1011 * Replaces this UnmodifiableRandomAccessList with an UnmodifiableList 1012 * so that JREs before 1.4 can deserialize this object without any 1013 * problems. This is necessary since RandomAccess API was introduced 1014 * only in 1.4. 1015 * <p> 1016 * 1017 * @return UnmodifiableList 1018 * 1019 * @see UnmodifiableList#readResolve() 1020 */ 1021 private Object writeReplace() { 1022 return new UnmodifiableList<E>(list); 1023 } 1024 } 1025 1026 private static class UnmodifiableList<E> extends UnmodifiableCollection<E> 1027 implements List<E> { 1028 private static final long serialVersionUID = -283967356065247728L; 1029 1030 final List<E> list; 1031 1032 UnmodifiableList(List<E> l) { 1033 super(l); 1034 list = l; 1035 } 1036 1037 @Override public void add(int location, E object) { 1038 throw new UnsupportedOperationException(); 1039 } 1040 1041 @Override public boolean addAll(int location, Collection<? extends E> collection) { 1042 throw new UnsupportedOperationException(); 1043 } 1044 1045 @Override public boolean equals(Object object) { 1046 return list.equals(object); 1047 } 1048 1049 @Override public E get(int location) { 1050 return list.get(location); 1051 } 1052 1053 @Override public int hashCode() { 1054 return list.hashCode(); 1055 } 1056 1057 @Override public int indexOf(Object object) { 1058 return list.indexOf(object); 1059 } 1060 1061 @Override public int lastIndexOf(Object object) { 1062 return list.lastIndexOf(object); 1063 } 1064 1065 @Override public ListIterator<E> listIterator() { 1066 return listIterator(0); 1067 } 1068 1069 @Override public ListIterator<E> listIterator(final int location) { 1070 return new ListIterator<E>() { 1071 ListIterator<E> iterator = list.listIterator(location); 1072 1073 @Override public void add(E object) { 1074 throw new UnsupportedOperationException(); 1075 } 1076 1077 @Override public boolean hasNext() { 1078 return iterator.hasNext(); 1079 } 1080 1081 @Override public boolean hasPrevious() { 1082 return iterator.hasPrevious(); 1083 } 1084 1085 @Override public E next() { 1086 return iterator.next(); 1087 } 1088 1089 @Override public int nextIndex() { 1090 return iterator.nextIndex(); 1091 } 1092 1093 @Override public E previous() { 1094 return iterator.previous(); 1095 } 1096 1097 @Override public int previousIndex() { 1098 return iterator.previousIndex(); 1099 } 1100 1101 @Override public void remove() { 1102 throw new UnsupportedOperationException(); 1103 } 1104 1105 @Override public void set(E object) { 1106 throw new UnsupportedOperationException(); 1107 } 1108 }; 1109 } 1110 1111 @Override public E remove(int location) { 1112 throw new UnsupportedOperationException(); 1113 } 1114 1115 @Override public E set(int location, E object) { 1116 throw new UnsupportedOperationException(); 1117 } 1118 1119 @Override public List<E> subList(int start, int end) { 1120 return new UnmodifiableList<E>(list.subList(start, end)); 1121 } 1122 1123 /** 1124 * Resolves UnmodifiableList instances to UnmodifiableRandomAccessList 1125 * instances if the underlying list is a Random Access list. 1126 * <p> 1127 * This is necessary since UnmodifiableRandomAccessList instances are 1128 * replaced with UnmodifiableList instances during serialization for 1129 * compliance with JREs before 1.4. 1130 * <p> 1131 * 1132 * @return an UnmodifiableList instance if the underlying list 1133 * implements RandomAccess interface, or this same object if 1134 * not. 1135 * 1136 * @see UnmodifiableRandomAccessList#writeReplace() 1137 */ 1138 private Object readResolve() { 1139 if (list instanceof RandomAccess) { 1140 return new UnmodifiableRandomAccessList<E>(list); 1141 } 1142 return this; 1143 } 1144 } 1145 1146 private static class UnmodifiableMap<K, V> implements Map<K, V>, 1147 Serializable { 1148 private static final long serialVersionUID = -1034234728574286014L; 1149 1150 private final Map<K, V> m; 1151 1152 private static class UnmodifiableEntrySet<K, V> extends 1153 UnmodifiableSet<Map.Entry<K, V>> { 1154 private static final long serialVersionUID = 7854390611657943733L; 1155 1156 private static class UnmodifiableMapEntry<K, V> implements 1157 Map.Entry<K, V> { 1158 Map.Entry<K, V> mapEntry; 1159 1160 UnmodifiableMapEntry(Map.Entry<K, V> entry) { 1161 mapEntry = entry; 1162 } 1163 1164 @Override public boolean equals(Object object) { 1165 return mapEntry.equals(object); 1166 } 1167 1168 @Override public K getKey() { 1169 return mapEntry.getKey(); 1170 } 1171 1172 @Override public V getValue() { 1173 return mapEntry.getValue(); 1174 } 1175 1176 @Override public int hashCode() { 1177 return mapEntry.hashCode(); 1178 } 1179 1180 @Override public V setValue(V object) { 1181 throw new UnsupportedOperationException(); 1182 } 1183 1184 @Override public String toString() { 1185 return mapEntry.toString(); 1186 } 1187 } 1188 1189 UnmodifiableEntrySet(Set<Map.Entry<K, V>> set) { 1190 super(set); 1191 } 1192 1193 @Override public Iterator<Map.Entry<K, V>> iterator() { 1194 return new Iterator<Map.Entry<K, V>>() { 1195 Iterator<Map.Entry<K, V>> iterator = c.iterator(); 1196 1197 @Override public boolean hasNext() { 1198 return iterator.hasNext(); 1199 } 1200 1201 @Override public Map.Entry<K, V> next() { 1202 return new UnmodifiableMapEntry<K, V>(iterator.next()); 1203 } 1204 1205 @Override public void remove() { 1206 throw new UnsupportedOperationException(); 1207 } 1208 }; 1209 } 1210 1211 @Override public Object[] toArray() { 1212 int length = c.size(); 1213 Object[] result = new Object[length]; 1214 Iterator<?> it = iterator(); 1215 for (int i = 0; i < length; i++) { 1216 result[i] = it.next(); 1217 } 1218 return result; 1219 } 1220 1221 @SuppressWarnings("unchecked") 1222 @Override public <T> T[] toArray(T[] contents) { 1223 int size = c.size(), index = 0; 1224 Iterator<Map.Entry<K, V>> it = iterator(); 1225 if (size > contents.length) { 1226 Class<?> ct = contents.getClass().getComponentType(); 1227 contents = (T[]) Array.newInstance(ct, size); 1228 } 1229 while (index < size) { 1230 contents[index++] = (T) it.next(); 1231 } 1232 if (index < contents.length) { 1233 contents[index] = null; 1234 } 1235 return contents; 1236 } 1237 } 1238 1239 UnmodifiableMap(Map<K, V> map) { 1240 m = map; 1241 } 1242 1243 @Override public void clear() { 1244 throw new UnsupportedOperationException(); 1245 } 1246 1247 @Override public boolean containsKey(Object key) { 1248 return m.containsKey(key); 1249 } 1250 1251 @Override public boolean containsValue(Object value) { 1252 return m.containsValue(value); 1253 } 1254 1255 @Override public Set<Map.Entry<K, V>> entrySet() { 1256 return new UnmodifiableEntrySet<K, V>(m.entrySet()); 1257 } 1258 1259 @Override public boolean equals(Object object) { 1260 return m.equals(object); 1261 } 1262 1263 @Override public V get(Object key) { 1264 return m.get(key); 1265 } 1266 1267 @Override public int hashCode() { 1268 return m.hashCode(); 1269 } 1270 1271 @Override public boolean isEmpty() { 1272 return m.isEmpty(); 1273 } 1274 1275 @Override public Set<K> keySet() { 1276 return new UnmodifiableSet<K>(m.keySet()); 1277 } 1278 1279 @Override public V put(K key, V value) { 1280 throw new UnsupportedOperationException(); 1281 } 1282 1283 @Override public void putAll(Map<? extends K, ? extends V> map) { 1284 throw new UnsupportedOperationException(); 1285 } 1286 1287 @Override public V remove(Object key) { 1288 throw new UnsupportedOperationException(); 1289 } 1290 1291 @Override public int size() { 1292 return m.size(); 1293 } 1294 1295 @Override public Collection<V> values() { 1296 return new UnmodifiableCollection<V>(m.values()); 1297 } 1298 1299 @Override public String toString() { 1300 return m.toString(); 1301 } 1302 } 1303 1304 private static class UnmodifiableSet<E> extends UnmodifiableCollection<E> 1305 implements Set<E> { 1306 private static final long serialVersionUID = -9215047833775013803L; 1307 1308 UnmodifiableSet(Set<E> set) { 1309 super(set); 1310 } 1311 1312 @Override public boolean equals(Object object) { 1313 return c.equals(object); 1314 } 1315 1316 @Override public int hashCode() { 1317 return c.hashCode(); 1318 } 1319 } 1320 1321 private static class UnmodifiableSortedMap<K, V> extends 1322 UnmodifiableMap<K, V> implements SortedMap<K, V> { 1323 private static final long serialVersionUID = -8806743815996713206L; 1324 1325 private final SortedMap<K, V> sm; 1326 1327 UnmodifiableSortedMap(SortedMap<K, V> map) { 1328 super(map); 1329 sm = map; 1330 } 1331 1332 @Override public Comparator<? super K> comparator() { 1333 return sm.comparator(); 1334 } 1335 1336 @Override public K firstKey() { 1337 return sm.firstKey(); 1338 } 1339 1340 @Override public SortedMap<K, V> headMap(K before) { 1341 return new UnmodifiableSortedMap<K, V>(sm.headMap(before)); 1342 } 1343 1344 @Override public K lastKey() { 1345 return sm.lastKey(); 1346 } 1347 1348 @Override public SortedMap<K, V> subMap(K start, K end) { 1349 return new UnmodifiableSortedMap<K, V>(sm.subMap(start, end)); 1350 } 1351 1352 @Override public SortedMap<K, V> tailMap(K after) { 1353 return new UnmodifiableSortedMap<K, V>(sm.tailMap(after)); 1354 } 1355 } 1356 1357 private static class UnmodifiableSortedSet<E> extends UnmodifiableSet<E> 1358 implements SortedSet<E> { 1359 private static final long serialVersionUID = -4929149591599911165L; 1360 1361 private final SortedSet<E> ss; 1362 1363 UnmodifiableSortedSet(SortedSet<E> set) { 1364 super(set); 1365 ss = set; 1366 } 1367 1368 @Override public Comparator<? super E> comparator() { 1369 return ss.comparator(); 1370 } 1371 1372 @Override public E first() { 1373 return ss.first(); 1374 } 1375 1376 @Override public SortedSet<E> headSet(E before) { 1377 return new UnmodifiableSortedSet<E>(ss.headSet(before)); 1378 } 1379 1380 @Override public E last() { 1381 return ss.last(); 1382 } 1383 1384 @Override public SortedSet<E> subSet(E start, E end) { 1385 return new UnmodifiableSortedSet<E>(ss.subSet(start, end)); 1386 } 1387 1388 @Override public SortedSet<E> tailSet(E after) { 1389 return new UnmodifiableSortedSet<E>(ss.tailSet(after)); 1390 } 1391 } 1392 1393 private Collections() {} 1394 1395 /** 1396 * Performs a binary search for the specified element in the specified 1397 * sorted list. The list needs to be already sorted in natural sorting 1398 * order. Searching in an unsorted array has an undefined result. It's also 1399 * undefined which element is found if there are multiple occurrences of the 1400 * same element. 1401 * 1402 * @param list 1403 * the sorted list to search. 1404 * @param object 1405 * the element to find. 1406 * @return the non-negative index of the element, or a negative index which 1407 * is the {@code -index - 1} where the element would be inserted 1408 * @throws ClassCastException 1409 * if an element in the List or the search element does not 1410 * implement Comparable, or cannot be compared to each other. 1411 */ 1412 @SuppressWarnings("unchecked") 1413 public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T object) { 1414 if (list == null) { 1415 throw new NullPointerException("list == null"); 1416 } 1417 if (list.isEmpty()) { 1418 return -1; 1419 } 1420 1421 1422 if (!(list instanceof RandomAccess)) { 1423 ListIterator<? extends Comparable<? super T>> it = list.listIterator(); 1424 while (it.hasNext()) { 1425 int result; 1426 if ((result = -it.next().compareTo(object)) <= 0) { 1427 if (result == 0) { 1428 return it.previousIndex(); 1429 } 1430 return -it.previousIndex() - 1; 1431 } 1432 } 1433 return -list.size() - 1; 1434 } 1435 1436 int low = 0, mid = list.size(), high = mid - 1, result = -1; 1437 while (low <= high) { 1438 mid = (low + high) >>> 1; 1439 if ((result = -list.get(mid).compareTo(object)) > 0) { 1440 low = mid + 1; 1441 } else if (result == 0) { 1442 return mid; 1443 } else { 1444 high = mid - 1; 1445 } 1446 } 1447 return -mid - (result < 0 ? 1 : 2); 1448 } 1449 1450 /** 1451 * Performs a binary search for the specified element in the specified 1452 * sorted list using the specified comparator. The list needs to be already 1453 * sorted according to the comparator passed. Searching in an unsorted array 1454 * has an undefined result. It's also undefined which element is found if 1455 * there are multiple occurrences of the same element. 1456 * 1457 * @param list 1458 * the sorted List to search. 1459 * @param object 1460 * the element to find. 1461 * @param comparator 1462 * the comparator. If the comparator is {@code null} then the 1463 * search uses the objects' natural ordering. 1464 * @return the non-negative index of the element, or a negative index which 1465 * is the {@code -index - 1} where the element would be inserted. 1466 * @throws ClassCastException 1467 * when an element in the list and the searched element cannot 1468 * be compared to each other using the comparator. 1469 */ 1470 @SuppressWarnings("unchecked") 1471 public static <T> int binarySearch(List<? extends T> list, T object, 1472 Comparator<? super T> comparator) { 1473 if (comparator == null) { 1474 return Collections.binarySearch( 1475 (List<? extends Comparable<? super T>>) list, object); 1476 } 1477 if (!(list instanceof RandomAccess)) { 1478 ListIterator<? extends T> it = list.listIterator(); 1479 while (it.hasNext()) { 1480 int result; 1481 if ((result = -comparator.compare(it.next(), object)) <= 0) { 1482 if (result == 0) { 1483 return it.previousIndex(); 1484 } 1485 return -it.previousIndex() - 1; 1486 } 1487 } 1488 return -list.size() - 1; 1489 } 1490 1491 int low = 0, mid = list.size(), high = mid - 1, result = -1; 1492 while (low <= high) { 1493 mid = (low + high) >>> 1; 1494 if ((result = -comparator.compare(list.get(mid), object)) > 0) { 1495 low = mid + 1; 1496 } else if (result == 0) { 1497 return mid; 1498 } else { 1499 high = mid - 1; 1500 } 1501 } 1502 return -mid - (result < 0 ? 1 : 2); 1503 } 1504 1505 /** 1506 * Copies the elements from the source list to the destination list. At the 1507 * end both lists will have the same objects at the same index. If the 1508 * destination array is larger than the source list, the elements in the 1509 * destination list with {@code index >= source.size()} will be unchanged. 1510 * 1511 * @param destination 1512 * the list whose elements are set from the source list. 1513 * @param source 1514 * the list with the elements to be copied into the destination. 1515 * @throws IndexOutOfBoundsException 1516 * when the destination list is smaller than the source list. 1517 * @throws UnsupportedOperationException 1518 * when replacing an element in the destination list is not 1519 * supported. 1520 */ 1521 public static <T> void copy(List<? super T> destination, List<? extends T> source) { 1522 if (destination.size() < source.size()) { 1523 throw new IndexOutOfBoundsException("destination.size() < source.size(): " + 1524 destination.size() + " < " + source.size()); 1525 } 1526 Iterator<? extends T> srcIt = source.iterator(); 1527 ListIterator<? super T> destIt = destination.listIterator(); 1528 while (srcIt.hasNext()) { 1529 try { 1530 destIt.next(); 1531 } catch (NoSuchElementException e) { 1532 // TODO: AssertionError? 1533 throw new IndexOutOfBoundsException("Source size " + source.size() + 1534 " does not fit into destination"); 1535 } 1536 destIt.set(srcIt.next()); 1537 } 1538 } 1539 1540 /** 1541 * Returns an {@code Enumeration} on the specified collection. 1542 * 1543 * @param collection 1544 * the collection to enumerate. 1545 * @return an Enumeration. 1546 */ 1547 public static <T> Enumeration<T> enumeration(Collection<T> collection) { 1548 final Collection<T> c = collection; 1549 return new Enumeration<T>() { 1550 Iterator<T> it = c.iterator(); 1551 1552 @Override public boolean hasMoreElements() { 1553 return it.hasNext(); 1554 } 1555 1556 @Override public T nextElement() { 1557 return it.next(); 1558 } 1559 }; 1560 } 1561 1562 /** 1563 * Fills the specified list with the specified element. 1564 * 1565 * @param list 1566 * the list to fill. 1567 * @param object 1568 * the element to fill the list with. 1569 * @throws UnsupportedOperationException 1570 * when replacing an element in the List is not supported. 1571 */ 1572 public static <T> void fill(List<? super T> list, T object) { 1573 ListIterator<? super T> it = list.listIterator(); 1574 while (it.hasNext()) { 1575 it.next(); 1576 it.set(object); 1577 } 1578 } 1579 1580 /** 1581 * Searches the specified collection for the maximum element. 1582 * 1583 * @param collection 1584 * the collection to search. 1585 * @return the maximum element in the Collection. 1586 * @throws ClassCastException 1587 * when an element in the collection does not implement 1588 * {@code Comparable} or elements cannot be compared to each 1589 * other. 1590 */ 1591 public static <T extends Object & Comparable<? super T>> T max( 1592 Collection<? extends T> collection) { 1593 Iterator<? extends T> it = collection.iterator(); 1594 T max = it.next(); 1595 while (it.hasNext()) { 1596 T next = it.next(); 1597 if (max.compareTo(next) < 0) { 1598 max = next; 1599 } 1600 } 1601 return max; 1602 } 1603 1604 /** 1605 * Searches the specified collection for the maximum element using the 1606 * specified comparator. 1607 * 1608 * @param collection 1609 * the collection to search. 1610 * @param comparator 1611 * the comparator. 1612 * @return the maximum element in the Collection. 1613 * @throws ClassCastException 1614 * when elements in the collection cannot be compared to each 1615 * other using the {@code Comparator}. 1616 */ 1617 public static <T> T max(Collection<? extends T> collection, 1618 Comparator<? super T> comparator) { 1619 if (comparator == null) { 1620 @SuppressWarnings("unchecked") // null comparator? T is comparable 1621 T result = (T) max((Collection<Comparable>) collection); 1622 return result; 1623 } 1624 1625 Iterator<? extends T> it = collection.iterator(); 1626 T max = it.next(); 1627 while (it.hasNext()) { 1628 T next = it.next(); 1629 if (comparator.compare(max, next) < 0) { 1630 max = next; 1631 } 1632 } 1633 return max; 1634 } 1635 1636 /** 1637 * Searches the specified collection for the minimum element. 1638 * 1639 * @param collection 1640 * the collection to search. 1641 * @return the minimum element in the collection. 1642 * @throws ClassCastException 1643 * when an element in the collection does not implement 1644 * {@code Comparable} or elements cannot be compared to each 1645 * other. 1646 */ 1647 public static <T extends Object & Comparable<? super T>> T min( 1648 Collection<? extends T> collection) { 1649 Iterator<? extends T> it = collection.iterator(); 1650 T min = it.next(); 1651 while (it.hasNext()) { 1652 T next = it.next(); 1653 if (min.compareTo(next) > 0) { 1654 min = next; 1655 } 1656 } 1657 return min; 1658 } 1659 1660 /** 1661 * Searches the specified collection for the minimum element using the 1662 * specified comparator. 1663 * 1664 * @param collection 1665 * the collection to search. 1666 * @param comparator 1667 * the comparator. 1668 * @return the minimum element in the collection. 1669 * @throws ClassCastException 1670 * when elements in the collection cannot be compared to each 1671 * other using the {@code Comparator}. 1672 */ 1673 public static <T> T min(Collection<? extends T> collection, 1674 Comparator<? super T> comparator) { 1675 if (comparator == null) { 1676 @SuppressWarnings("unchecked") // null comparator? T is comparable 1677 T result = (T) min((Collection<Comparable>) collection); 1678 return result; 1679 } 1680 1681 Iterator<? extends T> it = collection.iterator(); 1682 T min = it.next(); 1683 while (it.hasNext()) { 1684 T next = it.next(); 1685 if (comparator.compare(min, next) > 0) { 1686 min = next; 1687 } 1688 } 1689 return min; 1690 } 1691 1692 /** 1693 * Returns a list containing the specified number of the specified element. 1694 * The list cannot be modified. The list is serializable. 1695 * 1696 * @param length 1697 * the size of the returned list. 1698 * @param object 1699 * the element to be added {@code length} times to a list. 1700 * @return a list containing {@code length} copies of the element. 1701 * @throws IllegalArgumentException 1702 * when {@code length < 0}. 1703 */ 1704 public static <T> List<T> nCopies(final int length, T object) { 1705 return new CopiesList<T>(length, object); 1706 } 1707 1708 /** 1709 * Modifies the specified {@code List} by reversing the order of the 1710 * elements. 1711 * 1712 * @param list 1713 * the list to reverse. 1714 * @throws UnsupportedOperationException 1715 * when replacing an element in the List is not supported. 1716 */ 1717 @SuppressWarnings("unchecked") 1718 public static void reverse(List<?> list) { 1719 int size = list.size(); 1720 ListIterator<Object> front = (ListIterator<Object>) list.listIterator(); 1721 ListIterator<Object> back = (ListIterator<Object>) list 1722 .listIterator(size); 1723 for (int i = 0; i < size / 2; i++) { 1724 Object frontNext = front.next(); 1725 Object backPrev = back.previous(); 1726 front.set(backPrev); 1727 back.set(frontNext); 1728 } 1729 } 1730 1731 /** 1732 * A comparator which reverses the natural order of the elements. The 1733 * {@code Comparator} that's returned is {@link Serializable}. 1734 * 1735 * @return a {@code Comparator} instance. 1736 */ 1737 @SuppressWarnings("unchecked") 1738 public static <T> Comparator<T> reverseOrder() { 1739 return (Comparator) ReverseComparator.INSTANCE; 1740 } 1741 1742 /** 1743 * Returns a {@link Comparator} that reverses the order of the 1744 * {@code Comparator} passed. If the {@code Comparator} passed is 1745 * {@code null}, then this method is equivalent to {@link #reverseOrder()}. 1746 * <p> 1747 * The {@code Comparator} that's returned is {@link Serializable} if the 1748 * {@code Comparator} passed is serializable or {@code null}. 1749 * 1750 * @param c 1751 * the {@code Comparator} to reverse or {@code null}. 1752 * @return a {@code Comparator} instance. 1753 * @since 1.5 1754 */ 1755 public static <T> Comparator<T> reverseOrder(Comparator<T> c) { 1756 if (c == null) { 1757 return reverseOrder(); 1758 } 1759 if (c instanceof ReverseComparator2) { 1760 return ((ReverseComparator2<T>) c).cmp; 1761 } 1762 return new ReverseComparator2<T>(c); 1763 } 1764 1765 /** 1766 * Moves every element of the list to a random new position in the list. 1767 * 1768 * @param list 1769 * the List to shuffle. 1770 * 1771 * @throws UnsupportedOperationException 1772 * when replacing an element in the List is not supported. 1773 */ 1774 public static void shuffle(List<?> list) { 1775 shuffle(list, new Random()); 1776 } 1777 1778 /** 1779 * Moves every element of the list to a random new position in the list 1780 * using the specified random number generator. 1781 * 1782 * @param list 1783 * the list to shuffle. 1784 * @param random 1785 * the random number generator. 1786 * @throws UnsupportedOperationException 1787 * when replacing an element in the list is not supported. 1788 */ 1789 public static void shuffle(List<?> list, Random random) { 1790 @SuppressWarnings("unchecked") // we won't put foreign objects in 1791 final List<Object> objectList = (List<Object>) list; 1792 1793 if (list instanceof RandomAccess) { 1794 for (int i = objectList.size() - 1; i > 0; i--) { 1795 int index = random.nextInt(i + 1); 1796 objectList.set(index, objectList.set(i, objectList.get(index))); 1797 } 1798 } else { 1799 Object[] array = objectList.toArray(); 1800 for (int i = array.length - 1; i > 0; i--) { 1801 int index = random.nextInt(i + 1); 1802 Object temp = array[i]; 1803 array[i] = array[index]; 1804 array[index] = temp; 1805 } 1806 1807 int i = 0; 1808 ListIterator<Object> it = objectList.listIterator(); 1809 while (it.hasNext()) { 1810 it.next(); 1811 it.set(array[i++]); 1812 } 1813 } 1814 } 1815 1816 /** 1817 * Returns a set containing the specified element. The set cannot be 1818 * modified. The set is serializable. 1819 * 1820 * @param object 1821 * the element. 1822 * @return a set containing the element. 1823 */ 1824 public static <E> Set<E> singleton(E object) { 1825 return new SingletonSet<E>(object); 1826 } 1827 1828 /** 1829 * Returns a list containing the specified element. The list cannot be 1830 * modified. The list is serializable. 1831 * 1832 * @param object 1833 * the element. 1834 * @return a list containing the element. 1835 */ 1836 public static <E> List<E> singletonList(E object) { 1837 return new SingletonList<E>(object); 1838 } 1839 1840 /** 1841 * Returns a Map containing the specified key and value. The map cannot be 1842 * modified. The map is serializable. 1843 * 1844 * @param key 1845 * the key. 1846 * @param value 1847 * the value. 1848 * @return a Map containing the key and value. 1849 */ 1850 public static <K, V> Map<K, V> singletonMap(K key, V value) { 1851 return new SingletonMap<K, V>(key, value); 1852 } 1853 1854 /** 1855 * Sorts the given list in ascending natural order. The algorithm is 1856 * stable which means equal elements don't get reordered. 1857 * 1858 * @throws ClassCastException if any element does not implement {@code Comparable}, 1859 * or if {@code compareTo} throws for any pair of elements. 1860 */ 1861 @SuppressWarnings("unchecked") 1862 public static <T extends Comparable<? super T>> void sort(List<T> list) { 1863 Object[] array = list.toArray(); 1864 Arrays.sort(array); 1865 int i = 0; 1866 ListIterator<T> it = list.listIterator(); 1867 while (it.hasNext()) { 1868 it.next(); 1869 it.set((T) array[i++]); 1870 } 1871 } 1872 1873 /** 1874 * Sorts the given list using the given comparator. The algorithm is 1875 * stable which means equal elements don't get reordered. 1876 * 1877 * @throws ClassCastException if any element does not implement {@code Comparable}, 1878 * or if {@code compareTo} throws for any pair of elements. 1879 */ 1880 @SuppressWarnings("unchecked") 1881 public static <T> void sort(List<T> list, Comparator<? super T> comparator) { 1882 T[] array = list.toArray((T[]) new Object[list.size()]); 1883 Arrays.sort(array, comparator); 1884 int i = 0; 1885 ListIterator<T> it = list.listIterator(); 1886 while (it.hasNext()) { 1887 it.next(); 1888 it.set(array[i++]); 1889 } 1890 } 1891 1892 /** 1893 * Swaps the elements of list {@code list} at indices {@code index1} and 1894 * {@code index2}. 1895 * 1896 * @param list 1897 * the list to manipulate. 1898 * @param index1 1899 * position of the first element to swap with the element in 1900 * index2. 1901 * @param index2 1902 * position of the other element. 1903 * 1904 * @throws IndexOutOfBoundsException 1905 * if index1 or index2 is out of range of this list. 1906 * @since 1.4 1907 */ 1908 @SuppressWarnings("unchecked") 1909 public static void swap(List<?> list, int index1, int index2) { 1910 if (list == null) { 1911 throw new NullPointerException("list == null"); 1912 } 1913 final int size = list.size(); 1914 if (index1 < 0 || index1 >= size || index2 < 0 || index2 >= size) { 1915 throw new IndexOutOfBoundsException(); 1916 } 1917 if (index1 == index2) { 1918 return; 1919 } 1920 List<Object> rawList = (List<Object>) list; 1921 rawList.set(index2, rawList.set(index1, rawList.get(index2))); 1922 } 1923 1924 /** 1925 * Replaces all occurrences of Object {@code obj} in {@code list} with 1926 * {@code newObj}. If the {@code obj} is {@code null}, then all 1927 * occurrences of {@code null} are replaced with {@code newObj}. 1928 * 1929 * @param list 1930 * the list to modify. 1931 * @param obj 1932 * the object to find and replace occurrences of. 1933 * @param obj2 1934 * the object to replace all occurrences of {@code obj} in 1935 * {@code list}. 1936 * @return true, if at least one occurrence of {@code obj} has been found in 1937 * {@code list}. 1938 * @throws UnsupportedOperationException 1939 * if the list does not support setting elements. 1940 */ 1941 public static <T> boolean replaceAll(List<T> list, T obj, T obj2) { 1942 int index; 1943 boolean found = false; 1944 1945 while ((index = list.indexOf(obj)) > -1) { 1946 found = true; 1947 list.set(index, obj2); 1948 } 1949 return found; 1950 } 1951 1952 /** 1953 * Rotates the elements in {@code list} by the distance {@code dist} 1954 * <p> 1955 * e.g. for a given list with elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], 1956 * calling rotate(list, 3) or rotate(list, -7) would modify the list to look 1957 * like this: [8, 9, 0, 1, 2, 3, 4, 5, 6, 7] 1958 * 1959 * @param lst 1960 * the list whose elements are to be rotated. 1961 * @param dist 1962 * is the distance the list is rotated. This can be any valid 1963 * integer. Negative values rotate the list backwards. 1964 */ 1965 @SuppressWarnings("unchecked") 1966 public static void rotate(List<?> lst, int dist) { 1967 List<Object> list = (List<Object>) lst; 1968 int size = list.size(); 1969 1970 // Can't sensibly rotate an empty collection 1971 if (size == 0) { 1972 return; 1973 } 1974 1975 // normalize the distance 1976 int normdist; 1977 if (dist > 0) { 1978 normdist = dist % size; 1979 } else { 1980 normdist = size - ((dist % size) * (-1)); 1981 } 1982 1983 if (normdist == 0 || normdist == size) { 1984 return; 1985 } 1986 1987 if (list instanceof RandomAccess) { 1988 // make sure each element gets juggled 1989 // with the element in the position it is supposed to go to 1990 Object temp = list.get(0); 1991 int index = 0, beginIndex = 0; 1992 for (int i = 0; i < size; i++) { 1993 index = (index + normdist) % size; 1994 temp = list.set(index, temp); 1995 if (index == beginIndex) { 1996 index = ++beginIndex; 1997 temp = list.get(beginIndex); 1998 } 1999 } 2000 } else { 2001 int divideIndex = (size - normdist) % size; 2002 List<Object> sublist1 = list.subList(0, divideIndex); 2003 List<Object> sublist2 = list.subList(divideIndex, size); 2004 reverse(sublist1); 2005 reverse(sublist2); 2006 reverse(list); 2007 } 2008 } 2009 2010 /** 2011 * Searches the {@code list} for {@code sublist} and returns the beginning 2012 * index of the first occurrence. 2013 * <p> 2014 * -1 is returned if the {@code sublist} does not exist in {@code list}. 2015 * 2016 * @param list 2017 * the List to search {@code sublist} in. 2018 * @param sublist 2019 * the List to search in {@code list}. 2020 * @return the beginning index of the first occurrence of {@code sublist} in 2021 * {@code list}, or -1. 2022 */ 2023 public static int indexOfSubList(List<?> list, List<?> sublist) { 2024 int size = list.size(); 2025 int sublistSize = sublist.size(); 2026 2027 if (sublistSize > size) { 2028 return -1; 2029 } 2030 2031 if (sublistSize == 0) { 2032 return 0; 2033 } 2034 2035 // find the first element of sublist in the list to get a head start 2036 Object firstObj = sublist.get(0); 2037 int index = list.indexOf(firstObj); 2038 if (index == -1) { 2039 return -1; 2040 } 2041 2042 while (index < size && (size - index >= sublistSize)) { 2043 ListIterator<?> listIt = list.listIterator(index); 2044 2045 if ((firstObj == null) ? listIt.next() == null : firstObj 2046 .equals(listIt.next())) { 2047 2048 // iterate through the elements in sublist to see 2049 // if they are included in the same order in the list 2050 ListIterator<?> sublistIt = sublist.listIterator(1); 2051 boolean difFound = false; 2052 while (sublistIt.hasNext()) { 2053 Object element = sublistIt.next(); 2054 if (!listIt.hasNext()) { 2055 return -1; 2056 } 2057 if ((element == null) ? listIt.next() != null : !element 2058 .equals(listIt.next())) { 2059 difFound = true; 2060 break; 2061 } 2062 } 2063 // All elements of sublist are found in main list 2064 // starting from index. 2065 if (!difFound) { 2066 return index; 2067 } 2068 } 2069 // This was not the sequence we were looking for, 2070 // continue search for the firstObj in main list 2071 // at the position after index. 2072 index++; 2073 } 2074 return -1; 2075 } 2076 2077 /** 2078 * Searches the {@code list} for {@code sublist} and returns the beginning 2079 * index of the last occurrence. 2080 * <p> 2081 * -1 is returned if the {@code sublist} does not exist in {@code list}. 2082 * 2083 * @param list 2084 * the list to search {@code sublist} in. 2085 * @param sublist 2086 * the list to search in {@code list}. 2087 * @return the beginning index of the last occurrence of {@code sublist} in 2088 * {@code list}, or -1. 2089 */ 2090 public static int lastIndexOfSubList(List<?> list, List<?> sublist) { 2091 int sublistSize = sublist.size(); 2092 int size = list.size(); 2093 2094 if (sublistSize > size) { 2095 return -1; 2096 } 2097 2098 if (sublistSize == 0) { 2099 return size; 2100 } 2101 2102 // find the last element of sublist in the list to get a head start 2103 Object lastObj = sublist.get(sublistSize - 1); 2104 int index = list.lastIndexOf(lastObj); 2105 2106 while ((index > -1) && (index + 1 >= sublistSize)) { 2107 ListIterator<?> listIt = list.listIterator(index + 1); 2108 2109 if ((lastObj == null) ? listIt.previous() == null : lastObj 2110 .equals(listIt.previous())) { 2111 // iterate through the elements in sublist to see 2112 // if they are included in the same order in the list 2113 ListIterator<?> sublistIt = sublist 2114 .listIterator(sublistSize - 1); 2115 boolean difFound = false; 2116 while (sublistIt.hasPrevious()) { 2117 Object element = sublistIt.previous(); 2118 if (!listIt.hasPrevious()) { 2119 return -1; 2120 } 2121 if ((element == null) ? listIt.previous() != null 2122 : !element.equals(listIt.previous())) { 2123 difFound = true; 2124 break; 2125 } 2126 } 2127 // All elements of sublist are found in main list 2128 // starting from listIt.nextIndex(). 2129 if (!difFound) { 2130 return listIt.nextIndex(); 2131 } 2132 } 2133 // This was not the sequence we were looking for, 2134 // continue search for the lastObj in main list 2135 // at the position before index. 2136 index--; 2137 } 2138 return -1; 2139 } 2140 2141 /** 2142 * Returns an {@code ArrayList} with all the elements in the {@code 2143 * enumeration}. The elements in the returned {@code ArrayList} are in the 2144 * same order as in the {@code enumeration}. 2145 * 2146 * @param enumeration 2147 * the source {@link Enumeration}. 2148 * @return an {@code ArrayList} from {@code enumeration}. 2149 */ 2150 public static <T> ArrayList<T> list(Enumeration<T> enumeration) { 2151 ArrayList<T> list = new ArrayList<T>(); 2152 while (enumeration.hasMoreElements()) { 2153 list.add(enumeration.nextElement()); 2154 } 2155 return list; 2156 } 2157 2158 /** 2159 * Returns a wrapper on the specified collection which synchronizes all 2160 * access to the collection. 2161 * 2162 * @param collection 2163 * the Collection to wrap in a synchronized collection. 2164 * @return a synchronized Collection. 2165 */ 2166 public static <T> Collection<T> synchronizedCollection( 2167 Collection<T> collection) { 2168 if (collection == null) { 2169 throw new NullPointerException("collection == null"); 2170 } 2171 return new SynchronizedCollection<T>(collection); 2172 } 2173 2174 /** 2175 * Returns a wrapper on the specified List which synchronizes all access to 2176 * the List. 2177 * 2178 * @param list 2179 * the List to wrap in a synchronized list. 2180 * @return a synchronized List. 2181 */ 2182 public static <T> List<T> synchronizedList(List<T> list) { 2183 if (list == null) { 2184 throw new NullPointerException("list == null"); 2185 } 2186 if (list instanceof RandomAccess) { 2187 return new SynchronizedRandomAccessList<T>(list); 2188 } 2189 return new SynchronizedList<T>(list); 2190 } 2191 2192 /** 2193 * Returns a wrapper on the specified map which synchronizes all access to 2194 * the map. 2195 * 2196 * @param map 2197 * the map to wrap in a synchronized map. 2198 * @return a synchronized Map. 2199 */ 2200 public static <K, V> Map<K, V> synchronizedMap(Map<K, V> map) { 2201 if (map == null) { 2202 throw new NullPointerException("map == null"); 2203 } 2204 return new SynchronizedMap<K, V>(map); 2205 } 2206 2207 /** 2208 * Returns a wrapper on the specified set which synchronizes all access to 2209 * the set. 2210 * 2211 * @param set 2212 * the set to wrap in a synchronized set. 2213 * @return a synchronized set. 2214 */ 2215 public static <E> Set<E> synchronizedSet(Set<E> set) { 2216 if (set == null) { 2217 throw new NullPointerException("set == null"); 2218 } 2219 return new SynchronizedSet<E>(set); 2220 } 2221 2222 /** 2223 * Returns a wrapper on the specified sorted map which synchronizes all 2224 * access to the sorted map. 2225 * 2226 * @param map 2227 * the sorted map to wrap in a synchronized sorted map. 2228 * @return a synchronized sorted map. 2229 */ 2230 public static <K, V> SortedMap<K, V> synchronizedSortedMap( 2231 SortedMap<K, V> map) { 2232 if (map == null) { 2233 throw new NullPointerException("map == null"); 2234 } 2235 return new SynchronizedSortedMap<K, V>(map); 2236 } 2237 2238 /** 2239 * Returns a wrapper on the specified sorted set which synchronizes all 2240 * access to the sorted set. 2241 * 2242 * @param set 2243 * the sorted set to wrap in a synchronized sorted set. 2244 * @return a synchronized sorted set. 2245 */ 2246 public static <E> SortedSet<E> synchronizedSortedSet(SortedSet<E> set) { 2247 if (set == null) { 2248 throw new NullPointerException("set == null"); 2249 } 2250 return new SynchronizedSortedSet<E>(set); 2251 } 2252 2253 /** 2254 * Returns a wrapper on the specified collection which throws an 2255 * {@code UnsupportedOperationException} whenever an attempt is made to 2256 * modify the collection. 2257 * 2258 * @param collection 2259 * the collection to wrap in an unmodifiable collection. 2260 * @return an unmodifiable collection. 2261 */ 2262 @SuppressWarnings("unchecked") 2263 public static <E> Collection<E> unmodifiableCollection( 2264 Collection<? extends E> collection) { 2265 if (collection == null) { 2266 throw new NullPointerException("collection == null"); 2267 } 2268 return new UnmodifiableCollection<E>((Collection<E>) collection); 2269 } 2270 2271 /** 2272 * Returns a wrapper on the specified list which throws an 2273 * {@code UnsupportedOperationException} whenever an attempt is made to 2274 * modify the list. 2275 * 2276 * @param list 2277 * the list to wrap in an unmodifiable list. 2278 * @return an unmodifiable List. 2279 */ 2280 @SuppressWarnings("unchecked") 2281 public static <E> List<E> unmodifiableList(List<? extends E> list) { 2282 if (list == null) { 2283 throw new NullPointerException("list == null"); 2284 } 2285 if (list instanceof RandomAccess) { 2286 return new UnmodifiableRandomAccessList<E>((List<E>) list); 2287 } 2288 return new UnmodifiableList<E>((List<E>) list); 2289 } 2290 2291 /** 2292 * Returns a wrapper on the specified map which throws an 2293 * {@code UnsupportedOperationException} whenever an attempt is made to 2294 * modify the map. 2295 * 2296 * @param map 2297 * the map to wrap in an unmodifiable map. 2298 * @return a unmodifiable map. 2299 */ 2300 @SuppressWarnings("unchecked") 2301 public static <K, V> Map<K, V> unmodifiableMap( 2302 Map<? extends K, ? extends V> map) { 2303 if (map == null) { 2304 throw new NullPointerException("map == null"); 2305 } 2306 return new UnmodifiableMap<K, V>((Map<K, V>) map); 2307 } 2308 2309 /** 2310 * Returns a wrapper on the specified set which throws an 2311 * {@code UnsupportedOperationException} whenever an attempt is made to 2312 * modify the set. 2313 * 2314 * @param set 2315 * the set to wrap in an unmodifiable set. 2316 * @return a unmodifiable set 2317 */ 2318 @SuppressWarnings("unchecked") 2319 public static <E> Set<E> unmodifiableSet(Set<? extends E> set) { 2320 if (set == null) { 2321 throw new NullPointerException("set == null"); 2322 } 2323 return new UnmodifiableSet<E>((Set<E>) set); 2324 } 2325 2326 /** 2327 * Returns a wrapper on the specified sorted map which throws an 2328 * {@code UnsupportedOperationException} whenever an attempt is made to 2329 * modify the sorted map. 2330 * 2331 * @param map 2332 * the sorted map to wrap in an unmodifiable sorted map. 2333 * @return a unmodifiable sorted map 2334 */ 2335 @SuppressWarnings("unchecked") 2336 public static <K, V> SortedMap<K, V> unmodifiableSortedMap( 2337 SortedMap<K, ? extends V> map) { 2338 if (map == null) { 2339 throw new NullPointerException("map == null"); 2340 } 2341 return new UnmodifiableSortedMap<K, V>((SortedMap<K, V>) map); 2342 } 2343 2344 /** 2345 * Returns a wrapper on the specified sorted set which throws an 2346 * {@code UnsupportedOperationException} whenever an attempt is made to 2347 * modify the sorted set. 2348 * 2349 * @param set 2350 * the sorted set to wrap in an unmodifiable sorted set. 2351 * @return a unmodifiable sorted set. 2352 */ 2353 public static <E> SortedSet<E> unmodifiableSortedSet(SortedSet<E> set) { 2354 if (set == null) { 2355 throw new NullPointerException("set == null"); 2356 } 2357 return new UnmodifiableSortedSet<E>(set); 2358 } 2359 2360 /** 2361 * Returns the number of elements in the {@code Collection} that match the 2362 * {@code Object} passed. If the {@code Object} is {@code null}, then the 2363 * number of {@code null} elements is returned. 2364 * 2365 * @param c 2366 * the {@code Collection} to search. 2367 * @param o 2368 * the {@code Object} to search for. 2369 * @return the number of matching elements. 2370 * @throws NullPointerException 2371 * if the {@code Collection} parameter is {@code null}. 2372 * @since 1.5 2373 */ 2374 public static int frequency(Collection<?> c, Object o) { 2375 if (c == null) { 2376 throw new NullPointerException("c == null"); 2377 } 2378 if (c.isEmpty()) { 2379 return 0; 2380 } 2381 int result = 0; 2382 Iterator<?> itr = c.iterator(); 2383 while (itr.hasNext()) { 2384 Object e = itr.next(); 2385 if (o == null ? e == null : o.equals(e)) { 2386 result++; 2387 } 2388 } 2389 return result; 2390 } 2391 2392 /** 2393 * Returns a type-safe empty, immutable {@link List}. 2394 * 2395 * @return an empty {@link List}. 2396 * @since 1.5 2397 * @see #EMPTY_LIST 2398 */ 2399 @SuppressWarnings("unchecked") 2400 public static final <T> List<T> emptyList() { 2401 return EMPTY_LIST; 2402 } 2403 2404 /** 2405 * Returns a type-safe empty, immutable {@link Set}. 2406 * 2407 * @return an empty {@link Set}. 2408 * @since 1.5 2409 * @see #EMPTY_SET 2410 */ 2411 @SuppressWarnings("unchecked") 2412 public static final <T> Set<T> emptySet() { 2413 return EMPTY_SET; 2414 } 2415 2416 /** 2417 * Returns a type-safe empty, immutable {@link Map}. 2418 * 2419 * @return an empty {@link Map}. 2420 * @since 1.5 2421 * @see #EMPTY_MAP 2422 */ 2423 @SuppressWarnings("unchecked") 2424 public static final <K, V> Map<K, V> emptyMap() { 2425 return EMPTY_MAP; 2426 } 2427 2428 /** 2429 * Returns an enumeration containing no elements. 2430 * @since 1.7 2431 */ 2432 @SuppressWarnings("unchecked") 2433 public static <T> Enumeration<T> emptyEnumeration() { 2434 return (Enumeration<T>) EMPTY_ENUMERATION; 2435 } 2436 2437 /** 2438 * Returns an iterator containing no elements. 2439 * @since 1.7 2440 */ 2441 @SuppressWarnings("unchecked") 2442 public static <T> Iterator<T> emptyIterator() { 2443 return (Iterator<T>) EMPTY_ITERATOR; 2444 } 2445 2446 /** 2447 * Returns a list iterator containing no elements. 2448 * @since 1.7 2449 */ 2450 public static <T> ListIterator<T> emptyListIterator() { 2451 return Collections.<T>emptyList().listIterator(); 2452 } 2453 2454 /** 2455 * Returns a dynamically typesafe view of the specified collection. Trying 2456 * to insert an element of the wrong type into this collection throws a 2457 * {@code ClassCastException}. At creation time the types in {@code c} are 2458 * not checked for correct type. 2459 * 2460 * @param c 2461 * the collection to be wrapped in a typesafe collection. 2462 * @param type 2463 * the type of the elements permitted to insert. 2464 * @return a typesafe collection. 2465 */ 2466 public static <E> Collection<E> checkedCollection(Collection<E> c, 2467 Class<E> type) { 2468 return new CheckedCollection<E>(c, type); 2469 } 2470 2471 /** 2472 * Returns a dynamically typesafe view of the specified map. Trying to 2473 * insert an element of the wrong type into this map throws a 2474 * {@code ClassCastException}. At creation time the types in {@code m} are 2475 * not checked for correct type. 2476 * 2477 * @param m 2478 * the map to be wrapped in a typesafe map. 2479 * @param keyType 2480 * the type of the keys permitted to insert. 2481 * @param valueType 2482 * the type of the values permitted to insert. 2483 * @return a typesafe map. 2484 */ 2485 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, 2486 Class<V> valueType) { 2487 return new CheckedMap<K, V>(m, keyType, valueType); 2488 } 2489 2490 /** 2491 * Returns a dynamically typesafe view of the specified list. Trying to 2492 * insert an element of the wrong type into this list throws a 2493 * {@code ClassCastException}. At creation time the types in {@code list} 2494 * are not checked for correct type. 2495 * 2496 * @param list 2497 * the list to be wrapped in a typesafe list. 2498 * @param type 2499 * the type of the elements permitted to insert. 2500 * @return a typesafe list. 2501 */ 2502 public static <E> List<E> checkedList(List<E> list, Class<E> type) { 2503 if (list instanceof RandomAccess) { 2504 return new CheckedRandomAccessList<E>(list, type); 2505 } 2506 return new CheckedList<E>(list, type); 2507 } 2508 2509 /** 2510 * Returns a dynamically typesafe view of the specified set. Trying to 2511 * insert an element of the wrong type into this set throws a 2512 * {@code ClassCastException}. At creation time the types in {@code s} are 2513 * not checked for correct type. 2514 * 2515 * @param s 2516 * the set to be wrapped in a typesafe set. 2517 * @param type 2518 * the type of the elements permitted to insert. 2519 * @return a typesafe set. 2520 */ 2521 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) { 2522 return new CheckedSet<E>(s, type); 2523 } 2524 2525 /** 2526 * Returns a dynamically typesafe view of the specified sorted map. Trying 2527 * to insert an element of the wrong type into this sorted map throws a 2528 * {@code ClassCastException}. At creation time the types in {@code m} are 2529 * not checked for correct type. 2530 * 2531 * @param m 2532 * the sorted map to be wrapped in a typesafe sorted map. 2533 * @param keyType 2534 * the type of the keys permitted to insert. 2535 * @param valueType 2536 * the type of the values permitted to insert. 2537 * @return a typesafe sorted map. 2538 */ 2539 public static <K, V> SortedMap<K, V> checkedSortedMap(SortedMap<K, V> m, 2540 Class<K> keyType, Class<V> valueType) { 2541 return new CheckedSortedMap<K, V>(m, keyType, valueType); 2542 } 2543 2544 /** 2545 * Returns a dynamically typesafe view of the specified sorted set. Trying 2546 * to insert an element of the wrong type into this sorted set throws a 2547 * {@code ClassCastException}. At creation time the types in {@code s} are 2548 * not checked for correct type. 2549 * 2550 * @param s 2551 * the sorted set to be wrapped in a typesafe sorted set. 2552 * @param type 2553 * the type of the elements permitted to insert. 2554 * @return a typesafe sorted set. 2555 */ 2556 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, 2557 Class<E> type) { 2558 return new CheckedSortedSet<E>(s, type); 2559 } 2560 2561 /** 2562 * Adds all the specified elements to the specified collection. 2563 * 2564 * @param c 2565 * the collection the elements are to be inserted into. 2566 * @param a 2567 * the elements to insert. 2568 * @return true if the collection changed during insertion. 2569 * @throws UnsupportedOperationException 2570 * when the method is not supported. 2571 * @throws NullPointerException 2572 * when {@code c} or {@code a} is {@code null}, or {@code a} 2573 * contains one or more {@code null} elements and {@code c} 2574 * doesn't support {@code null} elements. 2575 * @throws IllegalArgumentException 2576 * if at least one of the elements can't be inserted into the 2577 * collection. 2578 */ 2579 @SafeVarargs 2580 public static <T> boolean addAll(Collection<? super T> c, T... a) { 2581 boolean modified = false; 2582 for (int i = 0; i < a.length; i++) { 2583 modified |= c.add(a[i]); 2584 } 2585 return modified; 2586 } 2587 2588 /** 2589 * Returns whether the specified collections have no elements in common. 2590 * 2591 * @param c1 2592 * the first collection. 2593 * @param c2 2594 * the second collection. 2595 * @return {@code true} if the collections have no elements in common, 2596 * {@code false} otherwise. 2597 * @throws NullPointerException 2598 * if one of the collections is {@code null}. 2599 */ 2600 public static boolean disjoint(Collection<?> c1, Collection<?> c2) { 2601 if ((c1 instanceof Set) && !(c2 instanceof Set) 2602 || (c2.size()) > c1.size()) { 2603 Collection<?> tmp = c1; 2604 c1 = c2; 2605 c2 = tmp; 2606 } 2607 Iterator<?> it = c1.iterator(); 2608 while (it.hasNext()) { 2609 if (c2.contains(it.next())) { 2610 return false; 2611 } 2612 } 2613 return true; 2614 } 2615 2616 /** 2617 * Checks if specified object is instance of specified class. Used for a 2618 * dynamically typesafe view of the collections. 2619 * 2620 * @param obj - 2621 * object is to be checked 2622 * @param type - 2623 * class of object that should be 2624 * @return specified object 2625 */ 2626 static <E> E checkType(E obj, Class<? extends E> type) { 2627 if (obj != null && !type.isInstance(obj)) { 2628 throw new ClassCastException("Attempt to insert element of type " + obj.getClass() + 2629 " into collection of type " + type); 2630 } 2631 return obj; 2632 } 2633 2634 /** 2635 * Returns a set backed by {@code map}. 2636 * 2637 * @throws IllegalArgumentException if the map is not empty 2638 * @since 1.6 2639 */ 2640 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 2641 if (map.isEmpty()) { 2642 return new SetFromMap<E>(map); 2643 } 2644 throw new IllegalArgumentException("map not empty"); 2645 } 2646 2647 /** 2648 * Returns a last-in, first-out queue as a view of {@code deque}. 2649 * 2650 * @since 1.6 2651 */ 2652 public static <T> Queue<T> asLifoQueue(Deque<T> deque) { 2653 return new AsLIFOQueue<T>(deque); 2654 } 2655 2656 private static class SetFromMap<E> extends AbstractSet<E> implements Serializable { 2657 private static final long serialVersionUID = 2454657854757543876L; 2658 2659 // Must be named as is, to pass serialization compatibility test. 2660 private final Map<E, Boolean> m; 2661 2662 private transient Set<E> backingSet; 2663 2664 SetFromMap(final Map<E, Boolean> map) { 2665 m = map; 2666 backingSet = map.keySet(); 2667 } 2668 2669 @Override public boolean equals(Object object) { 2670 return backingSet.equals(object); 2671 } 2672 2673 @Override public int hashCode() { 2674 return backingSet.hashCode(); 2675 } 2676 2677 @Override public boolean add(E object) { 2678 return m.put(object, Boolean.TRUE) == null; 2679 } 2680 2681 @Override public void clear() { 2682 m.clear(); 2683 } 2684 2685 @Override public String toString() { 2686 return backingSet.toString(); 2687 } 2688 2689 @Override public boolean contains(Object object) { 2690 return backingSet.contains(object); 2691 } 2692 2693 @Override public boolean containsAll(Collection<?> collection) { 2694 return backingSet.containsAll(collection); 2695 } 2696 2697 @Override public boolean isEmpty() { 2698 return m.isEmpty(); 2699 } 2700 2701 @Override public boolean remove(Object object) { 2702 return m.remove(object) != null; 2703 } 2704 2705 @Override public boolean retainAll(Collection<?> collection) { 2706 return backingSet.retainAll(collection); 2707 } 2708 2709 @Override public Object[] toArray() { 2710 return backingSet.toArray(); 2711 } 2712 2713 @Override 2714 public <T> T[] toArray(T[] contents) { 2715 return backingSet.toArray(contents); 2716 } 2717 2718 @Override public Iterator<E> iterator() { 2719 return backingSet.iterator(); 2720 } 2721 2722 @Override public int size() { 2723 return m.size(); 2724 } 2725 2726 @SuppressWarnings("unchecked") 2727 private void readObject(ObjectInputStream stream) 2728 throws IOException, ClassNotFoundException { 2729 stream.defaultReadObject(); 2730 backingSet = m.keySet(); 2731 } 2732 } 2733 2734 private static class AsLIFOQueue<E> extends AbstractQueue<E> implements Serializable { 2735 private static final long serialVersionUID = 1802017725587941708L; 2736 2737 // Must be named as is, to pass serialization compatibility test. 2738 private final Deque<E> q; 2739 2740 AsLIFOQueue(final Deque<E> deque) { 2741 this.q = deque; 2742 } 2743 2744 @Override public Iterator<E> iterator() { 2745 return q.iterator(); 2746 } 2747 2748 @Override public int size() { 2749 return q.size(); 2750 } 2751 2752 @Override public boolean offer(E o) { 2753 return q.offerFirst(o); 2754 } 2755 2756 @Override public E peek() { 2757 return q.peekFirst(); 2758 } 2759 2760 @Override public E poll() { 2761 return q.pollFirst(); 2762 } 2763 2764 @Override public boolean add(E o) { 2765 q.push(o); 2766 return true; 2767 } 2768 2769 @Override public void clear() { 2770 q.clear(); 2771 } 2772 2773 @Override public E element() { 2774 return q.getFirst(); 2775 } 2776 2777 @Override public E remove() { 2778 return q.pop(); 2779 } 2780 2781 @Override public boolean contains(Object object) { 2782 return q.contains(object); 2783 } 2784 2785 @Override public boolean containsAll(Collection<?> collection) { 2786 return q.containsAll(collection); 2787 } 2788 2789 @Override public boolean isEmpty() { 2790 return q.isEmpty(); 2791 } 2792 2793 @Override public boolean remove(Object object) { 2794 return q.remove(object); 2795 } 2796 2797 @Override public boolean removeAll(Collection<?> collection) { 2798 return q.removeAll(collection); 2799 } 2800 2801 @Override public boolean retainAll(Collection<?> collection) { 2802 return q.retainAll(collection); 2803 } 2804 2805 @Override public Object[] toArray() { 2806 return q.toArray(); 2807 } 2808 2809 @Override public <T> T[] toArray(T[] contents) { 2810 return q.toArray(contents); 2811 } 2812 2813 @Override public String toString() { 2814 return q.toString(); 2815 } 2816 } 2817 2818 /** 2819 * A dynamically typesafe view of a Collection. 2820 */ 2821 private static class CheckedCollection<E> implements Collection<E>, Serializable { 2822 2823 private static final long serialVersionUID = 1578914078182001775L; 2824 2825 final Collection<E> c; 2826 2827 final Class<E> type; 2828 2829 public CheckedCollection(Collection<E> c, Class<E> type) { 2830 if (c == null) { 2831 throw new NullPointerException("c == null"); 2832 } else if (type == null) { 2833 throw new NullPointerException("type == null"); 2834 } 2835 this.c = c; 2836 this.type = type; 2837 } 2838 2839 @Override public int size() { 2840 return c.size(); 2841 } 2842 2843 @Override public boolean isEmpty() { 2844 return c.isEmpty(); 2845 } 2846 2847 @Override public boolean contains(Object obj) { 2848 return c.contains(obj); 2849 } 2850 2851 @Override public Iterator<E> iterator() { 2852 Iterator<E> i = c.iterator(); 2853 if (i instanceof ListIterator) { 2854 i = new CheckedListIterator<E>((ListIterator<E>) i, type); 2855 } 2856 return i; 2857 } 2858 2859 @Override public Object[] toArray() { 2860 return c.toArray(); 2861 } 2862 2863 @Override public <T> T[] toArray(T[] arr) { 2864 return c.toArray(arr); 2865 } 2866 2867 @Override public boolean add(E obj) { 2868 return c.add(checkType(obj, type)); 2869 } 2870 2871 @Override public boolean remove(Object obj) { 2872 return c.remove(obj); 2873 } 2874 2875 @Override public boolean containsAll(Collection<?> c1) { 2876 return c.containsAll(c1); 2877 } 2878 2879 @SuppressWarnings("unchecked") 2880 @Override public boolean addAll(Collection<? extends E> c1) { 2881 Object[] array = c1.toArray(); 2882 for (Object o : array) { 2883 checkType(o, type); 2884 } 2885 return c.addAll((List<E>) Arrays.asList(array)); 2886 } 2887 2888 @Override public boolean removeAll(Collection<?> c1) { 2889 return c.removeAll(c1); 2890 } 2891 2892 @Override public boolean retainAll(Collection<?> c1) { 2893 return c.retainAll(c1); 2894 } 2895 2896 @Override public void clear() { 2897 c.clear(); 2898 } 2899 2900 @Override public String toString() { 2901 return c.toString(); 2902 } 2903 } 2904 2905 /** 2906 * Class represents a dynamically typesafe view of the specified 2907 * ListIterator. 2908 */ 2909 private static class CheckedListIterator<E> implements ListIterator<E> { 2910 2911 private final ListIterator<E> i; 2912 2913 private final Class<E> type; 2914 2915 /** 2916 * Constructs a dynamically typesafe view of the specified ListIterator. 2917 * 2918 * @param i - 2919 * the listIterator for which a dynamically typesafe view to 2920 * be constructed. 2921 */ 2922 public CheckedListIterator(ListIterator<E> i, Class<E> type) { 2923 this.i = i; 2924 this.type = type; 2925 } 2926 2927 @Override public boolean hasNext() { 2928 return i.hasNext(); 2929 } 2930 2931 @Override public E next() { 2932 return i.next(); 2933 } 2934 2935 @Override public void remove() { 2936 i.remove(); 2937 } 2938 2939 @Override public boolean hasPrevious() { 2940 return i.hasPrevious(); 2941 } 2942 2943 @Override public E previous() { 2944 return i.previous(); 2945 } 2946 2947 @Override public int nextIndex() { 2948 return i.nextIndex(); 2949 } 2950 2951 @Override public int previousIndex() { 2952 return i.previousIndex(); 2953 } 2954 2955 @Override public void set(E obj) { 2956 i.set(checkType(obj, type)); 2957 } 2958 2959 @Override public void add(E obj) { 2960 i.add(checkType(obj, type)); 2961 } 2962 } 2963 2964 /** 2965 * Class represents a dynamically typesafe view of a List. 2966 */ 2967 private static class CheckedList<E> extends CheckedCollection<E> implements List<E> { 2968 2969 private static final long serialVersionUID = 65247728283967356L; 2970 2971 final List<E> l; 2972 2973 public CheckedList(List<E> l, Class<E> type) { 2974 super(l, type); 2975 this.l = l; 2976 } 2977 2978 @SuppressWarnings("unchecked") 2979 @Override public boolean addAll(int index, Collection<? extends E> c1) { 2980 Object[] array = c1.toArray(); 2981 for (Object o : array) { 2982 checkType(o, type); 2983 } 2984 return l.addAll(index, (List<E>) Arrays.asList(array)); 2985 } 2986 2987 @Override public E get(int index) { 2988 return l.get(index); 2989 } 2990 2991 @Override public E set(int index, E obj) { 2992 return l.set(index, checkType(obj, type)); 2993 } 2994 2995 @Override public void add(int index, E obj) { 2996 l.add(index, checkType(obj, type)); 2997 } 2998 2999 @Override public E remove(int index) { 3000 return l.remove(index); 3001 } 3002 3003 @Override public int indexOf(Object obj) { 3004 return l.indexOf(obj); 3005 } 3006 3007 @Override public int lastIndexOf(Object obj) { 3008 return l.lastIndexOf(obj); 3009 } 3010 3011 @Override public ListIterator<E> listIterator() { 3012 return new CheckedListIterator<E>(l.listIterator(), type); 3013 } 3014 3015 @Override public ListIterator<E> listIterator(int index) { 3016 return new CheckedListIterator<E>(l.listIterator(index), type); 3017 } 3018 3019 @Override public List<E> subList(int fromIndex, int toIndex) { 3020 return checkedList(l.subList(fromIndex, toIndex), type); 3021 } 3022 3023 @Override public boolean equals(Object obj) { 3024 return l.equals(obj); 3025 } 3026 3027 @Override public int hashCode() { 3028 return l.hashCode(); 3029 } 3030 } 3031 3032 /** 3033 * A dynamically typesafe view of a RandomAccessList. 3034 */ 3035 private static class CheckedRandomAccessList<E> extends CheckedList<E> implements RandomAccess { 3036 3037 private static final long serialVersionUID = 1638200125423088369L; 3038 3039 public CheckedRandomAccessList(List<E> l, Class<E> type) { 3040 super(l, type); 3041 } 3042 } 3043 3044 /** 3045 * A dynamically typesafe view of a Set. 3046 */ 3047 private static class CheckedSet<E> extends CheckedCollection<E> implements Set<E> { 3048 3049 private static final long serialVersionUID = 4694047833775013803L; 3050 3051 public CheckedSet(Set<E> s, Class<E> type) { 3052 super(s, type); 3053 } 3054 3055 @Override public boolean equals(Object obj) { 3056 return c.equals(obj); 3057 } 3058 3059 @Override public int hashCode() { 3060 return c.hashCode(); 3061 } 3062 3063 } 3064 3065 /** 3066 * A dynamically typesafe view of a Map. 3067 */ 3068 private static class CheckedMap<K, V> implements Map<K, V>, Serializable { 3069 3070 private static final long serialVersionUID = 5742860141034234728L; 3071 3072 final Map<K, V> m; 3073 final Class<K> keyType; 3074 final Class<V> valueType; 3075 3076 private CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) { 3077 if (m == null) { 3078 throw new NullPointerException("m == null"); 3079 } else if (keyType == null) { 3080 throw new NullPointerException("keyType == null"); 3081 } else if (valueType == null) { 3082 throw new NullPointerException("valueType == null"); 3083 } 3084 this.m = m; 3085 this.keyType = keyType; 3086 this.valueType = valueType; 3087 } 3088 3089 @Override public int size() { 3090 return m.size(); 3091 } 3092 3093 @Override public boolean isEmpty() { 3094 return m.isEmpty(); 3095 } 3096 3097 @Override public boolean containsKey(Object key) { 3098 return m.containsKey(key); 3099 } 3100 3101 @Override public boolean containsValue(Object value) { 3102 return m.containsValue(value); 3103 } 3104 3105 @Override public V get(Object key) { 3106 return m.get(key); 3107 } 3108 3109 @Override public V put(K key, V value) { 3110 return m.put(checkType(key, keyType), checkType(value, valueType)); 3111 } 3112 3113 @Override public V remove(Object key) { 3114 return m.remove(key); 3115 } 3116 3117 @SuppressWarnings("unchecked") 3118 @Override public void putAll(Map<? extends K, ? extends V> map) { 3119 int size = map.size(); 3120 if (size == 0) { 3121 return; 3122 } 3123 Map.Entry<? extends K, ? extends V>[] entries = new Map.Entry[size]; 3124 Iterator<? extends Map.Entry<? extends K, ? extends V>> it = map 3125 .entrySet().iterator(); 3126 for (int i = 0; i < size; i++) { 3127 Map.Entry<? extends K, ? extends V> e = it.next(); 3128 checkType(e.getKey(), keyType); 3129 checkType(e.getValue(), valueType); 3130 entries[i] = e; 3131 } 3132 for (int i = 0; i < size; i++) { 3133 m.put(entries[i].getKey(), entries[i].getValue()); 3134 } 3135 } 3136 3137 @Override public void clear() { 3138 m.clear(); 3139 } 3140 3141 @Override public Set<K> keySet() { 3142 return m.keySet(); 3143 } 3144 3145 @Override public Collection<V> values() { 3146 return m.values(); 3147 } 3148 3149 @Override public Set<Map.Entry<K, V>> entrySet() { 3150 return new CheckedEntrySet<K, V>(m.entrySet(), valueType); 3151 } 3152 3153 @Override public boolean equals(Object obj) { 3154 return m.equals(obj); 3155 } 3156 3157 @Override public int hashCode() { 3158 return m.hashCode(); 3159 } 3160 3161 @Override public String toString() { 3162 return m.toString(); 3163 } 3164 3165 /** 3166 * A dynamically typesafe view of a Map.Entry. 3167 */ 3168 private static class CheckedEntry<K, V> implements Map.Entry<K, V> { 3169 final Map.Entry<K, V> e; 3170 final Class<V> valueType; 3171 3172 public CheckedEntry(Map.Entry<K, V> e, Class<V> valueType) { 3173 if (e == null) { 3174 throw new NullPointerException("e == null"); 3175 } 3176 this.e = e; 3177 this.valueType = valueType; 3178 } 3179 3180 @Override public K getKey() { 3181 return e.getKey(); 3182 } 3183 3184 @Override public V getValue() { 3185 return e.getValue(); 3186 } 3187 3188 @Override public V setValue(V obj) { 3189 return e.setValue(checkType(obj, valueType)); 3190 } 3191 3192 @Override public boolean equals(Object obj) { 3193 return e.equals(obj); 3194 } 3195 3196 @Override public int hashCode() { 3197 return e.hashCode(); 3198 } 3199 } 3200 3201 /** 3202 * A dynamically typesafe view of an entry set. 3203 */ 3204 private static class CheckedEntrySet<K, V> implements Set<Map.Entry<K, V>> { 3205 final Set<Map.Entry<K, V>> s; 3206 final Class<V> valueType; 3207 3208 public CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) { 3209 this.s = s; 3210 this.valueType = valueType; 3211 } 3212 3213 @Override public Iterator<Map.Entry<K, V>> iterator() { 3214 return new CheckedEntryIterator<K, V>(s.iterator(), valueType); 3215 } 3216 3217 @Override public Object[] toArray() { 3218 int thisSize = size(); 3219 Object[] array = new Object[thisSize]; 3220 Iterator<?> it = iterator(); 3221 for (int i = 0; i < thisSize; i++) { 3222 array[i] = it.next(); 3223 } 3224 return array; 3225 } 3226 3227 @SuppressWarnings("unchecked") 3228 @Override public <T> T[] toArray(T[] array) { 3229 int thisSize = size(); 3230 if (array.length < thisSize) { 3231 Class<?> ct = array.getClass().getComponentType(); 3232 array = (T[]) Array.newInstance(ct, thisSize); 3233 } 3234 Iterator<?> it = iterator(); 3235 for (int i = 0; i < thisSize; i++) { 3236 array[i] = (T) it.next(); 3237 } 3238 if (thisSize < array.length) { 3239 array[thisSize] = null; 3240 } 3241 return array; 3242 } 3243 3244 @Override public boolean retainAll(Collection<?> c) { 3245 return s.retainAll(c); 3246 } 3247 3248 @Override public boolean removeAll(Collection<?> c) { 3249 return s.removeAll(c); 3250 } 3251 3252 @Override public boolean containsAll(Collection<?> c) { 3253 return s.containsAll(c); 3254 } 3255 3256 @Override public boolean addAll(Collection<? extends Map.Entry<K, V>> c) { 3257 throw new UnsupportedOperationException(); 3258 } 3259 3260 @Override public boolean remove(Object o) { 3261 return s.remove(o); 3262 } 3263 3264 @Override public boolean contains(Object o) { 3265 return s.contains(o); 3266 } 3267 3268 @Override public boolean add(Map.Entry<K, V> o) { 3269 throw new UnsupportedOperationException(); 3270 } 3271 3272 @Override public boolean isEmpty() { 3273 return s.isEmpty(); 3274 } 3275 3276 @Override public void clear() { 3277 s.clear(); 3278 } 3279 3280 @Override public int size() { 3281 return s.size(); 3282 } 3283 3284 @Override public int hashCode() { 3285 return s.hashCode(); 3286 } 3287 3288 @Override public boolean equals(Object object) { 3289 return s.equals(object); 3290 } 3291 3292 /** 3293 * A dynamically typesafe view of an entry iterator. 3294 */ 3295 private static class CheckedEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> { 3296 Iterator<Map.Entry<K, V>> i; 3297 Class<V> valueType; 3298 3299 public CheckedEntryIterator(Iterator<Map.Entry<K, V>> i, 3300 Class<V> valueType) { 3301 this.i = i; 3302 this.valueType = valueType; 3303 } 3304 3305 @Override public boolean hasNext() { 3306 return i.hasNext(); 3307 } 3308 3309 @Override public void remove() { 3310 i.remove(); 3311 } 3312 3313 @Override public Map.Entry<K, V> next() { 3314 return new CheckedEntry<K, V>(i.next(), valueType); 3315 } 3316 } 3317 } 3318 } 3319 3320 /** 3321 * A dynamically typesafe view of a SortedSet. 3322 */ 3323 private static class CheckedSortedSet<E> extends CheckedSet<E> implements SortedSet<E> { 3324 private static final long serialVersionUID = 1599911165492914959L; 3325 private final SortedSet<E> ss; 3326 3327 public CheckedSortedSet(SortedSet<E> s, Class<E> type) { 3328 super(s, type); 3329 this.ss = s; 3330 } 3331 3332 @Override public Comparator<? super E> comparator() { 3333 return ss.comparator(); 3334 } 3335 3336 @Override public SortedSet<E> subSet(E fromElement, E toElement) { 3337 return new CheckedSortedSet<E>(ss.subSet(fromElement, toElement), 3338 type); 3339 } 3340 3341 @Override public SortedSet<E> headSet(E toElement) { 3342 return new CheckedSortedSet<E>(ss.headSet(toElement), type); 3343 } 3344 3345 @Override public SortedSet<E> tailSet(E fromElement) { 3346 return new CheckedSortedSet<E>(ss.tailSet(fromElement), type); 3347 } 3348 3349 @Override public E first() { 3350 return ss.first(); 3351 } 3352 3353 @Override public E last() { 3354 return ss.last(); 3355 } 3356 } 3357 3358 /** 3359 * A dynamically typesafe view of a SortedMap. 3360 */ 3361 private static class CheckedSortedMap<K, V> extends CheckedMap<K, V> 3362 implements SortedMap<K, V> { 3363 private static final long serialVersionUID = 1599671320688067438L; 3364 final SortedMap<K, V> sm; 3365 3366 CheckedSortedMap(SortedMap<K, V> m, Class<K> keyType, Class<V> valueType) { 3367 super(m, keyType, valueType); 3368 this.sm = m; 3369 } 3370 3371 @Override public Comparator<? super K> comparator() { 3372 return sm.comparator(); 3373 } 3374 3375 @Override public SortedMap<K, V> subMap(K fromKey, K toKey) { 3376 return new CheckedSortedMap<K, V>(sm.subMap(fromKey, toKey), keyType, valueType); 3377 } 3378 3379 @Override public SortedMap<K, V> headMap(K toKey) { 3380 return new CheckedSortedMap<K, V>(sm.headMap(toKey), keyType, valueType); 3381 } 3382 3383 @Override public SortedMap<K, V> tailMap(K fromKey) { 3384 return new CheckedSortedMap<K, V>(sm.tailMap(fromKey), keyType, valueType); 3385 } 3386 3387 @Override public K firstKey() { 3388 return sm.firstKey(); 3389 } 3390 3391 @Override public K lastKey() { 3392 return sm.lastKey(); 3393 } 3394 } 3395 3396 /** 3397 * Computes a hash code and applies a supplemental hash function to defend 3398 * against poor quality hash functions. This is critical because HashMap 3399 * uses power-of-two length hash tables, that otherwise encounter collisions 3400 * for hash codes that do not differ in lower or upper bits. 3401 * Routine taken from java.util.concurrent.ConcurrentHashMap.hash(int). 3402 * @hide 3403 */ 3404 public static int secondaryHash(Object key) { 3405 return secondaryHash(key.hashCode()); 3406 } 3407 3408 /** 3409 * Computes an identity hash code and applies a supplemental hash function to defend 3410 * against poor quality hash functions. This is critical because identity hash codes 3411 * are currently implemented as object addresses, which will have been aligned by the 3412 * underlying memory allocator causing all hash codes to have the same bottom bits. 3413 * @hide 3414 */ 3415 public static int secondaryIdentityHash(Object key) { 3416 return secondaryHash(System.identityHashCode(key)); 3417 } 3418 3419 private static int secondaryHash(int h) { 3420 // Spread bits to regularize both segment and index locations, 3421 // using variant of single-word Wang/Jenkins hash. 3422 h += (h << 15) ^ 0xffffcd7d; 3423 h ^= (h >>> 10); 3424 h += (h << 3); 3425 h ^= (h >>> 6); 3426 h += (h << 2) + (h << 14); 3427 return h ^ (h >>> 16); 3428 } 3429 3430 /** 3431 * Returns the smallest power of two >= its argument, with several caveats: 3432 * If the argument is negative but not Integer.MIN_VALUE, the method returns 3433 * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method 3434 * returns Integer.MIN_VALUE. If the argument is zero, the method returns 3435 * zero. 3436 * @hide 3437 */ 3438 public static int roundUpToPowerOfTwo(int i) { 3439 i--; // If input is a power of two, shift its high-order bit right. 3440 3441 // "Smear" the high-order bit all the way to the right. 3442 i |= i >>> 1; 3443 i |= i >>> 2; 3444 i |= i >>> 4; 3445 i |= i >>> 8; 3446 i |= i >>> 16; 3447 3448 return i + 1; 3449 } 3450 } 3451
