1 /* Collections.java -- Utility class with methods to operate on collections
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004
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., 59 Temple Place, Suite 330, 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>
71 * @status updated to 1.4
73 public class Collections
76 * Constant used to decide cutoff for when a non-RandomAccess list should
77 * be treated as sequential-access. Basically, quadratic behavior is
78 * acceptable for small lists when the overhead is so small in the first
79 * place. I arbitrarily set it to 16, so it may need some tuning.
81 private static final int LARGE_LIST_SIZE
= 16;
84 * Determines if a list should be treated as a sequential-access one.
85 * Rather than the old method of JDK 1.3 of assuming only instanceof
86 * AbstractSequentialList should be sequential, this uses the new method
87 * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
88 * and exceeds a large (unspecified) size should be sequential.
90 * @param l the list to check
91 * @return <code>true</code> if it should be treated as sequential-access
93 private static boolean isSequential(List l
)
95 return ! (l
instanceof RandomAccess
) && l
.size() > LARGE_LIST_SIZE
;
99 * This class is non-instantiable.
101 private Collections()
106 * An immutable, serializable, empty Set.
109 public static final Set EMPTY_SET
= new EmptySet();
112 * The implementation of {@link #EMPTY_SET}. This class name is required
113 * for compatibility with Sun's JDK serializability.
115 * @author Eric Blake <ebb9@email.byu.edu>
117 private static final class EmptySet
extends AbstractSet
118 implements Serializable
121 * Compatible with JDK 1.4.
123 private static final long serialVersionUID
= 1582296315990362920L;
126 * A private constructor adds overhead.
133 * The size: always 0!
142 * Returns an iterator that does not iterate.
143 * @return A non-iterating iterator.
145 // This is really cheating! I think it's perfectly valid, though.
146 public Iterator
iterator()
148 return EMPTY_LIST
.iterator();
151 // The remaining methods are optional, but provide a performance
152 // advantage by not allocating unnecessary iterators in AbstractSet.
154 * The empty set never contains anything.
155 * @param o The object to search for.
156 * @return <code>false</code>.
158 public boolean contains(Object o
)
164 * This is true only if the given collection is also empty.
165 * @param c The collection of objects which are to be compared
166 * against the members of this set.
167 * @return <code>true</code> if c is empty.
169 public boolean containsAll(Collection c
)
175 * Equal only if the other set is empty.
176 * @param o The object to compare with this set.
177 * @return <code>true</code> if o is an empty instance of <code>Set</code>.
179 public boolean equals(Object o
)
181 return o
instanceof Set
&& ((Set
) o
).isEmpty();
185 * The hashcode is always 0.
188 public int hashCode()
194 * Always succeeds with a <code>false</code> result.
195 * @param o The object to remove.
196 * @return <code>false</code>.
198 public boolean remove(Object o
)
204 * Always succeeds with a <code>false</code> result.
205 * @param c The collection of objects which should
206 * all be removed from this set.
207 * @return <code>false</code>.
209 public boolean removeAll(Collection c
)
215 * Always succeeds with a <code>false</code> result.
216 * @param c The collection of objects which should
217 * all be retained within this set.
218 * @return <code>false</code>.
220 public boolean retainAll(Collection c
)
226 * The array is always empty.
227 * @return A new array with a size of 0.
229 public Object
[] toArray()
231 return new Object
[0];
235 * We don't even need to use reflection!
236 * @param a An existing array, which can be empty.
237 * @return The original array with any existing
238 * initial element set to null.
240 public Object
[] toArray(Object
[] a
)
248 * The string never changes.
250 * @return the string "[]".
252 public String
toString()
259 * An immutable, serializable, empty List, which implements RandomAccess.
263 public static final List EMPTY_LIST
= new EmptyList();
266 * The implementation of {@link #EMPTY_LIST}. This class name is required
267 * for compatibility with Sun's JDK serializability.
269 * @author Eric Blake <ebb9@email.byu.edu>
271 private static final class EmptyList
extends AbstractList
272 implements Serializable
, RandomAccess
275 * Compatible with JDK 1.4.
277 private static final long serialVersionUID
= 8842843931221139166L;
280 * A private constructor adds overhead.
287 * The size is always 0.
296 * No matter the index, it is out of bounds. This
297 * method never returns, throwing an exception instead.
299 * @param index The index of the element to retrieve.
300 * @return the object at the specified index.
301 * @throws IndexOutofBoundsException as any given index
302 * is outside the bounds of an empty array.
304 public Object
get(int index
)
306 throw new IndexOutOfBoundsException();
309 // The remaining methods are optional, but provide a performance
310 // advantage by not allocating unnecessary iterators in AbstractList.
312 * Never contains anything.
313 * @param o The object to search for.
314 * @return <code>false</code>.
316 public boolean contains(Object o
)
322 * This is true only if the given collection is also empty.
323 * @param c The collection of objects, which should be compared
324 * against the members of this list.
325 * @return <code>true</code> if c is also empty.
327 public boolean containsAll(Collection c
)
333 * Equal only if the other list is empty.
334 * @param o The object to compare against this list.
335 * @return <code>true</code> if o is also an empty instance of
338 public boolean equals(Object o
)
340 return o
instanceof List
&& ((List
) o
).isEmpty();
344 * The hashcode is always 1.
347 public int hashCode()
354 * @param o The object to search for.
357 public int indexOf(Object o
)
364 * @param o The object to search for.
367 public int lastIndexOf(Object o
)
373 * Always succeeds with <code>false</code> result.
374 * @param o The object to remove.
377 public boolean remove(Object o
)
383 * Always succeeds with <code>false</code> result.
384 * @param c The collection of objects which should
385 * all be removed from this list.
386 * @return <code>false</code>.
388 public boolean removeAll(Collection c
)
394 * Always succeeds with <code>false</code> result.
395 * @param c The collection of objects which should
396 * all be retained within this list.
397 * @return <code>false</code>.
399 public boolean retainAll(Collection c
)
405 * The array is always empty.
406 * @return A new array with a size of 0.
408 public Object
[] toArray()
410 return new Object
[0];
414 * We don't even need to use reflection!
415 * @param a An existing array, which can be empty.
416 * @return The original array with any existing
417 * initial element set to null.
419 public Object
[] toArray(Object
[] a
)
427 * The string never changes.
429 * @return the string "[]".
431 public String
toString()
438 * An immutable, serializable, empty Map.
441 public static final Map EMPTY_MAP
= new EmptyMap();
444 * The implementation of {@link #EMPTY_MAP}. This class name is required
445 * for compatibility with Sun's JDK serializability.
447 * @author Eric Blake <ebb9@email.byu.edu>
449 private static final class EmptyMap
extends AbstractMap
450 implements Serializable
453 * Compatible with JDK 1.4.
455 private static final long serialVersionUID
= 6428348081105594320L;
458 * A private constructor adds overhead.
465 * There are no entries.
466 * @return The empty set.
468 public Set
entrySet()
473 // The remaining methods are optional, but provide a performance
474 // advantage by not allocating unnecessary iterators in AbstractMap.
477 * @param key The key to search for.
478 * @return <code>false</code>.
480 public boolean containsKey(Object key
)
487 * @param value The value to search for.
488 * @return <code>false</code>.
490 public boolean containsValue(Object value
)
496 * Equal to all empty maps.
497 * @param o The object o to compare against this map.
498 * @return <code>true</code> if o is also an empty instance of
501 public boolean equals(Object o
)
503 return o
instanceof Map
&& ((Map
) o
).isEmpty();
507 * No mappings, so this returns null.
508 * @param o The key of the object to retrieve.
511 public Object
get(Object o
)
517 * The hashcode is always 0.
520 public int hashCode()
527 * @return The empty set.
535 * Remove always succeeds, with null result.
536 * @param o The key of the mapping to remove.
537 * @return null, as there is never a mapping for o.
539 public Object
remove(Object o
)
554 * No entries. Technically, EMPTY_SET, while more specific than a general
555 * Collection, will work. Besides, that's what the JDK uses!
556 * @return The empty set.
558 public Collection
values()
564 * The string never changes.
566 * @return the string "[]".
568 public String
toString()
576 * Compare two objects with or without a Comparator. If c is null, uses the
577 * natural ordering. Slightly slower than doing it inline if the JVM isn't
578 * clever, but worth it for removing a duplicate of the search code.
579 * Note: This code is also used in Arrays (for sort as well as search).
581 static final int compare(Object o1
, Object o2
, Comparator c
)
583 return c
== null ?
((Comparable
) o1
).compareTo(o2
) : c
.compare(o1
, o2
);
587 * Perform a binary search of a List for a key, using the natural ordering of
588 * the elements. The list must be sorted (as by the sort() method) - if it is
589 * not, the behavior of this method is undefined, and may be an infinite
590 * loop. Further, the key must be comparable with every item in the list. If
591 * the list contains the key more than once, any one of them may be found.
594 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
595 * and uses a linear search with O(n) link traversals and log(n) comparisons
596 * with {@link AbstractSequentialList} lists. Note: although the
597 * specification allows for an infinite loop if the list is unsorted, it will
598 * not happen in this (Classpath) implementation.
600 * @param l the list to search (must be sorted)
601 * @param key the value to search for
602 * @return the index at which the key was found, or -n-1 if it was not
603 * found, where n is the index of the first value higher than key or
604 * a.length if there is no such value
605 * @throws ClassCastException if key could not be compared with one of the
607 * @throws NullPointerException if a null element has compareTo called
610 public static int binarySearch(List l
, Object key
)
612 return binarySearch(l
, key
, null);
616 * Perform a binary search of a List for a key, using a supplied Comparator.
617 * The list must be sorted (as by the sort() method with the same Comparator)
618 * - if it is not, the behavior of this method is undefined, and may be an
619 * infinite loop. Further, the key must be comparable with every item in the
620 * list. If the list contains the key more than once, any one of them may be
621 * found. If the comparator is null, the elements' natural ordering is used.
624 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
625 * and uses a linear search with O(n) link traversals and log(n) comparisons
626 * with {@link AbstractSequentialList} lists. Note: although the
627 * specification allows for an infinite loop if the list is unsorted, it will
628 * not happen in this (Classpath) implementation.
630 * @param l the list to search (must be sorted)
631 * @param key the value to search for
632 * @param c the comparator by which the list is sorted
633 * @return the index at which the key was found, or -n-1 if it was not
634 * found, where n is the index of the first value higher than key or
635 * a.length if there is no such value
636 * @throws ClassCastException if key could not be compared with one of the
638 * @throws NullPointerException if a null element is compared with natural
639 * ordering (only possible when c is null)
640 * @see #sort(List, Comparator)
642 public static int binarySearch(List l
, Object key
, Comparator c
)
646 int hi
= l
.size() - 1;
648 // We use a linear search with log(n) comparisons using an iterator
649 // if the list is sequential-access.
652 ListIterator itr
= l
.listIterator();
654 Object o
= itr
.next(); // Assumes list is not empty (see isSequential)
655 boolean forward
= true;
658 pos
= (low
+ hi
) >> 1;
662 itr
.next(); // Changing direction first.
663 for ( ; i
!= pos
; i
++, o
= itr
.next());
669 itr
.previous(); // Changing direction first.
670 for ( ; i
!= pos
; i
--, o
= itr
.previous());
673 final int d
= compare(key
, o
, c
);
679 // This gets the insertion point right on the last loop
687 pos
= (low
+ hi
) >> 1;
688 final int d
= compare(key
, l
.get(pos
), c
);
694 // This gets the insertion point right on the last loop
699 // If we failed to find it, we do the same whichever search we did.
704 * Copy one list to another. If the destination list is longer than the
705 * source list, the remaining elements are unaffected. This method runs in
708 * @param dest the destination list
709 * @param source the source list
710 * @throws IndexOutOfBoundsException if the destination list is shorter
711 * than the source list (the destination will be unmodified)
712 * @throws UnsupportedOperationException if dest.listIterator() does not
713 * support the set operation
715 public static void copy(List dest
, List source
)
717 int pos
= source
.size();
718 if (dest
.size() < pos
)
719 throw new IndexOutOfBoundsException("Source does not fit in dest");
721 Iterator i1
= source
.iterator();
722 ListIterator i2
= dest
.listIterator();
732 * Returns an Enumeration over a collection. This allows interoperability
733 * with legacy APIs that require an Enumeration as input.
735 * @param c the Collection to iterate over
736 * @return an Enumeration backed by an Iterator over c
738 public static Enumeration
enumeration(Collection c
)
740 final Iterator i
= c
.iterator();
741 return new Enumeration()
744 * Returns <code>true</code> if there are more elements to
747 * @return The result of <code>hasNext()</code>
748 * called on the underlying iterator.
750 public final boolean hasMoreElements()
756 * Returns the next element to be enumerated.
758 * @return The result of <code>next()</code>
759 * called on the underlying iterator.
761 public final Object
nextElement()
769 * Replace every element of a list with a given value. This method runs in
772 * @param l the list to fill.
773 * @param val the object to vill the list with.
774 * @throws UnsupportedOperationException if l.listIterator() does not
775 * support the set operation.
777 public static void fill(List l
, Object val
)
779 ListIterator itr
= l
.listIterator();
780 for (int i
= l
.size() - 1; i
>= 0; --i
)
788 * Returns the starting index where the specified sublist first occurs
789 * in a larger list, or -1 if there is no matching position. If
790 * <code>target.size() > source.size()</code>, this returns -1,
791 * otherwise this implementation uses brute force, checking for
792 * <code>source.sublist(i, i + target.size()).equals(target)</code>
793 * for all possible i.
795 * @param source the list to search
796 * @param target the sublist to search for
797 * @return the index where found, or -1
800 public static int indexOfSubList(List source
, List target
)
802 int ssize
= source
.size();
803 for (int i
= 0, j
= target
.size(); j
<= ssize
; i
++, j
++)
804 if (source
.subList(i
, j
).equals(target
))
810 * Returns the starting index where the specified sublist last occurs
811 * in a larger list, or -1 if there is no matching position. If
812 * <code>target.size() > source.size()</code>, this returns -1,
813 * otherwise this implementation uses brute force, checking for
814 * <code>source.sublist(i, i + target.size()).equals(target)</code>
815 * for all possible i.
817 * @param source the list to search
818 * @param target the sublist to search for
819 * @return the index where found, or -1
822 public static int lastIndexOfSubList(List source
, List target
)
824 int ssize
= source
.size();
825 for (int i
= ssize
- target
.size(), j
= ssize
; i
>= 0; i
--, j
--)
826 if (source
.subList(i
, j
).equals(target
))
832 * Returns an ArrayList holding the elements visited by a given
833 * Enumeration. This method exists for interoperability between legacy
834 * APIs and the new Collection API.
836 * @param e the enumeration to put in a list
837 * @return a list containing the enumeration elements
841 public static ArrayList
list(Enumeration e
)
843 ArrayList l
= new ArrayList();
844 while (e
.hasMoreElements())
845 l
.add(e
.nextElement());
850 * Find the maximum element in a Collection, according to the natural
851 * ordering of the elements. This implementation iterates over the
852 * Collection, so it works in linear time.
854 * @param c the Collection to find the maximum element of
855 * @return the maximum element of c
856 * @exception NoSuchElementException if c is empty
857 * @exception ClassCastException if elements in c are not mutually comparable
858 * @exception NullPointerException if null.compareTo is called
860 public static Object
max(Collection c
)
866 * Find the maximum element in a Collection, according to a specified
867 * Comparator. This implementation iterates over the Collection, so it
868 * works in linear time.
870 * @param c the Collection to find the maximum element of
871 * @param order the Comparator to order the elements by, or null for natural
873 * @return the maximum element of c
874 * @throws NoSuchElementException if c is empty
875 * @throws ClassCastException if elements in c are not mutually comparable
876 * @throws NullPointerException if null is compared by natural ordering
877 * (only possible when order is null)
879 public static Object
max(Collection c
, Comparator order
)
881 Iterator itr
= c
.iterator();
882 Object max
= itr
.next(); // throws NoSuchElementException
883 int csize
= c
.size();
884 for (int i
= 1; i
< csize
; i
++)
886 Object o
= itr
.next();
887 if (compare(max
, o
, order
) < 0)
894 * Find the minimum element in a Collection, according to the natural
895 * ordering of the elements. This implementation iterates over the
896 * Collection, so it works in linear time.
898 * @param c the Collection to find the minimum element of
899 * @return the minimum element of c
900 * @throws NoSuchElementException if c is empty
901 * @throws ClassCastException if elements in c are not mutually comparable
902 * @throws NullPointerException if null.compareTo is called
904 public static Object
min(Collection c
)
910 * Find the minimum element in a Collection, according to a specified
911 * Comparator. This implementation iterates over the Collection, so it
912 * works in linear time.
914 * @param c the Collection to find the minimum element of
915 * @param order the Comparator to order the elements by, or null for natural
917 * @return the minimum element of c
918 * @throws NoSuchElementException if c is empty
919 * @throws ClassCastException if elements in c are not mutually comparable
920 * @throws NullPointerException if null is compared by natural ordering
921 * (only possible when order is null)
923 public static Object
min(Collection c
, Comparator order
)
925 Iterator itr
= c
.iterator();
926 Object min
= itr
.next(); // throws NoSuchElementExcception
927 int csize
= c
.size();
928 for (int i
= 1; i
< csize
; i
++)
930 Object o
= itr
.next();
931 if (compare(min
, o
, order
) > 0)
938 * Creates an immutable list consisting of the same object repeated n times.
939 * The returned object is tiny, consisting of only a single reference to the
940 * object and a count of the number of elements. It is Serializable, and
941 * implements RandomAccess. You can use it in tandem with List.addAll for
942 * fast list construction.
944 * @param n the number of times to repeat the object
945 * @param o the object to repeat
946 * @return a List consisting of n copies of o
947 * @throws IllegalArgumentException if n < 0
948 * @see List#addAll(Collection)
952 public static List
nCopies(final int n
, final Object o
)
954 return new CopiesList(n
, o
);
958 * The implementation of {@link #nCopies(int, Object)}. This class name
959 * is required for compatibility with Sun's JDK serializability.
961 * @author Eric Blake <ebb9@email.byu.edu>
963 private static final class CopiesList
extends AbstractList
964 implements Serializable
, RandomAccess
967 * Compatible with JDK 1.4.
969 private static final long serialVersionUID
= 2739099268398711800L;
972 * The count of elements in this list.
973 * @serial the list size
978 * The repeated list element.
979 * @serial the list contents
981 private final Object element
;
984 * Constructs the list.
987 * @param o the object
988 * @throws IllegalArgumentException if n < 0
990 CopiesList(int n
, Object o
)
993 throw new IllegalArgumentException();
1000 * @return The size of the list.
1008 * The same element is returned.
1009 * @param index The index of the element to be returned (irrelevant
1010 * as the list contains only copies of <code>element</code>).
1011 * @return The element used by this list.
1013 public Object
get(int index
)
1015 if (index
< 0 || index
>= n
)
1016 throw new IndexOutOfBoundsException();
1020 // The remaining methods are optional, but provide a performance
1021 // advantage by not allocating unnecessary iterators in AbstractList.
1023 * This list only contains one element.
1024 * @param o The object to search for.
1025 * @return <code>true</code> if o is the element used by this list.
1027 public boolean contains(Object o
)
1029 return n
> 0 && equals(o
, element
);
1033 * The index is either 0 or -1.
1034 * @param o The object to find the index of.
1035 * @return 0 if <code>o == element</code>, -1 if not.
1037 public int indexOf(Object o
)
1039 return (n
> 0 && equals(o
, element
)) ?
0 : -1;
1043 * The index is either n-1 or -1.
1044 * @param o The object to find the last index of.
1045 * @return The last index in the list if <code>o == element</code>,
1048 public int lastIndexOf(Object o
)
1050 return equals(o
, element
) ? n
- 1 : -1;
1054 * A subList is just another CopiesList.
1055 * @param from The starting bound of the sublist.
1056 * @param to The ending bound of the sublist.
1057 * @return A list of copies containing <code>from - to</code>
1058 * elements, all of which are equal to the element
1059 * used by this list.
1061 public List
subList(int from
, int to
)
1063 if (from
< 0 || to
> n
)
1064 throw new IndexOutOfBoundsException();
1065 return new CopiesList(to
- from
, element
);
1069 * The array is easy.
1070 * @return An array of size n filled with copies of
1071 * the element used by this list.
1073 public Object
[] toArray()
1075 Object
[] a
= new Object
[n
];
1076 Arrays
.fill(a
, element
);
1081 * The string is easy to generate.
1082 * @return A string representation of the list.
1084 public String
toString()
1086 StringBuffer r
= new StringBuffer("{");
1087 for (int i
= n
- 1; --i
> 0; )
1088 r
.append(element
).append(", ");
1089 r
.append(element
).append("}");
1090 return r
.toString();
1092 } // class CopiesList
1095 * Replace all instances of one object with another in the specified list.
1096 * The list does not change size. An element e is replaced if
1097 * <code>oldval == null ? e == null : oldval.equals(e)</code>.
1099 * @param list the list to iterate over
1100 * @param oldval the element to replace
1101 * @param newval the new value for the element
1102 * @return <code>true</code> if a replacement occurred.
1103 * @throws UnsupportedOperationException if the list iterator does not allow
1104 * for the set operation
1105 * @throws ClassCastException if newval is of a type which cannot be added
1107 * @throws IllegalArgumentException if some other aspect of newval stops
1108 * it being added to the list
1111 public static boolean replaceAll(List list
, Object oldval
, Object newval
)
1113 ListIterator itr
= list
.listIterator();
1114 boolean replace_occured
= false;
1115 for (int i
= list
.size(); --i
>= 0; )
1116 if (AbstractCollection
.equals(oldval
, itr
.next()))
1119 replace_occured
= true;
1121 return replace_occured
;
1125 * Reverse a given list. This method works in linear time.
1127 * @param l the list to reverse
1128 * @throws UnsupportedOperationException if l.listIterator() does not
1129 * support the set operation
1131 public static void reverse(List l
)
1133 ListIterator i1
= l
.listIterator();
1135 int pos2
= l
.size();
1136 ListIterator i2
= l
.listIterator(pos2
);
1139 Object o
= i1
.next();
1140 i1
.set(i2
.previous());
1148 * Get a comparator that implements the reverse of natural ordering. In
1149 * other words, this sorts Comparable objects opposite of how their
1150 * compareTo method would sort. This makes it easy to sort into reverse
1151 * order, by simply passing Collections.reverseOrder() to the sort method.
1152 * The return value of this method is Serializable.
1154 * @return a comparator that imposes reverse natural ordering
1158 public static Comparator
reverseOrder()
1164 * The object for {@link #reverseOrder()}.
1166 private static final ReverseComparator rcInstance
= new ReverseComparator();
1169 * The implementation of {@link #reverseOrder()}. This class name
1170 * is required for compatibility with Sun's JDK serializability.
1172 * @author Eric Blake <ebb9@email.byu.edu>
1174 private static final class ReverseComparator
1175 implements Comparator
, Serializable
1178 * Compatible with JDK 1.4.
1180 private static final long serialVersionUID
= 7207038068494060240L;
1183 * A private constructor adds overhead.
1190 * Compare two objects in reverse natural order.
1192 * @param a the first object
1193 * @param b the second object
1194 * @return <, ==, or > 0 according to b.compareTo(a)
1196 public int compare(Object a
, Object b
)
1198 return ((Comparable
) b
).compareTo(a
);
1203 * Rotate the elements in a list by a specified distance. After calling this
1204 * method, the element now at index <code>i</code> was formerly at index
1205 * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
1208 * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
1209 * either <code>Collections.rotate(l, 4)</code> or
1210 * <code>Collections.rotate(l, -1)</code>, the new contents are
1211 * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
1212 * just a portion of the list. For example, to move element <code>a</code>
1213 * forward two positions in the original example, use
1214 * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
1215 * result in <code>[t, n, k, a, s]</code>.
1218 * If the list is small or implements {@link RandomAccess}, the
1219 * implementation exchanges the first element to its destination, then the
1220 * displaced element, and so on until a circuit has been completed. The
1221 * process is repeated if needed on the second element, and so forth, until
1222 * all elements have been swapped. For large non-random lists, the
1223 * implementation breaks the list into two sublists at index
1224 * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
1225 * pieces, then reverses the overall list.
1227 * @param list the list to rotate
1228 * @param distance the distance to rotate by; unrestricted in value
1229 * @throws UnsupportedOperationException if the list does not support set
1232 public static void rotate(List list
, int distance
)
1234 int size
= list
.size();
1243 if (isSequential(list
))
1246 reverse(list
.subList(0, distance
));
1247 reverse(list
.subList(distance
, size
));
1251 // Determine the least common multiple of distance and size, as there
1252 // are (distance / LCM) loops to cycle through.
1263 // Now, make the swaps. We must take the remainder every time through
1264 // the inner loop so that we don't overflow i to negative values.
1267 Object o
= list
.get(lcm
);
1268 for (int i
= lcm
+ distance
; i
!= lcm
; i
= (i
+ distance
) % size
)
1276 * Shuffle a list according to a default source of randomness. The algorithm
1277 * used iterates backwards over the list, swapping each element with an
1278 * element randomly selected from the elements in positions less than or
1279 * equal to it (using r.nextInt(int)).
1282 * This algorithm would result in a perfectly fair shuffle (that is, each
1283 * element would have an equal chance of ending up in any position) if r were
1284 * a perfect source of randomness. In practice the results are merely very
1288 * This method operates in linear time. To do this on large lists which do
1289 * not implement {@link RandomAccess}, a temporary array is used to acheive
1290 * this speed, since it would be quadratic access otherwise.
1292 * @param l the list to shuffle
1293 * @throws UnsupportedOperationException if l.listIterator() does not
1294 * support the set operation
1296 public static void shuffle(List l
)
1298 if (defaultRandom
== null)
1300 synchronized (Collections
.class)
1302 if (defaultRandom
== null)
1303 defaultRandom
= new Random();
1306 shuffle(l
, defaultRandom
);
1310 * Cache a single Random object for use by shuffle(List). This improves
1311 * performance as well as ensuring that sequential calls to shuffle() will
1312 * not result in the same shuffle order occurring: the resolution of
1313 * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
1315 private static Random defaultRandom
= null;
1318 * Shuffle a list according to a given source of randomness. The algorithm
1319 * used iterates backwards over the list, swapping each element with an
1320 * element randomly selected from the elements in positions less than or
1321 * equal to it (using r.nextInt(int)).
1324 * This algorithm would result in a perfectly fair shuffle (that is, each
1325 * element would have an equal chance of ending up in any position) if r were
1326 * a perfect source of randomness. In practise (eg if r = new Random()) the
1327 * results are merely very close to perfect.
1330 * This method operates in linear time. To do this on large lists which do
1331 * not implement {@link RandomAccess}, a temporary array is used to acheive
1332 * this speed, since it would be quadratic access otherwise.
1334 * @param l the list to shuffle
1335 * @param r the source of randomness to use for the shuffle
1336 * @throws UnsupportedOperationException if l.listIterator() does not
1337 * support the set operation
1339 public static void shuffle(List l
, Random r
)
1341 int lsize
= l
.size();
1342 ListIterator i
= l
.listIterator(lsize
);
1343 boolean sequential
= isSequential(l
);
1344 Object
[] a
= null; // stores a copy of the list for the sequential case
1349 for (int pos
= lsize
- 1; pos
> 0; --pos
)
1351 // Obtain a random position to swap with. pos + 1 is used so that the
1352 // range of the random number includes the current position.
1353 int swap
= r
.nextInt(pos
+ 1);
1355 // Swap the desired element.
1360 a
[swap
] = i
.previous();
1363 o
= l
.set(swap
, i
.previous());
1371 * Obtain an immutable Set consisting of a single element. The return value
1372 * of this method is Serializable.
1374 * @param o the single element
1375 * @return an immutable Set containing only o
1378 public static Set
singleton(Object o
)
1380 return new SingletonSet(o
);
1384 * The implementation of {@link #singleton(Object)}. This class name
1385 * is required for compatibility with Sun's JDK serializability.
1387 * @author Eric Blake <ebb9@email.byu.edu>
1389 private static final class SingletonSet
extends AbstractSet
1390 implements Serializable
1393 * Compatible with JDK 1.4.
1395 private static final long serialVersionUID
= 3193687207550431679L;
1399 * The single element; package visible for use in nested class.
1400 * @serial the singleton
1402 final Object element
;
1405 * Construct a singleton.
1406 * @param o the element
1408 SingletonSet(Object o
)
1414 * The size: always 1!
1423 * Returns an iterator over the lone element.
1425 public Iterator
iterator()
1427 return new Iterator()
1430 * Flag to indicate whether or not the element has
1433 private boolean hasNext
= true;
1436 * Returns <code>true</code> if elements still remain to be
1439 * @return <code>true</code> if the element has not yet been returned.
1441 public boolean hasNext()
1447 * Returns the element.
1449 * @return The element used by this singleton.
1450 * @throws NoSuchElementException if the object
1451 * has already been retrieved.
1453 public Object
next()
1461 throw new NoSuchElementException();
1465 * Removes the element from the singleton.
1466 * As this set is immutable, this will always
1467 * throw an exception.
1469 * @throws UnsupportedOperationException as the
1470 * singleton set doesn't support
1471 * <code>remove()</code>.
1473 public void remove()
1475 throw new UnsupportedOperationException();
1480 // The remaining methods are optional, but provide a performance
1481 // advantage by not allocating unnecessary iterators in AbstractSet.
1483 * The set only contains one element.
1485 * @param o The object to search for.
1486 * @return <code>true</code> if o == the element of the singleton.
1488 public boolean contains(Object o
)
1490 return equals(o
, element
);
1494 * This is true if the other collection only contains the element.
1496 * @param c A collection to compare against this singleton.
1497 * @return <code>true</code> if c only contains either no elements or
1498 * elements equal to the element in this singleton.
1500 public boolean containsAll(Collection c
)
1502 Iterator i
= c
.iterator();
1505 if (! equals(i
.next(), element
))
1511 * The hash is just that of the element.
1513 * @return The hashcode of the element.
1515 public int hashCode()
1517 return hashCode(element
);
1521 * Returning an array is simple.
1523 * @return An array containing the element.
1525 public Object
[] toArray()
1527 return new Object
[] {element
};
1533 * @return The string surrounded by enclosing
1536 public String
toString()
1538 return "[" + element
+ "]";
1540 } // class SingletonSet
1543 * Obtain an immutable List consisting of a single element. The return value
1544 * of this method is Serializable, and implements RandomAccess.
1546 * @param o the single element
1547 * @return an immutable List containing only o
1552 public static List
singletonList(Object o
)
1554 return new SingletonList(o
);
1558 * The implementation of {@link #singletonList(Object)}. This class name
1559 * is required for compatibility with Sun's JDK serializability.
1561 * @author Eric Blake <ebb9@email.byu.edu>
1563 private static final class SingletonList
extends AbstractList
1564 implements Serializable
, RandomAccess
1567 * Compatible with JDK 1.4.
1569 private static final long serialVersionUID
= 3093736618740652951L;
1572 * The single element.
1573 * @serial the singleton
1575 private final Object element
;
1578 * Construct a singleton.
1579 * @param o the element
1581 SingletonList(Object o
)
1587 * The size: always 1!
1596 * Only index 0 is valid.
1597 * @param index The index of the element
1599 * @return The singleton's element if the
1601 * @throws IndexOutOfBoundsException if
1604 public Object
get(int index
)
1608 throw new IndexOutOfBoundsException();
1611 // The remaining methods are optional, but provide a performance
1612 // advantage by not allocating unnecessary iterators in AbstractList.
1614 * The set only contains one element.
1616 * @param o The object to search for.
1617 * @return <code>true</code> if o == the singleton element.
1619 public boolean contains(Object o
)
1621 return equals(o
, element
);
1625 * This is true if the other collection only contains the element.
1627 * @param c A collection to compare against this singleton.
1628 * @return <code>true</code> if c only contains either no elements or
1629 * elements equal to the element in this singleton.
1631 public boolean containsAll(Collection c
)
1633 Iterator i
= c
.iterator();
1636 if (! equals(i
.next(), element
))
1642 * Speed up the hashcode computation.
1644 * @return The hashcode of the list, based
1645 * on the hashcode of the singleton element.
1647 public int hashCode()
1649 return 31 + hashCode(element
);
1653 * Either the list has it or not.
1655 * @param o The object to find the first index of.
1656 * @return 0 if o is the singleton element, -1 if not.
1658 public int indexOf(Object o
)
1660 return equals(o
, element
) ?
0 : -1;
1664 * Either the list has it or not.
1666 * @param o The object to find the last index of.
1667 * @return 0 if o is the singleton element, -1 if not.
1669 public int lastIndexOf(Object o
)
1671 return equals(o
, element
) ?
0 : -1;
1675 * Sublists are limited in scope.
1677 * @param from The starting bound for the sublist.
1678 * @param to The ending bound for the sublist.
1679 * @return Either an empty list if both bounds are
1680 * 0 or 1, or this list if the bounds are 0 and 1.
1681 * @throws IllegalArgumentException if <code>from > to</code>
1682 * @throws IndexOutOfBoundsException if either bound is greater
1685 public List
subList(int from
, int to
)
1687 if (from
== to
&& (to
== 0 || to
== 1))
1689 if (from
== 0 && to
== 1)
1692 throw new IllegalArgumentException();
1693 throw new IndexOutOfBoundsException();
1697 * Returning an array is simple.
1699 * @return An array containing the element.
1701 public Object
[] toArray()
1703 return new Object
[] {element
};
1709 * @return The string surrounded by enclosing
1712 public String
toString()
1714 return "[" + element
+ "]";
1716 } // class SingletonList
1719 * Obtain an immutable Map consisting of a single key-value pair.
1720 * The return value of this method is Serializable.
1722 * @param key the single key
1723 * @param value the single value
1724 * @return an immutable Map containing only the single key-value pair
1728 public static Map
singletonMap(Object key
, Object value
)
1730 return new SingletonMap(key
, value
);
1734 * The implementation of {@link #singletonMap(Object)}. This class name
1735 * is required for compatibility with Sun's JDK serializability.
1737 * @author Eric Blake <ebb9@email.byu.edu>
1739 private static final class SingletonMap
extends AbstractMap
1740 implements Serializable
1743 * Compatible with JDK 1.4.
1745 private static final long serialVersionUID
= -6979724477215052911L;
1749 * @serial the singleton key
1751 private final Object k
;
1754 * The corresponding value.
1755 * @serial the singleton value
1757 private final Object v
;
1760 * Cache the entry set.
1762 private transient Set entries
;
1765 * Construct a singleton.
1766 * @param key the key
1767 * @param value the value
1769 SingletonMap(Object key
, Object value
)
1776 * There is a single immutable entry.
1778 * @return A singleton containing the map entry.
1780 public Set
entrySet()
1782 if (entries
== null)
1783 entries
= singleton(new AbstractMap
.BasicMapEntry(k
, v
)
1786 * Sets the value of the map entry to the supplied value.
1787 * An exception is always thrown, as the map is immutable.
1789 * @param o The new value.
1790 * @return The old value.
1791 * @throws UnsupportedOperationException as setting the value
1794 public Object
setValue(Object o
)
1796 throw new UnsupportedOperationException();
1802 // The remaining methods are optional, but provide a performance
1803 // advantage by not allocating unnecessary iterators in AbstractMap.
1807 * @param key The key to look for.
1808 * @return <code>true</code> if the key is the same as the one used by
1811 public boolean containsKey(Object key
)
1813 return equals(key
, k
);
1819 * @param value The value to look for.
1820 * @return <code>true</code> if the value is the same as the one used by
1823 public boolean containsValue(Object value
)
1825 return equals(value
, v
);
1831 * @param key The key of the value to be retrieved.
1832 * @return The singleton value if the key is the same as the
1833 * singleton key, null otherwise.
1835 public Object
get(Object key
)
1837 return equals(key
, k
) ? v
: null;
1841 * Calculate the hashcode directly.
1843 * @return The hashcode computed from the singleton key
1844 * and the singleton value.
1846 public int hashCode()
1848 return hashCode(k
) ^
hashCode(v
);
1852 * Return the keyset.
1854 * @return A singleton containing the key.
1859 keys
= singleton(k
);
1864 * The size: always 1!
1874 * Return the values. Technically, a singleton, while more specific than
1875 * a general Collection, will work. Besides, that's what the JDK uses!
1877 * @return A singleton containing the value.
1879 public Collection
values()
1882 values
= singleton(v
);
1889 * @return A string containing the string representations of the key
1890 * and its associated value.
1892 public String
toString()
1894 return "{" + k
+ "=" + v
+ "}";
1896 } // class SingletonMap
1899 * Sort a list according to the natural ordering of its elements. The list
1900 * must be modifiable, but can be of fixed size. The sort algorithm is
1901 * precisely that used by Arrays.sort(Object[]), which offers guaranteed
1902 * nlog(n) performance. This implementation dumps the list into an array,
1903 * sorts the array, and then iterates over the list setting each element from
1906 * @param l the List to sort
1907 * @throws ClassCastException if some items are not mutually comparable
1908 * @throws UnsupportedOperationException if the List is not modifiable
1909 * @throws NullPointerException if some element is null
1910 * @see Arrays#sort(Object[])
1912 public static void sort(List l
)
1918 * Sort a list according to a specified Comparator. The list must be
1919 * modifiable, but can be of fixed size. The sort algorithm is precisely that
1920 * used by Arrays.sort(Object[], Comparator), which offers guaranteed
1921 * nlog(n) performance. This implementation dumps the list into an array,
1922 * sorts the array, and then iterates over the list setting each element from
1925 * @param l the List to sort
1926 * @param c the Comparator specifying the ordering for the elements, or
1927 * null for natural ordering
1928 * @throws ClassCastException if c will not compare some pair of items
1929 * @throws UnsupportedOperationException if the List is not modifiable
1930 * @throws NullPointerException if null is compared by natural ordering
1931 * (only possible when c is null)
1932 * @see Arrays#sort(Object[], Comparator)
1934 public static void sort(List l
, Comparator c
)
1936 Object
[] a
= l
.toArray();
1938 ListIterator i
= l
.listIterator();
1939 for (int pos
= 0, alen
= a
.length
; pos
< alen
; pos
++)
1947 * Swaps the elements at the specified positions within the list. Equal
1948 * positions have no effect.
1950 * @param l the list to work on
1951 * @param i the first index to swap
1952 * @param j the second index
1953 * @throws UnsupportedOperationException if list.set is not supported
1954 * @throws IndexOutOfBoundsException if either i or j is < 0 or >=
1958 public static void swap(List l
, int i
, int j
)
1960 l
.set(i
, l
.set(j
, l
.get(i
)));
1965 * Returns a synchronized (thread-safe) collection wrapper backed by the
1966 * given collection. Notice that element access through the iterators
1967 * is thread-safe, but if the collection can be structurally modified
1968 * (adding or removing elements) then you should synchronize around the
1969 * iteration to avoid non-deterministic behavior:<br>
1971 * Collection c = Collections.synchronizedCollection(new Collection(...));
1975 * Iterator i = c.iterator();
1976 * while (i.hasNext())
1981 * Since the collection might be a List or a Set, and those have incompatible
1982 * equals and hashCode requirements, this relies on Object's implementation
1983 * rather than passing those calls on to the wrapped collection. The returned
1984 * Collection implements Serializable, but can only be serialized if
1985 * the collection it wraps is likewise Serializable.
1987 * @param c the collection to wrap
1988 * @return a synchronized view of the collection
1991 public static Collection
synchronizedCollection(Collection c
)
1993 return new SynchronizedCollection(c
);
1997 * The implementation of {@link #synchronizedCollection(Collection)}. This
1998 * class name is required for compatibility with Sun's JDK serializability.
1999 * Package visible, so that collections such as the one for
2000 * Hashtable.values() can specify which object to synchronize on.
2002 * @author Eric Blake <ebb9@email.byu.edu>
2004 static class SynchronizedCollection
2005 implements Collection
, Serializable
2008 * Compatible with JDK 1.4.
2010 private static final long serialVersionUID
= 3053995032091335093L;
2013 * The wrapped collection. Package visible for use by subclasses.
2014 * @serial the real collection
2019 * The object to synchronize on. When an instance is created via public
2020 * methods, it will be this; but other uses like SynchronizedMap.values()
2021 * must specify another mutex. Package visible for use by subclasses.
2027 * Wrap a given collection.
2028 * @param c the collection to wrap
2029 * @throws NullPointerException if c is null
2031 SynchronizedCollection(Collection c
)
2036 throw new NullPointerException();
2040 * Called only by trusted code to specify the mutex as well as the
2042 * @param sync the mutex
2043 * @param c the collection
2045 SynchronizedCollection(Object sync
, Collection c
)
2052 * Adds the object to the underlying collection, first
2053 * obtaining a lock on the mutex.
2055 * @param o The object to add.
2056 * @return <code>true</code> if the collection was modified as a result
2058 * @throws UnsupportedOperationException if this collection does not
2059 * support the add operation.
2060 * @throws ClassCastException if o cannot be added to this collection due
2062 * @throws NullPointerException if o is null and this collection doesn't
2063 * support the addition of null values.
2064 * @throws IllegalArgumentException if o cannot be added to this
2065 * collection for some other reason.
2067 public boolean add(Object o
)
2069 synchronized (mutex
)
2076 * Adds the objects in col to the underlying collection, first
2077 * obtaining a lock on the mutex.
2079 * @param col The collection to take the new objects from.
2080 * @return <code>true</code> if the collection was modified as a result
2082 * @throws UnsupportedOperationException if this collection does not
2083 * support the addAll operation.
2084 * @throws ClassCastException if some element of col cannot be added to this
2085 * collection due to its type.
2086 * @throws NullPointerException if some element of col is null and this
2087 * collection does not support the addition of null values.
2088 * @throws NullPointerException if col itself is null.
2089 * @throws IllegalArgumentException if some element of col cannot be added
2090 * to this collection for some other reason.
2092 public boolean addAll(Collection col
)
2094 synchronized (mutex
)
2096 return c
.addAll(col
);
2101 * Removes all objects from the underlying collection,
2102 * first obtaining a lock on the mutex.
2104 * @throws UnsupportedOperationException if this collection does not
2105 * support the clear operation.
2109 synchronized (mutex
)
2116 * Checks for the existence of o within the underlying
2117 * collection, first obtaining a lock on the mutex.
2119 * @param o the element to look for.
2120 * @return <code>true</code> if this collection contains at least one
2121 * element e such that <code>o == null ? e == null : o.equals(e)</code>.
2122 * @throws ClassCastException if the type of o is not a valid type for this
2124 * @throws NullPointerException if o is null and this collection doesn't
2125 * support null values.
2127 public boolean contains(Object o
)
2129 synchronized (mutex
)
2131 return c
.contains(o
);
2136 * Checks for the existence of each object in cl
2137 * within the underlying collection, first obtaining
2138 * a lock on the mutex.
2140 * @param cl the collection to test for.
2141 * @return <code>true</code> if for every element o in c, contains(o)
2142 * would return <code>true</code>.
2143 * @throws ClassCastException if the type of any element in cl is not a valid
2144 * type for this collection.
2145 * @throws NullPointerException if some element of cl is null and this
2146 * collection does not support null values.
2147 * @throws NullPointerException if cl itself is null.
2149 public boolean containsAll(Collection c1
)
2151 synchronized (mutex
)
2153 return c
.containsAll(c1
);
2158 * Returns <code>true</code> if there are no objects in the underlying
2159 * collection. A lock on the mutex is obtained before the
2160 * check is performed.
2162 * @return <code>true</code> if this collection contains no elements.
2164 public boolean isEmpty()
2166 synchronized (mutex
)
2173 * Returns a synchronized iterator wrapper around the underlying
2174 * collection's iterator. A lock on the mutex is obtained before
2175 * retrieving the collection's iterator.
2177 * @return An iterator over the elements in the underlying collection,
2178 * which returns each element in any order.
2180 public Iterator
iterator()
2182 synchronized (mutex
)
2184 return new SynchronizedIterator(mutex
, c
.iterator());
2189 * Removes the specified object from the underlying collection,
2190 * first obtaining a lock on the mutex.
2192 * @param o The object to remove.
2193 * @return <code>true</code> if the collection changed as a result of this call, that is,
2194 * if the collection contained at least one occurrence of o.
2195 * @throws UnsupportedOperationException if this collection does not
2196 * support the remove operation.
2197 * @throws ClassCastException if the type of o is not a valid type
2198 * for this collection.
2199 * @throws NullPointerException if o is null and the collection doesn't
2200 * support null values.
2202 public boolean remove(Object o
)
2204 synchronized (mutex
)
2211 * Removes all elements, e, of the underlying
2212 * collection for which <code>col.contains(e)</code>
2213 * returns <code>true</code>. A lock on the mutex is obtained
2214 * before the operation proceeds.
2216 * @param col The collection of objects to be removed.
2217 * @return <code>true</code> if this collection was modified as a result of this call.
2218 * @throws UnsupportedOperationException if this collection does not
2219 * support the removeAll operation.
2220 * @throws ClassCastException if the type of any element in c is not a valid
2221 * type for this collection.
2222 * @throws NullPointerException if some element of c is null and this
2223 * collection does not support removing null values.
2224 * @throws NullPointerException if c itself is null.
2226 public boolean removeAll(Collection col
)
2228 synchronized (mutex
)
2230 return c
.removeAll(col
);
2235 * Retains all elements, e, of the underlying
2236 * collection for which <code>col.contains(e)</code>
2237 * returns <code>true</code>. That is, every element that doesn't
2238 * exist in col is removed. A lock on the mutex is obtained
2239 * before the operation proceeds.
2241 * @param col The collection of objects to be removed.
2242 * @return <code>true</code> if this collection was modified as a result of this call.
2243 * @throws UnsupportedOperationException if this collection does not
2244 * support the removeAll operation.
2245 * @throws ClassCastException if the type of any element in c is not a valid
2246 * type for this collection.
2247 * @throws NullPointerException if some element of c is null and this
2248 * collection does not support removing null values.
2249 * @throws NullPointerException if c itself is null.
2251 public boolean retainAll(Collection col
)
2253 synchronized (mutex
)
2255 return c
.retainAll(col
);
2260 * Retrieves the size of the underlying collection.
2261 * A lock on the mutex is obtained before the collection
2264 * @return The size of the collection.
2268 synchronized (mutex
)
2275 * Returns an array containing each object within the underlying
2276 * collection. A lock is obtained on the mutex before the collection
2279 * @return An array of objects, matching the collection in size. The
2280 * elements occur in any order.
2282 public Object
[] toArray()
2284 synchronized (mutex
)
2291 * Copies the elements in the underlying collection to the supplied
2292 * array. If <code>a.length < size()</code>, a new array of the
2293 * same run-time type is created, with a size equal to that of
2294 * the collection. If <code>a.length > size()</code>, then the
2295 * elements from 0 to <code>size() - 1</code> contain the elements
2296 * from this collection. The following element is set to null
2297 * to indicate the end of the collection objects. However, this
2298 * only makes a difference if null is not a permitted value within
2300 * Before the copying takes place, a lock is obtained on the mutex.
2302 * @param a An array to copy elements to.
2303 * @return An array containing the elements of the underlying collection.
2304 * @throws ArrayStoreException if the type of any element of the
2305 * collection is not a subtype of the element type of a.
2307 public Object
[] toArray(Object
[] a
)
2309 synchronized (mutex
)
2311 return c
.toArray(a
);
2316 * Returns a string representation of the underlying collection.
2317 * A lock is obtained on the mutex before the string is created.
2319 * @return A string representation of the collection.
2321 public String
toString()
2323 synchronized (mutex
)
2325 return c
.toString();
2328 } // class SynchronizedCollection
2331 * The implementation of the various iterator methods in the
2332 * synchronized classes. These iterators must "sync" on the same object
2333 * as the collection they iterate over.
2335 * @author Eric Blake <ebb9@email.byu.edu>
2337 private static class SynchronizedIterator
implements Iterator
2340 * The object to synchronize on. Package visible for use by subclass.
2345 * The wrapped iterator.
2347 private final Iterator i
;
2350 * Only trusted code creates a wrapper, with the specified sync.
2351 * @param sync the mutex
2352 * @param i the wrapped iterator
2354 SynchronizedIterator(Object sync
, Iterator i
)
2361 * Retrieves the next object in the underlying collection.
2362 * A lock is obtained on the mutex before the collection is accessed.
2364 * @return The next object in the collection.
2365 * @throws NoSuchElementException if there are no more elements
2367 public Object
next()
2369 synchronized (mutex
)
2376 * Returns <code>true</code> if objects can still be retrieved from the iterator
2377 * using <code>next()</code>. A lock is obtained on the mutex before
2378 * the collection is accessed.
2380 * @return <code>true</code> if at least one element is still to be returned by
2381 * <code>next()</code>.
2383 public boolean hasNext()
2385 synchronized (mutex
)
2392 * Removes the object that was last returned by <code>next()</code>
2393 * from the underlying collection. Only one call to this method is
2394 * allowed per call to the <code>next()</code> method, and it does
2395 * not affect the value that will be returned by <code>next()</code>.
2396 * Thus, if element n was retrieved from the collection by
2397 * <code>next()</code>, it is this element that gets removed.
2398 * Regardless of whether this takes place or not, element n+1 is
2399 * still returned on the subsequent <code>next()</code> call.
2401 * @throws IllegalStateException if next has not yet been called or remove
2402 * has already been called since the last call to next.
2403 * @throws UnsupportedOperationException if this Iterator does not support
2404 * the remove operation.
2406 public void remove()
2408 synchronized (mutex
)
2413 } // class SynchronizedIterator
2416 * Returns a synchronized (thread-safe) list wrapper backed by the
2417 * given list. Notice that element access through the iterators
2418 * is thread-safe, but if the list can be structurally modified
2419 * (adding or removing elements) then you should synchronize around the
2420 * iteration to avoid non-deterministic behavior:<br>
2422 * List l = Collections.synchronizedList(new List(...));
2426 * Iterator i = l.iterator();
2427 * while (i.hasNext())
2432 * The returned List implements Serializable, but can only be serialized if
2433 * the list it wraps is likewise Serializable. In addition, if the wrapped
2434 * list implements RandomAccess, this does too.
2436 * @param l the list to wrap
2437 * @return a synchronized view of the list
2441 public static List
synchronizedList(List l
)
2443 if (l
instanceof RandomAccess
)
2444 return new SynchronizedRandomAccessList(l
);
2445 return new SynchronizedList(l
);
2449 * The implementation of {@link #synchronizedList(List)} for sequential
2450 * lists. This class name is required for compatibility with Sun's JDK
2451 * serializability. Package visible, so that lists such as Vector.subList()
2452 * can specify which object to synchronize on.
2454 * @author Eric Blake <ebb9@email.byu.edu>
2456 static class SynchronizedList
extends SynchronizedCollection
2460 * Compatible with JDK 1.4.
2462 private static final long serialVersionUID
= -7754090372962971524L;
2465 * The wrapped list; stored both here and in the superclass to avoid
2466 * excessive casting. Package visible for use by subclass.
2467 * @serial the wrapped list
2472 * Wrap a given list.
2473 * @param l the list to wrap
2474 * @throws NullPointerException if l is null
2476 SynchronizedList(List l
)
2483 * Called only by trusted code to specify the mutex as well as the list.
2484 * @param sync the mutex
2487 SynchronizedList(Object sync
, List l
)
2494 * Insert an element into the underlying list at a given position (optional
2495 * operation). This shifts all existing elements from that position to the
2496 * end one index to the right. This version of add has no return, since it is
2497 * assumed to always succeed if there is no exception. Before the
2498 * addition takes place, a lock is obtained on the mutex.
2500 * @param index the location to insert the item
2501 * @param o the object to insert
2502 * @throws UnsupportedOperationException if this list does not support the
2504 * @throws IndexOutOfBoundsException if index < 0 || index > size()
2505 * @throws ClassCastException if o cannot be added to this list due to its
2507 * @throws IllegalArgumentException if o cannot be added to this list for
2509 * @throws NullPointerException if o is null and this list doesn't support
2510 * the addition of null values.
2512 public void add(int index
, Object o
)
2514 synchronized (mutex
)
2521 * Add an element to the end of the underlying list (optional operation).
2522 * If the list imposes restraints on what can be inserted, such as no null
2523 * elements, this should be documented. A lock is obtained on the mutex before
2524 * any of the elements are added.
2526 * @param o the object to add
2527 * @return <code>true</code>, as defined by Collection for a modified list
2528 * @throws UnsupportedOperationException if this list does not support the
2530 * @throws ClassCastException if o cannot be added to this list due to its
2532 * @throws IllegalArgumentException if o cannot be added to this list for
2534 * @throws NullPointerException if o is null and this list doesn't support
2535 * the addition of null values.
2537 public boolean addAll(int index
, Collection c
)
2539 synchronized (mutex
)
2541 return list
.addAll(index
, c
);
2546 * Tests whether the underlying list is equal to the supplied object.
2547 * The object is deemed to be equal if it is also a <code>List</code>
2548 * of equal size and with the same elements (i.e. each element, e1,
2549 * in list, l1, and each element, e2, in l2, must return <code>true</code> for
2550 * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the
2551 * comparison is made, a lock is obtained on the mutex.
2553 * @param o The object to test for equality with the underlying list.
2554 * @return <code>true</code> if o is equal to the underlying list under the above
2557 public boolean equals(Object o
)
2559 synchronized (mutex
)
2561 return list
.equals(o
);
2566 * Retrieves the object at the specified index. A lock
2567 * is obtained on the mutex before the list is accessed.
2569 * @param index the index of the element to be returned
2570 * @return the element at index index in this list
2571 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2573 public Object
get(int index
)
2575 synchronized (mutex
)
2577 return list
.get(index
);
2582 * Obtains a hashcode for the underlying list, first obtaining
2583 * a lock on the mutex. The calculation of the hashcode is
2584 * detailed in the documentation for the <code>List</code>
2587 * @return The hashcode of the underlying list.
2588 * @see List#hashCode()
2590 public int hashCode()
2592 synchronized (mutex
)
2594 return list
.hashCode();
2599 * Obtain the first index at which a given object is to be found in the
2600 * underlying list. A lock is obtained on the mutex before the list is
2603 * @param o the object to search for
2604 * @return the least integer n such that <code>o == null ? get(n) == null :
2605 * o.equals(get(n))</code>, or -1 if there is no such index.
2606 * @throws ClassCastException if the type of o is not a valid
2607 * type for this list.
2608 * @throws NullPointerException if o is null and this
2609 * list does not support null values.
2612 public int indexOf(Object o
)
2614 synchronized (mutex
)
2616 return list
.indexOf(o
);
2621 * Obtain the last index at which a given object is to be found in this
2622 * underlying list. A lock is obtained on the mutex before the list
2625 * @return the greatest integer n such that <code>o == null ? get(n) == null
2626 * : o.equals(get(n))</code>, or -1 if there is no such index.
2627 * @throws ClassCastException if the type of o is not a valid
2628 * type for this list.
2629 * @throws NullPointerException if o is null and this
2630 * list does not support null values.
2632 public int lastIndexOf(Object o
)
2634 synchronized (mutex
)
2636 return list
.lastIndexOf(o
);
2641 * Retrieves a synchronized wrapper around the underlying list's
2642 * list iterator. A lock is obtained on the mutex before the
2643 * list iterator is retrieved.
2645 * @return A list iterator over the elements in the underlying list.
2646 * The list iterator allows additional list-specific operations
2647 * to be performed, in addition to those supplied by the
2648 * standard iterator.
2650 public ListIterator
listIterator()
2652 synchronized (mutex
)
2654 return new SynchronizedListIterator(mutex
, list
.listIterator());
2659 * Retrieves a synchronized wrapper around the underlying list's
2660 * list iterator. A lock is obtained on the mutex before the
2661 * list iterator is retrieved. The iterator starts at the
2662 * index supplied, leading to the element at that index being
2663 * the first one returned by <code>next()</code>. Calling
2664 * <code>previous()</code> from this initial position returns
2667 * @param index the position, between 0 and size() inclusive, to begin the
2669 * @return A list iterator over the elements in the underlying list.
2670 * The list iterator allows additional list-specific operations
2671 * to be performed, in addition to those supplied by the
2672 * standard iterator.
2673 * @throws IndexOutOfBoundsException if index < 0 || index > size()
2675 public ListIterator
listIterator(int index
)
2677 synchronized (mutex
)
2679 return new SynchronizedListIterator(mutex
, list
.listIterator(index
));
2684 * Remove the element at a given position in the underlying list (optional
2685 * operation). All remaining elements are shifted to the left to fill the gap.
2686 * A lock on the mutex is obtained before the element is removed.
2688 * @param index the position within the list of the object to remove
2689 * @return the object that was removed
2690 * @throws UnsupportedOperationException if this list does not support the
2692 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2694 public Object
remove(int index
)
2696 synchronized (mutex
)
2698 return list
.remove(index
);
2703 * Replace an element of the underlying list with another object (optional
2704 * operation). A lock is obtained on the mutex before the element is
2707 * @param index the position within this list of the element to be replaced
2708 * @param o the object to replace it with
2709 * @return the object that was replaced
2710 * @throws UnsupportedOperationException if this list does not support the
2712 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2713 * @throws ClassCastException if o cannot be added to this list due to its
2715 * @throws IllegalArgumentException if o cannot be added to this list for
2717 * @throws NullPointerException if o is null and this
2718 * list does not support null values.
2720 public Object
set(int index
, Object o
)
2722 synchronized (mutex
)
2724 return list
.set(index
, o
);
2729 * Obtain a List view of a subsection of the underlying list, from fromIndex
2730 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2731 * sublist is empty. The returned list should be modifiable if and only
2732 * if this list is modifiable. Changes to the returned list should be
2733 * reflected in this list. If this list is structurally modified in
2734 * any way other than through the returned list, the result of any subsequent
2735 * operations on the returned list is undefined. A lock is obtained
2736 * on the mutex before the creation of the sublist. The returned list
2737 * is also synchronized, using the same mutex.
2739 * @param fromIndex the index that the returned list should start from
2741 * @param toIndex the index that the returned list should go to (exclusive)
2742 * @return a List backed by a subsection of this list
2743 * @throws IndexOutOfBoundsException if fromIndex < 0
2744 * || toIndex > size() || fromIndex > toIndex
2746 public List
subList(int fromIndex
, int toIndex
)
2748 synchronized (mutex
)
2750 return new SynchronizedList(mutex
, list
.subList(fromIndex
, toIndex
));
2753 } // class SynchronizedList
2756 * The implementation of {@link #synchronizedList(List)} for random-access
2757 * lists. This class name is required for compatibility with Sun's JDK
2760 * @author Eric Blake <ebb9@email.byu.edu>
2762 private static final class SynchronizedRandomAccessList
2763 extends SynchronizedList
implements RandomAccess
2766 * Compatible with JDK 1.4.
2768 private static final long serialVersionUID
= 1530674583602358482L;
2771 * Wrap a given list.
2772 * @param l the list to wrap
2773 * @throws NullPointerException if l is null
2775 SynchronizedRandomAccessList(List l
)
2781 * Called only by trusted code to specify the mutex as well as the
2783 * @param sync the mutex
2786 SynchronizedRandomAccessList(Object sync
, List l
)
2792 * Obtain a List view of a subsection of the underlying list, from fromIndex
2793 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2794 * sublist is empty. The returned list should be modifiable if and only
2795 * if this list is modifiable. Changes to the returned list should be
2796 * reflected in this list. If this list is structurally modified in
2797 * any way other than through the returned list, the result of any subsequent
2798 * operations on the returned list is undefined. A lock is obtained
2799 * on the mutex before the creation of the sublist. The returned list
2800 * is also synchronized, using the same mutex. Random accessibility
2801 * is also extended to the new list.
2803 * @param fromIndex the index that the returned list should start from
2805 * @param toIndex the index that the returned list should go to (exclusive)
2806 * @return a List backed by a subsection of this list
2807 * @throws IndexOutOfBoundsException if fromIndex < 0
2808 * || toIndex > size() || fromIndex > toIndex
2810 public List
subList(int fromIndex
, int toIndex
)
2812 synchronized (mutex
)
2814 return new SynchronizedRandomAccessList(mutex
,
2815 list
.subList(fromIndex
,
2819 } // class SynchronizedRandomAccessList
2822 * The implementation of {@link SynchronizedList#listIterator()}. This
2823 * iterator must "sync" on the same object as the list it iterates over.
2825 * @author Eric Blake <ebb9@email.byu.edu>
2827 private static final class SynchronizedListIterator
2828 extends SynchronizedIterator
implements ListIterator
2831 * The wrapped iterator, stored both here and in the superclass to
2832 * avoid excessive casting.
2834 private final ListIterator li
;
2837 * Only trusted code creates a wrapper, with the specified sync.
2838 * @param sync the mutex
2839 * @param li the wrapped iterator
2841 SynchronizedListIterator(Object sync
, ListIterator li
)
2848 * Insert an element into the underlying list at the current position of
2849 * the iterator (optional operation). The element is inserted in between
2850 * the element that would be returned by <code>previous()</code> and the
2851 * element that would be returned by <code>next()</code>. After the
2852 * insertion, a subsequent call to next is unaffected, but
2853 * a call to previous returns the item that was added. The values returned
2854 * by nextIndex() and previousIndex() are incremented. A lock is obtained
2855 * on the mutex before the addition takes place.
2857 * @param o the object to insert into the list
2858 * @throws ClassCastException if the object is of a type which cannot be added
2860 * @throws IllegalArgumentException if some other aspect of the object stops
2861 * it being added to this list.
2862 * @throws UnsupportedOperationException if this ListIterator does not
2863 * support the add operation.
2865 public void add(Object o
)
2867 synchronized (mutex
)
2874 * Tests whether there are elements remaining in the underlying list
2875 * in the reverse direction. In other words, <code>previous()</code>
2876 * will not fail with a NoSuchElementException. A lock is obtained
2877 * on the mutex before the check takes place.
2879 * @return <code>true</code> if the list continues in the reverse direction
2881 public boolean hasPrevious()
2883 synchronized (mutex
)
2885 return li
.hasPrevious();
2890 * Find the index of the element that would be returned by a call to
2891 * <code>next()</code>. If hasNext() returns <code>false</code>, this
2892 * returns the list size. A lock is obtained on the mutex before the
2893 * query takes place.
2895 * @return the index of the element that would be returned by next()
2897 public int nextIndex()
2899 synchronized (mutex
)
2901 return li
.nextIndex();
2906 * Obtain the previous element from the underlying list. Repeated
2907 * calls to previous may be used to iterate backwards over the entire list,
2908 * or calls to next and previous may be used together to go forwards and
2909 * backwards. Alternating calls to next and previous will return the same
2910 * element. A lock is obtained on the mutex before the object is retrieved.
2912 * @return the next element in the list in the reverse direction
2913 * @throws NoSuchElementException if there are no more elements
2915 public Object
previous()
2917 synchronized (mutex
)
2919 return li
.previous();
2924 * Find the index of the element that would be returned by a call to
2925 * previous. If hasPrevious() returns <code>false</code>, this returns -1.
2926 * A lock is obtained on the mutex before the query takes place.
2928 * @return the index of the element that would be returned by previous()
2930 public int previousIndex()
2932 synchronized (mutex
)
2934 return li
.previousIndex();
2939 * Replace the element last returned by a call to <code>next()</code> or
2940 * <code>previous()</code> with a given object (optional operation). This
2941 * method may only be called if neither <code>add()</code> nor
2942 * <code>remove()</code> have been called since the last call to
2943 * <code>next()</code> or <code>previous</code>. A lock is obtained
2944 * on the mutex before the list is modified.
2946 * @param o the object to replace the element with
2947 * @throws ClassCastException the object is of a type which cannot be added
2949 * @throws IllegalArgumentException some other aspect of the object stops
2950 * it being added to this list
2951 * @throws IllegalStateException if neither next or previous have been
2952 * called, or if add or remove has been called since the last call
2953 * to next or previous
2954 * @throws UnsupportedOperationException if this ListIterator does not
2955 * support the set operation
2957 public void set(Object o
)
2959 synchronized (mutex
)
2964 } // class SynchronizedListIterator
2967 * Returns a synchronized (thread-safe) map wrapper backed by the given
2968 * map. Notice that element access through the collection views and their
2969 * iterators are thread-safe, but if the map can be structurally modified
2970 * (adding or removing elements) then you should synchronize around the
2971 * iteration to avoid non-deterministic behavior:<br>
2973 * Map m = Collections.synchronizedMap(new Map(...));
2975 * Set s = m.keySet(); // safe outside a synchronized block
2976 * synchronized (m) // synch on m, not s
2978 * Iterator i = s.iterator();
2979 * while (i.hasNext())
2984 * The returned Map implements Serializable, but can only be serialized if
2985 * the map it wraps is likewise Serializable.
2987 * @param m the map to wrap
2988 * @return a synchronized view of the map
2991 public static Map
synchronizedMap(Map m
)
2993 return new SynchronizedMap(m
);
2997 * The implementation of {@link #synchronizedMap(Map)}. This
2998 * class name is required for compatibility with Sun's JDK serializability.
3000 * @author Eric Blake <ebb9@email.byu.edu>
3002 private static class SynchronizedMap
implements Map
, Serializable
3005 * Compatible with JDK 1.4.
3007 private static final long serialVersionUID
= 1978198479659022715L;
3011 * @serial the real map
3013 private final Map m
;
3016 * The object to synchronize on. When an instance is created via public
3017 * methods, it will be this; but other uses like
3018 * SynchronizedSortedMap.subMap() must specify another mutex. Package
3019 * visible for use by subclass.
3025 * Cache the entry set.
3027 private transient Set entries
;
3030 * Cache the key set.
3032 private transient Set keys
;
3035 * Cache the value collection.
3037 private transient Collection values
;
3041 * @param m the map to wrap
3042 * @throws NullPointerException if m is null
3044 SynchronizedMap(Map m
)
3049 throw new NullPointerException();
3053 * Called only by trusted code to specify the mutex as well as the map.
3054 * @param sync the mutex
3057 SynchronizedMap(Object sync
, Map m
)
3064 * Clears all the entries from the underlying map. A lock is obtained
3065 * on the mutex before the map is cleared.
3067 * @throws UnsupportedOperationException if clear is not supported
3071 synchronized (mutex
)
3078 * Returns <code>true</code> if the underlying map contains a entry for the given key.
3079 * A lock is obtained on the mutex before the map is queried.
3081 * @param key the key to search for.
3082 * @return <code>true</code> if the underlying map contains the key.
3083 * @throws ClassCastException if the key is of an inappropriate type.
3084 * @throws NullPointerException if key is <code>null</code> but the map
3085 * does not permit null keys.
3087 public boolean containsKey(Object key
)
3089 synchronized (mutex
)
3091 return m
.containsKey(key
);
3096 * Returns <code>true</code> if the underlying map contains at least one entry with the
3097 * given value. In other words, returns <code>true</code> if a value v exists where
3098 * <code>(value == null ? v == null : value.equals(v))</code>. This usually
3099 * requires linear time. A lock is obtained on the mutex before the map
3102 * @param value the value to search for
3103 * @return <code>true</code> if the map contains the value
3104 * @throws ClassCastException if the type of the value is not a valid type
3106 * @throws NullPointerException if the value is null and the map doesn't
3107 * support null values.
3109 public boolean containsValue(Object value
)
3111 synchronized (mutex
)
3113 return m
.containsValue(value
);
3117 // This is one of the ickiest cases of nesting I've ever seen. It just
3118 // means "return a SynchronizedSet, except that the iterator() method
3119 // returns an SynchronizedIterator whose next() method returns a
3120 // synchronized wrapper around its normal return value".
3121 public Set
entrySet()
3123 // Define this here to spare some nesting.
3124 class SynchronizedMapEntry
implements Map
.Entry
3127 SynchronizedMapEntry(Object o
)
3133 * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code>
3134 * with the same key and value as the underlying entry. A lock is
3135 * obtained on the mutex before the comparison takes place.
3137 * @param o The object to compare with this entry.
3138 * @return <code>true</code> if o is equivalent to the underlying map entry.
3140 public boolean equals(Object o
)
3142 synchronized (mutex
)
3149 * Returns the key used in the underlying map entry. A lock is obtained
3150 * on the mutex before the key is retrieved.
3152 * @return The key of the underlying map entry.
3154 public Object
getKey()
3156 synchronized (mutex
)
3163 * Returns the value used in the underlying map entry. A lock is obtained
3164 * on the mutex before the value is retrieved.
3166 * @return The value of the underlying map entry.
3168 public Object
getValue()
3170 synchronized (mutex
)
3172 return e
.getValue();
3177 * Computes the hash code for the underlying map entry.
3178 * This computation is described in the documentation for the
3179 * <code>Map</code> interface. A lock is obtained on the mutex
3180 * before the underlying map is accessed.
3182 * @return The hash code of the underlying map entry.
3183 * @see Map#hashCode()
3185 public int hashCode()
3187 synchronized (mutex
)
3189 return e
.hashCode();
3194 * Replaces the value in the underlying map entry with the specified
3195 * object (optional operation). A lock is obtained on the mutex
3196 * before the map is altered. The map entry, in turn, will alter
3197 * the underlying map object. The operation is undefined if the
3198 * <code>remove()</code> method of the iterator has been called
3201 * @param value the new value to store
3202 * @return the old value
3203 * @throws UnsupportedOperationException if the operation is not supported.
3204 * @throws ClassCastException if the value is of the wrong type.
3205 * @throws IllegalArgumentException if something about the value
3206 * prevents it from existing in this map.
3207 * @throws NullPointerException if the map forbids null values.
3209 public Object
setValue(Object value
)
3211 synchronized (mutex
)
3213 return e
.setValue(value
);
3218 * Returns a textual representation of the underlying map entry.
3219 * A lock is obtained on the mutex before the entry is accessed.
3221 * @return The contents of the map entry in <code>String</code> form.
3223 public String
toString()
3225 synchronized (mutex
)
3227 return e
.toString();
3230 } // class SynchronizedMapEntry
3232 // Now the actual code.
3233 if (entries
== null)
3234 synchronized (mutex
)
3236 entries
= new SynchronizedSet(mutex
, m
.entrySet())
3239 * Returns an iterator over the set. The iterator has no specific order,
3240 * unless further specified. A lock is obtained on the set's mutex
3241 * before the iterator is created. The created iterator is also
3244 * @return A synchronized set iterator.
3246 public Iterator
iterator()
3248 synchronized (super.mutex
)
3250 return new SynchronizedIterator(super.mutex
, c
.iterator())
3253 * Retrieves the next map entry from the iterator.
3254 * A lock is obtained on the iterator's mutex before
3255 * the entry is created. The new map entry is enclosed in
3256 * a thread-safe wrapper.
3258 * @return A synchronized map entry.
3260 public Object
next()
3262 synchronized (super.mutex
)
3264 return new SynchronizedMapEntry(super.next());
3276 * Returns <code>true</code> if the object, o, is also an instance
3277 * of <code>Map</code> and contains an equivalent
3278 * entry set to that of the underlying map. A lock
3279 * is obtained on the mutex before the objects are
3282 * @param o The object to compare.
3283 * @return <code>true</code> if o and the underlying map are equivalent.
3285 public boolean equals(Object o
)
3287 synchronized (mutex
)
3294 * Returns the value associated with the given key, or null
3295 * if no such mapping exists. An ambiguity exists with maps
3296 * that accept null values as a return value of null could
3297 * be due to a non-existent mapping or simply a null value
3298 * for that key. To resolve this, <code>containsKey</code>
3299 * should be used. A lock is obtained on the mutex before
3300 * the value is retrieved from the underlying map.
3302 * @param key The key of the required mapping.
3303 * @return The value associated with the given key, or
3304 * null if no such mapping exists.
3305 * @throws ClassCastException if the key is an inappropriate type.
3306 * @throws NullPointerException if this map does not accept null keys.
3308 public Object
get(Object key
)
3310 synchronized (mutex
)
3317 * Calculates the hash code of the underlying map as the
3318 * sum of the hash codes of all entries. A lock is obtained
3319 * on the mutex before the hash code is computed.
3321 * @return The hash code of the underlying map.
3323 public int hashCode()
3325 synchronized (mutex
)
3327 return m
.hashCode();
3332 * Returns <code>true</code> if the underlying map contains no entries.
3333 * A lock is obtained on the mutex before the map is examined.
3335 * @return <code>true</code> if the map is empty.
3337 public boolean isEmpty()
3339 synchronized (mutex
)
3346 * Returns a thread-safe set view of the keys in the underlying map. The
3347 * set is backed by the map, so that changes in one show up in the other.
3348 * Modifications made while an iterator is in progress cause undefined
3349 * behavior. If the set supports removal, these methods remove the
3350 * underlying mapping from the map: <code>Iterator.remove</code>,
3351 * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
3352 * and <code>clear</code>. Element addition, via <code>add</code> or
3353 * <code>addAll</code>, is not supported via this set. A lock is obtained
3354 * on the mutex before the set is created.
3356 * @return A synchronized set containing the keys of the underlying map.
3361 synchronized (mutex
)
3363 keys
= new SynchronizedSet(mutex
, m
.keySet());
3369 * Associates the given key to the given value (optional operation). If the
3370 * underlying map already contains the key, its value is replaced. Be aware
3371 * that in a map that permits <code>null</code> values, a null return does not
3372 * always imply that the mapping was created. A lock is obtained on the mutex
3373 * before the modification is made.
3375 * @param key the key to map.
3376 * @param value the value to be mapped.
3377 * @return the previous value of the key, or null if there was no mapping
3378 * @throws UnsupportedOperationException if the operation is not supported
3379 * @throws ClassCastException if the key or value is of the wrong type
3380 * @throws IllegalArgumentException if something about this key or value
3381 * prevents it from existing in this map
3382 * @throws NullPointerException if either the key or the value is null,
3383 * and the map forbids null keys or values
3384 * @see #containsKey(Object)
3386 public Object
put(Object key
, Object value
)
3388 synchronized (mutex
)
3390 return m
.put(key
, value
);
3395 * Copies all entries of the given map to the underlying one (optional
3396 * operation). If the map already contains a key, its value is replaced.
3397 * A lock is obtained on the mutex before the operation proceeds.
3399 * @param m the mapping to load into this map
3400 * @throws UnsupportedOperationException if the operation is not supported
3401 * @throws ClassCastException if a key or value is of the wrong type
3402 * @throws IllegalArgumentException if something about a key or value
3403 * prevents it from existing in this map
3404 * @throws NullPointerException if the map forbids null keys or values, or
3405 * if <code>m</code> is null.
3406 * @see #put(Object, Object)
3408 public void putAll(Map map
)
3410 synchronized (mutex
)
3417 * Removes the mapping for the key, o, if present (optional operation). If
3418 * the key is not present, this returns null. Note that maps which permit
3419 * null values may also return null if the key was removed. A prior
3420 * <code>containsKey()</code> check is required to avoid this ambiguity.
3421 * Before the mapping is removed, a lock is obtained on the mutex.
3423 * @param key the key to remove
3424 * @return the value the key mapped to, or null if not present
3425 * @throws UnsupportedOperationException if deletion is unsupported
3426 * @throws NullPointerException if the key is null and this map doesn't
3427 * support null keys.
3428 * @throws ClassCastException if the type of the key is not a valid type
3431 public Object
remove(Object o
)
3433 synchronized (mutex
)
3440 * Retrieves the size of the underlying map. A lock
3441 * is obtained on the mutex before access takes place.
3442 * Maps with a size greater than <code>Integer.MAX_VALUE</code>
3443 * return <code>Integer.MAX_VALUE</code> instead.
3445 * @return The size of the underlying map.
3449 synchronized (mutex
)
3456 * Returns a textual representation of the underlying
3457 * map. A lock is obtained on the mutex before the map
3460 * @return The map in <code>String</code> form.
3462 public String
toString()
3464 synchronized (mutex
)
3466 return m
.toString();
3471 * Returns a synchronized collection view of the values in the underlying
3472 * map. The collection is backed by the map, so that changes in one show up in
3473 * the other. Modifications made while an iterator is in progress cause
3474 * undefined behavior. If the collection supports removal, these methods
3475 * remove the underlying mapping from the map: <code>Iterator.remove</code>,
3476 * <code>Collection.remove</code>, <code>removeAll</code>,
3477 * <code>retainAll</code>, and <code>clear</code>. Element addition, via
3478 * <code>add</code> or <code>addAll</code>, is not supported via this
3479 * collection. A lock is obtained on the mutex before the collection
3482 * @return the collection of all values in the underlying map.
3484 public Collection
values()
3487 synchronized (mutex
)
3489 values
= new SynchronizedCollection(mutex
, m
.values());
3493 } // class SynchronizedMap
3496 * Returns a synchronized (thread-safe) set wrapper backed by the given
3497 * set. Notice that element access through the iterator is thread-safe, but
3498 * if the set can be structurally modified (adding or removing elements)
3499 * then you should synchronize around the iteration to avoid
3500 * non-deterministic behavior:<br>
3502 * Set s = Collections.synchronizedSet(new Set(...));
3506 * Iterator i = s.iterator();
3507 * while (i.hasNext())
3512 * The returned Set implements Serializable, but can only be serialized if
3513 * the set it wraps is likewise Serializable.
3515 * @param s the set to wrap
3516 * @return a synchronized view of the set
3519 public static Set
synchronizedSet(Set s
)
3521 return new SynchronizedSet(s
);
3525 * The implementation of {@link #synchronizedSet(Set)}. This class
3526 * name is required for compatibility with Sun's JDK serializability.
3527 * Package visible, so that sets such as Hashtable.keySet()
3528 * can specify which object to synchronize on.
3530 * @author Eric Blake <ebb9@email.byu.edu>
3532 static class SynchronizedSet
extends SynchronizedCollection
3536 * Compatible with JDK 1.4.
3538 private static final long serialVersionUID
= 487447009682186044L;
3542 * @param s the set to wrap
3543 * @throws NullPointerException if s is null
3545 SynchronizedSet(Set s
)
3551 * Called only by trusted code to specify the mutex as well as the set.
3552 * @param sync the mutex
3555 SynchronizedSet(Object sync
, Set s
)
3561 * Returns <code>true</code> if the object, o, is a <code>Set</code>
3562 * of the same size as the underlying set, and contains
3563 * each element, e, which occurs in the underlying set.
3564 * A lock is obtained on the mutex before the comparison
3567 * @param o The object to compare against.
3568 * @return <code>true</code> if o is an equivalent set.
3570 public boolean equals(Object o
)
3572 synchronized (mutex
)
3579 * Computes the hash code for the underlying set as the
3580 * sum of the hash code of all elements within the set.
3581 * A lock is obtained on the mutex before the computation
3584 * @return The hash code for the underlying set.
3586 public int hashCode()
3588 synchronized (mutex
)
3590 return c
.hashCode();
3593 } // class SynchronizedSet
3596 * Returns a synchronized (thread-safe) sorted map wrapper backed by the
3597 * given map. Notice that element access through the collection views,
3598 * subviews, and their iterators are thread-safe, but if the map can be
3599 * structurally modified (adding or removing elements) then you should
3600 * synchronize around the iteration to avoid non-deterministic behavior:<br>
3602 * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
3604 * Set s = m.keySet(); // safe outside a synchronized block
3605 * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
3606 * Set s2 = m2.keySet(); // safe outside a synchronized block
3607 * synchronized (m) // synch on m, not m2, s or s2
3609 * Iterator i = s.iterator();
3610 * while (i.hasNext())
3612 * i = s2.iterator();
3613 * while (i.hasNext())
3618 * The returned SortedMap implements Serializable, but can only be
3619 * serialized if the map it wraps is likewise Serializable.
3621 * @param m the sorted map to wrap
3622 * @return a synchronized view of the sorted map
3625 public static SortedMap
synchronizedSortedMap(SortedMap m
)
3627 return new SynchronizedSortedMap(m
);
3631 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
3632 * class name is required for compatibility with Sun's JDK serializability.
3634 * @author Eric Blake <ebb9@email.byu.edu>
3636 private static final class SynchronizedSortedMap
extends SynchronizedMap
3637 implements SortedMap
3640 * Compatible with JDK 1.4.
3642 private static final long serialVersionUID
= -8798146769416483793L;
3645 * The wrapped map; stored both here and in the superclass to avoid
3646 * excessive casting.
3647 * @serial the wrapped map
3649 private final SortedMap sm
;
3653 * @param sm the map to wrap
3654 * @throws NullPointerException if sm is null
3656 SynchronizedSortedMap(SortedMap sm
)
3663 * Called only by trusted code to specify the mutex as well as the map.
3664 * @param sync the mutex
3667 SynchronizedSortedMap(Object sync
, SortedMap sm
)
3674 * Returns the comparator used in sorting the underlying map, or null if
3675 * it is the keys' natural ordering. A lock is obtained on the mutex
3676 * before the comparator is retrieved.
3678 * @return the sorting comparator.
3680 public Comparator
comparator()
3682 synchronized (mutex
)
3684 return sm
.comparator();
3689 * Returns the first, lowest sorted, key from the underlying map.
3690 * A lock is obtained on the mutex before the map is accessed.
3692 * @return the first key.
3693 * @throws NoSuchElementException if this map is empty.
3695 public Object
firstKey()
3697 synchronized (mutex
)
3699 return sm
.firstKey();
3704 * Returns a submap containing the keys from the first
3705 * key (as returned by <code>firstKey()</code>) to
3706 * the key before that specified. The submap supports all
3707 * operations supported by the underlying map and all actions
3708 * taking place on the submap are also reflected in the underlying
3709 * map. A lock is obtained on the mutex prior to submap creation.
3710 * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>.
3711 * The submap retains the thread-safe status of this map.
3713 * @param toKey the exclusive upper range of the submap.
3714 * @return a submap from <code>firstKey()</code> to the
3715 * the key preceding toKey.
3716 * @throws ClassCastException if toKey is not comparable to the underlying
3718 * @throws IllegalArgumentException if toKey is outside the map's range.
3719 * @throws NullPointerException if toKey is null. but the map does not allow
3722 public SortedMap
headMap(Object toKey
)
3724 synchronized (mutex
)
3726 return new SynchronizedSortedMap(mutex
, sm
.headMap(toKey
));
3731 * Returns the last, highest sorted, key from the underlying map.
3732 * A lock is obtained on the mutex before the map is accessed.
3734 * @return the last key.
3735 * @throws NoSuchElementException if this map is empty.
3737 public Object
lastKey()
3739 synchronized (mutex
)
3741 return sm
.lastKey();
3746 * Returns a submap containing the keys from fromKey to
3747 * the key before toKey. The submap supports all
3748 * operations supported by the underlying map and all actions
3749 * taking place on the submap are also reflected in the underlying
3750 * map. A lock is obtained on the mutex prior to submap creation.
3751 * The submap retains the thread-safe status of this map.
3753 * @param fromKey the inclusive lower range of the submap.
3754 * @param toKey the exclusive upper range of the submap.
3755 * @return a submap from fromKey to the key preceding toKey.
3756 * @throws ClassCastException if fromKey or toKey is not comparable
3757 * to the underlying map's contents.
3758 * @throws IllegalArgumentException if fromKey or toKey is outside the map's
3760 * @throws NullPointerException if fromKey or toKey is null. but the map does
3761 * not allow null keys.
3763 public SortedMap
subMap(Object fromKey
, Object toKey
)
3765 synchronized (mutex
)
3767 return new SynchronizedSortedMap(mutex
, sm
.subMap(fromKey
, toKey
));
3772 * Returns a submap containing all the keys from fromKey onwards.
3773 * The submap supports all operations supported by the underlying
3774 * map and all actions taking place on the submap are also reflected
3775 * in the underlying map. A lock is obtained on the mutex prior to
3776 * submap creation. The submap retains the thread-safe status of
3779 * @param fromKey the inclusive lower range of the submap.
3780 * @return a submap from fromKey to <code>lastKey()</code>.
3781 * @throws ClassCastException if fromKey is not comparable to the underlying
3783 * @throws IllegalArgumentException if fromKey is outside the map's range.
3784 * @throws NullPointerException if fromKey is null. but the map does not allow
3787 public SortedMap
tailMap(Object fromKey
)
3789 synchronized (mutex
)
3791 return new SynchronizedSortedMap(mutex
, sm
.tailMap(fromKey
));
3794 } // class SynchronizedSortedMap
3797 * Returns a synchronized (thread-safe) sorted set wrapper backed by the
3798 * given set. Notice that element access through the iterator and through
3799 * subviews are thread-safe, but if the set can be structurally modified
3800 * (adding or removing elements) then you should synchronize around the
3801 * iteration to avoid non-deterministic behavior:<br>
3803 * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
3805 * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
3806 * synchronized (s) // synch on s, not s2
3808 * Iterator i = s2.iterator();
3809 * while (i.hasNext())
3814 * The returned SortedSet implements Serializable, but can only be
3815 * serialized if the set it wraps is likewise Serializable.
3817 * @param s the sorted set to wrap
3818 * @return a synchronized view of the sorted set
3821 public static SortedSet
synchronizedSortedSet(SortedSet s
)
3823 return new SynchronizedSortedSet(s
);
3827 * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
3828 * class name is required for compatibility with Sun's JDK serializability.
3830 * @author Eric Blake <ebb9@email.byu.edu>
3832 private static final class SynchronizedSortedSet
extends SynchronizedSet
3833 implements SortedSet
3836 * Compatible with JDK 1.4.
3838 private static final long serialVersionUID
= 8695801310862127406L;
3841 * The wrapped set; stored both here and in the superclass to avoid
3842 * excessive casting.
3843 * @serial the wrapped set
3845 private final SortedSet ss
;
3849 * @param ss the set to wrap
3850 * @throws NullPointerException if ss is null
3852 SynchronizedSortedSet(SortedSet ss
)
3859 * Called only by trusted code to specify the mutex as well as the set.
3860 * @param sync the mutex
3863 SynchronizedSortedSet(Object sync
, SortedSet ss
)
3870 * Returns the comparator used in sorting the underlying set, or null if
3871 * it is the elements' natural ordering. A lock is obtained on the mutex
3872 * before the comparator is retrieved.
3874 * @return the sorting comparator.
3876 public Comparator
comparator()
3878 synchronized (mutex
)
3880 return ss
.comparator();
3885 * Returns the first, lowest sorted, element from the underlying set.
3886 * A lock is obtained on the mutex before the set is accessed.
3888 * @return the first element.
3889 * @throws NoSuchElementException if this set is empty.
3891 public Object
first()
3893 synchronized (mutex
)
3900 * Returns a subset containing the element from the first
3901 * element (as returned by <code>first()</code>) to
3902 * the element before that specified. The subset supports all
3903 * operations supported by the underlying set and all actions
3904 * taking place on the subset are also reflected in the underlying
3905 * set. A lock is obtained on the mutex prior to subset creation.
3906 * This operation is equivalent to <code>subSet(first(), toElement)</code>.
3907 * The subset retains the thread-safe status of this set.
3909 * @param toElement the exclusive upper range of the subset.
3910 * @return a subset from <code>first()</code> to the
3911 * the element preceding toElement.
3912 * @throws ClassCastException if toElement is not comparable to the underlying
3914 * @throws IllegalArgumentException if toElement is outside the set's range.
3915 * @throws NullPointerException if toElement is null. but the set does not allow
3918 public SortedSet
headSet(Object toElement
)
3920 synchronized (mutex
)
3922 return new SynchronizedSortedSet(mutex
, ss
.headSet(toElement
));
3927 * Returns the last, highest sorted, element from the underlying set.
3928 * A lock is obtained on the mutex before the set is accessed.
3930 * @return the last element.
3931 * @throws NoSuchElementException if this set is empty.
3933 public Object
last()
3935 synchronized (mutex
)
3942 * Returns a subset containing the elements from fromElement to
3943 * the element before toElement. The subset supports all
3944 * operations supported by the underlying set and all actions
3945 * taking place on the subset are also reflected in the underlying
3946 * set. A lock is obtained on the mutex prior to subset creation.
3947 * The subset retains the thread-safe status of this set.
3949 * @param fromElement the inclusive lower range of the subset.
3950 * @param toElement the exclusive upper range of the subset.
3951 * @return a subset from fromElement to the element preceding toElement.
3952 * @throws ClassCastException if fromElement or toElement is not comparable
3953 * to the underlying set's contents.
3954 * @throws IllegalArgumentException if fromElement or toElement is outside the set's
3956 * @throws NullPointerException if fromElement or toElement is null. but the set does
3957 * not allow null elements.
3959 public SortedSet
subSet(Object fromElement
, Object toElement
)
3961 synchronized (mutex
)
3963 return new SynchronizedSortedSet(mutex
,
3964 ss
.subSet(fromElement
, toElement
));
3969 * Returns a subset containing all the elements from fromElement onwards.
3970 * The subset supports all operations supported by the underlying
3971 * set and all actions taking place on the subset are also reflected
3972 * in the underlying set. A lock is obtained on the mutex prior to
3973 * subset creation. The subset retains the thread-safe status of
3976 * @param fromElement the inclusive lower range of the subset.
3977 * @return a subset from fromElement to <code>last()</code>.
3978 * @throws ClassCastException if fromElement is not comparable to the underlying
3980 * @throws IllegalArgumentException if fromElement is outside the set's range.
3981 * @throws NullPointerException if fromElement is null. but the set does not allow
3984 public SortedSet
tailSet(Object fromElement
)
3986 synchronized (mutex
)
3988 return new SynchronizedSortedSet(mutex
, ss
.tailSet(fromElement
));
3991 } // class SynchronizedSortedSet
3995 * Returns an unmodifiable view of the given collection. This allows
3996 * "read-only" access, although changes in the backing collection show up
3997 * in this view. Attempts to modify the collection directly or via iterators
3998 * will fail with {@link UnsupportedOperationException}. Although this view
3999 * prevents changes to the structure of the collection and its elements, the values
4000 * referenced by the objects in the collection can still be modified.
4003 * Since the collection might be a List or a Set, and those have incompatible
4004 * equals and hashCode requirements, this relies on Object's implementation
4005 * rather than passing those calls on to the wrapped collection. The returned
4006 * Collection implements Serializable, but can only be serialized if
4007 * the collection it wraps is likewise Serializable.
4009 * @param c the collection to wrap
4010 * @return a read-only view of the collection
4013 public static Collection
unmodifiableCollection(Collection c
)
4015 return new UnmodifiableCollection(c
);
4019 * The implementation of {@link #unmodifiableCollection(Collection)}. This
4020 * class name is required for compatibility with Sun's JDK serializability.
4022 * @author Eric Blake <ebb9@email.byu.edu>
4024 private static class UnmodifiableCollection
4025 implements Collection
, Serializable
4028 * Compatible with JDK 1.4.
4030 private static final long serialVersionUID
= 1820017752578914078L;
4033 * The wrapped collection. Package visible for use by subclasses.
4034 * @serial the real collection
4039 * Wrap a given collection.
4040 * @param c the collection to wrap
4041 * @throws NullPointerException if c is null
4043 UnmodifiableCollection(Collection c
)
4047 throw new NullPointerException();
4051 * Blocks the addition of elements to the underlying collection.
4052 * This method never returns, throwing an exception instead.
4054 * @param o the object to add.
4055 * @return <code>true</code> if the collection was modified as a result of this action.
4056 * @throws UnsupportedOperationException as an unmodifiable collection does not
4057 * support the add operation.
4059 public boolean add(Object o
)
4061 throw new UnsupportedOperationException();
4065 * Blocks the addition of a collection of elements to the underlying
4066 * collection. This method never returns, throwing an exception instead.
4068 * @param c the collection to add.
4069 * @return <code>true</code> if the collection was modified as a result of this action.
4070 * @throws UnsupportedOperationException as an unmodifiable collection does not
4071 * support the <code>addAll</code> operation.
4073 public boolean addAll(Collection c
)
4075 throw new UnsupportedOperationException();
4079 * Blocks the clearing of the underlying collection. This method never
4080 * returns, throwing an exception instead.
4082 * @throws UnsupportedOperationException as an unmodifiable collection does
4083 * not support the <code>clear()</code> operation.
4087 throw new UnsupportedOperationException();
4091 * Test whether the underlying collection contains a given object as one of its
4094 * @param o the element to look for.
4095 * @return <code>true</code> if the underlying collection contains at least
4096 * one element e such that
4097 * <code>o == null ? e == null : o.equals(e)</code>.
4098 * @throws ClassCastException if the type of o is not a valid type for the
4099 * underlying collection.
4100 * @throws NullPointerException if o is null and the underlying collection
4101 * doesn't support null values.
4103 public boolean contains(Object o
)
4105 return c
.contains(o
);
4109 * Test whether the underlying collection contains every element in a given
4112 * @param c the collection to test for.
4113 * @return <code>true</code> if for every element o in c, contains(o) would
4114 * return <code>true</code>.
4115 * @throws ClassCastException if the type of any element in c is not a valid
4116 * type for the underlying collection.
4117 * @throws NullPointerException if some element of c is null and the underlying
4118 * collection does not support null values.
4119 * @throws NullPointerException if c itself is null.
4121 public boolean containsAll(Collection c1
)
4123 return c
.containsAll(c1
);
4127 * Tests whether the underlying collection is empty, that is,
4130 * @return <code>true</code> if this collection contains no elements.
4132 public boolean isEmpty()
4138 * Obtain an Iterator over the underlying collection, which maintains
4139 * its unmodifiable nature.
4141 * @return an UnmodifiableIterator over the elements of the underlying
4142 * collection, in any order.
4144 public Iterator
iterator()
4146 return new UnmodifiableIterator(c
.iterator());
4150 * Blocks the removal of an object from the underlying collection.
4151 * This method never returns, throwing an exception instead.
4153 * @param o The object to remove.
4154 * @return <code>true</code> if the object was removed (i.e. the underlying
4155 * collection returned 1 or more instances of o).
4156 * @throws UnsupportedOperationException as an unmodifiable collection
4157 * does not support the <code>remove()</code> operation.
4159 public boolean remove(Object o
)
4161 throw new UnsupportedOperationException();
4165 * Blocks the removal of a collection of objects from the underlying
4166 * collection. This method never returns, throwing an exception
4169 * @param c The collection of objects to remove.
4170 * @return <code>true</code> if the collection was modified.
4171 * @throws UnsupportedOperationException as an unmodifiable collection
4172 * does not support the <code>removeAll()</code> operation.
4174 public boolean removeAll(Collection c
)
4176 throw new UnsupportedOperationException();
4180 * Blocks the removal of all elements from the underlying collection,
4181 * except those in the supplied collection. This method never returns,
4182 * throwing an exception instead.
4184 * @param c The collection of objects to retain.
4185 * @return <code>true</code> if the collection was modified.
4186 * @throws UnsupportedOperationException as an unmodifiable collection
4187 * does not support the <code>retainAll()</code> operation.
4189 public boolean retainAll(Collection c
)
4191 throw new UnsupportedOperationException();
4195 * Retrieves the number of elements in the underlying collection.
4197 * @return the number of elements in the collection.
4205 * Copy the current contents of the underlying collection into an array.
4207 * @return an array of type Object[] with a length equal to the size of the
4208 * underlying collection and containing the elements currently in
4209 * the underlying collection, in any order.
4211 public Object
[] toArray()
4217 * Copy the current contents of the underlying collection into an array. If
4218 * the array passed as an argument has length less than the size of the
4219 * underlying collection, an array of the same run-time type as a, with a length
4220 * equal to the size of the underlying collection, is allocated using reflection.
4221 * Otherwise, a itself is used. The elements of the underlying collection are
4222 * copied into it, and if there is space in the array, the following element is
4223 * set to null. The resultant array is returned.
4224 * Note: The fact that the following element is set to null is only useful
4225 * if it is known that this collection does not contain any null elements.
4227 * @param a the array to copy this collection into.
4228 * @return an array containing the elements currently in the underlying
4229 * collection, in any order.
4230 * @throws ArrayStoreException if the type of any element of the
4231 * collection is not a subtype of the element type of a.
4233 public Object
[] toArray(Object
[] a
)
4235 return c
.toArray(a
);
4239 * A textual representation of the unmodifiable collection.
4241 * @return The unmodifiable collection in the form of a <code>String</code>.
4243 public String
toString()
4245 return c
.toString();
4247 } // class UnmodifiableCollection
4250 * The implementation of the various iterator methods in the
4251 * unmodifiable classes.
4253 * @author Eric Blake <ebb9@email.byu.edu>
4255 private static class UnmodifiableIterator
implements Iterator
4258 * The wrapped iterator.
4260 private final Iterator i
;
4263 * Only trusted code creates a wrapper.
4264 * @param i the wrapped iterator
4266 UnmodifiableIterator(Iterator i
)
4272 * Obtains the next element in the underlying collection.
4274 * @return the next element in the collection.
4275 * @throws NoSuchElementException if there are no more elements.
4277 public Object
next()
4282 * Tests whether there are still elements to be retrieved from the
4283 * underlying collection by <code>next()</code>. When this method
4284 * returns <code>true</code>, an exception will not be thrown on calling
4285 * <code>next()</code>.
4287 * @return <code>true</code> if there is at least one more element in the underlying
4290 public boolean hasNext()
4296 * Blocks the removal of elements from the underlying collection by the
4299 * @throws UnsupportedOperationException as an unmodifiable collection
4300 * does not support the removal of elements by its iterator.
4302 public void remove()
4304 throw new UnsupportedOperationException();
4306 } // class UnmodifiableIterator
4309 * Returns an unmodifiable view of the given list. This allows
4310 * "read-only" access, although changes in the backing list show up
4311 * in this view. Attempts to modify the list directly, via iterators, or
4312 * via sublists, will fail with {@link UnsupportedOperationException}.
4313 * Although this view prevents changes to the structure of the list and
4314 * its elements, the values referenced by the objects in the list can
4315 * still be modified.
4318 * The returned List implements Serializable, but can only be serialized if
4319 * the list it wraps is likewise Serializable. In addition, if the wrapped
4320 * list implements RandomAccess, this does too.
4322 * @param l the list to wrap
4323 * @return a read-only view of the list
4327 public static List
unmodifiableList(List l
)
4329 if (l
instanceof RandomAccess
)
4330 return new UnmodifiableRandomAccessList(l
);
4331 return new UnmodifiableList(l
);
4335 * The implementation of {@link #unmodifiableList(List)} for sequential
4336 * lists. This class name is required for compatibility with Sun's JDK
4339 * @author Eric Blake <ebb9@email.byu.edu>
4341 private static class UnmodifiableList
extends UnmodifiableCollection
4345 * Compatible with JDK 1.4.
4347 private static final long serialVersionUID
= -283967356065247728L;
4351 * The wrapped list; stored both here and in the superclass to avoid
4352 * excessive casting. Package visible for use by subclass.
4353 * @serial the wrapped list
4358 * Wrap a given list.
4359 * @param l the list to wrap
4360 * @throws NullPointerException if l is null
4362 UnmodifiableList(List l
)
4369 * Blocks the addition of an element to the underlying
4370 * list at a specific index. This method never returns,
4371 * throwing an exception instead.
4373 * @param index The index at which to place the new element.
4374 * @param o the object to add.
4375 * @throws UnsupportedOperationException as an unmodifiable
4376 * list doesn't support the <code>add()</code> operation.
4378 public void add(int index
, Object o
)
4380 throw new UnsupportedOperationException();
4384 * Blocks the addition of a collection of elements to the
4385 * underlying list at a specific index. This method never
4386 * returns, throwing an exception instead.
4388 * @param index The index at which to place the new element.
4389 * @param c the collections of objects to add.
4390 * @throws UnsupportedOperationException as an unmodifiable
4391 * list doesn't support the <code>addAll()</code> operation.
4393 public boolean addAll(int index
, Collection c
)
4395 throw new UnsupportedOperationException();
4399 * Returns <code>true</code> if the object, o, is an instance of
4400 * <code>List</code> with the same size and elements
4401 * as the underlying list.
4403 * @param o The object to compare.
4404 * @return <code>true</code> if o is equivalent to the underlying list.
4406 public boolean equals(Object o
)
4408 return list
.equals(o
);
4412 * Retrieves the element at a given index in the underlying list.
4414 * @param index the index of the element to be returned
4415 * @return the element at index index in this list
4416 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
4418 public Object
get(int index
)
4420 return list
.get(index
);
4424 * Computes the hash code for the underlying list.
4425 * The exact computation is described in the documentation
4426 * of the <code>List</code> interface.
4428 * @return The hash code of the underlying list.
4429 * @see List#hashCode()
4431 public int hashCode()
4433 return list
.hashCode();
4437 * Obtain the first index at which a given object is to be found in the
4440 * @param o the object to search for
4441 * @return the least integer n such that <code>o == null ? get(n) == null :
4442 * o.equals(get(n))</code>, or -1 if there is no such index.
4443 * @throws ClassCastException if the type of o is not a valid
4444 * type for the underlying list.
4445 * @throws NullPointerException if o is null and the underlying
4446 * list does not support null values.
4448 public int indexOf(Object o
)
4450 return list
.indexOf(o
);
4454 * Obtain the last index at which a given object is to be found in the
4457 * @return the greatest integer n such that <code>o == null ? get(n) == null
4458 * : o.equals(get(n))</code>, or -1 if there is no such index.
4459 * @throws ClassCastException if the type of o is not a valid
4460 * type for the underlying list.
4461 * @throws NullPointerException if o is null and the underlying
4462 * list does not support null values.
4464 public int lastIndexOf(Object o
)
4466 return list
.lastIndexOf(o
);
4470 * Obtains a list iterator over the underlying list, starting at the beginning
4471 * and maintaining the unmodifiable nature of this list.
4473 * @return a <code>UnmodifiableListIterator</code> over the elements of the
4474 * underlying list, in order, starting at the beginning.
4476 public ListIterator
listIterator()
4478 return new UnmodifiableListIterator(list
.listIterator());
4482 * Obtains a list iterator over the underlying list, starting at the specified
4483 * index and maintaining the unmodifiable nature of this list. An initial call
4484 * to <code>next()</code> will retrieve the element at the specified index,
4485 * and an initial call to <code>previous()</code> will retrieve the element
4489 * @param index the position, between 0 and size() inclusive, to begin the
4491 * @return a <code>UnmodifiableListIterator</code> over the elements of the
4492 * underlying list, in order, starting at the specified index.
4493 * @throws IndexOutOfBoundsException if index < 0 || index > size()
4495 public ListIterator
listIterator(int index
)
4497 return new UnmodifiableListIterator(list
.listIterator(index
));
4501 * Blocks the removal of the element at the specified index.
4502 * This method never returns, throwing an exception instead.
4504 * @param index The index of the element to remove.
4505 * @return the removed element.
4506 * @throws UnsupportedOperationException as an unmodifiable
4507 * list does not support the <code>remove()</code>
4510 public Object
remove(int index
)
4512 throw new UnsupportedOperationException();
4516 * Blocks the replacement of the element at the specified index.
4517 * This method never returns, throwing an exception instead.
4519 * @param index The index of the element to replace.
4520 * @param o The new object to place at the specified index.
4521 * @return the replaced element.
4522 * @throws UnsupportedOperationException as an unmodifiable
4523 * list does not support the <code>set()</code>
4526 public Object
set(int index
, Object o
)
4528 throw new UnsupportedOperationException();
4532 * Obtain a List view of a subsection of the underlying list, from
4533 * fromIndex (inclusive) to toIndex (exclusive). If the two indices
4534 * are equal, the sublist is empty. The returned list will be
4535 * unmodifiable, like this list. Changes to the elements of the
4536 * returned list will be reflected in the underlying list. No structural
4537 * modifications can take place in either list.
4539 * @param fromIndex the index that the returned list should start from
4541 * @param toIndex the index that the returned list should go to (exclusive).
4542 * @return a List backed by a subsection of the underlying list.
4543 * @throws IndexOutOfBoundsException if fromIndex < 0
4544 * || toIndex > size() || fromIndex > toIndex.
4546 public List
subList(int fromIndex
, int toIndex
)
4548 return unmodifiableList(list
.subList(fromIndex
, toIndex
));
4550 } // class UnmodifiableList
4553 * The implementation of {@link #unmodifiableList(List)} for random-access
4554 * lists. This class name is required for compatibility with Sun's JDK
4557 * @author Eric Blake <ebb9@email.byu.edu>
4559 private static final class UnmodifiableRandomAccessList
4560 extends UnmodifiableList
implements RandomAccess
4563 * Compatible with JDK 1.4.
4565 private static final long serialVersionUID
= -2542308836966382001L;
4568 * Wrap a given list.
4569 * @param l the list to wrap
4570 * @throws NullPointerException if l is null
4572 UnmodifiableRandomAccessList(List l
)
4576 } // class UnmodifiableRandomAccessList
4579 * The implementation of {@link UnmodifiableList#listIterator()}.
4581 * @author Eric Blake <ebb9@email.byu.edu>
4583 private static final class UnmodifiableListIterator
4584 extends UnmodifiableIterator
implements ListIterator
4587 * The wrapped iterator, stored both here and in the superclass to
4588 * avoid excessive casting.
4590 private final ListIterator li
;
4593 * Only trusted code creates a wrapper.
4594 * @param li the wrapped iterator
4596 UnmodifiableListIterator(ListIterator li
)
4603 * Blocks the addition of an object to the list underlying this iterator.
4604 * This method never returns, throwing an exception instead.
4606 * @param o The object to add.
4607 * @throws UnsupportedOperationException as the iterator of an unmodifiable
4608 * list does not support the <code>add()</code> operation.
4610 public void add(Object o
)
4612 throw new UnsupportedOperationException();
4616 * Tests whether there are still elements to be retrieved from the
4617 * underlying collection by <code>previous()</code>. When this method
4618 * returns <code>true</code>, an exception will not be thrown on calling
4619 * <code>previous()</code>.
4621 * @return <code>true</code> if there is at least one more element prior to the
4622 * current position in the underlying list.
4624 public boolean hasPrevious()
4626 return li
.hasPrevious();
4630 * Find the index of the element that would be returned by a call to next.
4631 * If <code>hasNext()</code> returns <code>false</code>, this returns the list size.
4633 * @return the index of the element that would be returned by
4634 * <code>next()</code>.
4636 public int nextIndex()
4638 return li
.nextIndex();
4642 * Obtains the previous element in the underlying list.
4644 * @return the previous element in the list.
4645 * @throws NoSuchElementException if there are no more prior elements.
4647 public Object
previous()
4649 return li
.previous();
4653 * Find the index of the element that would be returned by a call to
4654 * previous. If <code>hasPrevious()</code> returns <code>false</code>,
4657 * @return the index of the element that would be returned by
4658 * <code>previous()</code>.
4660 public int previousIndex()
4662 return li
.previousIndex();
4666 * Blocks the replacement of an element in the list underlying this
4667 * iterator. This method never returns, throwing an exception instead.
4669 * @param o The new object to replace the existing one.
4670 * @throws UnsupportedOperationException as the iterator of an unmodifiable
4671 * list does not support the <code>set()</code> operation.
4673 public void set(Object o
)
4675 throw new UnsupportedOperationException();
4677 } // class UnmodifiableListIterator
4680 * Returns an unmodifiable view of the given map. This allows "read-only"
4681 * access, although changes in the backing map show up in this view.
4682 * Attempts to modify the map directly, or via collection views or their
4683 * iterators will fail with {@link UnsupportedOperationException}.
4684 * Although this view prevents changes to the structure of the map and its
4685 * entries, the values referenced by the objects in the map can still be
4689 * The returned Map implements Serializable, but can only be serialized if
4690 * the map it wraps is likewise Serializable.
4692 * @param m the map to wrap
4693 * @return a read-only view of the map
4696 public static Map
unmodifiableMap(Map m
)
4698 return new UnmodifiableMap(m
);
4702 * The implementation of {@link #unmodifiableMap(Map)}. This
4703 * class name is required for compatibility with Sun's JDK serializability.
4705 * @author Eric Blake <ebb9@email.byu.edu>
4707 private static class UnmodifiableMap
implements Map
, Serializable
4710 * Compatible with JDK 1.4.
4712 private static final long serialVersionUID
= -1034234728574286014L;
4716 * @serial the real map
4718 private final Map m
;
4721 * Cache the entry set.
4723 private transient Set entries
;
4726 * Cache the key set.
4728 private transient Set keys
;
4731 * Cache the value collection.
4733 private transient Collection values
;
4737 * @param m the map to wrap
4738 * @throws NullPointerException if m is null
4740 UnmodifiableMap(Map m
)
4744 throw new NullPointerException();
4748 * Blocks the clearing of entries from the underlying map.
4749 * This method never returns, throwing an exception instead.
4751 * @throws UnsupportedOperationException as an unmodifiable
4752 * map does not support the <code>clear()</code> operation.
4756 throw new UnsupportedOperationException();
4760 * Returns <code>true</code> if the underlying map contains a mapping for
4763 * @param key the key to search for
4764 * @return <code>true</code> if the map contains the key
4765 * @throws ClassCastException if the key is of an inappropriate type
4766 * @throws NullPointerException if key is <code>null</code> but the map
4767 * does not permit null keys
4769 public boolean containsKey(Object key
)
4771 return m
.containsKey(key
);
4775 * Returns <code>true</code> if the underlying map contains at least one mapping with
4776 * the given value. In other words, it returns <code>true</code> if a value v exists where
4777 * <code>(value == null ? v == null : value.equals(v))</code>. This usually
4778 * requires linear time.
4780 * @param value the value to search for
4781 * @return <code>true</code> if the map contains the value
4782 * @throws ClassCastException if the type of the value is not a valid type
4784 * @throws NullPointerException if the value is null and the map doesn't
4785 * support null values.
4787 public boolean containsValue(Object value
)
4789 return m
.containsValue(value
);
4793 * Returns a unmodifiable set view of the entries in the underlying map.
4794 * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>.
4795 * The set is backed by the map, so that changes in one show up in the other.
4796 * Modifications made while an iterator is in progress cause undefined
4797 * behavior. These modifications are again limited to the values of
4800 * @return the unmodifiable set view of all mapping entries.
4803 public Set
entrySet()
4805 if (entries
== null)
4806 entries
= new UnmodifiableEntrySet(m
.entrySet());
4811 * The implementation of {@link UnmodifiableMap#entrySet()}. This class
4812 * name is required for compatibility with Sun's JDK serializability.
4814 * @author Eric Blake <ebb9@email.byu.edu>
4816 private static final class UnmodifiableEntrySet
extends UnmodifiableSet
4817 implements Serializable
4820 * Compatible with JDK 1.4.
4822 private static final long serialVersionUID
= 7854390611657943733L;
4826 * @param s the set to wrap
4828 UnmodifiableEntrySet(Set s
)
4833 // The iterator must return unmodifiable map entries.
4834 public Iterator
iterator()
4836 return new UnmodifiableIterator(c
.iterator())
4839 * Obtains the next element from the underlying set of
4842 * @return the next element in the collection.
4843 * @throws NoSuchElementException if there are no more elements.
4845 public Object
next()
4847 final Map
.Entry e
= (Map
.Entry
) super.next();
4848 return new Map
.Entry()
4851 * Returns <code>true</code> if the object, o, is also a map entry with an
4852 * identical key and value.
4854 * @param o the object to compare.
4855 * @return <code>true</code> if o is an equivalent map entry.
4857 public boolean equals(Object o
)
4863 * Returns the key of this map entry.
4867 public Object
getKey()
4873 * Returns the value of this map entry.
4875 * @return the value.
4877 public Object
getValue()
4879 return e
.getValue();
4883 * Computes the hash code of this map entry.
4884 * The computation is described in the <code>Map</code>
4885 * interface documentation.
4887 * @return the hash code of this entry.
4888 * @see Map#hashCode()
4890 public int hashCode()
4892 return e
.hashCode();
4896 * Blocks the alteration of the value of this map entry.
4897 * This method never returns, throwing an exception instead.
4899 * @param value The new value.
4900 * @throws UnsupportedOperationException as an unmodifiable
4901 * map entry does not support the <code>setValue()</code>
4904 public Object
setValue(Object value
)
4906 throw new UnsupportedOperationException();
4910 * Returns a textual representation of the map entry.
4912 * @return The map entry as a <code>String</code>.
4914 public String
toString()
4916 return e
.toString();
4922 } // class UnmodifiableEntrySet
4925 * Returns <code>true</code> if the object, o, is also an instance
4926 * of <code>Map</code> with an equal set of map entries.
4928 * @param o The object to compare.
4929 * @return <code>true</code> if o is an equivalent map.
4931 public boolean equals(Object o
)
4937 * Returns the value associated with the supplied key or
4938 * null if no such mapping exists. An ambiguity can occur
4939 * if null values are accepted by the underlying map.
4940 * In this case, <code>containsKey()</code> can be used
4941 * to separate the two possible cases of a null result.
4943 * @param key The key to look up.
4944 * @return the value associated with the key, or null if key not in map.
4945 * @throws ClassCastException if the key is an inappropriate type.
4946 * @throws NullPointerException if this map does not accept null keys.
4947 * @see #containsKey(Object)
4949 public Object
get(Object key
)
4955 * Blocks the addition of a new entry to the underlying map.
4956 * This method never returns, throwing an exception instead.
4958 * @param key The new key.
4959 * @param value The new value.
4960 * @return the previous value of the key, or null if there was no mapping.
4961 * @throws UnsupportedOperationException as an unmodifiable
4962 * map does not support the <code>put()</code> operation.
4964 public Object
put(Object key
, Object value
)
4966 throw new UnsupportedOperationException();
4970 * Computes the hash code for the underlying map, as the sum
4971 * of the hash codes of all entries.
4973 * @return The hash code of the underlying map.
4974 * @see Map.Entry#hashCode()
4976 public int hashCode()
4978 return m
.hashCode();
4982 * Returns <code>true</code> if the underlying map contains no entries.
4984 * @return <code>true</code> if the map is empty.
4986 public boolean isEmpty()
4992 * Returns a unmodifiable set view of the keys in the underlying map.
4993 * The set is backed by the map, so that changes in one show up in the other.
4994 * Modifications made while an iterator is in progress cause undefined
4995 * behavior. These modifications are again limited to the values of
4998 * @return the set view of all keys.
5003 keys
= new UnmodifiableSet(m
.keySet());
5008 * Blocks the addition of the entries in the supplied map.
5009 * This method never returns, throwing an exception instead.
5011 * @param m The map, the entries of which should be added
5012 * to the underlying map.
5013 * @throws UnsupportedOperationException as an unmodifiable
5014 * map does not support the <code>putAll</code> operation.
5016 public void putAll(Map m
)
5018 throw new UnsupportedOperationException();
5022 * Blocks the removal of an entry from the map.
5023 * This method never returns, throwing an exception instead.
5025 * @param o The key of the entry to remove.
5026 * @return The value the key was associated with, or null
5027 * if no such mapping existed. Null is also returned
5028 * if the removed entry had a null key.
5029 * @throws UnsupportedOperationException as an unmodifiable
5030 * map does not support the <code>remove</code> operation.
5032 public Object
remove(Object o
)
5034 throw new UnsupportedOperationException();
5039 * Returns the number of key-value mappings in the underlying map.
5040 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
5043 * @return the number of mappings.
5051 * Returns a textual representation of the map.
5053 * @return The map in the form of a <code>String</code>.
5055 public String
toString()
5057 return m
.toString();
5061 * Returns a unmodifiable collection view of the values in the underlying map.
5062 * The collection is backed by the map, so that changes in one show up in the other.
5063 * Modifications made while an iterator is in progress cause undefined
5064 * behavior. These modifications are again limited to the values of
5067 * @return the collection view of all values.
5069 public Collection
values()
5072 values
= new UnmodifiableCollection(m
.values());
5075 } // class UnmodifiableMap
5078 * Returns an unmodifiable view of the given set. This allows
5079 * "read-only" access, although changes in the backing set show up
5080 * in this view. Attempts to modify the set directly or via iterators
5081 * will fail with {@link UnsupportedOperationException}.
5082 * Although this view prevents changes to the structure of the set and its
5083 * entries, the values referenced by the objects in the set can still be
5087 * The returned Set implements Serializable, but can only be serialized if
5088 * the set it wraps is likewise Serializable.
5090 * @param s the set to wrap
5091 * @return a read-only view of the set
5094 public static Set
unmodifiableSet(Set s
)
5096 return new UnmodifiableSet(s
);
5100 * The implementation of {@link #unmodifiableSet(Set)}. This class
5101 * name is required for compatibility with Sun's JDK serializability.
5103 * @author Eric Blake <ebb9@email.byu.edu>
5105 private static class UnmodifiableSet
extends UnmodifiableCollection
5109 * Compatible with JDK 1.4.
5111 private static final long serialVersionUID
= -9215047833775013803L;
5115 * @param s the set to wrap
5116 * @throws NullPointerException if s is null
5118 UnmodifiableSet(Set s
)
5124 * Returns <code>true</code> if the object, o, is also an instance of
5125 * <code>Set</code> of the same size and with the same entries.
5127 * @return <code>true</code> if o is an equivalent set.
5129 public boolean equals(Object o
)
5135 * Computes the hash code of this set, as the sum of the
5136 * hash codes of all elements within the set.
5138 * @return the hash code of the set.
5140 public int hashCode()
5142 return c
.hashCode();
5144 } // class UnmodifiableSet
5147 * Returns an unmodifiable view of the given sorted map. This allows
5148 * "read-only" access, although changes in the backing map show up in this
5149 * view. Attempts to modify the map directly, via subviews, via collection
5150 * views, or iterators, will fail with {@link UnsupportedOperationException}.
5151 * Although this view prevents changes to the structure of the map and its
5152 * entries, the values referenced by the objects in the map can still be
5156 * The returned SortedMap implements Serializable, but can only be
5157 * serialized if the map it wraps is likewise Serializable.
5159 * @param m the map to wrap
5160 * @return a read-only view of the map
5163 public static SortedMap
unmodifiableSortedMap(SortedMap m
)
5165 return new UnmodifiableSortedMap(m
);
5169 * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
5170 * class name is required for compatibility with Sun's JDK serializability.
5172 * @author Eric Blake <ebb9@email.byu.edu>
5174 private static class UnmodifiableSortedMap
extends UnmodifiableMap
5175 implements SortedMap
5178 * Compatible with JDK 1.4.
5180 private static final long serialVersionUID
= -8806743815996713206L;
5183 * The wrapped map; stored both here and in the superclass to avoid
5184 * excessive casting.
5185 * @serial the wrapped map
5187 private final SortedMap sm
;
5191 * @param sm the map to wrap
5192 * @throws NullPointerException if sm is null
5194 UnmodifiableSortedMap(SortedMap sm
)
5201 * Returns the comparator used in sorting the underlying map,
5202 * or null if it is the keys' natural ordering.
5204 * @return the sorting comparator.
5206 public Comparator
comparator()
5208 return sm
.comparator();
5212 * Returns the first (lowest sorted) key in the map.
5214 * @return the first key.
5215 * @throws NoSuchElementException if this map is empty.
5217 public Object
firstKey()
5219 return sm
.firstKey();
5223 * Returns a unmodifiable view of the portion of the map strictly less
5224 * than toKey. The view is backed by the underlying map, so changes in
5225 * one show up in the other. The submap supports all optional operations
5226 * of the original. This operation is equivalent to
5227 * <code>subMap(firstKey(), toKey)</code>.
5230 * The returned map throws an IllegalArgumentException any time a key is
5231 * used which is out of the range of toKey. Note that the endpoint, toKey,
5232 * is not included; if you want this value to be included, pass its successor
5233 * object in to toKey. For example, for Integers, you could request
5234 * <code>headMap(new Integer(limit.intValue() + 1))</code>.
5236 * @param toKey the exclusive upper range of the submap.
5237 * @return the submap.
5238 * @throws ClassCastException if toKey is not comparable to the map contents.
5239 * @throws IllegalArgumentException if this is a subMap, and toKey is out
5241 * @throws NullPointerException if toKey is null but the map does not allow
5244 public SortedMap
headMap(Object toKey
)
5246 return new UnmodifiableSortedMap(sm
.headMap(toKey
));
5250 * Returns the last (highest sorted) key in the map.
5252 * @return the last key.
5253 * @throws NoSuchElementException if this map is empty.
5255 public Object
lastKey()
5257 return sm
.lastKey();
5261 * Returns a unmodifiable view of the portion of the map greater than or
5262 * equal to fromKey, and strictly less than toKey. The view is backed by
5263 * the underlying map, so changes in one show up in the other. The submap
5264 * supports all optional operations of the original.
5267 * The returned map throws an IllegalArgumentException any time a key is
5268 * used which is out of the range of fromKey and toKey. Note that the
5269 * lower endpoint is included, but the upper is not; if you want to
5270 * change the inclusion or exclusion of an endpoint, pass its successor
5271 * object in instead. For example, for Integers, you could request
5272 * <code>subMap(new Integer(lowlimit.intValue() + 1),
5273 * new Integer(highlimit.intValue() + 1))</code> to reverse
5274 * the inclusiveness of both endpoints.
5276 * @param fromKey the inclusive lower range of the submap.
5277 * @param toKey the exclusive upper range of the submap.
5278 * @return the submap.
5279 * @throws ClassCastException if fromKey or toKey is not comparable to
5281 * @throws IllegalArgumentException if this is a subMap, and fromKey or
5282 * toKey is out of range.
5283 * @throws NullPointerException if fromKey or toKey is null but the map
5284 * does not allow null keys.
5286 public SortedMap
subMap(Object fromKey
, Object toKey
)
5288 return new UnmodifiableSortedMap(sm
.subMap(fromKey
, toKey
));
5292 * Returns a unmodifiable view of the portion of the map greater than or
5293 * equal to fromKey. The view is backed by the underlying map, so changes
5294 * in one show up in the other. The submap supports all optional operations
5298 * The returned map throws an IllegalArgumentException any time a key is
5299 * used which is out of the range of fromKey. Note that the endpoint, fromKey, is
5300 * included; if you do not want this value to be included, pass its successor object in
5301 * to fromKey. For example, for Integers, you could request
5302 * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
5304 * @param fromKey the inclusive lower range of the submap
5305 * @return the submap
5306 * @throws ClassCastException if fromKey is not comparable to the map
5308 * @throws IllegalArgumentException if this is a subMap, and fromKey is out
5310 * @throws NullPointerException if fromKey is null but the map does not allow
5313 public SortedMap
tailMap(Object fromKey
)
5315 return new UnmodifiableSortedMap(sm
.tailMap(fromKey
));
5317 } // class UnmodifiableSortedMap
5320 * Returns an unmodifiable view of the given sorted set. This allows
5321 * "read-only" access, although changes in the backing set show up
5322 * in this view. Attempts to modify the set directly, via subsets, or via
5323 * iterators, will fail with {@link UnsupportedOperationException}.
5324 * Although this view prevents changes to the structure of the set and its
5325 * entries, the values referenced by the objects in the set can still be
5329 * The returns SortedSet implements Serializable, but can only be
5330 * serialized if the set it wraps is likewise Serializable.
5332 * @param s the set to wrap
5333 * @return a read-only view of the set
5336 public static SortedSet
unmodifiableSortedSet(SortedSet s
)
5338 return new UnmodifiableSortedSet(s
);
5342 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
5343 * class name is required for compatibility with Sun's JDK serializability.
5345 * @author Eric Blake <ebb9@email.byu.edu>
5347 private static class UnmodifiableSortedSet
extends UnmodifiableSet
5348 implements SortedSet
5351 * Compatible with JDK 1.4.
5353 private static final long serialVersionUID
= -4929149591599911165L;
5356 * The wrapped set; stored both here and in the superclass to avoid
5357 * excessive casting.
5358 * @serial the wrapped set
5360 private SortedSet ss
;
5364 * @param ss the set to wrap
5365 * @throws NullPointerException if ss is null
5367 UnmodifiableSortedSet(SortedSet ss
)
5374 * Returns the comparator used in sorting the underlying set,
5375 * or null if it is the elements' natural ordering.
5377 * @return the sorting comparator
5379 public Comparator
comparator()
5381 return ss
.comparator();
5385 * Returns the first (lowest sorted) element in the underlying
5388 * @return the first element.
5389 * @throws NoSuchElementException if the set is empty.
5391 public Object
first()
5397 * Returns a unmodifiable view of the portion of the set strictly
5398 * less than toElement. The view is backed by the underlying set,
5399 * so changes in one show up in the other. The subset supports
5400 * all optional operations of the original. This operation
5401 * is equivalent to <code>subSet(first(), toElement)</code>.
5404 * The returned set throws an IllegalArgumentException any time an element is
5405 * used which is out of the range of toElement. Note that the endpoint, toElement,
5406 * is not included; if you want this value included, pass its successor object in to
5407 * toElement. For example, for Integers, you could request
5408 * <code>headSet(new Integer(limit.intValue() + 1))</code>.
5410 * @param toElement the exclusive upper range of the subset
5411 * @return the subset.
5412 * @throws ClassCastException if toElement is not comparable to the set
5414 * @throws IllegalArgumentException if this is a subSet, and toElement is out
5416 * @throws NullPointerException if toElement is null but the set does not
5417 * allow null elements.
5419 public SortedSet
headSet(Object toElement
)
5421 return new UnmodifiableSortedSet(ss
.headSet(toElement
));
5425 * Returns the last (highest sorted) element in the underlying
5428 * @return the last element.
5429 * @throws NoSuchElementException if the set is empty.
5431 public Object
last()
5437 * Returns a unmodifiable view of the portion of the set greater than or
5438 * equal to fromElement, and strictly less than toElement. The view is backed by
5439 * the underlying set, so changes in one show up in the other. The subset
5440 * supports all optional operations of the original.
5443 * The returned set throws an IllegalArgumentException any time an element is
5444 * used which is out of the range of fromElement and toElement. Note that the
5445 * lower endpoint is included, but the upper is not; if you want to
5446 * change the inclusion or exclusion of an endpoint, pass its successor
5447 * object in instead. For example, for Integers, you can request
5448 * <code>subSet(new Integer(lowlimit.intValue() + 1),
5449 * new Integer(highlimit.intValue() + 1))</code> to reverse
5450 * the inclusiveness of both endpoints.
5452 * @param fromElement the inclusive lower range of the subset.
5453 * @param toElement the exclusive upper range of the subset.
5454 * @return the subset.
5455 * @throws ClassCastException if fromElement or toElement is not comparable
5456 * to the set contents.
5457 * @throws IllegalArgumentException if this is a subSet, and fromElement or
5458 * toElement is out of range.
5459 * @throws NullPointerException if fromElement or toElement is null but the
5460 * set does not allow null elements.
5462 public SortedSet
subSet(Object fromElement
, Object toElement
)
5464 return new UnmodifiableSortedSet(ss
.subSet(fromElement
, toElement
));
5468 * Returns a unmodifiable view of the portion of the set greater than or equal to
5469 * fromElement. The view is backed by the underlying set, so changes in one show up
5470 * in the other. The subset supports all optional operations of the original.
5473 * The returned set throws an IllegalArgumentException any time an element is
5474 * used which is out of the range of fromElement. Note that the endpoint,
5475 * fromElement, is included; if you do not want this value to be included, pass its
5476 * successor object in to fromElement. For example, for Integers, you could request
5477 * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
5479 * @param fromElement the inclusive lower range of the subset
5480 * @return the subset.
5481 * @throws ClassCastException if fromElement is not comparable to the set
5483 * @throws IllegalArgumentException if this is a subSet, and fromElement is
5485 * @throws NullPointerException if fromElement is null but the set does not
5486 * allow null elements.
5488 public SortedSet
tailSet(Object fromElement
)
5490 return new UnmodifiableSortedSet(ss
.tailSet(fromElement
));
5492 } // class UnmodifiableSortedSet
5493 } // class Collections