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 CopiesList(int length, E object)64 CopiesList(int length, E object) { 65 if (length < 0) { 66 throw new IllegalArgumentException(); 67 } 68 n = length; 69 element = object; 70 } 71 contains(Object object)72 @Override public boolean contains(Object object) { 73 return element == null ? object == null : element.equals(object); 74 } 75 size()76 @Override public int size() { 77 return n; 78 } 79 get(int location)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 contains(Object object)93 @Override public boolean contains(Object object) { 94 return false; 95 } 96 size()97 @Override public int size() { 98 return 0; 99 } 100 get(int location)101 @Override public Object get(int location) { 102 throw new IndexOutOfBoundsException(); 103 } 104 readResolve()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 contains(Object object)114 @Override public boolean contains(Object object) { 115 return false; 116 } 117 size()118 @Override public int size() { 119 return 0; 120 } 121 iterator()122 @Override public Iterator iterator() { 123 return EMPTY_ITERATOR; 124 } 125 readResolve()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 containsKey(Object key)135 @Override public boolean containsKey(Object key) { 136 return false; 137 } 138 containsValue(Object value)139 @Override public boolean containsValue(Object value) { 140 return false; 141 } 142 entrySet()143 @Override public Set entrySet() { 144 return EMPTY_SET; 145 } 146 get(Object key)147 @Override public Object get(Object key) { 148 return null; 149 } 150 keySet()151 @Override public Set keySet() { 152 return EMPTY_SET; 153 } 154 values()155 @Override public Collection values() { 156 return EMPTY_LIST; 157 } 158 readResolve()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") compare(T o1, T o2)191 @Override public int compare(T o1, T o2) { 192 Comparable<T> c2 = (Comparable<T>) o2; 193 return c2.compareTo(o1); 194 } 195 readResolve()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 ReverseComparator2(Comparator<T> comparator)205 ReverseComparator2(Comparator<T> comparator) { 206 this.cmp = comparator; 207 } 208 compare(T o1, T o2)209 @Override public int compare(T o1, T o2) { 210 return cmp.compare(o2, o1); 211 } 212 equals(Object o)213 @Override public boolean equals(Object o) { 214 return o instanceof ReverseComparator2 215 && ((ReverseComparator2) o).cmp.equals(cmp); 216 } 217 hashCode()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 SingletonSet(E object)227 SingletonSet(E object) { 228 element = object; 229 } 230 contains(Object object)231 @Override public boolean contains(Object object) { 232 return element == null ? object == null : element.equals(object); 233 } 234 size()235 @Override public int size() { 236 return 1; 237 } 238 iterator()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 SingletonList(E object)267 SingletonList(E object) { 268 element = object; 269 } 270 contains(Object object)271 @Override public boolean contains(Object object) { 272 return element == null ? object == null : element.equals(object); 273 } 274 get(int location)275 @Override public E get(int location) { 276 if (location == 0) { 277 return element; 278 } 279 throw new IndexOutOfBoundsException(); 280 } 281 size()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 SingletonMap(K key, V value)294 SingletonMap(K key, V value) { 295 k = key; 296 v = value; 297 } 298 containsKey(Object key)299 @Override public boolean containsKey(Object key) { 300 return k == null ? key == null : k.equals(key); 301 } 302 containsValue(Object value)303 @Override public boolean containsValue(Object value) { 304 return v == null ? value == null : v.equals(value); 305 } 306 get(Object key)307 @Override public V get(Object key) { 308 if (containsKey(key)) { 309 return v; 310 } 311 return null; 312 } 313 size()314 @Override public int size() { 315 return 1; 316 } 317 entrySet()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 = length; --i >= 0;) { 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(); 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 specified list in ascending natural order. The algorithm is 1856 * stable which means equal elements don't get reordered. 1857 * 1858 * @param list 1859 * the list to be sorted. 1860 * @throws ClassCastException 1861 * when an element in the List does not implement Comparable or 1862 * elements cannot be compared to each other. 1863 */ 1864 @SuppressWarnings("unchecked") 1865 public static <T extends Comparable<? super T>> void sort(List<T> list) { 1866 Object[] array = list.toArray(); 1867 Arrays.sort(array); 1868 int i = 0; 1869 ListIterator<T> it = list.listIterator(); 1870 while (it.hasNext()) { 1871 it.next(); 1872 it.set((T) array[i++]); 1873 } 1874 } 1875 1876 /** 1877 * Sorts the specified list using the specified comparator. The algorithm is 1878 * stable which means equal elements don't get reordered. 1879 * 1880 * @param list 1881 * the list to be sorted. 1882 * @param comparator 1883 * the comparator. 1884 * @throws ClassCastException 1885 * when elements in the list cannot be compared to each other 1886 * using the comparator. 1887 */ 1888 @SuppressWarnings("unchecked") 1889 public static <T> void sort(List<T> list, Comparator<? super T> comparator) { 1890 T[] array = list.toArray((T[]) new Object[list.size()]); 1891 Arrays.sort(array, comparator); 1892 int i = 0; 1893 ListIterator<T> it = list.listIterator(); 1894 while (it.hasNext()) { 1895 it.next(); 1896 it.set(array[i++]); 1897 } 1898 } 1899 1900 /** 1901 * Swaps the elements of list {@code list} at indices {@code index1} and 1902 * {@code index2}. 1903 * 1904 * @param list 1905 * the list to manipulate. 1906 * @param index1 1907 * position of the first element to swap with the element in 1908 * index2. 1909 * @param index2 1910 * position of the other element. 1911 * 1912 * @throws IndexOutOfBoundsException 1913 * if index1 or index2 is out of range of this list. 1914 * @since 1.4 1915 */ 1916 @SuppressWarnings("unchecked") 1917 public static void swap(List<?> list, int index1, int index2) { 1918 if (list == null) { 1919 throw new NullPointerException(); 1920 } 1921 final int size = list.size(); 1922 if (index1 < 0 || index1 >= size || index2 < 0 || index2 >= size) { 1923 throw new IndexOutOfBoundsException(); 1924 } 1925 if (index1 == index2) { 1926 return; 1927 } 1928 List<Object> rawList = (List<Object>) list; 1929 rawList.set(index2, rawList.set(index1, rawList.get(index2))); 1930 } 1931 1932 /** 1933 * Replaces all occurrences of Object {@code obj} in {@code list} with 1934 * {@code newObj}. If the {@code obj} is {@code null}, then all 1935 * occurrences of {@code null} are replaced with {@code newObj}. 1936 * 1937 * @param list 1938 * the list to modify. 1939 * @param obj 1940 * the object to find and replace occurrences of. 1941 * @param obj2 1942 * the object to replace all occurrences of {@code obj} in 1943 * {@code list}. 1944 * @return true, if at least one occurrence of {@code obj} has been found in 1945 * {@code list}. 1946 * @throws UnsupportedOperationException 1947 * if the list does not support setting elements. 1948 */ 1949 public static <T> boolean replaceAll(List<T> list, T obj, T obj2) { 1950 int index; 1951 boolean found = false; 1952 1953 while ((index = list.indexOf(obj)) > -1) { 1954 found = true; 1955 list.set(index, obj2); 1956 } 1957 return found; 1958 } 1959 1960 /** 1961 * Rotates the elements in {@code list} by the distance {@code dist} 1962 * <p> 1963 * e.g. for a given list with elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], 1964 * calling rotate(list, 3) or rotate(list, -7) would modify the list to look 1965 * like this: [8, 9, 0, 1, 2, 3, 4, 5, 6, 7] 1966 * 1967 * @param lst 1968 * the list whose elements are to be rotated. 1969 * @param dist 1970 * is the distance the list is rotated. This can be any valid 1971 * integer. Negative values rotate the list backwards. 1972 */ 1973 @SuppressWarnings("unchecked") 1974 public static void rotate(List<?> lst, int dist) { 1975 List<Object> list = (List<Object>) lst; 1976 int size = list.size(); 1977 1978 // Can't sensibly rotate an empty collection 1979 if (size == 0) { 1980 return; 1981 } 1982 1983 // normalize the distance 1984 int normdist; 1985 if (dist > 0) { 1986 normdist = dist % size; 1987 } else { 1988 normdist = size - ((dist % size) * (-1)); 1989 } 1990 1991 if (normdist == 0 || normdist == size) { 1992 return; 1993 } 1994 1995 if (list instanceof RandomAccess) { 1996 // make sure each element gets juggled 1997 // with the element in the position it is supposed to go to 1998 Object temp = list.get(0); 1999 int index = 0, beginIndex = 0; 2000 for (int i = 0; i < size; i++) { 2001 index = (index + normdist) % size; 2002 temp = list.set(index, temp); 2003 if (index == beginIndex) { 2004 index = ++beginIndex; 2005 temp = list.get(beginIndex); 2006 } 2007 } 2008 } else { 2009 int divideIndex = (size - normdist) % size; 2010 List<Object> sublist1 = list.subList(0, divideIndex); 2011 List<Object> sublist2 = list.subList(divideIndex, size); 2012 reverse(sublist1); 2013 reverse(sublist2); 2014 reverse(list); 2015 } 2016 } 2017 2018 /** 2019 * Searches the {@code list} for {@code sublist} and returns the beginning 2020 * index of the first occurrence. 2021 * <p> 2022 * -1 is returned if the {@code sublist} does not exist in {@code list}. 2023 * 2024 * @param list 2025 * the List to search {@code sublist} in. 2026 * @param sublist 2027 * the List to search in {@code list}. 2028 * @return the beginning index of the first occurrence of {@code sublist} in 2029 * {@code list}, or -1. 2030 */ 2031 public static int indexOfSubList(List<?> list, List<?> sublist) { 2032 int size = list.size(); 2033 int sublistSize = sublist.size(); 2034 2035 if (sublistSize > size) { 2036 return -1; 2037 } 2038 2039 if (sublistSize == 0) { 2040 return 0; 2041 } 2042 2043 // find the first element of sublist in the list to get a head start 2044 Object firstObj = sublist.get(0); 2045 int index = list.indexOf(firstObj); 2046 if (index == -1) { 2047 return -1; 2048 } 2049 2050 while (index < size && (size - index >= sublistSize)) { 2051 ListIterator<?> listIt = list.listIterator(index); 2052 2053 if ((firstObj == null) ? listIt.next() == null : firstObj 2054 .equals(listIt.next())) { 2055 2056 // iterate through the elements in sublist to see 2057 // if they are included in the same order in the list 2058 ListIterator<?> sublistIt = sublist.listIterator(1); 2059 boolean difFound = false; 2060 while (sublistIt.hasNext()) { 2061 Object element = sublistIt.next(); 2062 if (!listIt.hasNext()) { 2063 return -1; 2064 } 2065 if ((element == null) ? listIt.next() != null : !element 2066 .equals(listIt.next())) { 2067 difFound = true; 2068 break; 2069 } 2070 } 2071 // All elements of sublist are found in main list 2072 // starting from index. 2073 if (!difFound) { 2074 return index; 2075 } 2076 } 2077 // This was not the sequence we were looking for, 2078 // continue search for the firstObj in main list 2079 // at the position after index. 2080 index++; 2081 } 2082 return -1; 2083 } 2084 2085 /** 2086 * Searches the {@code list} for {@code sublist} and returns the beginning 2087 * index of the last occurrence. 2088 * <p> 2089 * -1 is returned if the {@code sublist} does not exist in {@code list}. 2090 * 2091 * @param list 2092 * the list to search {@code sublist} in. 2093 * @param sublist 2094 * the list to search in {@code list}. 2095 * @return the beginning index of the last occurrence of {@code sublist} in 2096 * {@code list}, or -1. 2097 */ 2098 public static int lastIndexOfSubList(List<?> list, List<?> sublist) { 2099 int sublistSize = sublist.size(); 2100 int size = list.size(); 2101 2102 if (sublistSize > size) { 2103 return -1; 2104 } 2105 2106 if (sublistSize == 0) { 2107 return size; 2108 } 2109 2110 // find the last element of sublist in the list to get a head start 2111 Object lastObj = sublist.get(sublistSize - 1); 2112 int index = list.lastIndexOf(lastObj); 2113 2114 while ((index > -1) && (index + 1 >= sublistSize)) { 2115 ListIterator<?> listIt = list.listIterator(index + 1); 2116 2117 if ((lastObj == null) ? listIt.previous() == null : lastObj 2118 .equals(listIt.previous())) { 2119 // iterate through the elements in sublist to see 2120 // if they are included in the same order in the list 2121 ListIterator<?> sublistIt = sublist 2122 .listIterator(sublistSize - 1); 2123 boolean difFound = false; 2124 while (sublistIt.hasPrevious()) { 2125 Object element = sublistIt.previous(); 2126 if (!listIt.hasPrevious()) { 2127 return -1; 2128 } 2129 if ((element == null) ? listIt.previous() != null 2130 : !element.equals(listIt.previous())) { 2131 difFound = true; 2132 break; 2133 } 2134 } 2135 // All elements of sublist are found in main list 2136 // starting from listIt.nextIndex(). 2137 if (!difFound) { 2138 return listIt.nextIndex(); 2139 } 2140 } 2141 // This was not the sequence we were looking for, 2142 // continue search for the lastObj in main list 2143 // at the position before index. 2144 index--; 2145 } 2146 return -1; 2147 } 2148 2149 /** 2150 * Returns an {@code ArrayList} with all the elements in the {@code 2151 * enumeration}. The elements in the returned {@code ArrayList} are in the 2152 * same order as in the {@code enumeration}. 2153 * 2154 * @param enumeration 2155 * the source {@link Enumeration}. 2156 * @return an {@code ArrayList} from {@code enumeration}. 2157 */ 2158 public static <T> ArrayList<T> list(Enumeration<T> enumeration) { 2159 ArrayList<T> list = new ArrayList<T>(); 2160 while (enumeration.hasMoreElements()) { 2161 list.add(enumeration.nextElement()); 2162 } 2163 return list; 2164 } 2165 2166 /** 2167 * Returns a wrapper on the specified collection which synchronizes all 2168 * access to the collection. 2169 * 2170 * @param collection 2171 * the Collection to wrap in a synchronized collection. 2172 * @return a synchronized Collection. 2173 */ 2174 public static <T> Collection<T> synchronizedCollection( 2175 Collection<T> collection) { 2176 if (collection == null) { 2177 throw new NullPointerException(); 2178 } 2179 return new SynchronizedCollection<T>(collection); 2180 } 2181 2182 /** 2183 * Returns a wrapper on the specified List which synchronizes all access to 2184 * the List. 2185 * 2186 * @param list 2187 * the List to wrap in a synchronized list. 2188 * @return a synchronized List. 2189 */ 2190 public static <T> List<T> synchronizedList(List<T> list) { 2191 if (list == null) { 2192 throw new NullPointerException(); 2193 } 2194 if (list instanceof RandomAccess) { 2195 return new SynchronizedRandomAccessList<T>(list); 2196 } 2197 return new SynchronizedList<T>(list); 2198 } 2199 2200 /** 2201 * Returns a wrapper on the specified map which synchronizes all access to 2202 * the map. 2203 * 2204 * @param map 2205 * the map to wrap in a synchronized map. 2206 * @return a synchronized Map. 2207 */ 2208 public static <K, V> Map<K, V> synchronizedMap(Map<K, V> map) { 2209 if (map == null) { 2210 throw new NullPointerException(); 2211 } 2212 return new SynchronizedMap<K, V>(map); 2213 } 2214 2215 /** 2216 * Returns a wrapper on the specified set which synchronizes all access to 2217 * the set. 2218 * 2219 * @param set 2220 * the set to wrap in a synchronized set. 2221 * @return a synchronized set. 2222 */ 2223 public static <E> Set<E> synchronizedSet(Set<E> set) { 2224 if (set == null) { 2225 throw new NullPointerException(); 2226 } 2227 return new SynchronizedSet<E>(set); 2228 } 2229 2230 /** 2231 * Returns a wrapper on the specified sorted map which synchronizes all 2232 * access to the sorted map. 2233 * 2234 * @param map 2235 * the sorted map to wrap in a synchronized sorted map. 2236 * @return a synchronized sorted map. 2237 */ 2238 public static <K, V> SortedMap<K, V> synchronizedSortedMap( 2239 SortedMap<K, V> map) { 2240 if (map == null) { 2241 throw new NullPointerException(); 2242 } 2243 return new SynchronizedSortedMap<K, V>(map); 2244 } 2245 2246 /** 2247 * Returns a wrapper on the specified sorted set which synchronizes all 2248 * access to the sorted set. 2249 * 2250 * @param set 2251 * the sorted set to wrap in a synchronized sorted set. 2252 * @return a synchronized sorted set. 2253 */ 2254 public static <E> SortedSet<E> synchronizedSortedSet(SortedSet<E> set) { 2255 if (set == null) { 2256 throw new NullPointerException(); 2257 } 2258 return new SynchronizedSortedSet<E>(set); 2259 } 2260 2261 /** 2262 * Returns a wrapper on the specified collection which throws an 2263 * {@code UnsupportedOperationException} whenever an attempt is made to 2264 * modify the collection. 2265 * 2266 * @param collection 2267 * the collection to wrap in an unmodifiable collection. 2268 * @return an unmodifiable collection. 2269 */ 2270 @SuppressWarnings("unchecked") 2271 public static <E> Collection<E> unmodifiableCollection( 2272 Collection<? extends E> collection) { 2273 if (collection == null) { 2274 throw new NullPointerException(); 2275 } 2276 return new UnmodifiableCollection<E>((Collection<E>) collection); 2277 } 2278 2279 /** 2280 * Returns a wrapper on the specified list which throws an 2281 * {@code UnsupportedOperationException} whenever an attempt is made to 2282 * modify the list. 2283 * 2284 * @param list 2285 * the list to wrap in an unmodifiable list. 2286 * @return an unmodifiable List. 2287 */ 2288 @SuppressWarnings("unchecked") 2289 public static <E> List<E> unmodifiableList(List<? extends E> list) { 2290 if (list == null) { 2291 throw new NullPointerException(); 2292 } 2293 if (list instanceof RandomAccess) { 2294 return new UnmodifiableRandomAccessList<E>((List<E>) list); 2295 } 2296 return new UnmodifiableList<E>((List<E>) list); 2297 } 2298 2299 /** 2300 * Returns a wrapper on the specified map which throws an 2301 * {@code UnsupportedOperationException} whenever an attempt is made to 2302 * modify the map. 2303 * 2304 * @param map 2305 * the map to wrap in an unmodifiable map. 2306 * @return a unmodifiable map. 2307 */ 2308 @SuppressWarnings("unchecked") 2309 public static <K, V> Map<K, V> unmodifiableMap( 2310 Map<? extends K, ? extends V> map) { 2311 if (map == null) { 2312 throw new NullPointerException(); 2313 } 2314 return new UnmodifiableMap<K, V>((Map<K, V>) map); 2315 } 2316 2317 /** 2318 * Returns a wrapper on the specified set which throws an 2319 * {@code UnsupportedOperationException} whenever an attempt is made to 2320 * modify the set. 2321 * 2322 * @param set 2323 * the set to wrap in an unmodifiable set. 2324 * @return a unmodifiable set 2325 */ 2326 @SuppressWarnings("unchecked") 2327 public static <E> Set<E> unmodifiableSet(Set<? extends E> set) { 2328 if (set == null) { 2329 throw new NullPointerException(); 2330 } 2331 return new UnmodifiableSet<E>((Set<E>) set); 2332 } 2333 2334 /** 2335 * Returns a wrapper on the specified sorted map which throws an 2336 * {@code UnsupportedOperationException} whenever an attempt is made to 2337 * modify the sorted map. 2338 * 2339 * @param map 2340 * the sorted map to wrap in an unmodifiable sorted map. 2341 * @return a unmodifiable sorted map 2342 */ 2343 @SuppressWarnings("unchecked") 2344 public static <K, V> SortedMap<K, V> unmodifiableSortedMap( 2345 SortedMap<K, ? extends V> map) { 2346 if (map == null) { 2347 throw new NullPointerException(); 2348 } 2349 return new UnmodifiableSortedMap<K, V>((SortedMap<K, V>) map); 2350 } 2351 2352 /** 2353 * Returns a wrapper on the specified sorted set which throws an 2354 * {@code UnsupportedOperationException} whenever an attempt is made to 2355 * modify the sorted set. 2356 * 2357 * @param set 2358 * the sorted set to wrap in an unmodifiable sorted set. 2359 * @return a unmodifiable sorted set. 2360 */ 2361 public static <E> SortedSet<E> unmodifiableSortedSet(SortedSet<E> set) { 2362 if (set == null) { 2363 throw new NullPointerException(); 2364 } 2365 return new UnmodifiableSortedSet<E>(set); 2366 } 2367 2368 /** 2369 * Returns the number of elements in the {@code Collection} that match the 2370 * {@code Object} passed. If the {@code Object} is {@code null}, then the 2371 * number of {@code null} elements is returned. 2372 * 2373 * @param c 2374 * the {@code Collection} to search. 2375 * @param o 2376 * the {@code Object} to search for. 2377 * @return the number of matching elements. 2378 * @throws NullPointerException 2379 * if the {@code Collection} parameter is {@code null}. 2380 * @since 1.5 2381 */ 2382 public static int frequency(Collection<?> c, Object o) { 2383 if (c == null) { 2384 throw new NullPointerException(); 2385 } 2386 if (c.isEmpty()) { 2387 return 0; 2388 } 2389 int result = 0; 2390 Iterator<?> itr = c.iterator(); 2391 while (itr.hasNext()) { 2392 Object e = itr.next(); 2393 if (o == null ? e == null : o.equals(e)) { 2394 result++; 2395 } 2396 } 2397 return result; 2398 } 2399 2400 /** 2401 * Returns a type-safe empty, immutable {@link List}. 2402 * 2403 * @return an empty {@link List}. 2404 * @since 1.5 2405 * @see #EMPTY_LIST 2406 */ 2407 @SuppressWarnings("unchecked") 2408 public static final <T> List<T> emptyList() { 2409 return EMPTY_LIST; 2410 } 2411 2412 /** 2413 * Returns a type-safe empty, immutable {@link Set}. 2414 * 2415 * @return an empty {@link Set}. 2416 * @since 1.5 2417 * @see #EMPTY_SET 2418 */ 2419 @SuppressWarnings("unchecked") 2420 public static final <T> Set<T> emptySet() { 2421 return EMPTY_SET; 2422 } 2423 2424 /** 2425 * Returns a type-safe empty, immutable {@link Map}. 2426 * 2427 * @return an empty {@link Map}. 2428 * @since 1.5 2429 * @see #EMPTY_MAP 2430 */ 2431 @SuppressWarnings("unchecked") 2432 public static final <K, V> Map<K, V> emptyMap() { 2433 return EMPTY_MAP; 2434 } 2435 2436 /** 2437 * Returns an enumeration containing no elements. 2438 * @hide 1.7 2439 */ 2440 @SuppressWarnings("unchecked") 2441 public static <T> Enumeration<T> emptyEnumeration() { 2442 return (Enumeration<T>) EMPTY_ENUMERATION; 2443 } 2444 2445 /** 2446 * Returns an iterator containing no elements. 2447 * @hide 1.7 2448 */ 2449 @SuppressWarnings("unchecked") 2450 public static <T> Iterator<T> emptyIterator() { 2451 return (Iterator<T>) EMPTY_ITERATOR; 2452 } 2453 2454 /** 2455 * Returns a list iterator containing no elements. 2456 * @hide 1.7 2457 */ 2458 public static <T> ListIterator<T> emptyListIterator() { 2459 return Collections.<T>emptyList().listIterator(); 2460 } 2461 2462 /** 2463 * Returns a dynamically typesafe view of the specified collection. Trying 2464 * to insert an element of the wrong type into this collection throws a 2465 * {@code ClassCastException}. At creation time the types in {@code c} are 2466 * not checked for correct type. 2467 * 2468 * @param c 2469 * the collection to be wrapped in a typesafe collection. 2470 * @param type 2471 * the type of the elements permitted to insert. 2472 * @return a typesafe collection. 2473 */ 2474 public static <E> Collection<E> checkedCollection(Collection<E> c, 2475 Class<E> type) { 2476 return new CheckedCollection<E>(c, type); 2477 } 2478 2479 /** 2480 * Returns a dynamically typesafe view of the specified map. Trying to 2481 * insert an element of the wrong type into this map throws a 2482 * {@code ClassCastException}. At creation time the types in {@code m} are 2483 * not checked for correct type. 2484 * 2485 * @param m 2486 * the map to be wrapped in a typesafe map. 2487 * @param keyType 2488 * the type of the keys permitted to insert. 2489 * @param valueType 2490 * the type of the values permitted to insert. 2491 * @return a typesafe map. 2492 */ 2493 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, 2494 Class<V> valueType) { 2495 return new CheckedMap<K, V>(m, keyType, valueType); 2496 } 2497 2498 /** 2499 * Returns a dynamically typesafe view of the specified list. Trying to 2500 * insert an element of the wrong type into this list throws a 2501 * {@code ClassCastException}. At creation time the types in {@code list} 2502 * are not checked for correct type. 2503 * 2504 * @param list 2505 * the list to be wrapped in a typesafe list. 2506 * @param type 2507 * the type of the elements permitted to insert. 2508 * @return a typesafe list. 2509 */ 2510 public static <E> List<E> checkedList(List<E> list, Class<E> type) { 2511 if (list instanceof RandomAccess) { 2512 return new CheckedRandomAccessList<E>(list, type); 2513 } 2514 return new CheckedList<E>(list, type); 2515 } 2516 2517 /** 2518 * Returns a dynamically typesafe view of the specified set. Trying to 2519 * insert an element of the wrong type into this set throws a 2520 * {@code ClassCastException}. At creation time the types in {@code s} are 2521 * not checked for correct type. 2522 * 2523 * @param s 2524 * the set to be wrapped in a typesafe set. 2525 * @param type 2526 * the type of the elements permitted to insert. 2527 * @return a typesafe set. 2528 */ 2529 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) { 2530 return new CheckedSet<E>(s, type); 2531 } 2532 2533 /** 2534 * Returns a dynamically typesafe view of the specified sorted map. Trying 2535 * to insert an element of the wrong type into this sorted map throws a 2536 * {@code ClassCastException}. At creation time the types in {@code m} are 2537 * not checked for correct type. 2538 * 2539 * @param m 2540 * the sorted map to be wrapped in a typesafe sorted map. 2541 * @param keyType 2542 * the type of the keys permitted to insert. 2543 * @param valueType 2544 * the type of the values permitted to insert. 2545 * @return a typesafe sorted map. 2546 */ 2547 public static <K, V> SortedMap<K, V> checkedSortedMap(SortedMap<K, V> m, 2548 Class<K> keyType, Class<V> valueType) { 2549 return new CheckedSortedMap<K, V>(m, keyType, valueType); 2550 } 2551 2552 /** 2553 * Returns a dynamically typesafe view of the specified sorted set. Trying 2554 * to insert an element of the wrong type into this sorted set throws a 2555 * {@code ClassCastException}. At creation time the types in {@code s} are 2556 * not checked for correct type. 2557 * 2558 * @param s 2559 * the sorted set to be wrapped in a typesafe sorted set. 2560 * @param type 2561 * the type of the elements permitted to insert. 2562 * @return a typesafe sorted set. 2563 */ 2564 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, 2565 Class<E> type) { 2566 return new CheckedSortedSet<E>(s, type); 2567 } 2568 2569 /** 2570 * Adds all the specified elements to the specified collection. 2571 * 2572 * @param c 2573 * the collection the elements are to be inserted into. 2574 * @param a 2575 * the elements to insert. 2576 * @return true if the collection changed during insertion. 2577 * @throws UnsupportedOperationException 2578 * when the method is not supported. 2579 * @throws NullPointerException 2580 * when {@code c} or {@code a} is {@code null}, or {@code a} 2581 * contains one or more {@code null} elements and {@code c} 2582 * doesn't support {@code null} elements. 2583 * @throws IllegalArgumentException 2584 * if at least one of the elements can't be inserted into the 2585 * collection. 2586 */ 2587 public static <T> boolean addAll(Collection<? super T> c, T... a) { 2588 boolean modified = false; 2589 for (int i = 0; i < a.length; i++) { 2590 modified |= c.add(a[i]); 2591 } 2592 return modified; 2593 } 2594 2595 /** 2596 * Returns whether the specified collections have no elements in common. 2597 * 2598 * @param c1 2599 * the first collection. 2600 * @param c2 2601 * the second collection. 2602 * @return {@code true} if the collections have no elements in common, 2603 * {@code false} otherwise. 2604 * @throws NullPointerException 2605 * if one of the collections is {@code null}. 2606 */ 2607 public static boolean disjoint(Collection<?> c1, Collection<?> c2) { 2608 if ((c1 instanceof Set) && !(c2 instanceof Set) 2609 || (c2.size()) > c1.size()) { 2610 Collection<?> tmp = c1; 2611 c1 = c2; 2612 c2 = tmp; 2613 } 2614 Iterator<?> it = c1.iterator(); 2615 while (it.hasNext()) { 2616 if (c2.contains(it.next())) { 2617 return false; 2618 } 2619 } 2620 return true; 2621 } 2622 2623 /** 2624 * Checks if specified object is instance of specified class. Used for a 2625 * dynamically typesafe view of the collections. 2626 * 2627 * @param obj - 2628 * object is to be checked 2629 * @param type - 2630 * class of object that should be 2631 * @return specified object 2632 */ 2633 static <E> E checkType(E obj, Class<? extends E> type) { 2634 if (obj != null && !type.isInstance(obj)) { 2635 throw new ClassCastException("Attempt to insert element of type " + obj.getClass() + 2636 " into collection of type " + type); 2637 } 2638 return obj; 2639 } 2640 2641 /** 2642 * Returns a set backed by {@code map}. 2643 * 2644 * @throws IllegalArgumentException if the map is not empty 2645 * @since 1.6 2646 */ 2647 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 2648 if (map.isEmpty()) { 2649 return new SetFromMap<E>(map); 2650 } 2651 throw new IllegalArgumentException(); 2652 } 2653 2654 /** 2655 * Returns a last-in, first-out queue as a view of {@code deque}. 2656 * 2657 * @since 1.6 2658 */ 2659 public static <T> Queue<T> asLifoQueue(Deque<T> deque) { 2660 return new AsLIFOQueue<T>(deque); 2661 } 2662 2663 private static class SetFromMap<E> extends AbstractSet<E> implements Serializable { 2664 private static final long serialVersionUID = 2454657854757543876L; 2665 2666 // must named as it, to pass serialization compatibility test. 2667 private Map<E, Boolean> m; 2668 2669 private transient Set<E> backingSet; 2670 2671 SetFromMap(final Map<E, Boolean> map) { 2672 m = map; 2673 backingSet = map.keySet(); 2674 } 2675 2676 @Override public boolean equals(Object object) { 2677 return backingSet.equals(object); 2678 } 2679 2680 @Override public int hashCode() { 2681 return backingSet.hashCode(); 2682 } 2683 2684 @Override public boolean add(E object) { 2685 return m.put(object, Boolean.TRUE) == null; 2686 } 2687 2688 @Override public void clear() { 2689 m.clear(); 2690 } 2691 2692 @Override public String toString() { 2693 return backingSet.toString(); 2694 } 2695 2696 @Override public boolean contains(Object object) { 2697 return backingSet.contains(object); 2698 } 2699 2700 @Override public boolean containsAll(Collection<?> collection) { 2701 return backingSet.containsAll(collection); 2702 } 2703 2704 @Override public boolean isEmpty() { 2705 return m.isEmpty(); 2706 } 2707 2708 @Override public boolean remove(Object object) { 2709 return m.remove(object) != null; 2710 } 2711 2712 @Override public boolean retainAll(Collection<?> collection) { 2713 return backingSet.retainAll(collection); 2714 } 2715 2716 @Override public Object[] toArray() { 2717 return backingSet.toArray(); 2718 } 2719 2720 @Override 2721 public <T> T[] toArray(T[] contents) { 2722 return backingSet.toArray(contents); 2723 } 2724 2725 @Override public Iterator<E> iterator() { 2726 return backingSet.iterator(); 2727 } 2728 2729 @Override public int size() { 2730 return m.size(); 2731 } 2732 2733 @SuppressWarnings("unchecked") 2734 private void readObject(ObjectInputStream stream) 2735 throws IOException, ClassNotFoundException { 2736 stream.defaultReadObject(); 2737 backingSet = m.keySet(); 2738 } 2739 } 2740 2741 private static class AsLIFOQueue<E> extends AbstractQueue<E> implements Serializable { 2742 private static final long serialVersionUID = 1802017725587941708L; 2743 2744 // must named as it, to pass serialization compatibility test. 2745 private final Deque<E> q; 2746 2747 AsLIFOQueue(final Deque<E> deque) { 2748 this.q = deque; 2749 } 2750 2751 @Override public Iterator<E> iterator() { 2752 return q.iterator(); 2753 } 2754 2755 @Override public int size() { 2756 return q.size(); 2757 } 2758 2759 @Override public boolean offer(E o) { 2760 return q.offerFirst(o); 2761 } 2762 2763 @Override public E peek() { 2764 return q.peekFirst(); 2765 } 2766 2767 @Override public E poll() { 2768 return q.pollFirst(); 2769 } 2770 2771 @Override public boolean add(E o) { 2772 q.push(o); 2773 return true; 2774 } 2775 2776 @Override public void clear() { 2777 q.clear(); 2778 } 2779 2780 @Override public E element() { 2781 return q.getFirst(); 2782 } 2783 2784 @Override public E remove() { 2785 return q.pop(); 2786 } 2787 2788 @Override public boolean contains(Object object) { 2789 return q.contains(object); 2790 } 2791 2792 @Override public boolean containsAll(Collection<?> collection) { 2793 return q.containsAll(collection); 2794 } 2795 2796 @Override public boolean isEmpty() { 2797 return q.isEmpty(); 2798 } 2799 2800 @Override public boolean remove(Object object) { 2801 return q.remove(object); 2802 } 2803 2804 @Override public boolean removeAll(Collection<?> collection) { 2805 return q.removeAll(collection); 2806 } 2807 2808 @Override public boolean retainAll(Collection<?> collection) { 2809 return q.retainAll(collection); 2810 } 2811 2812 @Override public Object[] toArray() { 2813 return q.toArray(); 2814 } 2815 2816 @Override public <T> T[] toArray(T[] contents) { 2817 return q.toArray(contents); 2818 } 2819 2820 @Override public String toString() { 2821 return q.toString(); 2822 } 2823 } 2824 2825 /** 2826 * A dynamically typesafe view of a Collection. 2827 */ 2828 private static class CheckedCollection<E> implements Collection<E>, Serializable { 2829 2830 private static final long serialVersionUID = 1578914078182001775L; 2831 2832 Collection<E> c; 2833 2834 Class<E> type; 2835 2836 public CheckedCollection(Collection<E> c, Class<E> type) { 2837 if (c == null || type == null) { 2838 throw new NullPointerException(); 2839 } 2840 this.c = c; 2841 this.type = type; 2842 } 2843 2844 @Override public int size() { 2845 return c.size(); 2846 } 2847 2848 @Override public boolean isEmpty() { 2849 return c.isEmpty(); 2850 } 2851 2852 @Override public boolean contains(Object obj) { 2853 return c.contains(obj); 2854 } 2855 2856 @Override public Iterator<E> iterator() { 2857 Iterator<E> i = c.iterator(); 2858 if (i instanceof ListIterator) { 2859 i = new CheckedListIterator<E>((ListIterator<E>) i, type); 2860 } 2861 return i; 2862 } 2863 2864 @Override public Object[] toArray() { 2865 return c.toArray(); 2866 } 2867 2868 @Override public <T> T[] toArray(T[] arr) { 2869 return c.toArray(arr); 2870 } 2871 2872 @Override public boolean add(E obj) { 2873 return c.add(checkType(obj, type)); 2874 } 2875 2876 @Override public boolean remove(Object obj) { 2877 return c.remove(obj); 2878 } 2879 2880 @Override public boolean containsAll(Collection<?> c1) { 2881 return c.containsAll(c1); 2882 } 2883 2884 @SuppressWarnings("unchecked") 2885 @Override public boolean addAll(Collection<? extends E> c1) { 2886 Object[] array = c1.toArray(); 2887 for (Object o : array) { 2888 checkType(o, type); 2889 } 2890 return c.addAll((List<E>) Arrays.asList(array)); 2891 } 2892 2893 @Override public boolean removeAll(Collection<?> c1) { 2894 return c.removeAll(c1); 2895 } 2896 2897 @Override public boolean retainAll(Collection<?> c1) { 2898 return c.retainAll(c1); 2899 } 2900 2901 @Override public void clear() { 2902 c.clear(); 2903 } 2904 2905 @Override public String toString() { 2906 return c.toString(); 2907 } 2908 } 2909 2910 /** 2911 * Class represents a dynamically typesafe view of the specified 2912 * ListIterator. 2913 */ 2914 private static class CheckedListIterator<E> implements ListIterator<E> { 2915 2916 private ListIterator<E> i; 2917 2918 private Class<E> type; 2919 2920 /** 2921 * Constructs a dynamically typesafe view of the specified ListIterator. 2922 * 2923 * @param i - 2924 * the listIterator for which a dynamically typesafe view to 2925 * be constructed. 2926 */ 2927 public CheckedListIterator(ListIterator<E> i, Class<E> type) { 2928 this.i = i; 2929 this.type = type; 2930 } 2931 2932 @Override public boolean hasNext() { 2933 return i.hasNext(); 2934 } 2935 2936 @Override public E next() { 2937 return i.next(); 2938 } 2939 2940 @Override public void remove() { 2941 i.remove(); 2942 } 2943 2944 @Override public boolean hasPrevious() { 2945 return i.hasPrevious(); 2946 } 2947 2948 @Override public E previous() { 2949 return i.previous(); 2950 } 2951 2952 @Override public int nextIndex() { 2953 return i.nextIndex(); 2954 } 2955 2956 @Override public int previousIndex() { 2957 return i.previousIndex(); 2958 } 2959 2960 @Override public void set(E obj) { 2961 i.set(checkType(obj, type)); 2962 } 2963 2964 @Override public void add(E obj) { 2965 i.add(checkType(obj, type)); 2966 } 2967 } 2968 2969 /** 2970 * Class represents a dynamically typesafe view of a List. 2971 */ 2972 private static class CheckedList<E> extends CheckedCollection<E> implements List<E> { 2973 2974 private static final long serialVersionUID = 65247728283967356L; 2975 2976 List<E> l; 2977 2978 public CheckedList(List<E> l, Class<E> type) { 2979 super(l, type); 2980 this.l = l; 2981 } 2982 2983 @SuppressWarnings("unchecked") 2984 @Override public boolean addAll(int index, Collection<? extends E> c1) { 2985 Object[] array = c1.toArray(); 2986 for (Object o : array) { 2987 checkType(o, type); 2988 } 2989 return l.addAll(index, (List<E>) Arrays.asList(array)); 2990 } 2991 2992 @Override public E get(int index) { 2993 return l.get(index); 2994 } 2995 2996 @Override public E set(int index, E obj) { 2997 return l.set(index, checkType(obj, type)); 2998 } 2999 3000 @Override public void add(int index, E obj) { 3001 l.add(index, checkType(obj, type)); 3002 } 3003 3004 @Override public E remove(int index) { 3005 return l.remove(index); 3006 } 3007 3008 @Override public int indexOf(Object obj) { 3009 return l.indexOf(obj); 3010 } 3011 3012 @Override public int lastIndexOf(Object obj) { 3013 return l.lastIndexOf(obj); 3014 } 3015 3016 @Override public ListIterator<E> listIterator() { 3017 return new CheckedListIterator<E>(l.listIterator(), type); 3018 } 3019 3020 @Override public ListIterator<E> listIterator(int index) { 3021 return new CheckedListIterator<E>(l.listIterator(index), type); 3022 } 3023 3024 @Override public List<E> subList(int fromIndex, int toIndex) { 3025 return checkedList(l.subList(fromIndex, toIndex), type); 3026 } 3027 3028 @Override public boolean equals(Object obj) { 3029 return l.equals(obj); 3030 } 3031 3032 @Override public int hashCode() { 3033 return l.hashCode(); 3034 } 3035 } 3036 3037 /** 3038 * A dynamically typesafe view of a RandomAccessList. 3039 */ 3040 private static class CheckedRandomAccessList<E> extends CheckedList<E> implements RandomAccess { 3041 3042 private static final long serialVersionUID = 1638200125423088369L; 3043 3044 public CheckedRandomAccessList(List<E> l, Class<E> type) { 3045 super(l, type); 3046 } 3047 } 3048 3049 /** 3050 * A dynamically typesafe view of a Set. 3051 */ 3052 private static class CheckedSet<E> extends CheckedCollection<E> implements Set<E> { 3053 3054 private static final long serialVersionUID = 4694047833775013803L; 3055 3056 public CheckedSet(Set<E> s, Class<E> type) { 3057 super(s, type); 3058 } 3059 3060 @Override public boolean equals(Object obj) { 3061 return c.equals(obj); 3062 } 3063 3064 @Override public int hashCode() { 3065 return c.hashCode(); 3066 } 3067 3068 } 3069 3070 /** 3071 * A dynamically typesafe view of a Map. 3072 */ 3073 private static class CheckedMap<K, V> implements Map<K, V>, Serializable { 3074 3075 private static final long serialVersionUID = 5742860141034234728L; 3076 3077 Map<K, V> m; 3078 Class<K> keyType; 3079 Class<V> valueType; 3080 3081 private CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) { 3082 if (m == null || keyType == null || valueType == null) { 3083 throw new NullPointerException(); 3084 } 3085 this.m = m; 3086 this.keyType = keyType; 3087 this.valueType = valueType; 3088 } 3089 3090 @Override public int size() { 3091 return m.size(); 3092 } 3093 3094 @Override public boolean isEmpty() { 3095 return m.isEmpty(); 3096 } 3097 3098 @Override public boolean containsKey(Object key) { 3099 return m.containsKey(key); 3100 } 3101 3102 @Override public boolean containsValue(Object value) { 3103 return m.containsValue(value); 3104 } 3105 3106 @Override public V get(Object key) { 3107 return m.get(key); 3108 } 3109 3110 @Override public V put(K key, V value) { 3111 return m.put(checkType(key, keyType), checkType(value, valueType)); 3112 } 3113 3114 @Override public V remove(Object key) { 3115 return m.remove(key); 3116 } 3117 3118 @SuppressWarnings("unchecked") 3119 @Override public void putAll(Map<? extends K, ? extends V> map) { 3120 int size = map.size(); 3121 if (size == 0) { 3122 return; 3123 } 3124 Map.Entry<? extends K, ? extends V>[] entries = new Map.Entry[size]; 3125 Iterator<? extends Map.Entry<? extends K, ? extends V>> it = map 3126 .entrySet().iterator(); 3127 for (int i = 0; i < size; i++) { 3128 Map.Entry<? extends K, ? extends V> e = it.next(); 3129 checkType(e.getKey(), keyType); 3130 checkType(e.getValue(), valueType); 3131 entries[i] = e; 3132 } 3133 for (int i = 0; i < size; i++) { 3134 m.put(entries[i].getKey(), entries[i].getValue()); 3135 } 3136 } 3137 3138 @Override public void clear() { 3139 m.clear(); 3140 } 3141 3142 @Override public Set<K> keySet() { 3143 return m.keySet(); 3144 } 3145 3146 @Override public Collection<V> values() { 3147 return m.values(); 3148 } 3149 3150 @Override public Set<Map.Entry<K, V>> entrySet() { 3151 return new CheckedEntrySet<K, V>(m.entrySet(), valueType); 3152 } 3153 3154 @Override public boolean equals(Object obj) { 3155 return m.equals(obj); 3156 } 3157 3158 @Override public int hashCode() { 3159 return m.hashCode(); 3160 } 3161 3162 @Override public String toString() { 3163 return m.toString(); 3164 } 3165 3166 /** 3167 * A dynamically typesafe view of a Map.Entry. 3168 */ 3169 private static class CheckedEntry<K, V> implements Map.Entry<K, V> { 3170 Map.Entry<K, V> e; 3171 Class<V> valueType; 3172 3173 public CheckedEntry(Map.Entry<K, V> e, Class<V> valueType) { 3174 if (e == null) { 3175 throw new NullPointerException(); 3176 } 3177 this.e = e; 3178 this.valueType = valueType; 3179 } 3180 3181 @Override public K getKey() { 3182 return e.getKey(); 3183 } 3184 3185 @Override public V getValue() { 3186 return e.getValue(); 3187 } 3188 3189 @Override public V setValue(V obj) { 3190 return e.setValue(checkType(obj, valueType)); 3191 } 3192 3193 @Override public boolean equals(Object obj) { 3194 return e.equals(obj); 3195 } 3196 3197 @Override public int hashCode() { 3198 return e.hashCode(); 3199 } 3200 } 3201 3202 /** 3203 * A dynamically typesafe view of an entry set. 3204 */ 3205 private static class CheckedEntrySet<K, V> implements Set<Map.Entry<K, V>> { 3206 Set<Map.Entry<K, V>> s; 3207 Class<V> valueType; 3208 3209 public CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) { 3210 this.s = s; 3211 this.valueType = valueType; 3212 } 3213 3214 @Override public Iterator<Map.Entry<K, V>> iterator() { 3215 return new CheckedEntryIterator<K, V>(s.iterator(), valueType); 3216 } 3217 3218 @Override public Object[] toArray() { 3219 int thisSize = size(); 3220 Object[] array = new Object[thisSize]; 3221 Iterator<?> it = iterator(); 3222 for (int i = 0; i < thisSize; i++) { 3223 array[i] = it.next(); 3224 } 3225 return array; 3226 } 3227 3228 @SuppressWarnings("unchecked") 3229 @Override public <T> T[] toArray(T[] array) { 3230 int thisSize = size(); 3231 if (array.length < thisSize) { 3232 Class<?> ct = array.getClass().getComponentType(); 3233 array = (T[]) Array.newInstance(ct, thisSize); 3234 } 3235 Iterator<?> it = iterator(); 3236 for (int i = 0; i < thisSize; i++) { 3237 array[i] = (T) it.next(); 3238 } 3239 if (thisSize < array.length) { 3240 array[thisSize] = null; 3241 } 3242 return array; 3243 } 3244 3245 @Override public boolean retainAll(Collection<?> c) { 3246 return s.retainAll(c); 3247 } 3248 3249 @Override public boolean removeAll(Collection<?> c) { 3250 return s.removeAll(c); 3251 } 3252 3253 @Override public boolean containsAll(Collection<?> c) { 3254 return s.containsAll(c); 3255 } 3256 3257 @Override public boolean addAll(Collection<? extends Map.Entry<K, V>> c) { 3258 throw new UnsupportedOperationException(); 3259 } 3260 3261 @Override public boolean remove(Object o) { 3262 return s.remove(o); 3263 } 3264 3265 @Override public boolean contains(Object o) { 3266 return s.contains(o); 3267 } 3268 3269 @Override public boolean add(Map.Entry<K, V> o) { 3270 throw new UnsupportedOperationException(); 3271 } 3272 3273 @Override public boolean isEmpty() { 3274 return s.isEmpty(); 3275 } 3276 3277 @Override public void clear() { 3278 s.clear(); 3279 } 3280 3281 @Override public int size() { 3282 return s.size(); 3283 } 3284 3285 @Override public int hashCode() { 3286 return s.hashCode(); 3287 } 3288 3289 @Override public boolean equals(Object object) { 3290 return s.equals(object); 3291 } 3292 3293 /** 3294 * A dynamically typesafe view of an entry iterator. 3295 */ 3296 private static class CheckedEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> { 3297 Iterator<Map.Entry<K, V>> i; 3298 Class<V> valueType; 3299 3300 public CheckedEntryIterator(Iterator<Map.Entry<K, V>> i, 3301 Class<V> valueType) { 3302 this.i = i; 3303 this.valueType = valueType; 3304 } 3305 3306 @Override public boolean hasNext() { 3307 return i.hasNext(); 3308 } 3309 3310 @Override public void remove() { 3311 i.remove(); 3312 } 3313 3314 @Override public Map.Entry<K, V> next() { 3315 return new CheckedEntry<K, V>(i.next(), valueType); 3316 } 3317 } 3318 } 3319 } 3320 3321 /** 3322 * A dynamically typesafe view of a SortedSet. 3323 */ 3324 private static class CheckedSortedSet<E> extends CheckedSet<E> implements SortedSet<E> { 3325 private static final long serialVersionUID = 1599911165492914959L; 3326 private SortedSet<E> ss; 3327 3328 public CheckedSortedSet(SortedSet<E> s, Class<E> type) { 3329 super(s, type); 3330 this.ss = s; 3331 } 3332 3333 @Override public Comparator<? super E> comparator() { 3334 return ss.comparator(); 3335 } 3336 3337 @Override public SortedSet<E> subSet(E fromElement, E toElement) { 3338 return new CheckedSortedSet<E>(ss.subSet(fromElement, toElement), 3339 type); 3340 } 3341 3342 @Override public SortedSet<E> headSet(E toElement) { 3343 return new CheckedSortedSet<E>(ss.headSet(toElement), type); 3344 } 3345 3346 @Override public SortedSet<E> tailSet(E fromElement) { 3347 return new CheckedSortedSet<E>(ss.tailSet(fromElement), type); 3348 } 3349 3350 @Override public E first() { 3351 return ss.first(); 3352 } 3353 3354 @Override public E last() { 3355 return ss.last(); 3356 } 3357 } 3358 3359 /** 3360 * A dynamically typesafe view of a SortedMap. 3361 */ 3362 private static class CheckedSortedMap<K, V> extends CheckedMap<K, V> 3363 implements SortedMap<K, V> { 3364 private static final long serialVersionUID = 1599671320688067438L; 3365 SortedMap<K, V> sm; 3366 3367 CheckedSortedMap(SortedMap<K, V> m, Class<K> keyType, Class<V> valueType) { 3368 super(m, keyType, valueType); 3369 this.sm = m; 3370 } 3371 3372 @Override public Comparator<? super K> comparator() { 3373 return sm.comparator(); 3374 } 3375 3376 @Override public SortedMap<K, V> subMap(K fromKey, K toKey) { 3377 return new CheckedSortedMap<K, V>(sm.subMap(fromKey, toKey), keyType, valueType); 3378 } 3379 3380 @Override public SortedMap<K, V> headMap(K toKey) { 3381 return new CheckedSortedMap<K, V>(sm.headMap(toKey), keyType, valueType); 3382 } 3383 3384 @Override public SortedMap<K, V> tailMap(K fromKey) { 3385 return new CheckedSortedMap<K, V>(sm.tailMap(fromKey), keyType, valueType); 3386 } 3387 3388 @Override public K firstKey() { 3389 return sm.firstKey(); 3390 } 3391 3392 @Override public K lastKey() { 3393 return sm.lastKey(); 3394 } 3395 } 3396 } 3397