diff options
Diffstat (limited to 'libjava/classpath/java/util/Collections.java')
| -rw-r--r-- | libjava/classpath/java/util/Collections.java | 5493 |
1 files changed, 5493 insertions, 0 deletions
diff --git a/libjava/classpath/java/util/Collections.java b/libjava/classpath/java/util/Collections.java new file mode 100644 index 0000000..ed8a005 --- /dev/null +++ b/libjava/classpath/java/util/Collections.java @@ -0,0 +1,5493 @@ +/* Collections.java -- Utility class with methods to operate on collections + Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 + Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + + +package java.util; + +import java.io.Serializable; + +/** + * Utility class consisting of static methods that operate on, or return + * Collections. Contains methods to sort, search, reverse, fill and shuffle + * Collections, methods to facilitate interoperability with legacy APIs that + * are unaware of collections, a method to return a list which consists of + * multiple copies of one element, and methods which "wrap" collections to give + * them extra properties, such as thread-safety and unmodifiability. + * <p> + * + * All methods which take a collection throw a {@link NullPointerException} if + * that collection is null. Algorithms which can change a collection may, but + * are not required, to throw the {@link UnsupportedOperationException} that + * the underlying collection would throw during an attempt at modification. + * For example, + * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code> + * does not throw a exception, even though addAll is an unsupported operation + * on a singleton; the reason for this is that addAll did not attempt to + * modify the set. + * + * @author Original author unknown + * @author Eric Blake (ebb9@email.byu.edu) + * @see Collection + * @see Set + * @see List + * @see Map + * @see Arrays + * @since 1.2 + * @status updated to 1.4 + */ +public class Collections +{ + /** + * Constant used to decide cutoff for when a non-RandomAccess list should + * be treated as sequential-access. Basically, quadratic behavior is + * acceptable for small lists when the overhead is so small in the first + * place. I arbitrarily set it to 16, so it may need some tuning. + */ + private static final int LARGE_LIST_SIZE = 16; + + /** + * Determines if a list should be treated as a sequential-access one. + * Rather than the old method of JDK 1.3 of assuming only instanceof + * AbstractSequentialList should be sequential, this uses the new method + * of JDK 1.4 of assuming anything that does NOT implement RandomAccess + * and exceeds a large (unspecified) size should be sequential. + * + * @param l the list to check + * @return <code>true</code> if it should be treated as sequential-access + */ + private static boolean isSequential(List l) + { + return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE; + } + + /** + * This class is non-instantiable. + */ + private Collections() + { + } + + /** + * An immutable, serializable, empty Set. + * @see Serializable + */ + public static final Set EMPTY_SET = new EmptySet(); + + /** + * The implementation of {@link #EMPTY_SET}. This class name is required + * for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class EmptySet extends AbstractSet + implements Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 1582296315990362920L; + + /** + * A private constructor adds overhead. + */ + EmptySet() + { + } + + /** + * The size: always 0! + * @return 0. + */ + public int size() + { + return 0; + } + + /** + * Returns an iterator that does not iterate. + * @return A non-iterating iterator. + */ + // This is really cheating! I think it's perfectly valid, though. + public Iterator iterator() + { + return EMPTY_LIST.iterator(); + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractSet. + /** + * The empty set never contains anything. + * @param o The object to search for. + * @return <code>false</code>. + */ + public boolean contains(Object o) + { + return false; + } + + /** + * This is true only if the given collection is also empty. + * @param c The collection of objects which are to be compared + * against the members of this set. + * @return <code>true</code> if c is empty. + */ + public boolean containsAll(Collection c) + { + return c.isEmpty(); + } + + /** + * Equal only if the other set is empty. + * @param o The object to compare with this set. + * @return <code>true</code> if o is an empty instance of <code>Set</code>. + */ + public boolean equals(Object o) + { + return o instanceof Set && ((Set) o).isEmpty(); + } + + /** + * The hashcode is always 0. + * @return 0. + */ + public int hashCode() + { + return 0; + } + + /** + * Always succeeds with a <code>false</code> result. + * @param o The object to remove. + * @return <code>false</code>. + */ + public boolean remove(Object o) + { + return false; + } + + /** + * Always succeeds with a <code>false</code> result. + * @param c The collection of objects which should + * all be removed from this set. + * @return <code>false</code>. + */ + public boolean removeAll(Collection c) + { + return false; + } + + /** + * Always succeeds with a <code>false</code> result. + * @param c The collection of objects which should + * all be retained within this set. + * @return <code>false</code>. + */ + public boolean retainAll(Collection c) + { + return false; + } + + /** + * The array is always empty. + * @return A new array with a size of 0. + */ + public Object[] toArray() + { + return new Object[0]; + } + + /** + * We don't even need to use reflection! + * @param a An existing array, which can be empty. + * @return The original array with any existing + * initial element set to null. + */ + public Object[] toArray(Object[] a) + { + if (a.length > 0) + a[0] = null; + return a; + } + + /** + * The string never changes. + * + * @return the string "[]". + */ + public String toString() + { + return "[]"; + } + } // class EmptySet + + /** + * An immutable, serializable, empty List, which implements RandomAccess. + * @see Serializable + * @see RandomAccess + */ + public static final List EMPTY_LIST = new EmptyList(); + + /** + * The implementation of {@link #EMPTY_LIST}. This class name is required + * for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class EmptyList extends AbstractList + implements Serializable, RandomAccess + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 8842843931221139166L; + + /** + * A private constructor adds overhead. + */ + EmptyList() + { + } + + /** + * The size is always 0. + * @return 0. + */ + public int size() + { + return 0; + } + + /** + * No matter the index, it is out of bounds. This + * method never returns, throwing an exception instead. + * + * @param index The index of the element to retrieve. + * @return the object at the specified index. + * @throws IndexOutOfBoundsException as any given index + * is outside the bounds of an empty array. + */ + public Object get(int index) + { + throw new IndexOutOfBoundsException(); + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractList. + /** + * Never contains anything. + * @param o The object to search for. + * @return <code>false</code>. + */ + public boolean contains(Object o) + { + return false; + } + + /** + * This is true only if the given collection is also empty. + * @param c The collection of objects, which should be compared + * against the members of this list. + * @return <code>true</code> if c is also empty. + */ + public boolean containsAll(Collection c) + { + return c.isEmpty(); + } + + /** + * Equal only if the other list is empty. + * @param o The object to compare against this list. + * @return <code>true</code> if o is also an empty instance of + * <code>List</code>. + */ + public boolean equals(Object o) + { + return o instanceof List && ((List) o).isEmpty(); + } + + /** + * The hashcode is always 1. + * @return 1. + */ + public int hashCode() + { + return 1; + } + + /** + * Returns -1. + * @param o The object to search for. + * @return -1. + */ + public int indexOf(Object o) + { + return -1; + } + + /** + * Returns -1. + * @param o The object to search for. + * @return -1. + */ + public int lastIndexOf(Object o) + { + return -1; + } + + /** + * Always succeeds with <code>false</code> result. + * @param o The object to remove. + * @return -1. + */ + public boolean remove(Object o) + { + return false; + } + + /** + * Always succeeds with <code>false</code> result. + * @param c The collection of objects which should + * all be removed from this list. + * @return <code>false</code>. + */ + public boolean removeAll(Collection c) + { + return false; + } + + /** + * Always succeeds with <code>false</code> result. + * @param c The collection of objects which should + * all be retained within this list. + * @return <code>false</code>. + */ + public boolean retainAll(Collection c) + { + return false; + } + + /** + * The array is always empty. + * @return A new array with a size of 0. + */ + public Object[] toArray() + { + return new Object[0]; + } + + /** + * We don't even need to use reflection! + * @param a An existing array, which can be empty. + * @return The original array with any existing + * initial element set to null. + */ + public Object[] toArray(Object[] a) + { + if (a.length > 0) + a[0] = null; + return a; + } + + /** + * The string never changes. + * + * @return the string "[]". + */ + public String toString() + { + return "[]"; + } + } // class EmptyList + + /** + * An immutable, serializable, empty Map. + * @see Serializable + */ + public static final Map EMPTY_MAP = new EmptyMap(); + + /** + * The implementation of {@link #EMPTY_MAP}. This class name is required + * for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class EmptyMap extends AbstractMap + implements Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 6428348081105594320L; + + /** + * A private constructor adds overhead. + */ + EmptyMap() + { + } + + /** + * There are no entries. + * @return The empty set. + */ + public Set entrySet() + { + return EMPTY_SET; + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractMap. + /** + * No entries! + * @param key The key to search for. + * @return <code>false</code>. + */ + public boolean containsKey(Object key) + { + return false; + } + + /** + * No entries! + * @param value The value to search for. + * @return <code>false</code>. + */ + public boolean containsValue(Object value) + { + return false; + } + + /** + * Equal to all empty maps. + * @param o The object o to compare against this map. + * @return <code>true</code> if o is also an empty instance of + * <code>Map</code>. + */ + public boolean equals(Object o) + { + return o instanceof Map && ((Map) o).isEmpty(); + } + + /** + * No mappings, so this returns null. + * @param o The key of the object to retrieve. + * @return null. + */ + public Object get(Object o) + { + return null; + } + + /** + * The hashcode is always 0. + * @return 0. + */ + public int hashCode() + { + return 0; + } + + /** + * No entries. + * @return The empty set. + */ + public Set keySet() + { + return EMPTY_SET; + } + + /** + * Remove always succeeds, with null result. + * @param o The key of the mapping to remove. + * @return null, as there is never a mapping for o. + */ + public Object remove(Object o) + { + return null; + } + + /** + * Size is always 0. + * @return 0. + */ + public int size() + { + return 0; + } + + /** + * No entries. Technically, EMPTY_SET, while more specific than a general + * Collection, will work. Besides, that's what the JDK uses! + * @return The empty set. + */ + public Collection values() + { + return EMPTY_SET; + } + + /** + * The string never changes. + * + * @return the string "[]". + */ + public String toString() + { + return "[]"; + } + } // class EmptyMap + + + /** + * Compare two objects with or without a Comparator. If c is null, uses the + * natural ordering. Slightly slower than doing it inline if the JVM isn't + * clever, but worth it for removing a duplicate of the search code. + * Note: This code is also used in Arrays (for sort as well as search). + */ + static final int compare(Object o1, Object o2, Comparator c) + { + return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2); + } + + /** + * Perform a binary search of a List for a key, using the natural ordering of + * the elements. The list must be sorted (as by the sort() method) - if it is + * not, the behavior of this method is undefined, and may be an infinite + * loop. Further, the key must be comparable with every item in the list. If + * the list contains the key more than once, any one of them may be found. + * <p> + * + * This algorithm behaves in log(n) time for {@link RandomAccess} lists, + * and uses a linear search with O(n) link traversals and log(n) comparisons + * with {@link AbstractSequentialList} lists. Note: although the + * specification allows for an infinite loop if the list is unsorted, it will + * not happen in this (Classpath) implementation. + * + * @param l the list to search (must be sorted) + * @param key the value to search for + * @return the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value + * @throws ClassCastException if key could not be compared with one of the + * elements of l + * @throws NullPointerException if a null element has compareTo called + * @see #sort(List) + */ + public static int binarySearch(List l, Object key) + { + return binarySearch(l, key, null); + } + + /** + * Perform a binary search of a List for a key, using a supplied Comparator. + * The list must be sorted (as by the sort() method with the same Comparator) + * - if it is not, the behavior of this method is undefined, and may be an + * infinite loop. Further, the key must be comparable with every item in the + * list. If the list contains the key more than once, any one of them may be + * found. If the comparator is null, the elements' natural ordering is used. + * <p> + * + * This algorithm behaves in log(n) time for {@link RandomAccess} lists, + * and uses a linear search with O(n) link traversals and log(n) comparisons + * with {@link AbstractSequentialList} lists. Note: although the + * specification allows for an infinite loop if the list is unsorted, it will + * not happen in this (Classpath) implementation. + * + * @param l the list to search (must be sorted) + * @param key the value to search for + * @param c the comparator by which the list is sorted + * @return the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value + * @throws ClassCastException if key could not be compared with one of the + * elements of l + * @throws NullPointerException if a null element is compared with natural + * ordering (only possible when c is null) + * @see #sort(List, Comparator) + */ + public static int binarySearch(List l, Object key, Comparator c) + { + int pos = 0; + int low = 0; + int hi = l.size() - 1; + + // We use a linear search with log(n) comparisons using an iterator + // if the list is sequential-access. + if (isSequential(l)) + { + ListIterator itr = l.listIterator(); + int i = 0; + Object o = itr.next(); // Assumes list is not empty (see isSequential) + boolean forward = true; + while (low <= hi) + { + pos = (low + hi) >> 1; + if (i < pos) + { + if (!forward) + itr.next(); // Changing direction first. + for ( ; i != pos; i++, o = itr.next()); + forward = true; + } + else + { + if (forward) + itr.previous(); // Changing direction first. + for ( ; i != pos; i--, o = itr.previous()); + forward = false; + } + final int d = compare(key, o, c); + if (d == 0) + return pos; + else if (d < 0) + hi = pos - 1; + else + // This gets the insertion point right on the last loop + low = ++pos; + } + } + else + { + while (low <= hi) + { + pos = (low + hi) >> 1; + final int d = compare(key, l.get(pos), c); + if (d == 0) + return pos; + else if (d < 0) + hi = pos - 1; + else + // This gets the insertion point right on the last loop + low = ++pos; + } + } + + // If we failed to find it, we do the same whichever search we did. + return -pos - 1; + } + + /** + * Copy one list to another. If the destination list is longer than the + * source list, the remaining elements are unaffected. This method runs in + * linear time. + * + * @param dest the destination list + * @param source the source list + * @throws IndexOutOfBoundsException if the destination list is shorter + * than the source list (the destination will be unmodified) + * @throws UnsupportedOperationException if dest.listIterator() does not + * support the set operation + */ + public static void copy(List dest, List source) + { + int pos = source.size(); + if (dest.size() < pos) + throw new IndexOutOfBoundsException("Source does not fit in dest"); + + Iterator i1 = source.iterator(); + ListIterator i2 = dest.listIterator(); + + while (--pos >= 0) + { + i2.next(); + i2.set(i1.next()); + } + } + + /** + * Returns an Enumeration over a collection. This allows interoperability + * with legacy APIs that require an Enumeration as input. + * + * @param c the Collection to iterate over + * @return an Enumeration backed by an Iterator over c + */ + public static Enumeration enumeration(Collection c) + { + final Iterator i = c.iterator(); + return new Enumeration() + { + /** + * Returns <code>true</code> if there are more elements to + * be enumerated. + * + * @return The result of <code>hasNext()</code> + * called on the underlying iterator. + */ + public final boolean hasMoreElements() + { + return i.hasNext(); + } + + /** + * Returns the next element to be enumerated. + * + * @return The result of <code>next()</code> + * called on the underlying iterator. + */ + public final Object nextElement() + { + return i.next(); + } + }; + } + + /** + * Replace every element of a list with a given value. This method runs in + * linear time. + * + * @param l the list to fill. + * @param val the object to vill the list with. + * @throws UnsupportedOperationException if l.listIterator() does not + * support the set operation. + */ + public static void fill(List l, Object val) + { + ListIterator itr = l.listIterator(); + for (int i = l.size() - 1; i >= 0; --i) + { + itr.next(); + itr.set(val); + } + } + + /** + * Returns the starting index where the specified sublist first occurs + * in a larger list, or -1 if there is no matching position. If + * <code>target.size() > source.size()</code>, this returns -1, + * otherwise this implementation uses brute force, checking for + * <code>source.sublist(i, i + target.size()).equals(target)</code> + * for all possible i. + * + * @param source the list to search + * @param target the sublist to search for + * @return the index where found, or -1 + * @since 1.4 + */ + public static int indexOfSubList(List source, List target) + { + int ssize = source.size(); + for (int i = 0, j = target.size(); j <= ssize; i++, j++) + if (source.subList(i, j).equals(target)) + return i; + return -1; + } + + /** + * Returns the starting index where the specified sublist last occurs + * in a larger list, or -1 if there is no matching position. If + * <code>target.size() > source.size()</code>, this returns -1, + * otherwise this implementation uses brute force, checking for + * <code>source.sublist(i, i + target.size()).equals(target)</code> + * for all possible i. + * + * @param source the list to search + * @param target the sublist to search for + * @return the index where found, or -1 + * @since 1.4 + */ + public static int lastIndexOfSubList(List source, List target) + { + int ssize = source.size(); + for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--) + if (source.subList(i, j).equals(target)) + return i; + return -1; + } + + /** + * Returns an ArrayList holding the elements visited by a given + * Enumeration. This method exists for interoperability between legacy + * APIs and the new Collection API. + * + * @param e the enumeration to put in a list + * @return a list containing the enumeration elements + * @see ArrayList + * @since 1.4 + */ + public static ArrayList list(Enumeration e) + { + ArrayList l = new ArrayList(); + while (e.hasMoreElements()) + l.add(e.nextElement()); + return l; + } + + /** + * Find the maximum element in a Collection, according to the natural + * ordering of the elements. This implementation iterates over the + * Collection, so it works in linear time. + * + * @param c the Collection to find the maximum element of + * @return the maximum element of c + * @exception NoSuchElementException if c is empty + * @exception ClassCastException if elements in c are not mutually comparable + * @exception NullPointerException if null.compareTo is called + */ + public static Object max(Collection c) + { + return max(c, null); + } + + /** + * Find the maximum element in a Collection, according to a specified + * Comparator. This implementation iterates over the Collection, so it + * works in linear time. + * + * @param c the Collection to find the maximum element of + * @param order the Comparator to order the elements by, or null for natural + * ordering + * @return the maximum element of c + * @throws NoSuchElementException if c is empty + * @throws ClassCastException if elements in c are not mutually comparable + * @throws NullPointerException if null is compared by natural ordering + * (only possible when order is null) + */ + public static Object max(Collection c, Comparator order) + { + Iterator itr = c.iterator(); + Object max = itr.next(); // throws NoSuchElementException + int csize = c.size(); + for (int i = 1; i < csize; i++) + { + Object o = itr.next(); + if (compare(max, o, order) < 0) + max = o; + } + return max; + } + + /** + * Find the minimum element in a Collection, according to the natural + * ordering of the elements. This implementation iterates over the + * Collection, so it works in linear time. + * + * @param c the Collection to find the minimum element of + * @return the minimum element of c + * @throws NoSuchElementException if c is empty + * @throws ClassCastException if elements in c are not mutually comparable + * @throws NullPointerException if null.compareTo is called + */ + public static Object min(Collection c) + { + return min(c, null); + } + + /** + * Find the minimum element in a Collection, according to a specified + * Comparator. This implementation iterates over the Collection, so it + * works in linear time. + * + * @param c the Collection to find the minimum element of + * @param order the Comparator to order the elements by, or null for natural + * ordering + * @return the minimum element of c + * @throws NoSuchElementException if c is empty + * @throws ClassCastException if elements in c are not mutually comparable + * @throws NullPointerException if null is compared by natural ordering + * (only possible when order is null) + */ + public static Object min(Collection c, Comparator order) + { + Iterator itr = c.iterator(); + Object min = itr.next(); // throws NoSuchElementExcception + int csize = c.size(); + for (int i = 1; i < csize; i++) + { + Object o = itr.next(); + if (compare(min, o, order) > 0) + min = o; + } + return min; + } + + /** + * Creates an immutable list consisting of the same object repeated n times. + * The returned object is tiny, consisting of only a single reference to the + * object and a count of the number of elements. It is Serializable, and + * implements RandomAccess. You can use it in tandem with List.addAll for + * fast list construction. + * + * @param n the number of times to repeat the object + * @param o the object to repeat + * @return a List consisting of n copies of o + * @throws IllegalArgumentException if n < 0 + * @see List#addAll(Collection) + * @see Serializable + * @see RandomAccess + */ + public static List nCopies(final int n, final Object o) + { + return new CopiesList(n, o); + } + + /** + * The implementation of {@link #nCopies(int, Object)}. This class name + * is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class CopiesList extends AbstractList + implements Serializable, RandomAccess + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 2739099268398711800L; + + /** + * The count of elements in this list. + * @serial the list size + */ + private final int n; + + /** + * The repeated list element. + * @serial the list contents + */ + private final Object element; + + /** + * Constructs the list. + * + * @param n the count + * @param o the object + * @throws IllegalArgumentException if n < 0 + */ + CopiesList(int n, Object o) + { + if (n < 0) + throw new IllegalArgumentException(); + this.n = n; + element = o; + } + + /** + * The size is fixed. + * @return The size of the list. + */ + public int size() + { + return n; + } + + /** + * The same element is returned. + * @param index The index of the element to be returned (irrelevant + * as the list contains only copies of <code>element</code>). + * @return The element used by this list. + */ + public Object get(int index) + { + if (index < 0 || index >= n) + throw new IndexOutOfBoundsException(); + return element; + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractList. + /** + * This list only contains one element. + * @param o The object to search for. + * @return <code>true</code> if o is the element used by this list. + */ + public boolean contains(Object o) + { + return n > 0 && equals(o, element); + } + + /** + * The index is either 0 or -1. + * @param o The object to find the index of. + * @return 0 if <code>o == element</code>, -1 if not. + */ + public int indexOf(Object o) + { + return (n > 0 && equals(o, element)) ? 0 : -1; + } + + /** + * The index is either n-1 or -1. + * @param o The object to find the last index of. + * @return The last index in the list if <code>o == element</code>, + * -1 if not. + */ + public int lastIndexOf(Object o) + { + return equals(o, element) ? n - 1 : -1; + } + + /** + * A subList is just another CopiesList. + * @param from The starting bound of the sublist. + * @param to The ending bound of the sublist. + * @return A list of copies containing <code>from - to</code> + * elements, all of which are equal to the element + * used by this list. + */ + public List subList(int from, int to) + { + if (from < 0 || to > n) + throw new IndexOutOfBoundsException(); + return new CopiesList(to - from, element); + } + + /** + * The array is easy. + * @return An array of size n filled with copies of + * the element used by this list. + */ + public Object[] toArray() + { + Object[] a = new Object[n]; + Arrays.fill(a, element); + return a; + } + + /** + * The string is easy to generate. + * @return A string representation of the list. + */ + public String toString() + { + StringBuffer r = new StringBuffer("{"); + for (int i = n - 1; --i > 0; ) + r.append(element).append(", "); + r.append(element).append("}"); + return r.toString(); + } + } // class CopiesList + + /** + * Replace all instances of one object with another in the specified list. + * The list does not change size. An element e is replaced if + * <code>oldval == null ? e == null : oldval.equals(e)</code>. + * + * @param list the list to iterate over + * @param oldval the element to replace + * @param newval the new value for the element + * @return <code>true</code> if a replacement occurred. + * @throws UnsupportedOperationException if the list iterator does not allow + * for the set operation + * @throws ClassCastException if newval is of a type which cannot be added + * to the list + * @throws IllegalArgumentException if some other aspect of newval stops + * it being added to the list + * @since 1.4 + */ + public static boolean replaceAll(List list, Object oldval, Object newval) + { + ListIterator itr = list.listIterator(); + boolean replace_occured = false; + for (int i = list.size(); --i >= 0; ) + if (AbstractCollection.equals(oldval, itr.next())) + { + itr.set(newval); + replace_occured = true; + } + return replace_occured; + } + + /** + * Reverse a given list. This method works in linear time. + * + * @param l the list to reverse + * @throws UnsupportedOperationException if l.listIterator() does not + * support the set operation + */ + public static void reverse(List l) + { + ListIterator i1 = l.listIterator(); + int pos1 = 1; + int pos2 = l.size(); + ListIterator i2 = l.listIterator(pos2); + while (pos1 < pos2) + { + Object o = i1.next(); + i1.set(i2.previous()); + i2.set(o); + ++pos1; + --pos2; + } + } + + /** + * Get a comparator that implements the reverse of natural ordering. In + * other words, this sorts Comparable objects opposite of how their + * compareTo method would sort. This makes it easy to sort into reverse + * order, by simply passing Collections.reverseOrder() to the sort method. + * The return value of this method is Serializable. + * + * @return a comparator that imposes reverse natural ordering + * @see Comparable + * @see Serializable + */ + public static Comparator reverseOrder() + { + return rcInstance; + } + + /** + * The object for {@link #reverseOrder()}. + */ + private static final ReverseComparator rcInstance = new ReverseComparator(); + + /** + * The implementation of {@link #reverseOrder()}. This class name + * is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class ReverseComparator + implements Comparator, Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 7207038068494060240L; + + /** + * A private constructor adds overhead. + */ + ReverseComparator() + { + } + + /** + * Compare two objects in reverse natural order. + * + * @param a the first object + * @param b the second object + * @return <, ==, or > 0 according to b.compareTo(a) + */ + public int compare(Object a, Object b) + { + return ((Comparable) b).compareTo(a); + } + } + + /** + * Rotate the elements in a list by a specified distance. After calling this + * method, the element now at index <code>i</code> was formerly at index + * <code>(i - distance) mod list.size()</code>. The list size is unchanged. + * <p> + * + * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After + * either <code>Collections.rotate(l, 4)</code> or + * <code>Collections.rotate(l, -1)</code>, the new contents are + * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate + * just a portion of the list. For example, to move element <code>a</code> + * forward two positions in the original example, use + * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will + * result in <code>[t, n, k, a, s]</code>. + * <p> + * + * If the list is small or implements {@link RandomAccess}, the + * implementation exchanges the first element to its destination, then the + * displaced element, and so on until a circuit has been completed. The + * process is repeated if needed on the second element, and so forth, until + * all elements have been swapped. For large non-random lists, the + * implementation breaks the list into two sublists at index + * <code>-distance mod size</code>, calls {@link #reverse(List)} on the + * pieces, then reverses the overall list. + * + * @param list the list to rotate + * @param distance the distance to rotate by; unrestricted in value + * @throws UnsupportedOperationException if the list does not support set + * @since 1.4 + */ + public static void rotate(List list, int distance) + { + int size = list.size(); + if (size == 0) + return; + distance %= size; + if (distance == 0) + return; + if (distance < 0) + distance += size; + + if (isSequential(list)) + { + reverse(list); + reverse(list.subList(0, distance)); + reverse(list.subList(distance, size)); + } + else + { + // Determine the least common multiple of distance and size, as there + // are (distance / LCM) loops to cycle through. + int a = size; + int lcm = distance; + int b = a % lcm; + while (b != 0) + { + a = lcm; + lcm = b; + b = a % lcm; + } + + // Now, make the swaps. We must take the remainder every time through + // the inner loop so that we don't overflow i to negative values. + while (--lcm >= 0) + { + Object o = list.get(lcm); + for (int i = lcm + distance; i != lcm; i = (i + distance) % size) + o = list.set(i, o); + list.set(lcm, o); + } + } + } + + /** + * Shuffle a list according to a default source of randomness. The algorithm + * used iterates backwards over the list, swapping each element with an + * element randomly selected from the elements in positions less than or + * equal to it (using r.nextInt(int)). + * <p> + * + * This algorithm would result in a perfectly fair shuffle (that is, each + * element would have an equal chance of ending up in any position) if r were + * a perfect source of randomness. In practice the results are merely very + * close to perfect. + * <p> + * + * This method operates in linear time. To do this on large lists which do + * not implement {@link RandomAccess}, a temporary array is used to acheive + * this speed, since it would be quadratic access otherwise. + * + * @param l the list to shuffle + * @throws UnsupportedOperationException if l.listIterator() does not + * support the set operation + */ + public static void shuffle(List l) + { + if (defaultRandom == null) + { + synchronized (Collections.class) + { + if (defaultRandom == null) + defaultRandom = new Random(); + } + } + shuffle(l, defaultRandom); + } + + /** + * Cache a single Random object for use by shuffle(List). This improves + * performance as well as ensuring that sequential calls to shuffle() will + * not result in the same shuffle order occurring: the resolution of + * System.currentTimeMillis() is not sufficient to guarantee a unique seed. + */ + private static Random defaultRandom = null; + + /** + * Shuffle a list according to a given source of randomness. The algorithm + * used iterates backwards over the list, swapping each element with an + * element randomly selected from the elements in positions less than or + * equal to it (using r.nextInt(int)). + * <p> + * + * This algorithm would result in a perfectly fair shuffle (that is, each + * element would have an equal chance of ending up in any position) if r were + * a perfect source of randomness. In practise (eg if r = new Random()) the + * results are merely very close to perfect. + * <p> + * + * This method operates in linear time. To do this on large lists which do + * not implement {@link RandomAccess}, a temporary array is used to acheive + * this speed, since it would be quadratic access otherwise. + * + * @param l the list to shuffle + * @param r the source of randomness to use for the shuffle + * @throws UnsupportedOperationException if l.listIterator() does not + * support the set operation + */ + public static void shuffle(List l, Random r) + { + int lsize = l.size(); + ListIterator i = l.listIterator(lsize); + boolean sequential = isSequential(l); + Object[] a = null; // stores a copy of the list for the sequential case + + if (sequential) + a = l.toArray(); + + for (int pos = lsize - 1; pos > 0; --pos) + { + // Obtain a random position to swap with. pos + 1 is used so that the + // range of the random number includes the current position. + int swap = r.nextInt(pos + 1); + + // Swap the desired element. + Object o; + if (sequential) + { + o = a[swap]; + a[swap] = i.previous(); + } + else + o = l.set(swap, i.previous()); + + i.set(o); + } + } + + + /** + * Obtain an immutable Set consisting of a single element. The return value + * of this method is Serializable. + * + * @param o the single element + * @return an immutable Set containing only o + * @see Serializable + */ + public static Set singleton(Object o) + { + return new SingletonSet(o); + } + + /** + * The implementation of {@link #singleton(Object)}. This class name + * is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SingletonSet extends AbstractSet + implements Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 3193687207550431679L; + + + /** + * The single element; package visible for use in nested class. + * @serial the singleton + */ + final Object element; + + /** + * Construct a singleton. + * @param o the element + */ + SingletonSet(Object o) + { + element = o; + } + + /** + * The size: always 1! + * @return 1. + */ + public int size() + { + return 1; + } + + /** + * Returns an iterator over the lone element. + */ + public Iterator iterator() + { + return new Iterator() + { + /** + * Flag to indicate whether or not the element has + * been retrieved. + */ + private boolean hasNext = true; + + /** + * Returns <code>true</code> if elements still remain to be + * iterated through. + * + * @return <code>true</code> if the element has not yet been returned. + */ + public boolean hasNext() + { + return hasNext; + } + + /** + * Returns the element. + * + * @return The element used by this singleton. + * @throws NoSuchElementException if the object + * has already been retrieved. + */ + public Object next() + { + if (hasNext) + { + hasNext = false; + return element; + } + else + throw new NoSuchElementException(); + } + + /** + * Removes the element from the singleton. + * As this set is immutable, this will always + * throw an exception. + * + * @throws UnsupportedOperationException as the + * singleton set doesn't support + * <code>remove()</code>. + */ + public void remove() + { + throw new UnsupportedOperationException(); + } + }; + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractSet. + /** + * The set only contains one element. + * + * @param o The object to search for. + * @return <code>true</code> if o == the element of the singleton. + */ + public boolean contains(Object o) + { + return equals(o, element); + } + + /** + * This is true if the other collection only contains the element. + * + * @param c A collection to compare against this singleton. + * @return <code>true</code> if c only contains either no elements or + * elements equal to the element in this singleton. + */ + public boolean containsAll(Collection c) + { + Iterator i = c.iterator(); + int pos = c.size(); + while (--pos >= 0) + if (! equals(i.next(), element)) + return false; + return true; + } + + /** + * The hash is just that of the element. + * + * @return The hashcode of the element. + */ + public int hashCode() + { + return hashCode(element); + } + + /** + * Returning an array is simple. + * + * @return An array containing the element. + */ + public Object[] toArray() + { + return new Object[] {element}; + } + + /** + * Obvious string. + * + * @return The string surrounded by enclosing + * square brackets. + */ + public String toString() + { + return "[" + element + "]"; + } + } // class SingletonSet + + /** + * Obtain an immutable List consisting of a single element. The return value + * of this method is Serializable, and implements RandomAccess. + * + * @param o the single element + * @return an immutable List containing only o + * @see Serializable + * @see RandomAccess + * @since 1.3 + */ + public static List singletonList(Object o) + { + return new SingletonList(o); + } + + /** + * The implementation of {@link #singletonList(Object)}. This class name + * is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SingletonList extends AbstractList + implements Serializable, RandomAccess + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 3093736618740652951L; + + /** + * The single element. + * @serial the singleton + */ + private final Object element; + + /** + * Construct a singleton. + * @param o the element + */ + SingletonList(Object o) + { + element = o; + } + + /** + * The size: always 1! + * @return 1. + */ + public int size() + { + return 1; + } + + /** + * Only index 0 is valid. + * @param index The index of the element + * to retrieve. + * @return The singleton's element if the + * index is 0. + * @throws IndexOutOfBoundsException if + * index is not 0. + */ + public Object get(int index) + { + if (index == 0) + return element; + throw new IndexOutOfBoundsException(); + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractList. + /** + * The set only contains one element. + * + * @param o The object to search for. + * @return <code>true</code> if o == the singleton element. + */ + public boolean contains(Object o) + { + return equals(o, element); + } + + /** + * This is true if the other collection only contains the element. + * + * @param c A collection to compare against this singleton. + * @return <code>true</code> if c only contains either no elements or + * elements equal to the element in this singleton. + */ + public boolean containsAll(Collection c) + { + Iterator i = c.iterator(); + int pos = c.size(); + while (--pos >= 0) + if (! equals(i.next(), element)) + return false; + return true; + } + + /** + * Speed up the hashcode computation. + * + * @return The hashcode of the list, based + * on the hashcode of the singleton element. + */ + public int hashCode() + { + return 31 + hashCode(element); + } + + /** + * Either the list has it or not. + * + * @param o The object to find the first index of. + * @return 0 if o is the singleton element, -1 if not. + */ + public int indexOf(Object o) + { + return equals(o, element) ? 0 : -1; + } + + /** + * Either the list has it or not. + * + * @param o The object to find the last index of. + * @return 0 if o is the singleton element, -1 if not. + */ + public int lastIndexOf(Object o) + { + return equals(o, element) ? 0 : -1; + } + + /** + * Sublists are limited in scope. + * + * @param from The starting bound for the sublist. + * @param to The ending bound for the sublist. + * @return Either an empty list if both bounds are + * 0 or 1, or this list if the bounds are 0 and 1. + * @throws IllegalArgumentException if <code>from > to</code> + * @throws IndexOutOfBoundsException if either bound is greater + * than 1. + */ + public List subList(int from, int to) + { + if (from == to && (to == 0 || to == 1)) + return EMPTY_LIST; + if (from == 0 && to == 1) + return this; + if (from > to) + throw new IllegalArgumentException(); + throw new IndexOutOfBoundsException(); + } + + /** + * Returning an array is simple. + * + * @return An array containing the element. + */ + public Object[] toArray() + { + return new Object[] {element}; + } + + /** + * Obvious string. + * + * @return The string surrounded by enclosing + * square brackets. + */ + public String toString() + { + return "[" + element + "]"; + } + } // class SingletonList + + /** + * Obtain an immutable Map consisting of a single key-value pair. + * The return value of this method is Serializable. + * + * @param key the single key + * @param value the single value + * @return an immutable Map containing only the single key-value pair + * @see Serializable + * @since 1.3 + */ + public static Map singletonMap(Object key, Object value) + { + return new SingletonMap(key, value); + } + + /** + * The implementation of {@link #singletonMap(Object)}. This class name + * is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SingletonMap extends AbstractMap + implements Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -6979724477215052911L; + + /** + * The single key. + * @serial the singleton key + */ + private final Object k; + + /** + * The corresponding value. + * @serial the singleton value + */ + private final Object v; + + /** + * Cache the entry set. + */ + private transient Set entries; + + /** + * Construct a singleton. + * @param key the key + * @param value the value + */ + SingletonMap(Object key, Object value) + { + k = key; + v = value; + } + + /** + * There is a single immutable entry. + * + * @return A singleton containing the map entry. + */ + public Set entrySet() + { + if (entries == null) + entries = singleton(new AbstractMap.BasicMapEntry(k, v) + { + /** + * Sets the value of the map entry to the supplied value. + * An exception is always thrown, as the map is immutable. + * + * @param o The new value. + * @return The old value. + * @throws UnsupportedOperationException as setting the value + * is not supported. + */ + public Object setValue(Object o) + { + throw new UnsupportedOperationException(); + } + }); + return entries; + } + + // The remaining methods are optional, but provide a performance + // advantage by not allocating unnecessary iterators in AbstractMap. + /** + * Single entry. + * + * @param key The key to look for. + * @return <code>true</code> if the key is the same as the one used by + * this map. + */ + public boolean containsKey(Object key) + { + return equals(key, k); + } + + /** + * Single entry. + * + * @param value The value to look for. + * @return <code>true</code> if the value is the same as the one used by + * this map. + */ + public boolean containsValue(Object value) + { + return equals(value, v); + } + + /** + * Single entry. + * + * @param key The key of the value to be retrieved. + * @return The singleton value if the key is the same as the + * singleton key, null otherwise. + */ + public Object get(Object key) + { + return equals(key, k) ? v : null; + } + + /** + * Calculate the hashcode directly. + * + * @return The hashcode computed from the singleton key + * and the singleton value. + */ + public int hashCode() + { + return hashCode(k) ^ hashCode(v); + } + + /** + * Return the keyset. + * + * @return A singleton containing the key. + */ + public Set keySet() + { + if (keys == null) + keys = singleton(k); + return keys; + } + + /** + * The size: always 1! + * + * @return 1. + */ + public int size() + { + return 1; + } + + /** + * Return the values. Technically, a singleton, while more specific than + * a general Collection, will work. Besides, that's what the JDK uses! + * + * @return A singleton containing the value. + */ + public Collection values() + { + if (values == null) + values = singleton(v); + return values; + } + + /** + * Obvious string. + * + * @return A string containing the string representations of the key + * and its associated value. + */ + public String toString() + { + return "{" + k + "=" + v + "}"; + } + } // class SingletonMap + + /** + * Sort a list according to the natural ordering of its elements. The list + * must be modifiable, but can be of fixed size. The sort algorithm is + * precisely that used by Arrays.sort(Object[]), which offers guaranteed + * nlog(n) performance. This implementation dumps the list into an array, + * sorts the array, and then iterates over the list setting each element from + * the array. + * + * @param l the List to sort + * @throws ClassCastException if some items are not mutually comparable + * @throws UnsupportedOperationException if the List is not modifiable + * @throws NullPointerException if some element is null + * @see Arrays#sort(Object[]) + */ + public static void sort(List l) + { + sort(l, null); + } + + /** + * Sort a list according to a specified Comparator. The list must be + * modifiable, but can be of fixed size. The sort algorithm is precisely that + * used by Arrays.sort(Object[], Comparator), which offers guaranteed + * nlog(n) performance. This implementation dumps the list into an array, + * sorts the array, and then iterates over the list setting each element from + * the array. + * + * @param l the List to sort + * @param c the Comparator specifying the ordering for the elements, or + * null for natural ordering + * @throws ClassCastException if c will not compare some pair of items + * @throws UnsupportedOperationException if the List is not modifiable + * @throws NullPointerException if null is compared by natural ordering + * (only possible when c is null) + * @see Arrays#sort(Object[], Comparator) + */ + public static void sort(List l, Comparator c) + { + Object[] a = l.toArray(); + Arrays.sort(a, c); + ListIterator i = l.listIterator(); + for (int pos = 0, alen = a.length; pos < alen; pos++) + { + i.next(); + i.set(a[pos]); + } + } + + /** + * Swaps the elements at the specified positions within the list. Equal + * positions have no effect. + * + * @param l the list to work on + * @param i the first index to swap + * @param j the second index + * @throws UnsupportedOperationException if list.set is not supported + * @throws IndexOutOfBoundsException if either i or j is < 0 or >= + * list.size() + * @since 1.4 + */ + public static void swap(List l, int i, int j) + { + l.set(i, l.set(j, l.get(i))); + } + + + /** + * Returns a synchronized (thread-safe) collection wrapper backed by the + * given collection. Notice that element access through the iterators + * is thread-safe, but if the collection can be structurally modified + * (adding or removing elements) then you should synchronize around the + * iteration to avoid non-deterministic behavior:<br> + * <pre> + * Collection c = Collections.synchronizedCollection(new Collection(...)); + * ... + * synchronized (c) + * { + * Iterator i = c.iterator(); + * while (i.hasNext()) + * foo(i.next()); + * } + * </pre><p> + * + * Since the collection might be a List or a Set, and those have incompatible + * equals and hashCode requirements, this relies on Object's implementation + * rather than passing those calls on to the wrapped collection. The returned + * Collection implements Serializable, but can only be serialized if + * the collection it wraps is likewise Serializable. + * + * @param c the collection to wrap + * @return a synchronized view of the collection + * @see Serializable + */ + public static Collection synchronizedCollection(Collection c) + { + return new SynchronizedCollection(c); + } + + /** + * The implementation of {@link #synchronizedCollection(Collection)}. This + * class name is required for compatibility with Sun's JDK serializability. + * Package visible, so that collections such as the one for + * Hashtable.values() can specify which object to synchronize on. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + static class SynchronizedCollection + implements Collection, Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 3053995032091335093L; + + /** + * The wrapped collection. Package visible for use by subclasses. + * @serial the real collection + */ + final Collection c; + + /** + * The object to synchronize on. When an instance is created via public + * methods, it will be this; but other uses like SynchronizedMap.values() + * must specify another mutex. Package visible for use by subclasses. + * @serial the lock + */ + final Object mutex; + + /** + * Wrap a given collection. + * @param c the collection to wrap + * @throws NullPointerException if c is null + */ + SynchronizedCollection(Collection c) + { + this.c = c; + mutex = this; + if (c == null) + throw new NullPointerException(); + } + + /** + * Called only by trusted code to specify the mutex as well as the + * collection. + * @param sync the mutex + * @param c the collection + */ + SynchronizedCollection(Object sync, Collection c) + { + this.c = c; + mutex = sync; + } + + /** + * Adds the object to the underlying collection, first + * obtaining a lock on the mutex. + * + * @param o The object to add. + * @return <code>true</code> if the collection was modified as a result + * of this action. + * @throws UnsupportedOperationException if this collection does not + * support the add operation. + * @throws ClassCastException if o cannot be added to this collection due + * to its type. + * @throws NullPointerException if o is null and this collection doesn't + * support the addition of null values. + * @throws IllegalArgumentException if o cannot be added to this + * collection for some other reason. + */ + public boolean add(Object o) + { + synchronized (mutex) + { + return c.add(o); + } + } + + /** + * Adds the objects in col to the underlying collection, first + * obtaining a lock on the mutex. + * + * @param col The collection to take the new objects from. + * @return <code>true</code> if the collection was modified as a result + * of this action. + * @throws UnsupportedOperationException if this collection does not + * support the addAll operation. + * @throws ClassCastException if some element of col cannot be added to this + * collection due to its type. + * @throws NullPointerException if some element of col is null and this + * collection does not support the addition of null values. + * @throws NullPointerException if col itself is null. + * @throws IllegalArgumentException if some element of col cannot be added + * to this collection for some other reason. + */ + public boolean addAll(Collection col) + { + synchronized (mutex) + { + return c.addAll(col); + } + } + + /** + * Removes all objects from the underlying collection, + * first obtaining a lock on the mutex. + * + * @throws UnsupportedOperationException if this collection does not + * support the clear operation. + */ + public void clear() + { + synchronized (mutex) + { + c.clear(); + } + } + + /** + * Checks for the existence of o within the underlying + * collection, first obtaining a lock on the mutex. + * + * @param o the element to look for. + * @return <code>true</code> if this collection contains at least one + * element e such that <code>o == null ? e == null : o.equals(e)</code>. + * @throws ClassCastException if the type of o is not a valid type for this + * collection. + * @throws NullPointerException if o is null and this collection doesn't + * support null values. + */ + public boolean contains(Object o) + { + synchronized (mutex) + { + return c.contains(o); + } + } + + /** + * Checks for the existence of each object in cl + * within the underlying collection, first obtaining + * a lock on the mutex. + * + * @param c1 the collection to test for. + * @return <code>true</code> if for every element o in c, contains(o) + * would return <code>true</code>. + * @throws ClassCastException if the type of any element in cl is not a valid + * type for this collection. + * @throws NullPointerException if some element of cl is null and this + * collection does not support null values. + * @throws NullPointerException if cl itself is null. + */ + public boolean containsAll(Collection c1) + { + synchronized (mutex) + { + return c.containsAll(c1); + } + } + + /** + * Returns <code>true</code> if there are no objects in the underlying + * collection. A lock on the mutex is obtained before the + * check is performed. + * + * @return <code>true</code> if this collection contains no elements. + */ + public boolean isEmpty() + { + synchronized (mutex) + { + return c.isEmpty(); + } + } + + /** + * Returns a synchronized iterator wrapper around the underlying + * collection's iterator. A lock on the mutex is obtained before + * retrieving the collection's iterator. + * + * @return An iterator over the elements in the underlying collection, + * which returns each element in any order. + */ + public Iterator iterator() + { + synchronized (mutex) + { + return new SynchronizedIterator(mutex, c.iterator()); + } + } + + /** + * Removes the specified object from the underlying collection, + * first obtaining a lock on the mutex. + * + * @param o The object to remove. + * @return <code>true</code> if the collection changed as a result of this call, that is, + * if the collection contained at least one occurrence of o. + * @throws UnsupportedOperationException if this collection does not + * support the remove operation. + * @throws ClassCastException if the type of o is not a valid type + * for this collection. + * @throws NullPointerException if o is null and the collection doesn't + * support null values. + */ + public boolean remove(Object o) + { + synchronized (mutex) + { + return c.remove(o); + } + } + + /** + * Removes all elements, e, of the underlying + * collection for which <code>col.contains(e)</code> + * returns <code>true</code>. A lock on the mutex is obtained + * before the operation proceeds. + * + * @param col The collection of objects to be removed. + * @return <code>true</code> if this collection was modified as a result of this call. + * @throws UnsupportedOperationException if this collection does not + * support the removeAll operation. + * @throws ClassCastException if the type of any element in c is not a valid + * type for this collection. + * @throws NullPointerException if some element of c is null and this + * collection does not support removing null values. + * @throws NullPointerException if c itself is null. + */ + public boolean removeAll(Collection col) + { + synchronized (mutex) + { + return c.removeAll(col); + } + } + + /** + * Retains all elements, e, of the underlying + * collection for which <code>col.contains(e)</code> + * returns <code>true</code>. That is, every element that doesn't + * exist in col is removed. A lock on the mutex is obtained + * before the operation proceeds. + * + * @param col The collection of objects to be removed. + * @return <code>true</code> if this collection was modified as a result of this call. + * @throws UnsupportedOperationException if this collection does not + * support the removeAll operation. + * @throws ClassCastException if the type of any element in c is not a valid + * type for this collection. + * @throws NullPointerException if some element of c is null and this + * collection does not support removing null values. + * @throws NullPointerException if c itself is null. + */ + public boolean retainAll(Collection col) + { + synchronized (mutex) + { + return c.retainAll(col); + } + } + + /** + * Retrieves the size of the underlying collection. + * A lock on the mutex is obtained before the collection + * is accessed. + * + * @return The size of the collection. + */ + public int size() + { + synchronized (mutex) + { + return c.size(); + } + } + + /** + * Returns an array containing each object within the underlying + * collection. A lock is obtained on the mutex before the collection + * is accessed. + * + * @return An array of objects, matching the collection in size. The + * elements occur in any order. + */ + public Object[] toArray() + { + synchronized (mutex) + { + return c.toArray(); + } + } + + /** + * Copies the elements in the underlying collection to the supplied + * array. If <code>a.length < size()</code>, a new array of the + * same run-time type is created, with a size equal to that of + * the collection. If <code>a.length > size()</code>, then the + * elements from 0 to <code>size() - 1</code> contain the elements + * from this collection. The following element is set to null + * to indicate the end of the collection objects. However, this + * only makes a difference if null is not a permitted value within + * the collection. + * Before the copying takes place, a lock is obtained on the mutex. + * + * @param a An array to copy elements to. + * @return An array containing the elements of the underlying collection. + * @throws ArrayStoreException if the type of any element of the + * collection is not a subtype of the element type of a. + */ + public Object[] toArray(Object[] a) + { + synchronized (mutex) + { + return c.toArray(a); + } + } + + /** + * Returns a string representation of the underlying collection. + * A lock is obtained on the mutex before the string is created. + * + * @return A string representation of the collection. + */ + public String toString() + { + synchronized (mutex) + { + return c.toString(); + } + } + } // class SynchronizedCollection + + /** + * The implementation of the various iterator methods in the + * synchronized classes. These iterators must "sync" on the same object + * as the collection they iterate over. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class SynchronizedIterator implements Iterator + { + /** + * The object to synchronize on. Package visible for use by subclass. + */ + final Object mutex; + + /** + * The wrapped iterator. + */ + private final Iterator i; + + /** + * Only trusted code creates a wrapper, with the specified sync. + * @param sync the mutex + * @param i the wrapped iterator + */ + SynchronizedIterator(Object sync, Iterator i) + { + this.i = i; + mutex = sync; + } + + /** + * Retrieves the next object in the underlying collection. + * A lock is obtained on the mutex before the collection is accessed. + * + * @return The next object in the collection. + * @throws NoSuchElementException if there are no more elements + */ + public Object next() + { + synchronized (mutex) + { + return i.next(); + } + } + + /** + * Returns <code>true</code> if objects can still be retrieved from the iterator + * using <code>next()</code>. A lock is obtained on the mutex before + * the collection is accessed. + * + * @return <code>true</code> if at least one element is still to be returned by + * <code>next()</code>. + */ + public boolean hasNext() + { + synchronized (mutex) + { + return i.hasNext(); + } + } + + /** + * Removes the object that was last returned by <code>next()</code> + * from the underlying collection. Only one call to this method is + * allowed per call to the <code>next()</code> method, and it does + * not affect the value that will be returned by <code>next()</code>. + * Thus, if element n was retrieved from the collection by + * <code>next()</code>, it is this element that gets removed. + * Regardless of whether this takes place or not, element n+1 is + * still returned on the subsequent <code>next()</code> call. + * + * @throws IllegalStateException if next has not yet been called or remove + * has already been called since the last call to next. + * @throws UnsupportedOperationException if this Iterator does not support + * the remove operation. + */ + public void remove() + { + synchronized (mutex) + { + i.remove(); + } + } + } // class SynchronizedIterator + + /** + * Returns a synchronized (thread-safe) list wrapper backed by the + * given list. Notice that element access through the iterators + * is thread-safe, but if the list can be structurally modified + * (adding or removing elements) then you should synchronize around the + * iteration to avoid non-deterministic behavior:<br> + * <pre> + * List l = Collections.synchronizedList(new List(...)); + * ... + * synchronized (l) + * { + * Iterator i = l.iterator(); + * while (i.hasNext()) + * foo(i.next()); + * } + * </pre><p> + * + * The returned List implements Serializable, but can only be serialized if + * the list it wraps is likewise Serializable. In addition, if the wrapped + * list implements RandomAccess, this does too. + * + * @param l the list to wrap + * @return a synchronized view of the list + * @see Serializable + * @see RandomAccess + */ + public static List synchronizedList(List l) + { + if (l instanceof RandomAccess) + return new SynchronizedRandomAccessList(l); + return new SynchronizedList(l); + } + + /** + * The implementation of {@link #synchronizedList(List)} for sequential + * lists. This class name is required for compatibility with Sun's JDK + * serializability. Package visible, so that lists such as Vector.subList() + * can specify which object to synchronize on. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + static class SynchronizedList extends SynchronizedCollection + implements List + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -7754090372962971524L; + + /** + * The wrapped list; stored both here and in the superclass to avoid + * excessive casting. Package visible for use by subclass. + * @serial the wrapped list + */ + final List list; + + /** + * Wrap a given list. + * @param l the list to wrap + * @throws NullPointerException if l is null + */ + SynchronizedList(List l) + { + super(l); + list = l; + } + + /** + * Called only by trusted code to specify the mutex as well as the list. + * @param sync the mutex + * @param l the list + */ + SynchronizedList(Object sync, List l) + { + super(sync, l); + list = l; + } + + /** + * Insert an element into the underlying list at a given position (optional + * operation). This shifts all existing elements from that position to the + * end one index to the right. This version of add has no return, since it is + * assumed to always succeed if there is no exception. Before the + * addition takes place, a lock is obtained on the mutex. + * + * @param index the location to insert the item + * @param o the object to insert + * @throws UnsupportedOperationException if this list does not support the + * add operation + * @throws IndexOutOfBoundsException if index < 0 || index > size() + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + * @throws NullPointerException if o is null and this list doesn't support + * the addition of null values. + */ + public void add(int index, Object o) + { + synchronized (mutex) + { + list.add(index, o); + } + } + + /** + * Add an element to the end of the underlying list (optional operation). + * If the list imposes restraints on what can be inserted, such as no null + * elements, this should be documented. A lock is obtained on the mutex before + * any of the elements are added. + * + * @param o the object to add + * @return <code>true</code>, as defined by Collection for a modified list + * @throws UnsupportedOperationException if this list does not support the + * add operation + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + * @throws NullPointerException if o is null and this list doesn't support + * the addition of null values. + */ + public boolean addAll(int index, Collection c) + { + synchronized (mutex) + { + return list.addAll(index, c); + } + } + + /** + * Tests whether the underlying list is equal to the supplied object. + * The object is deemed to be equal if it is also a <code>List</code> + * of equal size and with the same elements (i.e. each element, e1, + * in list, l1, and each element, e2, in l2, must return <code>true</code> for + * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the + * comparison is made, a lock is obtained on the mutex. + * + * @param o The object to test for equality with the underlying list. + * @return <code>true</code> if o is equal to the underlying list under the above + * definition. + */ + public boolean equals(Object o) + { + synchronized (mutex) + { + return list.equals(o); + } + } + + /** + * Retrieves the object at the specified index. A lock + * is obtained on the mutex before the list is accessed. + * + * @param index the index of the element to be returned + * @return the element at index index in this list + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + */ + public Object get(int index) + { + synchronized (mutex) + { + return list.get(index); + } + } + + /** + * Obtains a hashcode for the underlying list, first obtaining + * a lock on the mutex. The calculation of the hashcode is + * detailed in the documentation for the <code>List</code> + * interface. + * + * @return The hashcode of the underlying list. + * @see List#hashCode() + */ + public int hashCode() + { + synchronized (mutex) + { + return list.hashCode(); + } + } + + /** + * Obtain the first index at which a given object is to be found in the + * underlying list. A lock is obtained on the mutex before the list is + * accessed. + * + * @param o the object to search for + * @return the least integer n such that <code>o == null ? get(n) == null : + * o.equals(get(n))</code>, or -1 if there is no such index. + * @throws ClassCastException if the type of o is not a valid + * type for this list. + * @throws NullPointerException if o is null and this + * list does not support null values. + */ + + public int indexOf(Object o) + { + synchronized (mutex) + { + return list.indexOf(o); + } + } + + /** + * Obtain the last index at which a given object is to be found in this + * underlying list. A lock is obtained on the mutex before the list + * is accessed. + * + * @return the greatest integer n such that <code>o == null ? get(n) == null + * : o.equals(get(n))</code>, or -1 if there is no such index. + * @throws ClassCastException if the type of o is not a valid + * type for this list. + * @throws NullPointerException if o is null and this + * list does not support null values. + */ + public int lastIndexOf(Object o) + { + synchronized (mutex) + { + return list.lastIndexOf(o); + } + } + + /** + * Retrieves a synchronized wrapper around the underlying list's + * list iterator. A lock is obtained on the mutex before the + * list iterator is retrieved. + * + * @return A list iterator over the elements in the underlying list. + * The list iterator allows additional list-specific operations + * to be performed, in addition to those supplied by the + * standard iterator. + */ + public ListIterator listIterator() + { + synchronized (mutex) + { + return new SynchronizedListIterator(mutex, list.listIterator()); + } + } + + /** + * Retrieves a synchronized wrapper around the underlying list's + * list iterator. A lock is obtained on the mutex before the + * list iterator is retrieved. The iterator starts at the + * index supplied, leading to the element at that index being + * the first one returned by <code>next()</code>. Calling + * <code>previous()</code> from this initial position returns + * index - 1. + * + * @param index the position, between 0 and size() inclusive, to begin the + * iteration from + * @return A list iterator over the elements in the underlying list. + * The list iterator allows additional list-specific operations + * to be performed, in addition to those supplied by the + * standard iterator. + * @throws IndexOutOfBoundsException if index < 0 || index > size() + */ + public ListIterator listIterator(int index) + { + synchronized (mutex) + { + return new SynchronizedListIterator(mutex, list.listIterator(index)); + } + } + + /** + * Remove the element at a given position in the underlying list (optional + * operation). All remaining elements are shifted to the left to fill the gap. + * A lock on the mutex is obtained before the element is removed. + * + * @param index the position within the list of the object to remove + * @return the object that was removed + * @throws UnsupportedOperationException if this list does not support the + * remove operation + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + */ + public Object remove(int index) + { + synchronized (mutex) + { + return list.remove(index); + } + } + + /** + * Replace an element of the underlying list with another object (optional + * operation). A lock is obtained on the mutex before the element is + * replaced. + * + * @param index the position within this list of the element to be replaced + * @param o the object to replace it with + * @return the object that was replaced + * @throws UnsupportedOperationException if this list does not support the + * set operation. + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + * @throws ClassCastException if o cannot be added to this list due to its + * type + * @throws IllegalArgumentException if o cannot be added to this list for + * some other reason + * @throws NullPointerException if o is null and this + * list does not support null values. + */ + public Object set(int index, Object o) + { + synchronized (mutex) + { + return list.set(index, o); + } + } + + /** + * Obtain a List view of a subsection of the underlying list, from fromIndex + * (inclusive) to toIndex (exclusive). If the two indices are equal, the + * sublist is empty. The returned list should be modifiable if and only + * if this list is modifiable. Changes to the returned list should be + * reflected in this list. If this list is structurally modified in + * any way other than through the returned list, the result of any subsequent + * operations on the returned list is undefined. A lock is obtained + * on the mutex before the creation of the sublist. The returned list + * is also synchronized, using the same mutex. + * + * @param fromIndex the index that the returned list should start from + * (inclusive) + * @param toIndex the index that the returned list should go to (exclusive) + * @return a List backed by a subsection of this list + * @throws IndexOutOfBoundsException if fromIndex < 0 + * || toIndex > size() || fromIndex > toIndex + */ + public List subList(int fromIndex, int toIndex) + { + synchronized (mutex) + { + return new SynchronizedList(mutex, list.subList(fromIndex, toIndex)); + } + } + } // class SynchronizedList + + /** + * The implementation of {@link #synchronizedList(List)} for random-access + * lists. This class name is required for compatibility with Sun's JDK + * serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SynchronizedRandomAccessList + extends SynchronizedList implements RandomAccess + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 1530674583602358482L; + + /** + * Wrap a given list. + * @param l the list to wrap + * @throws NullPointerException if l is null + */ + SynchronizedRandomAccessList(List l) + { + super(l); + } + + /** + * Called only by trusted code to specify the mutex as well as the + * collection. + * @param sync the mutex + * @param l the list + */ + SynchronizedRandomAccessList(Object sync, List l) + { + super(sync, l); + } + + /** + * Obtain a List view of a subsection of the underlying list, from fromIndex + * (inclusive) to toIndex (exclusive). If the two indices are equal, the + * sublist is empty. The returned list should be modifiable if and only + * if this list is modifiable. Changes to the returned list should be + * reflected in this list. If this list is structurally modified in + * any way other than through the returned list, the result of any subsequent + * operations on the returned list is undefined. A lock is obtained + * on the mutex before the creation of the sublist. The returned list + * is also synchronized, using the same mutex. Random accessibility + * is also extended to the new list. + * + * @param fromIndex the index that the returned list should start from + * (inclusive) + * @param toIndex the index that the returned list should go to (exclusive) + * @return a List backed by a subsection of this list + * @throws IndexOutOfBoundsException if fromIndex < 0 + * || toIndex > size() || fromIndex > toIndex + */ + public List subList(int fromIndex, int toIndex) + { + synchronized (mutex) + { + return new SynchronizedRandomAccessList(mutex, + list.subList(fromIndex, + toIndex)); + } + } + } // class SynchronizedRandomAccessList + + /** + * The implementation of {@link SynchronizedList#listIterator()}. This + * iterator must "sync" on the same object as the list it iterates over. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SynchronizedListIterator + extends SynchronizedIterator implements ListIterator + { + /** + * The wrapped iterator, stored both here and in the superclass to + * avoid excessive casting. + */ + private final ListIterator li; + + /** + * Only trusted code creates a wrapper, with the specified sync. + * @param sync the mutex + * @param li the wrapped iterator + */ + SynchronizedListIterator(Object sync, ListIterator li) + { + super(sync, li); + this.li = li; + } + + /** + * Insert an element into the underlying list at the current position of + * the iterator (optional operation). The element is inserted in between + * the element that would be returned by <code>previous()</code> and the + * element that would be returned by <code>next()</code>. After the + * insertion, a subsequent call to next is unaffected, but + * a call to previous returns the item that was added. The values returned + * by nextIndex() and previousIndex() are incremented. A lock is obtained + * on the mutex before the addition takes place. + * + * @param o the object to insert into the list + * @throws ClassCastException if the object is of a type which cannot be added + * to this list. + * @throws IllegalArgumentException if some other aspect of the object stops + * it being added to this list. + * @throws UnsupportedOperationException if this ListIterator does not + * support the add operation. + */ + public void add(Object o) + { + synchronized (mutex) + { + li.add(o); + } + } + + /** + * Tests whether there are elements remaining in the underlying list + * in the reverse direction. In other words, <code>previous()</code> + * will not fail with a NoSuchElementException. A lock is obtained + * on the mutex before the check takes place. + * + * @return <code>true</code> if the list continues in the reverse direction + */ + public boolean hasPrevious() + { + synchronized (mutex) + { + return li.hasPrevious(); + } + } + + /** + * Find the index of the element that would be returned by a call to + * <code>next()</code>. If hasNext() returns <code>false</code>, this + * returns the list size. A lock is obtained on the mutex before the + * query takes place. + * + * @return the index of the element that would be returned by next() + */ + public int nextIndex() + { + synchronized (mutex) + { + return li.nextIndex(); + } + } + + /** + * Obtain the previous element from the underlying list. Repeated + * calls to previous may be used to iterate backwards over the entire list, + * or calls to next and previous may be used together to go forwards and + * backwards. Alternating calls to next and previous will return the same + * element. A lock is obtained on the mutex before the object is retrieved. + * + * @return the next element in the list in the reverse direction + * @throws NoSuchElementException if there are no more elements + */ + public Object previous() + { + synchronized (mutex) + { + return li.previous(); + } + } + + /** + * Find the index of the element that would be returned by a call to + * previous. If hasPrevious() returns <code>false</code>, this returns -1. + * A lock is obtained on the mutex before the query takes place. + * + * @return the index of the element that would be returned by previous() + */ + public int previousIndex() + { + synchronized (mutex) + { + return li.previousIndex(); + } + } + + /** + * Replace the element last returned by a call to <code>next()</code> or + * <code>previous()</code> with a given object (optional operation). This + * method may only be called if neither <code>add()</code> nor + * <code>remove()</code> have been called since the last call to + * <code>next()</code> or <code>previous</code>. A lock is obtained + * on the mutex before the list is modified. + * + * @param o the object to replace the element with + * @throws ClassCastException the object is of a type which cannot be added + * to this list + * @throws IllegalArgumentException some other aspect of the object stops + * it being added to this list + * @throws IllegalStateException if neither next or previous have been + * called, or if add or remove has been called since the last call + * to next or previous + * @throws UnsupportedOperationException if this ListIterator does not + * support the set operation + */ + public void set(Object o) + { + synchronized (mutex) + { + li.set(o); + } + } + } // class SynchronizedListIterator + + /** + * Returns a synchronized (thread-safe) map wrapper backed by the given + * map. Notice that element access through the collection views and their + * iterators are thread-safe, but if the map can be structurally modified + * (adding or removing elements) then you should synchronize around the + * iteration to avoid non-deterministic behavior:<br> + * <pre> + * Map m = Collections.synchronizedMap(new Map(...)); + * ... + * Set s = m.keySet(); // safe outside a synchronized block + * synchronized (m) // synch on m, not s + * { + * Iterator i = s.iterator(); + * while (i.hasNext()) + * foo(i.next()); + * } + * </pre><p> + * + * The returned Map implements Serializable, but can only be serialized if + * the map it wraps is likewise Serializable. + * + * @param m the map to wrap + * @return a synchronized view of the map + * @see Serializable + */ + public static Map synchronizedMap(Map m) + { + return new SynchronizedMap(m); + } + + /** + * The implementation of {@link #synchronizedMap(Map)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class SynchronizedMap implements Map, Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 1978198479659022715L; + + /** + * The wrapped map. + * @serial the real map + */ + private final Map m; + + /** + * The object to synchronize on. When an instance is created via public + * methods, it will be this; but other uses like + * SynchronizedSortedMap.subMap() must specify another mutex. Package + * visible for use by subclass. + * @serial the lock + */ + final Object mutex; + + /** + * Cache the entry set. + */ + private transient Set entries; + + /** + * Cache the key set. + */ + private transient Set keys; + + /** + * Cache the value collection. + */ + private transient Collection values; + + /** + * Wrap a given map. + * @param m the map to wrap + * @throws NullPointerException if m is null + */ + SynchronizedMap(Map m) + { + this.m = m; + mutex = this; + if (m == null) + throw new NullPointerException(); + } + + /** + * Called only by trusted code to specify the mutex as well as the map. + * @param sync the mutex + * @param m the map + */ + SynchronizedMap(Object sync, Map m) + { + this.m = m; + mutex = sync; + } + + /** + * Clears all the entries from the underlying map. A lock is obtained + * on the mutex before the map is cleared. + * + * @throws UnsupportedOperationException if clear is not supported + */ + public void clear() + { + synchronized (mutex) + { + m.clear(); + } + } + + /** + * Returns <code>true</code> if the underlying map contains a entry for the given key. + * A lock is obtained on the mutex before the map is queried. + * + * @param key the key to search for. + * @return <code>true</code> if the underlying map contains the key. + * @throws ClassCastException if the key is of an inappropriate type. + * @throws NullPointerException if key is <code>null</code> but the map + * does not permit null keys. + */ + public boolean containsKey(Object key) + { + synchronized (mutex) + { + return m.containsKey(key); + } + } + + /** + * Returns <code>true</code> if the underlying map contains at least one entry with the + * given value. In other words, returns <code>true</code> if a value v exists where + * <code>(value == null ? v == null : value.equals(v))</code>. This usually + * requires linear time. A lock is obtained on the mutex before the map + * is queried. + * + * @param value the value to search for + * @return <code>true</code> if the map contains the value + * @throws ClassCastException if the type of the value is not a valid type + * for this map. + * @throws NullPointerException if the value is null and the map doesn't + * support null values. + */ + public boolean containsValue(Object value) + { + synchronized (mutex) + { + return m.containsValue(value); + } + } + + // This is one of the ickiest cases of nesting I've ever seen. It just + // means "return a SynchronizedSet, except that the iterator() method + // returns an SynchronizedIterator whose next() method returns a + // synchronized wrapper around its normal return value". + public Set entrySet() + { + // Define this here to spare some nesting. + class SynchronizedMapEntry implements Map.Entry + { + final Map.Entry e; + SynchronizedMapEntry(Object o) + { + e = (Map.Entry) o; + } + + /** + * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code> + * with the same key and value as the underlying entry. A lock is + * obtained on the mutex before the comparison takes place. + * + * @param o The object to compare with this entry. + * @return <code>true</code> if o is equivalent to the underlying map entry. + */ + public boolean equals(Object o) + { + synchronized (mutex) + { + return e.equals(o); + } + } + + /** + * Returns the key used in the underlying map entry. A lock is obtained + * on the mutex before the key is retrieved. + * + * @return The key of the underlying map entry. + */ + public Object getKey() + { + synchronized (mutex) + { + return e.getKey(); + } + } + + /** + * Returns the value used in the underlying map entry. A lock is obtained + * on the mutex before the value is retrieved. + * + * @return The value of the underlying map entry. + */ + public Object getValue() + { + synchronized (mutex) + { + return e.getValue(); + } + } + + /** + * Computes the hash code for the underlying map entry. + * This computation is described in the documentation for the + * <code>Map</code> interface. A lock is obtained on the mutex + * before the underlying map is accessed. + * + * @return The hash code of the underlying map entry. + * @see Map#hashCode() + */ + public int hashCode() + { + synchronized (mutex) + { + return e.hashCode(); + } + } + + /** + * Replaces the value in the underlying map entry with the specified + * object (optional operation). A lock is obtained on the mutex + * before the map is altered. The map entry, in turn, will alter + * the underlying map object. The operation is undefined if the + * <code>remove()</code> method of the iterator has been called + * beforehand. + * + * @param value the new value to store + * @return the old value + * @throws UnsupportedOperationException if the operation is not supported. + * @throws ClassCastException if the value is of the wrong type. + * @throws IllegalArgumentException if something about the value + * prevents it from existing in this map. + * @throws NullPointerException if the map forbids null values. + */ + public Object setValue(Object value) + { + synchronized (mutex) + { + return e.setValue(value); + } + } + + /** + * Returns a textual representation of the underlying map entry. + * A lock is obtained on the mutex before the entry is accessed. + * + * @return The contents of the map entry in <code>String</code> form. + */ + public String toString() + { + synchronized (mutex) + { + return e.toString(); + } + } + } // class SynchronizedMapEntry + + // Now the actual code. + if (entries == null) + synchronized (mutex) + { + entries = new SynchronizedSet(mutex, m.entrySet()) + { + /** + * Returns an iterator over the set. The iterator has no specific order, + * unless further specified. A lock is obtained on the set's mutex + * before the iterator is created. The created iterator is also + * thread-safe. + * + * @return A synchronized set iterator. + */ + public Iterator iterator() + { + synchronized (super.mutex) + { + return new SynchronizedIterator(super.mutex, c.iterator()) + { + /** + * Retrieves the next map entry from the iterator. + * A lock is obtained on the iterator's mutex before + * the entry is created. The new map entry is enclosed in + * a thread-safe wrapper. + * + * @return A synchronized map entry. + */ + public Object next() + { + synchronized (super.mutex) + { + return new SynchronizedMapEntry(super.next()); + } + } + }; + } + } + }; + } + return entries; + } + + /** + * Returns <code>true</code> if the object, o, is also an instance + * of <code>Map</code> and contains an equivalent + * entry set to that of the underlying map. A lock + * is obtained on the mutex before the objects are + * compared. + * + * @param o The object to compare. + * @return <code>true</code> if o and the underlying map are equivalent. + */ + public boolean equals(Object o) + { + synchronized (mutex) + { + return m.equals(o); + } + } + + /** + * Returns the value associated with the given key, or null + * if no such mapping exists. An ambiguity exists with maps + * that accept null values as a return value of null could + * be due to a non-existent mapping or simply a null value + * for that key. To resolve this, <code>containsKey</code> + * should be used. A lock is obtained on the mutex before + * the value is retrieved from the underlying map. + * + * @param key The key of the required mapping. + * @return The value associated with the given key, or + * null if no such mapping exists. + * @throws ClassCastException if the key is an inappropriate type. + * @throws NullPointerException if this map does not accept null keys. + */ + public Object get(Object key) + { + synchronized (mutex) + { + return m.get(key); + } + } + + /** + * Calculates the hash code of the underlying map as the + * sum of the hash codes of all entries. A lock is obtained + * on the mutex before the hash code is computed. + * + * @return The hash code of the underlying map. + */ + public int hashCode() + { + synchronized (mutex) + { + return m.hashCode(); + } + } + + /** + * Returns <code>true</code> if the underlying map contains no entries. + * A lock is obtained on the mutex before the map is examined. + * + * @return <code>true</code> if the map is empty. + */ + public boolean isEmpty() + { + synchronized (mutex) + { + return m.isEmpty(); + } + } + + /** + * Returns a thread-safe set view of the keys in the underlying map. The + * set is backed by the map, so that changes in one show up in the other. + * Modifications made while an iterator is in progress cause undefined + * behavior. If the set supports removal, these methods remove the + * underlying mapping from the map: <code>Iterator.remove</code>, + * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, + * and <code>clear</code>. Element addition, via <code>add</code> or + * <code>addAll</code>, is not supported via this set. A lock is obtained + * on the mutex before the set is created. + * + * @return A synchronized set containing the keys of the underlying map. + */ + public Set keySet() + { + if (keys == null) + synchronized (mutex) + { + keys = new SynchronizedSet(mutex, m.keySet()); + } + return keys; + } + + /** + * Associates the given key to the given value (optional operation). If the + * underlying map already contains the key, its value is replaced. Be aware + * that in a map that permits <code>null</code> values, a null return does not + * always imply that the mapping was created. A lock is obtained on the mutex + * before the modification is made. + * + * @param key the key to map. + * @param value the value to be mapped. + * @return the previous value of the key, or null if there was no mapping + * @throws UnsupportedOperationException if the operation is not supported + * @throws ClassCastException if the key or value is of the wrong type + * @throws IllegalArgumentException if something about this key or value + * prevents it from existing in this map + * @throws NullPointerException if either the key or the value is null, + * and the map forbids null keys or values + * @see #containsKey(Object) + */ + public Object put(Object key, Object value) + { + synchronized (mutex) + { + return m.put(key, value); + } + } + + /** + * Copies all entries of the given map to the underlying one (optional + * operation). If the map already contains a key, its value is replaced. + * A lock is obtained on the mutex before the operation proceeds. + * + * @param map the mapping to load into this map + * @throws UnsupportedOperationException if the operation is not supported + * @throws ClassCastException if a key or value is of the wrong type + * @throws IllegalArgumentException if something about a key or value + * prevents it from existing in this map + * @throws NullPointerException if the map forbids null keys or values, or + * if <code>m</code> is null. + * @see #put(Object, Object) + */ + public void putAll(Map map) + { + synchronized (mutex) + { + m.putAll(map); + } + } + + /** + * Removes the mapping for the key, o, if present (optional operation). If + * the key is not present, this returns null. Note that maps which permit + * null values may also return null if the key was removed. A prior + * <code>containsKey()</code> check is required to avoid this ambiguity. + * Before the mapping is removed, a lock is obtained on the mutex. + * + * @param o the key to remove + * @return the value the key mapped to, or null if not present + * @throws UnsupportedOperationException if deletion is unsupported + * @throws NullPointerException if the key is null and this map doesn't + * support null keys. + * @throws ClassCastException if the type of the key is not a valid type + * for this map. + */ + public Object remove(Object o) + { + synchronized (mutex) + { + return m.remove(o); + } + } + + /** + * Retrieves the size of the underlying map. A lock + * is obtained on the mutex before access takes place. + * Maps with a size greater than <code>Integer.MAX_VALUE</code> + * return <code>Integer.MAX_VALUE</code> instead. + * + * @return The size of the underlying map. + */ + public int size() + { + synchronized (mutex) + { + return m.size(); + } + } + + /** + * Returns a textual representation of the underlying + * map. A lock is obtained on the mutex before the map + * is accessed. + * + * @return The map in <code>String</code> form. + */ + public String toString() + { + synchronized (mutex) + { + return m.toString(); + } + } + + /** + * Returns a synchronized collection view of the values in the underlying + * map. The collection is backed by the map, so that changes in one show up in + * the other. Modifications made while an iterator is in progress cause + * undefined behavior. If the collection supports removal, these methods + * remove the underlying mapping from the map: <code>Iterator.remove</code>, + * <code>Collection.remove</code>, <code>removeAll</code>, + * <code>retainAll</code>, and <code>clear</code>. Element addition, via + * <code>add</code> or <code>addAll</code>, is not supported via this + * collection. A lock is obtained on the mutex before the collection + * is created. + * + * @return the collection of all values in the underlying map. + */ + public Collection values() + { + if (values == null) + synchronized (mutex) + { + values = new SynchronizedCollection(mutex, m.values()); + } + return values; + } + } // class SynchronizedMap + + /** + * Returns a synchronized (thread-safe) set wrapper backed by the given + * set. Notice that element access through the iterator is thread-safe, but + * if the set can be structurally modified (adding or removing elements) + * then you should synchronize around the iteration to avoid + * non-deterministic behavior:<br> + * <pre> + * Set s = Collections.synchronizedSet(new Set(...)); + * ... + * synchronized (s) + * { + * Iterator i = s.iterator(); + * while (i.hasNext()) + * foo(i.next()); + * } + * </pre><p> + * + * The returned Set implements Serializable, but can only be serialized if + * the set it wraps is likewise Serializable. + * + * @param s the set to wrap + * @return a synchronized view of the set + * @see Serializable + */ + public static Set synchronizedSet(Set s) + { + return new SynchronizedSet(s); + } + + /** + * The implementation of {@link #synchronizedSet(Set)}. This class + * name is required for compatibility with Sun's JDK serializability. + * Package visible, so that sets such as Hashtable.keySet() + * can specify which object to synchronize on. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + static class SynchronizedSet extends SynchronizedCollection + implements Set + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 487447009682186044L; + + /** + * Wrap a given set. + * @param s the set to wrap + * @throws NullPointerException if s is null + */ + SynchronizedSet(Set s) + { + super(s); + } + + /** + * Called only by trusted code to specify the mutex as well as the set. + * @param sync the mutex + * @param s the set + */ + SynchronizedSet(Object sync, Set s) + { + super(sync, s); + } + + /** + * Returns <code>true</code> if the object, o, is a <code>Set</code> + * of the same size as the underlying set, and contains + * each element, e, which occurs in the underlying set. + * A lock is obtained on the mutex before the comparison + * takes place. + * + * @param o The object to compare against. + * @return <code>true</code> if o is an equivalent set. + */ + public boolean equals(Object o) + { + synchronized (mutex) + { + return c.equals(o); + } + } + + /** + * Computes the hash code for the underlying set as the + * sum of the hash code of all elements within the set. + * A lock is obtained on the mutex before the computation + * occurs. + * + * @return The hash code for the underlying set. + */ + public int hashCode() + { + synchronized (mutex) + { + return c.hashCode(); + } + } + } // class SynchronizedSet + + /** + * Returns a synchronized (thread-safe) sorted map wrapper backed by the + * given map. Notice that element access through the collection views, + * subviews, and their iterators are thread-safe, but if the map can be + * structurally modified (adding or removing elements) then you should + * synchronize around the iteration to avoid non-deterministic behavior:<br> + * <pre> + * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...)); + * ... + * Set s = m.keySet(); // safe outside a synchronized block + * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block + * Set s2 = m2.keySet(); // safe outside a synchronized block + * synchronized (m) // synch on m, not m2, s or s2 + * { + * Iterator i = s.iterator(); + * while (i.hasNext()) + * foo(i.next()); + * i = s2.iterator(); + * while (i.hasNext()) + * bar(i.next()); + * } + * </pre><p> + * + * The returned SortedMap implements Serializable, but can only be + * serialized if the map it wraps is likewise Serializable. + * + * @param m the sorted map to wrap + * @return a synchronized view of the sorted map + * @see Serializable + */ + public static SortedMap synchronizedSortedMap(SortedMap m) + { + return new SynchronizedSortedMap(m); + } + + /** + * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SynchronizedSortedMap extends SynchronizedMap + implements SortedMap + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -8798146769416483793L; + + /** + * The wrapped map; stored both here and in the superclass to avoid + * excessive casting. + * @serial the wrapped map + */ + private final SortedMap sm; + + /** + * Wrap a given map. + * @param sm the map to wrap + * @throws NullPointerException if sm is null + */ + SynchronizedSortedMap(SortedMap sm) + { + super(sm); + this.sm = sm; + } + + /** + * Called only by trusted code to specify the mutex as well as the map. + * @param sync the mutex + * @param sm the map + */ + SynchronizedSortedMap(Object sync, SortedMap sm) + { + super(sync, sm); + this.sm = sm; + } + + /** + * Returns the comparator used in sorting the underlying map, or null if + * it is the keys' natural ordering. A lock is obtained on the mutex + * before the comparator is retrieved. + * + * @return the sorting comparator. + */ + public Comparator comparator() + { + synchronized (mutex) + { + return sm.comparator(); + } + } + + /** + * Returns the first, lowest sorted, key from the underlying map. + * A lock is obtained on the mutex before the map is accessed. + * + * @return the first key. + * @throws NoSuchElementException if this map is empty. + */ + public Object firstKey() + { + synchronized (mutex) + { + return sm.firstKey(); + } + } + + /** + * Returns a submap containing the keys from the first + * key (as returned by <code>firstKey()</code>) to + * the key before that specified. The submap supports all + * operations supported by the underlying map and all actions + * taking place on the submap are also reflected in the underlying + * map. A lock is obtained on the mutex prior to submap creation. + * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>. + * The submap retains the thread-safe status of this map. + * + * @param toKey the exclusive upper range of the submap. + * @return a submap from <code>firstKey()</code> to the + * the key preceding toKey. + * @throws ClassCastException if toKey is not comparable to the underlying + * map's contents. + * @throws IllegalArgumentException if toKey is outside the map's range. + * @throws NullPointerException if toKey is null. but the map does not allow + * null keys. + */ + public SortedMap headMap(Object toKey) + { + synchronized (mutex) + { + return new SynchronizedSortedMap(mutex, sm.headMap(toKey)); + } + } + + /** + * Returns the last, highest sorted, key from the underlying map. + * A lock is obtained on the mutex before the map is accessed. + * + * @return the last key. + * @throws NoSuchElementException if this map is empty. + */ + public Object lastKey() + { + synchronized (mutex) + { + return sm.lastKey(); + } + } + + /** + * Returns a submap containing the keys from fromKey to + * the key before toKey. The submap supports all + * operations supported by the underlying map and all actions + * taking place on the submap are also reflected in the underlying + * map. A lock is obtained on the mutex prior to submap creation. + * The submap retains the thread-safe status of this map. + * + * @param fromKey the inclusive lower range of the submap. + * @param toKey the exclusive upper range of the submap. + * @return a submap from fromKey to the key preceding toKey. + * @throws ClassCastException if fromKey or toKey is not comparable + * to the underlying map's contents. + * @throws IllegalArgumentException if fromKey or toKey is outside the map's + * range. + * @throws NullPointerException if fromKey or toKey is null. but the map does + * not allow null keys. + */ + public SortedMap subMap(Object fromKey, Object toKey) + { + synchronized (mutex) + { + return new SynchronizedSortedMap(mutex, sm.subMap(fromKey, toKey)); + } + } + + /** + * Returns a submap containing all the keys from fromKey onwards. + * The submap supports all operations supported by the underlying + * map and all actions taking place on the submap are also reflected + * in the underlying map. A lock is obtained on the mutex prior to + * submap creation. The submap retains the thread-safe status of + * this map. + * + * @param fromKey the inclusive lower range of the submap. + * @return a submap from fromKey to <code>lastKey()</code>. + * @throws ClassCastException if fromKey is not comparable to the underlying + * map's contents. + * @throws IllegalArgumentException if fromKey is outside the map's range. + * @throws NullPointerException if fromKey is null. but the map does not allow + * null keys. + */ + public SortedMap tailMap(Object fromKey) + { + synchronized (mutex) + { + return new SynchronizedSortedMap(mutex, sm.tailMap(fromKey)); + } + } + } // class SynchronizedSortedMap + + /** + * Returns a synchronized (thread-safe) sorted set wrapper backed by the + * given set. Notice that element access through the iterator and through + * subviews are thread-safe, but if the set can be structurally modified + * (adding or removing elements) then you should synchronize around the + * iteration to avoid non-deterministic behavior:<br> + * <pre> + * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...)); + * ... + * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block + * synchronized (s) // synch on s, not s2 + * { + * Iterator i = s2.iterator(); + * while (i.hasNext()) + * foo(i.next()); + * } + * </pre><p> + * + * The returned SortedSet implements Serializable, but can only be + * serialized if the set it wraps is likewise Serializable. + * + * @param s the sorted set to wrap + * @return a synchronized view of the sorted set + * @see Serializable + */ + public static SortedSet synchronizedSortedSet(SortedSet s) + { + return new SynchronizedSortedSet(s); + } + + /** + * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class SynchronizedSortedSet extends SynchronizedSet + implements SortedSet + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 8695801310862127406L; + + /** + * The wrapped set; stored both here and in the superclass to avoid + * excessive casting. + * @serial the wrapped set + */ + private final SortedSet ss; + + /** + * Wrap a given set. + * @param ss the set to wrap + * @throws NullPointerException if ss is null + */ + SynchronizedSortedSet(SortedSet ss) + { + super(ss); + this.ss = ss; + } + + /** + * Called only by trusted code to specify the mutex as well as the set. + * @param sync the mutex + * @param l the list + */ + SynchronizedSortedSet(Object sync, SortedSet ss) + { + super(sync, ss); + this.ss = ss; + } + + /** + * Returns the comparator used in sorting the underlying set, or null if + * it is the elements' natural ordering. A lock is obtained on the mutex + * before the comparator is retrieved. + * + * @return the sorting comparator. + */ + public Comparator comparator() + { + synchronized (mutex) + { + return ss.comparator(); + } + } + + /** + * Returns the first, lowest sorted, element from the underlying set. + * A lock is obtained on the mutex before the set is accessed. + * + * @return the first element. + * @throws NoSuchElementException if this set is empty. + */ + public Object first() + { + synchronized (mutex) + { + return ss.first(); + } + } + + /** + * Returns a subset containing the element from the first + * element (as returned by <code>first()</code>) to + * the element before that specified. The subset supports all + * operations supported by the underlying set and all actions + * taking place on the subset are also reflected in the underlying + * set. A lock is obtained on the mutex prior to subset creation. + * This operation is equivalent to <code>subSet(first(), toElement)</code>. + * The subset retains the thread-safe status of this set. + * + * @param toElement the exclusive upper range of the subset. + * @return a subset from <code>first()</code> to the + * the element preceding toElement. + * @throws ClassCastException if toElement is not comparable to the underlying + * set's contents. + * @throws IllegalArgumentException if toElement is outside the set's range. + * @throws NullPointerException if toElement is null. but the set does not allow + * null elements. + */ + public SortedSet headSet(Object toElement) + { + synchronized (mutex) + { + return new SynchronizedSortedSet(mutex, ss.headSet(toElement)); + } + } + + /** + * Returns the last, highest sorted, element from the underlying set. + * A lock is obtained on the mutex before the set is accessed. + * + * @return the last element. + * @throws NoSuchElementException if this set is empty. + */ + public Object last() + { + synchronized (mutex) + { + return ss.last(); + } + } + + /** + * Returns a subset containing the elements from fromElement to + * the element before toElement. The subset supports all + * operations supported by the underlying set and all actions + * taking place on the subset are also reflected in the underlying + * set. A lock is obtained on the mutex prior to subset creation. + * The subset retains the thread-safe status of this set. + * + * @param fromElement the inclusive lower range of the subset. + * @param toElement the exclusive upper range of the subset. + * @return a subset from fromElement to the element preceding toElement. + * @throws ClassCastException if fromElement or toElement is not comparable + * to the underlying set's contents. + * @throws IllegalArgumentException if fromElement or toElement is outside the set's + * range. + * @throws NullPointerException if fromElement or toElement is null. but the set does + * not allow null elements. + */ + public SortedSet subSet(Object fromElement, Object toElement) + { + synchronized (mutex) + { + return new SynchronizedSortedSet(mutex, + ss.subSet(fromElement, toElement)); + } + } + + /** + * Returns a subset containing all the elements from fromElement onwards. + * The subset supports all operations supported by the underlying + * set and all actions taking place on the subset are also reflected + * in the underlying set. A lock is obtained on the mutex prior to + * subset creation. The subset retains the thread-safe status of + * this set. + * + * @param fromElement the inclusive lower range of the subset. + * @return a subset from fromElement to <code>last()</code>. + * @throws ClassCastException if fromElement is not comparable to the underlying + * set's contents. + * @throws IllegalArgumentException if fromElement is outside the set's range. + * @throws NullPointerException if fromElement is null. but the set does not allow + * null elements. + */ + public SortedSet tailSet(Object fromElement) + { + synchronized (mutex) + { + return new SynchronizedSortedSet(mutex, ss.tailSet(fromElement)); + } + } + } // class SynchronizedSortedSet + + + /** + * Returns an unmodifiable view of the given collection. This allows + * "read-only" access, although changes in the backing collection show up + * in this view. Attempts to modify the collection directly or via iterators + * will fail with {@link UnsupportedOperationException}. Although this view + * prevents changes to the structure of the collection and its elements, the values + * referenced by the objects in the collection can still be modified. + * <p> + * + * Since the collection might be a List or a Set, and those have incompatible + * equals and hashCode requirements, this relies on Object's implementation + * rather than passing those calls on to the wrapped collection. The returned + * Collection implements Serializable, but can only be serialized if + * the collection it wraps is likewise Serializable. + * + * @param c the collection to wrap + * @return a read-only view of the collection + * @see Serializable + */ + public static Collection unmodifiableCollection(Collection c) + { + return new UnmodifiableCollection(c); + } + + /** + * The implementation of {@link #unmodifiableCollection(Collection)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableCollection + implements Collection, Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 1820017752578914078L; + + /** + * The wrapped collection. Package visible for use by subclasses. + * @serial the real collection + */ + final Collection c; + + /** + * Wrap a given collection. + * @param c the collection to wrap + * @throws NullPointerException if c is null + */ + UnmodifiableCollection(Collection c) + { + this.c = c; + if (c == null) + throw new NullPointerException(); + } + + /** + * Blocks the addition of elements to the underlying collection. + * This method never returns, throwing an exception instead. + * + * @param o the object to add. + * @return <code>true</code> if the collection was modified as a result of this action. + * @throws UnsupportedOperationException as an unmodifiable collection does not + * support the add operation. + */ + public boolean add(Object o) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the addition of a collection of elements to the underlying + * collection. This method never returns, throwing an exception instead. + * + * @param c the collection to add. + * @return <code>true</code> if the collection was modified as a result of this action. + * @throws UnsupportedOperationException as an unmodifiable collection does not + * support the <code>addAll</code> operation. + */ + public boolean addAll(Collection c) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the clearing of the underlying collection. This method never + * returns, throwing an exception instead. + * + * @throws UnsupportedOperationException as an unmodifiable collection does + * not support the <code>clear()</code> operation. + */ + public void clear() + { + throw new UnsupportedOperationException(); + } + + /** + * Test whether the underlying collection contains a given object as one of its + * elements. + * + * @param o the element to look for. + * @return <code>true</code> if the underlying collection contains at least + * one element e such that + * <code>o == null ? e == null : o.equals(e)</code>. + * @throws ClassCastException if the type of o is not a valid type for the + * underlying collection. + * @throws NullPointerException if o is null and the underlying collection + * doesn't support null values. + */ + public boolean contains(Object o) + { + return c.contains(o); + } + + /** + * Test whether the underlying collection contains every element in a given + * collection. + * + * @param c1 the collection to test for. + * @return <code>true</code> if for every element o in c, contains(o) would + * return <code>true</code>. + * @throws ClassCastException if the type of any element in c is not a valid + * type for the underlying collection. + * @throws NullPointerException if some element of c is null and the underlying + * collection does not support null values. + * @throws NullPointerException if c itself is null. + */ + public boolean containsAll(Collection c1) + { + return c.containsAll(c1); + } + + /** + * Tests whether the underlying collection is empty, that is, + * if size() == 0. + * + * @return <code>true</code> if this collection contains no elements. + */ + public boolean isEmpty() + { + return c.isEmpty(); + } + + /** + * Obtain an Iterator over the underlying collection, which maintains + * its unmodifiable nature. + * + * @return an UnmodifiableIterator over the elements of the underlying + * collection, in any order. + */ + public Iterator iterator() + { + return new UnmodifiableIterator(c.iterator()); + } + + /** + * Blocks the removal of an object from the underlying collection. + * This method never returns, throwing an exception instead. + * + * @param o The object to remove. + * @return <code>true</code> if the object was removed (i.e. the underlying + * collection returned 1 or more instances of o). + * @throws UnsupportedOperationException as an unmodifiable collection + * does not support the <code>remove()</code> operation. + */ + public boolean remove(Object o) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the removal of a collection of objects from the underlying + * collection. This method never returns, throwing an exception + * instead. + * + * @param c The collection of objects to remove. + * @return <code>true</code> if the collection was modified. + * @throws UnsupportedOperationException as an unmodifiable collection + * does not support the <code>removeAll()</code> operation. + */ + public boolean removeAll(Collection c) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the removal of all elements from the underlying collection, + * except those in the supplied collection. This method never returns, + * throwing an exception instead. + * + * @param c The collection of objects to retain. + * @return <code>true</code> if the collection was modified. + * @throws UnsupportedOperationException as an unmodifiable collection + * does not support the <code>retainAll()</code> operation. + */ + public boolean retainAll(Collection c) + { + throw new UnsupportedOperationException(); + } + + /** + * Retrieves the number of elements in the underlying collection. + * + * @return the number of elements in the collection. + */ + public int size() + { + return c.size(); + } + + /** + * Copy the current contents of the underlying collection into an array. + * + * @return an array of type Object[] with a length equal to the size of the + * underlying collection and containing the elements currently in + * the underlying collection, in any order. + */ + public Object[] toArray() + { + return c.toArray(); + } + + /** + * Copy the current contents of the underlying collection into an array. If + * the array passed as an argument has length less than the size of the + * underlying collection, an array of the same run-time type as a, with a length + * equal to the size of the underlying collection, is allocated using reflection. + * Otherwise, a itself is used. The elements of the underlying collection are + * copied into it, and if there is space in the array, the following element is + * set to null. The resultant array is returned. + * Note: The fact that the following element is set to null is only useful + * if it is known that this collection does not contain any null elements. + * + * @param a the array to copy this collection into. + * @return an array containing the elements currently in the underlying + * collection, in any order. + * @throws ArrayStoreException if the type of any element of the + * collection is not a subtype of the element type of a. + */ + public Object[] toArray(Object[] a) + { + return c.toArray(a); + } + + /** + * A textual representation of the unmodifiable collection. + * + * @return The unmodifiable collection in the form of a <code>String</code>. + */ + public String toString() + { + return c.toString(); + } + } // class UnmodifiableCollection + + /** + * The implementation of the various iterator methods in the + * unmodifiable classes. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableIterator implements Iterator + { + /** + * The wrapped iterator. + */ + private final Iterator i; + + /** + * Only trusted code creates a wrapper. + * @param i the wrapped iterator + */ + UnmodifiableIterator(Iterator i) + { + this.i = i; + } + + /** + * Obtains the next element in the underlying collection. + * + * @return the next element in the collection. + * @throws NoSuchElementException if there are no more elements. + */ + public Object next() + { + return i.next(); + } + /** + * Tests whether there are still elements to be retrieved from the + * underlying collection by <code>next()</code>. When this method + * returns <code>true</code>, an exception will not be thrown on calling + * <code>next()</code>. + * + * @return <code>true</code> if there is at least one more element in the underlying + * collection. + */ + public boolean hasNext() + { + return i.hasNext(); + } + + /** + * Blocks the removal of elements from the underlying collection by the + * iterator. + * + * @throws UnsupportedOperationException as an unmodifiable collection + * does not support the removal of elements by its iterator. + */ + public void remove() + { + throw new UnsupportedOperationException(); + } + } // class UnmodifiableIterator + + /** + * Returns an unmodifiable view of the given list. This allows + * "read-only" access, although changes in the backing list show up + * in this view. Attempts to modify the list directly, via iterators, or + * via sublists, will fail with {@link UnsupportedOperationException}. + * Although this view prevents changes to the structure of the list and + * its elements, the values referenced by the objects in the list can + * still be modified. + * <p> + * + * The returned List implements Serializable, but can only be serialized if + * the list it wraps is likewise Serializable. In addition, if the wrapped + * list implements RandomAccess, this does too. + * + * @param l the list to wrap + * @return a read-only view of the list + * @see Serializable + * @see RandomAccess + */ + public static List unmodifiableList(List l) + { + if (l instanceof RandomAccess) + return new UnmodifiableRandomAccessList(l); + return new UnmodifiableList(l); + } + + /** + * The implementation of {@link #unmodifiableList(List)} for sequential + * lists. This class name is required for compatibility with Sun's JDK + * serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableList extends UnmodifiableCollection + implements List + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -283967356065247728L; + + + /** + * The wrapped list; stored both here and in the superclass to avoid + * excessive casting. Package visible for use by subclass. + * @serial the wrapped list + */ + final List list; + + /** + * Wrap a given list. + * @param l the list to wrap + * @throws NullPointerException if l is null + */ + UnmodifiableList(List l) + { + super(l); + list = l; + } + + /** + * Blocks the addition of an element to the underlying + * list at a specific index. This method never returns, + * throwing an exception instead. + * + * @param index The index at which to place the new element. + * @param o the object to add. + * @throws UnsupportedOperationException as an unmodifiable + * list doesn't support the <code>add()</code> operation. + */ + public void add(int index, Object o) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the addition of a collection of elements to the + * underlying list at a specific index. This method never + * returns, throwing an exception instead. + * + * @param index The index at which to place the new element. + * @param c the collections of objects to add. + * @throws UnsupportedOperationException as an unmodifiable + * list doesn't support the <code>addAll()</code> operation. + */ + public boolean addAll(int index, Collection c) + { + throw new UnsupportedOperationException(); + } + + /** + * Returns <code>true</code> if the object, o, is an instance of + * <code>List</code> with the same size and elements + * as the underlying list. + * + * @param o The object to compare. + * @return <code>true</code> if o is equivalent to the underlying list. + */ + public boolean equals(Object o) + { + return list.equals(o); + } + + /** + * Retrieves the element at a given index in the underlying list. + * + * @param index the index of the element to be returned + * @return the element at index index in this list + * @throws IndexOutOfBoundsException if index < 0 || index >= size() + */ + public Object get(int index) + { + return list.get(index); + } + + /** + * Computes the hash code for the underlying list. + * The exact computation is described in the documentation + * of the <code>List</code> interface. + * + * @return The hash code of the underlying list. + * @see List#hashCode() + */ + public int hashCode() + { + return list.hashCode(); + } + + /** + * Obtain the first index at which a given object is to be found in the + * underlying list. + * + * @param o the object to search for + * @return the least integer n such that <code>o == null ? get(n) == null : + * o.equals(get(n))</code>, or -1 if there is no such index. + * @throws ClassCastException if the type of o is not a valid + * type for the underlying list. + * @throws NullPointerException if o is null and the underlying + * list does not support null values. + */ + public int indexOf(Object o) + { + return list.indexOf(o); + } + + /** + * Obtain the last index at which a given object is to be found in the + * underlying list. + * + * @return the greatest integer n such that <code>o == null ? get(n) == null + * : o.equals(get(n))</code>, or -1 if there is no such index. + * @throws ClassCastException if the type of o is not a valid + * type for the underlying list. + * @throws NullPointerException if o is null and the underlying + * list does not support null values. + */ + public int lastIndexOf(Object o) + { + return list.lastIndexOf(o); + } + + /** + * Obtains a list iterator over the underlying list, starting at the beginning + * and maintaining the unmodifiable nature of this list. + * + * @return a <code>UnmodifiableListIterator</code> over the elements of the + * underlying list, in order, starting at the beginning. + */ + public ListIterator listIterator() + { + return new UnmodifiableListIterator(list.listIterator()); + } + + /** + * Obtains a list iterator over the underlying list, starting at the specified + * index and maintaining the unmodifiable nature of this list. An initial call + * to <code>next()</code> will retrieve the element at the specified index, + * and an initial call to <code>previous()</code> will retrieve the element + * at index - 1. + * + * + * @param index the position, between 0 and size() inclusive, to begin the + * iteration from. + * @return a <code>UnmodifiableListIterator</code> over the elements of the + * underlying list, in order, starting at the specified index. + * @throws IndexOutOfBoundsException if index < 0 || index > size() + */ + public ListIterator listIterator(int index) + { + return new UnmodifiableListIterator(list.listIterator(index)); + } + + /** + * Blocks the removal of the element at the specified index. + * This method never returns, throwing an exception instead. + * + * @param index The index of the element to remove. + * @return the removed element. + * @throws UnsupportedOperationException as an unmodifiable + * list does not support the <code>remove()</code> + * operation. + */ + public Object remove(int index) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the replacement of the element at the specified index. + * This method never returns, throwing an exception instead. + * + * @param index The index of the element to replace. + * @param o The new object to place at the specified index. + * @return the replaced element. + * @throws UnsupportedOperationException as an unmodifiable + * list does not support the <code>set()</code> + * operation. + */ + public Object set(int index, Object o) + { + throw new UnsupportedOperationException(); + } + + /** + * Obtain a List view of a subsection of the underlying list, from + * fromIndex (inclusive) to toIndex (exclusive). If the two indices + * are equal, the sublist is empty. The returned list will be + * unmodifiable, like this list. Changes to the elements of the + * returned list will be reflected in the underlying list. No structural + * modifications can take place in either list. + * + * @param fromIndex the index that the returned list should start from + * (inclusive). + * @param toIndex the index that the returned list should go to (exclusive). + * @return a List backed by a subsection of the underlying list. + * @throws IndexOutOfBoundsException if fromIndex < 0 + * || toIndex > size() || fromIndex > toIndex. + */ + public List subList(int fromIndex, int toIndex) + { + return unmodifiableList(list.subList(fromIndex, toIndex)); + } + } // class UnmodifiableList + + /** + * The implementation of {@link #unmodifiableList(List)} for random-access + * lists. This class name is required for compatibility with Sun's JDK + * serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class UnmodifiableRandomAccessList + extends UnmodifiableList implements RandomAccess + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -2542308836966382001L; + + /** + * Wrap a given list. + * @param l the list to wrap + * @throws NullPointerException if l is null + */ + UnmodifiableRandomAccessList(List l) + { + super(l); + } + } // class UnmodifiableRandomAccessList + + /** + * The implementation of {@link UnmodifiableList#listIterator()}. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class UnmodifiableListIterator + extends UnmodifiableIterator implements ListIterator + { + /** + * The wrapped iterator, stored both here and in the superclass to + * avoid excessive casting. + */ + private final ListIterator li; + + /** + * Only trusted code creates a wrapper. + * @param li the wrapped iterator + */ + UnmodifiableListIterator(ListIterator li) + { + super(li); + this.li = li; + } + + /** + * Blocks the addition of an object to the list underlying this iterator. + * This method never returns, throwing an exception instead. + * + * @param o The object to add. + * @throws UnsupportedOperationException as the iterator of an unmodifiable + * list does not support the <code>add()</code> operation. + */ + public void add(Object o) + { + throw new UnsupportedOperationException(); + } + + /** + * Tests whether there are still elements to be retrieved from the + * underlying collection by <code>previous()</code>. When this method + * returns <code>true</code>, an exception will not be thrown on calling + * <code>previous()</code>. + * + * @return <code>true</code> if there is at least one more element prior to the + * current position in the underlying list. + */ + public boolean hasPrevious() + { + return li.hasPrevious(); + } + + /** + * Find the index of the element that would be returned by a call to next. + * If <code>hasNext()</code> returns <code>false</code>, this returns the list size. + * + * @return the index of the element that would be returned by + * <code>next()</code>. + */ + public int nextIndex() + { + return li.nextIndex(); + } + + /** + * Obtains the previous element in the underlying list. + * + * @return the previous element in the list. + * @throws NoSuchElementException if there are no more prior elements. + */ + public Object previous() + { + return li.previous(); + } + + /** + * Find the index of the element that would be returned by a call to + * previous. If <code>hasPrevious()</code> returns <code>false</code>, + * this returns -1. + * + * @return the index of the element that would be returned by + * <code>previous()</code>. + */ + public int previousIndex() + { + return li.previousIndex(); + } + + /** + * Blocks the replacement of an element in the list underlying this + * iterator. This method never returns, throwing an exception instead. + * + * @param o The new object to replace the existing one. + * @throws UnsupportedOperationException as the iterator of an unmodifiable + * list does not support the <code>set()</code> operation. + */ + public void set(Object o) + { + throw new UnsupportedOperationException(); + } + } // class UnmodifiableListIterator + + /** + * Returns an unmodifiable view of the given map. This allows "read-only" + * access, although changes in the backing map show up in this view. + * Attempts to modify the map directly, or via collection views or their + * iterators will fail with {@link UnsupportedOperationException}. + * Although this view prevents changes to the structure of the map and its + * entries, the values referenced by the objects in the map can still be + * modified. + * <p> + * + * The returned Map implements Serializable, but can only be serialized if + * the map it wraps is likewise Serializable. + * + * @param m the map to wrap + * @return a read-only view of the map + * @see Serializable + */ + public static Map unmodifiableMap(Map m) + { + return new UnmodifiableMap(m); + } + + /** + * The implementation of {@link #unmodifiableMap(Map)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableMap implements Map, Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -1034234728574286014L; + + /** + * The wrapped map. + * @serial the real map + */ + private final Map m; + + /** + * Cache the entry set. + */ + private transient Set entries; + + /** + * Cache the key set. + */ + private transient Set keys; + + /** + * Cache the value collection. + */ + private transient Collection values; + + /** + * Wrap a given map. + * @param m the map to wrap + * @throws NullPointerException if m is null + */ + UnmodifiableMap(Map m) + { + this.m = m; + if (m == null) + throw new NullPointerException(); + } + + /** + * Blocks the clearing of entries from the underlying map. + * This method never returns, throwing an exception instead. + * + * @throws UnsupportedOperationException as an unmodifiable + * map does not support the <code>clear()</code> operation. + */ + public void clear() + { + throw new UnsupportedOperationException(); + } + + /** + * Returns <code>true</code> if the underlying map contains a mapping for + * the given key. + * + * @param key the key to search for + * @return <code>true</code> if the map contains the key + * @throws ClassCastException if the key is of an inappropriate type + * @throws NullPointerException if key is <code>null</code> but the map + * does not permit null keys + */ + public boolean containsKey(Object key) + { + return m.containsKey(key); + } + + /** + * Returns <code>true</code> if the underlying map contains at least one mapping with + * the given value. In other words, it returns <code>true</code> if a value v exists where + * <code>(value == null ? v == null : value.equals(v))</code>. This usually + * requires linear time. + * + * @param value the value to search for + * @return <code>true</code> if the map contains the value + * @throws ClassCastException if the type of the value is not a valid type + * for this map. + * @throws NullPointerException if the value is null and the map doesn't + * support null values. + */ + public boolean containsValue(Object value) + { + return m.containsValue(value); + } + + /** + * Returns a unmodifiable set view of the entries in the underlying map. + * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>. + * The set is backed by the map, so that changes in one show up in the other. + * Modifications made while an iterator is in progress cause undefined + * behavior. These modifications are again limited to the values of + * the objects. + * + * @return the unmodifiable set view of all mapping entries. + * @see Map.Entry + */ + public Set entrySet() + { + if (entries == null) + entries = new UnmodifiableEntrySet(m.entrySet()); + return entries; + } + + /** + * The implementation of {@link UnmodifiableMap#entrySet()}. This class + * name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static final class UnmodifiableEntrySet extends UnmodifiableSet + implements Serializable + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = 7854390611657943733L; + + /** + * Wrap a given set. + * @param s the set to wrap + */ + UnmodifiableEntrySet(Set s) + { + super(s); + } + + // The iterator must return unmodifiable map entries. + public Iterator iterator() + { + return new UnmodifiableIterator(c.iterator()) + { + /** + * Obtains the next element from the underlying set of + * map entries. + * + * @return the next element in the collection. + * @throws NoSuchElementException if there are no more elements. + */ + public Object next() + { + final Map.Entry e = (Map.Entry) super.next(); + return new Map.Entry() + { + /** + * Returns <code>true</code> if the object, o, is also a map entry with an + * identical key and value. + * + * @param o the object to compare. + * @return <code>true</code> if o is an equivalent map entry. + */ + public boolean equals(Object o) + { + return e.equals(o); + } + + /** + * Returns the key of this map entry. + * + * @return the key. + */ + public Object getKey() + { + return e.getKey(); + } + + /** + * Returns the value of this map entry. + * + * @return the value. + */ + public Object getValue() + { + return e.getValue(); + } + + /** + * Computes the hash code of this map entry. + * The computation is described in the <code>Map</code> + * interface documentation. + * + * @return the hash code of this entry. + * @see Map#hashCode() + */ + public int hashCode() + { + return e.hashCode(); + } + + /** + * Blocks the alteration of the value of this map entry. + * This method never returns, throwing an exception instead. + * + * @param value The new value. + * @throws UnsupportedOperationException as an unmodifiable + * map entry does not support the <code>setValue()</code> + * operation. + */ + public Object setValue(Object value) + { + throw new UnsupportedOperationException(); + } + + /** + * Returns a textual representation of the map entry. + * + * @return The map entry as a <code>String</code>. + */ + public String toString() + { + return e.toString(); + } + }; + } + }; + } + } // class UnmodifiableEntrySet + + /** + * Returns <code>true</code> if the object, o, is also an instance + * of <code>Map</code> with an equal set of map entries. + * + * @param o The object to compare. + * @return <code>true</code> if o is an equivalent map. + */ + public boolean equals(Object o) + { + return m.equals(o); + } + + /** + * Returns the value associated with the supplied key or + * null if no such mapping exists. An ambiguity can occur + * if null values are accepted by the underlying map. + * In this case, <code>containsKey()</code> can be used + * to separate the two possible cases of a null result. + * + * @param key The key to look up. + * @return the value associated with the key, or null if key not in map. + * @throws ClassCastException if the key is an inappropriate type. + * @throws NullPointerException if this map does not accept null keys. + * @see #containsKey(Object) + */ + public Object get(Object key) + { + return m.get(key); + } + + /** + * Blocks the addition of a new entry to the underlying map. + * This method never returns, throwing an exception instead. + * + * @param key The new key. + * @param value The new value. + * @return the previous value of the key, or null if there was no mapping. + * @throws UnsupportedOperationException as an unmodifiable + * map does not support the <code>put()</code> operation. + */ + public Object put(Object key, Object value) + { + throw new UnsupportedOperationException(); + } + + /** + * Computes the hash code for the underlying map, as the sum + * of the hash codes of all entries. + * + * @return The hash code of the underlying map. + * @see Map.Entry#hashCode() + */ + public int hashCode() + { + return m.hashCode(); + } + + /** + * Returns <code>true</code> if the underlying map contains no entries. + * + * @return <code>true</code> if the map is empty. + */ + public boolean isEmpty() + { + return m.isEmpty(); + } + + /** + * Returns a unmodifiable set view of the keys in the underlying map. + * The set is backed by the map, so that changes in one show up in the other. + * Modifications made while an iterator is in progress cause undefined + * behavior. These modifications are again limited to the values of + * the keys. + * + * @return the set view of all keys. + */ + public Set keySet() + { + if (keys == null) + keys = new UnmodifiableSet(m.keySet()); + return keys; + } + + /** + * Blocks the addition of the entries in the supplied map. + * This method never returns, throwing an exception instead. + * + * @param m The map, the entries of which should be added + * to the underlying map. + * @throws UnsupportedOperationException as an unmodifiable + * map does not support the <code>putAll</code> operation. + */ + public void putAll(Map m) + { + throw new UnsupportedOperationException(); + } + + /** + * Blocks the removal of an entry from the map. + * This method never returns, throwing an exception instead. + * + * @param o The key of the entry to remove. + * @return The value the key was associated with, or null + * if no such mapping existed. Null is also returned + * if the removed entry had a null key. + * @throws UnsupportedOperationException as an unmodifiable + * map does not support the <code>remove</code> operation. + */ + public Object remove(Object o) + { + throw new UnsupportedOperationException(); + } + + + /** + * Returns the number of key-value mappings in the underlying map. + * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE + * is returned. + * + * @return the number of mappings. + */ + public int size() + { + return m.size(); + } + + /** + * Returns a textual representation of the map. + * + * @return The map in the form of a <code>String</code>. + */ + public String toString() + { + return m.toString(); + } + + /** + * Returns a unmodifiable collection view of the values in the underlying map. + * The collection is backed by the map, so that changes in one show up in the other. + * Modifications made while an iterator is in progress cause undefined + * behavior. These modifications are again limited to the values of + * the keys. + * + * @return the collection view of all values. + */ + public Collection values() + { + if (values == null) + values = new UnmodifiableCollection(m.values()); + return values; + } + } // class UnmodifiableMap + + /** + * Returns an unmodifiable view of the given set. This allows + * "read-only" access, although changes in the backing set show up + * in this view. Attempts to modify the set directly or via iterators + * will fail with {@link UnsupportedOperationException}. + * Although this view prevents changes to the structure of the set and its + * entries, the values referenced by the objects in the set can still be + * modified. + * <p> + * + * The returned Set implements Serializable, but can only be serialized if + * the set it wraps is likewise Serializable. + * + * @param s the set to wrap + * @return a read-only view of the set + * @see Serializable + */ + public static Set unmodifiableSet(Set s) + { + return new UnmodifiableSet(s); + } + + /** + * The implementation of {@link #unmodifiableSet(Set)}. This class + * name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableSet extends UnmodifiableCollection + implements Set + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -9215047833775013803L; + + /** + * Wrap a given set. + * @param s the set to wrap + * @throws NullPointerException if s is null + */ + UnmodifiableSet(Set s) + { + super(s); + } + + /** + * Returns <code>true</code> if the object, o, is also an instance of + * <code>Set</code> of the same size and with the same entries. + * + * @return <code>true</code> if o is an equivalent set. + */ + public boolean equals(Object o) + { + return c.equals(o); + } + + /** + * Computes the hash code of this set, as the sum of the + * hash codes of all elements within the set. + * + * @return the hash code of the set. + */ + public int hashCode() + { + return c.hashCode(); + } + } // class UnmodifiableSet + + /** + * Returns an unmodifiable view of the given sorted map. This allows + * "read-only" access, although changes in the backing map show up in this + * view. Attempts to modify the map directly, via subviews, via collection + * views, or iterators, will fail with {@link UnsupportedOperationException}. + * Although this view prevents changes to the structure of the map and its + * entries, the values referenced by the objects in the map can still be + * modified. + * <p> + * + * The returned SortedMap implements Serializable, but can only be + * serialized if the map it wraps is likewise Serializable. + * + * @param m the map to wrap + * @return a read-only view of the map + * @see Serializable + */ + public static SortedMap unmodifiableSortedMap(SortedMap m) + { + return new UnmodifiableSortedMap(m); + } + + /** + * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableSortedMap extends UnmodifiableMap + implements SortedMap + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -8806743815996713206L; + + /** + * The wrapped map; stored both here and in the superclass to avoid + * excessive casting. + * @serial the wrapped map + */ + private final SortedMap sm; + + /** + * Wrap a given map. + * @param sm the map to wrap + * @throws NullPointerException if sm is null + */ + UnmodifiableSortedMap(SortedMap sm) + { + super(sm); + this.sm = sm; + } + + /** + * Returns the comparator used in sorting the underlying map, + * or null if it is the keys' natural ordering. + * + * @return the sorting comparator. + */ + public Comparator comparator() + { + return sm.comparator(); + } + + /** + * Returns the first (lowest sorted) key in the map. + * + * @return the first key. + * @throws NoSuchElementException if this map is empty. + */ + public Object firstKey() + { + return sm.firstKey(); + } + + /** + * Returns a unmodifiable view of the portion of the map strictly less + * than toKey. The view is backed by the underlying map, so changes in + * one show up in the other. The submap supports all optional operations + * of the original. This operation is equivalent to + * <code>subMap(firstKey(), toKey)</code>. + * <p> + * + * The returned map throws an IllegalArgumentException any time a key is + * used which is out of the range of toKey. Note that the endpoint, toKey, + * is not included; if you want this value to be included, pass its successor + * object in to toKey. For example, for Integers, you could request + * <code>headMap(new Integer(limit.intValue() + 1))</code>. + * + * @param toKey the exclusive upper range of the submap. + * @return the submap. + * @throws ClassCastException if toKey is not comparable to the map contents. + * @throws IllegalArgumentException if this is a subMap, and toKey is out + * of range. + * @throws NullPointerException if toKey is null but the map does not allow + * null keys. + */ + public SortedMap headMap(Object toKey) + { + return new UnmodifiableSortedMap(sm.headMap(toKey)); + } + + /** + * Returns the last (highest sorted) key in the map. + * + * @return the last key. + * @throws NoSuchElementException if this map is empty. + */ + public Object lastKey() + { + return sm.lastKey(); + } + + /** + * Returns a unmodifiable view of the portion of the map greater than or + * equal to fromKey, and strictly less than toKey. The view is backed by + * the underlying map, so changes in one show up in the other. The submap + * supports all optional operations of the original. + * <p> + * + * The returned map throws an IllegalArgumentException any time a key is + * used which is out of the range of fromKey and toKey. Note that the + * lower endpoint is included, but the upper is not; if you want to + * change the inclusion or exclusion of an endpoint, pass its successor + * object in instead. For example, for Integers, you could request + * <code>subMap(new Integer(lowlimit.intValue() + 1), + * new Integer(highlimit.intValue() + 1))</code> to reverse + * the inclusiveness of both endpoints. + * + * @param fromKey the inclusive lower range of the submap. + * @param toKey the exclusive upper range of the submap. + * @return the submap. + * @throws ClassCastException if fromKey or toKey is not comparable to + * the map contents. + * @throws IllegalArgumentException if this is a subMap, and fromKey or + * toKey is out of range. + * @throws NullPointerException if fromKey or toKey is null but the map + * does not allow null keys. + */ + public SortedMap subMap(Object fromKey, Object toKey) + { + return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey)); + } + + /** + * Returns a unmodifiable view of the portion of the map greater than or + * equal to fromKey. The view is backed by the underlying map, so changes + * in one show up in the other. The submap supports all optional operations + * of the original. + * <p> + * + * The returned map throws an IllegalArgumentException any time a key is + * used which is out of the range of fromKey. Note that the endpoint, fromKey, is + * included; if you do not want this value to be included, pass its successor object in + * to fromKey. For example, for Integers, you could request + * <code>tailMap(new Integer(limit.intValue() + 1))</code>. + * + * @param fromKey the inclusive lower range of the submap + * @return the submap + * @throws ClassCastException if fromKey is not comparable to the map + * contents + * @throws IllegalArgumentException if this is a subMap, and fromKey is out + * of range + * @throws NullPointerException if fromKey is null but the map does not allow + * null keys + */ + public SortedMap tailMap(Object fromKey) + { + return new UnmodifiableSortedMap(sm.tailMap(fromKey)); + } + } // class UnmodifiableSortedMap + + /** + * Returns an unmodifiable view of the given sorted set. This allows + * "read-only" access, although changes in the backing set show up + * in this view. Attempts to modify the set directly, via subsets, or via + * iterators, will fail with {@link UnsupportedOperationException}. + * Although this view prevents changes to the structure of the set and its + * entries, the values referenced by the objects in the set can still be + * modified. + * <p> + * + * The returns SortedSet implements Serializable, but can only be + * serialized if the set it wraps is likewise Serializable. + * + * @param s the set to wrap + * @return a read-only view of the set + * @see Serializable + */ + public static SortedSet unmodifiableSortedSet(SortedSet s) + { + return new UnmodifiableSortedSet(s); + } + + /** + * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This + * class name is required for compatibility with Sun's JDK serializability. + * + * @author Eric Blake (ebb9@email.byu.edu) + */ + private static class UnmodifiableSortedSet extends UnmodifiableSet + implements SortedSet + { + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -4929149591599911165L; + + /** + * The wrapped set; stored both here and in the superclass to avoid + * excessive casting. + * @serial the wrapped set + */ + private SortedSet ss; + + /** + * Wrap a given set. + * @param ss the set to wrap + * @throws NullPointerException if ss is null + */ + UnmodifiableSortedSet(SortedSet ss) + { + super(ss); + this.ss = ss; + } + + /** + * Returns the comparator used in sorting the underlying set, + * or null if it is the elements' natural ordering. + * + * @return the sorting comparator + */ + public Comparator comparator() + { + return ss.comparator(); + } + + /** + * Returns the first (lowest sorted) element in the underlying + * set. + * + * @return the first element. + * @throws NoSuchElementException if the set is empty. + */ + public Object first() + { + return ss.first(); + } + + /** + * Returns a unmodifiable view of the portion of the set strictly + * less than toElement. The view is backed by the underlying set, + * so changes in one show up in the other. The subset supports + * all optional operations of the original. This operation + * is equivalent to <code>subSet(first(), toElement)</code>. + * <p> + * + * The returned set throws an IllegalArgumentException any time an element is + * used which is out of the range of toElement. Note that the endpoint, toElement, + * is not included; if you want this value included, pass its successor object in to + * toElement. For example, for Integers, you could request + * <code>headSet(new Integer(limit.intValue() + 1))</code>. + * + * @param toElement the exclusive upper range of the subset + * @return the subset. + * @throws ClassCastException if toElement is not comparable to the set + * contents. + * @throws IllegalArgumentException if this is a subSet, and toElement is out + * of range. + * @throws NullPointerException if toElement is null but the set does not + * allow null elements. + */ + public SortedSet headSet(Object toElement) + { + return new UnmodifiableSortedSet(ss.headSet(toElement)); + } + + /** + * Returns the last (highest sorted) element in the underlying + * set. + * + * @return the last element. + * @throws NoSuchElementException if the set is empty. + */ + public Object last() + { + return ss.last(); + } + + /** + * Returns a unmodifiable view of the portion of the set greater than or + * equal to fromElement, and strictly less than toElement. The view is backed by + * the underlying set, so changes in one show up in the other. The subset + * supports all optional operations of the original. + * <p> + * + * The returned set throws an IllegalArgumentException any time an element is + * used which is out of the range of fromElement and toElement. Note that the + * lower endpoint is included, but the upper is not; if you want to + * change the inclusion or exclusion of an endpoint, pass its successor + * object in instead. For example, for Integers, you can request + * <code>subSet(new Integer(lowlimit.intValue() + 1), + * new Integer(highlimit.intValue() + 1))</code> to reverse + * the inclusiveness of both endpoints. + * + * @param fromElement the inclusive lower range of the subset. + * @param toElement the exclusive upper range of the subset. + * @return the subset. + * @throws ClassCastException if fromElement or toElement is not comparable + * to the set contents. + * @throws IllegalArgumentException if this is a subSet, and fromElement or + * toElement is out of range. + * @throws NullPointerException if fromElement or toElement is null but the + * set does not allow null elements. + */ + public SortedSet subSet(Object fromElement, Object toElement) + { + return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement)); + } + + /** + * Returns a unmodifiable view of the portion of the set greater than or equal to + * fromElement. The view is backed by the underlying set, so changes in one show up + * in the other. The subset supports all optional operations of the original. + * <p> + * + * The returned set throws an IllegalArgumentException any time an element is + * used which is out of the range of fromElement. Note that the endpoint, + * fromElement, is included; if you do not want this value to be included, pass its + * successor object in to fromElement. For example, for Integers, you could request + * <code>tailSet(new Integer(limit.intValue() + 1))</code>. + * + * @param fromElement the inclusive lower range of the subset + * @return the subset. + * @throws ClassCastException if fromElement is not comparable to the set + * contents. + * @throws IllegalArgumentException if this is a subSet, and fromElement is + * out of range. + * @throws NullPointerException if fromElement is null but the set does not + * allow null elements. + */ + public SortedSet tailSet(Object fromElement) + { + return new UnmodifiableSortedSet(ss.tailSet(fromElement)); + } + } // class UnmodifiableSortedSet +} // class Collections |