1 /* Collections.java -- Utility class with methods to operate on collections
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
3 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
7 GNU Classpath is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU Classpath is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Classpath; see the file COPYING. If not, write to the
19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 Linking this library statically or dynamically with other modules is
23 making a combined work based on this library. Thus, the terms and
24 conditions of the GNU General Public License cover the whole
27 As a special exception, the copyright holders of this library give you
28 permission to link this library with independent modules to produce an
29 executable, regardless of the license terms of these independent
30 modules, and to copy and distribute the resulting executable under
31 terms of your choice, provided that you also meet, for each linked
32 independent module, the terms and conditions of the license of that
33 module. An independent module is a module which is not derived from
34 or based on this library. If you modify this library, you may extend
35 this exception to your version of the library, but you are not
36 obligated to do so. If you do not wish to do so, delete this
37 exception statement from your version. */
42 import java.io.Serializable;
45 * Utility class consisting of static methods that operate on, or return
46 * Collections. Contains methods to sort, search, reverse, fill and shuffle
47 * Collections, methods to facilitate interoperability with legacy APIs that
48 * are unaware of collections, a method to return a list which consists of
49 * multiple copies of one element, and methods which "wrap" collections to give
50 * them extra properties, such as thread-safety and unmodifiability.
53 * All methods which take a collection throw a {@link NullPointerException} if
54 * that collection is null. Algorithms which can change a collection may, but
55 * are not required, to throw the {@link UnsupportedOperationException} that
56 * the underlying collection would throw during an attempt at modification.
58 * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code>
59 * does not throw a exception, even though addAll is an unsupported operation
60 * on a singleton; the reason for this is that addAll did not attempt to
63 * @author Original author unknown
64 * @author Eric Blake (ebb9@email.byu.edu)
65 * @author Tom Tromey (tromey@redhat.com)
66 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
73 * @status updated to 1.5
75 public class Collections
78 * Constant used to decide cutoff for when a non-RandomAccess list should
79 * be treated as sequential-access. Basically, quadratic behavior is
80 * acceptable for small lists when the overhead is so small in the first
81 * place. I arbitrarily set it to 16, so it may need some tuning.
83 private static final int LARGE_LIST_SIZE = 16;
86 * Determines if a list should be treated as a sequential-access one.
87 * Rather than the old method of JDK 1.3 of assuming only instanceof
88 * AbstractSequentialList should be sequential, this uses the new method
89 * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
90 * and exceeds a large (unspecified) size should be sequential.
92 * @param l the list to check
93 * @return <code>true</code> if it should be treated as sequential-access
95 private static boolean isSequential(List<?> l)
97 return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
101 * This class is non-instantiable.
103 private Collections()
108 * An immutable, serializable, empty Set.
111 public static final Set EMPTY_SET = new EmptySet();
114 * Returns an immutable, serializable parameterized empty set.
115 * Unlike the constant <code>EMPTY_SET</code>, the set returned by
116 * this method is type-safe.
118 * @return an empty parameterized set.
121 public static final <T> Set<T> emptySet()
123 /* FIXME: Could this be optimized? */
124 return new EmptySet<T>();
128 * The implementation of {@link #EMPTY_SET}. This class name is required
129 * for compatibility with Sun's JDK serializability.
131 * @author Eric Blake (ebb9@email.byu.edu)
133 private static final class EmptySet<T> extends AbstractSet<T>
134 implements Serializable
137 * Compatible with JDK 1.4.
139 private static final long serialVersionUID = 1582296315990362920L;
142 * A private constructor adds overhead.
149 * The size: always 0!
158 * Returns an iterator that does not iterate.
159 * @return A non-iterating iterator.
161 // This is really cheating! I think it's perfectly valid, though.
162 public Iterator<T> iterator()
164 return (Iterator<T>) EMPTY_LIST.iterator();
167 // The remaining methods are optional, but provide a performance
168 // advantage by not allocating unnecessary iterators in AbstractSet.
170 * The empty set never contains anything.
171 * @param o The object to search for.
172 * @return <code>false</code>.
174 public boolean contains(Object o)
180 * This is true only if the given collection is also empty.
181 * @param c The collection of objects which are to be compared
182 * against the members of this set.
183 * @return <code>true</code> if c is empty.
185 public boolean containsAll(Collection<?> c)
191 * Equal only if the other set is empty.
192 * @param o The object to compare with this set.
193 * @return <code>true</code> if o is an empty instance of <code>Set</code>.
195 public boolean equals(Object o)
197 return o instanceof Set && ((Set) o).isEmpty();
201 * The hashcode is always 0.
204 public int hashCode()
210 * Always succeeds with a <code>false</code> result.
211 * @param o The object to remove.
212 * @return <code>false</code>.
214 public boolean remove(Object o)
220 * Always succeeds with a <code>false</code> result.
221 * @param c The collection of objects which should
222 * all be removed from this set.
223 * @return <code>false</code>.
225 public boolean removeAll(Collection<?> c)
231 * Always succeeds with a <code>false</code> result.
232 * @param c The collection of objects which should
233 * all be retained within this set.
234 * @return <code>false</code>.
236 public boolean retainAll(Collection<?> c)
242 * The array is always empty.
243 * @return A new array with a size of 0.
245 public Object[] toArray()
247 return new Object[0];
251 * We don't even need to use reflection!
252 * @param a An existing array, which can be empty.
253 * @return The original array with any existing
254 * initial element set to null.
256 public <E> E[] toArray(E[] a)
264 * The string never changes.
266 * @return the string "[]".
268 public String toString()
275 * An immutable, serializable, empty List, which implements RandomAccess.
279 public static final List EMPTY_LIST = new EmptyList();
282 * Returns an immutable, serializable parameterized empty list.
283 * Unlike the constant <code>EMPTY_LIST</code>, the list returned by
284 * this method is type-safe.
286 * @return an empty parameterized list.
289 public static final <T> List<T> emptyList()
291 /* FIXME: Could this be optimized? */
292 return new EmptyList<T>();
296 * The implementation of {@link #EMPTY_LIST}. This class name is required
297 * for compatibility with Sun's JDK serializability.
299 * @author Eric Blake (ebb9@email.byu.edu)
301 private static final class EmptyList<T> extends AbstractList<T>
302 implements Serializable, RandomAccess
305 * Compatible with JDK 1.4.
307 private static final long serialVersionUID = 8842843931221139166L;
310 * A private constructor adds overhead.
317 * The size is always 0.
326 * No matter the index, it is out of bounds. This
327 * method never returns, throwing an exception instead.
329 * @param index The index of the element to retrieve.
330 * @return the object at the specified index.
331 * @throws IndexOutOfBoundsException as any given index
332 * is outside the bounds of an empty array.
334 public T get(int index)
336 throw new IndexOutOfBoundsException();
339 // The remaining methods are optional, but provide a performance
340 // advantage by not allocating unnecessary iterators in AbstractList.
342 * Never contains anything.
343 * @param o The object to search for.
344 * @return <code>false</code>.
346 public boolean contains(Object o)
352 * This is true only if the given collection is also empty.
353 * @param c The collection of objects, which should be compared
354 * against the members of this list.
355 * @return <code>true</code> if c is also empty.
357 public boolean containsAll(Collection<?> c)
363 * Equal only if the other list is empty.
364 * @param o The object to compare against this list.
365 * @return <code>true</code> if o is also an empty instance of
368 public boolean equals(Object o)
370 return o instanceof List && ((List) o).isEmpty();
374 * The hashcode is always 1.
377 public int hashCode()
384 * @param o The object to search for.
387 public int indexOf(Object o)
394 * @param o The object to search for.
397 public int lastIndexOf(Object o)
403 * Always succeeds with <code>false</code> result.
404 * @param o The object to remove.
407 public boolean remove(Object o)
413 * Always succeeds with <code>false</code> result.
414 * @param c The collection of objects which should
415 * all be removed from this list.
416 * @return <code>false</code>.
418 public boolean removeAll(Collection<?> c)
424 * Always succeeds with <code>false</code> result.
425 * @param c The collection of objects which should
426 * all be retained within this list.
427 * @return <code>false</code>.
429 public boolean retainAll(Collection<?> c)
435 * The array is always empty.
436 * @return A new array with a size of 0.
438 public Object[] toArray()
440 return new Object[0];
444 * We don't even need to use reflection!
445 * @param a An existing array, which can be empty.
446 * @return The original array with any existing
447 * initial element set to null.
449 public <E> E[] toArray(E[] a)
457 * The string never changes.
459 * @return the string "[]".
461 public String toString()
468 * An immutable, serializable, empty Map.
471 public static final Map EMPTY_MAP = new EmptyMap();
474 * Returns an immutable, serializable parameterized empty map.
475 * Unlike the constant <code>EMPTY_MAP</code>, the map returned by
476 * this method is type-safe.
478 * @return an empty parameterized map.
481 public static final <K,V> Map<K,V> emptyMap()
483 /* FIXME: Could this be optimized? */
484 return new EmptyMap<K,V>();
488 * The implementation of {@link #EMPTY_MAP}. This class name is required
489 * for compatibility with Sun's JDK serializability.
491 * @author Eric Blake (ebb9@email.byu.edu)
493 private static final class EmptyMap<K, V> extends AbstractMap<K, V>
494 implements Serializable
497 * Compatible with JDK 1.4.
499 private static final long serialVersionUID = 6428348081105594320L;
502 * A private constructor adds overhead.
509 * There are no entries.
510 * @return The empty set.
512 public Set<Map.Entry<K, V>> entrySet()
517 // The remaining methods are optional, but provide a performance
518 // advantage by not allocating unnecessary iterators in AbstractMap.
521 * @param key The key to search for.
522 * @return <code>false</code>.
524 public boolean containsKey(Object key)
531 * @param value The value to search for.
532 * @return <code>false</code>.
534 public boolean containsValue(Object value)
540 * Equal to all empty maps.
541 * @param o The object o to compare against this map.
542 * @return <code>true</code> if o is also an empty instance of
545 public boolean equals(Object o)
547 return o instanceof Map && ((Map) o).isEmpty();
551 * No mappings, so this returns null.
552 * @param o The key of the object to retrieve.
555 public V get(Object o)
561 * The hashcode is always 0.
564 public int hashCode()
571 * @return The empty set.
573 public Set<K> keySet()
579 * Remove always succeeds, with null result.
580 * @param o The key of the mapping to remove.
581 * @return null, as there is never a mapping for o.
583 public V remove(Object o)
598 * No entries. Technically, EMPTY_SET, while more specific than a general
599 * Collection, will work. Besides, that's what the JDK uses!
600 * @return The empty set.
602 public Collection<V> values()
608 * The string never changes.
610 * @return the string "[]".
612 public String toString()
620 * Compare two objects with or without a Comparator. If c is null, uses the
621 * natural ordering. Slightly slower than doing it inline if the JVM isn't
622 * clever, but worth it for removing a duplicate of the search code.
623 * Note: This code is also used in Arrays (for sort as well as search).
625 static final <T> int compare(T o1, T o2, Comparator<? super T> c)
627 return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
631 * Perform a binary search of a List for a key, using the natural ordering of
632 * the elements. The list must be sorted (as by the sort() method) - if it is
633 * not, the behavior of this method is undefined, and may be an infinite
634 * loop. Further, the key must be comparable with every item in the list. If
635 * the list contains the key more than once, any one of them may be found.
638 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
639 * and uses a linear search with O(n) link traversals and log(n) comparisons
640 * with {@link AbstractSequentialList} lists. Note: although the
641 * specification allows for an infinite loop if the list is unsorted, it will
642 * not happen in this (Classpath) implementation.
644 * @param l the list to search (must be sorted)
645 * @param key the value to search for
646 * @return the index at which the key was found, or -n-1 if it was not
647 * found, where n is the index of the first value higher than key or
648 * a.length if there is no such value
649 * @throws ClassCastException if key could not be compared with one of the
651 * @throws NullPointerException if a null element has compareTo called
654 public static <T> int binarySearch(List<? extends Comparable<? super T>> l,
657 return binarySearch(l, key, null);
661 * Perform a binary search of a List for a key, using a supplied Comparator.
662 * The list must be sorted (as by the sort() method with the same Comparator)
663 * - if it is not, the behavior of this method is undefined, and may be an
664 * infinite loop. Further, the key must be comparable with every item in the
665 * list. If the list contains the key more than once, any one of them may be
666 * found. If the comparator is null, the elements' natural ordering is used.
669 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
670 * and uses a linear search with O(n) link traversals and log(n) comparisons
671 * with {@link AbstractSequentialList} lists. Note: although the
672 * specification allows for an infinite loop if the list is unsorted, it will
673 * not happen in this (Classpath) implementation.
675 * @param l the list to search (must be sorted)
676 * @param key the value to search for
677 * @param c the comparator by which the list is sorted
678 * @return the index at which the key was found, or -n-1 if it was not
679 * found, where n is the index of the first value higher than key or
680 * a.length if there is no such value
681 * @throws ClassCastException if key could not be compared with one of the
683 * @throws NullPointerException if a null element is compared with natural
684 * ordering (only possible when c is null)
685 * @see #sort(List, Comparator)
687 public static <T> int binarySearch(List<? extends T> l, T key,
688 Comparator<? super T> c)
692 int hi = l.size() - 1;
694 // We use a linear search with log(n) comparisons using an iterator
695 // if the list is sequential-access.
698 ListIterator<T> itr = ((List<T>) l).listIterator();
700 T o = itr.next(); // Assumes list is not empty (see isSequential)
701 boolean forward = true;
704 pos = (low + hi) >>> 1;
708 itr.next(); // Changing direction first.
709 for ( ; i != pos; i++, o = itr.next());
715 itr.previous(); // Changing direction first.
716 for ( ; i != pos; i--, o = itr.previous());
719 final int d = compare(o, key, c);
725 // This gets the insertion point right on the last loop
733 pos = (low + hi) >>> 1;
734 final int d = compare(((List<T>) l).get(pos), key, c);
740 // This gets the insertion point right on the last loop
745 // If we failed to find it, we do the same whichever search we did.
750 * Copy one list to another. If the destination list is longer than the
751 * source list, the remaining elements are unaffected. This method runs in
754 * @param dest the destination list
755 * @param source the source list
756 * @throws IndexOutOfBoundsException if the destination list is shorter
757 * than the source list (the destination will be unmodified)
758 * @throws UnsupportedOperationException if dest.listIterator() does not
759 * support the set operation
761 public static <T> void copy(List<? super T> dest, List<? extends T> source)
763 int pos = source.size();
764 if (dest.size() < pos)
765 throw new IndexOutOfBoundsException("Source does not fit in dest");
767 Iterator<? extends T> i1 = source.iterator();
768 ListIterator<? super T> i2 = dest.listIterator();
778 * Returns an Enumeration over a collection. This allows interoperability
779 * with legacy APIs that require an Enumeration as input.
781 * @param c the Collection to iterate over
782 * @return an Enumeration backed by an Iterator over c
784 public static <T> Enumeration<T> enumeration(Collection<T> c)
786 final Iterator<T> i = c.iterator();
787 return new Enumeration<T>()
790 * Returns <code>true</code> if there are more elements to
793 * @return The result of <code>hasNext()</code>
794 * called on the underlying iterator.
796 public final boolean hasMoreElements()
802 * Returns the next element to be enumerated.
804 * @return The result of <code>next()</code>
805 * called on the underlying iterator.
807 public final T nextElement()
815 * Replace every element of a list with a given value. This method runs in
818 * @param l the list to fill.
819 * @param val the object to vill the list with.
820 * @throws UnsupportedOperationException if l.listIterator() does not
821 * support the set operation.
823 public static <T> void fill(List<? super T> l, T val)
825 ListIterator<? super T> itr = l.listIterator();
826 for (int i = l.size() - 1; i >= 0; --i)
834 * Returns the starting index where the specified sublist first occurs
835 * in a larger list, or -1 if there is no matching position. If
836 * <code>target.size() > source.size()</code>, this returns -1,
837 * otherwise this implementation uses brute force, checking for
838 * <code>source.sublist(i, i + target.size()).equals(target)</code>
839 * for all possible i.
841 * @param source the list to search
842 * @param target the sublist to search for
843 * @return the index where found, or -1
846 public static int indexOfSubList(List<?> source, List<?> target)
848 int ssize = source.size();
849 for (int i = 0, j = target.size(); j <= ssize; i++, j++)
850 if (source.subList(i, j).equals(target))
856 * Returns the starting index where the specified sublist last occurs
857 * in a larger list, or -1 if there is no matching position. If
858 * <code>target.size() > source.size()</code>, this returns -1,
859 * otherwise this implementation uses brute force, checking for
860 * <code>source.sublist(i, i + target.size()).equals(target)</code>
861 * for all possible i.
863 * @param source the list to search
864 * @param target the sublist to search for
865 * @return the index where found, or -1
868 public static int lastIndexOfSubList(List<?> source, List<?> target)
870 int ssize = source.size();
871 for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--)
872 if (source.subList(i, j).equals(target))
878 * Returns an ArrayList holding the elements visited by a given
879 * Enumeration. This method exists for interoperability between legacy
880 * APIs and the new Collection API.
882 * @param e the enumeration to put in a list
883 * @return a list containing the enumeration elements
887 public static <T> ArrayList<T> list(Enumeration<T> e)
889 ArrayList<T> l = new ArrayList<T>();
890 while (e.hasMoreElements())
891 l.add(e.nextElement());
896 * Find the maximum element in a Collection, according to the natural
897 * ordering of the elements. This implementation iterates over the
898 * Collection, so it works in linear time.
900 * @param c the Collection to find the maximum element of
901 * @return the maximum element of c
902 * @exception NoSuchElementException if c is empty
903 * @exception ClassCastException if elements in c are not mutually comparable
904 * @exception NullPointerException if null.compareTo is called
906 public static <T extends Object & Comparable<? super T>>
907 T max(Collection<? extends T> c)
913 * Find the maximum element in a Collection, according to a specified
914 * Comparator. This implementation iterates over the Collection, so it
915 * works in linear time.
917 * @param c the Collection to find the maximum element of
918 * @param order the Comparator to order the elements by, or null for natural
920 * @return the maximum element of c
921 * @throws NoSuchElementException if c is empty
922 * @throws ClassCastException if elements in c are not mutually comparable
923 * @throws NullPointerException if null is compared by natural ordering
924 * (only possible when order is null)
926 public static <T> T max(Collection<? extends T> c,
927 Comparator<? super T> order)
929 Iterator<? extends T> itr = c.iterator();
930 T max = itr.next(); // throws NoSuchElementException
931 int csize = c.size();
932 for (int i = 1; i < csize; i++)
935 if (compare(max, o, order) < 0)
942 * Find the minimum element in a Collection, according to the natural
943 * ordering of the elements. This implementation iterates over the
944 * Collection, so it works in linear time.
946 * @param c the Collection to find the minimum element of
947 * @return the minimum element of c
948 * @throws NoSuchElementException if c is empty
949 * @throws ClassCastException if elements in c are not mutually comparable
950 * @throws NullPointerException if null.compareTo is called
952 public static <T extends Object & Comparable<? super T>>
953 T min(Collection<? extends T> c)
959 * Find the minimum element in a Collection, according to a specified
960 * Comparator. This implementation iterates over the Collection, so it
961 * works in linear time.
963 * @param c the Collection to find the minimum element of
964 * @param order the Comparator to order the elements by, or null for natural
966 * @return the minimum element of c
967 * @throws NoSuchElementException if c is empty
968 * @throws ClassCastException if elements in c are not mutually comparable
969 * @throws NullPointerException if null is compared by natural ordering
970 * (only possible when order is null)
972 public static <T> T min(Collection<? extends T> c,
973 Comparator<? super T> order)
975 Iterator<? extends T> itr = c.iterator();
976 T min = itr.next(); // throws NoSuchElementExcception
977 int csize = c.size();
978 for (int i = 1; i < csize; i++)
981 if (compare(min, o, order) > 0)
988 * Creates an immutable list consisting of the same object repeated n times.
989 * The returned object is tiny, consisting of only a single reference to the
990 * object and a count of the number of elements. It is Serializable, and
991 * implements RandomAccess. You can use it in tandem with List.addAll for
992 * fast list construction.
994 * @param n the number of times to repeat the object
995 * @param o the object to repeat
996 * @return a List consisting of n copies of o
997 * @throws IllegalArgumentException if n < 0
998 * @see List#addAll(Collection)
1002 public static <T> List<T> nCopies(final int n, final T o)
1004 return new CopiesList<T>(n, o);
1008 * The implementation of {@link #nCopies(int, Object)}. This class name
1009 * is required for compatibility with Sun's JDK serializability.
1011 * @author Eric Blake (ebb9@email.byu.edu)
1013 private static final class CopiesList<T> extends AbstractList<T>
1014 implements Serializable, RandomAccess
1017 * Compatible with JDK 1.4.
1019 private static final long serialVersionUID = 2739099268398711800L;
1022 * The count of elements in this list.
1023 * @serial the list size
1025 private final int n;
1028 * The repeated list element.
1029 * @serial the list contents
1031 private final T element;
1034 * Constructs the list.
1036 * @param n the count
1037 * @param o the object
1038 * @throws IllegalArgumentException if n < 0
1040 CopiesList(int n, T o)
1043 throw new IllegalArgumentException();
1049 * The size is fixed.
1050 * @return The size of the list.
1058 * The same element is returned.
1059 * @param index The index of the element to be returned (irrelevant
1060 * as the list contains only copies of <code>element</code>).
1061 * @return The element used by this list.
1063 public T get(int index)
1065 if (index < 0 || index >= n)
1066 throw new IndexOutOfBoundsException();
1070 // The remaining methods are optional, but provide a performance
1071 // advantage by not allocating unnecessary iterators in AbstractList.
1073 * This list only contains one element.
1074 * @param o The object to search for.
1075 * @return <code>true</code> if o is the element used by this list.
1077 public boolean contains(Object o)
1079 return n > 0 && equals(o, element);
1083 * The index is either 0 or -1.
1084 * @param o The object to find the index of.
1085 * @return 0 if <code>o == element</code>, -1 if not.
1087 public int indexOf(Object o)
1089 return (n > 0 && equals(o, element)) ? 0 : -1;
1093 * The index is either n-1 or -1.
1094 * @param o The object to find the last index of.
1095 * @return The last index in the list if <code>o == element</code>,
1098 public int lastIndexOf(Object o)
1100 return equals(o, element) ? n - 1 : -1;
1104 * A subList is just another CopiesList.
1105 * @param from The starting bound of the sublist.
1106 * @param to The ending bound of the sublist.
1107 * @return A list of copies containing <code>from - to</code>
1108 * elements, all of which are equal to the element
1109 * used by this list.
1111 public List<T> subList(int from, int to)
1113 if (from < 0 || to > n)
1114 throw new IndexOutOfBoundsException();
1115 return new CopiesList<T>(to - from, element);
1119 * The array is easy.
1120 * @return An array of size n filled with copies of
1121 * the element used by this list.
1123 public Object[] toArray()
1125 Object[] a = new Object[n];
1126 Arrays.fill(a, element);
1131 * The string is easy to generate.
1132 * @return A string representation of the list.
1134 public String toString()
1136 StringBuffer r = new StringBuffer("{");
1137 for (int i = n - 1; --i > 0; )
1138 r.append(element).append(", ");
1139 r.append(element).append("}");
1140 return r.toString();
1142 } // class CopiesList
1145 * Replace all instances of one object with another in the specified list.
1146 * The list does not change size. An element e is replaced if
1147 * <code>oldval == null ? e == null : oldval.equals(e)</code>.
1149 * @param list the list to iterate over
1150 * @param oldval the element to replace
1151 * @param newval the new value for the element
1152 * @return <code>true</code> if a replacement occurred.
1153 * @throws UnsupportedOperationException if the list iterator does not allow
1154 * for the set operation
1155 * @throws ClassCastException if newval is of a type which cannot be added
1157 * @throws IllegalArgumentException if some other aspect of newval stops
1158 * it being added to the list
1161 public static <T> boolean replaceAll(List<T> list, T oldval, T newval)
1163 ListIterator<T> itr = list.listIterator();
1164 boolean replace_occured = false;
1165 for (int i = list.size(); --i >= 0; )
1166 if (AbstractCollection.equals(oldval, itr.next()))
1169 replace_occured = true;
1171 return replace_occured;
1175 * Reverse a given list. This method works in linear time.
1177 * @param l the list to reverse
1178 * @throws UnsupportedOperationException if l.listIterator() does not
1179 * support the set operation
1181 public static void reverse(List<?> l)
1183 ListIterator i1 = l.listIterator();
1185 int pos2 = l.size();
1186 ListIterator i2 = l.listIterator(pos2);
1189 Object o1 = i1.next();
1190 Object o2 = i2.previous();
1199 * Get a comparator that implements the reverse of the ordering
1200 * specified by the given Comparator. If the Comparator is null,
1201 * this is equivalent to {@link #reverseOrder()}. The return value
1202 * of this method is Serializable, if the specified Comparator is
1203 * either Serializable or null.
1205 * @param c the comparator to invert
1206 * @return a comparator that imposes reverse ordering
1212 public static <T> Comparator<T> reverseOrder(final Comparator<T> c)
1215 return (Comparator<T>) rcInstance;
1216 return new ReverseComparator<T> ()
1218 public int compare(T a, T b)
1220 return - c.compare(a, b);
1226 * Get a comparator that implements the reverse of natural ordering. In
1227 * other words, this sorts Comparable objects opposite of how their
1228 * compareTo method would sort. This makes it easy to sort into reverse
1229 * order, by simply passing Collections.reverseOrder() to the sort method.
1230 * The return value of this method is Serializable.
1232 * @return a comparator that imposes reverse natural ordering
1236 public static <T> Comparator<T> reverseOrder()
1238 return (Comparator<T>) rcInstance;
1242 * The object for {@link #reverseOrder()}.
1244 private static final ReverseComparator rcInstance = new ReverseComparator();
1247 * The implementation of {@link #reverseOrder()}. This class name
1248 * is required for compatibility with Sun's JDK serializability.
1250 * @author Eric Blake (ebb9@email.byu.edu)
1252 private static class ReverseComparator<T>
1253 implements Comparator<T>, Serializable
1256 * Compatible with JDK 1.4.
1258 private static final long serialVersionUID = 7207038068494060240L;
1261 * A private constructor adds overhead.
1268 * Compare two objects in reverse natural order.
1270 * @param a the first object
1271 * @param b the second object
1272 * @return <, ==, or > 0 according to b.compareTo(a)
1274 public int compare(T a, T b)
1276 return ((Comparable) b).compareTo(a);
1281 * Rotate the elements in a list by a specified distance. After calling this
1282 * method, the element now at index <code>i</code> was formerly at index
1283 * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
1286 * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
1287 * either <code>Collections.rotate(l, 4)</code> or
1288 * <code>Collections.rotate(l, -1)</code>, the new contents are
1289 * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
1290 * just a portion of the list. For example, to move element <code>a</code>
1291 * forward two positions in the original example, use
1292 * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
1293 * result in <code>[t, n, k, a, s]</code>.
1296 * If the list is small or implements {@link RandomAccess}, the
1297 * implementation exchanges the first element to its destination, then the
1298 * displaced element, and so on until a circuit has been completed. The
1299 * process is repeated if needed on the second element, and so forth, until
1300 * all elements have been swapped. For large non-random lists, the
1301 * implementation breaks the list into two sublists at index
1302 * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
1303 * pieces, then reverses the overall list.
1305 * @param list the list to rotate
1306 * @param distance the distance to rotate by; unrestricted in value
1307 * @throws UnsupportedOperationException if the list does not support set
1310 public static void rotate(List<?> list, int distance)
1312 int size = list.size();
1321 if (isSequential(list))
1324 reverse(list.subList(0, distance));
1325 reverse(list.subList(distance, size));
1329 // Determine the least common multiple of distance and size, as there
1330 // are (distance / LCM) loops to cycle through.
1341 // Now, make the swaps. We must take the remainder every time through
1342 // the inner loop so that we don't overflow i to negative values.
1343 List<Object> objList = (List<Object>) list;
1346 Object o = objList.get(lcm);
1347 for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
1348 o = objList.set(i, o);
1349 objList.set(lcm, o);
1355 * Shuffle a list according to a default source of randomness. The algorithm
1356 * used iterates backwards over the list, swapping each element with an
1357 * element randomly selected from the elements in positions less than or
1358 * equal to it (using r.nextInt(int)).
1361 * This algorithm would result in a perfectly fair shuffle (that is, each
1362 * element would have an equal chance of ending up in any position) if r were
1363 * a perfect source of randomness. In practice the results are merely very
1367 * This method operates in linear time. To do this on large lists which do
1368 * not implement {@link RandomAccess}, a temporary array is used to acheive
1369 * this speed, since it would be quadratic access otherwise.
1371 * @param l the list to shuffle
1372 * @throws UnsupportedOperationException if l.listIterator() does not
1373 * support the set operation
1375 public static void shuffle(List<?> l)
1377 if (defaultRandom == null)
1379 synchronized (Collections.class)
1381 if (defaultRandom == null)
1382 defaultRandom = new Random();
1385 shuffle(l, defaultRandom);
1389 * Cache a single Random object for use by shuffle(List). This improves
1390 * performance as well as ensuring that sequential calls to shuffle() will
1391 * not result in the same shuffle order occurring: the resolution of
1392 * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
1394 private static Random defaultRandom = null;
1397 * Shuffle a list according to a given source of randomness. The algorithm
1398 * used iterates backwards over the list, swapping each element with an
1399 * element randomly selected from the elements in positions less than or
1400 * equal to it (using r.nextInt(int)).
1403 * This algorithm would result in a perfectly fair shuffle (that is, each
1404 * element would have an equal chance of ending up in any position) if r were
1405 * a perfect source of randomness. In practise (eg if r = new Random()) the
1406 * results are merely very close to perfect.
1409 * This method operates in linear time. To do this on large lists which do
1410 * not implement {@link RandomAccess}, a temporary array is used to acheive
1411 * this speed, since it would be quadratic access otherwise.
1413 * @param l the list to shuffle
1414 * @param r the source of randomness to use for the shuffle
1415 * @throws UnsupportedOperationException if l.listIterator() does not
1416 * support the set operation
1418 public static void shuffle(List<?> l, Random r)
1420 int lsize = l.size();
1421 List<Object> list = (List<Object>) l;
1422 ListIterator<Object> i = list.listIterator(lsize);
1423 boolean sequential = isSequential(l);
1424 Object[] a = null; // stores a copy of the list for the sequential case
1429 for (int pos = lsize - 1; pos > 0; --pos)
1431 // Obtain a random position to swap with. pos + 1 is used so that the
1432 // range of the random number includes the current position.
1433 int swap = r.nextInt(pos + 1);
1435 // Swap the desired element.
1440 a[swap] = i.previous();
1443 o = list.set(swap, i.previous());
1450 * Returns the frequency of the specified object within the supplied
1451 * collection. The frequency represents the number of occurrences of
1452 * elements within the collection which return <code>true</code> when
1453 * compared with the object using the <code>equals</code> method.
1455 * @param c the collection to scan for occurrences of the object.
1456 * @param o the object to locate occurrances of within the collection.
1457 * @throws NullPointerException if the collection is <code>null</code>.
1460 public static int frequency (Collection<?> c, Object o)
1465 if (AbstractCollection.equals(o, v))
1472 * Adds all the specified elements to the given collection, in a similar
1473 * way to the <code>addAll</code> method of the <code>Collection</code>.
1474 * However, this is a variable argument method which allows the new elements
1475 * to be specified individually or in array form, as opposed to the list
1476 * required by the collection's <code>addAll</code> method. This has
1477 * benefits in both simplicity (multiple elements can be added without
1478 * having to be wrapped inside a grouping structure) and efficiency
1479 * (as a redundant list doesn't have to be created to add an individual
1480 * set of elements or an array).
1482 * @param c the collection to which the elements should be added.
1483 * @param a the elements to be added to the collection.
1484 * @return true if the collection changed its contents as a result.
1485 * @throws UnsupportedOperationException if the collection does not support
1487 * @throws NullPointerException if one or more elements in a are null,
1488 * and the collection does not allow null
1489 * elements. This exception is also thrown
1490 * if either <code>c</code> or <code>a</code>
1492 * @throws IllegalArgumentException if the collection won't allow an element
1493 * to be added for some other reason.
1496 public static <T> boolean addAll(Collection<? super T> c, T... a)
1498 boolean overall = false;
1502 boolean result = c.add(element);
1510 * Returns true if the two specified collections have no elements in
1511 * common. This method may give unusual results if one or both collections
1512 * use a non-standard equality test. In the trivial case of comparing
1513 * a collection with itself, this method returns true if, and only if,
1514 * the collection is empty.
1516 * @param c1 the first collection to compare.
1517 * @param c2 the second collection to compare.
1518 * @return true if the collections are disjoint.
1519 * @throws NullPointerException if either collection is null.
1522 public static boolean disjoint(Collection<?> c1, Collection<?> c2)
1524 Collection<Object> oc1 = (Collection<Object>) c1;
1525 for (Object o : oc1)
1533 * Obtain an immutable Set consisting of a single element. The return value
1534 * of this method is Serializable.
1536 * @param o the single element
1537 * @return an immutable Set containing only o
1540 public static <T> Set<T> singleton(T o)
1542 return new SingletonSet<T>(o);
1546 * The implementation of {@link #singleton(Object)}. This class name
1547 * is required for compatibility with Sun's JDK serializability.
1549 * @author Eric Blake (ebb9@email.byu.edu)
1551 private static final class SingletonSet<T> extends AbstractSet<T>
1552 implements Serializable
1555 * Compatible with JDK 1.4.
1557 private static final long serialVersionUID = 3193687207550431679L;
1561 * The single element; package visible for use in nested class.
1562 * @serial the singleton
1567 * Construct a singleton.
1568 * @param o the element
1576 * The size: always 1!
1585 * Returns an iterator over the lone element.
1587 public Iterator<T> iterator()
1589 return new Iterator<T>()
1592 * Flag to indicate whether or not the element has
1595 private boolean hasNext = true;
1598 * Returns <code>true</code> if elements still remain to be
1601 * @return <code>true</code> if the element has not yet been returned.
1603 public boolean hasNext()
1609 * Returns the element.
1611 * @return The element used by this singleton.
1612 * @throws NoSuchElementException if the object
1613 * has already been retrieved.
1623 throw new NoSuchElementException();
1627 * Removes the element from the singleton.
1628 * As this set is immutable, this will always
1629 * throw an exception.
1631 * @throws UnsupportedOperationException as the
1632 * singleton set doesn't support
1633 * <code>remove()</code>.
1635 public void remove()
1637 throw new UnsupportedOperationException();
1642 // The remaining methods are optional, but provide a performance
1643 // advantage by not allocating unnecessary iterators in AbstractSet.
1645 * The set only contains one element.
1647 * @param o The object to search for.
1648 * @return <code>true</code> if o == the element of the singleton.
1650 public boolean contains(Object o)
1652 return equals(o, element);
1656 * This is true if the other collection only contains the element.
1658 * @param c A collection to compare against this singleton.
1659 * @return <code>true</code> if c only contains either no elements or
1660 * elements equal to the element in this singleton.
1662 public boolean containsAll(Collection<?> c)
1664 Iterator<?> i = c.iterator();
1667 if (! equals(i.next(), element))
1673 * The hash is just that of the element.
1675 * @return The hashcode of the element.
1677 public int hashCode()
1679 return hashCode(element);
1683 * Returning an array is simple.
1685 * @return An array containing the element.
1687 public Object[] toArray()
1689 return new Object[] {element};
1695 * @return The string surrounded by enclosing
1698 public String toString()
1700 return "[" + element + "]";
1702 } // class SingletonSet
1705 * Obtain an immutable List consisting of a single element. The return value
1706 * of this method is Serializable, and implements RandomAccess.
1708 * @param o the single element
1709 * @return an immutable List containing only o
1714 public static <T> List<T> singletonList(T o)
1716 return new SingletonList<T>(o);
1720 * The implementation of {@link #singletonList(Object)}. This class name
1721 * is required for compatibility with Sun's JDK serializability.
1723 * @author Eric Blake (ebb9@email.byu.edu)
1725 private static final class SingletonList<T> extends AbstractList<T>
1726 implements Serializable, RandomAccess
1729 * Compatible with JDK 1.4.
1731 private static final long serialVersionUID = 3093736618740652951L;
1734 * The single element.
1735 * @serial the singleton
1737 private final T element;
1740 * Construct a singleton.
1741 * @param o the element
1749 * The size: always 1!
1758 * Only index 0 is valid.
1759 * @param index The index of the element
1761 * @return The singleton's element if the
1763 * @throws IndexOutOfBoundsException if
1766 public T get(int index)
1770 throw new IndexOutOfBoundsException();
1773 // The remaining methods are optional, but provide a performance
1774 // advantage by not allocating unnecessary iterators in AbstractList.
1776 * The set only contains one element.
1778 * @param o The object to search for.
1779 * @return <code>true</code> if o == the singleton element.
1781 public boolean contains(Object o)
1783 return equals(o, element);
1787 * This is true if the other collection only contains the element.
1789 * @param c A collection to compare against this singleton.
1790 * @return <code>true</code> if c only contains either no elements or
1791 * elements equal to the element in this singleton.
1793 public boolean containsAll(Collection<?> c)
1795 Iterator<?> i = c.iterator();
1798 if (! equals(i.next(), element))
1804 * Speed up the hashcode computation.
1806 * @return The hashcode of the list, based
1807 * on the hashcode of the singleton element.
1809 public int hashCode()
1811 return 31 + hashCode(element);
1815 * Either the list has it or not.
1817 * @param o The object to find the first index of.
1818 * @return 0 if o is the singleton element, -1 if not.
1820 public int indexOf(Object o)
1822 return equals(o, element) ? 0 : -1;
1826 * Either the list has it or not.
1828 * @param o The object to find the last index of.
1829 * @return 0 if o is the singleton element, -1 if not.
1831 public int lastIndexOf(Object o)
1833 return equals(o, element) ? 0 : -1;
1837 * Sublists are limited in scope.
1839 * @param from The starting bound for the sublist.
1840 * @param to The ending bound for the sublist.
1841 * @return Either an empty list if both bounds are
1842 * 0 or 1, or this list if the bounds are 0 and 1.
1843 * @throws IllegalArgumentException if <code>from > to</code>
1844 * @throws IndexOutOfBoundsException if either bound is greater
1847 public List<T> subList(int from, int to)
1849 if (from == to && (to == 0 || to == 1))
1851 if (from == 0 && to == 1)
1854 throw new IllegalArgumentException();
1855 throw new IndexOutOfBoundsException();
1859 * Returning an array is simple.
1861 * @return An array containing the element.
1863 public Object[] toArray()
1865 return new Object[] {element};
1871 * @return The string surrounded by enclosing
1874 public String toString()
1876 return "[" + element + "]";
1878 } // class SingletonList
1881 * Obtain an immutable Map consisting of a single key-value pair.
1882 * The return value of this method is Serializable.
1884 * @param key the single key
1885 * @param value the single value
1886 * @return an immutable Map containing only the single key-value pair
1890 public static <K, V> Map<K, V> singletonMap(K key, V value)
1892 return new SingletonMap<K, V>(key, value);
1896 * The implementation of {@link #singletonMap(Object, Object)}. This class
1897 * name is required for compatibility with Sun's JDK serializability.
1899 * @author Eric Blake (ebb9@email.byu.edu)
1901 private static final class SingletonMap<K, V> extends AbstractMap<K, V>
1902 implements Serializable
1905 * Compatible with JDK 1.4.
1907 private static final long serialVersionUID = -6979724477215052911L;
1911 * @serial the singleton key
1916 * The corresponding value.
1917 * @serial the singleton value
1922 * Cache the entry set.
1924 private transient Set<Map.Entry<K, V>> entries;
1927 * Construct a singleton.
1928 * @param key the key
1929 * @param value the value
1931 SingletonMap(K key, V value)
1938 * There is a single immutable entry.
1940 * @return A singleton containing the map entry.
1942 public Set<Map.Entry<K, V>> entrySet()
1944 if (entries == null)
1946 Map.Entry<K,V> entry = new AbstractMap.SimpleEntry<K, V>(k, v)
1949 * Sets the value of the map entry to the supplied value.
1950 * An exception is always thrown, as the map is immutable.
1952 * @param o The new value.
1953 * @return The old value.
1954 * @throws UnsupportedOperationException as setting the value
1957 public V setValue(V o)
1959 throw new UnsupportedOperationException();
1962 entries = singleton(entry);
1967 // The remaining methods are optional, but provide a performance
1968 // advantage by not allocating unnecessary iterators in AbstractMap.
1972 * @param key The key to look for.
1973 * @return <code>true</code> if the key is the same as the one used by
1976 public boolean containsKey(Object key)
1978 return equals(key, k);
1984 * @param value The value to look for.
1985 * @return <code>true</code> if the value is the same as the one used by
1988 public boolean containsValue(Object value)
1990 return equals(value, v);
1996 * @param key The key of the value to be retrieved.
1997 * @return The singleton value if the key is the same as the
1998 * singleton key, null otherwise.
2000 public V get(Object key)
2002 return equals(key, k) ? v : null;
2006 * Calculate the hashcode directly.
2008 * @return The hashcode computed from the singleton key
2009 * and the singleton value.
2011 public int hashCode()
2013 return hashCode(k) ^ hashCode(v);
2017 * Return the keyset.
2019 * @return A singleton containing the key.
2021 public Set<K> keySet()
2024 keys = singleton(k);
2029 * The size: always 1!
2039 * Return the values. Technically, a singleton, while more specific than
2040 * a general Collection, will work. Besides, that's what the JDK uses!
2042 * @return A singleton containing the value.
2044 public Collection<V> values()
2047 values = singleton(v);
2054 * @return A string containing the string representations of the key
2055 * and its associated value.
2057 public String toString()
2059 return "{" + k + "=" + v + "}";
2061 } // class SingletonMap
2064 * Sort a list according to the natural ordering of its elements. The list
2065 * must be modifiable, but can be of fixed size. The sort algorithm is
2066 * precisely that used by Arrays.sort(Object[]), which offers guaranteed
2067 * nlog(n) performance. This implementation dumps the list into an array,
2068 * sorts the array, and then iterates over the list setting each element from
2071 * @param l the List to sort (<code>null</code> not permitted)
2072 * @throws ClassCastException if some items are not mutually comparable
2073 * @throws UnsupportedOperationException if the List is not modifiable
2074 * @throws NullPointerException if the list is <code>null</code>, or contains
2075 * some element that is <code>null</code>.
2076 * @see Arrays#sort(Object[])
2078 public static <T extends Comparable<? super T>> void sort(List<T> l)
2084 * Sort a list according to a specified Comparator. The list must be
2085 * modifiable, but can be of fixed size. The sort algorithm is precisely that
2086 * used by Arrays.sort(Object[], Comparator), which offers guaranteed
2087 * nlog(n) performance. This implementation dumps the list into an array,
2088 * sorts the array, and then iterates over the list setting each element from
2091 * @param l the List to sort (<code>null</code> not permitted)
2092 * @param c the Comparator specifying the ordering for the elements, or
2093 * <code>null</code> for natural ordering
2094 * @throws ClassCastException if c will not compare some pair of items
2095 * @throws UnsupportedOperationException if the List is not modifiable
2096 * @throws NullPointerException if the List is <code>null</code> or
2097 * <code>null</code> is compared by natural ordering (only possible
2098 * when c is <code>null</code>)
2100 * @see Arrays#sort(Object[], Comparator)
2102 public static <T> void sort(List<T> l, Comparator<? super T> c)
2104 T[] a = (T[]) l.toArray();
2106 ListIterator<T> i = l.listIterator();
2107 for (int pos = 0, alen = a.length; pos < alen; pos++)
2115 * Swaps the elements at the specified positions within the list. Equal
2116 * positions have no effect.
2118 * @param l the list to work on
2119 * @param i the first index to swap
2120 * @param j the second index
2121 * @throws UnsupportedOperationException if list.set is not supported
2122 * @throws IndexOutOfBoundsException if either i or j is < 0 or >=
2126 public static void swap(List<?> l, int i, int j)
2128 List<Object> list = (List<Object>) l;
2129 list.set(i, list.set(j, list.get(i)));
2134 * Returns a synchronized (thread-safe) collection wrapper backed by the
2135 * given collection. Notice that element access through the iterators
2136 * is thread-safe, but if the collection can be structurally modified
2137 * (adding or removing elements) then you should synchronize around the
2138 * iteration to avoid non-deterministic behavior:<br>
2140 * Collection c = Collections.synchronizedCollection(new Collection(...));
2144 * Iterator i = c.iterator();
2145 * while (i.hasNext())
2150 * Since the collection might be a List or a Set, and those have incompatible
2151 * equals and hashCode requirements, this relies on Object's implementation
2152 * rather than passing those calls on to the wrapped collection. The returned
2153 * Collection implements Serializable, but can only be serialized if
2154 * the collection it wraps is likewise Serializable.
2156 * @param c the collection to wrap
2157 * @return a synchronized view of the collection
2160 public static <T> Collection<T> synchronizedCollection(Collection<T> c)
2162 return new SynchronizedCollection<T>(c);
2166 * The implementation of {@link #synchronizedCollection(Collection)}. This
2167 * class name is required for compatibility with Sun's JDK serializability.
2168 * Package visible, so that collections such as the one for
2169 * Hashtable.values() can specify which object to synchronize on.
2171 * @author Eric Blake (ebb9@email.byu.edu)
2173 static class SynchronizedCollection<T>
2174 implements Collection<T>, Serializable
2177 * Compatible with JDK 1.4.
2179 private static final long serialVersionUID = 3053995032091335093L;
2182 * The wrapped collection. Package visible for use by subclasses.
2183 * @serial the real collection
2185 final Collection<T> c;
2188 * The object to synchronize on. When an instance is created via public
2189 * methods, it will be this; but other uses like SynchronizedMap.values()
2190 * must specify another mutex. Package visible for use by subclasses.
2196 * Wrap a given collection.
2197 * @param c the collection to wrap
2198 * @throws NullPointerException if c is null
2200 SynchronizedCollection(Collection<T> c)
2205 throw new NullPointerException();
2209 * Called only by trusted code to specify the mutex as well as the
2211 * @param sync the mutex
2212 * @param c the collection
2214 SynchronizedCollection(Object sync, Collection<T> c)
2221 * Adds the object to the underlying collection, first
2222 * obtaining a lock on the mutex.
2224 * @param o The object to add.
2225 * @return <code>true</code> if the collection was modified as a result
2227 * @throws UnsupportedOperationException if this collection does not
2228 * support the add operation.
2229 * @throws ClassCastException if o cannot be added to this collection due
2231 * @throws NullPointerException if o is null and this collection doesn't
2232 * support the addition of null values.
2233 * @throws IllegalArgumentException if o cannot be added to this
2234 * collection for some other reason.
2236 public boolean add(T o)
2238 synchronized (mutex)
2245 * Adds the objects in col to the underlying collection, first
2246 * obtaining a lock on the mutex.
2248 * @param col The collection to take the new objects from.
2249 * @return <code>true</code> if the collection was modified as a result
2251 * @throws UnsupportedOperationException if this collection does not
2252 * support the addAll operation.
2253 * @throws ClassCastException if some element of col cannot be added to this
2254 * collection due to its type.
2255 * @throws NullPointerException if some element of col is null and this
2256 * collection does not support the addition of null values.
2257 * @throws NullPointerException if col itself is null.
2258 * @throws IllegalArgumentException if some element of col cannot be added
2259 * to this collection for some other reason.
2261 public boolean addAll(Collection<? extends T> col)
2263 synchronized (mutex)
2265 return c.addAll(col);
2270 * Removes all objects from the underlying collection,
2271 * first obtaining a lock on the mutex.
2273 * @throws UnsupportedOperationException if this collection does not
2274 * support the clear operation.
2278 synchronized (mutex)
2285 * Checks for the existence of o within the underlying
2286 * collection, first obtaining a lock on the mutex.
2288 * @param o the element to look for.
2289 * @return <code>true</code> if this collection contains at least one
2290 * element e such that <code>o == null ? e == null : o.equals(e)</code>.
2291 * @throws ClassCastException if the type of o is not a valid type for this
2293 * @throws NullPointerException if o is null and this collection doesn't
2294 * support null values.
2296 public boolean contains(Object o)
2298 synchronized (mutex)
2300 return c.contains(o);
2305 * Checks for the existence of each object in cl
2306 * within the underlying collection, first obtaining
2307 * a lock on the mutex.
2309 * @param c1 the collection to test for.
2310 * @return <code>true</code> if for every element o in c, contains(o)
2311 * would return <code>true</code>.
2312 * @throws ClassCastException if the type of any element in cl is not a valid
2313 * type for this collection.
2314 * @throws NullPointerException if some element of cl is null and this
2315 * collection does not support null values.
2316 * @throws NullPointerException if cl itself is null.
2318 public boolean containsAll(Collection<?> c1)
2320 synchronized (mutex)
2322 return c.containsAll(c1);
2327 * Returns <code>true</code> if there are no objects in the underlying
2328 * collection. A lock on the mutex is obtained before the
2329 * check is performed.
2331 * @return <code>true</code> if this collection contains no elements.
2333 public boolean isEmpty()
2335 synchronized (mutex)
2342 * Returns a synchronized iterator wrapper around the underlying
2343 * collection's iterator. A lock on the mutex is obtained before
2344 * retrieving the collection's iterator.
2346 * @return An iterator over the elements in the underlying collection,
2347 * which returns each element in any order.
2349 public Iterator<T> iterator()
2351 synchronized (mutex)
2353 return new SynchronizedIterator<T>(mutex, c.iterator());
2358 * Removes the specified object from the underlying collection,
2359 * first obtaining a lock on the mutex.
2361 * @param o The object to remove.
2362 * @return <code>true</code> if the collection changed as a result of this call, that is,
2363 * if the collection contained at least one occurrence of o.
2364 * @throws UnsupportedOperationException if this collection does not
2365 * support the remove operation.
2366 * @throws ClassCastException if the type of o is not a valid type
2367 * for this collection.
2368 * @throws NullPointerException if o is null and the collection doesn't
2369 * support null values.
2371 public boolean remove(Object o)
2373 synchronized (mutex)
2380 * Removes all elements, e, of the underlying
2381 * collection for which <code>col.contains(e)</code>
2382 * returns <code>true</code>. A lock on the mutex is obtained
2383 * before the operation proceeds.
2385 * @param col The collection of objects to be removed.
2386 * @return <code>true</code> if this collection was modified as a result of this call.
2387 * @throws UnsupportedOperationException if this collection does not
2388 * support the removeAll operation.
2389 * @throws ClassCastException if the type of any element in c is not a valid
2390 * type for this collection.
2391 * @throws NullPointerException if some element of c is null and this
2392 * collection does not support removing null values.
2393 * @throws NullPointerException if c itself is null.
2395 public boolean removeAll(Collection<?> col)
2397 synchronized (mutex)
2399 return c.removeAll(col);
2404 * Retains all elements, e, of the underlying
2405 * collection for which <code>col.contains(e)</code>
2406 * returns <code>true</code>. That is, every element that doesn't
2407 * exist in col is removed. A lock on the mutex is obtained
2408 * before the operation proceeds.
2410 * @param col The collection of objects to be removed.
2411 * @return <code>true</code> if this collection was modified as a result of this call.
2412 * @throws UnsupportedOperationException if this collection does not
2413 * support the removeAll operation.
2414 * @throws ClassCastException if the type of any element in c is not a valid
2415 * type for this collection.
2416 * @throws NullPointerException if some element of c is null and this
2417 * collection does not support removing null values.
2418 * @throws NullPointerException if c itself is null.
2420 public boolean retainAll(Collection<?> col)
2422 synchronized (mutex)
2424 return c.retainAll(col);
2429 * Retrieves the size of the underlying collection.
2430 * A lock on the mutex is obtained before the collection
2433 * @return The size of the collection.
2437 synchronized (mutex)
2444 * Returns an array containing each object within the underlying
2445 * collection. A lock is obtained on the mutex before the collection
2448 * @return An array of objects, matching the collection in size. The
2449 * elements occur in any order.
2451 public Object[] toArray()
2453 synchronized (mutex)
2460 * Copies the elements in the underlying collection to the supplied
2461 * array. If <code>a.length < size()</code>, a new array of the
2462 * same run-time type is created, with a size equal to that of
2463 * the collection. If <code>a.length > size()</code>, then the
2464 * elements from 0 to <code>size() - 1</code> contain the elements
2465 * from this collection. The following element is set to null
2466 * to indicate the end of the collection objects. However, this
2467 * only makes a difference if null is not a permitted value within
2469 * Before the copying takes place, a lock is obtained on the mutex.
2471 * @param a An array to copy elements to.
2472 * @return An array containing the elements of the underlying collection.
2473 * @throws ArrayStoreException if the type of any element of the
2474 * collection is not a subtype of the element type of a.
2476 public <T> T[] toArray(T[] a)
2478 synchronized (mutex)
2480 return c.toArray(a);
2485 * Returns a string representation of the underlying collection.
2486 * A lock is obtained on the mutex before the string is created.
2488 * @return A string representation of the collection.
2490 public String toString()
2492 synchronized (mutex)
2494 return c.toString();
2497 } // class SynchronizedCollection
2500 * The implementation of the various iterator methods in the
2501 * synchronized classes. These iterators must "sync" on the same object
2502 * as the collection they iterate over.
2504 * @author Eric Blake (ebb9@email.byu.edu)
2506 private static class SynchronizedIterator<T> implements Iterator<T>
2509 * The object to synchronize on. Package visible for use by subclass.
2514 * The wrapped iterator.
2516 private final Iterator<T> i;
2519 * Only trusted code creates a wrapper, with the specified sync.
2520 * @param sync the mutex
2521 * @param i the wrapped iterator
2523 SynchronizedIterator(Object sync, Iterator<T> i)
2530 * Retrieves the next object in the underlying collection.
2531 * A lock is obtained on the mutex before the collection is accessed.
2533 * @return The next object in the collection.
2534 * @throws NoSuchElementException if there are no more elements
2538 synchronized (mutex)
2545 * Returns <code>true</code> if objects can still be retrieved from the iterator
2546 * using <code>next()</code>. A lock is obtained on the mutex before
2547 * the collection is accessed.
2549 * @return <code>true</code> if at least one element is still to be returned by
2550 * <code>next()</code>.
2552 public boolean hasNext()
2554 synchronized (mutex)
2561 * Removes the object that was last returned by <code>next()</code>
2562 * from the underlying collection. Only one call to this method is
2563 * allowed per call to the <code>next()</code> method, and it does
2564 * not affect the value that will be returned by <code>next()</code>.
2565 * Thus, if element n was retrieved from the collection by
2566 * <code>next()</code>, it is this element that gets removed.
2567 * Regardless of whether this takes place or not, element n+1 is
2568 * still returned on the subsequent <code>next()</code> call.
2570 * @throws IllegalStateException if next has not yet been called or remove
2571 * has already been called since the last call to next.
2572 * @throws UnsupportedOperationException if this Iterator does not support
2573 * the remove operation.
2575 public void remove()
2577 synchronized (mutex)
2582 } // class SynchronizedIterator
2585 * Returns a synchronized (thread-safe) list wrapper backed by the
2586 * given list. Notice that element access through the iterators
2587 * is thread-safe, but if the list can be structurally modified
2588 * (adding or removing elements) then you should synchronize around the
2589 * iteration to avoid non-deterministic behavior:<br>
2591 * List l = Collections.synchronizedList(new List(...));
2595 * Iterator i = l.iterator();
2596 * while (i.hasNext())
2601 * The returned List implements Serializable, but can only be serialized if
2602 * the list it wraps is likewise Serializable. In addition, if the wrapped
2603 * list implements RandomAccess, this does too.
2605 * @param l the list to wrap
2606 * @return a synchronized view of the list
2610 public static <T> List<T> synchronizedList(List<T> l)
2612 if (l instanceof RandomAccess)
2613 return new SynchronizedRandomAccessList<T>(l);
2614 return new SynchronizedList<T>(l);
2618 * The implementation of {@link #synchronizedList(List)} for sequential
2619 * lists. This class name is required for compatibility with Sun's JDK
2620 * serializability. Package visible, so that lists such as Vector.subList()
2621 * can specify which object to synchronize on.
2623 * @author Eric Blake (ebb9@email.byu.edu)
2625 static class SynchronizedList<T> extends SynchronizedCollection<T>
2629 * Compatible with JDK 1.4.
2631 private static final long serialVersionUID = -7754090372962971524L;
2634 * The wrapped list; stored both here and in the superclass to avoid
2635 * excessive casting. Package visible for use by subclass.
2636 * @serial the wrapped list
2641 * Wrap a given list.
2642 * @param l the list to wrap
2643 * @throws NullPointerException if l is null
2645 SynchronizedList(List<T> l)
2652 * Called only by trusted code to specify the mutex as well as the list.
2653 * @param sync the mutex
2656 SynchronizedList(Object sync, List<T> l)
2663 * Insert an element into the underlying list at a given position (optional
2664 * operation). This shifts all existing elements from that position to the
2665 * end one index to the right. This version of add has no return, since it is
2666 * assumed to always succeed if there is no exception. Before the
2667 * addition takes place, a lock is obtained on the mutex.
2669 * @param index the location to insert the item
2670 * @param o the object to insert
2671 * @throws UnsupportedOperationException if this list does not support the
2673 * @throws IndexOutOfBoundsException if index < 0 || index > size()
2674 * @throws ClassCastException if o cannot be added to this list due to its
2676 * @throws IllegalArgumentException if o cannot be added to this list for
2678 * @throws NullPointerException if o is null and this list doesn't support
2679 * the addition of null values.
2681 public void add(int index, T o)
2683 synchronized (mutex)
2690 * Add the contents of a collection to the underlying list at the given
2691 * index (optional operation). If the list imposes restraints on what
2692 * can be inserted, such as no null elements, this should be documented.
2693 * A lock is obtained on the mutex before any of the elements are added.
2695 * @param index the index at which to insert
2696 * @param c the collection to add
2697 * @return <code>true</code>, as defined by Collection for a modified list
2698 * @throws UnsupportedOperationException if this list does not support the
2700 * @throws ClassCastException if o cannot be added to this list due to its
2702 * @throws IllegalArgumentException if o cannot be added to this list for
2704 * @throws NullPointerException if o is null and this list doesn't support
2705 * the addition of null values.
2707 public boolean addAll(int index, Collection<? extends T> c)
2709 synchronized (mutex)
2711 return list.addAll(index, c);
2716 * Tests whether the underlying list is equal to the supplied object.
2717 * The object is deemed to be equal if it is also a <code>List</code>
2718 * of equal size and with the same elements (i.e. each element, e1,
2719 * in list, l1, and each element, e2, in l2, must return <code>true</code> for
2720 * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the
2721 * comparison is made, a lock is obtained on the mutex.
2723 * @param o The object to test for equality with the underlying list.
2724 * @return <code>true</code> if o is equal to the underlying list under the above
2727 public boolean equals(Object o)
2729 synchronized (mutex)
2731 return list.equals(o);
2736 * Retrieves the object at the specified index. A lock
2737 * is obtained on the mutex before the list is accessed.
2739 * @param index the index of the element to be returned
2740 * @return the element at index index in this list
2741 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2743 public T get(int index)
2745 synchronized (mutex)
2747 return list.get(index);
2752 * Obtains a hashcode for the underlying list, first obtaining
2753 * a lock on the mutex. The calculation of the hashcode is
2754 * detailed in the documentation for the <code>List</code>
2757 * @return The hashcode of the underlying list.
2758 * @see List#hashCode()
2760 public int hashCode()
2762 synchronized (mutex)
2764 return list.hashCode();
2769 * Obtain the first index at which a given object is to be found in the
2770 * underlying list. A lock is obtained on the mutex before the list is
2773 * @param o the object to search for
2774 * @return the least integer n such that <code>o == null ? get(n) == null :
2775 * o.equals(get(n))</code>, or -1 if there is no such index.
2776 * @throws ClassCastException if the type of o is not a valid
2777 * type for this list.
2778 * @throws NullPointerException if o is null and this
2779 * list does not support null values.
2782 public int indexOf(Object o)
2784 synchronized (mutex)
2786 return list.indexOf(o);
2791 * Obtain the last index at which a given object is to be found in this
2792 * underlying list. A lock is obtained on the mutex before the list
2795 * @return the greatest integer n such that <code>o == null ? get(n) == null
2796 * : o.equals(get(n))</code>, or -1 if there is no such index.
2797 * @throws ClassCastException if the type of o is not a valid
2798 * type for this list.
2799 * @throws NullPointerException if o is null and this
2800 * list does not support null values.
2802 public int lastIndexOf(Object o)
2804 synchronized (mutex)
2806 return list.lastIndexOf(o);
2811 * Retrieves a synchronized wrapper around the underlying list's
2812 * list iterator. A lock is obtained on the mutex before the
2813 * list iterator is retrieved.
2815 * @return A list iterator over the elements in the underlying list.
2816 * The list iterator allows additional list-specific operations
2817 * to be performed, in addition to those supplied by the
2818 * standard iterator.
2820 public ListIterator<T> listIterator()
2822 synchronized (mutex)
2824 return new SynchronizedListIterator<T>(mutex, list.listIterator());
2829 * Retrieves a synchronized wrapper around the underlying list's
2830 * list iterator. A lock is obtained on the mutex before the
2831 * list iterator is retrieved. The iterator starts at the
2832 * index supplied, leading to the element at that index being
2833 * the first one returned by <code>next()</code>. Calling
2834 * <code>previous()</code> from this initial position returns
2837 * @param index the position, between 0 and size() inclusive, to begin the
2839 * @return A list iterator over the elements in the underlying list.
2840 * The list iterator allows additional list-specific operations
2841 * to be performed, in addition to those supplied by the
2842 * standard iterator.
2843 * @throws IndexOutOfBoundsException if index < 0 || index > size()
2845 public ListIterator<T> listIterator(int index)
2847 synchronized (mutex)
2849 return new SynchronizedListIterator<T>(mutex,
2850 list.listIterator(index));
2855 * Remove the element at a given position in the underlying list (optional
2856 * operation). All remaining elements are shifted to the left to fill the gap.
2857 * A lock on the mutex is obtained before the element is removed.
2859 * @param index the position within the list of the object to remove
2860 * @return the object that was removed
2861 * @throws UnsupportedOperationException if this list does not support the
2863 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2865 public T remove(int index)
2867 synchronized (mutex)
2869 return list.remove(index);
2874 * Replace an element of the underlying list with another object (optional
2875 * operation). A lock is obtained on the mutex before the element is
2878 * @param index the position within this list of the element to be replaced
2879 * @param o the object to replace it with
2880 * @return the object that was replaced
2881 * @throws UnsupportedOperationException if this list does not support the
2883 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2884 * @throws ClassCastException if o cannot be added to this list due to its
2886 * @throws IllegalArgumentException if o cannot be added to this list for
2888 * @throws NullPointerException if o is null and this
2889 * list does not support null values.
2891 public T set(int index, T o)
2893 synchronized (mutex)
2895 return list.set(index, o);
2900 * Obtain a List view of a subsection of the underlying list, from fromIndex
2901 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2902 * sublist is empty. The returned list should be modifiable if and only
2903 * if this list is modifiable. Changes to the returned list should be
2904 * reflected in this list. If this list is structurally modified in
2905 * any way other than through the returned list, the result of any subsequent
2906 * operations on the returned list is undefined. A lock is obtained
2907 * on the mutex before the creation of the sublist. The returned list
2908 * is also synchronized, using the same mutex.
2910 * @param fromIndex the index that the returned list should start from
2912 * @param toIndex the index that the returned list should go to (exclusive)
2913 * @return a List backed by a subsection of this list
2914 * @throws IndexOutOfBoundsException if fromIndex < 0
2915 * || toIndex > size() || fromIndex > toIndex
2917 public List<T> subList(int fromIndex, int toIndex)
2919 synchronized (mutex)
2921 return new SynchronizedList<T>(mutex,
2922 list.subList(fromIndex, toIndex));
2925 } // class SynchronizedList
2928 * The implementation of {@link #synchronizedList(List)} for random-access
2929 * lists. This class name is required for compatibility with Sun's JDK
2932 * @author Eric Blake (ebb9@email.byu.edu)
2934 private static final class SynchronizedRandomAccessList<T>
2935 extends SynchronizedList<T> implements RandomAccess
2938 * Compatible with JDK 1.4.
2940 private static final long serialVersionUID = 1530674583602358482L;
2943 * Wrap a given list.
2944 * @param l the list to wrap
2945 * @throws NullPointerException if l is null
2947 SynchronizedRandomAccessList(List<T> l)
2953 * Called only by trusted code to specify the mutex as well as the
2955 * @param sync the mutex
2958 SynchronizedRandomAccessList(Object sync, List<T> l)
2964 * Obtain a List view of a subsection of the underlying list, from fromIndex
2965 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2966 * sublist is empty. The returned list should be modifiable if and only
2967 * if this list is modifiable. Changes to the returned list should be
2968 * reflected in this list. If this list is structurally modified in
2969 * any way other than through the returned list, the result of any subsequent
2970 * operations on the returned list is undefined. A lock is obtained
2971 * on the mutex before the creation of the sublist. The returned list
2972 * is also synchronized, using the same mutex. Random accessibility
2973 * is also extended to the new list.
2975 * @param fromIndex the index that the returned list should start from
2977 * @param toIndex the index that the returned list should go to (exclusive)
2978 * @return a List backed by a subsection of this list
2979 * @throws IndexOutOfBoundsException if fromIndex < 0
2980 * || toIndex > size() || fromIndex > toIndex
2982 public List<T> subList(int fromIndex, int toIndex)
2984 synchronized (mutex)
2986 return new SynchronizedRandomAccessList<T>(mutex,
2987 list.subList(fromIndex,
2991 } // class SynchronizedRandomAccessList
2994 * The implementation of {@link SynchronizedList#listIterator()}. This
2995 * iterator must "sync" on the same object as the list it iterates over.
2997 * @author Eric Blake (ebb9@email.byu.edu)
2999 private static final class SynchronizedListIterator<T>
3000 extends SynchronizedIterator<T> implements ListIterator<T>
3003 * The wrapped iterator, stored both here and in the superclass to
3004 * avoid excessive casting.
3006 private final ListIterator<T> li;
3009 * Only trusted code creates a wrapper, with the specified sync.
3010 * @param sync the mutex
3011 * @param li the wrapped iterator
3013 SynchronizedListIterator(Object sync, ListIterator<T> li)
3020 * Insert an element into the underlying list at the current position of
3021 * the iterator (optional operation). The element is inserted in between
3022 * the element that would be returned by <code>previous()</code> and the
3023 * element that would be returned by <code>next()</code>. After the
3024 * insertion, a subsequent call to next is unaffected, but
3025 * a call to previous returns the item that was added. The values returned
3026 * by nextIndex() and previousIndex() are incremented. A lock is obtained
3027 * on the mutex before the addition takes place.
3029 * @param o the object to insert into the list
3030 * @throws ClassCastException if the object is of a type which cannot be added
3032 * @throws IllegalArgumentException if some other aspect of the object stops
3033 * it being added to this list.
3034 * @throws UnsupportedOperationException if this ListIterator does not
3035 * support the add operation.
3037 public void add(T o)
3039 synchronized (mutex)
3046 * Tests whether there are elements remaining in the underlying list
3047 * in the reverse direction. In other words, <code>previous()</code>
3048 * will not fail with a NoSuchElementException. A lock is obtained
3049 * on the mutex before the check takes place.
3051 * @return <code>true</code> if the list continues in the reverse direction
3053 public boolean hasPrevious()
3055 synchronized (mutex)
3057 return li.hasPrevious();
3062 * Find the index of the element that would be returned by a call to
3063 * <code>next()</code>. If hasNext() returns <code>false</code>, this
3064 * returns the list size. A lock is obtained on the mutex before the
3065 * query takes place.
3067 * @return the index of the element that would be returned by next()
3069 public int nextIndex()
3071 synchronized (mutex)
3073 return li.nextIndex();
3078 * Obtain the previous element from the underlying list. Repeated
3079 * calls to previous may be used to iterate backwards over the entire list,
3080 * or calls to next and previous may be used together to go forwards and
3081 * backwards. Alternating calls to next and previous will return the same
3082 * element. A lock is obtained on the mutex before the object is retrieved.
3084 * @return the next element in the list in the reverse direction
3085 * @throws NoSuchElementException if there are no more elements
3089 synchronized (mutex)
3091 return li.previous();
3096 * Find the index of the element that would be returned by a call to
3097 * previous. If hasPrevious() returns <code>false</code>, this returns -1.
3098 * A lock is obtained on the mutex before the query takes place.
3100 * @return the index of the element that would be returned by previous()
3102 public int previousIndex()
3104 synchronized (mutex)
3106 return li.previousIndex();
3111 * Replace the element last returned by a call to <code>next()</code> or
3112 * <code>previous()</code> with a given object (optional operation). This
3113 * method may only be called if neither <code>add()</code> nor
3114 * <code>remove()</code> have been called since the last call to
3115 * <code>next()</code> or <code>previous</code>. A lock is obtained
3116 * on the mutex before the list is modified.
3118 * @param o the object to replace the element with
3119 * @throws ClassCastException the object is of a type which cannot be added
3121 * @throws IllegalArgumentException some other aspect of the object stops
3122 * it being added to this list
3123 * @throws IllegalStateException if neither next or previous have been
3124 * called, or if add or remove has been called since the last call
3125 * to next or previous
3126 * @throws UnsupportedOperationException if this ListIterator does not
3127 * support the set operation
3129 public void set(T o)
3131 synchronized (mutex)
3136 } // class SynchronizedListIterator
3139 * Returns a synchronized (thread-safe) map wrapper backed by the given
3140 * map. Notice that element access through the collection views and their
3141 * iterators are thread-safe, but if the map can be structurally modified
3142 * (adding or removing elements) then you should synchronize around the
3143 * iteration to avoid non-deterministic behavior:<br>
3145 * Map m = Collections.synchronizedMap(new Map(...));
3147 * Set s = m.keySet(); // safe outside a synchronized block
3148 * synchronized (m) // synch on m, not s
3150 * Iterator i = s.iterator();
3151 * while (i.hasNext())
3156 * The returned Map implements Serializable, but can only be serialized if
3157 * the map it wraps is likewise Serializable.
3159 * @param m the map to wrap
3160 * @return a synchronized view of the map
3163 public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m)
3165 return new SynchronizedMap<K, V>(m);
3169 * The implementation of {@link #synchronizedMap(Map)}. This
3170 * class name is required for compatibility with Sun's JDK serializability.
3172 * @author Eric Blake (ebb9@email.byu.edu)
3174 private static class SynchronizedMap<K, V> implements Map<K, V>, Serializable
3177 * Compatible with JDK 1.4.
3179 private static final long serialVersionUID = 1978198479659022715L;
3183 * @serial the real map
3185 private final Map<K, V> m;
3188 * The object to synchronize on. When an instance is created via public
3189 * methods, it will be this; but other uses like
3190 * SynchronizedSortedMap.subMap() must specify another mutex. Package
3191 * visible for use by subclass.
3197 * Cache the entry set.
3199 private transient Set<Map.Entry<K, V>> entries;
3202 * Cache the key set.
3204 private transient Set<K> keys;
3207 * Cache the value collection.
3209 private transient Collection<V> values;
3213 * @param m the map to wrap
3214 * @throws NullPointerException if m is null
3216 SynchronizedMap(Map<K, V> m)
3221 throw new NullPointerException();
3225 * Called only by trusted code to specify the mutex as well as the map.
3226 * @param sync the mutex
3229 SynchronizedMap(Object sync, Map<K, V> m)
3236 * Clears all the entries from the underlying map. A lock is obtained
3237 * on the mutex before the map is cleared.
3239 * @throws UnsupportedOperationException if clear is not supported
3243 synchronized (mutex)
3250 * Returns <code>true</code> if the underlying map contains a entry for the given key.
3251 * A lock is obtained on the mutex before the map is queried.
3253 * @param key the key to search for.
3254 * @return <code>true</code> if the underlying map contains the key.
3255 * @throws ClassCastException if the key is of an inappropriate type.
3256 * @throws NullPointerException if key is <code>null</code> but the map
3257 * does not permit null keys.
3259 public boolean containsKey(Object key)
3261 synchronized (mutex)
3263 return m.containsKey(key);
3268 * Returns <code>true</code> if the underlying map contains at least one entry with the
3269 * given value. In other words, returns <code>true</code> if a value v exists where
3270 * <code>(value == null ? v == null : value.equals(v))</code>. This usually
3271 * requires linear time. A lock is obtained on the mutex before the map
3274 * @param value the value to search for
3275 * @return <code>true</code> if the map contains the value
3276 * @throws ClassCastException if the type of the value is not a valid type
3278 * @throws NullPointerException if the value is null and the map doesn't
3279 * support null values.
3281 public boolean containsValue(Object value)
3283 synchronized (mutex)
3285 return m.containsValue(value);
3289 // This is one of the ickiest cases of nesting I've ever seen. It just
3290 // means "return a SynchronizedSet, except that the iterator() method
3291 // returns an SynchronizedIterator whose next() method returns a
3292 // synchronized wrapper around its normal return value".
3293 public Set<Map.Entry<K, V>> entrySet()
3295 // Define this here to spare some nesting.
3296 class SynchronizedMapEntry<K, V> implements Map.Entry<K, V>
3298 final Map.Entry<K, V> e;
3299 SynchronizedMapEntry(Map.Entry<K, V> o)
3305 * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code>
3306 * with the same key and value as the underlying entry. A lock is
3307 * obtained on the mutex before the comparison takes place.
3309 * @param o The object to compare with this entry.
3310 * @return <code>true</code> if o is equivalent to the underlying map entry.
3312 public boolean equals(Object o)
3314 synchronized (mutex)
3321 * Returns the key used in the underlying map entry. A lock is obtained
3322 * on the mutex before the key is retrieved.
3324 * @return The key of the underlying map entry.
3328 synchronized (mutex)
3335 * Returns the value used in the underlying map entry. A lock is obtained
3336 * on the mutex before the value is retrieved.
3338 * @return The value of the underlying map entry.
3342 synchronized (mutex)
3344 return e.getValue();
3349 * Computes the hash code for the underlying map entry.
3350 * This computation is described in the documentation for the
3351 * <code>Map</code> interface. A lock is obtained on the mutex
3352 * before the underlying map is accessed.
3354 * @return The hash code of the underlying map entry.
3355 * @see Map#hashCode()
3357 public int hashCode()
3359 synchronized (mutex)
3361 return e.hashCode();
3366 * Replaces the value in the underlying map entry with the specified
3367 * object (optional operation). A lock is obtained on the mutex
3368 * before the map is altered. The map entry, in turn, will alter
3369 * the underlying map object. The operation is undefined if the
3370 * <code>remove()</code> method of the iterator has been called
3373 * @param value the new value to store
3374 * @return the old value
3375 * @throws UnsupportedOperationException if the operation is not supported.
3376 * @throws ClassCastException if the value is of the wrong type.
3377 * @throws IllegalArgumentException if something about the value
3378 * prevents it from existing in this map.
3379 * @throws NullPointerException if the map forbids null values.
3381 public V setValue(V value)
3383 synchronized (mutex)
3385 return e.setValue(value);
3390 * Returns a textual representation of the underlying map entry.
3391 * A lock is obtained on the mutex before the entry is accessed.
3393 * @return The contents of the map entry in <code>String</code> form.
3395 public String toString()
3397 synchronized (mutex)
3399 return e.toString();
3402 } // class SynchronizedMapEntry
3404 // Now the actual code.
3405 if (entries == null)
3406 synchronized (mutex)
3408 entries = new SynchronizedSet<Map.Entry<K, V>>(mutex, m.entrySet())
3411 * Returns an iterator over the set. The iterator has no specific order,
3412 * unless further specified. A lock is obtained on the set's mutex
3413 * before the iterator is created. The created iterator is also
3416 * @return A synchronized set iterator.
3418 public Iterator<Map.Entry<K, V>> iterator()
3420 synchronized (super.mutex)
3422 return new SynchronizedIterator<Map.Entry<K, V>>(super.mutex,
3426 * Retrieves the next map entry from the iterator.
3427 * A lock is obtained on the iterator's mutex before
3428 * the entry is created. The new map entry is enclosed in
3429 * a thread-safe wrapper.
3431 * @return A synchronized map entry.
3433 public Map.Entry<K, V> next()
3435 synchronized (super.mutex)
3437 return new SynchronizedMapEntry<K, V>(super.next());
3449 * Returns <code>true</code> if the object, o, is also an instance
3450 * of <code>Map</code> and contains an equivalent
3451 * entry set to that of the underlying map. A lock
3452 * is obtained on the mutex before the objects are
3455 * @param o The object to compare.
3456 * @return <code>true</code> if o and the underlying map are equivalent.
3458 public boolean equals(Object o)
3460 synchronized (mutex)
3467 * Returns the value associated with the given key, or null
3468 * if no such mapping exists. An ambiguity exists with maps
3469 * that accept null values as a return value of null could
3470 * be due to a non-existent mapping or simply a null value
3471 * for that key. To resolve this, <code>containsKey</code>
3472 * should be used. A lock is obtained on the mutex before
3473 * the value is retrieved from the underlying map.
3475 * @param key The key of the required mapping.
3476 * @return The value associated with the given key, or
3477 * null if no such mapping exists.
3478 * @throws ClassCastException if the key is an inappropriate type.
3479 * @throws NullPointerException if this map does not accept null keys.
3481 public V get(Object key)
3483 synchronized (mutex)
3490 * Calculates the hash code of the underlying map as the
3491 * sum of the hash codes of all entries. A lock is obtained
3492 * on the mutex before the hash code is computed.
3494 * @return The hash code of the underlying map.
3496 public int hashCode()
3498 synchronized (mutex)
3500 return m.hashCode();
3505 * Returns <code>true</code> if the underlying map contains no entries.
3506 * A lock is obtained on the mutex before the map is examined.
3508 * @return <code>true</code> if the map is empty.
3510 public boolean isEmpty()
3512 synchronized (mutex)
3519 * Returns a thread-safe set view of the keys in the underlying map. The
3520 * set is backed by the map, so that changes in one show up in the other.
3521 * Modifications made while an iterator is in progress cause undefined
3522 * behavior. If the set supports removal, these methods remove the
3523 * underlying mapping from the map: <code>Iterator.remove</code>,
3524 * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
3525 * and <code>clear</code>. Element addition, via <code>add</code> or
3526 * <code>addAll</code>, is not supported via this set. A lock is obtained
3527 * on the mutex before the set is created.
3529 * @return A synchronized set containing the keys of the underlying map.
3531 public Set<K> keySet()
3534 synchronized (mutex)
3536 keys = new SynchronizedSet<K>(mutex, m.keySet());
3542 * Associates the given key to the given value (optional operation). If the
3543 * underlying map already contains the key, its value is replaced. Be aware
3544 * that in a map that permits <code>null</code> values, a null return does not
3545 * always imply that the mapping was created. A lock is obtained on the mutex
3546 * before the modification is made.
3548 * @param key the key to map.
3549 * @param value the value to be mapped.
3550 * @return the previous value of the key, or null if there was no mapping
3551 * @throws UnsupportedOperationException if the operation is not supported
3552 * @throws ClassCastException if the key or value is of the wrong type
3553 * @throws IllegalArgumentException if something about this key or value
3554 * prevents it from existing in this map
3555 * @throws NullPointerException if either the key or the value is null,
3556 * and the map forbids null keys or values
3557 * @see #containsKey(Object)
3559 public V put(K key, V value)
3561 synchronized (mutex)
3563 return m.put(key, value);
3568 * Copies all entries of the given map to the underlying one (optional
3569 * operation). If the map already contains a key, its value is replaced.
3570 * A lock is obtained on the mutex before the operation proceeds.
3572 * @param map the mapping to load into this map
3573 * @throws UnsupportedOperationException if the operation is not supported
3574 * @throws ClassCastException if a key or value is of the wrong type
3575 * @throws IllegalArgumentException if something about a key or value
3576 * prevents it from existing in this map
3577 * @throws NullPointerException if the map forbids null keys or values, or
3578 * if <code>m</code> is null.
3579 * @see #put(Object, Object)
3581 public void putAll(Map<? extends K, ? extends V> map)
3583 synchronized (mutex)
3590 * Removes the mapping for the key, o, if present (optional operation). If
3591 * the key is not present, this returns null. Note that maps which permit
3592 * null values may also return null if the key was removed. A prior
3593 * <code>containsKey()</code> check is required to avoid this ambiguity.
3594 * Before the mapping is removed, a lock is obtained on the mutex.
3596 * @param o the key to remove
3597 * @return the value the key mapped to, or null if not present
3598 * @throws UnsupportedOperationException if deletion is unsupported
3599 * @throws NullPointerException if the key is null and this map doesn't
3600 * support null keys.
3601 * @throws ClassCastException if the type of the key is not a valid type
3604 public V remove(Object o)
3606 synchronized (mutex)
3613 * Retrieves the size of the underlying map. A lock
3614 * is obtained on the mutex before access takes place.
3615 * Maps with a size greater than <code>Integer.MAX_VALUE</code>
3616 * return <code>Integer.MAX_VALUE</code> instead.
3618 * @return The size of the underlying map.
3622 synchronized (mutex)
3629 * Returns a textual representation of the underlying
3630 * map. A lock is obtained on the mutex before the map
3633 * @return The map in <code>String</code> form.
3635 public String toString()
3637 synchronized (mutex)
3639 return m.toString();
3644 * Returns a synchronized collection view of the values in the underlying
3645 * map. The collection is backed by the map, so that changes in one show up in
3646 * the other. Modifications made while an iterator is in progress cause
3647 * undefined behavior. If the collection supports removal, these methods
3648 * remove the underlying mapping from the map: <code>Iterator.remove</code>,
3649 * <code>Collection.remove</code>, <code>removeAll</code>,
3650 * <code>retainAll</code>, and <code>clear</code>. Element addition, via
3651 * <code>add</code> or <code>addAll</code>, is not supported via this
3652 * collection. A lock is obtained on the mutex before the collection
3655 * @return the collection of all values in the underlying map.
3657 public Collection<V> values()
3660 synchronized (mutex)
3662 values = new SynchronizedCollection<V>(mutex, m.values());
3666 } // class SynchronizedMap
3669 * Returns a synchronized (thread-safe) set wrapper backed by the given
3670 * set. Notice that element access through the iterator is thread-safe, but
3671 * if the set can be structurally modified (adding or removing elements)
3672 * then you should synchronize around the iteration to avoid
3673 * non-deterministic behavior:<br>
3675 * Set s = Collections.synchronizedSet(new Set(...));
3679 * Iterator i = s.iterator();
3680 * while (i.hasNext())
3685 * The returned Set implements Serializable, but can only be serialized if
3686 * the set it wraps is likewise Serializable.
3688 * @param s the set to wrap
3689 * @return a synchronized view of the set
3692 public static <T> Set<T> synchronizedSet(Set<T> s)
3694 return new SynchronizedSet<T>(s);
3698 * The implementation of {@link #synchronizedSet(Set)}. This class
3699 * name is required for compatibility with Sun's JDK serializability.
3700 * Package visible, so that sets such as Hashtable.keySet()
3701 * can specify which object to synchronize on.
3703 * @author Eric Blake (ebb9@email.byu.edu)
3705 static class SynchronizedSet<T> extends SynchronizedCollection<T>
3709 * Compatible with JDK 1.4.
3711 private static final long serialVersionUID = 487447009682186044L;
3715 * @param s the set to wrap
3716 * @throws NullPointerException if s is null
3718 SynchronizedSet(Set<T> s)
3724 * Called only by trusted code to specify the mutex as well as the set.
3725 * @param sync the mutex
3728 SynchronizedSet(Object sync, Set<T> s)
3734 * Returns <code>true</code> if the object, o, is a <code>Set</code>
3735 * of the same size as the underlying set, and contains
3736 * each element, e, which occurs in the underlying set.
3737 * A lock is obtained on the mutex before the comparison
3740 * @param o The object to compare against.
3741 * @return <code>true</code> if o is an equivalent set.
3743 public boolean equals(Object o)
3745 synchronized (mutex)
3752 * Computes the hash code for the underlying set as the
3753 * sum of the hash code of all elements within the set.
3754 * A lock is obtained on the mutex before the computation
3757 * @return The hash code for the underlying set.
3759 public int hashCode()
3761 synchronized (mutex)
3763 return c.hashCode();
3766 } // class SynchronizedSet
3769 * Returns a synchronized (thread-safe) sorted map wrapper backed by the
3770 * given map. Notice that element access through the collection views,
3771 * subviews, and their iterators are thread-safe, but if the map can be
3772 * structurally modified (adding or removing elements) then you should
3773 * synchronize around the iteration to avoid non-deterministic behavior:<br>
3775 * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
3777 * Set s = m.keySet(); // safe outside a synchronized block
3778 * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
3779 * Set s2 = m2.keySet(); // safe outside a synchronized block
3780 * synchronized (m) // synch on m, not m2, s or s2
3782 * Iterator i = s.iterator();
3783 * while (i.hasNext())
3785 * i = s2.iterator();
3786 * while (i.hasNext())
3791 * The returned SortedMap implements Serializable, but can only be
3792 * serialized if the map it wraps is likewise Serializable.
3794 * @param m the sorted map to wrap
3795 * @return a synchronized view of the sorted map
3798 public static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> m)
3800 return new SynchronizedSortedMap<K, V>(m);
3804 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
3805 * class name is required for compatibility with Sun's JDK serializability.
3807 * @author Eric Blake (ebb9@email.byu.edu)
3809 private static final class SynchronizedSortedMap<K, V>
3810 extends SynchronizedMap<K, V>
3811 implements SortedMap<K, V>
3814 * Compatible with JDK 1.4.
3816 private static final long serialVersionUID = -8798146769416483793L;
3819 * The wrapped map; stored both here and in the superclass to avoid
3820 * excessive casting.
3821 * @serial the wrapped map
3823 private final SortedMap<K, V> sm;
3827 * @param sm the map to wrap
3828 * @throws NullPointerException if sm is null
3830 SynchronizedSortedMap(SortedMap<K, V> sm)
3837 * Called only by trusted code to specify the mutex as well as the map.
3838 * @param sync the mutex
3841 SynchronizedSortedMap(Object sync, SortedMap<K, V> sm)
3848 * Returns the comparator used in sorting the underlying map, or null if
3849 * it is the keys' natural ordering. A lock is obtained on the mutex
3850 * before the comparator is retrieved.
3852 * @return the sorting comparator.
3854 public Comparator<? super K> comparator()
3856 synchronized (mutex)
3858 return sm.comparator();
3863 * Returns the first, lowest sorted, key from the underlying map.
3864 * A lock is obtained on the mutex before the map is accessed.
3866 * @return the first key.
3867 * @throws NoSuchElementException if this map is empty.
3871 synchronized (mutex)
3873 return sm.firstKey();
3878 * Returns a submap containing the keys from the first
3879 * key (as returned by <code>firstKey()</code>) to
3880 * the key before that specified. The submap supports all
3881 * operations supported by the underlying map and all actions
3882 * taking place on the submap are also reflected in the underlying
3883 * map. A lock is obtained on the mutex prior to submap creation.
3884 * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>.
3885 * The submap retains the thread-safe status of this map.
3887 * @param toKey the exclusive upper range of the submap.
3888 * @return a submap from <code>firstKey()</code> to the
3889 * the key preceding toKey.
3890 * @throws ClassCastException if toKey is not comparable to the underlying
3892 * @throws IllegalArgumentException if toKey is outside the map's range.
3893 * @throws NullPointerException if toKey is null. but the map does not allow
3896 public SortedMap<K, V> headMap(K toKey)
3898 synchronized (mutex)
3900 return new SynchronizedSortedMap<K, V>(mutex, sm.headMap(toKey));
3905 * Returns the last, highest sorted, key from the underlying map.
3906 * A lock is obtained on the mutex before the map is accessed.
3908 * @return the last key.
3909 * @throws NoSuchElementException if this map is empty.
3913 synchronized (mutex)
3915 return sm.lastKey();
3920 * Returns a submap containing the keys from fromKey to
3921 * the key before toKey. The submap supports all
3922 * operations supported by the underlying map and all actions
3923 * taking place on the submap are also reflected in the underlying
3924 * map. A lock is obtained on the mutex prior to submap creation.
3925 * The submap retains the thread-safe status of this map.
3927 * @param fromKey the inclusive lower range of the submap.
3928 * @param toKey the exclusive upper range of the submap.
3929 * @return a submap from fromKey to the key preceding toKey.
3930 * @throws ClassCastException if fromKey or toKey is not comparable
3931 * to the underlying map's contents.
3932 * @throws IllegalArgumentException if fromKey or toKey is outside the map's
3934 * @throws NullPointerException if fromKey or toKey is null. but the map does
3935 * not allow null keys.
3937 public SortedMap<K, V> subMap(K fromKey, K toKey)
3939 synchronized (mutex)
3941 return new SynchronizedSortedMap<K, V>(mutex,
3942 sm.subMap(fromKey, toKey));
3947 * Returns a submap containing all the keys from fromKey onwards.
3948 * The submap supports all operations supported by the underlying
3949 * map and all actions taking place on the submap are also reflected
3950 * in the underlying map. A lock is obtained on the mutex prior to
3951 * submap creation. The submap retains the thread-safe status of
3954 * @param fromKey the inclusive lower range of the submap.
3955 * @return a submap from fromKey to <code>lastKey()</code>.
3956 * @throws ClassCastException if fromKey is not comparable to the underlying
3958 * @throws IllegalArgumentException if fromKey is outside the map's range.
3959 * @throws NullPointerException if fromKey is null. but the map does not allow
3962 public SortedMap<K, V> tailMap(K fromKey)
3964 synchronized (mutex)
3966 return new SynchronizedSortedMap<K, V>(mutex, sm.tailMap(fromKey));
3969 } // class SynchronizedSortedMap
3972 * Returns a synchronized (thread-safe) sorted set wrapper backed by the
3973 * given set. Notice that element access through the iterator and through
3974 * subviews are thread-safe, but if the set can be structurally modified
3975 * (adding or removing elements) then you should synchronize around the
3976 * iteration to avoid non-deterministic behavior:<br>
3978 * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
3980 * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
3981 * synchronized (s) // synch on s, not s2
3983 * Iterator i = s2.iterator();
3984 * while (i.hasNext())
3989 * The returned SortedSet implements Serializable, but can only be
3990 * serialized if the set it wraps is likewise Serializable.
3992 * @param s the sorted set to wrap
3993 * @return a synchronized view of the sorted set
3996 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
3998 return new SynchronizedSortedSet<T>(s);
4002 * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
4003 * class name is required for compatibility with Sun's JDK serializability.
4005 * @author Eric Blake (ebb9@email.byu.edu)
4007 private static final class SynchronizedSortedSet<T>
4008 extends SynchronizedSet<T>
4009 implements SortedSet<T>
4012 * Compatible with JDK 1.4.
4014 private static final long serialVersionUID = 8695801310862127406L;
4017 * The wrapped set; stored both here and in the superclass to avoid
4018 * excessive casting.
4019 * @serial the wrapped set
4021 private final SortedSet<T> ss;
4025 * @param ss the set to wrap
4026 * @throws NullPointerException if ss is null
4028 SynchronizedSortedSet(SortedSet<T> ss)
4035 * Called only by trusted code to specify the mutex as well as the set.
4036 * @param sync the mutex
4039 SynchronizedSortedSet(Object sync, SortedSet<T> ss)
4046 * Returns the comparator used in sorting the underlying set, or null if
4047 * it is the elements' natural ordering. A lock is obtained on the mutex
4048 * before the comparator is retrieved.
4050 * @return the sorting comparator.
4052 public Comparator<? super T> comparator()
4054 synchronized (mutex)
4056 return ss.comparator();
4061 * Returns the first, lowest sorted, element from the underlying set.
4062 * A lock is obtained on the mutex before the set is accessed.
4064 * @return the first element.
4065 * @throws NoSuchElementException if this set is empty.
4069 synchronized (mutex)
4076 * Returns a subset containing the element from the first
4077 * element (as returned by <code>first()</code>) to
4078 * the element before that specified. The subset supports all
4079 * operations supported by the underlying set and all actions
4080 * taking place on the subset are also reflected in the underlying
4081 * set. A lock is obtained on the mutex prior to subset creation.
4082 * This operation is equivalent to <code>subSet(first(), toElement)</code>.
4083 * The subset retains the thread-safe status of this set.
4085 * @param toElement the exclusive upper range of the subset.
4086 * @return a subset from <code>first()</code> to the
4087 * the element preceding toElement.
4088 * @throws ClassCastException if toElement is not comparable to the underlying
4090 * @throws IllegalArgumentException if toElement is outside the set's range.
4091 * @throws NullPointerException if toElement is null. but the set does not allow
4094 public SortedSet<T> headSet(T toElement)
4096 synchronized (mutex)
4098 return new SynchronizedSortedSet<T>(mutex, ss.headSet(toElement));
4103 * Returns the last, highest sorted, element from the underlying set.
4104 * A lock is obtained on the mutex before the set is accessed.
4106 * @return the last element.
4107 * @throws NoSuchElementException if this set is empty.
4111 synchronized (mutex)
4118 * Returns a subset containing the elements from fromElement to
4119 * the element before toElement. The subset supports all
4120 * operations supported by the underlying set and all actions
4121 * taking place on the subset are also reflected in the underlying
4122 * set. A lock is obtained on the mutex prior to subset creation.
4123 * The subset retains the thread-safe status of this set.
4125 * @param fromElement the inclusive lower range of the subset.
4126 * @param toElement the exclusive upper range of the subset.
4127 * @return a subset from fromElement to the element preceding toElement.
4128 * @throws ClassCastException if fromElement or toElement is not comparable
4129 * to the underlying set's contents.
4130 * @throws IllegalArgumentException if fromElement or toElement is outside the set's
4132 * @throws NullPointerException if fromElement or toElement is null. but the set does
4133 * not allow null elements.
4135 public SortedSet<T> subSet(T fromElement, T toElement)
4137 synchronized (mutex)
4139 return new SynchronizedSortedSet<T>(mutex,
4140 ss.subSet(fromElement,
4146 * Returns a subset containing all the elements from fromElement onwards.
4147 * The subset supports all operations supported by the underlying
4148 * set and all actions taking place on the subset are also reflected
4149 * in the underlying set. A lock is obtained on the mutex prior to
4150 * subset creation. The subset retains the thread-safe status of
4153 * @param fromElement the inclusive lower range of the subset.
4154 * @return a subset from fromElement to <code>last()</code>.
4155 * @throws ClassCastException if fromElement is not comparable to the underlying
4157 * @throws IllegalArgumentException if fromElement is outside the set's range.
4158 * @throws NullPointerException if fromElement is null. but the set does not allow
4161 public SortedSet<T> tailSet(T fromElement)
4163 synchronized (mutex)
4165 return new SynchronizedSortedSet<T>(mutex, ss.tailSet(fromElement));
4168 } // class SynchronizedSortedSet
4172 * Returns an unmodifiable view of the given collection. This allows
4173 * "read-only" access, although changes in the backing collection show up
4174 * in this view. Attempts to modify the collection directly or via iterators
4175 * will fail with {@link UnsupportedOperationException}. Although this view
4176 * prevents changes to the structure of the collection and its elements, the values
4177 * referenced by the objects in the collection can still be modified.
4180 * Since the collection might be a List or a Set, and those have incompatible
4181 * equals and hashCode requirements, this relies on Object's implementation
4182 * rather than passing those calls on to the wrapped collection. The returned
4183 * Collection implements Serializable, but can only be serialized if
4184 * the collection it wraps is likewise Serializable.
4186 * @param c the collection to wrap
4187 * @return a read-only view of the collection
4190 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)
4192 return new UnmodifiableCollection<T>(c);
4196 * The implementation of {@link #unmodifiableCollection(Collection)}. This
4197 * class name is required for compatibility with Sun's JDK serializability.
4199 * @author Eric Blake (ebb9@email.byu.edu)
4201 private static class UnmodifiableCollection<T>
4202 implements Collection<T>, Serializable
4205 * Compatible with JDK 1.4.
4207 private static final long serialVersionUID = 1820017752578914078L;
4210 * The wrapped collection. Package visible for use by subclasses.
4211 * @serial the real collection
4213 final Collection<? extends T> c;
4216 * Wrap a given collection.
4217 * @param c the collection to wrap
4218 * @throws NullPointerException if c is null
4220 UnmodifiableCollection(Collection<? extends T> c)
4224 throw new NullPointerException();
4228 * Blocks the addition of elements to the underlying collection.
4229 * This method never returns, throwing an exception instead.
4231 * @param o the object to add.
4232 * @return <code>true</code> if the collection was modified as a result of this action.
4233 * @throws UnsupportedOperationException as an unmodifiable collection does not
4234 * support the add operation.
4236 public boolean add(T o)
4238 throw new UnsupportedOperationException();
4242 * Blocks the addition of a collection of elements to the underlying
4243 * collection. This method never returns, throwing an exception instead.
4245 * @param c the collection to add.
4246 * @return <code>true</code> if the collection was modified as a result of this action.
4247 * @throws UnsupportedOperationException as an unmodifiable collection does not
4248 * support the <code>addAll</code> operation.
4250 public boolean addAll(Collection<? extends T> c)
4252 throw new UnsupportedOperationException();
4256 * Blocks the clearing of the underlying collection. This method never
4257 * returns, throwing an exception instead.
4259 * @throws UnsupportedOperationException as an unmodifiable collection does
4260 * not support the <code>clear()</code> operation.
4264 throw new UnsupportedOperationException();
4268 * Test whether the underlying collection contains a given object as one of its
4271 * @param o the element to look for.
4272 * @return <code>true</code> if the underlying collection contains at least
4273 * one element e such that
4274 * <code>o == null ? e == null : o.equals(e)</code>.
4275 * @throws ClassCastException if the type of o is not a valid type for the
4276 * underlying collection.
4277 * @throws NullPointerException if o is null and the underlying collection
4278 * doesn't support null values.
4280 public boolean contains(Object o)
4282 return c.contains(o);
4286 * Test whether the underlying collection contains every element in a given
4289 * @param c1 the collection to test for.
4290 * @return <code>true</code> if for every element o in c, contains(o) would
4291 * return <code>true</code>.
4292 * @throws ClassCastException if the type of any element in c is not a valid
4293 * type for the underlying collection.
4294 * @throws NullPointerException if some element of c is null and the underlying
4295 * collection does not support null values.
4296 * @throws NullPointerException if c itself is null.
4298 public boolean containsAll(Collection<?> c1)
4300 return c.containsAll(c1);
4304 * Tests whether the underlying collection is empty, that is,
4307 * @return <code>true</code> if this collection contains no elements.
4309 public boolean isEmpty()
4315 * Obtain an Iterator over the underlying collection, which maintains
4316 * its unmodifiable nature.
4318 * @return an UnmodifiableIterator over the elements of the underlying
4319 * collection, in any order.
4321 public Iterator<T> iterator()
4323 return new UnmodifiableIterator<T>(c.iterator());
4327 * Blocks the removal of an object from the underlying collection.
4328 * This method never returns, throwing an exception instead.
4330 * @param o The object to remove.
4331 * @return <code>true</code> if the object was removed (i.e. the underlying
4332 * collection returned 1 or more instances of o).
4333 * @throws UnsupportedOperationException as an unmodifiable collection
4334 * does not support the <code>remove()</code> operation.
4336 public boolean remove(Object o)
4338 throw new UnsupportedOperationException();
4342 * Blocks the removal of a collection of objects from the underlying
4343 * collection. This method never returns, throwing an exception
4346 * @param c The collection of objects to remove.
4347 * @return <code>true</code> if the collection was modified.
4348 * @throws UnsupportedOperationException as an unmodifiable collection
4349 * does not support the <code>removeAll()</code> operation.
4351 public boolean removeAll(Collection<?> c)
4353 throw new UnsupportedOperationException();
4357 * Blocks the removal of all elements from the underlying collection,
4358 * except those in the supplied collection. This method never returns,
4359 * throwing an exception instead.
4361 * @param c The collection of objects to retain.
4362 * @return <code>true</code> if the collection was modified.
4363 * @throws UnsupportedOperationException as an unmodifiable collection
4364 * does not support the <code>retainAll()</code> operation.
4366 public boolean retainAll(Collection<?> c)
4368 throw new UnsupportedOperationException();
4372 * Retrieves the number of elements in the underlying collection.
4374 * @return the number of elements in the collection.
4382 * Copy the current contents of the underlying collection into an array.
4384 * @return an array of type Object[] with a length equal to the size of the
4385 * underlying collection and containing the elements currently in
4386 * the underlying collection, in any order.
4388 public Object[] toArray()
4394 * Copy the current contents of the underlying collection into an array. If
4395 * the array passed as an argument has length less than the size of the
4396 * underlying collection, an array of the same run-time type as a, with a length
4397 * equal to the size of the underlying collection, is allocated using reflection.
4398 * Otherwise, a itself is used. The elements of the underlying collection are
4399 * copied into it, and if there is space in the array, the following element is
4400 * set to null. The resultant array is returned.
4401 * Note: The fact that the following element is set to null is only useful
4402 * if it is known that this collection does not contain any null elements.
4404 * @param a the array to copy this collection into.
4405 * @return an array containing the elements currently in the underlying
4406 * collection, in any order.
4407 * @throws ArrayStoreException if the type of any element of the
4408 * collection is not a subtype of the element type of a.
4410 public <S> S[] toArray(S[] a)
4412 return c.toArray(a);
4416 * A textual representation of the unmodifiable collection.
4418 * @return The unmodifiable collection in the form of a <code>String</code>.
4420 public String toString()
4422 return c.toString();
4424 } // class UnmodifiableCollection
4427 * The implementation of the various iterator methods in the
4428 * unmodifiable classes.
4430 * @author Eric Blake (ebb9@email.byu.edu)
4432 private static class UnmodifiableIterator<T> implements Iterator<T>
4435 * The wrapped iterator.
4437 private final Iterator<? extends T> i;
4440 * Only trusted code creates a wrapper.
4441 * @param i the wrapped iterator
4443 UnmodifiableIterator(Iterator<? extends T> i)
4449 * Obtains the next element in the underlying collection.
4451 * @return the next element in the collection.
4452 * @throws NoSuchElementException if there are no more elements.
4460 * Tests whether there are still elements to be retrieved from the
4461 * underlying collection by <code>next()</code>. When this method
4462 * returns <code>true</code>, an exception will not be thrown on calling
4463 * <code>next()</code>.
4465 * @return <code>true</code> if there is at least one more element in the underlying
4468 public boolean hasNext()
4474 * Blocks the removal of elements from the underlying collection by the
4477 * @throws UnsupportedOperationException as an unmodifiable collection
4478 * does not support the removal of elements by its iterator.
4480 public void remove()
4482 throw new UnsupportedOperationException();
4484 } // class UnmodifiableIterator
4487 * Returns an unmodifiable view of the given list. This allows
4488 * "read-only" access, although changes in the backing list show up
4489 * in this view. Attempts to modify the list directly, via iterators, or
4490 * via sublists, will fail with {@link UnsupportedOperationException}.
4491 * Although this view prevents changes to the structure of the list and
4492 * its elements, the values referenced by the objects in the list can
4493 * still be modified.
4496 * The returned List implements Serializable, but can only be serialized if
4497 * the list it wraps is likewise Serializable. In addition, if the wrapped
4498 * list implements RandomAccess, this does too.
4500 * @param l the list to wrap
4501 * @return a read-only view of the list
4505 public static <T> List<T> unmodifiableList(List<? extends T> l)
4507 if (l instanceof RandomAccess)
4508 return new UnmodifiableRandomAccessList<T>(l);
4509 return new UnmodifiableList<T>(l);
4513 * The implementation of {@link #unmodifiableList(List)} for sequential
4514 * lists. This class name is required for compatibility with Sun's JDK
4517 * @author Eric Blake (ebb9@email.byu.edu)
4519 private static class UnmodifiableList<T> extends UnmodifiableCollection<T>
4523 * Compatible with JDK 1.4.
4525 private static final long serialVersionUID = -283967356065247728L;
4529 * The wrapped list; stored both here and in the superclass to avoid
4530 * excessive casting. Package visible for use by subclass.
4531 * @serial the wrapped list
4536 * Wrap a given list.
4537 * @param l the list to wrap
4538 * @throws NullPointerException if l is null
4540 UnmodifiableList(List<? extends T> l)
4547 * Blocks the addition of an element to the underlying
4548 * list at a specific index. This method never returns,
4549 * throwing an exception instead.
4551 * @param index The index at which to place the new element.
4552 * @param o the object to add.
4553 * @throws UnsupportedOperationException as an unmodifiable
4554 * list doesn't support the <code>add()</code> operation.
4556 public void add(int index, T o)
4558 throw new UnsupportedOperationException();
4562 * Blocks the addition of a collection of elements to the
4563 * underlying list at a specific index. This method never
4564 * returns, throwing an exception instead.
4566 * @param index The index at which to place the new element.
4567 * @param c the collections of objects to add.
4568 * @throws UnsupportedOperationException as an unmodifiable
4569 * list doesn't support the <code>addAll()</code> operation.
4571 public boolean addAll(int index, Collection<? extends T> c)
4573 throw new UnsupportedOperationException();
4577 * Returns <code>true</code> if the object, o, is an instance of
4578 * <code>List</code> with the same size and elements
4579 * as the underlying list.
4581 * @param o The object to compare.
4582 * @return <code>true</code> if o is equivalent to the underlying list.
4584 public boolean equals(Object o)
4586 return list.equals(o);
4590 * Retrieves the element at a given index in the underlying list.
4592 * @param index the index of the element to be returned
4593 * @return the element at index index in this list
4594 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
4596 public T get(int index)
4598 return list.get(index);
4602 * Computes the hash code for the underlying list.
4603 * The exact computation is described in the documentation
4604 * of the <code>List</code> interface.
4606 * @return The hash code of the underlying list.
4607 * @see List#hashCode()
4609 public int hashCode()
4611 return list.hashCode();
4615 * Obtain the first index at which a given object is to be found in the
4618 * @param o the object to search for
4619 * @return the least integer n such that <code>o == null ? get(n) == null :
4620 * o.equals(get(n))</code>, or -1 if there is no such index.
4621 * @throws ClassCastException if the type of o is not a valid
4622 * type for the underlying list.
4623 * @throws NullPointerException if o is null and the underlying
4624 * list does not support null values.
4626 public int indexOf(Object o)
4628 return list.indexOf(o);
4632 * Obtain the last index at which a given object is to be found in the
4635 * @return the greatest integer n such that <code>o == null ? get(n) == null
4636 * : o.equals(get(n))</code>, or -1 if there is no such index.
4637 * @throws ClassCastException if the type of o is not a valid
4638 * type for the underlying list.
4639 * @throws NullPointerException if o is null and the underlying
4640 * list does not support null values.
4642 public int lastIndexOf(Object o)
4644 return list.lastIndexOf(o);
4648 * Obtains a list iterator over the underlying list, starting at the beginning
4649 * and maintaining the unmodifiable nature of this list.
4651 * @return a <code>UnmodifiableListIterator</code> over the elements of the
4652 * underlying list, in order, starting at the beginning.
4654 public ListIterator<T> listIterator()
4656 return new UnmodifiableListIterator<T>(list.listIterator());
4660 * Obtains a list iterator over the underlying list, starting at the specified
4661 * index and maintaining the unmodifiable nature of this list. An initial call
4662 * to <code>next()</code> will retrieve the element at the specified index,
4663 * and an initial call to <code>previous()</code> will retrieve the element
4667 * @param index the position, between 0 and size() inclusive, to begin the
4669 * @return a <code>UnmodifiableListIterator</code> over the elements of the
4670 * underlying list, in order, starting at the specified index.
4671 * @throws IndexOutOfBoundsException if index < 0 || index > size()
4673 public ListIterator<T> listIterator(int index)
4675 return new UnmodifiableListIterator<T>(list.listIterator(index));
4679 * Blocks the removal of the element at the specified index.
4680 * This method never returns, throwing an exception instead.
4682 * @param index The index of the element to remove.
4683 * @return the removed element.
4684 * @throws UnsupportedOperationException as an unmodifiable
4685 * list does not support the <code>remove()</code>
4688 public T remove(int index)
4690 throw new UnsupportedOperationException();
4694 * Blocks the replacement of the element at the specified index.
4695 * This method never returns, throwing an exception instead.
4697 * @param index The index of the element to replace.
4698 * @param o The new object to place at the specified index.
4699 * @return the replaced element.
4700 * @throws UnsupportedOperationException as an unmodifiable
4701 * list does not support the <code>set()</code>
4704 public T set(int index, T o)
4706 throw new UnsupportedOperationException();
4710 * Obtain a List view of a subsection of the underlying list, from
4711 * fromIndex (inclusive) to toIndex (exclusive). If the two indices
4712 * are equal, the sublist is empty. The returned list will be
4713 * unmodifiable, like this list. Changes to the elements of the
4714 * returned list will be reflected in the underlying list. No structural
4715 * modifications can take place in either list.
4717 * @param fromIndex the index that the returned list should start from
4719 * @param toIndex the index that the returned list should go to (exclusive).
4720 * @return a List backed by a subsection of the underlying list.
4721 * @throws IndexOutOfBoundsException if fromIndex < 0
4722 * || toIndex > size() || fromIndex > toIndex.
4724 public List<T> subList(int fromIndex, int toIndex)
4726 return unmodifiableList(list.subList(fromIndex, toIndex));
4728 } // class UnmodifiableList
4731 * The implementation of {@link #unmodifiableList(List)} for random-access
4732 * lists. This class name is required for compatibility with Sun's JDK
4735 * @author Eric Blake (ebb9@email.byu.edu)
4737 private static final class UnmodifiableRandomAccessList<T>
4738 extends UnmodifiableList<T> implements RandomAccess
4741 * Compatible with JDK 1.4.
4743 private static final long serialVersionUID = -2542308836966382001L;
4746 * Wrap a given list.
4747 * @param l the list to wrap
4748 * @throws NullPointerException if l is null
4750 UnmodifiableRandomAccessList(List<? extends T> l)
4754 } // class UnmodifiableRandomAccessList
4757 * The implementation of {@link UnmodifiableList#listIterator()}.
4759 * @author Eric Blake (ebb9@email.byu.edu)
4761 private static final class UnmodifiableListIterator<T>
4762 extends UnmodifiableIterator<T> implements ListIterator<T>
4765 * The wrapped iterator, stored both here and in the superclass to
4766 * avoid excessive casting.
4768 private final ListIterator<T> li;
4771 * Only trusted code creates a wrapper.
4772 * @param li the wrapped iterator
4774 UnmodifiableListIterator(ListIterator<T> li)
4781 * Blocks the addition of an object to the list underlying this iterator.
4782 * This method never returns, throwing an exception instead.
4784 * @param o The object to add.
4785 * @throws UnsupportedOperationException as the iterator of an unmodifiable
4786 * list does not support the <code>add()</code> operation.
4788 public void add(T o)
4790 throw new UnsupportedOperationException();
4794 * Tests whether there are still elements to be retrieved from the
4795 * underlying collection by <code>previous()</code>. When this method
4796 * returns <code>true</code>, an exception will not be thrown on calling
4797 * <code>previous()</code>.
4799 * @return <code>true</code> if there is at least one more element prior to the
4800 * current position in the underlying list.
4802 public boolean hasPrevious()
4804 return li.hasPrevious();
4808 * Find the index of the element that would be returned by a call to next.
4809 * If <code>hasNext()</code> returns <code>false</code>, this returns the list size.
4811 * @return the index of the element that would be returned by
4812 * <code>next()</code>.
4814 public int nextIndex()
4816 return li.nextIndex();
4820 * Obtains the previous element in the underlying list.
4822 * @return the previous element in the list.
4823 * @throws NoSuchElementException if there are no more prior elements.
4827 return li.previous();
4831 * Find the index of the element that would be returned by a call to
4832 * previous. If <code>hasPrevious()</code> returns <code>false</code>,
4835 * @return the index of the element that would be returned by
4836 * <code>previous()</code>.
4838 public int previousIndex()
4840 return li.previousIndex();
4844 * Blocks the replacement of an element in the list underlying this
4845 * iterator. This method never returns, throwing an exception instead.
4847 * @param o The new object to replace the existing one.
4848 * @throws UnsupportedOperationException as the iterator of an unmodifiable
4849 * list does not support the <code>set()</code> operation.
4851 public void set(T o)
4853 throw new UnsupportedOperationException();
4855 } // class UnmodifiableListIterator
4858 * Returns an unmodifiable view of the given map. This allows "read-only"
4859 * access, although changes in the backing map show up in this view.
4860 * Attempts to modify the map directly, or via collection views or their
4861 * iterators will fail with {@link UnsupportedOperationException}.
4862 * Although this view prevents changes to the structure of the map and its
4863 * entries, the values referenced by the objects in the map can still be
4867 * The returned Map implements Serializable, but can only be serialized if
4868 * the map it wraps is likewise Serializable.
4870 * @param m the map to wrap
4871 * @return a read-only view of the map
4874 public static <K, V> Map<K, V> unmodifiableMap(Map<? extends K,
4877 return new UnmodifiableMap<K, V>(m);
4881 * The implementation of {@link #unmodifiableMap(Map)}. This
4882 * class name is required for compatibility with Sun's JDK serializability.
4884 * @author Eric Blake (ebb9@email.byu.edu)
4886 private static class UnmodifiableMap<K, V> implements Map<K, V>, Serializable
4889 * Compatible with JDK 1.4.
4891 private static final long serialVersionUID = -1034234728574286014L;
4895 * @serial the real map
4897 private final Map<K, V> m;
4900 * Cache the entry set.
4902 private transient Set<Map.Entry<K, V>> entries;
4905 * Cache the key set.
4907 private transient Set<K> keys;
4910 * Cache the value collection.
4912 private transient Collection<V> values;
4916 * @param m the map to wrap
4917 * @throws NullPointerException if m is null
4919 UnmodifiableMap(Map<? extends K, ? extends V> m)
4921 this.m = (Map<K,V>) m;
4923 throw new NullPointerException();
4927 * Blocks the clearing of entries from the underlying map.
4928 * This method never returns, throwing an exception instead.
4930 * @throws UnsupportedOperationException as an unmodifiable
4931 * map does not support the <code>clear()</code> operation.
4935 throw new UnsupportedOperationException();
4939 * Returns <code>true</code> if the underlying map contains a mapping for
4942 * @param key the key to search for
4943 * @return <code>true</code> if the map contains the key
4944 * @throws ClassCastException if the key is of an inappropriate type
4945 * @throws NullPointerException if key is <code>null</code> but the map
4946 * does not permit null keys
4948 public boolean containsKey(Object key)
4950 return m.containsKey(key);
4954 * Returns <code>true</code> if the underlying map contains at least one mapping with
4955 * the given value. In other words, it returns <code>true</code> if a value v exists where
4956 * <code>(value == null ? v == null : value.equals(v))</code>. This usually
4957 * requires linear time.
4959 * @param value the value to search for
4960 * @return <code>true</code> if the map contains the value
4961 * @throws ClassCastException if the type of the value is not a valid type
4963 * @throws NullPointerException if the value is null and the map doesn't
4964 * support null values.
4966 public boolean containsValue(Object value)
4968 return m.containsValue(value);
4972 * Returns a unmodifiable set view of the entries in the underlying map.
4973 * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>.
4974 * The set is backed by the map, so that changes in one show up in the other.
4975 * Modifications made while an iterator is in progress cause undefined
4976 * behavior. These modifications are again limited to the values of
4979 * @return the unmodifiable set view of all mapping entries.
4982 public Set<Map.Entry<K, V>> entrySet()
4984 if (entries == null)
4985 entries = new UnmodifiableEntrySet<K,V>(m.entrySet());
4990 * The implementation of {@link UnmodifiableMap#entrySet()}. This class
4991 * name is required for compatibility with Sun's JDK serializability.
4993 * @author Eric Blake (ebb9@email.byu.edu)
4995 private static final class UnmodifiableEntrySet<K,V>
4996 extends UnmodifiableSet<Map.Entry<K,V>>
4997 implements Serializable
4999 // Unmodifiable implementation of Map.Entry used as return value for
5000 // UnmodifiableEntrySet accessors (iterator, toArray, toArray(Object[]))
5001 private static final class UnmodifiableMapEntry<K,V>
5002 implements Map.Entry<K,V>
5004 private final Map.Entry<K,V> e;
5006 private UnmodifiableMapEntry(Map.Entry<K,V> e)
5013 * Returns <code>true</code> if the object, o, is also a map entry
5014 * with an identical key and value.
5016 * @param o the object to compare.
5017 * @return <code>true</code> if o is an equivalent map entry.
5019 public boolean equals(Object o)
5025 * Returns the key of this map entry.
5035 * Returns the value of this map entry.
5037 * @return the value.
5041 return e.getValue();
5045 * Computes the hash code of this map entry. The computation is
5046 * described in the <code>Map</code> interface documentation.
5048 * @return the hash code of this entry.
5049 * @see Map#hashCode()
5051 public int hashCode()
5053 return e.hashCode();
5057 * Blocks the alteration of the value of this map entry. This method
5058 * never returns, throwing an exception instead.
5060 * @param value The new value.
5061 * @throws UnsupportedOperationException as an unmodifiable map entry
5062 * does not support the <code>setValue()</code> operation.
5064 public V setValue(V value)
5066 throw new UnsupportedOperationException();
5070 * Returns a textual representation of the map entry.
5072 * @return The map entry as a <code>String</code>.
5074 public String toString()
5076 return e.toString();
5081 * Compatible with JDK 1.4.
5083 private static final long serialVersionUID = 7854390611657943733L;
5087 * @param s the set to wrap
5089 UnmodifiableEntrySet(Set<Map.Entry<K,V>> s)
5094 // The iterator must return unmodifiable map entries.
5095 public Iterator<Map.Entry<K,V>> iterator()
5097 return new UnmodifiableIterator<Map.Entry<K,V>>(c.iterator())
5100 * Obtains the next element from the underlying set of
5103 * @return the next element in the collection.
5104 * @throws NoSuchElementException if there are no more elements.
5106 public Map.Entry<K,V> next()
5108 final Map.Entry<K,V> e = super.next();
5109 return new UnmodifiableMapEntry<K,V>(e);
5114 // The array returned is an array of UnmodifiableMapEntry instead of
5116 public Map.Entry<K,V>[] toArray()
5118 Object[] mapEntryResult = super.toArray();
5119 UnmodifiableMapEntry<K,V> result[] = null;
5121 if (mapEntryResult != null)
5123 result = (UnmodifiableMapEntry<K,V>[])
5124 new UnmodifiableMapEntry[mapEntryResult.length];
5125 for (int i = 0; i < mapEntryResult.length; ++i)
5126 result[i] = new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>)mapEntryResult[i]);
5131 // The array returned is an array of UnmodifiableMapEntry instead of
5133 public <S> S[] toArray(S[] array)
5135 S[] result = super.toArray(array);
5138 for (int i = 0; i < result.length; i++)
5140 (S) new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>) result[i]);
5145 } // class UnmodifiableEntrySet
5148 * Returns <code>true</code> if the object, o, is also an instance
5149 * of <code>Map</code> with an equal set of map entries.
5151 * @param o The object to compare.
5152 * @return <code>true</code> if o is an equivalent map.
5154 public boolean equals(Object o)
5160 * Returns the value associated with the supplied key or
5161 * null if no such mapping exists. An ambiguity can occur
5162 * if null values are accepted by the underlying map.
5163 * In this case, <code>containsKey()</code> can be used
5164 * to separate the two possible cases of a null result.
5166 * @param key The key to look up.
5167 * @return the value associated with the key, or null if key not in map.
5168 * @throws ClassCastException if the key is an inappropriate type.
5169 * @throws NullPointerException if this map does not accept null keys.
5170 * @see #containsKey(Object)
5172 public V get(Object key)
5178 * Blocks the addition of a new entry to the underlying map.
5179 * This method never returns, throwing an exception instead.
5181 * @param key The new key.
5182 * @param value The new value.
5183 * @return the previous value of the key, or null if there was no mapping.
5184 * @throws UnsupportedOperationException as an unmodifiable
5185 * map does not support the <code>put()</code> operation.
5187 public V put(K key, V value)
5189 throw new UnsupportedOperationException();
5193 * Computes the hash code for the underlying map, as the sum
5194 * of the hash codes of all entries.
5196 * @return The hash code of the underlying map.
5197 * @see Map.Entry#hashCode()
5199 public int hashCode()
5201 return m.hashCode();
5205 * Returns <code>true</code> if the underlying map contains no entries.
5207 * @return <code>true</code> if the map is empty.
5209 public boolean isEmpty()
5215 * Returns a unmodifiable set view of the keys in the underlying map.
5216 * The set is backed by the map, so that changes in one show up in the other.
5217 * Modifications made while an iterator is in progress cause undefined
5218 * behavior. These modifications are again limited to the values of
5221 * @return the set view of all keys.
5223 public Set<K> keySet()
5226 keys = new UnmodifiableSet<K>(m.keySet());
5231 * Blocks the addition of the entries in the supplied map.
5232 * This method never returns, throwing an exception instead.
5234 * @param m The map, the entries of which should be added
5235 * to the underlying map.
5236 * @throws UnsupportedOperationException as an unmodifiable
5237 * map does not support the <code>putAll</code> operation.
5239 public void putAll(Map<? extends K, ? extends V> m)
5241 throw new UnsupportedOperationException();
5245 * Blocks the removal of an entry from the map.
5246 * This method never returns, throwing an exception instead.
5248 * @param o The key of the entry to remove.
5249 * @return The value the key was associated with, or null
5250 * if no such mapping existed. Null is also returned
5251 * if the removed entry had a null key.
5252 * @throws UnsupportedOperationException as an unmodifiable
5253 * map does not support the <code>remove</code> operation.
5255 public V remove(Object o)
5257 throw new UnsupportedOperationException();
5262 * Returns the number of key-value mappings in the underlying map.
5263 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
5266 * @return the number of mappings.
5274 * Returns a textual representation of the map.
5276 * @return The map in the form of a <code>String</code>.
5278 public String toString()
5280 return m.toString();
5284 * Returns a unmodifiable collection view of the values in the underlying map.
5285 * The collection is backed by the map, so that changes in one show up in the other.
5286 * Modifications made while an iterator is in progress cause undefined
5287 * behavior. These modifications are again limited to the values of
5290 * @return the collection view of all values.
5292 public Collection<V> values()
5295 values = new UnmodifiableCollection<V>(m.values());
5298 } // class UnmodifiableMap
5301 * Returns an unmodifiable view of the given set. This allows
5302 * "read-only" access, although changes in the backing set show up
5303 * in this view. Attempts to modify the set directly or via iterators
5304 * will fail with {@link UnsupportedOperationException}.
5305 * Although this view prevents changes to the structure of the set and its
5306 * entries, the values referenced by the objects in the set can still be
5310 * The returned Set implements Serializable, but can only be serialized if
5311 * the set it wraps is likewise Serializable.
5313 * @param s the set to wrap
5314 * @return a read-only view of the set
5317 public static <T> Set<T> unmodifiableSet(Set<? extends T> s)
5319 return new UnmodifiableSet<T>(s);
5323 * The implementation of {@link #unmodifiableSet(Set)}. This class
5324 * name is required for compatibility with Sun's JDK serializability.
5326 * @author Eric Blake (ebb9@email.byu.edu)
5328 private static class UnmodifiableSet<T> extends UnmodifiableCollection<T>
5332 * Compatible with JDK 1.4.
5334 private static final long serialVersionUID = -9215047833775013803L;
5338 * @param s the set to wrap
5339 * @throws NullPointerException if s is null
5341 UnmodifiableSet(Set<? extends T> s)
5347 * Returns <code>true</code> if the object, o, is also an instance of
5348 * <code>Set</code> of the same size and with the same entries.
5350 * @return <code>true</code> if o is an equivalent set.
5352 public boolean equals(Object o)
5358 * Computes the hash code of this set, as the sum of the
5359 * hash codes of all elements within the set.
5361 * @return the hash code of the set.
5363 public int hashCode()
5365 return c.hashCode();
5367 } // class UnmodifiableSet
5370 * Returns an unmodifiable view of the given sorted map. This allows
5371 * "read-only" access, although changes in the backing map show up in this
5372 * view. Attempts to modify the map directly, via subviews, via collection
5373 * views, or iterators, will fail with {@link UnsupportedOperationException}.
5374 * Although this view prevents changes to the structure of the map and its
5375 * entries, the values referenced by the objects in the map can still be
5379 * The returned SortedMap implements Serializable, but can only be
5380 * serialized if the map it wraps is likewise Serializable.
5382 * @param m the map to wrap
5383 * @return a read-only view of the map
5386 public static <K, V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K,
5389 return new UnmodifiableSortedMap<K, V>(m);
5393 * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
5394 * class name is required for compatibility with Sun's JDK serializability.
5396 * @author Eric Blake (ebb9@email.byu.edu)
5398 private static class UnmodifiableSortedMap<K, V>
5399 extends UnmodifiableMap<K, V>
5400 implements SortedMap<K, V>
5403 * Compatible with JDK 1.4.
5405 private static final long serialVersionUID = -8806743815996713206L;
5408 * The wrapped map; stored both here and in the superclass to avoid
5409 * excessive casting.
5410 * @serial the wrapped map
5412 private final SortedMap<K, V> sm;
5416 * @param sm the map to wrap
5417 * @throws NullPointerException if sm is null
5419 UnmodifiableSortedMap(SortedMap<K, ? extends V> sm)
5422 this.sm = (SortedMap<K,V>) sm;
5426 * Returns the comparator used in sorting the underlying map,
5427 * or null if it is the keys' natural ordering.
5429 * @return the sorting comparator.
5431 public Comparator<? super K> comparator()
5433 return sm.comparator();
5437 * Returns the first (lowest sorted) key in the map.
5439 * @return the first key.
5440 * @throws NoSuchElementException if this map is empty.
5444 return sm.firstKey();
5448 * Returns a unmodifiable view of the portion of the map strictly less
5449 * than toKey. The view is backed by the underlying map, so changes in
5450 * one show up in the other. The submap supports all optional operations
5451 * of the original. This operation is equivalent to
5452 * <code>subMap(firstKey(), toKey)</code>.
5455 * The returned map throws an IllegalArgumentException any time a key is
5456 * used which is out of the range of toKey. Note that the endpoint, toKey,
5457 * is not included; if you want this value to be included, pass its successor
5458 * object in to toKey. For example, for Integers, you could request
5459 * <code>headMap(new Integer(limit.intValue() + 1))</code>.
5461 * @param toKey the exclusive upper range of the submap.
5462 * @return the submap.
5463 * @throws ClassCastException if toKey is not comparable to the map contents.
5464 * @throws IllegalArgumentException if this is a subMap, and toKey is out
5466 * @throws NullPointerException if toKey is null but the map does not allow
5469 public SortedMap<K, V> headMap(K toKey)
5471 return new UnmodifiableSortedMap<K, V>(sm.headMap(toKey));
5475 * Returns the last (highest sorted) key in the map.
5477 * @return the last key.
5478 * @throws NoSuchElementException if this map is empty.
5482 return sm.lastKey();
5486 * Returns a unmodifiable view of the portion of the map greater than or
5487 * equal to fromKey, and strictly less than toKey. The view is backed by
5488 * the underlying map, so changes in one show up in the other. The submap
5489 * supports all optional operations of the original.
5492 * The returned map throws an IllegalArgumentException any time a key is
5493 * used which is out of the range of fromKey and toKey. Note that the
5494 * lower endpoint is included, but the upper is not; if you want to
5495 * change the inclusion or exclusion of an endpoint, pass its successor
5496 * object in instead. For example, for Integers, you could request
5497 * <code>subMap(new Integer(lowlimit.intValue() + 1),
5498 * new Integer(highlimit.intValue() + 1))</code> to reverse
5499 * the inclusiveness of both endpoints.
5501 * @param fromKey the inclusive lower range of the submap.
5502 * @param toKey the exclusive upper range of the submap.
5503 * @return the submap.
5504 * @throws ClassCastException if fromKey or toKey is not comparable to
5506 * @throws IllegalArgumentException if this is a subMap, and fromKey or
5507 * toKey is out of range.
5508 * @throws NullPointerException if fromKey or toKey is null but the map
5509 * does not allow null keys.
5511 public SortedMap<K, V> subMap(K fromKey, K toKey)
5513 return new UnmodifiableSortedMap<K, V>(sm.subMap(fromKey, toKey));
5517 * Returns a unmodifiable view of the portion of the map greater than or
5518 * equal to fromKey. The view is backed by the underlying map, so changes
5519 * in one show up in the other. The submap supports all optional operations
5523 * The returned map throws an IllegalArgumentException any time a key is
5524 * used which is out of the range of fromKey. Note that the endpoint, fromKey, is
5525 * included; if you do not want this value to be included, pass its successor object in
5526 * to fromKey. For example, for Integers, you could request
5527 * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
5529 * @param fromKey the inclusive lower range of the submap
5530 * @return the submap
5531 * @throws ClassCastException if fromKey is not comparable to the map
5533 * @throws IllegalArgumentException if this is a subMap, and fromKey is out
5535 * @throws NullPointerException if fromKey is null but the map does not allow
5538 public SortedMap<K, V> tailMap(K fromKey)
5540 return new UnmodifiableSortedMap<K, V>(sm.tailMap(fromKey));
5542 } // class UnmodifiableSortedMap
5545 * Returns an unmodifiable view of the given sorted set. This allows
5546 * "read-only" access, although changes in the backing set show up
5547 * in this view. Attempts to modify the set directly, via subsets, or via
5548 * iterators, will fail with {@link UnsupportedOperationException}.
5549 * Although this view prevents changes to the structure of the set and its
5550 * entries, the values referenced by the objects in the set can still be
5554 * The returns SortedSet implements Serializable, but can only be
5555 * serialized if the set it wraps is likewise Serializable.
5557 * @param s the set to wrap
5558 * @return a read-only view of the set
5561 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)
5563 return new UnmodifiableSortedSet<T>(s);
5567 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
5568 * class name is required for compatibility with Sun's JDK serializability.
5570 * @author Eric Blake (ebb9@email.byu.edu)
5572 private static class UnmodifiableSortedSet<T> extends UnmodifiableSet<T>
5573 implements SortedSet<T>
5576 * Compatible with JDK 1.4.
5578 private static final long serialVersionUID = -4929149591599911165L;
5581 * The wrapped set; stored both here and in the superclass to avoid
5582 * excessive casting.
5583 * @serial the wrapped set
5585 private SortedSet<T> ss;
5589 * @param ss the set to wrap
5590 * @throws NullPointerException if ss is null
5592 UnmodifiableSortedSet(SortedSet<T> ss)
5599 * Returns the comparator used in sorting the underlying set,
5600 * or null if it is the elements' natural ordering.
5602 * @return the sorting comparator
5604 public Comparator<? super T> comparator()
5606 return ss.comparator();
5610 * Returns the first (lowest sorted) element in the underlying
5613 * @return the first element.
5614 * @throws NoSuchElementException if the set is empty.
5622 * Returns a unmodifiable view of the portion of the set strictly
5623 * less than toElement. The view is backed by the underlying set,
5624 * so changes in one show up in the other. The subset supports
5625 * all optional operations of the original. This operation
5626 * is equivalent to <code>subSet(first(), toElement)</code>.
5629 * The returned set throws an IllegalArgumentException any time an element is
5630 * used which is out of the range of toElement. Note that the endpoint, toElement,
5631 * is not included; if you want this value included, pass its successor object in to
5632 * toElement. For example, for Integers, you could request
5633 * <code>headSet(new Integer(limit.intValue() + 1))</code>.
5635 * @param toElement the exclusive upper range of the subset
5636 * @return the subset.
5637 * @throws ClassCastException if toElement is not comparable to the set
5639 * @throws IllegalArgumentException if this is a subSet, and toElement is out
5641 * @throws NullPointerException if toElement is null but the set does not
5642 * allow null elements.
5644 public SortedSet<T> headSet(T toElement)
5646 return new UnmodifiableSortedSet<T>(ss.headSet(toElement));
5650 * Returns the last (highest sorted) element in the underlying
5653 * @return the last element.
5654 * @throws NoSuchElementException if the set is empty.
5662 * Returns a unmodifiable view of the portion of the set greater than or
5663 * equal to fromElement, and strictly less than toElement. The view is backed by
5664 * the underlying set, so changes in one show up in the other. The subset
5665 * supports all optional operations of the original.
5668 * The returned set throws an IllegalArgumentException any time an element is
5669 * used which is out of the range of fromElement and toElement. Note that the
5670 * lower endpoint is included, but the upper is not; if you want to
5671 * change the inclusion or exclusion of an endpoint, pass its successor
5672 * object in instead. For example, for Integers, you can request
5673 * <code>subSet(new Integer(lowlimit.intValue() + 1),
5674 * new Integer(highlimit.intValue() + 1))</code> to reverse
5675 * the inclusiveness of both endpoints.
5677 * @param fromElement the inclusive lower range of the subset.
5678 * @param toElement the exclusive upper range of the subset.
5679 * @return the subset.
5680 * @throws ClassCastException if fromElement or toElement is not comparable
5681 * to the set contents.
5682 * @throws IllegalArgumentException if this is a subSet, and fromElement or
5683 * toElement is out of range.
5684 * @throws NullPointerException if fromElement or toElement is null but the
5685 * set does not allow null elements.
5687 public SortedSet<T> subSet(T fromElement, T toElement)
5689 return new UnmodifiableSortedSet<T>(ss.subSet(fromElement, toElement));
5693 * Returns a unmodifiable view of the portion of the set greater than or equal to
5694 * fromElement. The view is backed by the underlying set, so changes in one show up
5695 * in the other. The subset supports all optional operations of the original.
5698 * The returned set throws an IllegalArgumentException any time an element is
5699 * used which is out of the range of fromElement. Note that the endpoint,
5700 * fromElement, is included; if you do not want this value to be included, pass its
5701 * successor object in to fromElement. For example, for Integers, you could request
5702 * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
5704 * @param fromElement the inclusive lower range of the subset
5705 * @return the subset.
5706 * @throws ClassCastException if fromElement is not comparable to the set
5708 * @throws IllegalArgumentException if this is a subSet, and fromElement is
5710 * @throws NullPointerException if fromElement is null but the set does not
5711 * allow null elements.
5713 public SortedSet<T> tailSet(T fromElement)
5715 return new UnmodifiableSortedSet<T>(ss.tailSet(fromElement));
5717 } // class UnmodifiableSortedSet
5721 * Returns a dynamically typesafe view of the given collection,
5722 * where any modification is first checked to ensure that the type
5723 * of the new data is appropriate. Although the addition of
5724 * generics and parametrically-typed collections prevents an
5725 * incorrect type of element being added to a collection at
5726 * compile-time, via static type checking, this can be overridden by
5727 * casting. In contrast, wrapping the collection within a
5728 * dynamically-typesafe wrapper, using this and associated methods,
5729 * <emph>guarantees</emph> that the collection will only contain
5730 * elements of an appropriate type (provided it only contains such
5731 * at the type of wrapping, and all subsequent access is via the
5732 * wrapper). This can be useful for debugging the cause of a
5733 * <code>ClassCastException</code> caused by erroneous casting, or
5734 * for protecting collections from corruption by external libraries.
5737 * Since the collection might be a List or a Set, and those
5738 * have incompatible equals and hashCode requirements, this relies
5739 * on Object's implementation rather than passing those calls on to
5740 * the wrapped collection. The returned Collection implements
5741 * Serializable, but can only be serialized if the collection it
5742 * wraps is likewise Serializable.
5745 * @param c the collection to wrap in a dynamically typesafe wrapper
5746 * @param type the type of elements the collection should hold.
5747 * @return a dynamically typesafe view of the collection.
5751 public static <E> Collection<E> checkedCollection(Collection<E> c,
5754 return new CheckedCollection<E>(c, type);
5758 * The implementation of {@link #checkedCollection(Collection,Class)}. This
5759 * class name is required for compatibility with Sun's JDK serializability.
5761 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
5764 private static class CheckedCollection<E>
5765 implements Collection<E>, Serializable
5768 * Compatible with JDK 1.5.
5770 private static final long serialVersionUID = 1578914078182001775L;
5773 * The wrapped collection. Package visible for use by subclasses.
5774 * @serial the real collection
5776 final Collection<E> c;
5779 * The type of the elements of this collection.
5780 * @serial the element type.
5782 final Class<E> type;
5785 * Wrap a given collection.
5786 * @param c the collection to wrap
5787 * @param type the type to wrap
5788 * @throws NullPointerException if c is null
5790 CheckedCollection(Collection<E> c, Class<E> type)
5795 throw new NullPointerException();
5799 * Adds the supplied object to the collection, on the condition that
5800 * it is of the correct type.
5802 * @param o the object to add.
5803 * @return <code>true</code> if the collection was modified as a result
5805 * @throws ClassCastException if the object is not of the correct type.
5807 public boolean add(E o)
5809 if (type.isInstance(o))
5812 throw new ClassCastException("The element is of the incorrect type.");
5816 * Adds the elements of the specified collection to the backing collection,
5817 * provided they are all of the correct type.
5819 * @param coll the collection to add.
5820 * @return <code>true</code> if the collection was modified as a result
5822 * @throws ClassCastException if <code>c</code> contained elements of an
5825 public boolean addAll(Collection<? extends E> coll)
5827 Collection<E> typedColl = (Collection<E>) c;
5828 for (E element : typedColl)
5830 if (!type.isInstance(element))
5831 throw new ClassCastException("A member of the collection is not of the correct type.");
5833 return c.addAll(typedColl);
5837 * Removes all elements from the underlying collection.
5845 * Test whether the underlying collection contains a given object as one
5848 * @param o the element to look for.
5849 * @return <code>true</code> if the underlying collection contains at least
5850 * one element e such that
5851 * <code>o == null ? e == null : o.equals(e)</code>.
5852 * @throws ClassCastException if the type of o is not a valid type for the
5853 * underlying collection.
5854 * @throws NullPointerException if o is null and the underlying collection
5855 * doesn't support null values.
5857 public boolean contains(Object o)
5859 return c.contains(o);
5863 * Test whether the underlying collection contains every element in a given
5866 * @param coll the collection to test for.
5867 * @return <code>true</code> if for every element o in c, contains(o) would
5868 * return <code>true</code>.
5869 * @throws ClassCastException if the type of any element in c is not a
5870 * valid type for the underlying collection.
5871 * @throws NullPointerException if some element of c is null and the
5872 * underlying collection does not support
5874 * @throws NullPointerException if c itself is null.
5876 public boolean containsAll(Collection<?> coll)
5878 return c.containsAll(coll);
5882 * Tests whether the underlying collection is empty, that is,
5885 * @return <code>true</code> if this collection contains no elements.
5887 public boolean isEmpty()
5893 * Obtain an Iterator over the underlying collection, which maintains
5894 * its checked nature.
5896 * @return a Iterator over the elements of the underlying
5897 * collection, in any order.
5899 public Iterator<E> iterator()
5901 return new CheckedIterator<E>(c.iterator(), type);
5905 * Removes the supplied object from the collection, if it exists.
5907 * @param o The object to remove.
5908 * @return <code>true</code> if the object was removed (i.e. the underlying
5909 * collection returned 1 or more instances of o).
5911 public boolean remove(Object o)
5917 * Removes all objects in the supplied collection from the backing
5918 * collection, if they exist within it.
5920 * @param coll the collection of objects to remove.
5921 * @return <code>true</code> if the collection was modified.
5923 public boolean removeAll(Collection<?> coll)
5925 return c.removeAll(coll);
5929 * Retains all objects specified by the supplied collection which exist
5930 * within the backing collection, and removes all others.
5932 * @param coll the collection of objects to retain.
5933 * @return <code>true</code> if the collection was modified.
5935 public boolean retainAll(Collection<?> coll)
5937 return c.retainAll(coll);
5941 * Retrieves the number of elements in the underlying collection.
5943 * @return the number of elements in the collection.
5951 * Copy the current contents of the underlying collection into an array.
5953 * @return an array of type Object[] with a length equal to the size of the
5954 * underlying collection and containing the elements currently in
5955 * the underlying collection, in any order.
5957 public Object[] toArray()
5964 * Copy the current contents of the underlying collection into an array. If
5965 * the array passed as an argument has length less than the size of the
5966 * underlying collection, an array of the same run-time type as a, with a
5967 * length equal to the size of the underlying collection, is allocated
5971 * Otherwise, a itself is used. The elements of the underlying collection
5972 * are copied into it, and if there is space in the array, the following
5973 * element is set to null. The resultant array is returned.
5976 * <emph>Note</emph>: The fact that the following element is set to null
5977 * is only useful if it is known that this collection does not contain
5978 * any null elements.
5980 * @param a the array to copy this collection into.
5981 * @return an array containing the elements currently in the underlying
5982 * collection, in any order.
5983 * @throws ArrayStoreException if the type of any element of the
5984 * collection is not a subtype of the element type of a.
5986 public <S> S[] toArray(S[] a)
5988 return c.toArray(a);
5992 * A textual representation of the unmodifiable collection.
5994 * @return The checked collection in the form of a <code>String</code>.
5996 public String toString()
5998 return c.toString();
6000 } // class CheckedCollection
6003 * The implementation of the various iterator methods in the
6006 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6009 private static class CheckedIterator<E>
6010 implements Iterator<E>
6013 * The wrapped iterator.
6015 private final Iterator<E> i;
6018 * The type of the elements of this collection.
6019 * @serial the element type.
6021 final Class<E> type;
6024 * Only trusted code creates a wrapper.
6025 * @param i the wrapped iterator
6026 * @param type the type of the elements within the checked list.
6028 CheckedIterator(Iterator<E> i, Class<E> type)
6035 * Obtains the next element in the underlying collection.
6037 * @return the next element in the collection.
6038 * @throws NoSuchElementException if there are no more elements.
6046 * Tests whether there are still elements to be retrieved from the
6047 * underlying collection by <code>next()</code>. When this method
6048 * returns <code>true</code>, an exception will not be thrown on calling
6049 * <code>next()</code>.
6051 * @return <code>true</code> if there is at least one more element in the
6052 * underlying collection.
6054 public boolean hasNext()
6060 * Removes the next element from the collection.
6062 public void remove()
6066 } // class CheckedIterator
6070 * Returns a dynamically typesafe view of the given list,
6071 * where any modification is first checked to ensure that the type
6072 * of the new data is appropriate. Although the addition of
6073 * generics and parametrically-typed collections prevents an
6074 * incorrect type of element being added to a collection at
6075 * compile-time, via static type checking, this can be overridden by
6076 * casting. In contrast, wrapping the collection within a
6077 * dynamically-typesafe wrapper, using this and associated methods,
6078 * <emph>guarantees</emph> that the collection will only contain
6079 * elements of an appropriate type (provided it only contains such
6080 * at the type of wrapping, and all subsequent access is via the
6081 * wrapper). This can be useful for debugging the cause of a
6082 * <code>ClassCastException</code> caused by erroneous casting, or
6083 * for protecting collections from corruption by external libraries.
6086 * The returned List implements Serializable, but can only be serialized if
6087 * the list it wraps is likewise Serializable. In addition, if the wrapped
6088 * list implements RandomAccess, this does too.
6091 * @param l the list to wrap
6092 * @param type the type of the elements within the checked list.
6093 * @return a dynamically typesafe view of the list
6097 public static <E> List<E> checkedList(List<E> l, Class<E> type)
6099 if (l instanceof RandomAccess)
6100 return new CheckedRandomAccessList<E>(l, type);
6101 return new CheckedList<E>(l, type);
6105 * The implementation of {@link #checkedList(List,Class)} for sequential
6106 * lists. This class name is required for compatibility with Sun's JDK
6109 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6112 private static class CheckedList<E>
6113 extends CheckedCollection<E>
6117 * Compatible with JDK 1.5.
6119 private static final long serialVersionUID = 65247728283967356L;
6122 * The wrapped list; stored both here and in the superclass to avoid
6123 * excessive casting. Package visible for use by subclass.
6124 * @serial the wrapped list
6129 * Wrap a given list.
6130 * @param l the list to wrap
6131 * @param type the type of the elements within the checked list.
6132 * @throws NullPointerException if l is null
6134 CheckedList(List<E> l, Class<E> type)
6141 * Adds the supplied element to the underlying list at the specified
6142 * index, provided it is of the right type.
6144 * @param index The index at which to place the new element.
6145 * @param o the object to add.
6146 * @throws ClassCastException if the type of the object is not a
6147 * valid type for the underlying collection.
6149 public void add(int index, E o)
6151 if (type.isInstance(o))
6154 throw new ClassCastException("The object is of the wrong type.");
6158 * Adds the members of the supplied collection to the underlying
6159 * collection at the specified index, provided they are all of the
6162 * @param index the index at which to place the new element.
6163 * @param c the collections of objects to add.
6164 * @throws ClassCastException if the type of any element in c is not a
6165 * valid type for the underlying collection.
6167 public boolean addAll(int index, Collection<? extends E> coll)
6169 Collection<E> typedColl = (Collection<E>) coll;
6170 for (E element : typedColl)
6172 if (!type.isInstance(element))
6173 throw new ClassCastException("A member of the collection is not of the correct type.");
6175 return list.addAll(index, coll);
6179 * Returns <code>true</code> if the object, o, is an instance of
6180 * <code>List</code> with the same size and elements
6181 * as the underlying list.
6183 * @param o The object to compare.
6184 * @return <code>true</code> if o is equivalent to the underlying list.
6186 public boolean equals(Object o)
6188 return list.equals(o);
6192 * Retrieves the element at a given index in the underlying list.
6194 * @param index the index of the element to be returned
6195 * @return the element at the specified index in the underlying list
6196 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
6198 public E get(int index)
6200 return list.get(index);
6204 * Computes the hash code for the underlying list.
6205 * The exact computation is described in the documentation
6206 * of the <code>List</code> interface.
6208 * @return The hash code of the underlying list.
6209 * @see List#hashCode()
6211 public int hashCode()
6213 return list.hashCode();
6217 * Obtain the first index at which a given object is to be found in the
6220 * @param o the object to search for
6221 * @return the least integer n such that <code>o == null ? get(n) == null :
6222 * o.equals(get(n))</code>, or -1 if there is no such index.
6223 * @throws ClassCastException if the type of o is not a valid
6224 * type for the underlying list.
6225 * @throws NullPointerException if o is null and the underlying
6226 * list does not support null values.
6228 public int indexOf(Object o)
6230 return list.indexOf(o);
6234 * Obtain the last index at which a given object is to be found in the
6237 * @return the greatest integer n such that
6238 * <code>o == null ? get(n) == null : o.equals(get(n))</code>,
6239 * or -1 if there is no such index.
6240 * @throws ClassCastException if the type of o is not a valid
6241 * type for the underlying list.
6242 * @throws NullPointerException if o is null and the underlying
6243 * list does not support null values.
6245 public int lastIndexOf(Object o)
6247 return list.lastIndexOf(o);
6251 * Obtains a list iterator over the underlying list, starting at the
6252 * beginning and maintaining the checked nature of this list.
6254 * @return a <code>CheckedListIterator</code> over the elements of the
6255 * underlying list, in order, starting at the beginning.
6257 public ListIterator<E> listIterator()
6259 return new CheckedListIterator<E>(list.listIterator(), type);
6263 * Obtains a list iterator over the underlying list, starting at the
6264 * specified index and maintaining the checked nature of this list. An
6265 * initial call to <code>next()</code> will retrieve the element at the
6266 * specified index, and an initial call to <code>previous()</code> will
6267 * retrieve the element at index - 1.
6269 * @param index the position, between 0 and size() inclusive, to begin the
6271 * @return a <code>CheckedListIterator</code> over the elements of the
6272 * underlying list, in order, starting at the specified index.
6273 * @throws IndexOutOfBoundsException if index < 0 || index > size()
6275 public ListIterator<E> listIterator(int index)
6277 return new CheckedListIterator<E>(list.listIterator(index), type);
6281 * Removes the element at the specified index.
6283 * @param index The index of the element to remove.
6284 * @return the removed element.
6286 public E remove(int index)
6288 return list.remove(index);
6292 * Replaces the element at the specified index in the underlying list
6293 * with that supplied.
6295 * @param index the index of the element to replace.
6296 * @param o the new object to place at the specified index.
6297 * @return the replaced element.
6299 public E set(int index, E o)
6301 return list.set(index, o);
6305 * Obtain a List view of a subsection of the underlying list, from
6306 * fromIndex (inclusive) to toIndex (exclusive). If the two indices
6307 * are equal, the sublist is empty. The returned list will be
6308 * checked, like this list. Changes to the elements of the
6309 * returned list will be reflected in the underlying list. The effect
6310 * of structural modifications is undefined.
6312 * @param fromIndex the index that the returned list should start from
6314 * @param toIndex the index that the returned list should go
6316 * @return a List backed by a subsection of the underlying list.
6317 * @throws IndexOutOfBoundsException if fromIndex < 0
6318 * || toIndex > size() || fromIndex > toIndex.
6320 public List<E> subList(int fromIndex, int toIndex)
6322 return checkedList(list.subList(fromIndex, toIndex), type);
6324 } // class CheckedList
6327 * The implementation of {@link #checkedList(List)} for random-access
6328 * lists. This class name is required for compatibility with Sun's JDK
6331 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6334 private static final class CheckedRandomAccessList<E>
6335 extends CheckedList<E>
6336 implements RandomAccess
6339 * Compatible with JDK 1.5.
6341 private static final long serialVersionUID = 1638200125423088369L;
6344 * Wrap a given list.
6345 * @param l the list to wrap
6346 * @param type the type of the elements within the checked list.
6347 * @throws NullPointerException if l is null
6349 CheckedRandomAccessList(List<E> l, Class<E> type)
6353 } // class CheckedRandomAccessList
6356 * The implementation of {@link CheckedList#listIterator()}.
6358 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6361 private static final class CheckedListIterator<E>
6362 extends CheckedIterator<E>
6363 implements ListIterator<E>
6366 * The wrapped iterator, stored both here and in the superclass to
6367 * avoid excessive casting.
6369 private final ListIterator<E> li;
6372 * Only trusted code creates a wrapper.
6373 * @param li the wrapped iterator
6375 CheckedListIterator(ListIterator<E> li, Class<E> type)
6382 * Adds the supplied object at the current iterator position, provided
6383 * it is of the correct type.
6385 * @param o the object to add.
6386 * @throws ClassCastException if the type of the object is not a
6387 * valid type for the underlying collection.
6389 public void add(E o)
6391 if (type.isInstance(o))
6394 throw new ClassCastException("The object is of the wrong type.");
6398 * Tests whether there are still elements to be retrieved from the
6399 * underlying collection by <code>previous()</code>. When this method
6400 * returns <code>true</code>, an exception will not be thrown on calling
6401 * <code>previous()</code>.
6403 * @return <code>true</code> if there is at least one more element prior
6404 * to the current position in the underlying list.
6406 public boolean hasPrevious()
6408 return li.hasPrevious();
6412 * Find the index of the element that would be returned by a call to next.
6413 * If <code>hasNext()</code> returns <code>false</code>, this returns the
6416 * @return the index of the element that would be returned by
6417 * <code>next()</code>.
6419 public int nextIndex()
6421 return li.nextIndex();
6425 * Obtains the previous element in the underlying list.
6427 * @return the previous element in the list.
6428 * @throws NoSuchElementException if there are no more prior elements.
6432 return li.previous();
6436 * Find the index of the element that would be returned by a call to
6437 * previous. If <code>hasPrevious()</code> returns <code>false</code>,
6440 * @return the index of the element that would be returned by
6441 * <code>previous()</code>.
6443 public int previousIndex()
6445 return li.previousIndex();
6449 * Sets the next element to that supplied, provided that it is of the
6452 * @param o The new object to replace the existing one.
6453 * @throws ClassCastException if the type of the object is not a
6454 * valid type for the underlying collection.
6456 public void set(E o)
6458 if (type.isInstance(o))
6461 throw new ClassCastException("The object is of the wrong type.");
6463 } // class CheckedListIterator
6467 * Returns a dynamically typesafe view of the given map,
6468 * where any modification is first checked to ensure that the type
6469 * of the new data is appropriate. Although the addition of
6470 * generics and parametrically-typed collections prevents an
6471 * incorrect type of element being added to a collection at
6472 * compile-time, via static type checking, this can be overridden by
6473 * casting. In contrast, wrapping the collection within a
6474 * dynamically-typesafe wrapper, using this and associated methods,
6475 * <emph>guarantees</emph> that the collection will only contain
6476 * elements of an appropriate type (provided it only contains such
6477 * at the type of wrapping, and all subsequent access is via the
6478 * wrapper). This can be useful for debugging the cause of a
6479 * <code>ClassCastException</code> caused by erroneous casting, or
6480 * for protecting collections from corruption by external libraries.
6483 * The returned Map implements Serializable, but can only be serialized if
6484 * the map it wraps is likewise Serializable.
6487 * @param m the map to wrap
6488 * @param keyType the dynamic type of the map's keys.
6489 * @param valueType the dynamic type of the map's values.
6490 * @return a dynamically typesafe view of the map
6493 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType,
6496 return new CheckedMap<K, V>(m, keyType, valueType);
6500 * The implementation of {@link #checkedMap(Map)}. This
6501 * class name is required for compatibility with Sun's JDK serializability.
6503 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6506 private static class CheckedMap<K, V>
6507 implements Map<K, V>, Serializable
6510 * Compatible with JDK 1.5.
6512 private static final long serialVersionUID = 5742860141034234728L;
6516 * @serial the real map
6518 private final Map<K, V> m;
6521 * The type of the map's keys.
6522 * @serial the key type.
6524 final Class<K> keyType;
6527 * The type of the map's values.
6528 * @serial the value type.
6530 final Class<V> valueType;
6533 * Cache the entry set.
6535 private transient Set<Map.Entry<K, V>> entries;
6538 * Cache the key set.
6540 private transient Set<K> keys;
6543 * Cache the value collection.
6545 private transient Collection<V> values;
6549 * @param m the map to wrap
6550 * @param keyType the dynamic type of the map's keys.
6551 * @param valueType the dynamic type of the map's values.
6552 * @throws NullPointerException if m is null
6554 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType)
6557 this.keyType = keyType;
6558 this.valueType = valueType;
6560 throw new NullPointerException();
6564 * Clears all pairs from the map.
6572 * Returns <code>true</code> if the underlying map contains a mapping for
6575 * @param key the key to search for
6576 * @return <code>true</code> if the map contains the key
6577 * @throws ClassCastException if the key is of an inappropriate type
6578 * @throws NullPointerException if key is <code>null</code> but the map
6579 * does not permit null keys
6581 public boolean containsKey(Object key)
6583 return m.containsKey(key);
6587 * Returns <code>true</code> if the underlying map contains at least one
6588 * mapping with the given value. In other words, it returns
6589 * <code>true</code> if a value v exists where
6590 * <code>(value == null ? v == null : value.equals(v))</code>.
6591 * This usually requires linear time.
6593 * @param value the value to search for
6594 * @return <code>true</code> if the map contains the value
6595 * @throws ClassCastException if the type of the value is not a valid type
6597 * @throws NullPointerException if the value is null and the map doesn't
6598 * support null values.
6600 public boolean containsValue(Object value)
6602 return m.containsValue(value);
6607 * Returns a checked set view of the entries in the underlying map.
6608 * Each element in the set is a unmodifiable variant of
6609 * <code>Map.Entry</code>.
6612 * The set is backed by the map, so that changes in one show up in the
6613 * other. Modifications made while an iterator is in progress cause
6614 * undefined behavior.
6617 * @return the checked set view of all mapping entries.
6620 public Set<Map.Entry<K, V>> entrySet()
6622 if (entries == null)
6624 Class<Map.Entry<K,V>> klass =
6625 (Class<Map.Entry<K,V>>) (Class) Map.Entry.class;
6626 entries = new CheckedEntrySet<Map.Entry<K,V>,K,V>(m.entrySet(),
6635 * The implementation of {@link CheckedMap#entrySet()}. This class
6636 * is <emph>not</emph> serializable.
6638 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6641 private static final class CheckedEntrySet<E,SK,SV>
6642 extends CheckedSet<E>
6645 * The type of the map's keys.
6646 * @serial the key type.
6648 private final Class<SK> keyType;
6651 * The type of the map's values.
6652 * @serial the value type.
6654 private final Class<SV> valueType;
6657 * Wrap a given set of map entries.
6659 * @param s the set to wrap.
6660 * @param type the type of the set's entries.
6661 * @param keyType the type of the map's keys.
6662 * @param valueType the type of the map's values.
6664 CheckedEntrySet(Set<E> s, Class<E> type, Class<SK> keyType,
6665 Class<SV> valueType)
6668 this.keyType = keyType;
6669 this.valueType = valueType;
6672 // The iterator must return checked map entries.
6673 public Iterator<E> iterator()
6675 return new CheckedIterator<E>(c.iterator(), type)
6678 * Obtains the next element from the underlying set of
6681 * @return the next element in the collection.
6682 * @throws NoSuchElementException if there are no more elements.
6686 final Map.Entry e = (Map.Entry) super.next();
6687 return (E) new Map.Entry()
6690 * Returns <code>true</code> if the object, o, is also a map
6691 * entry with an identical key and value.
6693 * @param o the object to compare.
6694 * @return <code>true</code> if o is an equivalent map entry.
6696 public boolean equals(Object o)
6702 * Returns the key of this map entry.
6706 public Object getKey()
6712 * Returns the value of this map entry.
6714 * @return the value.
6716 public Object getValue()
6718 return e.getValue();
6722 * Computes the hash code of this map entry.
6723 * The computation is described in the <code>Map</code>
6724 * interface documentation.
6726 * @return the hash code of this entry.
6727 * @see Map#hashCode()
6729 public int hashCode()
6731 return e.hashCode();
6735 * Sets the value of this map entry, provided it is of the
6738 * @param value The new value.
6739 * @throws ClassCastException if the type of the value is not
6740 * a valid type for the underlying
6743 public Object setValue(Object value)
6745 if (valueType.isInstance(value))
6746 return e.setValue(value);
6748 throw new ClassCastException("The value is of the wrong type.");
6752 * Returns a textual representation of the map entry.
6754 * @return The map entry as a <code>String</code>.
6756 public String toString()
6758 return e.toString();
6764 } // class CheckedEntrySet
6767 * Returns <code>true</code> if the object, o, is also an instance
6768 * of <code>Map</code> with an equal set of map entries.
6770 * @param o The object to compare.
6771 * @return <code>true</code> if o is an equivalent map.
6773 public boolean equals(Object o)
6779 * Returns the value associated with the supplied key or
6780 * null if no such mapping exists. An ambiguity can occur
6781 * if null values are accepted by the underlying map.
6782 * In this case, <code>containsKey()</code> can be used
6783 * to separate the two possible cases of a null result.
6785 * @param key The key to look up.
6786 * @return the value associated with the key, or null if key not in map.
6787 * @throws ClassCastException if the key is an inappropriate type.
6788 * @throws NullPointerException if this map does not accept null keys.
6789 * @see #containsKey(Object)
6791 public V get(Object key)
6797 * Adds a new pair to the map, provided both the key and the value are
6798 * of the correct types.
6800 * @param key The new key.
6801 * @param value The new value.
6802 * @return the previous value of the key, or null if there was no mapping.
6803 * @throws ClassCastException if the type of the key or the value is
6804 * not a valid type for the underlying map.
6806 public V put(K key, V value)
6808 if (keyType.isInstance(key))
6810 if (valueType.isInstance(value))
6811 return m.put(key,value);
6813 throw new ClassCastException("The value is of the wrong type.");
6815 throw new ClassCastException("The key is of the wrong type.");
6819 * Computes the hash code for the underlying map, as the sum
6820 * of the hash codes of all entries.
6822 * @return The hash code of the underlying map.
6823 * @see Map.Entry#hashCode()
6825 public int hashCode()
6827 return m.hashCode();
6831 * Returns <code>true</code> if the underlying map contains no entries.
6833 * @return <code>true</code> if the map is empty.
6835 public boolean isEmpty()
6842 * Returns a checked set view of the keys in the underlying map.
6843 * The set is backed by the map, so that changes in one show up in the
6847 * Modifications made while an iterator is in progress cause undefined
6848 * behavior. These modifications are again limited to the values of
6852 * @return the set view of all keys.
6854 public Set<K> keySet()
6857 keys = new CheckedSet<K>(m.keySet(), keyType);
6862 * Adds all pairs within the supplied map to the underlying map,
6863 * provided they are all have the correct key and value types.
6865 * @param m the map, the entries of which should be added
6866 * to the underlying map.
6867 * @throws ClassCastException if the type of a key or value is
6868 * not a valid type for the underlying map.
6870 public void putAll(Map<? extends K, ? extends V> map)
6872 Map<K,V> typedMap = (Map<K,V>) map;
6873 for (Map.Entry<K,V> entry : typedMap.entrySet())
6875 if (!keyType.isInstance(entry.getKey()))
6876 throw new ClassCastException("A key is of the wrong type.");
6877 if (!valueType.isInstance(entry.getValue()))
6878 throw new ClassCastException("A value is of the wrong type.");
6884 * Removes a pair from the map.
6886 * @param o The key of the entry to remove.
6887 * @return The value the key was associated with, or null
6888 * if no such mapping existed. Null is also returned
6889 * if the removed entry had a null key.
6890 * @throws UnsupportedOperationException as an unmodifiable
6891 * map does not support the <code>remove</code> operation.
6893 public V remove(Object o)
6900 * Returns the number of key-value mappings in the underlying map.
6901 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
6904 * @return the number of mappings.
6912 * Returns a textual representation of the map.
6914 * @return The map in the form of a <code>String</code>.
6916 public String toString()
6918 return m.toString();
6923 * Returns a unmodifiable collection view of the values in the underlying
6924 * map. The collection is backed by the map, so that changes in one show
6928 * Modifications made while an iterator is in progress cause undefined
6929 * behavior. These modifications are again limited to the values of
6933 * @return the collection view of all values.
6935 public Collection<V> values()
6938 values = new CheckedCollection<V>(m.values(), valueType);
6941 } // class CheckedMap
6945 * Returns a dynamically typesafe view of the given set,
6946 * where any modification is first checked to ensure that the type
6947 * of the new data is appropriate. Although the addition of
6948 * generics and parametrically-typed collections prevents an
6949 * incorrect type of element being added to a collection at
6950 * compile-time, via static type checking, this can be overridden by
6951 * casting. In contrast, wrapping the collection within a
6952 * dynamically-typesafe wrapper, using this and associated methods,
6953 * <emph>guarantees</emph> that the collection will only contain
6954 * elements of an appropriate type (provided it only contains such
6955 * at the type of wrapping, and all subsequent access is via the
6956 * wrapper). This can be useful for debugging the cause of a
6957 * <code>ClassCastException</code> caused by erroneous casting, or
6958 * for protecting collections from corruption by external libraries.
6961 * The returned Set implements Serializable, but can only be serialized if
6962 * the set it wraps is likewise Serializable.
6965 * @param s the set to wrap.
6966 * @param type the type of the elements within the checked list.
6967 * @return a dynamically typesafe view of the set
6970 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)
6972 return new CheckedSet<E>(s, type);
6976 * The implementation of {@link #checkedSet(Set)}. This class
6977 * name is required for compatibility with Sun's JDK serializability.
6979 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6982 private static class CheckedSet<E>
6983 extends CheckedCollection<E>
6987 * Compatible with JDK 1.5.
6989 private static final long serialVersionUID = 4694047833775013803L;
6994 * @param s the set to wrap
6995 * @throws NullPointerException if s is null
6997 CheckedSet(Set<E> s, Class<E> type)
7003 * Returns <code>true</code> if the object, o, is also an instance of
7004 * <code>Set</code> of the same size and with the same entries.
7006 * @return <code>true</code> if o is an equivalent set.
7008 public boolean equals(Object o)
7014 * Computes the hash code of this set, as the sum of the
7015 * hash codes of all elements within the set.
7017 * @return the hash code of the set.
7019 public int hashCode()
7021 return c.hashCode();
7023 } // class CheckedSet
7027 * Returns a dynamically typesafe view of the given sorted map,
7028 * where any modification is first checked to ensure that the type
7029 * of the new data is appropriate. Although the addition of
7030 * generics and parametrically-typed collections prevents an
7031 * incorrect type of element being added to a collection at
7032 * compile-time, via static type checking, this can be overridden by
7033 * casting. In contrast, wrapping the collection within a
7034 * dynamically-typesafe wrapper, using this and associated methods,
7035 * <emph>guarantees</emph> that the collection will only contain
7036 * elements of an appropriate type (provided it only contains such
7037 * at the type of wrapping, and all subsequent access is via the
7038 * wrapper). This can be useful for debugging the cause of a
7039 * <code>ClassCastException</code> caused by erroneous casting, or
7040 * for protecting collections from corruption by external libraries.
7043 * The returned SortedMap implements Serializable, but can only be
7044 * serialized if the map it wraps is likewise Serializable.
7047 * @param m the map to wrap.
7048 * @param keyType the dynamic type of the map's keys.
7049 * @param valueType the dynamic type of the map's values.
7050 * @return a dynamically typesafe view of the map
7053 public static <K, V> SortedMap<K, V> checkedSortedMap(SortedMap<K, V> m,
7057 return new CheckedSortedMap<K, V>(m, keyType, valueType);
7061 * The implementation of {@link #checkedSortedMap(SortedMap,Class,Class)}.
7062 * This class name is required for compatibility with Sun's JDK
7065 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7067 private static class CheckedSortedMap<K, V>
7068 extends CheckedMap<K, V>
7069 implements SortedMap<K, V>
7072 * Compatible with JDK 1.5.
7074 private static final long serialVersionUID = 1599671320688067438L;
7077 * The wrapped map; stored both here and in the superclass to avoid
7078 * excessive casting.
7079 * @serial the wrapped map
7081 private final SortedMap<K, V> sm;
7086 * @param sm the map to wrap
7087 * @param keyType the dynamic type of the map's keys.
7088 * @param valueType the dynamic type of the map's values.
7089 * @throws NullPointerException if sm is null
7091 CheckedSortedMap(SortedMap<K, V> sm, Class<K> keyType, Class<V> valueType)
7093 super(sm, keyType, valueType);
7098 * Returns the comparator used in sorting the underlying map,
7099 * or null if it is the keys' natural ordering.
7101 * @return the sorting comparator.
7103 public Comparator<? super K> comparator()
7105 return sm.comparator();
7109 * Returns the first (lowest sorted) key in the map.
7111 * @return the first key.
7112 * @throws NoSuchElementException if this map is empty.
7116 return sm.firstKey();
7121 * Returns a checked view of the portion of the map strictly less
7122 * than toKey. The view is backed by the underlying map, so changes in
7123 * one show up in the other. The submap supports all optional operations
7124 * of the original. This operation is equivalent to
7125 * <code>subMap(firstKey(), toKey)</code>.
7128 * The returned map throws an IllegalArgumentException any time a key is
7129 * used which is out of the range of toKey. Note that the endpoint, toKey,
7130 * is not included; if you want this value to be included, pass its
7131 * successor object in to toKey. For example, for Integers, you could
7132 * request <code>headMap(new Integer(limit.intValue() + 1))</code>.
7135 * @param toKey the exclusive upper range of the submap.
7136 * @return the submap.
7137 * @throws ClassCastException if toKey is not comparable to the map
7139 * @throws IllegalArgumentException if this is a subMap, and toKey is out
7141 * @throws NullPointerException if toKey is null but the map does not allow
7144 public SortedMap<K, V> headMap(K toKey)
7146 return new CheckedSortedMap<K, V>(sm.headMap(toKey), keyType, valueType);
7150 * Returns the last (highest sorted) key in the map.
7152 * @return the last key.
7153 * @throws NoSuchElementException if this map is empty.
7157 return sm.lastKey();
7162 * Returns a checked view of the portion of the map greater than or
7163 * equal to fromKey, and strictly less than toKey. The view is backed by
7164 * the underlying map, so changes in one show up in the other. The submap
7165 * supports all optional operations of the original.
7168 * The returned map throws an IllegalArgumentException any time a key is
7169 * used which is out of the range of fromKey and toKey. Note that the
7170 * lower endpoint is included, but the upper is not; if you want to
7171 * change the inclusion or exclusion of an endpoint, pass its successor
7172 * object in instead. For example, for Integers, you could request
7173 * <code>subMap(new Integer(lowlimit.intValue() + 1),
7174 * new Integer(highlimit.intValue() + 1))</code> to reverse
7175 * the inclusiveness of both endpoints.
7178 * @param fromKey the inclusive lower range of the submap.
7179 * @param toKey the exclusive upper range of the submap.
7180 * @return the submap.
7181 * @throws ClassCastException if fromKey or toKey is not comparable to
7183 * @throws IllegalArgumentException if this is a subMap, and fromKey or
7184 * toKey is out of range.
7185 * @throws NullPointerException if fromKey or toKey is null but the map
7186 * does not allow null keys.
7188 public SortedMap<K, V> subMap(K fromKey, K toKey)
7190 return new CheckedSortedMap<K, V>(sm.subMap(fromKey, toKey), keyType,
7196 * Returns a checked view of the portion of the map greater than or
7197 * equal to fromKey. The view is backed by the underlying map, so changes
7198 * in one show up in the other. The submap supports all optional operations
7202 * The returned map throws an IllegalArgumentException any time a key is
7203 * used which is out of the range of fromKey. Note that the endpoint,
7204 * fromKey, is included; if you do not want this value to be included,
7205 * pass its successor object in to fromKey. For example, for Integers,
7207 * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
7210 * @param fromKey the inclusive lower range of the submap
7211 * @return the submap
7212 * @throws ClassCastException if fromKey is not comparable to the map
7214 * @throws IllegalArgumentException if this is a subMap, and fromKey is out
7216 * @throws NullPointerException if fromKey is null but the map does not
7219 public SortedMap<K, V> tailMap(K fromKey)
7221 return new CheckedSortedMap<K, V>(sm.tailMap(fromKey), keyType,
7224 } // class CheckedSortedMap
7228 * Returns a dynamically typesafe view of the given sorted set,
7229 * where any modification is first checked to ensure that the type
7230 * of the new data is appropriate. Although the addition of
7231 * generics and parametrically-typed collections prevents an
7232 * incorrect type of element being added to a collection at
7233 * compile-time, via static type checking, this can be overridden by
7234 * casting. In contrast, wrapping the collection within a
7235 * dynamically-typesafe wrapper, using this and associated methods,
7236 * <emph>guarantees</emph> that the collection will only contain
7237 * elements of an appropriate type (provided it only contains such
7238 * at the type of wrapping, and all subsequent access is via the
7239 * wrapper). This can be useful for debugging the cause of a
7240 * <code>ClassCastException</code> caused by erroneous casting, or
7241 * for protecting collections from corruption by external libraries.
7244 * The returned SortedSet implements Serializable, but can only be
7245 * serialized if the set it wraps is likewise Serializable.
7248 * @param s the set to wrap.
7249 * @param type the type of the set's elements.
7250 * @return a dynamically typesafe view of the set
7253 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
7256 return new CheckedSortedSet<E>(s, type);
7260 * The implementation of {@link #checkedSortedSet(SortedSet,Class)}. This
7261 * class name is required for compatibility with Sun's JDK serializability.
7263 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7266 private static class CheckedSortedSet<E>
7267 extends CheckedSet<E>
7268 implements SortedSet<E>
7271 * Compatible with JDK 1.4.
7273 private static final long serialVersionUID = 1599911165492914959L;
7276 * The wrapped set; stored both here and in the superclass to avoid
7277 * excessive casting.
7279 * @serial the wrapped set
7281 private SortedSet<E> ss;
7286 * @param ss the set to wrap.
7287 * @param type the type of the set's elements.
7288 * @throws NullPointerException if ss is null
7290 CheckedSortedSet(SortedSet<E> ss, Class<E> type)
7297 * Returns the comparator used in sorting the underlying set,
7298 * or null if it is the elements' natural ordering.
7300 * @return the sorting comparator
7302 public Comparator<? super E> comparator()
7304 return ss.comparator();
7308 * Returns the first (lowest sorted) element in the underlying
7311 * @return the first element.
7312 * @throws NoSuchElementException if the set is empty.
7321 * Returns a checked view of the portion of the set strictly
7322 * less than toElement. The view is backed by the underlying set,
7323 * so changes in one show up in the other. The subset supports
7324 * all optional operations of the original. This operation
7325 * is equivalent to <code>subSet(first(), toElement)</code>.
7328 * The returned set throws an IllegalArgumentException any time an
7329 * element is used which is out of the range of toElement. Note that
7330 * the endpoint, toElement, is not included; if you want this value
7331 * included, pass its successor object in to toElement. For example,
7332 * for Integers, you could request
7333 * <code>headSet(new Integer(limit.intValue() + 1))</code>.
7336 * @param toElement the exclusive upper range of the subset
7337 * @return the subset.
7338 * @throws ClassCastException if toElement is not comparable to the set
7340 * @throws IllegalArgumentException if this is a subSet, and toElement is
7342 * @throws NullPointerException if toElement is null but the set does not
7343 * allow null elements.
7345 public SortedSet<E> headSet(E toElement)
7347 return new CheckedSortedSet<E>(ss.headSet(toElement), type);
7351 * Returns the last (highest sorted) element in the underlying
7354 * @return the last element.
7355 * @throws NoSuchElementException if the set is empty.
7364 * Returns a checked view of the portion of the set greater than or
7365 * equal to fromElement, and strictly less than toElement. The view is
7366 * backed by the underlying set, so changes in one show up in the other.
7367 * The subset supports all optional operations of the original.
7370 * The returned set throws an IllegalArgumentException any time an
7371 * element is used which is out of the range of fromElement and toElement.
7372 * Note that the lower endpoint is included, but the upper is not; if you
7373 * want to change the inclusion or exclusion of an endpoint, pass its
7374 * successor object in instead. For example, for Integers, you can request
7375 * <code>subSet(new Integer(lowlimit.intValue() + 1),
7376 * new Integer(highlimit.intValue() + 1))</code> to reverse
7377 * the inclusiveness of both endpoints.
7380 * @param fromElement the inclusive lower range of the subset.
7381 * @param toElement the exclusive upper range of the subset.
7382 * @return the subset.
7383 * @throws ClassCastException if fromElement or toElement is not comparable
7384 * to the set contents.
7385 * @throws IllegalArgumentException if this is a subSet, and fromElement or
7386 * toElement is out of range.
7387 * @throws NullPointerException if fromElement or toElement is null but the
7388 * set does not allow null elements.
7390 public SortedSet<E> subSet(E fromElement, E toElement)
7392 return new CheckedSortedSet<E>(ss.subSet(fromElement, toElement), type);
7397 * Returns a checked view of the portion of the set greater than or equal
7398 * to fromElement. The view is backed by the underlying set, so changes in
7399 * one show up in the other. The subset supports all optional operations
7403 * The returned set throws an IllegalArgumentException any time an
7404 * element is used which is out of the range of fromElement. Note that
7405 * the endpoint, fromElement, is included; if you do not want this value
7406 * to be included, pass its successor object in to fromElement. For
7407 * example, for Integers, you could request
7408 * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
7411 * @param fromElement the inclusive lower range of the subset
7412 * @return the subset.
7413 * @throws ClassCastException if fromElement is not comparable to the set
7415 * @throws IllegalArgumentException if this is a subSet, and fromElement is
7417 * @throws NullPointerException if fromElement is null but the set does not
7418 * allow null elements.
7420 public SortedSet<E> tailSet(E fromElement)
7422 return new CheckedSortedSet<E>(ss.tailSet(fromElement), type);
7424 } // class CheckedSortedSet
7426 } // class Collections