home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / util / Collections.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  59.6 KB  |  1,663 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)Collections.java    1.32 98/11/05
  3.  *
  4.  * Copyright 1997, 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16. import java.io.Serializable;
  17.  
  18. /**
  19.  * This class consists exclusively of static methods that operate on or return
  20.  * collections.  It contains polymorphic algorithms that operate on
  21.  * collections, "wrappers", which return a new collection backed by a
  22.  * specified collection, and a few other odds and ends.<p>
  23.  *
  24.  * The documentation for the polymorphic algorithms contained in this class
  25.  * generally includes a brief description of the <i>implementation</i>.  Such
  26.  * descriptions should be regarded as <i>implementation notes</i>, rather than
  27.  * parts of the <i>specification</i>.  Implementors should feel free to
  28.  * substitute other algorithms, so long as the specification itself is adhered
  29.  * to.  (For example, the algorithm used by <tt>sort</tt> does not have to be
  30.  * a mergesort, but it does have to be <i>stable</i>.)
  31.  *
  32.  * @author  Josh Bloch
  33.  * @version 1.32 11/05/98
  34.  * @see        Collection
  35.  * @see        Set
  36.  * @see        List
  37.  * @see        Map
  38.  * @since JDK1.2
  39.  */
  40.  
  41. public class Collections {
  42.     // Suppresses default constructor, ensuring non-instantiability.
  43.     private Collections() {
  44.     }
  45.  
  46.     // Algorithms
  47.  
  48.     /**
  49.      * Sorts the specified list into ascending order, according to the
  50.      * <i>natural ordering</i> of its elements.  All elements in the list must
  51.      * implement the <tt>Comparable</tt> interface.  Furthermore, all elements
  52.      * in the list must be <i>mutually comparable</i> (that is,
  53.      * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
  54.      * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
  55.      *
  56.      * This sort is guaranteed to be <i>stable</i>:  equal elements will
  57.      * not be reordered as a result of the sort.<p>
  58.      *
  59.      * The specified list must be modifiable, but need not be resizable.<p>
  60.      *
  61.      * The sorting algorithm is a modified mergesort (in which the merge is
  62.      * omitted if the highest element in the low sublist is less than the
  63.      * lowest element in the high sublist).  This algorithm offers guaranteed
  64.      * n log(n) performance, and can approach linear performance on nearly
  65.      * sorted lists.<p>
  66.      *
  67.      * This implementation dumps the specified list into an array, sorts
  68.      * the array, and iterates over the list resetting each element
  69.      * from the corresponding position in the array.  This avoids the
  70.      * n<sup>2</sup> log(n) performance that would result from attempting
  71.      * to sort a linked list in place.
  72.      *
  73.      * @param  list the list to be sorted.
  74.      * @throws ClassCastException if the list contains elements that are not
  75.      *           <i>mutually comparable</i> (for example, strings and integers).
  76.      * @throws UnsupportedOperationException if the specified list's
  77.      *           list-iterator does not support the <tt>set</tt> operation.
  78.      * @see Comparable
  79.      */
  80.     public static void sort(List list) {
  81.     Object a[] = list.toArray();
  82.     Arrays.sort(a);
  83.     ListIterator i = list.listIterator();
  84.     for (int j=0; j<a.length; j++) {
  85.         i.next();
  86.         i.set(a[j]);
  87.     }
  88.     }
  89.  
  90.     /**
  91.      * Sorts the specified list according to the order induced by the
  92.      * specified comparator.  All elements in the list must be <i>mutually
  93.      * comparable</i> using the specified comparator (that is,
  94.      * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
  95.      * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
  96.      *
  97.      * This sort is guaranteed to be <i>stable</i>:  equal elements will
  98.      * not be reordered as a result of the sort.<p>
  99.      *
  100.      * The sorting algorithm is a modified mergesort (in which the merge is
  101.      * omitted if the highest element in the low sublist is less than the
  102.      * lowest element in the high sublist).  This algorithm offers guaranteed
  103.      * n log(n) performance, and can approach linear performance on nearly
  104.      * sorted lists.<p>
  105.      *
  106.      * The specified list must be modifiable, but need not be resizable.
  107.      * This implementation dumps the specified list into an array, sorts
  108.      * the array, and iterates over the list resetting each element
  109.      * from the corresponding position in the array.  This avoids the
  110.      * n<sup>2</sup> log(n) performance that would result from attempting
  111.      * to sort a linked list in place.
  112.      *
  113.      * @param  list the list to be sorted.
  114.      * @param  c the comparator to determine the order of the array.
  115.      * @throws ClassCastException if the list contains elements that are not
  116.      *           <i>mutually comparable</i> using the specified comparator.
  117.      * @throws UnsupportedOperationException if the specified list's
  118.      *           list-iterator does not support the <tt>set</tt> operation.
  119.      * @see Comparator
  120.      */
  121.     public static void sort(List list, Comparator c) {
  122.     Object a[] = list.toArray();
  123.     Arrays.sort(a, c);
  124.     ListIterator i = list.listIterator();
  125.     for (int j=0; j<a.length; j++) {
  126.         i.next();
  127.         i.set(a[j]);
  128.     }
  129.     }
  130.  
  131.  
  132.     /**
  133.      * Searches the specified list for the specified object using the binary
  134.      * search algorithm.  The list must be sorted into ascending order
  135.      * according to the <i>natural ordering</i> of its elements (as by the
  136.      * <tt>sort(List)</tt> method, above) prior to making this call.  If it is
  137.      * not sorted, the results are undefined.  If the list contains multiple
  138.      * elements equal to the specified object, there is no guarantee which one
  139.      * will be found.<p>
  140.      *
  141.      * This method runs in log(n) time for a "random access" list (which
  142.      * provides near-constant-time positional access).  It may
  143.      * run in n log(n) time if it is called on a "sequential access" list
  144.      * (which provides linear-time positional access).</p>
  145.      *
  146.      * If the specified list implements the <tt>AbstracSequentialList</tt>
  147.      * interface, this method will do a sequential search instead of a binary
  148.      * search; this offers linear performance instead of n log(n) performance
  149.      * if this method is called on a <tt>LinkedList</tt> object.
  150.      *
  151.      * @param  list the list to be searched.
  152.      * @param  key the key to be searched for.
  153.      * @return index of the search key, if it is contained in the list;
  154.      *           otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
  155.      *           <i>insertion point</i> is defined as the point at which the
  156.      *           key would be inserted into the list: the index of the first
  157.      *           element greater than the key, or <tt>list.size()</tt>, if all
  158.      *           elements in the list are less than the specified key.  Note
  159.      *           that this guarantees that the return value will be >= 0 if
  160.      *           and only if the key is found.
  161.      * @throws ClassCastException if the list contains elements that are not
  162.      *           <i>mutually comparable</i> (for example, strings and
  163.      *           integers), or the search key in not mutually comparable
  164.      *           with the elements of the list.
  165.      * @see    Comparable
  166.      * @see #sort(List)
  167.      */
  168.     public static int binarySearch(List list, Object key) {
  169.     // Do a sequential search if appropriate
  170.     if (list instanceof AbstractSequentialList) {
  171.         ListIterator i = list.listIterator();
  172.         while (i.hasNext()) {
  173.         int cmp = ((Comparable)(i.next())).compareTo(key);
  174.         if (cmp == 0)
  175.             return i.previousIndex();
  176.         else if (cmp > 0)
  177.             return -i.nextIndex();  // key not found.
  178.         }
  179.         return -i.nextIndex()-1;  // key not found, list exhausted
  180.     }
  181.  
  182.     // Otherwise, do a binary search
  183.     int low = 0;
  184.     int high = list.size()-1;
  185.  
  186.     while (low <= high) {
  187.         int mid =(low + high)/2;
  188.         Object midVal = list.get(mid);
  189.         int cmp = ((Comparable)midVal).compareTo(key);
  190.  
  191.         if (cmp < 0)
  192.         low = mid + 1;
  193.         else if (cmp > 0)
  194.         high = mid - 1;
  195.         else
  196.         return mid; // key found
  197.     }
  198.     return -(low + 1);  // key not found
  199.     }
  200.  
  201.     /**
  202.      * Searches the specified list for the specified object using the binary
  203.      * search algorithm.  The list must be sorted into ascending order
  204.      * according to the specified comparator (as by the <tt>Sort(List,
  205.      * Comparator)</tt> method, above), prior to making this call.  If it is
  206.      * not sorted, the results are undefined.  If the list contains multiple
  207.      * elements equal to the specified object, there is no guarantee which one
  208.      * will be found.<p>
  209.      *
  210.      * This method runs in log(n) time for a "random access" list (which
  211.      * provides near-constant-time positional access).  It may
  212.      * run in n log(n) time if it is called on a "sequential access" list
  213.      * (which provides linear-time positional access).</p>
  214.      *
  215.      * If the specified list implements the <tt>AbstracSequentialList</tt>
  216.      * interface, this method will do a sequential search instead of a binary
  217.      * search; this offers linear performance instead of n log(n) performance
  218.      * if this method is called on a <tt>LinkedList</tt> object.
  219.      *
  220.      * @param  list the list to be searched.
  221.      * @param  key the key to be searched for.
  222.      * @param  c the comparator by which the list is ordered.
  223.      * @return index of the search key, if it is contained in the list;
  224.      *           otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
  225.      *           <i>insertion point</i> is defined as the point at which the
  226.      *           key would be inserted into the list: the index of the first
  227.      *           element greater than the key, or <tt>list.size()</tt>, if all
  228.      *           elements in the list are less than the specified key.  Note
  229.      *           that this guarantees that the return value will be >= 0 if
  230.      *           and only if the key is found.
  231.      * @throws ClassCastException if the list contains elements that are not
  232.      *           <i>mutually comparable</i> using the specified comparator,
  233.      *           or the search key in not mutually comparable with the
  234.      *           elements of the list using this comparator.
  235.      * @see    Comparable
  236.      * @see #sort(List, Comparator)
  237.      */
  238.     public static int binarySearch(List list, Object key, Comparator c) {
  239.     // Do a sequential search if appropriate
  240.     if (list instanceof AbstractSequentialList) {
  241.         ListIterator i = list.listIterator();
  242.         while (i.hasNext()) {
  243.         int cmp = c.compare(i.next(), key);
  244.         if (cmp == 0)
  245.             return i.previousIndex();
  246.         else if (cmp > 0)
  247.             return -i.nextIndex();  // key not found.
  248.         }
  249.         return -i.nextIndex()-1;  // key not found, list exhausted
  250.     }
  251.  
  252.     // Otherwise, do a binary search
  253.     int low = 0;
  254.     int high = list.size()-1;
  255.  
  256.     while (low <= high) {
  257.         int mid =(low + high)/2;
  258.         Object midVal = list.get(mid);
  259.         int cmp = c.compare(midVal, key);
  260.  
  261.         if (cmp < 0)
  262.         low = mid + 1;
  263.         else if (cmp > 0)
  264.         high = mid - 1;
  265.         else
  266.         return mid; // key found
  267.     }
  268.     return -(low + 1);  // key not found
  269.     }
  270.  
  271.     /**
  272.      * Reverses the order of the elements in the specified list.<p>
  273.      *
  274.      * This method runs in linear time.
  275.      *
  276.      * @param  list the list whose elements are to be reversed.
  277.      * @throws UnsupportedOperationException if the specified list's
  278.      *           list-iterator does not support the <tt>set</tt> operation.
  279.      */
  280.     public static void reverse(List l) {
  281.         ListIterator fwd = l.listIterator(), rev = l.listIterator(l.size());
  282.         for (int i=0, n=l.size()/2; i<n; i++) {
  283.             Object tmp = fwd.next();
  284.             fwd.set(rev.previous());
  285.             rev.set(tmp);
  286.         }
  287.     }
  288.  
  289.     /**
  290.      * Randomly permutes the specified list using a default source of
  291.      * randomness.  All permutations occur with approximately equal
  292.      * likelihood.<p>
  293.      *
  294.      * The hedge "approximately" is used in the foregoing description because
  295.      * default source of randomenss is only approximately an unbiased source
  296.      * of independently chosen bits. If it were a perfect source of randomly
  297.      * chosen bits, then the algorithm would choose permutations with perfect
  298.      * uniformity.<p>
  299.      *
  300.      * This implementation traverses the list backwards, from the last element
  301.      * up to the second, repeatedly swapping a randomly selected element into
  302.      * the "current position".  Elements are randomly selected from the
  303.      * portion of the list that runs from the first element to the current
  304.      * position, inclusive.<p>
  305.      *
  306.      * This method runs in linear time for a "random access" list (which
  307.      * provides near-constant-time positional access).  It may require
  308.      * quadratic time for a "sequential access" list.
  309.      *
  310.      * @param  list the list to be shuffled.
  311.      * @throws UnsupportedOperationException if the specified list's
  312.      *         list-iterator does not support the <tt>set</tt> operation.
  313.      */
  314.     public static void shuffle(List list) {
  315.         shuffle(list, r);
  316.     }
  317.     private static Random r = new Random();
  318.  
  319.     /**
  320.      * Randomly permute the specified list using the specified source of
  321.      * randomness.  All permutations occur with equal likelihood
  322.      * assuming that the source of randomness is fair.<p>
  323.      *
  324.      * This implementation traverses the list backwards, from the last element
  325.      * up to the second, repeatedly swapping a randomly selected element into
  326.      * the "current position".  Elements are randomly selected from the
  327.      * portion of the list that runs from the first element to the current
  328.      * position, inclusive.<p>
  329.      *
  330.      * This method runs in linear time for a "random access" list (which
  331.      * provides near-constant-time positional access).  It may require
  332.      * quadratic time for a "sequential access" list.
  333.      *
  334.      * @param  list the list to be shuffled.
  335.      * @param  r the source of randomness to use to shuffle the list.
  336.      * @throws UnsupportedOperationException if the specified list's
  337.      *         list-iterator does not support the <tt>set</tt> operation.
  338.      */
  339.     public static void shuffle(List list, Random rnd) {
  340.         for (int i=list.size(); i>1; i--)
  341.             swap(list, i-1, rnd.nextInt(i));
  342.     }
  343.  
  344.     /**
  345.      * Swaps the two specified elements in the specified list.
  346.      */
  347.     private static void swap(List a, int i, int j) {
  348.         Object tmp = a.get(i);
  349.         a.set(i, a.get(j));
  350.         a.set(j, tmp);
  351.     }
  352.  
  353.     /**
  354.      * Replaces all of the elements of the specified list with the specified
  355.      * element. <p>
  356.      *
  357.      * This method runs in linear time.
  358.      *
  359.      * @param  list the list to be filled with the specified element.
  360.      * @param  o The element with which to fill the specified list.
  361.      * @throws UnsupportedOperationException if the specified list's
  362.      *           list-iterator does not support the <tt>set</tt> operation.
  363.      */
  364.     public static void fill(List list, Object o) {
  365.         for (ListIterator i = list.listIterator(); i.hasNext(); ) {
  366.             i.next();
  367.             i.set(o);
  368.         }
  369.     }
  370.  
  371.     /**
  372.      * Copies all of the elements from one list into another.  After the
  373.      * operation, the index of each copied element in the destination list
  374.      * will be identical to its index in the source list.  The destination
  375.      * list must be at least as long as the source list.  If it is longer, the
  376.      * remaining elements in the destination list are unaffected. <p>
  377.      *
  378.      * This method runs in linear time.
  379.      *
  380.      * @param  dest The destination list.
  381.      * @param  src The source list.
  382.      * @throws IndexOutOfBoundsException if the destination list is too small
  383.      *         to contain the entire source List.
  384.      * @throws UnsupportedOperationException if the destination list's
  385.      *         list-iterator does not support the <tt>set</tt> operation.
  386.      */
  387.     public static void copy (List dest, List src) {
  388.         try {
  389.         for (ListIterator di=dest.listIterator(), si=src.listIterator();
  390.          si.hasNext(); ) {
  391.                 di.next();
  392.                 di.set(si.next());
  393.             }
  394.     } catch(NoSuchElementException e) {
  395.            throw new IndexOutOfBoundsException("Source does not fit in dest.");
  396.         }
  397.     }
  398.  
  399.     /**
  400.      * Returns the minimum element of the given collection, according to the
  401.      * <i>natural ordering</i> of its elements.  All elements in the
  402.      * collection must implement the <tt>Comparable</tt> interface.
  403.      * Furthermore, all elements in the collection must be <i>mutually
  404.      * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
  405.      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  406.      * <tt>e2</tt> in the collection).<p>
  407.      *
  408.      * This method iterates over the entire collection, hence it requires
  409.      * time proportional to the size of the collection.
  410.      *
  411.      * @param  coll the collection whose minimum element is to be determined.
  412.      * @return the minimum element of the given collection, according
  413.      *         to the <i>natural ordering</i> of its elements.
  414.      * @throws ClassCastException if the collection contains elements that are
  415.      *           not <i>mutually comparable</i> (for example, strings and
  416.      *           integers).
  417.      * @throws NoSuchElementException if the collection is empty.
  418.      * @see Comparable
  419.      */
  420.     public static Object min(Collection coll) {
  421.     Iterator i = coll.iterator();
  422.     Comparable candidate = (Comparable)(i.next());
  423.     while (i.hasNext()) {
  424.         Comparable next = (Comparable)(i.next());
  425.         if (next.compareTo(candidate) < 0)
  426.         candidate = next;
  427.     }
  428.     return candidate;
  429.     }
  430.  
  431.     /**
  432.      * Returns the minimum element of the given collection, according to the
  433.      * order induced by the specified comparator.  All elements in the
  434.      * collection must be <i>mutually comparable</i> by the specified
  435.      * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
  436.      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  437.      * <tt>e2</tt> in the collection).<p>
  438.      *
  439.      * This method iterates over the entire collection, hence it requires
  440.      * time proportional to the size of the collection.
  441.      *
  442.      * @param  coll the collection whose minimum element is to be determined.
  443.      * @return the minimum element of the given collection, according
  444.      *         to the specified comparator.
  445.      * @throws ClassCastException if the collection contains elements that are
  446.      *           not <i>mutually comparable</i> using the specified comparator.
  447.      * @throws NoSuchElementException if the collection is empty.
  448.      * @see Comparable
  449.      */
  450.     public static Object min(Collection coll, Comparator comp) {
  451.     Iterator i = coll.iterator();
  452.     Object candidate = i.next();
  453.     while (i.hasNext()) {
  454.         Object next = i.next();
  455.         if (comp.compare(next, candidate) < 0)
  456.         candidate = next;
  457.     }
  458.     return candidate;
  459.     }
  460.  
  461.     /**
  462.      * Returns the maximum element of the given collection, according to the
  463.      * <i>natural ordering</i> of its elements.  All elements in the
  464.      * collection must implement the <tt>Comparable</tt> interface.
  465.      * Furthermore, all elements in the collection must be <i>mutually
  466.      * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
  467.      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  468.      * <tt>e2</tt> in the collection).<p>
  469.      *
  470.      * This method iterates over the entire collection, hence it requires
  471.      * time proportional to the size of the collection.
  472.      *
  473.      * @param  coll the collection whose maximum element is to be determined.
  474.      * @return the maximum element of the given collection, according
  475.      *         to the <i>natural ordering</i> of its elements.
  476.      * @throws ClassCastException if the collection contains elements that are
  477.      *           not <i>mutually comparable</i> (for example, strings and
  478.      *         integers).
  479.      * @throws NoSuchElementException if the collection is empty.
  480.      * @see Comparable
  481.      */
  482.     public static Object max(Collection coll) {
  483.     Iterator i = coll.iterator();
  484.     Comparable candidate = (Comparable)(i.next());
  485.     while (i.hasNext()) {
  486.         Comparable next = (Comparable)(i.next());
  487.         if (next.compareTo(candidate) > 0)
  488.         candidate = next;
  489.     }
  490.     return candidate;
  491.     }
  492.  
  493.     /**
  494.      * Returns the maximum element of the given collection, according to the
  495.      * order induced by the specified comparator.  All elements in the
  496.      * collection must be <i>mutually comparable</i> by the specified
  497.      * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
  498.      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  499.      * <tt>e2</tt> in the collection).<p>
  500.      *
  501.      * This method iterates over the entire collection, hence it requires
  502.      * time proportional to the size of the collection.
  503.      *
  504.      * @param  coll the collection whose maximum element is to be determined.
  505.      * @return the maximum element of the given collection, according
  506.      *         to the specified comparator.
  507.      * @throws ClassCastException if the collection contains elements that are
  508.      *           not <i>mutually comparable</i> using the specified comparator.
  509.      * @throws NoSuchElementException if the collection is empty.
  510.      * @see Comparable
  511.      */
  512.     public static Object max(Collection coll, Comparator comp) {
  513.     Iterator i = coll.iterator();
  514.     Object candidate = i.next();
  515.     while (i.hasNext()) {
  516.         Object next = i.next();
  517.         if (comp.compare(next, candidate) > 0)
  518.         candidate = next;
  519.     }
  520.     return candidate;
  521.     }
  522.  
  523.  
  524.     // Unmodifiable Wrappers
  525.  
  526.     /**
  527.      * Returns an unmodifiable view of the specified collection.  This method
  528.      * allows modules to provide users with "read-only" access to internal
  529.      * collections.  Query operations on the returned collection "read through"
  530.      * to the specified collection, and attempts to modify the returned
  531.      * collection, whether direct or via its iterator, result in an
  532.      * <tt>UnsupportedOperationException</tt>.<p>
  533.      *
  534.      * The returned collection does <i>not</i> pass the hashCode and equals
  535.      * operations through to the backing collection, but relies on
  536.      * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods.  This
  537.      * is necessary to preserve the contracts of these operations in the case
  538.      * that the backing collection is a set or a list.<p>
  539.      *
  540.      * The returned collection will be serializable if the specified collection
  541.      * is serializable. 
  542.      *
  543.      * @param  c the collection for which an unmodifiable view is to be
  544.      *           returned.
  545.      * @return an unmodifiable view of the specified collection.
  546.      */
  547.     public static Collection unmodifiableCollection(Collection c) {
  548.     return new UnmodifiableCollection(c);
  549.     }
  550.  
  551.     static class UnmodifiableCollection implements Collection, Serializable {
  552.     Collection c;
  553.  
  554.     UnmodifiableCollection(Collection c) {this.c = c;}
  555.  
  556.     public int size()             {return c.size();}
  557.     public boolean isEmpty()         {return c.isEmpty();}
  558.     public boolean contains(Object o)   {return c.contains(o);}
  559.     public Object[] toArray()         {return c.toArray();}
  560.     public Object[] toArray(Object[] a) {return c.toArray(a);}
  561.  
  562.     public Iterator iterator() {
  563.         return new Iterator() {
  564.         Iterator i = c.iterator();
  565.  
  566.         public boolean hasNext() {return i.hasNext();}
  567.         public Object next()      {return i.next();}
  568.         public void remove() {
  569.             throw new UnsupportedOperationException();
  570.                 }
  571.         };
  572.         }
  573.  
  574.     public boolean add(Object o){
  575.         throw new UnsupportedOperationException();
  576.         }
  577.     public boolean remove(Object o) {
  578.         throw new UnsupportedOperationException();
  579.         }
  580.  
  581.     public boolean containsAll(Collection coll) {
  582.         return c.containsAll(coll);
  583.         }
  584.     public boolean addAll(Collection coll) {
  585.         throw new UnsupportedOperationException();
  586.         }
  587.     public boolean removeAll(Collection coll) {
  588.         throw new UnsupportedOperationException();
  589.         }
  590.     public boolean retainAll(Collection coll) {
  591.         throw new UnsupportedOperationException();
  592.         }
  593.     public void clear() {
  594.         throw new UnsupportedOperationException();
  595.         }
  596.     }
  597.  
  598.     /**
  599.      * Returns an unmodifiable view of the specified set.  This method allows
  600.      * modules to provide users with "read-only" access to internal sets.
  601.      * Query operations on the returned set "read through" to the specified
  602.      * set, and attempts to modify the returned set, whether direct or via its
  603.      * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
  604.      *
  605.      * The returned set will be serializable if the specified set
  606.      * is serializable. 
  607.      *
  608.      * @param  s the set for which an unmodifiable view is to be returned.
  609.      * @return an unmodifiable view of the specified set.
  610.      */
  611.  
  612.     public static Set unmodifiableSet(Set s) {
  613.     return new UnmodifiableSet(s);
  614.     }
  615.  
  616.     static class UnmodifiableSet extends UnmodifiableCollection
  617.                      implements Set, Serializable {
  618.     UnmodifiableSet(Set s)         {super(s);}
  619.  
  620.     public boolean equals(Object o) {return c.equals(o);}
  621.     public int hashCode()         {return c.hashCode();}
  622.     }
  623.  
  624.     /**
  625.      * Returns an unmodifiable view of the specified sorted set.  This method
  626.      * allows modules to provide users with "read-only" access to internal
  627.      * sorted sets.  Query operations on the returned sorted set "read
  628.      * through" to the specified sorted set.  Attempts to modify the returned
  629.      * sorted set, whether direct, via its iterator, or via its
  630.      * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
  631.      * an <tt>UnsupportedOperationException</tt>.<p>
  632.      *
  633.      * The returned sorted set will be serializable if the specified sorted set
  634.      * is serializable. 
  635.      *
  636.      * @param s the sorted set for which an unmodifiable view is to be
  637.      *        returned. 
  638.      * @return an unmodifiable view of the specified sorted set.
  639.      */
  640.     public static SortedSet unmodifiableSortedSet(SortedSet s) {
  641.     return new UnmodifiableSortedSet(s);
  642.     }
  643.  
  644.     static class UnmodifiableSortedSet extends UnmodifiableSet
  645.                      implements SortedSet, Serializable {
  646.         private SortedSet ss;
  647.  
  648.     UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;}
  649.  
  650.         public Comparator comparator()     {return ss.comparator();}
  651.  
  652.         public SortedSet subSet(Object fromElement, Object toElement) {
  653.             return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement));
  654.         }
  655.         public SortedSet headSet(Object toElement) {
  656.             return new UnmodifiableSortedSet(ss.headSet(toElement));
  657.         }
  658.         public SortedSet tailSet(Object fromElement) {
  659.             return new UnmodifiableSortedSet(ss.tailSet(fromElement));
  660.         }
  661.  
  662.         public Object first()                {return ss.first();}
  663.         public Object last()                 {return ss.last();}
  664.     }
  665.  
  666.     /**
  667.      * Returns an unmodifiable view of the specified list.  This method allows
  668.      * modules to provide users with "read-only" access to internal
  669.      * lists.  Query operations on the returned list "read through" to the
  670.      * specified list, and attempts to modify the returned list, whether
  671.      * direct or via its iterator, result in an
  672.      * <tt>UnsupportedOperationException</tt>.<p>
  673.      *
  674.      * The returned list will be serializable if the specified list
  675.      * is serializable. 
  676.      *
  677.      * @param  list the list for which an unmodifiable view is to be returned.
  678.      * @return an unmodifiable view of the specified list.
  679.      */
  680.     public static List unmodifiableList(List list) {
  681.     return new UnmodifiableList(list);
  682.     }
  683.  
  684.     static class UnmodifiableList extends UnmodifiableCollection
  685.                       implements List {
  686.     private List list;
  687.  
  688.     UnmodifiableList(List list) {
  689.         super(list);
  690.         this.list = list;
  691.     }
  692.  
  693.     public boolean equals(Object o) {return list.equals(o);}
  694.     public int hashCode()         {return list.hashCode();}
  695.  
  696.     public Object get(int index) {return list.get(index);}
  697.     public Object set(int index, Object element) {
  698.         throw new UnsupportedOperationException();
  699.         }
  700.     public void add(int index, Object element) {
  701.         throw new UnsupportedOperationException();
  702.         }
  703.     public Object remove(int index) {
  704.         throw new UnsupportedOperationException();
  705.         }
  706.     public int indexOf(Object o)            {return list.indexOf(o);}
  707.     public int lastIndexOf(Object o)        {return list.lastIndexOf(o);}
  708.     public boolean addAll(int index, Collection c) {
  709.         throw new UnsupportedOperationException();
  710.         }
  711.     public ListIterator listIterator()     {return listIterator(0);}
  712.  
  713.     public ListIterator listIterator(final int index) {
  714.         return new ListIterator() {
  715.         ListIterator i = list.listIterator(index);
  716.  
  717.         public boolean hasNext()     {return i.hasNext();}
  718.         public Object next()         {return i.next();}
  719.         public boolean hasPrevious() {return i.hasPrevious();}
  720.         public Object previous()     {return i.previous();}
  721.         public int nextIndex()       {return i.nextIndex();}
  722.         public int previousIndex()   {return i.previousIndex();}
  723.  
  724.         public void remove() {
  725.             throw new UnsupportedOperationException();
  726.                 }
  727.         public void set(Object o) {
  728.             throw new UnsupportedOperationException();
  729.                 }
  730.         public void add(Object o) {
  731.             throw new UnsupportedOperationException();
  732.                 }
  733.         };
  734.     }
  735.  
  736.     public List subList(int fromIndex, int toIndex) {
  737.             return new UnmodifiableList(list.subList(fromIndex, toIndex));
  738.         }
  739.     }
  740.  
  741.     /**
  742.      * Returns an unmodifiable view of the specified map.  This method
  743.      * allows modules to provide users with "read-only" access to internal
  744.      * maps.  Query operations on the returned map "read through"
  745.      * to the specified map, and attempts to modify the returned
  746.      * map, whether direct or via its collection views, result in an
  747.      * <tt>UnsupportedOperationException</tt>.<p>
  748.      *
  749.      * The returned map will be serializable if the specified map
  750.      * is serializable. 
  751.      *
  752.      * @param  m the map for which an unmodifiable view is to be returned.
  753.      * @return an unmodifiable view of the specified map.
  754.      */
  755.     public static Map unmodifiableMap(Map m) {
  756.     return new UnmodifiableMap(m);
  757.     }
  758.  
  759.     private static class UnmodifiableMap implements Map, Serializable {
  760.     private final Map m;
  761.  
  762.     UnmodifiableMap(Map m)                  {this.m = m;}
  763.  
  764.     public int size()                  {return m.size();}
  765.     public boolean isEmpty()              {return m.isEmpty();}
  766.     public boolean containsKey(Object key)   {return m.containsKey(key);}
  767.     public boolean containsValue(Object val) {return m.containsValue(val);}
  768.     public Object get(Object key)              {return m.get(key);}
  769.  
  770.     public Object put(Object key, Object value) {
  771.         throw new UnsupportedOperationException();
  772.         }
  773.     public Object remove(Object key) {
  774.         throw new UnsupportedOperationException();
  775.         }
  776.     public void putAll(Map t) {
  777.         throw new UnsupportedOperationException();
  778.         }
  779.     public void clear() {
  780.         throw new UnsupportedOperationException();
  781.         }
  782.  
  783.     private transient Set keySet = null;
  784.     private transient Set entrySet = null;
  785.     private transient Collection values = null;
  786.  
  787.     public Set keySet() {
  788.         if (keySet==null)
  789.         keySet = unmodifiableSet(m.keySet());
  790.         return keySet;
  791.     }
  792.  
  793.     public Set entrySet() {
  794.         if (entrySet==null)
  795.         entrySet = new UnmodifiableEntrySet(m.entrySet());
  796.         return entrySet;
  797.     }
  798.  
  799.     public Collection values() {
  800.         if (values==null)
  801.         values = unmodifiableCollection(m.values());
  802.         return values;
  803.     }
  804.  
  805.     public boolean equals(Object o) {return m.equals(o);}
  806.     public int hashCode()           {return m.hashCode();}
  807.  
  808.  
  809.         /**
  810.          * We need this class in addition to UnmodifiableSet as
  811.          * Map.Entries themselves permit modification of the backing Map
  812.          * via their setValue operation.  This class is subtle: there are
  813.          * many possible attacks that must be thwarted.
  814.          */
  815.         static class UnmodifiableEntrySet extends UnmodifiableSet {
  816.             UnmodifiableEntrySet(Set s) {
  817.                 super(s);
  818.             }
  819.  
  820.             public Iterator iterator() {
  821.                 return new Iterator() {
  822.                     Iterator i = c.iterator();
  823.  
  824.                     public boolean hasNext() {
  825.                         return i.hasNext();
  826.                     }
  827.                     public Object next()      {
  828.                         return new UnmodifiableEntry((Map.Entry)i.next());
  829.                     }
  830.                     public void remove() {
  831.                         throw new UnsupportedOperationException();
  832.                     }
  833.                 };
  834.             }
  835.  
  836.             public Object[] toArray() {
  837.                 Object[] a = c.toArray();
  838.                 for (int i=0; i<a.length; i++)
  839.                     a[i] = new UnmodifiableEntry((Map.Entry)a[i]);
  840.                 return a;
  841.             }
  842.  
  843.             public Object[] toArray(Object a[]) {
  844.                 // We don't pass a to c.toArray, to avoid window of
  845.                 // vulnerability wherein an unscrupulous multithreaded client
  846.                 // could get his hands on raw (unwrapped) Entries from c.
  847.                 Object[] arr = c.toArray(a.length==0 ? a :
  848.                             (Object[])java.lang.reflect.Array.newInstance(
  849.                                           a.getClass().getComponentType(), 0));
  850.                 for (int i=0; i<arr.length; i++)
  851.                     arr[i] = new UnmodifiableEntry((Map.Entry)arr[i]);
  852.  
  853.                 if (arr.length > a.length)
  854.                     return arr;
  855.  
  856.                 System.arraycopy(arr, 0, a, 0, arr.length);
  857.                 if (a.length > arr.length)
  858.                     a[arr.length] = null;
  859.                 return a;
  860.             }
  861.  
  862.             /**
  863.              * This method is overridden to protect the backing set against
  864.              * an object with a nefarious equals function that senses
  865.              * that the equality-candidate is Map.Entry and calls its
  866.              * setValue method.
  867.              */
  868.             public boolean contains(Object o) {
  869.                 if (!(o instanceof Map.Entry))
  870.                     return false;
  871.                 return c.contains(new UnmodifiableEntry((Map.Entry)o));
  872.             }
  873.  
  874.             /**
  875.              * The next two methods are overridden to protect against
  876.              * an unscrupulous List whose contains(Object o) method senses
  877.              * when o is a Map.Entry, and calls o.setValue.
  878.              */
  879.             public boolean containsAll(Collection coll) {
  880.                 Iterator e = coll.iterator();
  881.                 while (e.hasNext())
  882.                     if(!contains(e.next())) // Invokes safe contains() above
  883.                         return false;
  884.                 return true;
  885.             }
  886.             public boolean equals(Object o) {
  887.                 if (o == this)
  888.                     return true;
  889.  
  890.                 if (!(o instanceof Set))
  891.                     return false;
  892.                 Set s = (Set) o;
  893.                 if (s.size() != c.size())
  894.                     return false;
  895.                 return containsAll(s); // Invokes safe containsAll() above
  896.             }
  897.  
  898.             /**
  899.              * This "wrapper class" serves two purposes: it prevents
  900.              * the client from modifying the backing Map, by short-circuiting
  901.              * the setValue method, and it protects the backing Map against
  902.              * an ill-behaved Map.Entry that attempts to modify another
  903.              * Map Entry when asked to perform an equality check.
  904.              */
  905.             private static class UnmodifiableEntry implements Map.Entry {
  906.                 private Map.Entry e;
  907.  
  908.                 UnmodifiableEntry(Map.Entry e) {this.e = e;}
  909.  
  910.                 public Object getKey()      {return e.getKey();}
  911.                 public Object getValue()  {return e.getValue();}
  912.                 public Object setValue(Object value) {
  913.                     throw new UnsupportedOperationException();
  914.                 }
  915.                 public int hashCode()      {return e.hashCode();}
  916.                 public boolean equals(Object o) {
  917.                     if (!(o instanceof Map.Entry))
  918.                         return false;
  919.                     Map.Entry t = (Map.Entry)o;
  920.                     return eq(e.getKey(),   t.getKey()) &&
  921.                            eq(e.getValue(), t.getValue());
  922.                 }
  923.                 public String toString()  {return e.toString();}
  924.             }
  925.         }
  926.     }
  927.  
  928.     /**
  929.      * Returns an unmodifiable view of the specified sorted map.  This method
  930.      * allows modules to provide users with "read-only" access to internal
  931.      * sorted maps.  Query operations on the returned sorted map "read through"
  932.      * to the specified sorted map.  Attempts to modify the returned
  933.      * sorted map, whether direct, via its collection views, or via its
  934.      * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
  935.      * an <tt>UnsupportedOperationException</tt>.<p>
  936.      *
  937.      * The returned sorted map will be serializable if the specified sorted map
  938.      * is serializable. 
  939.      *
  940.      * @param m the sorted map for which an unmodifiable view is to be
  941.      *        returned. 
  942.      * @return an unmodifiable view of the specified sorted map.
  943.      */
  944.     public static SortedMap unmodifiableSortedMap(SortedMap m) {
  945.     return new UnmodifiableSortedMap(m);
  946.     }
  947.  
  948.     static class UnmodifiableSortedMap extends UnmodifiableMap
  949.                      implements SortedMap, Serializable {
  950.         private SortedMap sm;
  951.  
  952.     UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;}
  953.  
  954.         public Comparator comparator()     {return sm.comparator();}
  955.  
  956.         public SortedMap subMap(Object fromKey, Object toKey) {
  957.             return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
  958.         }
  959.         public SortedMap headMap(Object toKey) {
  960.             return new UnmodifiableSortedMap(sm.headMap(toKey));
  961.         }
  962.         public SortedMap tailMap(Object fromKey) {
  963.             return new UnmodifiableSortedMap(sm.tailMap(fromKey));
  964.         }
  965.  
  966.         public Object firstKey()           {return sm.firstKey();}
  967.         public Object lastKey()            {return sm.lastKey();}
  968.     }
  969.  
  970.  
  971.     // Synch Wrappers
  972.  
  973.     /**
  974.      * Returns a synchronized (thread-safe) collection backed by the specified
  975.      * collection.  In order to guarantee serial access, it is critical that
  976.      * <strong>all</strong> access to the backing collection is accomplished
  977.      * through the returned collection.<p>
  978.      *
  979.      * It is imperative that the user manually synchronize on the returned
  980.      * collection when iterating over it:
  981.      * <pre>
  982.      *  Collection c = Collections.synchronizedCollection(myCollection);
  983.      *     ...
  984.      *  synchronized(c) {
  985.      *      Iterator i = c.iterator(); // Must be in the synchronized block
  986.      *      while (i.hasNext())
  987.      *         foo(i.next());
  988.      *  }
  989.      * </pre>
  990.      * Failure to follow this advice may result in non-deterministic behavior.
  991.      *
  992.      * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
  993.      * and <tt>equals</tt> operations through to the backing collection, but
  994.      * relies on <tt>Object</tt>'s equals and hashCode methods.  This is
  995.      * necessary to preserve the contracts of these operations in the case
  996.      * that the backing collection is a set or a list.<p>
  997.      *
  998.      * The returned collection will be serializable if the specified collection
  999.      * is serializable. 
  1000.      *
  1001.      * @param  c the collection to be "wrapped" in a synchronized collection.
  1002.      * @return a synchronized view of the specified collection.
  1003.      */
  1004.     public static Collection synchronizedCollection(Collection c) {
  1005.     return new SynchronizedCollection(c);
  1006.     }
  1007.  
  1008.     static Collection synchronizedCollection(Collection c, Object mutex) {
  1009.     return new SynchronizedCollection(c, mutex);
  1010.     }
  1011.  
  1012.     static class SynchronizedCollection implements Collection, Serializable {
  1013.     Collection c;       // Backing Collection
  1014.     Object       mutex;  // Object on which to synchronize
  1015.  
  1016.     SynchronizedCollection(Collection c) {
  1017.         this.c = c; mutex = this;
  1018.         }
  1019.     SynchronizedCollection(Collection c, Object mutex) {
  1020.         this.c = c; this.mutex = mutex;
  1021.         }
  1022.  
  1023.     public int size() {
  1024.         synchronized(mutex) {return c.size();}
  1025.         }
  1026.     public boolean isEmpty() {
  1027.         synchronized(mutex) {return c.isEmpty();}
  1028.         }
  1029.     public boolean contains(Object o) {
  1030.         synchronized(mutex) {return c.contains(o);}
  1031.         }
  1032.     public Object[] toArray() {
  1033.         synchronized(mutex) {return c.toArray();}
  1034.         }
  1035.     public Object[] toArray(Object[] a) {
  1036.         synchronized(mutex) {return c.toArray(a);}
  1037.         }
  1038.  
  1039.     public Iterator iterator() {
  1040.             return c.iterator(); // Must be manually synched by user!
  1041.         }
  1042.  
  1043.     public boolean add(Object o) {
  1044.         synchronized(mutex) {return c.add(o);}
  1045.         }
  1046.     public boolean remove(Object o) {
  1047.         synchronized(mutex) {return c.remove(o);}
  1048.         }
  1049.  
  1050.     public boolean containsAll(Collection coll) {
  1051.         synchronized(mutex) {return c.containsAll(coll);}
  1052.         }
  1053.     public boolean addAll(Collection coll) {
  1054.         synchronized(mutex) {return c.addAll(coll);}
  1055.         }
  1056.     public boolean removeAll(Collection coll) {
  1057.         synchronized(mutex) {return c.removeAll(coll);}
  1058.         }
  1059.     public boolean retainAll(Collection coll) {
  1060.         synchronized(mutex) {return c.retainAll(coll);}
  1061.         }
  1062.     public void clear() {
  1063.         synchronized(mutex) {c.clear();}
  1064.         }
  1065.     }
  1066.  
  1067.     /**
  1068.      * Returns a synchronized (thread-safe) set backed by the specified
  1069.      * set.  In order to guarantee serial access, it is critical that
  1070.      * <strong>all</strong> access to the backing set is accomplished
  1071.      * through the returned set.<p>
  1072.      *
  1073.      * It is imperative that the user manually synchronize on the returned
  1074.      * set when iterating over it:
  1075.      * <pre>
  1076.      *  Set s = Collections.synchronizedSet(new HashSet());
  1077.      *      ...
  1078.      *  synchronized(s) {
  1079.      *      Iterator i = s.iterator(); // Must be in the synchronized block
  1080.      *      while (i.hasNext())
  1081.      *          foo(i.next());
  1082.      *  }
  1083.      * </pre>
  1084.      * Failure to follow this advice may result in non-deterministic behavior.
  1085.      *
  1086.      * <p>The returned set will be serializable if the specified set is
  1087.      * serializable.
  1088.      *
  1089.      * @param  s the set to be "wrapped" in a synchronized set.
  1090.      * @return a synchronized view of the specified set.
  1091.      */
  1092.     public static Set synchronizedSet(Set s) {
  1093.     return new SynchronizedSet(s);
  1094.     }
  1095.  
  1096.     static Set synchronizedSet(Set s, Object mutex) {
  1097.     return new SynchronizedSet(s, mutex);
  1098.     }
  1099.  
  1100.     static class SynchronizedSet extends SynchronizedCollection
  1101.                      implements Set {
  1102.     SynchronizedSet(Set s) {
  1103.             super(s);
  1104.         }
  1105.     SynchronizedSet(Set s, Object mutex) {
  1106.             super(s, mutex);
  1107.         }
  1108.  
  1109.     public boolean equals(Object o) {
  1110.         synchronized(mutex) {return c.equals(o);}
  1111.         }
  1112.     public int hashCode() {
  1113.         synchronized(mutex) {return c.hashCode();}
  1114.         }
  1115.     }
  1116.  
  1117.     /**
  1118.      * Returns a synchronized (thread-safe) sorted set backed by the specified
  1119.      * sorted set.  In order to guarantee serial access, it is critical that
  1120.      * <strong>all</strong> access to the backing sorted set is accomplished
  1121.      * through the returned sorted set (or its views).<p>
  1122.      *
  1123.      * It is imperative that the user manually synchronize on the returned
  1124.      * sorted set when iterating over it or any of its <tt>subSet</tt>,
  1125.      * <tt>headSet</tt>, or <tt>tailSet</tt> views.
  1126.      * <pre>
  1127.      *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
  1128.      *      ...
  1129.      *  synchronized(s) {
  1130.      *      Iterator i = s.iterator(); // Must be in the synchronized block
  1131.      *      while (i.hasNext())
  1132.      *          foo(i.next());
  1133.      *  }
  1134.      * </pre>
  1135.      * or:
  1136.      * <pre>
  1137.      *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
  1138.      *  SortedSet s2 = s.headSet(foo);
  1139.      *      ...
  1140.      *  synchronized(s) {  // Note: s, not s2!!!
  1141.      *      Iterator i = s2.iterator(); // Must be in the synchronized block
  1142.      *      while (i.hasNext())
  1143.      *          foo(i.next());
  1144.      *  }
  1145.      * </pre>
  1146.      * Failure to follow this advice may result in non-deterministic behavior.
  1147.      *
  1148.      * <p>The returned sorted set will be serializable if the specified
  1149.      * sorted set is serializable.
  1150.      *
  1151.      * @param  s the sorted set to be "wrapped" in a synchronized sorted set.
  1152.      * @return a synchronized view of the specified sorted set.
  1153.      */
  1154.     public static SortedSet synchronizedSortedSet(SortedSet s) {
  1155.     return new SynchronizedSortedSet(s);
  1156.     }
  1157.  
  1158.     static class SynchronizedSortedSet extends SynchronizedSet
  1159.                      implements SortedSet
  1160.     {
  1161.         private SortedSet ss;
  1162.  
  1163.     SynchronizedSortedSet(SortedSet s) {
  1164.             super(s);
  1165.             ss = s;
  1166.         }
  1167.     SynchronizedSortedSet(SortedSet s, Object mutex) {
  1168.             super(s, mutex);
  1169.             ss = s;
  1170.         }
  1171.  
  1172.     public Comparator comparator() {
  1173.         synchronized(mutex) {return ss.comparator();}
  1174.         }
  1175.  
  1176.         public SortedSet subSet(Object fromElement, Object toElement) {
  1177.         synchronized(mutex) {
  1178.                 return new SynchronizedSortedSet(
  1179.                     ss.subSet(fromElement, toElement), mutex);
  1180.             }
  1181.         }
  1182.         public SortedSet headSet(Object toElement) {
  1183.         synchronized(mutex) {
  1184.                 return new SynchronizedSortedSet(ss.headSet(toElement), mutex);
  1185.             }
  1186.         }
  1187.         public SortedSet tailSet(Object fromElement) {
  1188.         synchronized(mutex) {
  1189.                return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex);
  1190.             }
  1191.         }
  1192.  
  1193.         public Object first() {
  1194.         synchronized(mutex) {return ss.first();}
  1195.         }
  1196.         public Object last() {
  1197.         synchronized(mutex) {return ss.last();}
  1198.         }
  1199.     }
  1200.  
  1201.     /**
  1202.      * Returns a synchronized (thread-safe) list backed by the specified
  1203.      * list.  In order to guarantee serial access, it is critical that
  1204.      * <strong>all</strong> access to the backing list is accomplished
  1205.      * through the returned list.<p>
  1206.      *
  1207.      * It is imperative that the user manually synchronize on the returned
  1208.      * list when iterating over it:
  1209.      * <pre>
  1210.      *  List list = Collections.synchronizedList(new ArrayList());
  1211.      *      ...
  1212.      *  synchronized(list) {
  1213.      *      Iterator i = list.iterator(); // Must be in synchronized block
  1214.      *      while (i.hasNext())
  1215.      *          foo(i.next());
  1216.      *  }
  1217.      * </pre>
  1218.      * Failure to follow this advice may result in non-deterministic behavior.
  1219.      *
  1220.      * <p>The returned list will be serializable if the specified list is
  1221.      * serializable.
  1222.      *
  1223.      * @param  list the list to be "wrapped" in a synchronized list.
  1224.      * @return a synchronized view of the specified list.
  1225.      */
  1226.     public static List synchronizedList(List list) {
  1227.     return new SynchronizedList(list);
  1228.     }
  1229.  
  1230.     static List synchronizedList(List list, Object mutex) {
  1231.     return new SynchronizedList(list, mutex);
  1232.     }
  1233.  
  1234.     static class SynchronizedList extends SynchronizedCollection
  1235.                           implements List {
  1236.     private List list;
  1237.  
  1238.     SynchronizedList(List list) {
  1239.         super(list);
  1240.         this.list = list;
  1241.     }
  1242.     SynchronizedList(List list, Object mutex) {
  1243.             super(list, mutex);
  1244.         this.list = list;
  1245.         }
  1246.  
  1247.     public boolean equals(Object o) {
  1248.         synchronized(mutex) {return list.equals(o);}
  1249.         }
  1250.     public int hashCode() {
  1251.         synchronized(mutex) {return list.hashCode();}
  1252.         }
  1253.  
  1254.     public Object get(int index) {
  1255.         synchronized(mutex) {return list.get(index);}
  1256.         }
  1257.     public Object set(int index, Object element) {
  1258.         synchronized(mutex) {return list.set(index, element);}
  1259.         }
  1260.     public void add(int index, Object element) {
  1261.         synchronized(mutex) {list.add(index, element);}
  1262.         }
  1263.     public Object remove(int index) {
  1264.         synchronized(mutex) {return list.remove(index);}
  1265.         }
  1266.  
  1267.     public int indexOf(Object o) {
  1268.         synchronized(mutex) {return list.indexOf(o);}
  1269.         }
  1270.     public int lastIndexOf(Object o) {
  1271.         synchronized(mutex) {return list.lastIndexOf(o);}
  1272.         }
  1273.  
  1274.     public boolean addAll(int index, Collection c) {
  1275.         synchronized(mutex) {return list.addAll(index, c);}
  1276.         }
  1277.  
  1278.     public ListIterator listIterator() {
  1279.         return list.listIterator(); // Must be manually synched by user
  1280.         }
  1281.  
  1282.     public ListIterator listIterator(int index) {
  1283.         return list.listIterator(index); // Must be manually synched by usr
  1284.         }
  1285.  
  1286.     public List subList(int fromIndex, int toIndex) {
  1287.         synchronized(mutex) {
  1288.                 return new SynchronizedList(list.subList(fromIndex, toIndex),
  1289.                                             mutex);
  1290.             }
  1291.         }
  1292.     }
  1293.  
  1294.     /**
  1295.      * Returns a synchronized (thread-safe) map backed by the specified
  1296.      * map.  In order to guarantee serial access, it is critical that
  1297.      * <strong>all</strong> access to the backing map is accomplished
  1298.      * through the returned map.<p>
  1299.      *
  1300.      * It is imperative that the user manually synchronize on the returned
  1301.      * map when iterating over any of its collection views:
  1302.      * <pre>
  1303.      *  Map m = Collections.synchronizedMap(new HashMap());
  1304.      *      ...
  1305.      *  Set s = m.keySet();  // Needn't be in synchronized block
  1306.      *      ...
  1307.      *  synchronized(m) {  // Synchronizing on m, not s!
  1308.      *      Iterator i = s.iterator(); // Must be in synchronized block
  1309.      *      while (i.hasNext())
  1310.      *          foo(i.next());
  1311.      *  }
  1312.      * </pre>
  1313.      * Failure to follow this advice may result in non-deterministic behavior.
  1314.      *
  1315.      * <p>The returned map will be serializable if the specified map is
  1316.      * serializable.
  1317.      *
  1318.      * @param  m the map to be "wrapped" in a synchronized map.
  1319.      * @return a synchronized view of the specified map.
  1320.      */
  1321.     public static Map synchronizedMap(Map m) {
  1322.     return new SynchronizedMap(m);
  1323.     }
  1324.  
  1325.     private static class SynchronizedMap implements Map, Serializable {
  1326.     private Map m;            // Backing Map
  1327.         Object      mutex;    // Object on which to synchronize
  1328.  
  1329.     SynchronizedMap(Map m) {
  1330.             this.m = m;     mutex = this;
  1331.         }
  1332.  
  1333.     SynchronizedMap(Map m, Object mutex) {
  1334.             this.m = m;     this.mutex = mutex;
  1335.         }
  1336.  
  1337.     public int size() {
  1338.         synchronized(mutex) {return m.size();}
  1339.         }
  1340.     public boolean isEmpty(){
  1341.         synchronized(mutex) {return m.isEmpty();}
  1342.         }
  1343.     public boolean containsKey(Object key) {
  1344.         synchronized(mutex) {return m.containsKey(key);}
  1345.         }
  1346.     public boolean containsValue(Object value){
  1347.         synchronized(mutex) {return m.containsValue(value);}
  1348.         }
  1349.     public Object get(Object key) {
  1350.         synchronized(mutex) {return m.get(key);}
  1351.         }
  1352.  
  1353.     public Object put(Object key, Object value) {
  1354.         synchronized(mutex) {return m.put(key, value);}
  1355.         }
  1356.     public Object remove(Object key) {
  1357.         synchronized(mutex) {return m.remove(key);}
  1358.         }
  1359.     public void putAll(Map map) {
  1360.         synchronized(mutex) {m.putAll(map);}
  1361.         }
  1362.     public void clear() {
  1363.         synchronized(mutex) {m.clear();}
  1364.         }
  1365.  
  1366.     private transient Set keySet = null;
  1367.     private transient Set entrySet = null;
  1368.     private transient Collection values = null;
  1369.  
  1370.     public Set keySet() {
  1371.             synchronized(mutex) {
  1372.                 if (keySet==null)
  1373.                     keySet = new SynchronizedSet(m.keySet(), this);
  1374.                 return keySet;
  1375.             }
  1376.     }
  1377.  
  1378.     public Set entrySet() {
  1379.             synchronized(mutex) {
  1380.                 if (entrySet==null)
  1381.                     entrySet = new SynchronizedSet(m.entrySet(), this);
  1382.                 return entrySet;
  1383.             }
  1384.     }
  1385.  
  1386.     public Collection values() {
  1387.             synchronized(mutex) {
  1388.                 if (values==null)
  1389.                     values = new SynchronizedCollection(m.values(), this);
  1390.                 return values;
  1391.             }
  1392.         }
  1393.  
  1394.     public boolean equals(Object o) {
  1395.             synchronized(mutex) {return m.equals(o);}
  1396.         }
  1397.     public int hashCode() {
  1398.             synchronized(mutex) {return m.hashCode();}
  1399.         }
  1400.     }
  1401.  
  1402.     /**
  1403.      * Returns a synchronized (thread-safe) sorted map backed by the specified
  1404.      * sorted map.  In order to guarantee serial access, it is critical that
  1405.      * <strong>all</strong> access to the backing sorted map is accomplished
  1406.      * through the returned sorted map (or its views).<p>
  1407.      *
  1408.      * It is imperative that the user manually synchronize on the returned
  1409.      * sorted map when iterating over any of its collection views, or the
  1410.      * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
  1411.      * <tt>tailMap</tt> views.
  1412.      * <pre>
  1413.      *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
  1414.      *      ...
  1415.      *  Set s = m.keySet();  // Needn't be in synchronized block
  1416.      *      ...
  1417.      *  synchronized(m) {  // Synchronizing on m, not s!
  1418.      *      Iterator i = s.iterator(); // Must be in synchronized block
  1419.      *      while (i.hasNext())
  1420.      *          foo(i.next());
  1421.      *  }
  1422.      * </pre>
  1423.      * or:
  1424.      * <pre>
  1425.      *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
  1426.      *  SortedMap m2 = m.subMap(foo, bar);
  1427.      *      ...
  1428.      *  Set s2 = m2.keySet();  // Needn't be in synchronized block
  1429.      *      ...
  1430.      *  synchronized(m) {  // Synchronizing on m, not m2 or s2!
  1431.      *      Iterator i = s.iterator(); // Must be in synchronized block
  1432.      *      while (i.hasNext())
  1433.      *          foo(i.next());
  1434.      *  }
  1435.      * </pre>
  1436.      * Failure to follow this advice may result in non-deterministic behavior.
  1437.      *
  1438.      * <p>The returned sorted map will be serializable if the specified
  1439.      * sorted map is serializable.
  1440.      *
  1441.      * @param  m the sorted map to be "wrapped" in a synchronized sorted map.
  1442.      * @return a synchronized view of the specified sorted map.
  1443.      */
  1444.     public static SortedMap synchronizedSortedMap(SortedMap m) {
  1445.     return new SynchronizedSortedMap(m);
  1446.     }
  1447.  
  1448.  
  1449.     static class SynchronizedSortedMap extends SynchronizedMap
  1450.                      implements SortedMap
  1451.     {
  1452.         private SortedMap sm;
  1453.  
  1454.     SynchronizedSortedMap(SortedMap m) {
  1455.             super(m);
  1456.             sm = m;
  1457.         }
  1458.     SynchronizedSortedMap(SortedMap m, Object mutex) {
  1459.             super(m, mutex);
  1460.             sm = m;
  1461.         }
  1462.  
  1463.     public Comparator comparator() {
  1464.         synchronized(mutex) {return sm.comparator();}
  1465.         }
  1466.  
  1467.         public SortedMap subMap(Object fromKey, Object toKey) {
  1468.         synchronized(mutex) {
  1469.                 return new SynchronizedSortedMap(
  1470.                     sm.subMap(fromKey, toKey), mutex);
  1471.             }
  1472.         }
  1473.         public SortedMap headMap(Object toKey) {
  1474.         synchronized(mutex) {
  1475.                 return new SynchronizedSortedMap(sm.headMap(toKey), mutex);
  1476.             }
  1477.         }
  1478.         public SortedMap tailMap(Object fromKey) {
  1479.         synchronized(mutex) {
  1480.                return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex);
  1481.             }
  1482.         }
  1483.  
  1484.         public Object firstKey() {
  1485.         synchronized(mutex) {return sm.firstKey();}
  1486.         }
  1487.         public Object lastKey() {
  1488.         synchronized(mutex) {return sm.lastKey();}
  1489.         }
  1490.     }
  1491.  
  1492.  
  1493.     // Miscellaneous
  1494.  
  1495.     /**
  1496.      * The empty set (immutable).  This set is serializable.
  1497.      */
  1498.     public static final Set EMPTY_SET = new AbstractSet() {
  1499.         public Iterator iterator() {
  1500.             return new Iterator() {
  1501.                 public boolean hasNext() {
  1502.                     return false;
  1503.                 }
  1504.                 public Object next() {
  1505.                     throw new NoSuchElementException();
  1506.                 }
  1507.                 public void remove() {
  1508.                     throw new UnsupportedOperationException();
  1509.                 }
  1510.             };
  1511.         }
  1512.  
  1513.         public int size() {return 0;}
  1514.  
  1515.         public boolean contains(Object obj) {return false;}
  1516.     };
  1517.  
  1518.     /**
  1519.      * The empty list (immutable).  This list is serializable.
  1520.      */
  1521.     public static final List EMPTY_LIST = new AbstractList() {
  1522.         public int size() {return 0;}
  1523.  
  1524.         public boolean contains(Object obj) {return false;}
  1525.  
  1526.         public Object get(int index) {
  1527.             throw new IndexOutOfBoundsException("Index: "+index);
  1528.         }
  1529.     };
  1530.  
  1531.     /**
  1532.      * Returns an immutable set containing only the specified object.
  1533.      * The returned set is serializable.
  1534.      *
  1535.      * @return an immutable set containing only the specified object.
  1536.      */
  1537.     public static Set singleton(final Object o) {
  1538.     return new AbstractSet() {
  1539.             public Iterator iterator() {
  1540.                 return new Iterator() {
  1541.                     private boolean hasNext = true;
  1542.                     public boolean hasNext() {
  1543.                         return hasNext;
  1544.                     }
  1545.                     public Object next() {
  1546.                         if (hasNext) {
  1547.                             hasNext = false;
  1548.                             return o;
  1549.                         }
  1550.                         throw new NoSuchElementException();
  1551.                     }
  1552.                     public void remove() {
  1553.                         throw new UnsupportedOperationException();
  1554.                     }
  1555.                 };
  1556.             }
  1557.  
  1558.         public int size() {return 1;}
  1559.  
  1560.         public boolean contains(Object obj) {return eq(obj, o);}
  1561.         };
  1562.     }
  1563.  
  1564.     /**
  1565.      * Returns an immutable list consisting of <tt>n</tt> copies of the
  1566.      * specified object.  The newly allocated data object is tiny (it contains
  1567.      * a single reference to the data object).  This method is useful in
  1568.      * combination with the <tt>List.addAll</tt> method to grow lists.
  1569.      * The returned list is serializable.
  1570.      *
  1571.      * @param  n the number of elements in the returned list.
  1572.      * @param  o the element to appear repeatedly in the returned list.
  1573.      * @return an immutable list consisting of <tt>n</tt> copies of the
  1574.      *            specified object.
  1575.      * @throws IllegalArgumentException if n < 0.
  1576.      * @see    List#addAll(Collection)
  1577.      * @see    List#addAll(int, Collection)
  1578.      */
  1579.     public static List nCopies(final int n, final Object o) {
  1580.     if (n < 0)
  1581.         throw new IllegalArgumentException("List length = " + n);
  1582.  
  1583.     return new AbstractList() {
  1584.         public int size() {
  1585.         return n;
  1586.         }
  1587.  
  1588.         public boolean contains(Object obj) {
  1589.         return n != 0 && eq(obj, o);
  1590.         }
  1591.  
  1592.         public Object get(int index) {
  1593.         if (index<0 || index>=n)
  1594.             throw new IndexOutOfBoundsException("Index: "+index+
  1595.                             ", Size: "+n);
  1596.         return o;
  1597.         }
  1598.         };
  1599.     }
  1600.  
  1601.     /**
  1602.      * Returns a comparator that imposes the reverse of the <i>natural
  1603.      * ordering</i> on a collection of objects that implement the
  1604.      * <tt>Comparable</tt> interface.  (The natural ordering is the ordering
  1605.      * imposed by the objects' own <tt>compareTo</tt> method.)  This enables a
  1606.      * simple idiom for sorting (or maintaining) collections (or arrays) of
  1607.      * objects that implement the <tt>Comparable</tt> interface in
  1608.      * reverse-natural-order.  For example, suppose a is an array of
  1609.      * strings. Then: <pre>
  1610.      *         Arrays.sort(a, Collections.reverseOrder());
  1611.      * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
  1612.      *
  1613.      * The returned comparator is serializable.
  1614.      *
  1615.      * @return a comparator that imposes the reverse of the <i>natural
  1616.      *            ordering</i> on a collection of objects that implement
  1617.      *           the <tt>Comparable</tt> interface.
  1618.      * @see Comparable
  1619.      */
  1620.     public static Comparator reverseOrder() {
  1621.         return REVERSE_ORDER;
  1622.     }
  1623.  
  1624.     private static final Comparator REVERSE_ORDER = new ReverseComparator();
  1625.  
  1626.     private static class ReverseComparator implements Comparator,Serializable {
  1627.         public int compare(Object o1, Object o2) {
  1628.             Comparable c1 = (Comparable)o1;
  1629.             Comparable c2 = (Comparable)o2;
  1630.             return -c1.compareTo(c2);
  1631.         }
  1632.     }
  1633.  
  1634.     /**
  1635.      * Returns an enumeration over the specified collection.  This provides
  1636.      * interoperatbility with legacy APIs that require an enumeration
  1637.      * as input.
  1638.      *
  1639.      * @param c the collection for which an enumeration is to be returned.
  1640.      * @return an enumeration over the specified collection.
  1641.      */
  1642.     public static Enumeration enumeration(final Collection c) {
  1643.     return new Enumeration() {
  1644.         Iterator i = c.iterator();
  1645.  
  1646.         public boolean hasMoreElements() {
  1647.         return i.hasNext();
  1648.         }
  1649.  
  1650.         public Object nextElement() {
  1651.         return i.next();
  1652.         }
  1653.         };
  1654.     }
  1655.  
  1656.     /**
  1657.      * Returns true if the specified arguments are equal, or both null.
  1658.      */
  1659.     private static boolean eq(Object o1, Object o2) {
  1660.         return (o1==null ? o2==null : o1.equals(o2));
  1661.     }
  1662. }
  1663.