Java 1.2 How-To/JavaHowTo.iso/3rdParty/jbuilder/unsupported/JDK1.2beta3/SOURCE/SRC.ZIP/java/util/Collections.java

Java Source | 1998-03-20 | 47.8 KB | 1,425 lines

/*
 * @(#)Collections.java    1.21 98/03/18
 *
 * Copyright 1997, 1998 by Sun Microsystems, Inc.,
 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information
 * of Sun Microsystems, Inc. ("Confidential Information").  You
 * shall not disclose such Confidential Information and shall use
 * it only in accordance with the terms of the license agreement
 * you entered into with Sun.
 */

package java.util;
import java.io.Serializable;

/**
 * This class consists exclusively of static methods that operate on or
 * return Collections.  It contains polymorphic algorithms that operate
 * on collections, "views" and "wrappers", which return a new collection
 * backed by a specified collection, and a few other odds and ends.
 *
 * @author  Josh Bloch
 * @version 1.21 03/18/98
 * @see        Collection
 * @see        Set
 * @see        List
 * @see        Map
 * @since JDK1.2
 */

public class Collections {
    // Algorithms

    /**
     * Sorts the specified List into ascending order, according
     * to the <i>natural comparison method</i> of its elements.  All
     * elements in the List must implement the Comparable interface.
     * Furthermore, all elements in the List must be <i>mutually
     * comparable</i> (that is, e1.compareTo(e2) must not throw a
     * typeMismatchException for any elements e1 and e2 in the List).
     * <p>
     * The sorting algorithm is a tuned quicksort, adapted from Jon
     * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
     * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
     * 1993).  This algorithm offers n*log(n) performance on many data sets
     * that cause other quicksorts to degrade to quadratic performance.
     * <p>
     * The specified List must be modifiable, but need not be resizable.
     * This implementation dumps the specified List into an List, sorts
     * the array, and iterates over the List resetting each element
     * from the corresponding position in the array.  This avoids the
     * n^2*log(n) performance that would result from attempting
     * to sort a LinkedList in place.
     *
     * @param      list the List to be sorted.
     * @exception ClassCastException List contains elements that are not
     *          <i>mutually comparable</i> (for example, Strings and
     *          Integers).
     * @exception UnsupportedOperationException The specified List's
     *          ListIterator not support the set operation.
     * @see Comparable
     */
    public static void sort(List list) {
    Object a[] = list.toArray();
    Arrays.sort(a);
    ListIterator i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set(a[j]);
    }
    }

    /**
     * Sorts the specified List according to the order induced by the
     * specified Comparator.  All elements in the List must be <i>mutually
     * comparable</i> by the specified comparator (that is,
     * comparator.compare(e1, e2) must not throw a typeMismatchException for
     * any elements e1 and e2 in the List).
     * <p>
     * The sorting algorithm is a tuned quicksort, adapted from Jon
     * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
     * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
     * 1993).  This algorithm offers n*log(n) performance on many data sets
     * that cause other quicksorts to degrade to quadratic performance.
     * <p>
     * The specified List must be modifiable, but need not be resizable.
     * This implementation dumps the specified List into an array, sorts
     * the array, and iterates over the List resetting each element
     * from the corresponding position in the array.  This avoids the
     * n^2*log(n) performance that would result from attempting
     * to sort a LinkedList in place.
     *
     * @param      list the List to be sorted.
     * @exception ClassCastException List contains elements that are not
     *          <i>mutually comparable</i> with the specified Comparator.
     * @exception UnsupportedOperationException The specified List's did
     *          ListIterator not support the set operation.
     * @see Comparator
     */
    public static void sort(List list, Comparator c) {
    Object a[] = list.toArray();
    Arrays.sort(a, c);
    ListIterator i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set(a[j]);
    }
    }


    /**
     * Searches the specified List for the specified Object using the binary
     * search algorithm.  The List must be sorted into ascending order
     * according to the <i>natural comparison method</i> of its elements (as by
     * Sort(List), above) prior to making this call.  If it is not sorted,
     * the results are undefined: in particular, the call may enter an infinite
     * loop.  If the List contains multiple elements equal to the specified
     * Object, there is no guarantee which instance will be found.
     *<p>
     * This method will run in log(n) time for a "random access" List (which
     * provides near-constant-time positional access) like a Vector.  It may
     * run in n*log(n) time if it is called on a "sequential access" List
     * (which provides linear-time positional access).  If the specified List
     * is an instanceof AbstracSequentialList, this method will do a
     * sequential search instead of a binary search; this offers linear
     * performance instead of n*log(n) performance if this method is called on
     * a LinkedList.
     *
     * @param      list the List to be searched.
     * @param      key the key to be searched for.
     * @return index of the search key, if it is contained in the List;
     *           otherwise, (-(<i>insertion point</i>) - 1).  The <i>insertion
     *           point</i> is defined as the the point at which the value would
     *            be inserted into the List: the index of the first element
     *           greater than the value, or list.size(), if all elements in
     *           the List are less than the specified value.  Note that this
     *           guarantees that the return value will be >= 0 if and only
     *           if the Object is found.
     * @exception ClassCastException List contains elements that are not
     *          <i>mutually comparable</i> (for example, Strings and
     *          Integers), or the search key in not mutually comparable
     *          with the elements of the List.
     * @see Comparable
     * @see #sort(List)
     */
    public static int binarySearch(List list, Object key) {
    // Do a sequential search if appropriate
    if (list instanceof AbstractSequentialList) {
        ListIterator i = list.listIterator();
        while (i.hasNext()) {
        int cmp = ((Comparable)(i.next())).compareTo(key);
        if (cmp == 0)
            return i.previousIndex();
        else if (cmp > 0)
            return -i.nextIndex();  // key not found.
        }
        return -i.nextIndex();  // key not found, list exhausted
    }

    // Otherwise, do a binary search
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid =(low + high)/2;
        Object midVal = list.get(mid);
        int cmp = ((Comparable)midVal).compareTo(key);

        if (cmp < 0)
        low = mid + 1;
        else if (cmp > 0)
        high = mid - 1;
        else
        return mid; // key found
    }
    return -(low + 1);  // key not found
    }

    /**
     * Searches the specified List for the specified Object using the binary
     * search algorithm.  The List must be sorted into ascending order
     * according to the specified Comparator (as by Sort(List, Comparator),
     * above), prior to making this call.
     *<p>
     * This method will run in log(n) time for a "random access" List (which
     * provides near-constant-time positional access) like a Vector.  It may
     * run in n*log(n) time if it is called on a "sequential access" List
     * (which provides linear-time positional access).  If the specified List
     * is an instanceof AbstracSequentialList, this method will do a
     * sequential search instead of a binary search; this offers linear
     * performance instead of n*log(n) performance if this method is called on
     * a LinkedList.
     *
     * @param      list the List to be searched.
     * @param      key the key to be searched for.
     * @return index of the search key, if it is contained in the List;
     *           otherwise, (-(<i>insertion point</i>) - 1).  The <i>insertion
     *           point</i> is defined as the the point at which the value would
     *            be inserted into the List: the index of the first element
     *           greater than the value, or list.size(), if all elements in
     *           the List are less than the specified value.  Note that this
     *           guarantees that the return value will be >= 0 if and only
     *           if the Object is found.
     * @exception ClassCastException List contains elements that are not
     *          <i>mutually comparable</i> with the specified Comparator,
     *          or the search key in not mutually comparable with the
     *          elements of the List using this Comparator.
     * @see Comparable
     * @see #sort(List, Comparator)
     */
    public static int binarySearch(List list, Object key, Comparator c) {
    // Do a sequential search if appropriate
    if (list instanceof AbstractSequentialList) {
        ListIterator i = list.listIterator();
        while (i.hasNext()) {
        int cmp = c.compare(i.next(), key);
        if (cmp == 0)
            return i.previousIndex();
        else if (cmp > 0)
            return -i.nextIndex();  // key not found.
        }
        return -i.nextIndex();  // key not found, list exhausted
    }

    // Otherwise, do a binary search
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid =(low + high)/2;
        Object midVal = list.get(mid);
        int cmp = c.compare(midVal, key);

        if (cmp < 0)
        low = mid + 1;
        else if (cmp > 0)
        high = mid - 1;
        else
        return mid; // key found
    }
    return -(low + 1);  // key not found
    }

    /**
     * Returns the minimum element of the given Collection, according
     * to the <i>natural comparison method</i> of its elements.  All
     * elements in the Collection must implement the Comparable interface.
     * Furthermore, all elements in the Collection must be <i>mutually
     * comparable</i> (that is, e1.compareTo(e2) must not throw a
     * typeMismatchException for any elements e1 and e2 in the Collection).
     * <p>
     * This method iterates over the entire Collection, hence it requires
     * time proportional to the size of the Collection.
     *
     * @param coll the collection whose minimum element is to be determined.
     * @exception ClassCastException Collection contains elements that are not
     *          <i>mutually comparable</i> (for example, Strings and
     *          Integers).
     * @exception NoSuchElementException Collection is empty.
     *
     * @see Comparable
     */
    public static Object min(Collection coll) {
    Iterator i = coll.iterator();
    Comparable candidate = (Comparable)(i.next());
    while (i.hasNext()) {
        Comparable next = (Comparable)(i.next());
        if (next.compareTo(candidate) < 0)
        candidate = next;
    }
    return candidate;
    }

    /**
     * Returns the minimum element of the given Collection, according to the
     * order induced by the specified Comparator.  All elements in the
     * Collection must be <i>mutually comparable</i> by the specified
     * comparator (that is, comparator.compare(e1, e2) must not throw a
     * typeMismatchException for any elements e1 and e2 in the Collection).
     * <p>
     * This method iterates over the entire Collection, hence it requires
     * time proportional to the size of the Collection.
     *
     * @param coll the collection whose minimum element is to be determined.
     * @exception ClassCastException Collection contains elements that are not
     *          <i>mutually comparable</i> with the specified Comparator.
     * @exception NoSuchElementException Collection is empty.
     *
     * @see Comparable
     */
    public static Object min(Collection coll, Comparator comp) {
    Iterator i = coll.iterator();
    Object candidate = i.next();
    while (i.hasNext()) {
        Object next = i.next();
        if (comp.compare(next, candidate) < 0)
        candidate = next;
    }
    return candidate;
    }

    /**
     * Returns the maximum element of the given Collection, according
     * to the <i>natural comparison method</i> of its elements.  All
     * elements in the Collection must implement the Comparable interface.
     * Furthermore, all elements in the Collection must be <i>mutually
     * comparable</i> (that is, e1.compareTo(e2) must not throw a
     * typeMismatchException for any elements e1 and e2 in the Collection).
     * <p>
     * This method iterates over the entire Collection, hence it requires
     * time proportional to the size of the Collection.
     *
     * @param coll the collection whose maximum element is to be determined.
     * @exception ClassCastException Collection contains elements that are not
     *          <i>mutually comparable</i> (for example, Strings and
     *          Integers).
     * @exception NoSuchElementException Collection is empty.
     *
     * @see Comparable
     */
    public static Object max(Collection coll) {
    Iterator i = coll.iterator();
    Comparable candidate = (Comparable)(i.next());
    while (i.hasNext()) {
        Comparable next = (Comparable)(i.next());
        if (next.compareTo(candidate) > 0)
        candidate = next;
    }
    return candidate;
    }


    /**
     * Returns the maximum element of the given Collection, according to the
     * order induced by the specified Comparator.  All elements in the
     * Collection must be <i>mutually comparable</i> by the specified
     * comparator (that is, comparator.compare(e1, e2) must not throw a
     * typeMismatchException for any elements e1 and e2 in the Collection).
     * <p>
     * This method iterates over the entire Collection, hence it requires
     * time proportional to the size of the Collection.
     *
     * @param coll the collection whose maximum element is to be determined.
     * @exception ClassCastException Collection contains elements that are not
     *          <i>mutually comparable</i> with the specified Comparator.
     * @exception NoSuchElementException Collection is empty.
     *
     * @see Comparable
     */
    public static Object max(Collection coll, Comparator comp) {
    Iterator i = coll.iterator();
    Object candidate = i.next();
    while (i.hasNext()) {
        Object next = i.next();
        if (comp.compare(next, candidate) > 0)
        candidate = next;
    }
    return candidate;
    }

    // List Views

    /**
     * Returns a List backed by the specified List that represents the portion
     * of the specified List whose index ranges from fromIndex (inclusive) to
     * toIndex (exclusive).  The returned List is not resizable.  (Its size
     * is fixed at (toIndex - fromIndex).)  The returned List is mutable iff
     * the specified List is mutable.  Changes to the returned List "write
     * through" to the specified List, and vice-versa.
     * <p>
     * If the caller wants a List that is independent of the input List,
     * and free of the restrictions noted above, he should immediately
     * copy the returned List into a new List, for example:
     * <pre>
     *     Vector v = new Vector(Collections.subList(myList, 17, 42));
     * </pre>
     *
     * @param list the List whose subList is to be returned.
     * @param fromIndex the index (in this List) of the first element to
     *          appear in the subList.
     * @param toIndex the index (in this List) following the last element to
     *          appear in the subList.
     * @exception IndexOutOfBoundsException fromIndex or toIndex is out
     *          of range (fromIndex < 0 || fromIndex > size ||
     *          toIndex < 0 || toIndex > size).
     * @exception IllegalArgumentException fromIndex > toIndex.
     */
    public static List subList(List list, int fromIndex, int toIndex) {
    return new SubList(list, fromIndex, toIndex);
    }

    /**
     * SubList - Implements a SubList view backed by an arbitrary List.
     */
    static class SubList extends AbstractList {
    private List backer;
    private int offset;
    private int size;

    SubList(List list, int fromIndex, int toIndex) {
        backer = list;
        offset = fromIndex;
        size = toIndex - fromIndex;

        if (size<0)
        throw new IllegalArgumentException("fromIndex < toIndex");

        int backerSize = backer.size();
        if (fromIndex < 0 || fromIndex > backerSize ||
        toIndex   < 0 || toIndex   > backerSize)
        throw new IndexOutOfBoundsException();
    }

    public int size() {
        return size;
    }

    public Iterator iterator() {
        return listIterator();
    }

    public Object get(int index) {
        rangeCheck(index);
        return backer.get(index + offset);
    }

    public Object set(int index, Object element) {
        rangeCheck(index);
        return backer.set(index + offset, element);
    }

    public int indexOf(Object o, int index) {
        rangeCheck(index);
        ListIterator i = backer.listIterator(index + offset);

        if (o==null) {
        for(int j=index; j<size; j++)
            if (i.next()==null)
            return i.previousIndex() - offset;
        } else {
        for(int j=index; j<size; j++)
            if (o.equals(i.next()))
            return i.previousIndex() - offset;
        }
        return -1;
    }

    public int lastIndexOf(Object o, int index) {
        rangeCheck(index);
        ListIterator i = backer.listIterator(index + offset + 1);

        if (o==null) {
        for(int j=index; j>=0; j--)
            if (i.previous()==null)
            return i.nextIndex() - offset;
        } else {
        for(int j=index; j>=0; j--)
            if (o.equals(i.previous()))
            return i.nextIndex() - offset;
        }
        return -1;
    }

    public ListIterator listIterator(final int index) {
        if (index<0 || index>size)
        throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: "+size);

        return new ListIterator() {
        private ListIterator i = backer.listIterator(index+offset);

        public boolean hasNext() {
            return nextIndex() < size;
        }

        public Object next() {
            if (hasNext())
            return i.next();
            else
            throw new NoSuchElementException();
        }

        public boolean hasPrevious() {
            return previousIndex() >= 0;
        }

        public Object previous() {
            if (hasPrevious())
            return i.previous();
            else
            throw new NoSuchElementException();
        }

        public int nextIndex() {
            return i.nextIndex() - offset;
        }

        public int previousIndex() {
            return i.previousIndex() - offset;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public void set(Object o) {
            i.set(o);
        }

        public void add(Object o) {
            throw new UnsupportedOperationException();
        }
        };
    }

    private void rangeCheck(int index) {
        if (index<0 || index>=size)
        throw new IndexOutOfBoundsException("Index: "+index+
                            ",Size: "+size);
    }
    }


    // Unmodifiable Wrappers

    /**
     * Returns an unmodifiable view of the specified Collection.  This method
     * allows modules to provide users with "read-only" access to internal
     * Collections. Query operations on the returned Collection "read through"
     * to the specified Collection, and attempts to modify the returned
     * Collection, whether direct or via its Iterator, result in an
     * UnsupportedOperationException.
     * <p>
     * The returned Collection does <em>not</em> pass the hashCode and
     * equals operations through to the backing Collection, but relies
     * on Object's equals and hashCode methods.  This is necessary to
     * preserve the contracts of these operations in the case that the
     * backing Collection is a Set or a List.
     * <p>
     * The returned Collection will be Serializable if the specified Collection
     * is Serializable.
     *
     * @param c the Collection for which an unmodifiable view is to be
     *        returned.
     */
    public static Collection unmodifiableCollection(Collection c) {
    return new UnmodifiableCollection(c);
    }

    static class UnmodifiableCollection implements Collection, Serializable {
    private Collection c;

    UnmodifiableCollection(Collection c) {this.c = c;}

    public int size()             {return c.size();}
    public boolean isEmpty()         {return c.isEmpty();}
    public boolean contains(Object o)   {return c.contains(o);}
    public Object[] toArray()         {return c.toArray();}
    public Object[] toArray(Object[] a) {return c.toArray(a);}

    public Iterator iterator() {
        return new Iterator() {
        Iterator i = c.iterator();

        public boolean hasNext() {return i.hasNext();}
        public Object next()      {return i.next();}
        public void remove() {
            throw new UnsupportedOperationException();
                }
        };
        }

    public boolean add(Object o){
        throw new UnsupportedOperationException();
        }
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
        }

    public boolean containsAll(Collection coll) {
        return c.containsAll(coll);
        }
    public boolean addAll(Collection coll) {
        throw new UnsupportedOperationException();
        }
    public boolean removeAll(Collection coll) {
        throw new UnsupportedOperationException();
        }
    public boolean retainAll(Collection coll) {
        throw new UnsupportedOperationException();
        }
    public void clear() {
        throw new UnsupportedOperationException();
        }
    }

    /**
     * Returns an unmodifiable view of the specified Set.  This method allows
     * modules to provide users with "read-only" access to internal
     * Sets. Query operations on the returned Set "read through" to the
     * specified Set, and attempts to modify the returned Set, whether direct
     * or via its Iterator, result in an UnsupportedOperationException.
     * <p>
     * The returned Set will be Serializable if the specified Set
     * is Serializable.
     *
     * @param s the Set for which an unmodifiable view is to be returned.
     */

    public static Set unmodifiableSet(Set s) {
    return new UnmodifiableSet(s);
    }

    static class UnmodifiableSet extends UnmodifiableCollection
                     implements Set, Serializable {
    UnmodifiableSet(Set s)         {super(s);}

    public boolean equals(Object o) {return c.equals(o);}
    public int hashCode()         {return c.hashCode();}
    }

    /**
     * Returns an unmodifiable view of the specified SortedSet.  This method
     * allows modules to provide users with "read-only" access to internal
     * SortedSets.  Query operations on the returned SortedSet "read through"
     * to the specified SortedSet.  Attempts to modify the returned
     * SortedSet, whether direct, via its Iterator, or via its subSet,
     * headSet, or tailSet views, result in an UnsupportedOperationException.
     *<p>
     * The returned SortedSet will be Serializable if the specified SortedSet
     * is Serializable.
     *
     * @param s the SortedSet for which an unmodifiable view is to be returned.
     */
    public static SortedSet unmodifiableSortedSet(SortedSet s) {
    return new UnmodifiableSortedSet(s);
    }

    static class UnmodifiableSortedSet extends UnmodifiableSet
                     implements SortedSet, Serializable {
        private SortedSet ss;

    UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;}

        public Comparator comparator()     {return ss.comparator();}

        public SortedSet subSet(Object fromElement, Object toElement) {
            return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement));
        }
        public SortedSet headSet(Object toElement) {
            return new UnmodifiableSortedSet(ss.headSet(toElement));
        }
        public SortedSet tailSet(Object fromElement) {
            return new UnmodifiableSortedSet(ss.tailSet(fromElement));
        }

        public Object first()                {return ss.first();}
        public Object last()                 {return ss.last();}
    }

    /**
     * Returns an unmodifiable view of the specified List.  This method allows
     * modules to provide users with "read-only" access to internal
     * Lists. Query operations on the returned List "read through" to the
     * specified List, and attempts to modify the returned List, whether direct
     * or via its Iterator, result in an UnsupportedOperationException.
     * <p>
     * The returned List will be Serializable if the specified List
     * is Serializable.
     *
     * @param list the List for which an unmodifiable view is to be returned.
     */

    public static List unmodifiableList(List list) {
    return new UnmodifiableList(list);
    }

    static class UnmodifiableList extends UnmodifiableCollection
                      implements List {
    private List list;

    UnmodifiableList(List list) {
        super(list);
        this.list = list;
    }

    public boolean equals(Object o) {return list.equals(o);}
    public int hashCode()         {return list.hashCode();}

    public Object get(int index) {return list.get(index);}
    public Object set(int index, Object element) {
        throw new UnsupportedOperationException();
        }
    public void add(int index, Object element) {
        throw new UnsupportedOperationException();
        }
    public Object remove(int index) {
        throw new UnsupportedOperationException();
        }
    public int indexOf(Object o)            {return list.indexOf(o);}
    public int indexOf(Object o, int i)     {return list.indexOf(o, i);}
    public int lastIndexOf(Object o)        {return list.lastIndexOf(o);}
    public int lastIndexOf(Object o, int i) {return list.lastIndexOf(o,i);}
    public void removeRange(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException();
        }
    public boolean addAll(int index, Collection c) {
        throw new UnsupportedOperationException();
        }
    public ListIterator listIterator()     {return listIterator(0);}

    public ListIterator listIterator(final int index) {
        return new ListIterator() {
        ListIterator i = list.listIterator(index);

        public boolean hasNext()     {return i.hasNext();}
        public Object next()         {return i.next();}
        public boolean hasPrevious() {return i.hasPrevious();}
        public Object previous()     {return i.previous();}
        public int nextIndex()       {return i.nextIndex();}
        public int previousIndex()   {return i.previousIndex();}

        public void remove() {
            throw new UnsupportedOperationException();
                }
        public void set(Object o) {
            throw new UnsupportedOperationException();
                }
        public void add(Object o) {
            throw new UnsupportedOperationException();
                }
        };
    }
    }

    /**
     * Returns an unmodifiable view of the specified Map.  This method
     * allows modules to provide users with "read-only" access to internal
     * Maps. Query operations on the returned Map "read through"
     * to the specified Map, and attempts to modify the returned
     * Map, whether direct or via its Collection views, result in an
     * UnsupportedOperationException.
     * <p>
     * The returned Map will be Serializable if the specified Map
     * is Serializable.
     *
     * @param m the Map for which an unmodifiable view is to be returned.
     */
    public static Map unmodifiableMap(Map m) {
    return new UnmodifiableMap(m);
    }

    private static class UnmodifiableMap implements Map, Serializable {
    private final Map m;

    UnmodifiableMap(Map m)                  {this.m = m;}

    public int size()                  {return m.size();}
    public boolean isEmpty()              {return m.isEmpty();}
    public boolean containsKey(Object key)   {return m.containsKey(key);}
    public boolean containsValue(Object val) {return m.containsValue(val);}
    public Object get(Object key)              {return m.get(key);}

    public Object put(Object key, Object value) {
        throw new UnsupportedOperationException();
        }
    public Object remove(Object key) {
        throw new UnsupportedOperationException();
        }
    public void putAll(Map t) {
        throw new UnsupportedOperationException();
        }
    public void clear() {
        throw new UnsupportedOperationException();
        }

    private transient Set keySet = null;
    private transient Set entries = null;
    private transient Collection values = null;

    public Set keySet() {
        if (keySet==null)
        keySet = unmodifiableSet(m.keySet());
        return keySet;
    }

    public Set entries() {
        if (entries==null)
        entries = unmodifiableSet(m.entries());
        return entries;
    }

    public Collection values() {
        if (values==null)
        values = unmodifiableCollection(m.values());
        return values;
    }

    public boolean equals(Object o) {return m.equals(o);}
    public int hashCode()           {return m.hashCode();}
    }

    /**
     * Returns an unmodifiable view of the specified SortedMap.  This method
     * allows modules to provide users with "read-only" access to internal
     * SortedMaps. Query operations on the returned SortedMap "read through"
     * to the specified SortedMap.  Attempts to modify the returned
     * SortedMap, whether direct, via its Collection views, or via its
     * subMap, headMap, or tailMap views, result in an
     * UnsupportedOperationException.
     * <p>
     * The returned SortedMap will be Serializable if the specified SortedMap
     * is Serializable.
     *
     * @param m the SortedMap for which an unmodifiable view is to be returned.
     */
    public static SortedMap unmodifiableSortedMap(SortedMap m) {
    return new UnmodifiableSortedMap(m);
    }

    static class UnmodifiableSortedMap extends UnmodifiableMap
                     implements SortedMap, Serializable {
        private SortedMap sm;

    UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;}

        public Comparator comparator()     {return sm.comparator();}

        public SortedMap subMap(Object fromKey, Object toKey) {
            return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
        }
        public SortedMap headMap(Object toKey) {
            return new UnmodifiableSortedMap(sm.headMap(toKey));
        }
        public SortedMap tailMap(Object fromKey) {
            return new UnmodifiableSortedMap(sm.tailMap(fromKey));
        }

        public Object firstKey()           {return sm.firstKey();}
        public Object lastKey()            {return sm.lastKey();}
    }


    // Synch Wrappers

    /**
     * Returns a synchronized (thread-safe) Collection backed by the specified
     * Collection. In order to guarantee serial access, it is critical that
     * <strong>all</strong> access to the backing Collection is accomplished
     * through the returned Collection.
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * Collection when iterating over it:
     * <pre>
     *  Collection c = synchronizedCollection(myCollection);
     *     ...
     *  synchronized(c) {
     *      Iterator i = c.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *         foo(i.next();
     *  }
     * </pre>
     * Failure to follow this advice may result in non-deterministic behavior.
     * <p>
     * The returned Collection does <em>not</em> pass the hashCode and
     * equals operations through to the backing Collection, but relies
     * on Object's equals and hashCode methods.  This is necessary to
     * preserve the contracts of these operations in the case that the
     * backing Collection is a Set or a List.
     * <p>
     * The returned Collection will be Serializable if the specified Collection
     * is Serializable.
     *
     * @param c the Collection to be "wrapped" in a synchronized Collection.
     */
    public static Collection synchronizedCollection(Collection c) {
    return new SynchronizedCollection(c);
    }

    static class SynchronizedCollection implements Collection, Serializable {
    private Collection c;       // Backing Collection
    private Object       mutex;  // Object on which to synchronize

    SynchronizedCollection(Collection c) {
        this.c = c; mutex = this;
        }
    SynchronizedCollection(Collection c, Object mutex) {
        this.c = c; this.mutex = mutex;
        }

    public int size() {
        synchronized(mutex) {return c.size();}
        }
    public boolean isEmpty() {
        synchronized(mutex) {return c.isEmpty();}
        }
    public boolean contains(Object o) {
        synchronized(mutex) {return c.contains(o);}
        }
    public Object[] toArray() {
        synchronized(mutex) {return c.toArray();}
        }
    public Object[] toArray(Object[] a) {
        synchronized(mutex) {return c.toArray(a);}
        }

    public Iterator iterator() {
            return c.iterator(); // Must be manually synched by user!
        }

    public boolean add(Object o) {
        synchronized(mutex) {return c.add(o);}
        }
    public boolean remove(Object o) {
        synchronized(mutex) {return c.remove(o);}
        }

    public boolean containsAll(Collection coll) {
        synchronized(mutex) {return c.containsAll(coll);}
        }
    public boolean addAll(Collection coll) {
        synchronized(mutex) {return c.addAll(coll);}
        }
    public boolean removeAll(Collection coll) {
        synchronized(mutex) {return c.removeAll(coll);}
        }
    public boolean retainAll(Collection coll) {
        synchronized(mutex) {return c.retainAll(coll);}
        }
    public void clear() {
        synchronized(mutex) {c.clear();}
        }
    }

    /**
     * Returns a synchronized (thread-safe) Set backed by the specified
     * Set. In order to guarantee serial access, it is critical that
     * <strong>all</strong> access to the backing Set is accomplished
     * through the returned Set.
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * Set when iterating over it:
     * <pre>
     *  Set s = synchronizedSet(new HashSet());
     *      ...
     *  synchronized(s) {
     *      Iterator i = s.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * Failure to follow this advice may result in non-deterministic behavior.
     * <p>
     * The returned Set will be Serializable if the specified Set is
     * Serializable.
     *
     * @param s the Set to be "wrapped" in a synchronized Set.
     */
    public static Set synchronizedSet(Set s) {
    return new SynchronizedSet(s);
    }

    static class SynchronizedSet extends SynchronizedCollection
                     implements Set {
    SynchronizedSet(Set s) {
            super(s);
        }
    SynchronizedSet(Set s, Object mutex) {
            super(s, mutex);
        }

    public boolean equals(Object o) {
        synchronized(mutex) {return c.equals(o);}
        }
    public int hashCode() {
        synchronized(mutex) {return c.hashCode();}
        }
    }

    /**
     * Returns a synchronized (thread-safe) SortedSet backed by the specified
     * SortedSet. In order to guarantee serial access, it is critical that
     * <strong>all</strong> access to the backing SortedSet is accomplished
     * through the returned SortedSet (or its views).
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * SortedSet when iterating over it or any of its subSet, headSet, or
     * tailSet views.
     * <pre>
     *  SortedSet s = synchronizedSortedSet(new HashSortedSet());
     *      ...
     *  synchronized(s) {
     *      Iterator i = s.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * or:
     * <pre>
     *  SortedSet s = synchronizedSortedSet(new HashSortedSet());
     *  SortedSet s2 = s.headSet(foo);
     *      ...
     *  synchronized(s) {  // Note: s, not s2!!!
     *      Iterator i = s2.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * Failure to follow this advice may result in non-deterministic behavior.
     * <p>
     * The returned SortedSet will be Serializable if the specified SortedSet
     * is Serializable.
     *
     * @param s the SortedSet to be "wrapped" in a synchronized SortedSet.
     */
    public static SortedSet synchronizedSortedSet(SortedSet s) {
    return new SynchronizedSortedSet(s);
    }

    static class SynchronizedSortedSet extends SynchronizedSet
                     implements SortedSet
    {
        private SortedSet ss;

    SynchronizedSortedSet(SortedSet s) {
            super(s);
            ss = s;
        }
    SynchronizedSortedSet(SortedSet s, Object mutex) {
            super(s, mutex);
            ss = s;
        }

    public Comparator comparator() {
        synchronized(mutex) {return ss.comparator();}
        }

        public SortedSet subSet(Object fromElement, Object toElement) {
        synchronized(mutex) {
                return new SynchronizedSortedSet(
                    ss.subSet(fromElement, toElement), mutex);
            }
        }
        public SortedSet headSet(Object toElement) {
        synchronized(mutex) {
                return new SynchronizedSortedSet(ss.headSet(toElement), mutex);
            }
        }
        public SortedSet tailSet(Object fromElement) {
        synchronized(mutex) {
               return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex);
            }
        }

        public Object first() {
        synchronized(mutex) {return ss.first();}
        }
        public Object last() {
        synchronized(mutex) {return ss.last();}
        }
    }

    /**
     * Returns a synchronized (thread-safe) List backed by the specified
     * List. In order to guarantee serial access, it is critical that
     * <strong>all</strong> access to the backing List is accomplished
     * through the returned List.
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * List when iterating over it:
     * <pre>
     *  List list = synchronizedList(new Arraylist());
     *      ...
     *  synchronized(list) {
     *      Iterator i = list.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * Failure to follow this advice may result in non-deterministic behavior.
     * <p>
     * The returned List will be Serializable if the specified List is
     * Serializable.
     *
     * @param list the List to be "wrapped" in a synchronized List.
     */
    public static List synchronizedList(List list) {
    return new SynchronizedList(list);
    }

    static class SynchronizedList extends SynchronizedCollection
                          implements List {
    private List list;

    SynchronizedList(List list) {
        super(list);
        this.list = list;
    }

    public boolean equals(Object o) {
        synchronized(mutex) {return list.equals(o);}
        }
    public int hashCode() {
        synchronized(mutex) {return list.hashCode();}
        }

    public Object get(int index) {
        synchronized(mutex) {return list.get(index);}
        }
    public Object set(int index, Object element) {
        synchronized(mutex) {return list.set(index, element);}
        }
    public void add(int index, Object element) {
        synchronized(mutex) {list.add(index, element);}
        }
    public Object remove(int index) {
        synchronized(mutex) {return list.remove(index);}
        }

    public int indexOf(Object o) {
        synchronized(mutex) {return list.indexOf(o);}
        }
    public int indexOf(Object o, int i) {
        synchronized(mutex) {return list.indexOf(o, i);}
        }
    public int lastIndexOf(Object o) {
        synchronized(mutex) {return list.lastIndexOf(o);}
        }
    public int lastIndexOf(Object o, int i) {
        synchronized(mutex) {return list.lastIndexOf(o,i);}
        }

    public void removeRange(int fromIndex, int toIndex) {
        synchronized(mutex) {list.removeRange(fromIndex, toIndex);}
        }
    public boolean addAll(int index, Collection c) {
        synchronized(mutex) {return list.addAll(index, c);}
        }

    public ListIterator listIterator() {
        return list.listIterator(); // Must be manually synched by user
        }

    public ListIterator listIterator(int index) {
        return list.listIterator(index); // Must be manually synched by usr
        }
    }

    /**
     * Returns a synchronized (thread-safe) Map backed by the specified
     * Map. In order to guarantee serial access, it is critical that
     * <strong>all</strong> access to the backing Map is accomplished
     * through the returned Map.
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * Map when iterating over any of its Collection views:
     * <pre>
     *  Map m = synchronizedMap(new HashMap());
     *      ...
     *  Set s = m.keySet();  // Needn't be in synchronized block
     *      ...
     *  synchronized(m) {  // Synchronizing on m, not s!
     *      Iterator i = s.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * Failure to follow this advice may result in non-deterministic behavior.
     * <p>
     * The returned Map will be Serializable if the specified Map is
     * Serializable.
     *
     * @param m the Map to be "wrapped" in a synchronized Map.
     */
    public static Map synchronizedMap(Map m) {
    return new SynchronizedMap(m);
    }

    private static class SynchronizedMap implements Map {
    private Map    m;    // Backing Map
        private Object mutex;    // Object on which to synchronize

    SynchronizedMap(Map m) {
            this.m = m;     mutex = this;
        }

    SynchronizedMap(Map m, Object mutex) {
            this.m = m;     this.mutex = mutex;
        }

    public int size() {
        synchronized(mutex) {return m.size();}
        }
    public boolean isEmpty(){
        synchronized(mutex) {return m.isEmpty();}
        }
    public boolean containsKey(Object key) {
        synchronized(mutex) {return m.containsKey(key);}
        }
    public boolean containsValue(Object value){
        synchronized(mutex) {return m.containsValue(value);}
        }
    public Object get(Object key) {
        synchronized(mutex) {return m.get(key);}
        }

    public Object put(Object key, Object value) {
        synchronized(mutex) {return m.put(key, value);}
        }
    public Object remove(Object key) {
        synchronized(mutex) {return m.remove(key);}
        }
    public void putAll(Map map) {
        synchronized(mutex) {m.putAll(map);}
        }
    public void clear() {
        synchronized(mutex) {m.clear();}
        }

    private transient Set keySet = null;
    private transient Set entries = null;
    private transient Collection values = null;

    public Set keySet() {
            synchronized(mutex) {
                if (keySet==null)
                    keySet = new SynchronizedSet(m.keySet(), this);
                return keySet;
            }
    }

    public Set entries() {
            synchronized(mutex) {
                if (entries==null)
                    entries = new SynchronizedSet(m.entries(), this);
                return entries;
            }
    }

    public Collection values() {
            synchronized(mutex) {
                if (values==null)
                    values = new SynchronizedCollection(m.values(), this);
                return values;
            }
        }

    public boolean equals(Object o) {
            synchronized(mutex) {return m.equals(o);}
        }
    public int hashCode() {
            synchronized(mutex) {return m.hashCode();}
        }
    }

    /**
     * Returns a synchronized (thread-safe) SortedMap backed by the specified
     * SortedMap. In order to guarantee serial access, it is critical that
     * <strong>all</strong> access to the backing SortedMap is accomplished
     * through the returned SortedMap (or its views).
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * SortedMap when iterating over any of its Collection views, or the
     * Collections views of any of its subMap, headMap or tailMap views.
     * <pre>
     *  SortedMap m = synchronizedSortedMap(new HashSortedMap());
     *      ...
     *  Set s = m.keySet();  // Needn't be in synchronized block
     *      ...
     *  synchronized(m) {  // Synchronizing on m, not s!
     *      Iterator i = s.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * or:
     * <pre>
     *  SortedMap m = synchronizedSortedMap(new HashSortedMap());
     *  SortedMap m2 = m.subMap(foo, bar);
     *      ...
     *  Set s2 = m2.keySet();  // Needn't be in synchronized block
     *      ...
     *  synchronized(m) {  // Synchronizing on m, not m2 or s2!
     *      Iterator i = s.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next();
     *  }
     * </pre>
     * Failure to follow this advice may result in non-deterministic behavior.
     * <p>
     * The returned SortedMap will be Serializable if the specified SortedMap
     * is  Serializable.
     *
     * @param m the SortedMap to be "wrapped" in a synchronized SortedMap.
     */
    public static SortedMap synchronizedSortedMap(SortedMap m) {
    return new SynchronizedSortedMap(m);
    }


    static class SynchronizedSortedMap extends SynchronizedMap
                     implements SortedMap
    {
        private SortedMap sm;

    SynchronizedSortedMap(SortedMap m) {
            super(m);
            sm = m;
        }
    SynchronizedSortedMap(SortedMap m, Object mutex) {
            super(m, mutex);
            sm = m;
        }

    public Comparator comparator() {
        synchronized(mutex) {return sm.comparator();}
        }

        public SortedMap subMap(Object fromKey, Object toKey) {
        synchronized(mutex) {
                return new SynchronizedSortedMap(
                    sm.subMap(fromKey, toKey), mutex);
            }
        }
        public SortedMap headMap(Object toKey) {
        synchronized(mutex) {
                return new SynchronizedSortedMap(sm.headMap(toKey), mutex);
            }
        }
        public SortedMap tailMap(Object fromKey) {
        synchronized(mutex) {
               return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex);
            }
        }

        public Object firstKey() {
        synchronized(mutex) {return sm.firstKey();}
        }
        public Object lastKey() {
        synchronized(mutex) {return sm.lastKey();}
        }
    }

    // Miscellaneous

    /**
     * Returns an immutable List consisting of n copies of the specified
     * Object.  The newly allocated data Object is tiny (it contains a single
     * reference to the data Object).  This method is useful in combination
     * with List.addAll to grow Lists.
     *
     * @param n the number of elements in the returned List.
     * @param o the element to appear repeatedly in the returned List.
     * @exception IllegalArgumentException n < 0.
     * @see List#addAll(Collection)
     * @see List#addAll(int, Collection)
     */
    public static List nCopies(final int n, final Object o) {
    if (n < 0)
        throw new IllegalArgumentException("List length = " + n);

    return new AbstractList() {
        public int size() {
        return n;
        }

        public boolean contains(Object obj) {
        return n!=0 && o.equals(obj);
        }

        public Object get(int index) {
        if (index<0 || index>n)
            throw new IndexOutOfBoundsException("Index: "+index+
                            ",Size: "+n);
        return o;
        }
        };
    }

    /**
     * A Comparator that imposes the reverse of the <em>natural ordering</em>
     * on a collection of Comparable objects.  (The natural ordering is the
     * ordering imposed by the objects' own compareTo method.)  This
     * enables a simple idiom for sorting (or maintaining) collections
     * (or arrays) of Comparable objects in reverse-natural-order.  For
     * example, suppose a is an array of String. Then: <pre>
     *         Arrays.sort(a, Collections.REVERSE_ORDER);
     * </pre> sorts the array in reverse-lexicographic (alphabetical) order.
     * <p>
     * This Comparator is Serializable.
     */
    public static final Comparator REVERSE_ORDER = new ReverseComparator();

    private static class ReverseComparator implements Comparator,Serializable {
        public int compare(Object o1, Object o2) {
            Comparable c1 = (Comparable)o1;
            Comparable c2 = (Comparable)o2;
            return -c1.compareTo(c2);
        }
    }

    /**
     * Returns an Enumeration over the specified Collection.  This provides
     * interoperatbility with legacy APIs that require an Enumeration
     * as input.
     *
     * @param c the Collection for which an Enumeration is to be returned.
     */
    public static Enumeration enumeration(final Collection c) {
    return new Enumeration() {
        Iterator i = c.iterator();

        public boolean hasMoreElements() {
        return i.hasNext();
        }

        public Object nextElement() {
        return i.next();
        }
        };
    }
}