001/* Collections.java -- Utility class with methods to operate on collections
002   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
003   Free Software Foundation, Inc.
004
005This file is part of GNU Classpath.
006
007GNU Classpath is free software; you can redistribute it and/or modify
008it under the terms of the GNU General Public License as published by
009the Free Software Foundation; either version 2, or (at your option)
010any later version.
011
012GNU Classpath is distributed in the hope that it will be useful, but
013WITHOUT ANY WARRANTY; without even the implied warranty of
014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015General Public License for more details.
016
017You should have received a copy of the GNU General Public License
018along with GNU Classpath; see the file COPYING.  If not, write to the
019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02002110-1301 USA.
021
022Linking this library statically or dynamically with other modules is
023making a combined work based on this library.  Thus, the terms and
024conditions of the GNU General Public License cover the whole
025combination.
026
027As a special exception, the copyright holders of this library give you
028permission to link this library with independent modules to produce an
029executable, regardless of the license terms of these independent
030modules, and to copy and distribute the resulting executable under
031terms of your choice, provided that you also meet, for each linked
032independent module, the terms and conditions of the license of that
033module.  An independent module is a module which is not derived from
034or based on this library.  If you modify this library, you may extend
035this exception to your version of the library, but you are not
036obligated to do so.  If you do not wish to do so, delete this
037exception statement from your version. */
038
039
040package java.util;
041
042import gnu.java.lang.CPStringBuilder;
043
044import java.io.Serializable;
045
046/**
047 * Utility class consisting of static methods that operate on, or return
048 * Collections. Contains methods to sort, search, reverse, fill and shuffle
049 * Collections, methods to facilitate interoperability with legacy APIs that
050 * are unaware of collections, a method to return a list which consists of
051 * multiple copies of one element, and methods which "wrap" collections to give
052 * them extra properties, such as thread-safety and unmodifiability.
053 * <p>
054 *
055 * All methods which take a collection throw a {@link NullPointerException} if
056 * that collection is null. Algorithms which can change a collection may, but
057 * are not required, to throw the {@link UnsupportedOperationException} that
058 * the underlying collection would throw during an attempt at modification.
059 * For example,
060 * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code>
061 * does not throw a exception, even though addAll is an unsupported operation
062 * on a singleton; the reason for this is that addAll did not attempt to
063 * modify the set.
064 *
065 * @author Original author unknown
066 * @author Eric Blake (ebb9@email.byu.edu)
067 * @author Tom Tromey (tromey@redhat.com)
068 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
069 * @see Collection
070 * @see Set
071 * @see List
072 * @see Map
073 * @see Arrays
074 * @since 1.2
075 * @status updated to 1.5
076 */
077public class Collections
078{
079  /**
080   * Constant used to decide cutoff for when a non-RandomAccess list should
081   * be treated as sequential-access. Basically, quadratic behavior is
082   * acceptable for small lists when the overhead is so small in the first
083   * place. I arbitrarily set it to 16, so it may need some tuning.
084   */
085  private static final int LARGE_LIST_SIZE = 16;
086
087  /**
088   * Determines if a list should be treated as a sequential-access one.
089   * Rather than the old method of JDK 1.3 of assuming only instanceof
090   * AbstractSequentialList should be sequential, this uses the new method
091   * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
092   * and exceeds a large (unspecified) size should be sequential.
093   *
094   * @param l the list to check
095   * @return <code>true</code> if it should be treated as sequential-access
096   */
097  private static boolean isSequential(List<?> l)
098  {
099    return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
100  }
101
102  /**
103   * This class is non-instantiable.
104   */
105  private Collections()
106  {
107  }
108
109  /**
110   * An immutable, serializable, empty Set.
111   * @see Serializable
112   */
113  public static final Set EMPTY_SET = new EmptySet();
114
115  /**
116   * Returns an immutable, serializable parameterized empty set.
117   * Unlike the constant <code>EMPTY_SET</code>, the set returned by
118   * this method is type-safe.
119   *
120   * @return an empty parameterized set.
121   * @since 1.5
122   */
123  public static final <T> Set<T> emptySet()
124  {
125    /* FIXME: Could this be optimized? */
126    return new EmptySet<T>();
127  }
128
129  /**
130   * The implementation of {@link #EMPTY_SET}. This class name is required
131   * for compatibility with Sun's JDK serializability.
132   *
133   * @author Eric Blake (ebb9@email.byu.edu)
134   */
135  private static final class EmptySet<T> extends AbstractSet<T>
136    implements Serializable
137  {
138    /**
139     * Compatible with JDK 1.4.
140     */
141    private static final long serialVersionUID = 1582296315990362920L;
142
143    /**
144     * A private constructor adds overhead.
145     */
146    EmptySet()
147    {
148    }
149
150    /**
151     * The size: always 0!
152     * @return 0.
153     */
154    public int size()
155    {
156      return 0;
157    }
158
159    /**
160     * Returns an iterator that does not iterate.
161     * @return A non-iterating iterator.
162     */
163    // This is really cheating! I think it's perfectly valid, though.
164    public Iterator<T> iterator()
165    {
166      return (Iterator<T>) EMPTY_LIST.iterator();
167    }
168
169    // The remaining methods are optional, but provide a performance
170    // advantage by not allocating unnecessary iterators in AbstractSet.
171    /**
172     * The empty set never contains anything.
173     * @param o The object to search for.
174     * @return <code>false</code>.
175     */
176    public boolean contains(Object o)
177    {
178      return false;
179    }
180
181    /**
182     * This is true only if the given collection is also empty.
183     * @param c The collection of objects which are to be compared
184     *          against the members of this set.
185     * @return <code>true</code> if c is empty.
186     */
187    public boolean containsAll(Collection<?> c)
188    {
189      return c.isEmpty();
190    }
191
192    /**
193     * Equal only if the other set is empty.
194     * @param o The object to compare with this set.
195     * @return <code>true</code> if o is an empty instance of <code>Set</code>.
196     */
197    public boolean equals(Object o)
198    {
199      return o instanceof Set && ((Set) o).isEmpty();
200    }
201
202    /**
203     * The hashcode is always 0.
204     * @return 0.
205     */
206    public int hashCode()
207    {
208      return 0;
209    }
210
211    /**
212     * Always succeeds with a <code>false</code> result.
213     * @param o The object to remove.
214     * @return <code>false</code>.
215     */
216    public boolean remove(Object o)
217    {
218      return false;
219    }
220
221    /**
222     * Always succeeds with a <code>false</code> result.
223     * @param c The collection of objects which should
224     *          all be removed from this set.
225     * @return <code>false</code>.
226     */
227    public boolean removeAll(Collection<?> c)
228    {
229      return false;
230    }
231
232    /**
233     * Always succeeds with a <code>false</code> result.
234     * @param c The collection of objects which should
235     *          all be retained within this set.
236     * @return <code>false</code>.
237     */
238    public boolean retainAll(Collection<?> c)
239    {
240      return false;
241    }
242
243    /**
244     * The array is always empty.
245     * @return A new array with a size of 0.
246     */
247    public Object[] toArray()
248    {
249      return new Object[0];
250    }
251
252    /**
253     * We don't even need to use reflection!
254     * @param a An existing array, which can be empty.
255     * @return The original array with any existing
256     *         initial element set to null.
257     */
258    public <E> E[] toArray(E[] a)
259    {
260      if (a.length > 0)
261        a[0] = null;
262      return a;
263    }
264
265    /**
266     * The string never changes.
267     *
268     * @return the string "[]".
269     */
270    public String toString()
271    {
272      return "[]";
273    }
274  } // class EmptySet
275
276  /**
277   * An immutable, serializable, empty List, which implements RandomAccess.
278   * @see Serializable
279   * @see RandomAccess
280   */
281  public static final List EMPTY_LIST = new EmptyList();
282
283  /**
284   * Returns an immutable, serializable parameterized empty list.
285   * Unlike the constant <code>EMPTY_LIST</code>, the list returned by
286   * this method is type-safe.
287   *
288   * @return an empty parameterized list.
289   * @since 1.5
290   */
291  public static final <T> List<T> emptyList()
292  {
293    /* FIXME: Could this be optimized? */
294    return new EmptyList<T>();
295  }
296
297  /**
298   * The implementation of {@link #EMPTY_LIST}. This class name is required
299   * for compatibility with Sun's JDK serializability.
300   *
301   * @author Eric Blake (ebb9@email.byu.edu)
302   */
303  private static final class EmptyList<T> extends AbstractList<T>
304    implements Serializable, RandomAccess
305  {
306    /**
307     * Compatible with JDK 1.4.
308     */
309    private static final long serialVersionUID = 8842843931221139166L;
310
311    /**
312     * A private constructor adds overhead.
313     */
314    EmptyList()
315    {
316    }
317
318    /**
319     * The size is always 0.
320     * @return 0.
321     */
322    public int size()
323    {
324      return 0;
325    }
326
327    /**
328     * No matter the index, it is out of bounds.  This
329     * method never returns, throwing an exception instead.
330     *
331     * @param index The index of the element to retrieve.
332     * @return the object at the specified index.
333     * @throws IndexOutOfBoundsException as any given index
334     *         is outside the bounds of an empty array.
335     */
336    public T get(int index)
337    {
338      throw new IndexOutOfBoundsException();
339    }
340
341    // The remaining methods are optional, but provide a performance
342    // advantage by not allocating unnecessary iterators in AbstractList.
343    /**
344     * Never contains anything.
345     * @param o The object to search for.
346     * @return <code>false</code>.
347     */
348    public boolean contains(Object o)
349    {
350      return false;
351    }
352
353    /**
354     * This is true only if the given collection is also empty.
355     * @param c The collection of objects, which should be compared
356     *          against the members of this list.
357     * @return <code>true</code> if c is also empty.
358     */
359    public boolean containsAll(Collection<?> c)
360    {
361      return c.isEmpty();
362    }
363
364    /**
365     * Equal only if the other list is empty.
366     * @param o The object to compare against this list.
367     * @return <code>true</code> if o is also an empty instance of
368     *         <code>List</code>.
369     */
370    public boolean equals(Object o)
371    {
372      return o instanceof List && ((List) o).isEmpty();
373    }
374
375    /**
376     * The hashcode is always 1.
377     * @return 1.
378     */
379    public int hashCode()
380    {
381      return 1;
382    }
383
384    /**
385     * Returns -1.
386     * @param o The object to search for.
387     * @return -1.
388     */
389    public int indexOf(Object o)
390    {
391      return -1;
392    }
393
394    /**
395     * Returns -1.
396     * @param o The object to search for.
397     * @return -1.
398     */
399    public int lastIndexOf(Object o)
400    {
401      return -1;
402    }
403
404    /**
405     * Always succeeds with <code>false</code> result.
406     * @param o The object to remove.
407     * @return -1.
408     */
409    public boolean remove(Object o)
410    {
411      return false;
412    }
413
414    /**
415     * Always succeeds with <code>false</code> result.
416     * @param c The collection of objects which should
417     *          all be removed from this list.
418     * @return <code>false</code>.
419     */
420    public boolean removeAll(Collection<?> c)
421    {
422      return false;
423    }
424
425    /**
426     * Always succeeds with <code>false</code> result.
427     * @param c The collection of objects which should
428     *          all be retained within this list.
429     * @return <code>false</code>.
430     */
431    public boolean retainAll(Collection<?> c)
432    {
433      return false;
434    }
435
436    /**
437     * The array is always empty.
438     * @return A new array with a size of 0.
439     */
440    public Object[] toArray()
441    {
442      return new Object[0];
443    }
444
445    /**
446     * We don't even need to use reflection!
447     * @param a An existing array, which can be empty.
448     * @return The original array with any existing
449     *         initial element set to null.
450     */
451    public <E> E[] toArray(E[] a)
452    {
453      if (a.length > 0)
454        a[0] = null;
455      return a;
456    }
457
458    /**
459     * The string never changes.
460     *
461     * @return the string "[]".
462     */
463    public String toString()
464    {
465      return "[]";
466    }
467  } // class EmptyList
468
469  /**
470   * An immutable, serializable, empty Map.
471   * @see Serializable
472   */
473  public static final Map EMPTY_MAP = new EmptyMap();
474
475  /**
476   * Returns an immutable, serializable parameterized empty map.
477   * Unlike the constant <code>EMPTY_MAP</code>, the map returned by
478   * this method is type-safe.
479   *
480   * @return an empty parameterized map.
481   * @since 1.5
482   */
483  public static final <K,V> Map<K,V> emptyMap()
484  {
485    /* FIXME: Could this be optimized? */
486    return new EmptyMap<K,V>();
487  }
488
489  /**
490   * The implementation of {@link #EMPTY_MAP}. This class name is required
491   * for compatibility with Sun's JDK serializability.
492   *
493   * @author Eric Blake (ebb9@email.byu.edu)
494   */
495  private static final class EmptyMap<K, V> extends AbstractMap<K, V>
496    implements Serializable
497  {
498    /**
499     * Compatible with JDK 1.4.
500     */
501    private static final long serialVersionUID = 6428348081105594320L;
502
503    /**
504     * A private constructor adds overhead.
505     */
506    EmptyMap()
507    {
508    }
509
510    /**
511     * There are no entries.
512     * @return The empty set.
513     */
514    public Set<Map.Entry<K, V>> entrySet()
515    {
516      return EMPTY_SET;
517    }
518
519    // The remaining methods are optional, but provide a performance
520    // advantage by not allocating unnecessary iterators in AbstractMap.
521    /**
522     * No entries!
523     * @param key The key to search for.
524     * @return <code>false</code>.
525     */
526    public boolean containsKey(Object key)
527    {
528      return false;
529    }
530
531    /**
532     * No entries!
533     * @param value The value to search for.
534     * @return <code>false</code>.
535     */
536    public boolean containsValue(Object value)
537    {
538      return false;
539    }
540
541    /**
542     * Equal to all empty maps.
543     * @param o The object o to compare against this map.
544     * @return <code>true</code> if o is also an empty instance of
545     *         <code>Map</code>.
546     */
547    public boolean equals(Object o)
548    {
549      return o instanceof Map && ((Map) o).isEmpty();
550    }
551
552    /**
553     * No mappings, so this returns null.
554     * @param o The key of the object to retrieve.
555     * @return null.
556     */
557    public V get(Object o)
558    {
559      return null;
560    }
561
562    /**
563     * The hashcode is always 0.
564     * @return 0.
565     */
566    public int hashCode()
567    {
568      return 0;
569    }
570
571    /**
572     * No entries.
573     * @return The empty set.
574     */
575    public Set<K> keySet()
576    {
577      return EMPTY_SET;
578    }
579
580    /**
581     * Remove always succeeds, with null result.
582     * @param o The key of the mapping to remove.
583     * @return null, as there is never a mapping for o.
584     */
585    public V remove(Object o)
586    {
587      return null;
588    }
589
590    /**
591     * Size is always 0.
592     * @return 0.
593     */
594    public int size()
595    {
596      return 0;
597    }
598
599    /**
600     * No entries. Technically, EMPTY_SET, while more specific than a general
601     * Collection, will work. Besides, that's what the JDK uses!
602     * @return The empty set.
603     */
604    public Collection<V> values()
605    {
606      return EMPTY_SET;
607    }
608
609    /**
610     * The string never changes.
611     *
612     * @return the string "[]".
613     */
614    public String toString()
615    {
616      return "[]";
617    }
618  } // class EmptyMap
619
620
621  /**
622   * Compare two objects with or without a Comparator. If c is null, uses the
623   * natural ordering. Slightly slower than doing it inline if the JVM isn't
624   * clever, but worth it for removing a duplicate of the search code.
625   * Note: This code is also used in Arrays (for sort as well as search).
626   */
627  static final <T> int compare(T o1, T o2, Comparator<? super T> c)
628  {
629    return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
630  }
631
632  /**
633   * Perform a binary search of a List for a key, using the natural ordering of
634   * the elements. The list must be sorted (as by the sort() method) - if it is
635   * not, the behavior of this method is undefined, and may be an infinite
636   * loop. Further, the key must be comparable with every item in the list. If
637   * the list contains the key more than once, any one of them may be found.
638   * <p>
639   *
640   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
641   * and uses a linear search with O(n) link traversals and log(n) comparisons
642   * with {@link AbstractSequentialList} lists. Note: although the
643   * specification allows for an infinite loop if the list is unsorted, it will
644   * not happen in this (Classpath) implementation.
645   *
646   * @param l the list to search (must be sorted)
647   * @param key the value to search for
648   * @return the index at which the key was found, or -n-1 if it was not
649   *         found, where n is the index of the first value higher than key or
650   *         a.length if there is no such value
651   * @throws ClassCastException if key could not be compared with one of the
652   *         elements of l
653   * @throws NullPointerException if a null element has compareTo called
654   * @see #sort(List)
655   */
656  public static <T> int binarySearch(List<? extends Comparable<? super T>> l,
657                                     T key)
658  {
659    return binarySearch(l, key, null);
660  }
661
662  /**
663   * Perform a binary search of a List for a key, using a supplied Comparator.
664   * The list must be sorted (as by the sort() method with the same Comparator)
665   * - if it is not, the behavior of this method is undefined, and may be an
666   * infinite loop. Further, the key must be comparable with every item in the
667   * list. If the list contains the key more than once, any one of them may be
668   * found. If the comparator is null, the elements' natural ordering is used.
669   * <p>
670   *
671   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
672   * and uses a linear search with O(n) link traversals and log(n) comparisons
673   * with {@link AbstractSequentialList} lists. Note: although the
674   * specification allows for an infinite loop if the list is unsorted, it will
675   * not happen in this (Classpath) implementation.
676   *
677   * @param l the list to search (must be sorted)
678   * @param key the value to search for
679   * @param c the comparator by which the list is sorted
680   * @return the index at which the key was found, or -n-1 if it was not
681   *         found, where n is the index of the first value higher than key or
682   *         a.length if there is no such value
683   * @throws ClassCastException if key could not be compared with one of the
684   *         elements of l
685   * @throws NullPointerException if a null element is compared with natural
686   *         ordering (only possible when c is null)
687   * @see #sort(List, Comparator)
688   */
689  public static <T> int binarySearch(List<? extends T> l, T key,
690                                     Comparator<? super T> c)
691  {
692    int pos = 0;
693    int low = 0;
694    int hi = l.size() - 1;
695
696    // We use a linear search with log(n) comparisons using an iterator
697    // if the list is sequential-access.
698    if (isSequential(l))
699      {
700        ListIterator<T> itr = ((List<T>) l).listIterator();
701        int i = 0;
702        T o = itr.next(); // Assumes list is not empty (see isSequential)
703        boolean forward = true;
704        while (low <= hi)
705          {
706            pos = (low + hi) >>> 1;
707            if (i < pos)
708              {
709                if (!forward)
710                  itr.next(); // Changing direction first.
711                for ( ; i != pos; i++, o = itr.next())
712                  ;
713                forward = true;
714              }
715            else
716              {
717                if (forward)
718                  itr.previous(); // Changing direction first.
719                for ( ; i != pos; i--, o = itr.previous())
720                  ;
721                forward = false;
722              }
723            final int d = compare(o, key, c);
724            if (d == 0)
725              return pos;
726            else if (d > 0)
727              hi = pos - 1;
728            else
729              // This gets the insertion point right on the last loop
730              low = ++pos;
731          }
732      }
733    else
734      {
735        while (low <= hi)
736          {
737            pos = (low + hi) >>> 1;
738            final int d = compare(((List<T>) l).get(pos), key, c);
739            if (d == 0)
740              return pos;
741            else if (d > 0)
742              hi = pos - 1;
743            else
744              // This gets the insertion point right on the last loop
745              low = ++pos;
746          }
747      }
748
749    // If we failed to find it, we do the same whichever search we did.
750    return -pos - 1;
751  }
752
753  /**
754   * Copy one list to another. If the destination list is longer than the
755   * source list, the remaining elements are unaffected. This method runs in
756   * linear time.
757   *
758   * @param dest the destination list
759   * @param source the source list
760   * @throws IndexOutOfBoundsException if the destination list is shorter
761   *         than the source list (the destination will be unmodified)
762   * @throws UnsupportedOperationException if dest.listIterator() does not
763   *         support the set operation
764   */
765  public static <T> void copy(List<? super T> dest, List<? extends T> source)
766  {
767    int pos = source.size();
768    if (dest.size() < pos)
769      throw new IndexOutOfBoundsException("Source does not fit in dest");
770
771    Iterator<? extends T> i1 = source.iterator();
772    ListIterator<? super T> i2 = dest.listIterator();
773
774    while (--pos >= 0)
775      {
776        i2.next();
777        i2.set(i1.next());
778      }
779  }
780
781  /**
782   * Returns an Enumeration over a collection. This allows interoperability
783   * with legacy APIs that require an Enumeration as input.
784   *
785   * @param c the Collection to iterate over
786   * @return an Enumeration backed by an Iterator over c
787   */
788  public static <T> Enumeration<T> enumeration(Collection<T> c)
789  {
790    final Iterator<T> i = c.iterator();
791    return new Enumeration<T>()
792    {
793      /**
794       * Returns <code>true</code> if there are more elements to
795       * be enumerated.
796       *
797       * @return The result of <code>hasNext()</code>
798       *         called on the underlying iterator.
799       */
800      public final boolean hasMoreElements()
801      {
802        return i.hasNext();
803      }
804
805      /**
806       * Returns the next element to be enumerated.
807       *
808       * @return The result of <code>next()</code>
809       *         called on the underlying iterator.
810       */
811      public final T nextElement()
812      {
813        return i.next();
814      }
815    };
816  }
817
818  /**
819   * Replace every element of a list with a given value. This method runs in
820   * linear time.
821   *
822   * @param l the list to fill.
823   * @param val the object to vill the list with.
824   * @throws UnsupportedOperationException if l.listIterator() does not
825   *         support the set operation.
826   */
827  public static <T> void fill(List<? super T> l, T val)
828  {
829    ListIterator<? super T> itr = l.listIterator();
830    for (int i = l.size() - 1; i >= 0; --i)
831      {
832        itr.next();
833        itr.set(val);
834      }
835  }
836
837  /**
838   * Returns the starting index where the specified sublist first occurs
839   * in a larger list, or -1 if there is no matching position. If
840   * <code>target.size() &gt; source.size()</code>, this returns -1,
841   * otherwise this implementation uses brute force, checking for
842   * <code>source.sublist(i, i + target.size()).equals(target)</code>
843   * for all possible i.
844   *
845   * @param source the list to search
846   * @param target the sublist to search for
847   * @return the index where found, or -1
848   * @since 1.4
849   */
850  public static int indexOfSubList(List<?> source, List<?> target)
851  {
852    int ssize = source.size();
853    for (int i = 0, j = target.size(); j <= ssize; i++, j++)
854      if (source.subList(i, j).equals(target))
855        return i;
856    return -1;
857  }
858
859  /**
860   * Returns the starting index where the specified sublist last occurs
861   * in a larger list, or -1 if there is no matching position. If
862   * <code>target.size() &gt; source.size()</code>, this returns -1,
863   * otherwise this implementation uses brute force, checking for
864   * <code>source.sublist(i, i + target.size()).equals(target)</code>
865   * for all possible i.
866   *
867   * @param source the list to search
868   * @param target the sublist to search for
869   * @return the index where found, or -1
870   * @since 1.4
871   */
872  public static int lastIndexOfSubList(List<?> source, List<?> target)
873  {
874    int ssize = source.size();
875    for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--)
876      if (source.subList(i, j).equals(target))
877        return i;
878    return -1;
879  }
880
881  /**
882   * Returns an ArrayList holding the elements visited by a given
883   * Enumeration. This method exists for interoperability between legacy
884   * APIs and the new Collection API.
885   *
886   * @param e the enumeration to put in a list
887   * @return a list containing the enumeration elements
888   * @see ArrayList
889   * @since 1.4
890   */
891  public static <T> ArrayList<T> list(Enumeration<T> e)
892  {
893    ArrayList<T> l = new ArrayList<T>();
894    while (e.hasMoreElements())
895      l.add(e.nextElement());
896    return l;
897  }
898
899  /**
900   * Find the maximum element in a Collection, according to the natural
901   * ordering of the elements. This implementation iterates over the
902   * Collection, so it works in linear time.
903   *
904   * @param c the Collection to find the maximum element of
905   * @return the maximum element of c
906   * @exception NoSuchElementException if c is empty
907   * @exception ClassCastException if elements in c are not mutually comparable
908   * @exception NullPointerException if null.compareTo is called
909   */
910  public static <T extends Object & Comparable<? super T>>
911  T max(Collection<? extends T> c)
912  {
913    return max(c, null);
914  }
915
916  /**
917   * Find the maximum element in a Collection, according to a specified
918   * Comparator. This implementation iterates over the Collection, so it
919   * works in linear time.
920   *
921   * @param c the Collection to find the maximum element of
922   * @param order the Comparator to order the elements by, or null for natural
923   *        ordering
924   * @return the maximum element of c
925   * @throws NoSuchElementException if c is empty
926   * @throws ClassCastException if elements in c are not mutually comparable
927   * @throws NullPointerException if null is compared by natural ordering
928   *        (only possible when order is null)
929   */
930  public static <T> T max(Collection<? extends T> c,
931                          Comparator<? super T> order)
932  {
933    Iterator<? extends T> itr = c.iterator();
934    T max = itr.next(); // throws NoSuchElementException
935    int csize = c.size();
936    for (int i = 1; i < csize; i++)
937      {
938        T o = itr.next();
939        if (compare(max, o, order) < 0)
940          max = o;
941      }
942    return max;
943  }
944
945  /**
946   * Find the minimum element in a Collection, according to the natural
947   * ordering of the elements. This implementation iterates over the
948   * Collection, so it works in linear time.
949   *
950   * @param c the Collection to find the minimum element of
951   * @return the minimum element of c
952   * @throws NoSuchElementException if c is empty
953   * @throws ClassCastException if elements in c are not mutually comparable
954   * @throws NullPointerException if null.compareTo is called
955   */
956  public static <T extends Object & Comparable<? super T>>
957  T min(Collection<? extends T> c)
958  {
959    return min(c, null);
960  }
961
962  /**
963   * Find the minimum element in a Collection, according to a specified
964   * Comparator. This implementation iterates over the Collection, so it
965   * works in linear time.
966   *
967   * @param c the Collection to find the minimum element of
968   * @param order the Comparator to order the elements by, or null for natural
969   *        ordering
970   * @return the minimum element of c
971   * @throws NoSuchElementException if c is empty
972   * @throws ClassCastException if elements in c are not mutually comparable
973   * @throws NullPointerException if null is compared by natural ordering
974   *        (only possible when order is null)
975   */
976  public static <T> T min(Collection<? extends T> c,
977                          Comparator<? super T> order)
978  {
979    Iterator<? extends T> itr = c.iterator();
980    T min = itr.next(); // throws NoSuchElementExcception
981    int csize = c.size();
982    for (int i = 1; i < csize; i++)
983      {
984        T o = itr.next();
985        if (compare(min, o, order) > 0)
986          min = o;
987      }
988    return min;
989  }
990
991  /**
992   * Creates an immutable list consisting of the same object repeated n times.
993   * The returned object is tiny, consisting of only a single reference to the
994   * object and a count of the number of elements. It is Serializable, and
995   * implements RandomAccess. You can use it in tandem with List.addAll for
996   * fast list construction.
997   *
998   * @param n the number of times to repeat the object
999   * @param o the object to repeat
1000   * @return a List consisting of n copies of o
1001   * @throws IllegalArgumentException if n &lt; 0
1002   * @see List#addAll(Collection)
1003   * @see Serializable
1004   * @see RandomAccess
1005   */
1006  public static <T> List<T> nCopies(final int n, final T o)
1007  {
1008    return new CopiesList<T>(n, o);
1009  }
1010
1011  /**
1012   * The implementation of {@link #nCopies(int, Object)}. This class name
1013   * is required for compatibility with Sun's JDK serializability.
1014   *
1015   * @author Eric Blake (ebb9@email.byu.edu)
1016   */
1017  private static final class CopiesList<T> extends AbstractList<T>
1018    implements Serializable, RandomAccess
1019  {
1020    /**
1021     * Compatible with JDK 1.4.
1022     */
1023    private static final long serialVersionUID = 2739099268398711800L;
1024
1025    /**
1026     * The count of elements in this list.
1027     * @serial the list size
1028     */
1029    private final int n;
1030
1031    /**
1032     * The repeated list element.
1033     * @serial the list contents
1034     */
1035    private final T element;
1036
1037    /**
1038     * Constructs the list.
1039     *
1040     * @param n the count
1041     * @param o the object
1042     * @throws IllegalArgumentException if n &lt; 0
1043     */
1044    CopiesList(int n, T o)
1045    {
1046      if (n < 0)
1047        throw new IllegalArgumentException();
1048      this.n = n;
1049      element = o;
1050    }
1051
1052    /**
1053     * The size is fixed.
1054     * @return The size of the list.
1055     */
1056    public int size()
1057    {
1058      return n;
1059    }
1060
1061    /**
1062     * The same element is returned.
1063     * @param index The index of the element to be returned (irrelevant
1064     *        as the list contains only copies of <code>element</code>).
1065     * @return The element used by this list.
1066     */
1067    public T get(int index)
1068    {
1069      if (index < 0 || index >= n)
1070        throw new IndexOutOfBoundsException();
1071      return element;
1072    }
1073
1074    // The remaining methods are optional, but provide a performance
1075    // advantage by not allocating unnecessary iterators in AbstractList.
1076    /**
1077     * This list only contains one element.
1078     * @param o The object to search for.
1079     * @return <code>true</code> if o is the element used by this list.
1080     */
1081    public boolean contains(Object o)
1082    {
1083      return n > 0 && equals(o, element);
1084    }
1085
1086    /**
1087     * The index is either 0 or -1.
1088     * @param o The object to find the index of.
1089     * @return 0 if <code>o == element</code>, -1 if not.
1090     */
1091    public int indexOf(Object o)
1092    {
1093      return (n > 0 && equals(o, element)) ? 0 : -1;
1094    }
1095
1096    /**
1097     * The index is either n-1 or -1.
1098     * @param o The object to find the last index of.
1099     * @return The last index in the list if <code>o == element</code>,
1100     *         -1 if not.
1101     */
1102    public int lastIndexOf(Object o)
1103    {
1104      return equals(o, element) ? n - 1 : -1;
1105    }
1106
1107    /**
1108     * A subList is just another CopiesList.
1109     * @param from The starting bound of the sublist.
1110     * @param to The ending bound of the sublist.
1111     * @return A list of copies containing <code>from - to</code>
1112     *         elements, all of which are equal to the element
1113     *         used by this list.
1114     */
1115    public List<T> subList(int from, int to)
1116    {
1117      if (from < 0 || to > n)
1118        throw new IndexOutOfBoundsException();
1119      return new CopiesList<T>(to - from, element);
1120    }
1121
1122    /**
1123     * The array is easy.
1124     * @return An array of size n filled with copies of
1125     *         the element used by this list.
1126     */
1127    public Object[] toArray()
1128    {
1129      Object[] a = new Object[n];
1130      Arrays.fill(a, element);
1131      return a;
1132    }
1133
1134    /**
1135     * The string is easy to generate.
1136     * @return A string representation of the list.
1137     */
1138    public String toString()
1139    {
1140      CPStringBuilder r = new CPStringBuilder("{");
1141      for (int i = n - 1; --i > 0; )
1142        r.append(element).append(", ");
1143      r.append(element).append("}");
1144      return r.toString();
1145    }
1146  } // class CopiesList
1147
1148  /**
1149   * Replace all instances of one object with another in the specified list.
1150   * The list does not change size. An element e is replaced if
1151   * <code>oldval == null ? e == null : oldval.equals(e)</code>.
1152   *
1153   * @param list the list to iterate over
1154   * @param oldval the element to replace
1155   * @param newval the new value for the element
1156   * @return <code>true</code> if a replacement occurred.
1157   * @throws UnsupportedOperationException if the list iterator does not allow
1158   *         for the set operation
1159   * @throws ClassCastException if newval is of a type which cannot be added
1160   *         to the list
1161   * @throws IllegalArgumentException if some other aspect of newval stops
1162   *         it being added to the list
1163   * @since 1.4
1164   */
1165  public static <T> boolean replaceAll(List<T> list, T oldval, T newval)
1166  {
1167    ListIterator<T> itr = list.listIterator();
1168    boolean replace_occured = false;
1169    for (int i = list.size(); --i >= 0; )
1170      if (AbstractCollection.equals(oldval, itr.next()))
1171        {
1172          itr.set(newval);
1173          replace_occured = true;
1174        }
1175    return replace_occured;
1176  }
1177
1178  /**
1179   * Reverse a given list. This method works in linear time.
1180   *
1181   * @param l the list to reverse
1182   * @throws UnsupportedOperationException if l.listIterator() does not
1183   *         support the set operation
1184   */
1185  public static void reverse(List<?> l)
1186  {
1187    ListIterator i1 = l.listIterator();
1188    int pos1 = 1;
1189    int pos2 = l.size();
1190    ListIterator i2 = l.listIterator(pos2);
1191    while (pos1 < pos2)
1192      {
1193        Object o1 = i1.next();
1194    Object o2 = i2.previous();
1195        i1.set(o2);
1196        i2.set(o1);
1197        ++pos1;
1198        --pos2;
1199      }
1200  }
1201
1202  /**
1203   * Get a comparator that implements the reverse of the ordering
1204   * specified by the given Comparator. If the Comparator is null,
1205   * this is equivalent to {@link #reverseOrder()}.  The return value
1206   * of this method is Serializable, if the specified Comparator is
1207   * either Serializable or null.
1208   *
1209   * @param c the comparator to invert
1210   * @return a comparator that imposes reverse ordering
1211   * @see Comparable
1212   * @see Serializable
1213   *
1214   * @since 1.5
1215   */
1216  public static <T> Comparator<T> reverseOrder(final Comparator<T> c)
1217  {
1218    if (c == null)
1219      return (Comparator<T>) rcInstance;
1220    return new ReverseComparator<T> ()
1221    {
1222      public int compare(T a, T b)
1223      {
1224        return - c.compare(a, b);
1225      }
1226    };
1227  }
1228
1229  /**
1230   * Get a comparator that implements the reverse of natural ordering. In
1231   * other words, this sorts Comparable objects opposite of how their
1232   * compareTo method would sort. This makes it easy to sort into reverse
1233   * order, by simply passing Collections.reverseOrder() to the sort method.
1234   * The return value of this method is Serializable.
1235   *
1236   * @return a comparator that imposes reverse natural ordering
1237   * @see Comparable
1238   * @see Serializable
1239   */
1240  public static <T> Comparator<T> reverseOrder()
1241  {
1242    return (Comparator<T>) rcInstance;
1243  }
1244
1245  /**
1246   * The object for {@link #reverseOrder()}.
1247   */
1248  private static final ReverseComparator rcInstance = new ReverseComparator();
1249
1250  /**
1251   * The implementation of {@link #reverseOrder()}. This class name
1252   * is required for compatibility with Sun's JDK serializability.
1253   *
1254   * @author Eric Blake (ebb9@email.byu.edu)
1255   */
1256  private static class ReverseComparator<T>
1257    implements Comparator<T>, Serializable
1258  {
1259    /**
1260     * Compatible with JDK 1.4.
1261     */
1262    private static final long serialVersionUID = 7207038068494060240L;
1263
1264    /**
1265     * A private constructor adds overhead.
1266     */
1267    ReverseComparator()
1268    {
1269    }
1270
1271    /**
1272     * Compare two objects in reverse natural order.
1273     *
1274     * @param a the first object
1275     * @param b the second object
1276     * @return &lt;, ==, or &gt; 0 according to b.compareTo(a)
1277     */
1278    public int compare(T a, T b)
1279    {
1280      return ((Comparable) b).compareTo(a);
1281    }
1282  }
1283
1284  /**
1285   * Rotate the elements in a list by a specified distance. After calling this
1286   * method, the element now at index <code>i</code> was formerly at index
1287   * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
1288   * <p>
1289   *
1290   * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
1291   * either <code>Collections.rotate(l, 4)</code> or
1292   * <code>Collections.rotate(l, -1)</code>, the new contents are
1293   * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
1294   * just a portion of the list. For example, to move element <code>a</code>
1295   * forward two positions in the original example, use
1296   * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
1297   * result in <code>[t, n, k, a, s]</code>.
1298   * <p>
1299   *
1300   * If the list is small or implements {@link RandomAccess}, the
1301   * implementation exchanges the first element to its destination, then the
1302   * displaced element, and so on until a circuit has been completed. The
1303   * process is repeated if needed on the second element, and so forth, until
1304   * all elements have been swapped.  For large non-random lists, the
1305   * implementation breaks the list into two sublists at index
1306   * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
1307   * pieces, then reverses the overall list.
1308   *
1309   * @param list the list to rotate
1310   * @param distance the distance to rotate by; unrestricted in value
1311   * @throws UnsupportedOperationException if the list does not support set
1312   * @since 1.4
1313   */
1314  public static void rotate(List<?> list, int distance)
1315  {
1316    int size = list.size();
1317    if (size == 0)
1318      return;
1319    distance %= size;
1320    if (distance == 0)
1321      return;
1322    if (distance < 0)
1323      distance += size;
1324
1325    if (isSequential(list))
1326      {
1327        reverse(list);
1328        reverse(list.subList(0, distance));
1329        reverse(list.subList(distance, size));
1330      }
1331    else
1332      {
1333        // Determine the least common multiple of distance and size, as there
1334        // are (distance / LCM) loops to cycle through.
1335        int a = size;
1336        int lcm = distance;
1337        int b = a % lcm;
1338        while (b != 0)
1339          {
1340            a = lcm;
1341            lcm = b;
1342            b = a % lcm;
1343          }
1344
1345        // Now, make the swaps. We must take the remainder every time through
1346        // the inner loop so that we don't overflow i to negative values.
1347        List<Object> objList = (List<Object>) list;
1348        while (--lcm >= 0)
1349          {
1350            Object o = objList.get(lcm);
1351            for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
1352              o = objList.set(i, o);
1353            objList.set(lcm, o);
1354          }
1355      }
1356  }
1357
1358  /**
1359   * Shuffle a list according to a default source of randomness. The algorithm
1360   * used iterates backwards over the list, swapping each element with an
1361   * element randomly selected from the elements in positions less than or
1362   * equal to it (using r.nextInt(int)).
1363   * <p>
1364   *
1365   * This algorithm would result in a perfectly fair shuffle (that is, each
1366   * element would have an equal chance of ending up in any position) if r were
1367   * a perfect source of randomness. In practice the results are merely very
1368   * close to perfect.
1369   * <p>
1370   *
1371   * This method operates in linear time. To do this on large lists which do
1372   * not implement {@link RandomAccess}, a temporary array is used to acheive
1373   * this speed, since it would be quadratic access otherwise.
1374   *
1375   * @param l the list to shuffle
1376   * @throws UnsupportedOperationException if l.listIterator() does not
1377   *         support the set operation
1378   */
1379  public static void shuffle(List<?> l)
1380  {
1381    if (defaultRandom == null)
1382      {
1383        synchronized (Collections.class)
1384          {
1385            if (defaultRandom == null)
1386              defaultRandom = new Random();
1387          }
1388      }
1389    shuffle(l, defaultRandom);
1390  }
1391
1392  /**
1393   * Cache a single Random object for use by shuffle(List). This improves
1394   * performance as well as ensuring that sequential calls to shuffle() will
1395   * not result in the same shuffle order occurring: the resolution of
1396   * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
1397   */
1398  private static Random defaultRandom = null;
1399
1400  /**
1401   * Shuffle a list according to a given source of randomness. The algorithm
1402   * used iterates backwards over the list, swapping each element with an
1403   * element randomly selected from the elements in positions less than or
1404   * equal to it (using r.nextInt(int)).
1405   * <p>
1406   *
1407   * This algorithm would result in a perfectly fair shuffle (that is, each
1408   * element would have an equal chance of ending up in any position) if r were
1409   * a perfect source of randomness. In practise (eg if r = new Random()) the
1410   * results are merely very close to perfect.
1411   * <p>
1412   *
1413   * This method operates in linear time. To do this on large lists which do
1414   * not implement {@link RandomAccess}, a temporary array is used to acheive
1415   * this speed, since it would be quadratic access otherwise.
1416   *
1417   * @param l the list to shuffle
1418   * @param r the source of randomness to use for the shuffle
1419   * @throws UnsupportedOperationException if l.listIterator() does not
1420   *         support the set operation
1421   */
1422  public static void shuffle(List<?> l, Random r)
1423  {
1424    int lsize = l.size();
1425    List<Object> list = (List<Object>) l;
1426    ListIterator<Object> i = list.listIterator(lsize);
1427    boolean sequential = isSequential(l);
1428    Object[] a = null; // stores a copy of the list for the sequential case
1429
1430    if (sequential)
1431      a = list.toArray();
1432
1433    for (int pos = lsize - 1; pos > 0; --pos)
1434      {
1435        // Obtain a random position to swap with. pos + 1 is used so that the
1436        // range of the random number includes the current position.
1437        int swap = r.nextInt(pos + 1);
1438
1439        // Swap the desired element.
1440        Object o;
1441        if (sequential)
1442          {
1443            o = a[swap];
1444            a[swap] = i.previous();
1445          }
1446        else
1447          o = list.set(swap, i.previous());
1448
1449        i.set(o);
1450      }
1451  }
1452
1453  /**
1454   * Returns the frequency of the specified object within the supplied
1455   * collection.  The frequency represents the number of occurrences of
1456   * elements within the collection which return <code>true</code> when
1457   * compared with the object using the <code>equals</code> method.
1458   *
1459   * @param c the collection to scan for occurrences of the object.
1460   * @param o the object to locate occurrances of within the collection.
1461   * @throws NullPointerException if the collection is <code>null</code>.
1462   * @since 1.5
1463   */
1464  public static int frequency (Collection<?> c, Object o)
1465  {
1466    int result = 0;
1467    final Iterator<?> it = c.iterator();
1468    while (it.hasNext())
1469      {
1470        Object v = it.next();
1471        if (AbstractCollection.equals(o, v))
1472          ++result;
1473      }
1474    return result;
1475  }
1476
1477  /**
1478   * Adds all the specified elements to the given collection, in a similar
1479   * way to the <code>addAll</code> method of the <code>Collection</code>.
1480   * However, this is a variable argument method which allows the new elements
1481   * to be specified individually or in array form, as opposed to the list
1482   * required by the collection's <code>addAll</code> method.  This has
1483   * benefits in both simplicity (multiple elements can be added without
1484   * having to be wrapped inside a grouping structure) and efficiency
1485   * (as a redundant list doesn't have to be created to add an individual
1486   * set of elements or an array).
1487   *
1488   * @param c the collection to which the elements should be added.
1489   * @param a the elements to be added to the collection.
1490   * @return true if the collection changed its contents as a result.
1491   * @throws UnsupportedOperationException if the collection does not support
1492   *                                       addition.
1493   * @throws NullPointerException if one or more elements in a are null,
1494   *                              and the collection does not allow null
1495   *                              elements.  This exception is also thrown
1496   *                              if either <code>c</code> or <code>a</code>
1497   *                              are null.
1498   * @throws IllegalArgumentException if the collection won't allow an element
1499   *                                  to be added for some other reason.
1500   * @since 1.5
1501   */
1502  public static <T> boolean addAll(Collection<? super T> c, T... a)
1503  {
1504    boolean overall = false;
1505
1506    for (T element : a)
1507      {
1508        boolean result = c.add(element);
1509        if (result)
1510          overall = true;
1511      }
1512    return overall;
1513  }
1514
1515  /**
1516   * Returns true if the two specified collections have no elements in
1517   * common.  This method may give unusual results if one or both collections
1518   * use a non-standard equality test.  In the trivial case of comparing
1519   * a collection with itself, this method returns true if, and only if,
1520   * the collection is empty.
1521   *
1522   * @param c1 the first collection to compare.
1523   * @param c2 the second collection to compare.
1524   * @return true if the collections are disjoint.
1525   * @throws NullPointerException if either collection is null.
1526   * @since 1.5
1527   */
1528  public static boolean disjoint(Collection<?> c1, Collection<?> c2)
1529  {
1530    Collection<Object> oc1 = (Collection<Object>) c1;
1531    final Iterator<Object> it = oc1.iterator();
1532    while (it.hasNext())
1533      if (c2.contains(it.next()))
1534        return false;
1535    return true;
1536  }
1537
1538
1539  /**
1540   * Obtain an immutable Set consisting of a single element. The return value
1541   * of this method is Serializable.
1542   *
1543   * @param o the single element
1544   * @return an immutable Set containing only o
1545   * @see Serializable
1546   */
1547  public static <T> Set<T> singleton(T o)
1548  {
1549    return new SingletonSet<T>(o);
1550  }
1551
1552  /**
1553   * The implementation of {@link #singleton(Object)}. This class name
1554   * is required for compatibility with Sun's JDK serializability.
1555   *
1556   * @author Eric Blake (ebb9@email.byu.edu)
1557   */
1558  private static final class SingletonSet<T> extends AbstractSet<T>
1559    implements Serializable
1560  {
1561    /**
1562     * Compatible with JDK 1.4.
1563     */
1564    private static final long serialVersionUID = 3193687207550431679L;
1565
1566
1567    /**
1568     * The single element; package visible for use in nested class.
1569     * @serial the singleton
1570     */
1571    final T element;
1572
1573    /**
1574     * Construct a singleton.
1575     * @param o the element
1576     */
1577    SingletonSet(T o)
1578    {
1579      element = o;
1580    }
1581
1582    /**
1583     * The size: always 1!
1584     * @return 1.
1585     */
1586    public int size()
1587    {
1588      return 1;
1589    }
1590
1591    /**
1592     * Returns an iterator over the lone element.
1593     */
1594    public Iterator<T> iterator()
1595    {
1596      return new Iterator<T>()
1597      {
1598        /**
1599         * Flag to indicate whether or not the element has
1600         * been retrieved.
1601         */
1602        private boolean hasNext = true;
1603
1604        /**
1605         * Returns <code>true</code> if elements still remain to be
1606         * iterated through.
1607         *
1608         * @return <code>true</code> if the element has not yet been returned.
1609         */
1610        public boolean hasNext()
1611        {
1612          return hasNext;
1613        }
1614
1615        /**
1616         * Returns the element.
1617         *
1618         * @return The element used by this singleton.
1619         * @throws NoSuchElementException if the object
1620         *         has already been retrieved.
1621         */
1622        public T next()
1623        {
1624          if (hasNext)
1625          {
1626            hasNext = false;
1627            return element;
1628          }
1629          else
1630            throw new NoSuchElementException();
1631        }
1632
1633        /**
1634         * Removes the element from the singleton.
1635         * As this set is immutable, this will always
1636         * throw an exception.
1637         *
1638         * @throws UnsupportedOperationException as the
1639         *         singleton set doesn't support
1640         *         <code>remove()</code>.
1641         */
1642        public void remove()
1643        {
1644          throw new UnsupportedOperationException();
1645        }
1646      };
1647    }
1648
1649    // The remaining methods are optional, but provide a performance
1650    // advantage by not allocating unnecessary iterators in AbstractSet.
1651    /**
1652     * The set only contains one element.
1653     *
1654     * @param o The object to search for.
1655     * @return <code>true</code> if o == the element of the singleton.
1656     */
1657    public boolean contains(Object o)
1658    {
1659      return equals(o, element);
1660    }
1661
1662    /**
1663     * This is true if the other collection only contains the element.
1664     *
1665     * @param c A collection to compare against this singleton.
1666     * @return <code>true</code> if c only contains either no elements or
1667     *         elements equal to the element in this singleton.
1668     */
1669    public boolean containsAll(Collection<?> c)
1670    {
1671      Iterator<?> i = c.iterator();
1672      int pos = c.size();
1673      while (--pos >= 0)
1674        if (! equals(i.next(), element))
1675          return false;
1676      return true;
1677    }
1678
1679    /**
1680     * The hash is just that of the element.
1681     *
1682     * @return The hashcode of the element.
1683     */
1684    public int hashCode()
1685    {
1686      return hashCode(element);
1687    }
1688
1689    /**
1690     * Returning an array is simple.
1691     *
1692     * @return An array containing the element.
1693     */
1694    public Object[] toArray()
1695    {
1696      return new Object[] {element};
1697    }
1698
1699    /**
1700     * Obvious string.
1701     *
1702     * @return The string surrounded by enclosing
1703     *         square brackets.
1704     */
1705    public String toString()
1706    {
1707      return "[" + element + "]";
1708    }
1709  } // class SingletonSet
1710
1711  /**
1712   * Obtain an immutable List consisting of a single element. The return value
1713   * of this method is Serializable, and implements RandomAccess.
1714   *
1715   * @param o the single element
1716   * @return an immutable List containing only o
1717   * @see Serializable
1718   * @see RandomAccess
1719   * @since 1.3
1720   */
1721  public static <T> List<T> singletonList(T o)
1722  {
1723    return new SingletonList<T>(o);
1724  }
1725
1726  /**
1727   * The implementation of {@link #singletonList(Object)}. This class name
1728   * is required for compatibility with Sun's JDK serializability.
1729   *
1730   * @author Eric Blake (ebb9@email.byu.edu)
1731   */
1732  private static final class SingletonList<T> extends AbstractList<T>
1733    implements Serializable, RandomAccess
1734  {
1735    /**
1736     * Compatible with JDK 1.4.
1737     */
1738    private static final long serialVersionUID = 3093736618740652951L;
1739
1740    /**
1741     * The single element.
1742     * @serial the singleton
1743     */
1744    private final T element;
1745
1746    /**
1747     * Construct a singleton.
1748     * @param o the element
1749     */
1750    SingletonList(T o)
1751    {
1752      element = o;
1753    }
1754
1755    /**
1756     * The size: always 1!
1757     * @return 1.
1758     */
1759    public int size()
1760    {
1761      return 1;
1762    }
1763
1764    /**
1765     * Only index 0 is valid.
1766     * @param index The index of the element
1767     *        to retrieve.
1768     * @return The singleton's element if the
1769     *         index is 0.
1770     * @throws IndexOutOfBoundsException if
1771     *         index is not 0.
1772     */
1773    public T get(int index)
1774    {
1775      if (index == 0)
1776        return element;
1777      throw new IndexOutOfBoundsException();
1778    }
1779
1780    // The remaining methods are optional, but provide a performance
1781    // advantage by not allocating unnecessary iterators in AbstractList.
1782    /**
1783     * The set only contains one element.
1784     *
1785     * @param o The object to search for.
1786     * @return <code>true</code> if o == the singleton element.
1787     */
1788    public boolean contains(Object o)
1789    {
1790      return equals(o, element);
1791    }
1792
1793    /**
1794     * This is true if the other collection only contains the element.
1795     *
1796     * @param c A collection to compare against this singleton.
1797     * @return <code>true</code> if c only contains either no elements or
1798     *         elements equal to the element in this singleton.
1799     */
1800    public boolean containsAll(Collection<?> c)
1801    {
1802      Iterator<?> i = c.iterator();
1803      int pos = c.size();
1804      while (--pos >= 0)
1805        if (! equals(i.next(), element))
1806          return false;
1807      return true;
1808    }
1809
1810    /**
1811     * Speed up the hashcode computation.
1812     *
1813     * @return The hashcode of the list, based
1814     *         on the hashcode of the singleton element.
1815     */
1816    public int hashCode()
1817    {
1818      return 31 + hashCode(element);
1819    }
1820
1821    /**
1822     * Either the list has it or not.
1823     *
1824     * @param o The object to find the first index of.
1825     * @return 0 if o is the singleton element, -1 if not.
1826     */
1827    public int indexOf(Object o)
1828    {
1829      return equals(o, element) ? 0 : -1;
1830    }
1831
1832    /**
1833     * Either the list has it or not.
1834     *
1835     * @param o The object to find the last index of.
1836     * @return 0 if o is the singleton element, -1 if not.
1837     */
1838    public int lastIndexOf(Object o)
1839    {
1840      return equals(o, element) ? 0 : -1;
1841    }
1842
1843    /**
1844     * Sublists are limited in scope.
1845     *
1846     * @param from The starting bound for the sublist.
1847     * @param to The ending bound for the sublist.
1848     * @return Either an empty list if both bounds are
1849     *         0 or 1, or this list if the bounds are 0 and 1.
1850     * @throws IllegalArgumentException if <code>from > to</code>
1851     * @throws IndexOutOfBoundsException if either bound is greater
1852     *         than 1.
1853     */
1854    public List<T> subList(int from, int to)
1855    {
1856      if (from == to && (to == 0 || to == 1))
1857        return EMPTY_LIST;
1858      if (from == 0 && to == 1)
1859        return this;
1860      if (from > to)
1861        throw new IllegalArgumentException();
1862      throw new IndexOutOfBoundsException();
1863    }
1864
1865    /**
1866     * Returning an array is simple.
1867     *
1868     * @return An array containing the element.
1869     */
1870    public Object[] toArray()
1871    {
1872      return new Object[] {element};
1873    }
1874
1875    /**
1876     * Obvious string.
1877     *
1878     * @return The string surrounded by enclosing
1879     *         square brackets.
1880     */
1881    public String toString()
1882    {
1883      return "[" + element + "]";
1884    }
1885  } // class SingletonList
1886
1887  /**
1888   * Obtain an immutable Map consisting of a single key-value pair.
1889   * The return value of this method is Serializable.
1890   *
1891   * @param key the single key
1892   * @param value the single value
1893   * @return an immutable Map containing only the single key-value pair
1894   * @see Serializable
1895   * @since 1.3
1896   */
1897  public static <K, V> Map<K, V> singletonMap(K key, V value)
1898  {
1899    return new SingletonMap<K, V>(key, value);
1900  }
1901
1902  /**
1903   * The implementation of {@link #singletonMap(Object, Object)}. This class
1904   * name is required for compatibility with Sun's JDK serializability.
1905   *
1906   * @author Eric Blake (ebb9@email.byu.edu)
1907   */
1908  private static final class SingletonMap<K, V> extends AbstractMap<K, V>
1909    implements Serializable
1910  {
1911    /**
1912     * Compatible with JDK 1.4.
1913     */
1914    private static final long serialVersionUID = -6979724477215052911L;
1915
1916    /**
1917     * The single key.
1918     * @serial the singleton key
1919     */
1920    private final K k;
1921
1922    /**
1923     * The corresponding value.
1924     * @serial the singleton value
1925     */
1926    private final V v;
1927
1928    /**
1929     * Cache the entry set.
1930     */
1931    private transient Set<Map.Entry<K, V>> entries;
1932
1933    /**
1934     * Construct a singleton.
1935     * @param key the key
1936     * @param value the value
1937     */
1938    SingletonMap(K key, V value)
1939    {
1940      k = key;
1941      v = value;
1942    }
1943
1944    /**
1945     * There is a single immutable entry.
1946     *
1947     * @return A singleton containing the map entry.
1948     */
1949    public Set<Map.Entry<K, V>> entrySet()
1950    {
1951      if (entries == null)
1952        {
1953          Map.Entry<K,V> entry = new AbstractMap.SimpleEntry<K, V>(k, v)
1954          {
1955            /**
1956             * Sets the value of the map entry to the supplied value.
1957             * An exception is always thrown, as the map is immutable.
1958             *
1959             * @param o The new value.
1960             * @return The old value.
1961             * @throws UnsupportedOperationException as setting the value
1962             *         is not supported.
1963             */
1964            public V setValue(V o)
1965            {
1966              throw new UnsupportedOperationException();
1967            }
1968          };
1969          entries = singleton(entry);
1970        }
1971      return entries;
1972    }
1973
1974    // The remaining methods are optional, but provide a performance
1975    // advantage by not allocating unnecessary iterators in AbstractMap.
1976    /**
1977     * Single entry.
1978     *
1979     * @param key The key to look for.
1980     * @return <code>true</code> if the key is the same as the one used by
1981     *         this map.
1982     */
1983    public boolean containsKey(Object key)
1984    {
1985      return equals(key, k);
1986    }
1987
1988    /**
1989     * Single entry.
1990     *
1991     * @param value The value to look for.
1992     * @return <code>true</code> if the value is the same as the one used by
1993     *         this map.
1994     */
1995    public boolean containsValue(Object value)
1996    {
1997      return equals(value, v);
1998    }
1999
2000    /**
2001     * Single entry.
2002     *
2003     * @param key The key of the value to be retrieved.
2004     * @return The singleton value if the key is the same as the
2005     *         singleton key, null otherwise.
2006     */
2007    public V get(Object key)
2008    {
2009      return equals(key, k) ? v : null;
2010    }
2011
2012    /**
2013     * Calculate the hashcode directly.
2014     *
2015     * @return The hashcode computed from the singleton key
2016     *         and the singleton value.
2017     */
2018    public int hashCode()
2019    {
2020      return hashCode(k) ^ hashCode(v);
2021    }
2022
2023    /**
2024     * Return the keyset.
2025     *
2026     * @return A singleton containing the key.
2027     */
2028    public Set<K> keySet()
2029    {
2030      if (keys == null)
2031        keys = singleton(k);
2032      return keys;
2033    }
2034
2035    /**
2036     * The size: always 1!
2037     *
2038     * @return 1.
2039     */
2040    public int size()
2041    {
2042      return 1;
2043    }
2044
2045    /**
2046     * Return the values. Technically, a singleton, while more specific than
2047     * a general Collection, will work. Besides, that's what the JDK uses!
2048     *
2049     * @return A singleton containing the value.
2050     */
2051    public Collection<V> values()
2052    {
2053      if (values == null)
2054        values = singleton(v);
2055      return values;
2056    }
2057
2058    /**
2059     * Obvious string.
2060     *
2061     * @return A string containing the string representations of the key
2062     *         and its associated value.
2063     */
2064    public String toString()
2065    {
2066      return "{" + k + "=" + v + "}";
2067    }
2068  } // class SingletonMap
2069
2070  /**
2071   * Sort a list according to the natural ordering of its elements. The list
2072   * must be modifiable, but can be of fixed size. The sort algorithm is
2073   * precisely that used by Arrays.sort(Object[]), which offers guaranteed
2074   * nlog(n) performance. This implementation dumps the list into an array,
2075   * sorts the array, and then iterates over the list setting each element from
2076   * the array.
2077   *
2078   * @param l the List to sort (<code>null</code> not permitted)
2079   * @throws ClassCastException if some items are not mutually comparable
2080   * @throws UnsupportedOperationException if the List is not modifiable
2081   * @throws NullPointerException if the list is <code>null</code>, or contains
2082   *     some element that is <code>null</code>.
2083   * @see Arrays#sort(Object[])
2084   */
2085  public static <T extends Comparable<? super T>> void sort(List<T> l)
2086  {
2087    sort(l, null);
2088  }
2089
2090  /**
2091   * Sort a list according to a specified Comparator. The list must be
2092   * modifiable, but can be of fixed size. The sort algorithm is precisely that
2093   * used by Arrays.sort(Object[], Comparator), which offers guaranteed
2094   * nlog(n) performance. This implementation dumps the list into an array,
2095   * sorts the array, and then iterates over the list setting each element from
2096   * the array.
2097   *
2098   * @param l the List to sort (<code>null</code> not permitted)
2099   * @param c the Comparator specifying the ordering for the elements, or
2100   *        <code>null</code> for natural ordering
2101   * @throws ClassCastException if c will not compare some pair of items
2102   * @throws UnsupportedOperationException if the List is not modifiable
2103   * @throws NullPointerException if the List is <code>null</code> or
2104   *         <code>null</code> is compared by natural ordering (only possible
2105   *         when c is <code>null</code>)
2106   *
2107   * @see Arrays#sort(Object[], Comparator)
2108   */
2109  public static <T> void sort(List<T> l, Comparator<? super T> c)
2110  {
2111    T[] a = (T[]) l.toArray();
2112    Arrays.sort(a, c);
2113    ListIterator<T> i = l.listIterator();
2114    for (int pos = 0, alen = a.length;  pos < alen;  pos++)
2115      {
2116        i.next();
2117        i.set(a[pos]);
2118      }
2119  }
2120
2121  /**
2122   * Swaps the elements at the specified positions within the list. Equal
2123   * positions have no effect.
2124   *
2125   * @param l the list to work on
2126   * @param i the first index to swap
2127   * @param j the second index
2128   * @throws UnsupportedOperationException if list.set is not supported
2129   * @throws IndexOutOfBoundsException if either i or j is &lt; 0 or &gt;=
2130   *         list.size()
2131   * @since 1.4
2132   */
2133  public static void swap(List<?> l, int i, int j)
2134  {
2135    List<Object> list = (List<Object>) l;
2136    list.set(i, list.set(j, list.get(i)));
2137  }
2138
2139
2140  /**
2141   * Returns a synchronized (thread-safe) collection wrapper backed by the
2142   * given collection. Notice that element access through the iterators
2143   * is thread-safe, but if the collection can be structurally modified
2144   * (adding or removing elements) then you should synchronize around the
2145   * iteration to avoid non-deterministic behavior:<br>
2146   * <pre>
2147   * Collection c = Collections.synchronizedCollection(new Collection(...));
2148   * ...
2149   * synchronized (c)
2150   *   {
2151   *     Iterator i = c.iterator();
2152   *     while (i.hasNext())
2153   *       foo(i.next());
2154   *   }
2155   * </pre><p>
2156   *
2157   * Since the collection might be a List or a Set, and those have incompatible
2158   * equals and hashCode requirements, this relies on Object's implementation
2159   * rather than passing those calls on to the wrapped collection. The returned
2160   * Collection implements Serializable, but can only be serialized if
2161   * the collection it wraps is likewise Serializable.
2162   *
2163   * @param c the collection to wrap
2164   * @return a synchronized view of the collection
2165   * @see Serializable
2166   */
2167  public static <T> Collection<T> synchronizedCollection(Collection<T> c)
2168  {
2169    return new SynchronizedCollection<T>(c);
2170  }
2171
2172  /**
2173   * The implementation of {@link #synchronizedCollection(Collection)}. This
2174   * class name is required for compatibility with Sun's JDK serializability.
2175   * Package visible, so that collections such as the one for
2176   * Hashtable.values() can specify which object to synchronize on.
2177   *
2178   * @author Eric Blake (ebb9@email.byu.edu)
2179   */
2180  static class SynchronizedCollection<T>
2181    implements Collection<T>, Serializable
2182  {
2183    /**
2184     * Compatible with JDK 1.4.
2185     */
2186    private static final long serialVersionUID = 3053995032091335093L;
2187
2188    /**
2189     * The wrapped collection. Package visible for use by subclasses.
2190     * @serial the real collection
2191     */
2192    final Collection<T> c;
2193
2194    /**
2195     * The object to synchronize on.  When an instance is created via public
2196     * methods, it will be this; but other uses like SynchronizedMap.values()
2197     * must specify another mutex. Package visible for use by subclasses.
2198     * @serial the lock
2199     */
2200    final Object mutex;
2201
2202    /**
2203     * Wrap a given collection.
2204     * @param c the collection to wrap
2205     * @throws NullPointerException if c is null
2206     */
2207    SynchronizedCollection(Collection<T> c)
2208    {
2209      this.c = c;
2210      mutex = this;
2211      if (c == null)
2212        throw new NullPointerException();
2213    }
2214
2215    /**
2216     * Called only by trusted code to specify the mutex as well as the
2217     * collection.
2218     * @param sync the mutex
2219     * @param c the collection
2220     */
2221    SynchronizedCollection(Object sync, Collection<T> c)
2222    {
2223      this.c = c;
2224      mutex = sync;
2225    }
2226
2227    /**
2228     * Adds the object to the underlying collection, first
2229     * obtaining a lock on the mutex.
2230     *
2231     * @param o The object to add.
2232     * @return <code>true</code> if the collection was modified as a result
2233     *         of this action.
2234     * @throws UnsupportedOperationException if this collection does not
2235     *         support the add operation.
2236     * @throws ClassCastException if o cannot be added to this collection due
2237     *         to its type.
2238     * @throws NullPointerException if o is null and this collection doesn't
2239     *         support the addition of null values.
2240     * @throws IllegalArgumentException if o cannot be added to this
2241     *         collection for some other reason.
2242     */
2243    public boolean add(T o)
2244    {
2245      synchronized (mutex)
2246        {
2247          return c.add(o);
2248        }
2249    }
2250
2251    /**
2252     * Adds the objects in col to the underlying collection, first
2253     * obtaining a lock on the mutex.
2254     *
2255     * @param col The collection to take the new objects from.
2256     * @return <code>true</code> if the collection was modified as a result
2257     *          of this action.
2258     * @throws UnsupportedOperationException if this collection does not
2259     *         support the addAll operation.
2260     * @throws ClassCastException if some element of col cannot be added to this
2261     *         collection due to its type.
2262     * @throws NullPointerException if some element of col is null and this
2263     *         collection does not support the addition of null values.
2264     * @throws NullPointerException if col itself is null.
2265     * @throws IllegalArgumentException if some element of col cannot be added
2266     *         to this collection for some other reason.
2267     */
2268    public boolean addAll(Collection<? extends T> col)
2269    {
2270      synchronized (mutex)
2271        {
2272          return c.addAll(col);
2273        }
2274    }
2275
2276    /**
2277     * Removes all objects from the underlying collection,
2278     * first obtaining a lock on the mutex.
2279     *
2280     * @throws UnsupportedOperationException if this collection does not
2281     *         support the clear operation.
2282     */
2283    public void clear()
2284    {
2285      synchronized (mutex)
2286        {
2287          c.clear();
2288        }
2289    }
2290
2291    /**
2292     * Checks for the existence of o within the underlying
2293     * collection, first obtaining a lock on the mutex.
2294     *
2295     * @param o the element to look for.
2296     * @return <code>true</code> if this collection contains at least one
2297     *         element e such that <code>o == null ? e == null : o.equals(e)</code>.
2298     * @throws ClassCastException if the type of o is not a valid type for this
2299     *         collection.
2300     * @throws NullPointerException if o is null and this collection doesn't
2301     *         support null values.
2302     */
2303    public boolean contains(Object o)
2304    {
2305      synchronized (mutex)
2306        {
2307          return c.contains(o);
2308        }
2309    }
2310
2311    /**
2312     * Checks for the existence of each object in cl
2313     * within the underlying collection, first obtaining
2314     * a lock on the mutex.
2315     *
2316     * @param c1 the collection to test for.
2317     * @return <code>true</code> if for every element o in c, contains(o)
2318     *         would return <code>true</code>.
2319     * @throws ClassCastException if the type of any element in cl is not a valid
2320     *         type for this collection.
2321     * @throws NullPointerException if some element of cl is null and this
2322     *         collection does not support null values.
2323     * @throws NullPointerException if cl itself is null.
2324     */
2325    public boolean containsAll(Collection<?> c1)
2326    {
2327      synchronized (mutex)
2328        {
2329          return c.containsAll(c1);
2330        }
2331    }
2332
2333    /**
2334     * Returns <code>true</code> if there are no objects in the underlying
2335     * collection.  A lock on the mutex is obtained before the
2336     * check is performed.
2337     *
2338     * @return <code>true</code> if this collection contains no elements.
2339     */
2340    public boolean isEmpty()
2341    {
2342      synchronized (mutex)
2343        {
2344          return c.isEmpty();
2345        }
2346    }
2347
2348    /**
2349     * Returns a synchronized iterator wrapper around the underlying
2350     * collection's iterator.  A lock on the mutex is obtained before
2351     * retrieving the collection's iterator.
2352     *
2353     * @return An iterator over the elements in the underlying collection,
2354     *         which returns each element in any order.
2355     */
2356    public Iterator<T> iterator()
2357    {
2358      synchronized (mutex)
2359        {
2360          return new SynchronizedIterator<T>(mutex, c.iterator());
2361        }
2362    }
2363
2364    /**
2365     * Removes the specified object from the underlying collection,
2366     * first obtaining a lock on the mutex.
2367     *
2368     * @param o The object to remove.
2369     * @return <code>true</code> if the collection changed as a result of this call, that is,
2370     *         if the collection contained at least one occurrence of o.
2371     * @throws UnsupportedOperationException if this collection does not
2372     *         support the remove operation.
2373     * @throws ClassCastException if the type of o is not a valid type
2374     *         for this collection.
2375     * @throws NullPointerException if o is null and the collection doesn't
2376     *         support null values.
2377     */
2378    public boolean remove(Object o)
2379    {
2380      synchronized (mutex)
2381        {
2382          return c.remove(o);
2383        }
2384    }
2385
2386    /**
2387     * Removes all elements, e, of the underlying
2388     * collection for which <code>col.contains(e)</code>
2389     * returns <code>true</code>.  A lock on the mutex is obtained
2390     * before the operation proceeds.
2391     *
2392     * @param col The collection of objects to be removed.
2393     * @return <code>true</code> if this collection was modified as a result of this call.
2394     * @throws UnsupportedOperationException if this collection does not
2395     *   support the removeAll operation.
2396     * @throws ClassCastException if the type of any element in c is not a valid
2397     *   type for this collection.
2398     * @throws NullPointerException if some element of c is null and this
2399     *   collection does not support removing null values.
2400     * @throws NullPointerException if c itself is null.
2401     */
2402    public boolean removeAll(Collection<?> col)
2403    {
2404      synchronized (mutex)
2405        {
2406          return c.removeAll(col);
2407        }
2408    }
2409
2410    /**
2411     * Retains all elements, e, of the underlying
2412     * collection for which <code>col.contains(e)</code>
2413     * returns <code>true</code>.  That is, every element that doesn't
2414     * exist in col is removed.  A lock on the mutex is obtained
2415     * before the operation proceeds.
2416     *
2417     * @param col The collection of objects to be removed.
2418     * @return <code>true</code> if this collection was modified as a result of this call.
2419     * @throws UnsupportedOperationException if this collection does not
2420     *   support the removeAll operation.
2421     * @throws ClassCastException if the type of any element in c is not a valid
2422     *   type for this collection.
2423     * @throws NullPointerException if some element of c is null and this
2424     *   collection does not support removing null values.
2425     * @throws NullPointerException if c itself is null.
2426     */
2427    public boolean retainAll(Collection<?> col)
2428    {
2429      synchronized (mutex)
2430        {
2431          return c.retainAll(col);
2432        }
2433    }
2434
2435    /**
2436     * Retrieves the size of the underlying collection.
2437     * A lock on the mutex is obtained before the collection
2438     * is accessed.
2439     *
2440     * @return The size of the collection.
2441     */
2442    public int size()
2443    {
2444      synchronized (mutex)
2445        {
2446          return c.size();
2447        }
2448    }
2449
2450    /**
2451     * Returns an array containing each object within the underlying
2452     * collection.  A lock is obtained on the mutex before the collection
2453     * is accessed.
2454     *
2455     * @return An array of objects, matching the collection in size.  The
2456     *         elements occur in any order.
2457     */
2458    public Object[] toArray()
2459    {
2460      synchronized (mutex)
2461        {
2462          return c.toArray();
2463        }
2464    }
2465
2466    /**
2467     * Copies the elements in the underlying collection to the supplied
2468     * array.  If <code>a.length < size()</code>, a new array of the
2469     * same run-time type is created, with a size equal to that of
2470     * the collection.  If <code>a.length > size()</code>, then the
2471     * elements from 0 to <code>size() - 1</code> contain the elements
2472     * from this collection.  The following element is set to null
2473     * to indicate the end of the collection objects.  However, this
2474     * only makes a difference if null is not a permitted value within
2475     * the collection.
2476     * Before the copying takes place, a lock is obtained on the mutex.
2477     *
2478     * @param a An array to copy elements to.
2479     * @return An array containing the elements of the underlying collection.
2480     * @throws ArrayStoreException if the type of any element of the
2481     *         collection is not a subtype of the element type of a.
2482     */
2483    public <T> T[] toArray(T[] a)
2484    {
2485      synchronized (mutex)
2486        {
2487          return c.toArray(a);
2488        }
2489    }
2490
2491    /**
2492     * Returns a string representation of the underlying collection.
2493     * A lock is obtained on the mutex before the string is created.
2494     *
2495     * @return A string representation of the collection.
2496     */
2497    public String toString()
2498    {
2499      synchronized (mutex)
2500        {
2501          return c.toString();
2502        }
2503    }
2504  } // class SynchronizedCollection
2505
2506  /**
2507   * The implementation of the various iterator methods in the
2508   * synchronized classes. These iterators must "sync" on the same object
2509   * as the collection they iterate over.
2510   *
2511   * @author Eric Blake (ebb9@email.byu.edu)
2512   */
2513  private static class SynchronizedIterator<T> implements Iterator<T>
2514  {
2515    /**
2516     * The object to synchronize on. Package visible for use by subclass.
2517     */
2518    final Object mutex;
2519
2520    /**
2521     * The wrapped iterator.
2522     */
2523    private final Iterator<T> i;
2524
2525    /**
2526     * Only trusted code creates a wrapper, with the specified sync.
2527     * @param sync the mutex
2528     * @param i the wrapped iterator
2529     */
2530    SynchronizedIterator(Object sync, Iterator<T> i)
2531    {
2532      this.i = i;
2533      mutex = sync;
2534    }
2535
2536    /**
2537     * Retrieves the next object in the underlying collection.
2538     * A lock is obtained on the mutex before the collection is accessed.
2539     *
2540     * @return The next object in the collection.
2541     * @throws NoSuchElementException if there are no more elements
2542     */
2543    public T next()
2544    {
2545      synchronized (mutex)
2546        {
2547          return i.next();
2548        }
2549    }
2550
2551    /**
2552     * Returns <code>true</code> if objects can still be retrieved from the iterator
2553     * using <code>next()</code>.  A lock is obtained on the mutex before
2554     * the collection is accessed.
2555     *
2556     * @return <code>true</code> if at least one element is still to be returned by
2557     *         <code>next()</code>.
2558     */
2559    public boolean hasNext()
2560    {
2561      synchronized (mutex)
2562        {
2563          return i.hasNext();
2564        }
2565    }
2566
2567    /**
2568     * Removes the object that was last returned by <code>next()</code>
2569     * from the underlying collection.  Only one call to this method is
2570     * allowed per call to the <code>next()</code> method, and it does
2571     * not affect the value that will be returned by <code>next()</code>.
2572     * Thus, if element n was retrieved from the collection by
2573     * <code>next()</code>, it is this element that gets removed.
2574     * Regardless of whether this takes place or not, element n+1 is
2575     * still returned on the subsequent <code>next()</code> call.
2576     *
2577     * @throws IllegalStateException if next has not yet been called or remove
2578     *         has already been called since the last call to next.
2579     * @throws UnsupportedOperationException if this Iterator does not support
2580     *         the remove operation.
2581     */
2582    public void remove()
2583    {
2584      synchronized (mutex)
2585        {
2586          i.remove();
2587        }
2588    }
2589  } // class SynchronizedIterator
2590
2591  /**
2592   * Returns a synchronized (thread-safe) list wrapper backed by the
2593   * given list. Notice that element access through the iterators
2594   * is thread-safe, but if the list can be structurally modified
2595   * (adding or removing elements) then you should synchronize around the
2596   * iteration to avoid non-deterministic behavior:<br>
2597   * <pre>
2598   * List l = Collections.synchronizedList(new List(...));
2599   * ...
2600   * synchronized (l)
2601   *   {
2602   *     Iterator i = l.iterator();
2603   *     while (i.hasNext())
2604   *       foo(i.next());
2605   *   }
2606   * </pre><p>
2607   *
2608   * The returned List implements Serializable, but can only be serialized if
2609   * the list it wraps is likewise Serializable. In addition, if the wrapped
2610   * list implements RandomAccess, this does too.
2611   *
2612   * @param l the list to wrap
2613   * @return a synchronized view of the list
2614   * @see Serializable
2615   * @see RandomAccess
2616   */
2617  public static <T> List<T> synchronizedList(List<T> l)
2618  {
2619    if (l instanceof RandomAccess)
2620      return new SynchronizedRandomAccessList<T>(l);
2621    return new SynchronizedList<T>(l);
2622  }
2623
2624  /**
2625   * The implementation of {@link #synchronizedList(List)} for sequential
2626   * lists. This class name is required for compatibility with Sun's JDK
2627   * serializability. Package visible, so that lists such as Vector.subList()
2628   * can specify which object to synchronize on.
2629   *
2630   * @author Eric Blake (ebb9@email.byu.edu)
2631   */
2632  static class SynchronizedList<T> extends SynchronizedCollection<T>
2633    implements List<T>
2634  {
2635    /**
2636     * Compatible with JDK 1.4.
2637     */
2638    private static final long serialVersionUID = -7754090372962971524L;
2639
2640    /**
2641     * The wrapped list; stored both here and in the superclass to avoid
2642     * excessive casting. Package visible for use by subclass.
2643     * @serial the wrapped list
2644     */
2645    final List<T> list;
2646
2647    /**
2648     * Wrap a given list.
2649     * @param l the list to wrap
2650     * @throws NullPointerException if l is null
2651     */
2652    SynchronizedList(List<T> l)
2653    {
2654      super(l);
2655      list = l;
2656    }
2657
2658    /**
2659     * Called only by trusted code to specify the mutex as well as the list.
2660     * @param sync the mutex
2661     * @param l the list
2662     */
2663    SynchronizedList(Object sync, List<T> l)
2664    {
2665      super(sync, l);
2666      list = l;
2667    }
2668
2669  /**
2670   * Insert an element into the underlying list at a given position (optional
2671   * operation).  This shifts all existing elements from that position to the
2672   * end one index to the right. This version of add has no return, since it is
2673   * assumed to always succeed if there is no exception.  Before the
2674   * addition takes place, a lock is obtained on the mutex.
2675   *
2676   * @param index the location to insert the item
2677   * @param o the object to insert
2678   * @throws UnsupportedOperationException if this list does not support the
2679   *         add operation
2680   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
2681   * @throws ClassCastException if o cannot be added to this list due to its
2682   *         type
2683   * @throws IllegalArgumentException if o cannot be added to this list for
2684   *         some other reason
2685   * @throws NullPointerException if o is null and this list doesn't support
2686   *         the addition of null values.
2687   */
2688    public void add(int index, T o)
2689    {
2690      synchronized (mutex)
2691        {
2692          list.add(index, o);
2693        }
2694    }
2695
2696  /**
2697   * Add the contents of a collection to the underlying list at the given
2698   * index (optional operation).  If the list imposes restraints on what
2699   * can be inserted, such as no null elements, this should be documented.
2700   * A lock is obtained on the mutex before any of the elements are added.
2701   *
2702   * @param index the index at which to insert
2703   * @param c the collection to add
2704   * @return <code>true</code>, as defined by Collection for a modified list
2705   * @throws UnsupportedOperationException if this list does not support the
2706   *         add operation
2707   * @throws ClassCastException if o cannot be added to this list due to its
2708   *         type
2709   * @throws IllegalArgumentException if o cannot be added to this list for
2710   *         some other reason
2711   * @throws NullPointerException if o is null and this list doesn't support
2712   *         the addition of null values.
2713   */
2714    public boolean addAll(int index, Collection<? extends T> c)
2715    {
2716      synchronized (mutex)
2717        {
2718          return list.addAll(index, c);
2719        }
2720    }
2721
2722   /**
2723    * Tests whether the underlying list is equal to the supplied object.
2724    * The object is deemed to be equal if it is also a <code>List</code>
2725    * of equal size and with the same elements (i.e. each element, e1,
2726    * in list, l1, and each element, e2, in l2, must return <code>true</code> for
2727    * <code>e1 == null ? e2 == null : e1.equals(e2)</code>.  Before the
2728    * comparison is made, a lock is obtained on the mutex.
2729    *
2730    * @param o The object to test for equality with the underlying list.
2731    * @return <code>true</code> if o is equal to the underlying list under the above
2732    *         definition.
2733    */
2734    public boolean equals(Object o)
2735    {
2736      synchronized (mutex)
2737        {
2738          return list.equals(o);
2739        }
2740    }
2741
2742    /**
2743     * Retrieves the object at the specified index.  A lock
2744     * is obtained on the mutex before the list is accessed.
2745     *
2746     * @param index the index of the element to be returned
2747     * @return the element at index index in this list
2748     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2749     */
2750    public T get(int index)
2751    {
2752      synchronized (mutex)
2753        {
2754          return list.get(index);
2755        }
2756    }
2757
2758    /**
2759     * Obtains a hashcode for the underlying list, first obtaining
2760     * a lock on the mutex.  The calculation of the hashcode is
2761     * detailed in the documentation for the <code>List</code>
2762     * interface.
2763     *
2764     * @return The hashcode of the underlying list.
2765     * @see List#hashCode()
2766     */
2767    public int hashCode()
2768    {
2769      synchronized (mutex)
2770        {
2771          return list.hashCode();
2772        }
2773    }
2774
2775    /**
2776     * Obtain the first index at which a given object is to be found in the
2777     * underlying list.  A lock is obtained on the mutex before the list is
2778     * accessed.
2779     *
2780     * @param o the object to search for
2781     * @return the least integer n such that <code>o == null ? get(n) == null :
2782     *         o.equals(get(n))</code>, or -1 if there is no such index.
2783     * @throws ClassCastException if the type of o is not a valid
2784     *         type for this list.
2785     * @throws NullPointerException if o is null and this
2786     *         list does not support null values.
2787     */
2788
2789    public int indexOf(Object o)
2790    {
2791      synchronized (mutex)
2792        {
2793          return list.indexOf(o);
2794        }
2795    }
2796
2797    /**
2798     * Obtain the last index at which a given object is to be found in this
2799     * underlying list.  A lock is obtained on the mutex before the list
2800     * is accessed.
2801     *
2802     * @return the greatest integer n such that <code>o == null ? get(n) == null
2803     *         : o.equals(get(n))</code>, or -1 if there is no such index.
2804     * @throws ClassCastException if the type of o is not a valid
2805     *         type for this list.
2806     * @throws NullPointerException if o is null and this
2807     *         list does not support null values.
2808     */
2809    public int lastIndexOf(Object o)
2810    {
2811      synchronized (mutex)
2812        {
2813          return list.lastIndexOf(o);
2814        }
2815    }
2816
2817    /**
2818     * Retrieves a synchronized wrapper around the underlying list's
2819     * list iterator.  A lock is obtained on the mutex before the
2820     * list iterator is retrieved.
2821     *
2822     * @return A list iterator over the elements in the underlying list.
2823     *         The list iterator allows additional list-specific operations
2824     *         to be performed, in addition to those supplied by the
2825     *         standard iterator.
2826     */
2827    public ListIterator<T> listIterator()
2828    {
2829      synchronized (mutex)
2830        {
2831          return new SynchronizedListIterator<T>(mutex, list.listIterator());
2832        }
2833    }
2834
2835    /**
2836     * Retrieves a synchronized wrapper around the underlying list's
2837     * list iterator.  A lock is obtained on the mutex before the
2838     * list iterator is retrieved.  The iterator starts at the
2839     * index supplied, leading to the element at that index being
2840     * the first one returned by <code>next()</code>.  Calling
2841     * <code>previous()</code> from this initial position returns
2842     * index - 1.
2843     *
2844     * @param index the position, between 0 and size() inclusive, to begin the
2845     *        iteration from
2846     * @return A list iterator over the elements in the underlying list.
2847     *         The list iterator allows additional list-specific operations
2848     *         to be performed, in addition to those supplied by the
2849     *         standard iterator.
2850     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
2851     */
2852    public ListIterator<T> listIterator(int index)
2853    {
2854      synchronized (mutex)
2855        {
2856          return new SynchronizedListIterator<T>(mutex,
2857                                                 list.listIterator(index));
2858        }
2859    }
2860
2861    /**
2862     * Remove the element at a given position in the underlying list (optional
2863     * operation).  All remaining elements are shifted to the left to fill the gap.
2864     * A lock on the mutex is obtained before the element is removed.
2865     *
2866     * @param index the position within the list of the object to remove
2867     * @return the object that was removed
2868     * @throws UnsupportedOperationException if this list does not support the
2869     *         remove operation
2870     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2871     */
2872    public T remove(int index)
2873    {
2874      synchronized (mutex)
2875        {
2876          return list.remove(index);
2877        }
2878    }
2879
2880  /**
2881   * Replace an element of the underlying list with another object (optional
2882   * operation).  A lock is obtained on the mutex before the element is
2883   * replaced.
2884   *
2885   * @param index the position within this list of the element to be replaced
2886   * @param o the object to replace it with
2887   * @return the object that was replaced
2888   * @throws UnsupportedOperationException if this list does not support the
2889   *         set operation.
2890   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2891   * @throws ClassCastException if o cannot be added to this list due to its
2892   *         type
2893   * @throws IllegalArgumentException if o cannot be added to this list for
2894   *         some other reason
2895   * @throws NullPointerException if o is null and this
2896   *         list does not support null values.
2897   */
2898    public T set(int index, T o)
2899    {
2900      synchronized (mutex)
2901        {
2902          return list.set(index, o);
2903        }
2904    }
2905
2906    /**
2907     * Obtain a List view of a subsection of the underlying list, from fromIndex
2908     * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2909     * sublist is empty. The returned list should be modifiable if and only
2910     * if this list is modifiable. Changes to the returned list should be
2911     * reflected in this list. If this list is structurally modified in
2912     * any way other than through the returned list, the result of any subsequent
2913     * operations on the returned list is undefined.  A lock is obtained
2914     * on the mutex before the creation of the sublist.  The returned list
2915     * is also synchronized, using the same mutex.
2916     *
2917     * @param fromIndex the index that the returned list should start from
2918     *        (inclusive)
2919     * @param toIndex the index that the returned list should go to (exclusive)
2920     * @return a List backed by a subsection of this list
2921     * @throws IndexOutOfBoundsException if fromIndex &lt; 0
2922     *         || toIndex &gt; size() || fromIndex &gt; toIndex
2923     */
2924    public List<T> subList(int fromIndex, int toIndex)
2925    {
2926      synchronized (mutex)
2927        {
2928          return new SynchronizedList<T>(mutex,
2929                                         list.subList(fromIndex, toIndex));
2930        }
2931    }
2932  } // class SynchronizedList
2933
2934  /**
2935   * The implementation of {@link #synchronizedList(List)} for random-access
2936   * lists. This class name is required for compatibility with Sun's JDK
2937   * serializability.
2938   *
2939   * @author Eric Blake (ebb9@email.byu.edu)
2940   */
2941  private static final class SynchronizedRandomAccessList<T>
2942    extends SynchronizedList<T> implements RandomAccess
2943  {
2944    /**
2945     * Compatible with JDK 1.4.
2946     */
2947    private static final long serialVersionUID = 1530674583602358482L;
2948
2949    /**
2950     * Wrap a given list.
2951     * @param l the list to wrap
2952     * @throws NullPointerException if l is null
2953     */
2954    SynchronizedRandomAccessList(List<T> l)
2955    {
2956      super(l);
2957    }
2958
2959    /**
2960     * Called only by trusted code to specify the mutex as well as the
2961     * collection.
2962     * @param sync the mutex
2963     * @param l the list
2964     */
2965    SynchronizedRandomAccessList(Object sync, List<T> l)
2966    {
2967      super(sync, l);
2968    }
2969
2970    /**
2971     * Obtain a List view of a subsection of the underlying list, from fromIndex
2972     * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2973     * sublist is empty. The returned list should be modifiable if and only
2974     * if this list is modifiable. Changes to the returned list should be
2975     * reflected in this list. If this list is structurally modified in
2976     * any way other than through the returned list, the result of any subsequent
2977     * operations on the returned list is undefined.    A lock is obtained
2978     * on the mutex before the creation of the sublist.  The returned list
2979     * is also synchronized, using the same mutex.  Random accessibility
2980     * is also extended to the new list.
2981     *
2982     * @param fromIndex the index that the returned list should start from
2983     *        (inclusive)
2984     * @param toIndex the index that the returned list should go to (exclusive)
2985     * @return a List backed by a subsection of this list
2986     * @throws IndexOutOfBoundsException if fromIndex &lt; 0
2987     *         || toIndex &gt; size() || fromIndex &gt; toIndex
2988     */
2989    public List<T> subList(int fromIndex, int toIndex)
2990    {
2991      synchronized (mutex)
2992        {
2993          return new SynchronizedRandomAccessList<T>(mutex,
2994                                                     list.subList(fromIndex,
2995                                                                  toIndex));
2996        }
2997    }
2998  } // class SynchronizedRandomAccessList
2999
3000  /**
3001   * The implementation of {@link SynchronizedList#listIterator()}. This
3002   * iterator must "sync" on the same object as the list it iterates over.
3003   *
3004   * @author Eric Blake (ebb9@email.byu.edu)
3005   */
3006  private static final class SynchronizedListIterator<T>
3007    extends SynchronizedIterator<T> implements ListIterator<T>
3008  {
3009    /**
3010     * The wrapped iterator, stored both here and in the superclass to
3011     * avoid excessive casting.
3012     */
3013    private final ListIterator<T> li;
3014
3015    /**
3016     * Only trusted code creates a wrapper, with the specified sync.
3017     * @param sync the mutex
3018     * @param li the wrapped iterator
3019     */
3020    SynchronizedListIterator(Object sync, ListIterator<T> li)
3021    {
3022      super(sync, li);
3023      this.li = li;
3024    }
3025
3026    /**
3027     * Insert an element into the underlying list at the current position of
3028     * the iterator (optional operation). The element is inserted in between
3029     * the element that would be returned by <code>previous()</code> and the
3030     * element that would be returned by <code>next()</code>. After the
3031     * insertion, a subsequent call to next is unaffected, but
3032     * a call to previous returns the item that was added. The values returned
3033     * by nextIndex() and previousIndex() are incremented.  A lock is obtained
3034     * on the mutex before the addition takes place.
3035     *
3036     * @param o the object to insert into the list
3037     * @throws ClassCastException if the object is of a type which cannot be added
3038     *         to this list.
3039     * @throws IllegalArgumentException if some other aspect of the object stops
3040     *         it being added to this list.
3041     * @throws UnsupportedOperationException if this ListIterator does not
3042     *         support the add operation.
3043     */
3044    public void add(T o)
3045    {
3046      synchronized (mutex)
3047        {
3048          li.add(o);
3049        }
3050    }
3051
3052    /**
3053     * Tests whether there are elements remaining in the underlying list
3054     * in the reverse direction. In other words, <code>previous()</code>
3055     * will not fail with a NoSuchElementException.  A lock is obtained
3056     * on the mutex before the check takes place.
3057     *
3058     * @return <code>true</code> if the list continues in the reverse direction
3059     */
3060    public boolean hasPrevious()
3061    {
3062      synchronized (mutex)
3063        {
3064          return li.hasPrevious();
3065        }
3066    }
3067
3068    /**
3069      * Find the index of the element that would be returned by a call to
3070      * <code>next()</code>.  If hasNext() returns <code>false</code>, this
3071      * returns the list size.  A lock is obtained on the mutex before the
3072      * query takes place.
3073      *
3074      * @return the index of the element that would be returned by next()
3075      */
3076    public int nextIndex()
3077    {
3078      synchronized (mutex)
3079        {
3080          return li.nextIndex();
3081        }
3082    }
3083
3084    /**
3085     * Obtain the previous element from the underlying list. Repeated
3086     * calls to previous may be used to iterate backwards over the entire list,
3087     * or calls to next and previous may be used together to go forwards and
3088     * backwards. Alternating calls to next and previous will return the same
3089     * element.  A lock is obtained on the mutex before the object is retrieved.
3090     *
3091     * @return the next element in the list in the reverse direction
3092     * @throws NoSuchElementException if there are no more elements
3093     */
3094    public T previous()
3095    {
3096      synchronized (mutex)
3097        {
3098          return li.previous();
3099        }
3100    }
3101
3102    /**
3103     * Find the index of the element that would be returned by a call to
3104     * previous. If hasPrevious() returns <code>false</code>, this returns -1.
3105     * A lock is obtained on the mutex before the query takes place.
3106     *
3107     * @return the index of the element that would be returned by previous()
3108     */
3109    public int previousIndex()
3110    {
3111      synchronized (mutex)
3112        {
3113          return li.previousIndex();
3114        }
3115    }
3116
3117    /**
3118     * Replace the element last returned by a call to <code>next()</code> or
3119     * <code>previous()</code> with a given object (optional operation).  This
3120     * method may only be called if neither <code>add()</code> nor
3121     * <code>remove()</code> have been called since the last call to
3122     * <code>next()</code> or <code>previous</code>.  A lock is obtained
3123     * on the mutex before the list is modified.
3124     *
3125     * @param o the object to replace the element with
3126     * @throws ClassCastException the object is of a type which cannot be added
3127     *         to this list
3128     * @throws IllegalArgumentException some other aspect of the object stops
3129     *         it being added to this list
3130     * @throws IllegalStateException if neither next or previous have been
3131     *         called, or if add or remove has been called since the last call
3132     *         to next or previous
3133     * @throws UnsupportedOperationException if this ListIterator does not
3134     *         support the set operation
3135     */
3136    public void set(T o)
3137    {
3138      synchronized (mutex)
3139        {
3140          li.set(o);
3141        }
3142    }
3143  } // class SynchronizedListIterator
3144
3145  /**
3146   * Returns a synchronized (thread-safe) map wrapper backed by the given
3147   * map. Notice that element access through the collection views and their
3148   * iterators are thread-safe, but if the map can be structurally modified
3149   * (adding or removing elements) then you should synchronize around the
3150   * iteration to avoid non-deterministic behavior:<br>
3151   * <pre>
3152   * Map m = Collections.synchronizedMap(new Map(...));
3153   * ...
3154   * Set s = m.keySet(); // safe outside a synchronized block
3155   * synchronized (m) // synch on m, not s
3156   *   {
3157   *     Iterator i = s.iterator();
3158   *     while (i.hasNext())
3159   *       foo(i.next());
3160   *   }
3161   * </pre><p>
3162   *
3163   * The returned Map implements Serializable, but can only be serialized if
3164   * the map it wraps is likewise Serializable.
3165   *
3166   * @param m the map to wrap
3167   * @return a synchronized view of the map
3168   * @see Serializable
3169   */
3170  public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m)
3171  {
3172    return new SynchronizedMap<K, V>(m);
3173  }
3174
3175  /**
3176   * The implementation of {@link #synchronizedMap(Map)}. This
3177   * class name is required for compatibility with Sun's JDK serializability.
3178   *
3179   * @author Eric Blake (ebb9@email.byu.edu)
3180   */
3181  private static class SynchronizedMap<K, V> implements Map<K, V>, Serializable
3182  {
3183    /**
3184     * Compatible with JDK 1.4.
3185     */
3186    private static final long serialVersionUID = 1978198479659022715L;
3187
3188    /**
3189     * The wrapped map.
3190     * @serial the real map
3191     */
3192    private final Map<K, V> m;
3193
3194    /**
3195     * The object to synchronize on.  When an instance is created via public
3196     * methods, it will be this; but other uses like
3197     * SynchronizedSortedMap.subMap() must specify another mutex. Package
3198     * visible for use by subclass.
3199     * @serial the lock
3200     */
3201    final Object mutex;
3202
3203    /**
3204     * Cache the entry set.
3205     */
3206    private transient Set<Map.Entry<K, V>> entries;
3207
3208    /**
3209     * Cache the key set.
3210     */
3211    private transient Set<K> keys;
3212
3213    /**
3214     * Cache the value collection.
3215     */
3216    private transient Collection<V> values;
3217
3218    /**
3219     * Wrap a given map.
3220     * @param m the map to wrap
3221     * @throws NullPointerException if m is null
3222     */
3223    SynchronizedMap(Map<K, V> m)
3224    {
3225      this.m = m;
3226      mutex = this;
3227      if (m == null)
3228        throw new NullPointerException();
3229    }
3230
3231    /**
3232     * Called only by trusted code to specify the mutex as well as the map.
3233     * @param sync the mutex
3234     * @param m the map
3235     */
3236    SynchronizedMap(Object sync, Map<K, V> m)
3237    {
3238      this.m = m;
3239      mutex = sync;
3240    }
3241
3242    /**
3243     * Clears all the entries from the underlying map.  A lock is obtained
3244     * on the mutex before the map is cleared.
3245     *
3246     * @throws UnsupportedOperationException if clear is not supported
3247     */
3248    public void clear()
3249    {
3250      synchronized (mutex)
3251        {
3252          m.clear();
3253        }
3254    }
3255
3256    /**
3257     * Returns <code>true</code> if the underlying map contains a entry for the given key.
3258     * A lock is obtained on the mutex before the map is queried.
3259     *
3260     * @param key the key to search for.
3261     * @return <code>true</code> if the underlying map contains the key.
3262     * @throws ClassCastException if the key is of an inappropriate type.
3263     * @throws NullPointerException if key is <code>null</code> but the map
3264     *         does not permit null keys.
3265     */
3266    public boolean containsKey(Object key)
3267    {
3268      synchronized (mutex)
3269        {
3270          return m.containsKey(key);
3271        }
3272    }
3273
3274  /**
3275   * Returns <code>true</code> if the underlying map contains at least one entry with the
3276   * given value.  In other words, returns <code>true</code> if a value v exists where
3277   * <code>(value == null ? v == null : value.equals(v))</code>. This usually
3278   * requires linear time.  A lock is obtained on the mutex before the map
3279   * is queried.
3280   *
3281   * @param value the value to search for
3282   * @return <code>true</code> if the map contains the value
3283   * @throws ClassCastException if the type of the value is not a valid type
3284   *         for this map.
3285   * @throws NullPointerException if the value is null and the map doesn't
3286   *         support null values.
3287   */
3288    public boolean containsValue(Object value)
3289    {
3290      synchronized (mutex)
3291        {
3292          return m.containsValue(value);
3293        }
3294    }
3295
3296    // This is one of the ickiest cases of nesting I've ever seen. It just
3297    // means "return a SynchronizedSet, except that the iterator() method
3298    // returns an SynchronizedIterator whose next() method returns a
3299    // synchronized wrapper around its normal return value".
3300    public Set<Map.Entry<K, V>> entrySet()
3301    {
3302      // Define this here to spare some nesting.
3303      class SynchronizedMapEntry<K, V> implements Map.Entry<K, V>
3304      {
3305        final Map.Entry<K, V> e;
3306        SynchronizedMapEntry(Map.Entry<K, V> o)
3307        {
3308          e = o;
3309        }
3310
3311        /**
3312         * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code>
3313         * with the same key and value as the underlying entry.  A lock is
3314         * obtained on the mutex before the comparison takes place.
3315         *
3316         * @param o The object to compare with this entry.
3317         * @return <code>true</code> if o is equivalent to the underlying map entry.
3318         */
3319        public boolean equals(Object o)
3320        {
3321          synchronized (mutex)
3322            {
3323              return e.equals(o);
3324            }
3325        }
3326
3327        /**
3328         * Returns the key used in the underlying map entry.  A lock is obtained
3329         * on the mutex before the key is retrieved.
3330         *
3331         * @return The key of the underlying map entry.
3332         */
3333        public K getKey()
3334        {
3335          synchronized (mutex)
3336            {
3337              return e.getKey();
3338            }
3339        }
3340
3341        /**
3342         * Returns the value used in the underlying map entry.  A lock is obtained
3343         * on the mutex before the value is retrieved.
3344         *
3345         * @return The value of the underlying map entry.
3346         */
3347        public V getValue()
3348        {
3349          synchronized (mutex)
3350            {
3351              return e.getValue();
3352            }
3353        }
3354
3355        /**
3356         * Computes the hash code for the underlying map entry.
3357         * This computation is described in the documentation for the
3358         * <code>Map</code> interface.  A lock is obtained on the mutex
3359         * before the underlying map is accessed.
3360         *
3361         * @return The hash code of the underlying map entry.
3362         * @see Map#hashCode()
3363         */
3364        public int hashCode()
3365        {
3366          synchronized (mutex)
3367            {
3368              return e.hashCode();
3369            }
3370        }
3371
3372        /**
3373         * Replaces the value in the underlying map entry with the specified
3374         * object (optional operation).  A lock is obtained on the mutex
3375         * before the map is altered.  The map entry, in turn, will alter
3376         * the underlying map object.  The operation is undefined if the
3377         * <code>remove()</code> method of the iterator has been called
3378         * beforehand.
3379         *
3380         * @param value the new value to store
3381         * @return the old value
3382         * @throws UnsupportedOperationException if the operation is not supported.
3383         * @throws ClassCastException if the value is of the wrong type.
3384         * @throws IllegalArgumentException if something about the value
3385         *         prevents it from existing in this map.
3386         * @throws NullPointerException if the map forbids null values.
3387         */
3388        public V setValue(V value)
3389        {
3390          synchronized (mutex)
3391            {
3392              return e.setValue(value);
3393            }
3394        }
3395
3396        /**
3397         * Returns a textual representation of the underlying map entry.
3398         * A lock is obtained on the mutex before the entry is accessed.
3399         *
3400         * @return The contents of the map entry in <code>String</code> form.
3401         */
3402        public String toString()
3403        {
3404          synchronized (mutex)
3405            {
3406              return e.toString();
3407            }
3408        }
3409      } // class SynchronizedMapEntry
3410
3411      // Now the actual code.
3412      if (entries == null)
3413        synchronized (mutex)
3414          {
3415            entries = new SynchronizedSet<Map.Entry<K, V>>(mutex, m.entrySet())
3416            {
3417              /**
3418               * Returns an iterator over the set.  The iterator has no specific order,
3419               * unless further specified.  A lock is obtained on the set's mutex
3420               * before the iterator is created.  The created iterator is also
3421               * thread-safe.
3422               *
3423               * @return A synchronized set iterator.
3424               */
3425              public Iterator<Map.Entry<K, V>> iterator()
3426              {
3427                synchronized (super.mutex)
3428                  {
3429                    return new SynchronizedIterator<Map.Entry<K, V>>(super.mutex,
3430                                                                     c.iterator())
3431                    {
3432                      /**
3433                       * Retrieves the next map entry from the iterator.
3434                       * A lock is obtained on the iterator's mutex before
3435                       * the entry is created.  The new map entry is enclosed in
3436                       * a thread-safe wrapper.
3437                       *
3438                       * @return A synchronized map entry.
3439                       */
3440                      public Map.Entry<K, V> next()
3441                      {
3442                        synchronized (super.mutex)
3443                          {
3444                            return new SynchronizedMapEntry<K, V>(super.next());
3445                          }
3446                      }
3447                    };
3448                  }
3449              }
3450            };
3451          }
3452      return entries;
3453    }
3454
3455    /**
3456     * Returns <code>true</code> if the object, o, is also an instance
3457     * of <code>Map</code> and contains an equivalent
3458     * entry set to that of the underlying map.  A lock
3459     * is obtained on the mutex before the objects are
3460     * compared.
3461     *
3462     * @param o The object to compare.
3463     * @return <code>true</code> if o and the underlying map are equivalent.
3464     */
3465    public boolean equals(Object o)
3466    {
3467      synchronized (mutex)
3468        {
3469          return m.equals(o);
3470        }
3471    }
3472
3473    /**
3474     * Returns the value associated with the given key, or null
3475     * if no such mapping exists.  An ambiguity exists with maps
3476     * that accept null values as a return value of null could
3477     * be due to a non-existent mapping or simply a null value
3478     * for that key.  To resolve this, <code>containsKey</code>
3479     * should be used.  A lock is obtained on the mutex before
3480     * the value is retrieved from the underlying map.
3481     *
3482     * @param key The key of the required mapping.
3483     * @return The value associated with the given key, or
3484     *         null if no such mapping exists.
3485     * @throws ClassCastException if the key is an inappropriate type.
3486     * @throws NullPointerException if this map does not accept null keys.
3487     */
3488    public V get(Object key)
3489    {
3490      synchronized (mutex)
3491        {
3492          return m.get(key);
3493        }
3494    }
3495
3496    /**
3497     * Calculates the hash code of the underlying map as the
3498     * sum of the hash codes of all entries.  A lock is obtained
3499     * on the mutex before the hash code is computed.
3500     *
3501     * @return The hash code of the underlying map.
3502     */
3503    public int hashCode()
3504    {
3505      synchronized (mutex)
3506        {
3507          return m.hashCode();
3508        }
3509    }
3510
3511    /**
3512     * Returns <code>true</code> if the underlying map contains no entries.
3513     * A lock is obtained on the mutex before the map is examined.
3514     *
3515     * @return <code>true</code> if the map is empty.
3516     */
3517    public boolean isEmpty()
3518    {
3519      synchronized (mutex)
3520        {
3521          return m.isEmpty();
3522        }
3523    }
3524
3525    /**
3526     * Returns a thread-safe set view of the keys in the underlying map.  The
3527     * set is backed by the map, so that changes in one show up in the other.
3528     * Modifications made while an iterator is in progress cause undefined
3529     * behavior.  If the set supports removal, these methods remove the
3530     * underlying mapping from the map: <code>Iterator.remove</code>,
3531     * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
3532     * and <code>clear</code>.  Element addition, via <code>add</code> or
3533     * <code>addAll</code>, is not supported via this set.  A lock is obtained
3534     * on the mutex before the set is created.
3535     *
3536     * @return A synchronized set containing the keys of the underlying map.
3537     */
3538    public Set<K> keySet()
3539    {
3540      if (keys == null)
3541        synchronized (mutex)
3542          {
3543            keys = new SynchronizedSet<K>(mutex, m.keySet());
3544          }
3545      return keys;
3546    }
3547
3548    /**
3549     * Associates the given key to the given value (optional operation). If the
3550     * underlying map already contains the key, its value is replaced. Be aware
3551     * that in a map that permits <code>null</code> values, a null return does not
3552     * always imply that the mapping was created.  A lock is obtained on the mutex
3553     * before the modification is made.
3554     *
3555     * @param key the key to map.
3556     * @param value the value to be mapped.
3557     * @return the previous value of the key, or null if there was no mapping
3558     * @throws UnsupportedOperationException if the operation is not supported
3559     * @throws ClassCastException if the key or value is of the wrong type
3560     * @throws IllegalArgumentException if something about this key or value
3561     *         prevents it from existing in this map
3562     * @throws NullPointerException if either the key or the value is null,
3563     *         and the map forbids null keys or values
3564     * @see #containsKey(Object)
3565     */
3566    public V put(K key, V value)
3567    {
3568      synchronized (mutex)
3569        {
3570          return m.put(key, value);
3571        }
3572    }
3573
3574    /**
3575     * Copies all entries of the given map to the underlying one (optional
3576     * operation). If the map already contains a key, its value is replaced.
3577     * A lock is obtained on the mutex before the operation proceeds.
3578     *
3579     * @param map the mapping to load into this map
3580     * @throws UnsupportedOperationException if the operation is not supported
3581     * @throws ClassCastException if a key or value is of the wrong type
3582     * @throws IllegalArgumentException if something about a key or value
3583     *         prevents it from existing in this map
3584     * @throws NullPointerException if the map forbids null keys or values, or
3585     *         if <code>m</code> is null.
3586     * @see #put(Object, Object)
3587     */
3588    public void putAll(Map<? extends K, ? extends V> map)
3589    {
3590      synchronized (mutex)
3591        {
3592          m.putAll(map);
3593        }
3594    }
3595
3596    /**
3597     * Removes the mapping for the key, o, if present (optional operation). If
3598     * the key is not present, this returns null. Note that maps which permit
3599     * null values may also return null if the key was removed.  A prior
3600     * <code>containsKey()</code> check is required to avoid this ambiguity.
3601     * Before the mapping is removed, a lock is obtained on the mutex.
3602     *
3603     * @param o the key to remove
3604     * @return the value the key mapped to, or null if not present
3605     * @throws UnsupportedOperationException if deletion is unsupported
3606     * @throws NullPointerException if the key is null and this map doesn't
3607     *         support null keys.
3608     * @throws ClassCastException if the type of the key is not a valid type
3609     *         for this map.
3610     */
3611    public V remove(Object o)
3612    {
3613      synchronized (mutex)
3614        {
3615          return m.remove(o);
3616        }
3617    }
3618
3619    /**
3620     * Retrieves the size of the underlying map.  A lock
3621     * is obtained on the mutex before access takes place.
3622     * Maps with a size greater than <code>Integer.MAX_VALUE</code>
3623     * return <code>Integer.MAX_VALUE</code> instead.
3624     *
3625     * @return The size of the underlying map.
3626     */
3627    public int size()
3628    {
3629      synchronized (mutex)
3630        {
3631          return m.size();
3632        }
3633    }
3634
3635    /**
3636     * Returns a textual representation of the underlying
3637     * map.  A lock is obtained on the mutex before the map
3638     * is accessed.
3639     *
3640     * @return The map in <code>String</code> form.
3641     */
3642    public String toString()
3643    {
3644      synchronized (mutex)
3645        {
3646          return m.toString();
3647        }
3648    }
3649
3650    /**
3651     * Returns a synchronized collection view of the values in the underlying
3652     * map.  The collection is backed by the map, so that changes in one show up in
3653     * the other.  Modifications made while an iterator is in progress cause
3654     * undefined behavior.  If the collection supports removal, these methods
3655     * remove the underlying mapping from the map: <code>Iterator.remove</code>,
3656     * <code>Collection.remove</code>, <code>removeAll</code>,
3657     * <code>retainAll</code>, and <code>clear</code>. Element addition, via
3658     * <code>add</code> or <code>addAll</code>, is not supported via this
3659     * collection.  A lock is obtained on the mutex before the collection
3660     * is created.
3661     *
3662     * @return the collection of all values in the underlying map.
3663     */
3664    public Collection<V> values()
3665    {
3666      if (values == null)
3667        synchronized (mutex)
3668          {
3669            values = new SynchronizedCollection<V>(mutex, m.values());
3670          }
3671      return values;
3672    }
3673  } // class SynchronizedMap
3674
3675  /**
3676   * Returns a synchronized (thread-safe) set wrapper backed by the given
3677   * set. Notice that element access through the iterator is thread-safe, but
3678   * if the set can be structurally modified (adding or removing elements)
3679   * then you should synchronize around the iteration to avoid
3680   * non-deterministic behavior:<br>
3681   * <pre>
3682   * Set s = Collections.synchronizedSet(new Set(...));
3683   * ...
3684   * synchronized (s)
3685   *   {
3686   *     Iterator i = s.iterator();
3687   *     while (i.hasNext())
3688   *       foo(i.next());
3689   *   }
3690   * </pre><p>
3691   *
3692   * The returned Set implements Serializable, but can only be serialized if
3693   * the set it wraps is likewise Serializable.
3694   *
3695   * @param s the set to wrap
3696   * @return a synchronized view of the set
3697   * @see Serializable
3698   */
3699  public static <T> Set<T> synchronizedSet(Set<T> s)
3700  {
3701    return new SynchronizedSet<T>(s);
3702  }
3703
3704  /**
3705   * The implementation of {@link #synchronizedSet(Set)}. This class
3706   * name is required for compatibility with Sun's JDK serializability.
3707   * Package visible, so that sets such as Hashtable.keySet()
3708   * can specify which object to synchronize on.
3709   *
3710   * @author Eric Blake (ebb9@email.byu.edu)
3711   */
3712  static class SynchronizedSet<T> extends SynchronizedCollection<T>
3713    implements Set<T>
3714  {
3715    /**
3716     * Compatible with JDK 1.4.
3717     */
3718    private static final long serialVersionUID = 487447009682186044L;
3719
3720    /**
3721     * Wrap a given set.
3722     * @param s the set to wrap
3723     * @throws NullPointerException if s is null
3724     */
3725    SynchronizedSet(Set<T> s)
3726    {
3727      super(s);
3728    }
3729
3730    /**
3731     * Called only by trusted code to specify the mutex as well as the set.
3732     * @param sync the mutex
3733     * @param s the set
3734     */
3735    SynchronizedSet(Object sync, Set<T> s)
3736    {
3737      super(sync, s);
3738    }
3739
3740    /**
3741     * Returns <code>true</code> if the object, o, is a <code>Set</code>
3742     * of the same size as the underlying set, and contains
3743     * each element, e, which occurs in the underlying set.
3744     * A lock is obtained on the mutex before the comparison
3745     * takes place.
3746     *
3747     * @param o The object to compare against.
3748     * @return <code>true</code> if o is an equivalent set.
3749     */
3750    public boolean equals(Object o)
3751    {
3752      synchronized (mutex)
3753        {
3754          return c.equals(o);
3755        }
3756    }
3757
3758    /**
3759     * Computes the hash code for the underlying set as the
3760     * sum of the hash code of all elements within the set.
3761     * A lock is obtained on the mutex before the computation
3762     * occurs.
3763     *
3764     * @return The hash code for the underlying set.
3765     */
3766    public int hashCode()
3767    {
3768      synchronized (mutex)
3769        {
3770          return c.hashCode();
3771        }
3772    }
3773  } // class SynchronizedSet
3774
3775  /**
3776   * Returns a synchronized (thread-safe) sorted map wrapper backed by the
3777   * given map. Notice that element access through the collection views,
3778   * subviews, and their iterators are thread-safe, but if the map can be
3779   * structurally modified (adding or removing elements) then you should
3780   * synchronize around the iteration to avoid non-deterministic behavior:<br>
3781   * <pre>
3782   * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
3783   * ...
3784   * Set s = m.keySet(); // safe outside a synchronized block
3785   * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
3786   * Set s2 = m2.keySet(); // safe outside a synchronized block
3787   * synchronized (m) // synch on m, not m2, s or s2
3788   *   {
3789   *     Iterator i = s.iterator();
3790   *     while (i.hasNext())
3791   *       foo(i.next());
3792   *     i = s2.iterator();
3793   *     while (i.hasNext())
3794   *       bar(i.next());
3795   *   }
3796   * </pre><p>
3797   *
3798   * The returned SortedMap implements Serializable, but can only be
3799   * serialized if the map it wraps is likewise Serializable.
3800   *
3801   * @param m the sorted map to wrap
3802   * @return a synchronized view of the sorted map
3803   * @see Serializable
3804   */
3805  public static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> m)
3806  {
3807    return new SynchronizedSortedMap<K, V>(m);
3808  }
3809
3810  /**
3811   * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
3812   * class name is required for compatibility with Sun's JDK serializability.
3813   *
3814   * @author Eric Blake (ebb9@email.byu.edu)
3815   */
3816  private static final class SynchronizedSortedMap<K, V>
3817    extends SynchronizedMap<K, V>
3818    implements SortedMap<K, V>
3819  {
3820    /**
3821     * Compatible with JDK 1.4.
3822     */
3823    private static final long serialVersionUID = -8798146769416483793L;
3824
3825    /**
3826     * The wrapped map; stored both here and in the superclass to avoid
3827     * excessive casting.
3828     * @serial the wrapped map
3829     */
3830    private final SortedMap<K, V> sm;
3831
3832    /**
3833     * Wrap a given map.
3834     * @param sm the map to wrap
3835     * @throws NullPointerException if sm is null
3836     */
3837    SynchronizedSortedMap(SortedMap<K, V> sm)
3838    {
3839      super(sm);
3840      this.sm = sm;
3841    }
3842
3843    /**
3844     * Called only by trusted code to specify the mutex as well as the map.
3845     * @param sync the mutex
3846     * @param sm the map
3847     */
3848    SynchronizedSortedMap(Object sync, SortedMap<K, V> sm)
3849    {
3850      super(sync, sm);
3851      this.sm = sm;
3852    }
3853
3854    /**
3855     * Returns the comparator used in sorting the underlying map, or null if
3856     * it is the keys' natural ordering.  A lock is obtained on the mutex
3857     * before the comparator is retrieved.
3858     *
3859     * @return the sorting comparator.
3860     */
3861    public Comparator<? super K> comparator()
3862    {
3863      synchronized (mutex)
3864        {
3865          return sm.comparator();
3866        }
3867    }
3868
3869    /**
3870     * Returns the first, lowest sorted, key from the underlying map.
3871     * A lock is obtained on the mutex before the map is accessed.
3872     *
3873     * @return the first key.
3874     * @throws NoSuchElementException if this map is empty.
3875     */
3876    public K firstKey()
3877    {
3878      synchronized (mutex)
3879        {
3880          return sm.firstKey();
3881        }
3882    }
3883
3884    /**
3885     * Returns a submap containing the keys from the first
3886     * key (as returned by <code>firstKey()</code>) to
3887     * the key before that specified.  The submap supports all
3888     * operations supported by the underlying map and all actions
3889     * taking place on the submap are also reflected in the underlying
3890     * map.  A lock is obtained on the mutex prior to submap creation.
3891     * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>.
3892     * The submap retains the thread-safe status of this map.
3893     *
3894     * @param toKey the exclusive upper range of the submap.
3895     * @return a submap from <code>firstKey()</code> to the
3896     *         the key preceding toKey.
3897     * @throws ClassCastException if toKey is not comparable to the underlying
3898     *         map's contents.
3899     * @throws IllegalArgumentException if toKey is outside the map's range.
3900     * @throws NullPointerException if toKey is null. but the map does not allow
3901     *         null keys.
3902     */
3903    public SortedMap<K, V> headMap(K toKey)
3904    {
3905      synchronized (mutex)
3906        {
3907          return new SynchronizedSortedMap<K, V>(mutex, sm.headMap(toKey));
3908        }
3909    }
3910
3911    /**
3912     * Returns the last, highest sorted, key from the underlying map.
3913     * A lock is obtained on the mutex before the map is accessed.
3914     *
3915     * @return the last key.
3916     * @throws NoSuchElementException if this map is empty.
3917     */
3918    public K lastKey()
3919    {
3920      synchronized (mutex)
3921        {
3922          return sm.lastKey();
3923        }
3924    }
3925
3926    /**
3927     * Returns a submap containing the keys from fromKey to
3928     * the key before toKey.  The submap supports all
3929     * operations supported by the underlying map and all actions
3930     * taking place on the submap are also reflected in the underlying
3931     * map.  A lock is obtained on the mutex prior to submap creation.
3932     * The submap retains the thread-safe status of this map.
3933     *
3934     * @param fromKey the inclusive lower range of the submap.
3935     * @param toKey the exclusive upper range of the submap.
3936     * @return a submap from fromKey to the key preceding toKey.
3937     * @throws ClassCastException if fromKey or toKey is not comparable
3938     *         to the underlying map's contents.
3939     * @throws IllegalArgumentException if fromKey or toKey is outside the map's
3940     *         range.
3941     * @throws NullPointerException if fromKey or toKey is null. but the map does
3942     *         not allow  null keys.
3943     */
3944    public SortedMap<K, V> subMap(K fromKey, K toKey)
3945    {
3946      synchronized (mutex)
3947        {
3948          return new SynchronizedSortedMap<K, V>(mutex,
3949                                                 sm.subMap(fromKey, toKey));
3950        }
3951    }
3952
3953    /**
3954     * Returns a submap containing all the keys from fromKey onwards.
3955     * The submap supports all operations supported by the underlying
3956     * map and all actions taking place on the submap are also reflected
3957     * in the underlying map.  A lock is obtained on the mutex prior to
3958     * submap creation.  The submap retains the thread-safe status of
3959     * this map.
3960     *
3961     * @param fromKey the inclusive lower range of the submap.
3962     * @return a submap from fromKey to <code>lastKey()</code>.
3963     * @throws ClassCastException if fromKey is not comparable to the underlying
3964     *         map's contents.
3965     * @throws IllegalArgumentException if fromKey is outside the map's range.
3966     * @throws NullPointerException if fromKey is null. but the map does not allow
3967     *         null keys.
3968     */
3969    public SortedMap<K, V> tailMap(K fromKey)
3970    {
3971      synchronized (mutex)
3972        {
3973          return new SynchronizedSortedMap<K, V>(mutex, sm.tailMap(fromKey));
3974        }
3975    }
3976  } // class SynchronizedSortedMap
3977
3978  /**
3979   * Returns a synchronized (thread-safe) sorted set wrapper backed by the
3980   * given set. Notice that element access through the iterator and through
3981   * subviews are thread-safe, but if the set can be structurally modified
3982   * (adding or removing elements) then you should synchronize around the
3983   * iteration to avoid non-deterministic behavior:<br>
3984   * <pre>
3985   * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
3986   * ...
3987   * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
3988   * synchronized (s) // synch on s, not s2
3989   *   {
3990   *     Iterator i = s2.iterator();
3991   *     while (i.hasNext())
3992   *       foo(i.next());
3993   *   }
3994   * </pre><p>
3995   *
3996   * The returned SortedSet implements Serializable, but can only be
3997   * serialized if the set it wraps is likewise Serializable.
3998   *
3999   * @param s the sorted set to wrap
4000   * @return a synchronized view of the sorted set
4001   * @see Serializable
4002   */
4003  public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
4004  {
4005    return new SynchronizedSortedSet<T>(s);
4006  }
4007
4008  /**
4009   * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
4010   * class name is required for compatibility with Sun's JDK serializability.
4011   *
4012   * @author Eric Blake (ebb9@email.byu.edu)
4013   */
4014  private static final class SynchronizedSortedSet<T>
4015    extends SynchronizedSet<T>
4016    implements SortedSet<T>
4017  {
4018    /**
4019     * Compatible with JDK 1.4.
4020     */
4021    private static final long serialVersionUID = 8695801310862127406L;
4022
4023    /**
4024     * The wrapped set; stored both here and in the superclass to avoid
4025     * excessive casting.
4026     * @serial the wrapped set
4027     */
4028    private final SortedSet<T> ss;
4029
4030    /**
4031     * Wrap a given set.
4032     * @param ss the set to wrap
4033     * @throws NullPointerException if ss is null
4034     */
4035    SynchronizedSortedSet(SortedSet<T> ss)
4036    {
4037      super(ss);
4038      this.ss = ss;
4039    }
4040
4041    /**
4042     * Called only by trusted code to specify the mutex as well as the set.
4043     * @param sync the mutex
4044     * @param ss the set
4045     */
4046    SynchronizedSortedSet(Object sync, SortedSet<T> ss)
4047    {
4048      super(sync, ss);
4049      this.ss = ss;
4050    }
4051
4052    /**
4053     * Returns the comparator used in sorting the underlying set, or null if
4054     * it is the elements' natural ordering.  A lock is obtained on the mutex
4055     * before the comparator is retrieved.
4056     *
4057     * @return the sorting comparator.
4058     */
4059    public Comparator<? super T> comparator()
4060    {
4061      synchronized (mutex)
4062        {
4063          return ss.comparator();
4064        }
4065    }
4066
4067    /**
4068     * Returns the first, lowest sorted, element from the underlying set.
4069     * A lock is obtained on the mutex before the set is accessed.
4070     *
4071     * @return the first element.
4072     * @throws NoSuchElementException if this set is empty.
4073     */
4074    public T first()
4075    {
4076      synchronized (mutex)
4077        {
4078          return ss.first();
4079        }
4080    }
4081
4082    /**
4083     * Returns a subset containing the element from the first
4084     * element (as returned by <code>first()</code>) to
4085     * the element before that specified.  The subset supports all
4086     * operations supported by the underlying set and all actions
4087     * taking place on the subset are also reflected in the underlying
4088     * set.  A lock is obtained on the mutex prior to subset creation.
4089     * This operation is equivalent to <code>subSet(first(), toElement)</code>.
4090     * The subset retains the thread-safe status of this set.
4091     *
4092     * @param toElement the exclusive upper range of the subset.
4093     * @return a subset from <code>first()</code> to the
4094     *         the element preceding toElement.
4095     * @throws ClassCastException if toElement is not comparable to the underlying
4096     *         set's contents.
4097     * @throws IllegalArgumentException if toElement is outside the set's range.
4098     * @throws NullPointerException if toElement is null. but the set does not allow
4099     *         null elements.
4100     */
4101    public SortedSet<T> headSet(T toElement)
4102    {
4103      synchronized (mutex)
4104        {
4105          return new SynchronizedSortedSet<T>(mutex, ss.headSet(toElement));
4106        }
4107    }
4108
4109    /**
4110     * Returns the last, highest sorted, element from the underlying set.
4111     * A lock is obtained on the mutex before the set is accessed.
4112     *
4113     * @return the last element.
4114     * @throws NoSuchElementException if this set is empty.
4115     */
4116    public T last()
4117    {
4118      synchronized (mutex)
4119        {
4120          return ss.last();
4121        }
4122    }
4123
4124    /**
4125     * Returns a subset containing the elements from fromElement to
4126     * the element before toElement.  The subset supports all
4127     * operations supported by the underlying set and all actions
4128     * taking place on the subset are also reflected in the underlying
4129     * set.  A lock is obtained on the mutex prior to subset creation.
4130     * The subset retains the thread-safe status of this set.
4131     *
4132     * @param fromElement the inclusive lower range of the subset.
4133     * @param toElement the exclusive upper range of the subset.
4134     * @return a subset from fromElement to the element preceding toElement.
4135     * @throws ClassCastException if fromElement or toElement is not comparable
4136     *         to the underlying set's contents.
4137     * @throws IllegalArgumentException if fromElement or toElement is outside the set's
4138     *         range.
4139     * @throws NullPointerException if fromElement or toElement is null. but the set does
4140     *         not allow null elements.
4141     */
4142    public SortedSet<T> subSet(T fromElement, T toElement)
4143    {
4144      synchronized (mutex)
4145        {
4146          return new SynchronizedSortedSet<T>(mutex,
4147                                              ss.subSet(fromElement,
4148                                                        toElement));
4149        }
4150    }
4151
4152    /**
4153     * Returns a subset containing all the elements from fromElement onwards.
4154     * The subset supports all operations supported by the underlying
4155     * set and all actions taking place on the subset are also reflected
4156     * in the underlying set.  A lock is obtained on the mutex prior to
4157     * subset creation.  The subset retains the thread-safe status of
4158     * this set.
4159     *
4160     * @param fromElement the inclusive lower range of the subset.
4161     * @return a subset from fromElement to <code>last()</code>.
4162     * @throws ClassCastException if fromElement is not comparable to the underlying
4163     *         set's contents.
4164     * @throws IllegalArgumentException if fromElement is outside the set's range.
4165     * @throws NullPointerException if fromElement is null. but the set does not allow
4166     *         null elements.
4167     */
4168    public SortedSet<T> tailSet(T fromElement)
4169    {
4170      synchronized (mutex)
4171        {
4172          return new SynchronizedSortedSet<T>(mutex, ss.tailSet(fromElement));
4173        }
4174    }
4175  } // class SynchronizedSortedSet
4176
4177
4178  /**
4179   * Returns an unmodifiable view of the given collection. This allows
4180   * "read-only" access, although changes in the backing collection show up
4181   * in this view. Attempts to modify the collection directly or via iterators
4182   * will fail with {@link UnsupportedOperationException}.  Although this view
4183   * prevents changes to the structure of the collection and its elements, the values
4184   * referenced by the objects in the collection can still be modified.
4185   * <p>
4186   *
4187   * Since the collection might be a List or a Set, and those have incompatible
4188   * equals and hashCode requirements, this relies on Object's implementation
4189   * rather than passing those calls on to the wrapped collection. The returned
4190   * Collection implements Serializable, but can only be serialized if
4191   * the collection it wraps is likewise Serializable.
4192   *
4193   * @param c the collection to wrap
4194   * @return a read-only view of the collection
4195   * @see Serializable
4196   */
4197  public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)
4198  {
4199    return new UnmodifiableCollection<T>(c);
4200  }
4201
4202  /**
4203   * The implementation of {@link #unmodifiableCollection(Collection)}. This
4204   * class name is required for compatibility with Sun's JDK serializability.
4205   *
4206   * @author Eric Blake (ebb9@email.byu.edu)
4207   */
4208  private static class UnmodifiableCollection<T>
4209    implements Collection<T>, Serializable
4210  {
4211    /**
4212     * Compatible with JDK 1.4.
4213     */
4214    private static final long serialVersionUID = 1820017752578914078L;
4215
4216    /**
4217     * The wrapped collection. Package visible for use by subclasses.
4218     * @serial the real collection
4219     */
4220    final Collection<? extends T> c;
4221
4222    /**
4223     * Wrap a given collection.
4224     * @param c the collection to wrap
4225     * @throws NullPointerException if c is null
4226     */
4227    UnmodifiableCollection(Collection<? extends T> c)
4228    {
4229      this.c = c;
4230      if (c == null)
4231        throw new NullPointerException();
4232    }
4233
4234    /**
4235     * Blocks the addition of elements to the underlying collection.
4236     * This method never returns, throwing an exception instead.
4237     *
4238     * @param o the object to add.
4239     * @return <code>true</code> if the collection was modified as a result of this action.
4240     * @throws UnsupportedOperationException as an unmodifiable collection does not
4241     *         support the add operation.
4242     */
4243    public boolean add(T o)
4244    {
4245      throw new UnsupportedOperationException();
4246    }
4247
4248    /**
4249     * Blocks the addition of a collection of elements to the underlying
4250     * collection.  This method never returns, throwing an exception instead.
4251     *
4252     * @param c the collection to add.
4253     * @return <code>true</code> if the collection was modified as a result of this action.
4254     * @throws UnsupportedOperationException as an unmodifiable collection does not
4255     *         support the <code>addAll</code> operation.
4256     */
4257    public boolean addAll(Collection<? extends T> c)
4258    {
4259      throw new UnsupportedOperationException();
4260    }
4261
4262    /**
4263     * Blocks the clearing of the underlying collection.  This method never
4264     * returns, throwing an exception instead.
4265     *
4266     * @throws UnsupportedOperationException as an unmodifiable collection does
4267     *         not support the <code>clear()</code> operation.
4268     */
4269    public void clear()
4270    {
4271      throw new UnsupportedOperationException();
4272    }
4273
4274    /**
4275     * Test whether the underlying collection contains a given object as one of its
4276     * elements.
4277     *
4278     * @param o the element to look for.
4279     * @return <code>true</code> if the underlying collection contains at least
4280     *         one element e such that
4281     *         <code>o == null ? e == null : o.equals(e)</code>.
4282     * @throws ClassCastException if the type of o is not a valid type for the
4283     *         underlying collection.
4284     * @throws NullPointerException if o is null and the underlying collection
4285     *         doesn't support null values.
4286     */
4287    public boolean contains(Object o)
4288    {
4289      return c.contains(o);
4290    }
4291
4292    /**
4293     * Test whether the underlying collection contains every element in a given
4294     * collection.
4295     *
4296     * @param c1 the collection to test for.
4297     * @return <code>true</code> if for every element o in c, contains(o) would
4298     *         return <code>true</code>.
4299     * @throws ClassCastException if the type of any element in c is not a valid
4300     *   type for the underlying collection.
4301     * @throws NullPointerException if some element of c is null and the underlying
4302     *   collection does not support null values.
4303     * @throws NullPointerException if c itself is null.
4304     */
4305    public boolean containsAll(Collection<?> c1)
4306    {
4307      return c.containsAll(c1);
4308    }
4309
4310    /**
4311     * Tests whether the underlying collection is empty, that is,
4312     * if size() == 0.
4313     *
4314     * @return <code>true</code> if this collection contains no elements.
4315     */
4316    public boolean isEmpty()
4317    {
4318      return c.isEmpty();
4319    }
4320
4321    /**
4322     * Obtain an Iterator over the underlying collection, which maintains
4323     * its unmodifiable nature.
4324     *
4325     * @return an UnmodifiableIterator over the elements of the underlying
4326     *         collection, in any order.
4327     */
4328    public Iterator<T> iterator()
4329    {
4330      return new UnmodifiableIterator<T>(c.iterator());
4331    }
4332
4333    /**
4334     * Blocks the removal of an object from the underlying collection.
4335     * This method never returns, throwing an exception instead.
4336     *
4337     * @param o The object to remove.
4338     * @return <code>true</code> if the object was removed (i.e. the underlying
4339     *         collection returned 1 or more instances of o).
4340     * @throws UnsupportedOperationException as an unmodifiable collection
4341     *         does not support the <code>remove()</code> operation.
4342     */
4343    public boolean remove(Object o)
4344    {
4345      throw new UnsupportedOperationException();
4346    }
4347
4348    /**
4349     * Blocks the removal of a collection of objects from the underlying
4350     * collection.  This method never returns, throwing an exception
4351     * instead.
4352     *
4353     * @param c The collection of objects to remove.
4354     * @return <code>true</code> if the collection was modified.
4355     * @throws UnsupportedOperationException as an unmodifiable collection
4356     *         does not support the <code>removeAll()</code> operation.
4357     */
4358    public boolean removeAll(Collection<?> c)
4359    {
4360      throw new UnsupportedOperationException();
4361    }
4362
4363    /**
4364     * Blocks the removal of all elements from the underlying collection,
4365     * except those in the supplied collection.  This method never returns,
4366     * throwing an exception instead.
4367     *
4368     * @param c The collection of objects to retain.
4369     * @return <code>true</code> if the collection was modified.
4370     * @throws UnsupportedOperationException as an unmodifiable collection
4371     *         does not support the <code>retainAll()</code> operation.
4372     */
4373    public boolean retainAll(Collection<?> c)
4374    {
4375      throw new UnsupportedOperationException();
4376    }
4377
4378    /**
4379     * Retrieves the number of elements in the underlying collection.
4380     *
4381     * @return the number of elements in the collection.
4382     */
4383    public int size()
4384    {
4385      return c.size();
4386    }
4387
4388    /**
4389     * Copy the current contents of the underlying collection into an array.
4390     *
4391     * @return an array of type Object[] with a length equal to the size of the
4392     *         underlying collection and containing the elements currently in
4393     *         the underlying collection, in any order.
4394     */
4395    public Object[] toArray()
4396    {
4397      return c.toArray();
4398    }
4399
4400    /**
4401     * Copy the current contents of the underlying collection into an array.  If
4402     * the array passed as an argument has length less than the size of the
4403     * underlying collection, an array of the same run-time type as a, with a length
4404     * equal to the size of the underlying collection, is allocated using reflection.
4405     * Otherwise, a itself is used.  The elements of the underlying collection are
4406     * copied into it, and if there is space in the array, the following element is
4407     * set to null. The resultant array is returned.
4408     * Note: The fact that the following element is set to null is only useful
4409     * if it is known that this collection does not contain any null elements.
4410     *
4411     * @param a the array to copy this collection into.
4412     * @return an array containing the elements currently in the underlying
4413     *         collection, in any order.
4414     * @throws ArrayStoreException if the type of any element of the
4415     *         collection is not a subtype of the element type of a.
4416     */
4417    public <S> S[] toArray(S[] a)
4418    {
4419      return c.toArray(a);
4420    }
4421
4422    /**
4423     * A textual representation of the unmodifiable collection.
4424     *
4425     * @return The unmodifiable collection in the form of a <code>String</code>.
4426     */
4427    public String toString()
4428    {
4429      return c.toString();
4430    }
4431  } // class UnmodifiableCollection
4432
4433  /**
4434   * The implementation of the various iterator methods in the
4435   * unmodifiable classes.
4436   *
4437   * @author Eric Blake (ebb9@email.byu.edu)
4438   */
4439  private static class UnmodifiableIterator<T> implements Iterator<T>
4440  {
4441    /**
4442     * The wrapped iterator.
4443     */
4444    private final Iterator<? extends T> i;
4445
4446    /**
4447     * Only trusted code creates a wrapper.
4448     * @param i the wrapped iterator
4449     */
4450    UnmodifiableIterator(Iterator<? extends T> i)
4451    {
4452      this.i = i;
4453    }
4454
4455    /**
4456     * Obtains the next element in the underlying collection.
4457     *
4458     * @return the next element in the collection.
4459     * @throws NoSuchElementException if there are no more elements.
4460     */
4461    public T next()
4462    {
4463      return i.next();
4464    }
4465
4466    /**
4467     * Tests whether there are still elements to be retrieved from the
4468     * underlying collection by <code>next()</code>.  When this method
4469     * returns <code>true</code>, an exception will not be thrown on calling
4470     * <code>next()</code>.
4471     *
4472     * @return <code>true</code> if there is at least one more element in the underlying
4473     *         collection.
4474     */
4475    public boolean hasNext()
4476    {
4477      return i.hasNext();
4478    }
4479
4480    /**
4481     * Blocks the removal of elements from the underlying collection by the
4482     * iterator.
4483     *
4484     * @throws UnsupportedOperationException as an unmodifiable collection
4485     *         does not support the removal of elements by its iterator.
4486     */
4487    public void remove()
4488    {
4489      throw new UnsupportedOperationException();
4490    }
4491  } // class UnmodifiableIterator
4492
4493  /**
4494   * Returns an unmodifiable view of the given list. This allows
4495   * "read-only" access, although changes in the backing list show up
4496   * in this view. Attempts to modify the list directly, via iterators, or
4497   * via sublists, will fail with {@link UnsupportedOperationException}.
4498   * Although this view prevents changes to the structure of the list and
4499   * its elements, the values referenced by the objects in the list can
4500   * still be modified.
4501   * <p>
4502   *
4503   * The returned List implements Serializable, but can only be serialized if
4504   * the list it wraps is likewise Serializable. In addition, if the wrapped
4505   * list implements RandomAccess, this does too.
4506   *
4507   * @param l the list to wrap
4508   * @return a read-only view of the list
4509   * @see Serializable
4510   * @see RandomAccess
4511   */
4512  public static <T> List<T> unmodifiableList(List<? extends T> l)
4513  {
4514    if (l instanceof RandomAccess)
4515      return new UnmodifiableRandomAccessList<T>(l);
4516    return new UnmodifiableList<T>(l);
4517  }
4518
4519  /**
4520   * The implementation of {@link #unmodifiableList(List)} for sequential
4521   * lists. This class name is required for compatibility with Sun's JDK
4522   * serializability.
4523   *
4524   * @author Eric Blake (ebb9@email.byu.edu)
4525   */
4526  private static class UnmodifiableList<T> extends UnmodifiableCollection<T>
4527    implements List<T>
4528  {
4529    /**
4530     * Compatible with JDK 1.4.
4531     */
4532    private static final long serialVersionUID = -283967356065247728L;
4533
4534
4535    /**
4536     * The wrapped list; stored both here and in the superclass to avoid
4537     * excessive casting. Package visible for use by subclass.
4538     * @serial the wrapped list
4539     */
4540    final List<T> list;
4541
4542    /**
4543     * Wrap a given list.
4544     * @param l the list to wrap
4545     * @throws NullPointerException if l is null
4546     */
4547    UnmodifiableList(List<? extends T> l)
4548    {
4549      super(l);
4550      list = (List<T>) l;
4551    }
4552
4553    /**
4554     * Blocks the addition of an element to the underlying
4555     * list at a specific index.  This method never returns,
4556     * throwing an exception instead.
4557     *
4558     * @param index The index at which to place the new element.
4559     * @param o the object to add.
4560     * @throws UnsupportedOperationException as an unmodifiable
4561     *         list doesn't support the <code>add()</code> operation.
4562     */
4563    public void add(int index, T o)
4564    {
4565      throw new UnsupportedOperationException();
4566    }
4567
4568    /**
4569     * Blocks the addition of a collection of elements to the
4570     * underlying list at a specific index.  This method never
4571     * returns, throwing an exception instead.
4572     *
4573     * @param index The index at which to place the new element.
4574     * @param c the collections of objects to add.
4575     * @throws UnsupportedOperationException as an unmodifiable
4576     *         list doesn't support the <code>addAll()</code> operation.
4577     */
4578    public boolean addAll(int index, Collection<? extends T> c)
4579    {
4580      throw new UnsupportedOperationException();
4581    }
4582
4583    /**
4584     * Returns <code>true</code> if the object, o, is an instance of
4585     * <code>List</code> with the same size and elements
4586     * as the underlying list.
4587     *
4588     * @param o The object to compare.
4589     * @return <code>true</code> if o is equivalent to the underlying list.
4590     */
4591    public boolean equals(Object o)
4592    {
4593      return list.equals(o);
4594    }
4595
4596    /**
4597     * Retrieves the element at a given index in the underlying list.
4598     *
4599     * @param index the index of the element to be returned
4600     * @return the element at index index in this list
4601     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
4602     */
4603    public T get(int index)
4604    {
4605      return list.get(index);
4606    }
4607
4608    /**
4609     * Computes the hash code for the underlying list.
4610     * The exact computation is described in the documentation
4611     * of the <code>List</code> interface.
4612     *
4613     * @return The hash code of the underlying list.
4614     * @see List#hashCode()
4615     */
4616    public int hashCode()
4617    {
4618      return list.hashCode();
4619    }
4620
4621    /**
4622     * Obtain the first index at which a given object is to be found in the
4623     * underlying list.
4624     *
4625     * @param o the object to search for
4626     * @return the least integer n such that <code>o == null ? get(n) == null :
4627     *         o.equals(get(n))</code>, or -1 if there is no such index.
4628     * @throws ClassCastException if the type of o is not a valid
4629     *         type for the underlying list.
4630     * @throws NullPointerException if o is null and the underlying
4631     *         list does not support null values.
4632     */
4633    public int indexOf(Object o)
4634    {
4635      return list.indexOf(o);
4636    }
4637
4638    /**
4639     * Obtain the last index at which a given object is to be found in the
4640     * underlying list.
4641     *
4642     * @return the greatest integer n such that <code>o == null ? get(n) == null
4643     *         : o.equals(get(n))</code>, or -1 if there is no such index.
4644     * @throws ClassCastException if the type of o is not a valid
4645     *         type for the underlying list.
4646     * @throws NullPointerException if o is null and the underlying
4647     *         list does not support null values.
4648     */
4649    public int lastIndexOf(Object o)
4650    {
4651      return list.lastIndexOf(o);
4652    }
4653
4654  /**
4655   * Obtains a list iterator over the underlying list, starting at the beginning
4656   * and maintaining the unmodifiable nature of this list.
4657   *
4658   * @return a <code>UnmodifiableListIterator</code> over the elements of the
4659   *         underlying list, in order, starting at the beginning.
4660   */
4661    public ListIterator<T> listIterator()
4662    {
4663      return new UnmodifiableListIterator<T>(list.listIterator());
4664    }
4665
4666  /**
4667   * Obtains a list iterator over the underlying list, starting at the specified
4668   * index and maintaining the unmodifiable nature of this list.  An initial call
4669   * to <code>next()</code> will retrieve the element at the specified index,
4670   * and an initial call to <code>previous()</code> will retrieve the element
4671   * at index - 1.
4672   *
4673   *
4674   * @param index the position, between 0 and size() inclusive, to begin the
4675   *        iteration from.
4676   * @return a <code>UnmodifiableListIterator</code> over the elements of the
4677   *         underlying list, in order, starting at the specified index.
4678   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
4679   */
4680    public ListIterator<T> listIterator(int index)
4681    {
4682      return new UnmodifiableListIterator<T>(list.listIterator(index));
4683    }
4684
4685    /**
4686     * Blocks the removal of the element at the specified index.
4687     * This method never returns, throwing an exception instead.
4688     *
4689     * @param index The index of the element to remove.
4690     * @return the removed element.
4691     * @throws UnsupportedOperationException as an unmodifiable
4692     *         list does not support the <code>remove()</code>
4693     *         operation.
4694     */
4695    public T remove(int index)
4696    {
4697      throw new UnsupportedOperationException();
4698    }
4699
4700    /**
4701     * Blocks the replacement of the element at the specified index.
4702     * This method never returns, throwing an exception instead.
4703     *
4704     * @param index The index of the element to replace.
4705     * @param o The new object to place at the specified index.
4706     * @return the replaced element.
4707     * @throws UnsupportedOperationException as an unmodifiable
4708     *         list does not support the <code>set()</code>
4709     *         operation.
4710     */
4711    public T set(int index, T o)
4712    {
4713      throw new UnsupportedOperationException();
4714    }
4715
4716    /**
4717     * Obtain a List view of a subsection of the underlying list, from
4718     * fromIndex (inclusive) to toIndex (exclusive). If the two indices
4719     * are equal, the sublist is empty. The returned list will be
4720     * unmodifiable, like this list.  Changes to the elements of the
4721     * returned list will be reflected in the underlying list. No structural
4722     * modifications can take place in either list.
4723     *
4724     * @param fromIndex the index that the returned list should start from
4725     *        (inclusive).
4726     * @param toIndex the index that the returned list should go to (exclusive).
4727     * @return a List backed by a subsection of the underlying list.
4728     * @throws IndexOutOfBoundsException if fromIndex &lt; 0
4729     *         || toIndex &gt; size() || fromIndex &gt; toIndex.
4730     */
4731    public List<T> subList(int fromIndex, int toIndex)
4732    {
4733      return unmodifiableList(list.subList(fromIndex, toIndex));
4734    }
4735  } // class UnmodifiableList
4736
4737  /**
4738   * The implementation of {@link #unmodifiableList(List)} for random-access
4739   * lists. This class name is required for compatibility with Sun's JDK
4740   * serializability.
4741   *
4742   * @author Eric Blake (ebb9@email.byu.edu)
4743   */
4744  private static final class UnmodifiableRandomAccessList<T>
4745    extends UnmodifiableList<T> implements RandomAccess
4746  {
4747    /**
4748     * Compatible with JDK 1.4.
4749     */
4750    private static final long serialVersionUID = -2542308836966382001L;
4751
4752    /**
4753     * Wrap a given list.
4754     * @param l the list to wrap
4755     * @throws NullPointerException if l is null
4756     */
4757    UnmodifiableRandomAccessList(List<? extends T> l)
4758    {
4759      super(l);
4760    }
4761  } // class UnmodifiableRandomAccessList
4762
4763  /**
4764   * The implementation of {@link UnmodifiableList#listIterator()}.
4765   *
4766   * @author Eric Blake (ebb9@email.byu.edu)
4767   */
4768  private static final class UnmodifiableListIterator<T>
4769    extends UnmodifiableIterator<T> implements ListIterator<T>
4770  {
4771    /**
4772     * The wrapped iterator, stored both here and in the superclass to
4773     * avoid excessive casting.
4774     */
4775    private final ListIterator<T> li;
4776
4777    /**
4778     * Only trusted code creates a wrapper.
4779     * @param li the wrapped iterator
4780     */
4781    UnmodifiableListIterator(ListIterator<T> li)
4782    {
4783      super(li);
4784      this.li = li;
4785    }
4786
4787    /**
4788     * Blocks the addition of an object to the list underlying this iterator.
4789     * This method never returns, throwing an exception instead.
4790     *
4791     * @param o The object to add.
4792     * @throws UnsupportedOperationException as the iterator of an unmodifiable
4793     *         list does not support the <code>add()</code> operation.
4794     */
4795    public void add(T o)
4796    {
4797      throw new UnsupportedOperationException();
4798    }
4799
4800    /**
4801     * Tests whether there are still elements to be retrieved from the
4802     * underlying collection by <code>previous()</code>.  When this method
4803     * returns <code>true</code>, an exception will not be thrown on calling
4804     * <code>previous()</code>.
4805     *
4806     * @return <code>true</code> if there is at least one more element prior to the
4807     *         current position in the underlying list.
4808     */
4809    public boolean hasPrevious()
4810    {
4811      return li.hasPrevious();
4812    }
4813
4814    /**
4815     * Find the index of the element that would be returned by a call to next.
4816     * If <code>hasNext()</code> returns <code>false</code>, this returns the list size.
4817     *
4818     * @return the index of the element that would be returned by
4819     *         <code>next()</code>.
4820     */
4821    public int nextIndex()
4822    {
4823      return li.nextIndex();
4824    }
4825
4826    /**
4827     * Obtains the previous element in the underlying list.
4828     *
4829     * @return the previous element in the list.
4830     * @throws NoSuchElementException if there are no more prior elements.
4831     */
4832    public T previous()
4833    {
4834      return li.previous();
4835    }
4836
4837    /**
4838     * Find the index of the element that would be returned by a call to
4839     * previous. If <code>hasPrevious()</code> returns <code>false</code>,
4840     * this returns -1.
4841     *
4842     * @return the index of the element that would be returned by
4843     *         <code>previous()</code>.
4844     */
4845    public int previousIndex()
4846    {
4847      return li.previousIndex();
4848    }
4849
4850    /**
4851     * Blocks the replacement of an element in the list underlying this
4852     * iterator.  This method never returns, throwing an exception instead.
4853     *
4854     * @param o The new object to replace the existing one.
4855     * @throws UnsupportedOperationException as the iterator of an unmodifiable
4856     *         list does not support the <code>set()</code> operation.
4857     */
4858    public void set(T o)
4859    {
4860      throw new UnsupportedOperationException();
4861    }
4862  } // class UnmodifiableListIterator
4863
4864  /**
4865   * Returns an unmodifiable view of the given map. This allows "read-only"
4866   * access, although changes in the backing map show up in this view.
4867   * Attempts to modify the map directly, or via collection views or their
4868   * iterators will fail with {@link UnsupportedOperationException}.
4869   * Although this view prevents changes to the structure of the map and its
4870   * entries, the values referenced by the objects in the map can still be
4871   * modified.
4872   * <p>
4873   *
4874   * The returned Map implements Serializable, but can only be serialized if
4875   * the map it wraps is likewise Serializable.
4876   *
4877   * @param m the map to wrap
4878   * @return a read-only view of the map
4879   * @see Serializable
4880   */
4881  public static <K, V> Map<K, V> unmodifiableMap(Map<? extends K,
4882                                                 ? extends V> m)
4883  {
4884    return new UnmodifiableMap<K, V>(m);
4885  }
4886
4887  /**
4888   * The implementation of {@link #unmodifiableMap(Map)}. This
4889   * class name is required for compatibility with Sun's JDK serializability.
4890   *
4891   * @author Eric Blake (ebb9@email.byu.edu)
4892   */
4893  private static class UnmodifiableMap<K, V> implements Map<K, V>, Serializable
4894  {
4895    /**
4896     * Compatible with JDK 1.4.
4897     */
4898    private static final long serialVersionUID = -1034234728574286014L;
4899
4900    /**
4901     * The wrapped map.
4902     * @serial the real map
4903     */
4904    private final Map<K, V> m;
4905
4906    /**
4907     * Cache the entry set.
4908     */
4909    private transient Set<Map.Entry<K, V>> entries;
4910
4911    /**
4912     * Cache the key set.
4913     */
4914    private transient Set<K> keys;
4915
4916    /**
4917     * Cache the value collection.
4918     */
4919    private transient Collection<V> values;
4920
4921    /**
4922     * Wrap a given map.
4923     * @param m the map to wrap
4924     * @throws NullPointerException if m is null
4925     */
4926    UnmodifiableMap(Map<? extends K, ? extends V> m)
4927    {
4928      this.m = (Map<K,V>) m;
4929      if (m == null)
4930        throw new NullPointerException();
4931    }
4932
4933    /**
4934     * Blocks the clearing of entries from the underlying map.
4935     * This method never returns, throwing an exception instead.
4936     *
4937     * @throws UnsupportedOperationException as an unmodifiable
4938     *         map does not support the <code>clear()</code> operation.
4939     */
4940    public void clear()
4941    {
4942      throw new UnsupportedOperationException();
4943    }
4944
4945    /**
4946     * Returns <code>true</code> if the underlying map contains a mapping for
4947     * the given key.
4948     *
4949     * @param key the key to search for
4950     * @return <code>true</code> if the map contains the key
4951     * @throws ClassCastException if the key is of an inappropriate type
4952     * @throws NullPointerException if key is <code>null</code> but the map
4953     *         does not permit null keys
4954     */
4955    public boolean containsKey(Object key)
4956    {
4957      return m.containsKey(key);
4958    }
4959
4960    /**
4961     * Returns <code>true</code> if the underlying map contains at least one mapping with
4962     * the given value.  In other words, it returns <code>true</code> if a value v exists where
4963     * <code>(value == null ? v == null : value.equals(v))</code>. This usually
4964     * requires linear time.
4965     *
4966     * @param value the value to search for
4967     * @return <code>true</code> if the map contains the value
4968     * @throws ClassCastException if the type of the value is not a valid type
4969     *         for this map.
4970     * @throws NullPointerException if the value is null and the map doesn't
4971     *         support null values.
4972     */
4973    public boolean containsValue(Object value)
4974    {
4975      return m.containsValue(value);
4976    }
4977
4978    /**
4979     * Returns a unmodifiable set view of the entries in the underlying map.
4980     * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>.
4981     * The set is backed by the map, so that changes in one show up in the other.
4982     * Modifications made while an iterator is in progress cause undefined
4983     * behavior.  These modifications are again limited to the values of
4984     * the objects.
4985     *
4986     * @return the unmodifiable set view of all mapping entries.
4987     * @see Map.Entry
4988     */
4989    public Set<Map.Entry<K, V>> entrySet()
4990    {
4991      if (entries == null)
4992        entries = new UnmodifiableEntrySet<K,V>(m.entrySet());
4993      return entries;
4994    }
4995
4996    /**
4997     * The implementation of {@link UnmodifiableMap#entrySet()}. This class
4998     * name is required for compatibility with Sun's JDK serializability.
4999     *
5000     * @author Eric Blake (ebb9@email.byu.edu)
5001     */
5002    private static final class UnmodifiableEntrySet<K,V>
5003      extends UnmodifiableSet<Map.Entry<K,V>>
5004      implements Serializable
5005    {
5006      // Unmodifiable implementation of Map.Entry used as return value for
5007      // UnmodifiableEntrySet accessors (iterator, toArray, toArray(Object[]))
5008      private static final class UnmodifiableMapEntry<K,V>
5009          implements Map.Entry<K,V>
5010      {
5011        private final Map.Entry<K,V> e;
5012
5013        private UnmodifiableMapEntry(Map.Entry<K,V> e)
5014        {
5015          super();
5016          this.e = e;
5017        }
5018
5019        /**
5020         * Returns <code>true</code> if the object, o, is also a map entry
5021         * with an identical key and value.
5022         *
5023         * @param o the object to compare.
5024         * @return <code>true</code> if o is an equivalent map entry.
5025         */
5026        public boolean equals(Object o)
5027        {
5028          return e.equals(o);
5029        }
5030
5031        /**
5032         * Returns the key of this map entry.
5033         *
5034         * @return the key.
5035         */
5036        public K getKey()
5037        {
5038          return e.getKey();
5039        }
5040
5041        /**
5042         * Returns the value of this map entry.
5043         *
5044         * @return the value.
5045         */
5046        public V getValue()
5047        {
5048          return e.getValue();
5049        }
5050
5051        /**
5052         * Computes the hash code of this map entry. The computation is
5053         * described in the <code>Map</code> interface documentation.
5054         *
5055         * @return the hash code of this entry.
5056         * @see Map#hashCode()
5057         */
5058        public int hashCode()
5059        {
5060          return e.hashCode();
5061        }
5062
5063        /**
5064         * Blocks the alteration of the value of this map entry. This method
5065         * never returns, throwing an exception instead.
5066         *
5067         * @param value The new value.
5068         * @throws UnsupportedOperationException as an unmodifiable map entry
5069         *           does not support the <code>setValue()</code> operation.
5070         */
5071        public V setValue(V value)
5072        {
5073          throw new UnsupportedOperationException();
5074        }
5075
5076        /**
5077         * Returns a textual representation of the map entry.
5078         *
5079         * @return The map entry as a <code>String</code>.
5080         */
5081        public String toString()
5082        {
5083          return e.toString();
5084        }
5085      }
5086
5087      /**
5088       * Compatible with JDK 1.4.
5089       */
5090      private static final long serialVersionUID = 7854390611657943733L;
5091
5092      /**
5093       * Wrap a given set.
5094       * @param s the set to wrap
5095       */
5096      UnmodifiableEntrySet(Set<Map.Entry<K,V>> s)
5097      {
5098        super(s);
5099      }
5100
5101      // The iterator must return unmodifiable map entries.
5102      public Iterator<Map.Entry<K,V>> iterator()
5103      {
5104        return new UnmodifiableIterator<Map.Entry<K,V>>(c.iterator())
5105        {
5106          /**
5107           * Obtains the next element from the underlying set of
5108           * map entries.
5109           *
5110           * @return the next element in the collection.
5111           * @throws NoSuchElementException if there are no more elements.
5112           */
5113          public Map.Entry<K,V> next()
5114          {
5115            final Map.Entry<K,V> e = super.next();
5116            return new UnmodifiableMapEntry<K,V>(e);
5117          }
5118        };
5119      }
5120
5121      // The array returned is an array of UnmodifiableMapEntry instead of
5122      // Map.Entry
5123      public Object[] toArray()
5124      {
5125        Object[] mapEntryResult = super.toArray();
5126        UnmodifiableMapEntry<K,V> result[] = null;
5127
5128        if (mapEntryResult != null)
5129          {
5130            result = (UnmodifiableMapEntry<K,V>[])
5131              new UnmodifiableMapEntry[mapEntryResult.length];
5132            for (int i = 0; i < mapEntryResult.length; ++i)
5133              result[i] = new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>)mapEntryResult[i]);
5134          }
5135        return result;
5136      }
5137
5138      // The array returned is an array of UnmodifiableMapEntry instead of
5139      // Map.Entry
5140      public <S> S[] toArray(S[] array)
5141      {
5142        S[] result = super.toArray(array);
5143
5144        if (result != null)
5145          for (int i = 0; i < result.length; i++)
5146            array[i] =
5147              (S) new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>) result[i]);
5148        return array;
5149      }
5150
5151
5152    } // class UnmodifiableEntrySet
5153
5154    /**
5155     * Returns <code>true</code> if the object, o, is also an instance
5156     * of <code>Map</code> with an equal set of map entries.
5157     *
5158     * @param o The object to compare.
5159     * @return <code>true</code> if o is an equivalent map.
5160     */
5161    public boolean equals(Object o)
5162    {
5163      return m.equals(o);
5164    }
5165
5166    /**
5167     * Returns the value associated with the supplied key or
5168     * null if no such mapping exists.  An ambiguity can occur
5169     * if null values are accepted by the underlying map.
5170     * In this case, <code>containsKey()</code> can be used
5171     * to separate the two possible cases of a null result.
5172     *
5173     * @param key The key to look up.
5174     * @return the value associated with the key, or null if key not in map.
5175     * @throws ClassCastException if the key is an inappropriate type.
5176     * @throws NullPointerException if this map does not accept null keys.
5177     * @see #containsKey(Object)
5178     */
5179    public V get(Object key)
5180    {
5181      return m.get(key);
5182    }
5183
5184    /**
5185     * Blocks the addition of a new entry to the underlying map.
5186     * This method never returns, throwing an exception instead.
5187     *
5188     * @param key The new key.
5189     * @param value The new value.
5190     * @return the previous value of the key, or null if there was no mapping.
5191     * @throws UnsupportedOperationException as an unmodifiable
5192     *         map does not support the <code>put()</code> operation.
5193     */
5194    public V put(K key, V value)
5195    {
5196      throw new UnsupportedOperationException();
5197    }
5198
5199    /**
5200     * Computes the hash code for the underlying map, as the sum
5201     * of the hash codes of all entries.
5202     *
5203     * @return The hash code of the underlying map.
5204     * @see Map.Entry#hashCode()
5205     */
5206    public int hashCode()
5207    {
5208      return m.hashCode();
5209    }
5210
5211    /**
5212     * Returns <code>true</code> if the underlying map contains no entries.
5213     *
5214     * @return <code>true</code> if the map is empty.
5215     */
5216    public boolean isEmpty()
5217    {
5218      return m.isEmpty();
5219    }
5220
5221    /**
5222     * Returns a unmodifiable set view of the keys in the underlying map.
5223     * The set is backed by the map, so that changes in one show up in the other.
5224     * Modifications made while an iterator is in progress cause undefined
5225     * behavior.  These modifications are again limited to the values of
5226     * the keys.
5227     *
5228     * @return the set view of all keys.
5229     */
5230    public Set<K> keySet()
5231    {
5232      if (keys == null)
5233        keys = new UnmodifiableSet<K>(m.keySet());
5234      return keys;
5235    }
5236
5237    /**
5238     * Blocks the addition of the entries in the supplied map.
5239     * This method never returns, throwing an exception instead.
5240     *
5241     * @param m The map, the entries of which should be added
5242     *          to the underlying map.
5243     * @throws UnsupportedOperationException as an unmodifiable
5244     *         map does not support the <code>putAll</code> operation.
5245     */
5246    public void putAll(Map<? extends K, ? extends V> m)
5247    {
5248      throw new UnsupportedOperationException();
5249    }
5250
5251    /**
5252     * Blocks the removal of an entry from the map.
5253     * This method never returns, throwing an exception instead.
5254     *
5255     * @param o The key of the entry to remove.
5256     * @return The value the key was associated with, or null
5257     *         if no such mapping existed.  Null is also returned
5258     *         if the removed entry had a null key.
5259     * @throws UnsupportedOperationException as an unmodifiable
5260     *         map does not support the <code>remove</code> operation.
5261     */
5262    public V remove(Object o)
5263    {
5264      throw new UnsupportedOperationException();
5265    }
5266
5267
5268    /**
5269     * Returns the number of key-value mappings in the underlying map.
5270     * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
5271     * is returned.
5272     *
5273     * @return the number of mappings.
5274     */
5275    public int size()
5276    {
5277      return m.size();
5278    }
5279
5280    /**
5281     * Returns a textual representation of the map.
5282     *
5283     * @return The map in the form of a <code>String</code>.
5284     */
5285    public String toString()
5286    {
5287      return m.toString();
5288    }
5289
5290    /**
5291     * Returns a unmodifiable collection view of the values in the underlying map.
5292     * The collection is backed by the map, so that changes in one show up in the other.
5293     * Modifications made while an iterator is in progress cause undefined
5294     * behavior.  These modifications are again limited to the values of
5295     * the keys.
5296     *
5297     * @return the collection view of all values.
5298     */
5299    public Collection<V> values()
5300    {
5301      if (values == null)
5302        values = new UnmodifiableCollection<V>(m.values());
5303      return values;
5304    }
5305  } // class UnmodifiableMap
5306
5307  /**
5308   * Returns an unmodifiable view of the given set. This allows
5309   * "read-only" access, although changes in the backing set show up
5310   * in this view. Attempts to modify the set directly or via iterators
5311   * will fail with {@link UnsupportedOperationException}.
5312   * Although this view prevents changes to the structure of the set and its
5313   * entries, the values referenced by the objects in the set can still be
5314   * modified.
5315   * <p>
5316   *
5317   * The returned Set implements Serializable, but can only be serialized if
5318   * the set it wraps is likewise Serializable.
5319   *
5320   * @param s the set to wrap
5321   * @return a read-only view of the set
5322   * @see Serializable
5323   */
5324  public static <T> Set<T> unmodifiableSet(Set<? extends T> s)
5325  {
5326    return new UnmodifiableSet<T>(s);
5327  }
5328
5329  /**
5330   * The implementation of {@link #unmodifiableSet(Set)}. This class
5331   * name is required for compatibility with Sun's JDK serializability.
5332   *
5333   * @author Eric Blake (ebb9@email.byu.edu)
5334   */
5335  private static class UnmodifiableSet<T> extends UnmodifiableCollection<T>
5336    implements Set<T>
5337  {
5338    /**
5339     * Compatible with JDK 1.4.
5340     */
5341    private static final long serialVersionUID = -9215047833775013803L;
5342
5343    /**
5344     * Wrap a given set.
5345     * @param s the set to wrap
5346     * @throws NullPointerException if s is null
5347     */
5348    UnmodifiableSet(Set<? extends T> s)
5349    {
5350      super(s);
5351    }
5352
5353    /**
5354     * Returns <code>true</code> if the object, o, is also an instance of
5355     * <code>Set</code> of the same size and with the same entries.
5356     *
5357     * @return <code>true</code> if o is an equivalent set.
5358     */
5359    public boolean equals(Object o)
5360    {
5361      return c.equals(o);
5362    }
5363
5364    /**
5365     * Computes the hash code of this set, as the sum of the
5366     * hash codes of all elements within the set.
5367     *
5368     * @return the hash code of the set.
5369     */
5370    public int hashCode()
5371    {
5372      return c.hashCode();
5373    }
5374  } // class UnmodifiableSet
5375
5376  /**
5377   * Returns an unmodifiable view of the given sorted map. This allows
5378   * "read-only" access, although changes in the backing map show up in this
5379   * view. Attempts to modify the map directly, via subviews, via collection
5380   * views, or iterators, will fail with {@link UnsupportedOperationException}.
5381   * Although this view prevents changes to the structure of the map and its
5382   * entries, the values referenced by the objects in the map can still be
5383   * modified.
5384   * <p>
5385   *
5386   * The returned SortedMap implements Serializable, but can only be
5387   * serialized if the map it wraps is likewise Serializable.
5388   *
5389   * @param m the map to wrap
5390   * @return a read-only view of the map
5391   * @see Serializable
5392   */
5393  public static <K, V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K,
5394                                                             ? extends V> m)
5395  {
5396    return new UnmodifiableSortedMap<K, V>(m);
5397  }
5398
5399  /**
5400   * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
5401   * class name is required for compatibility with Sun's JDK serializability.
5402   *
5403   * @author Eric Blake (ebb9@email.byu.edu)
5404   */
5405  private static class UnmodifiableSortedMap<K, V>
5406    extends UnmodifiableMap<K, V>
5407    implements SortedMap<K, V>
5408  {
5409    /**
5410     * Compatible with JDK 1.4.
5411     */
5412    private static final long serialVersionUID = -8806743815996713206L;
5413
5414    /**
5415     * The wrapped map; stored both here and in the superclass to avoid
5416     * excessive casting.
5417     * @serial the wrapped map
5418     */
5419    private final SortedMap<K, V> sm;
5420
5421    /**
5422     * Wrap a given map.
5423     * @param sm the map to wrap
5424     * @throws NullPointerException if sm is null
5425     */
5426    UnmodifiableSortedMap(SortedMap<K, ? extends V> sm)
5427    {
5428      super(sm);
5429      this.sm = (SortedMap<K,V>) sm;
5430    }
5431
5432    /**
5433     * Returns the comparator used in sorting the underlying map,
5434     * or null if it is the keys' natural ordering.
5435     *
5436     * @return the sorting comparator.
5437     */
5438    public Comparator<? super K> comparator()
5439    {
5440      return sm.comparator();
5441    }
5442
5443    /**
5444     * Returns the first (lowest sorted) key in the map.
5445     *
5446     * @return the first key.
5447     * @throws NoSuchElementException if this map is empty.
5448     */
5449    public K firstKey()
5450    {
5451      return sm.firstKey();
5452    }
5453
5454    /**
5455     * Returns a unmodifiable view of the portion of the map strictly less
5456     * than toKey. The view is backed by the underlying map, so changes in
5457     * one show up in the other.  The submap supports all optional operations
5458     * of the original.  This operation is equivalent to
5459     * <code>subMap(firstKey(), toKey)</code>.
5460     * <p>
5461     *
5462     * The returned map throws an IllegalArgumentException any time a key is
5463     * used which is out of the range of toKey. Note that the endpoint, toKey,
5464     * is not included; if you want this value to be included, pass its successor
5465     * object in to toKey.  For example, for Integers, you could request
5466     * <code>headMap(new Integer(limit.intValue() + 1))</code>.
5467     *
5468     * @param toKey the exclusive upper range of the submap.
5469     * @return the submap.
5470     * @throws ClassCastException if toKey is not comparable to the map contents.
5471     * @throws IllegalArgumentException if this is a subMap, and toKey is out
5472     *         of range.
5473     * @throws NullPointerException if toKey is null but the map does not allow
5474     *         null keys.
5475     */
5476    public SortedMap<K, V> headMap(K toKey)
5477    {
5478      return new UnmodifiableSortedMap<K, V>(sm.headMap(toKey));
5479    }
5480
5481    /**
5482     * Returns the last (highest sorted) key in the map.
5483     *
5484     * @return the last key.
5485     * @throws NoSuchElementException if this map is empty.
5486     */
5487    public K lastKey()
5488    {
5489      return sm.lastKey();
5490    }
5491
5492    /**
5493     * Returns a unmodifiable view of the portion of the map greater than or
5494     * equal to fromKey, and strictly less than toKey. The view is backed by
5495     * the underlying map, so changes in one show up in the other. The submap
5496     * supports all optional operations of the original.
5497     * <p>
5498     *
5499     * The returned map throws an IllegalArgumentException any time a key is
5500     * used which is out of the range of fromKey and toKey. Note that the
5501     * lower endpoint is included, but the upper is not; if you want to
5502     * change the inclusion or exclusion of an endpoint, pass its successor
5503     * object in instead.  For example, for Integers, you could request
5504     * <code>subMap(new Integer(lowlimit.intValue() + 1),
5505     * new Integer(highlimit.intValue() + 1))</code> to reverse
5506     * the inclusiveness of both endpoints.
5507     *
5508     * @param fromKey the inclusive lower range of the submap.
5509     * @param toKey the exclusive upper range of the submap.
5510     * @return the submap.
5511     * @throws ClassCastException if fromKey or toKey is not comparable to
5512     *         the map contents.
5513     * @throws IllegalArgumentException if this is a subMap, and fromKey or
5514     *         toKey is out of range.
5515     * @throws NullPointerException if fromKey or toKey is null but the map
5516     *         does not allow null keys.
5517     */
5518    public SortedMap<K, V> subMap(K fromKey, K toKey)
5519    {
5520      return new UnmodifiableSortedMap<K, V>(sm.subMap(fromKey, toKey));
5521    }
5522
5523    /**
5524     * Returns a unmodifiable view of the portion of the map greater than or
5525     * equal to fromKey. The view is backed by the underlying map, so changes
5526     * in one show up in the other. The submap supports all optional operations
5527     * of the original.
5528     * <p>
5529     *
5530     * The returned map throws an IllegalArgumentException any time a key is
5531     * used which is out of the range of fromKey. Note that the endpoint, fromKey, is
5532     * included; if you do not want this value to be included, pass its successor object in
5533     * to fromKey.  For example, for Integers, you could request
5534     * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
5535     *
5536     * @param fromKey the inclusive lower range of the submap
5537     * @return the submap
5538     * @throws ClassCastException if fromKey is not comparable to the map
5539     *         contents
5540     * @throws IllegalArgumentException if this is a subMap, and fromKey is out
5541     *         of range
5542     * @throws NullPointerException if fromKey is null but the map does not allow
5543     *         null keys
5544     */
5545    public SortedMap<K, V> tailMap(K fromKey)
5546    {
5547      return new UnmodifiableSortedMap<K, V>(sm.tailMap(fromKey));
5548    }
5549  } // class UnmodifiableSortedMap
5550
5551  /**
5552   * Returns an unmodifiable view of the given sorted set. This allows
5553   * "read-only" access, although changes in the backing set show up
5554   * in this view. Attempts to modify the set directly, via subsets, or via
5555   * iterators, will fail with {@link UnsupportedOperationException}.
5556   * Although this view prevents changes to the structure of the set and its
5557   * entries, the values referenced by the objects in the set can still be
5558   * modified.
5559   * <p>
5560   *
5561   * The returns SortedSet implements Serializable, but can only be
5562   * serialized if the set it wraps is likewise Serializable.
5563   *
5564   * @param s the set to wrap
5565   * @return a read-only view of the set
5566   * @see Serializable
5567   */
5568  public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)
5569  {
5570    return new UnmodifiableSortedSet<T>(s);
5571  }
5572
5573  /**
5574   * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
5575   * class name is required for compatibility with Sun's JDK serializability.
5576   *
5577   * @author Eric Blake (ebb9@email.byu.edu)
5578   */
5579  private static class UnmodifiableSortedSet<T> extends UnmodifiableSet<T>
5580    implements SortedSet<T>
5581  {
5582    /**
5583     * Compatible with JDK 1.4.
5584     */
5585    private static final long serialVersionUID = -4929149591599911165L;
5586
5587    /**
5588     * The wrapped set; stored both here and in the superclass to avoid
5589     * excessive casting.
5590     * @serial the wrapped set
5591     */
5592    private SortedSet<T> ss;
5593
5594    /**
5595     * Wrap a given set.
5596     * @param ss the set to wrap
5597     * @throws NullPointerException if ss is null
5598     */
5599    UnmodifiableSortedSet(SortedSet<T> ss)
5600    {
5601      super(ss);
5602      this.ss = ss;
5603    }
5604
5605    /**
5606     * Returns the comparator used in sorting the underlying set,
5607     * or null if it is the elements' natural ordering.
5608     *
5609     * @return the sorting comparator
5610     */
5611    public Comparator<? super T> comparator()
5612    {
5613      return ss.comparator();
5614    }
5615
5616    /**
5617     * Returns the first (lowest sorted) element in the underlying
5618     * set.
5619     *
5620     * @return the first element.
5621     * @throws NoSuchElementException if the set is empty.
5622     */
5623    public T first()
5624    {
5625      return ss.first();
5626    }
5627
5628    /**
5629     * Returns a unmodifiable view of the portion of the set strictly
5630     * less than toElement. The view is backed by the underlying set,
5631     * so changes in one show up in the other.  The subset supports
5632     * all optional operations of the original.  This operation
5633     * is equivalent to <code>subSet(first(), toElement)</code>.
5634     * <p>
5635     *
5636     * The returned set throws an IllegalArgumentException any time an element is
5637     * used which is out of the range of toElement. Note that the endpoint, toElement,
5638     * is not included; if you want this value included, pass its successor object in to
5639     * toElement.  For example, for Integers, you could request
5640     * <code>headSet(new Integer(limit.intValue() + 1))</code>.
5641     *
5642     * @param toElement the exclusive upper range of the subset
5643     * @return the subset.
5644     * @throws ClassCastException if toElement is not comparable to the set
5645     *         contents.
5646     * @throws IllegalArgumentException if this is a subSet, and toElement is out
5647     *         of range.
5648     * @throws NullPointerException if toElement is null but the set does not
5649     *         allow null elements.
5650     */
5651    public SortedSet<T> headSet(T toElement)
5652    {
5653      return new UnmodifiableSortedSet<T>(ss.headSet(toElement));
5654    }
5655
5656    /**
5657     * Returns the last (highest sorted) element in the underlying
5658     * set.
5659     *
5660     * @return the last element.
5661     * @throws NoSuchElementException if the set is empty.
5662     */
5663    public T last()
5664    {
5665      return ss.last();
5666    }
5667
5668    /**
5669     * Returns a unmodifiable view of the portion of the set greater than or
5670     * equal to fromElement, and strictly less than toElement. The view is backed by
5671     * the underlying set, so changes in one show up in the other. The subset
5672     * supports all optional operations of the original.
5673     * <p>
5674     *
5675     * The returned set throws an IllegalArgumentException any time an element is
5676     * used which is out of the range of fromElement and toElement. Note that the
5677     * lower endpoint is included, but the upper is not; if you want to
5678     * change the inclusion or exclusion of an endpoint, pass its successor
5679     * object in instead.  For example, for Integers, you can request
5680     * <code>subSet(new Integer(lowlimit.intValue() + 1),
5681     * new Integer(highlimit.intValue() + 1))</code> to reverse
5682     * the inclusiveness of both endpoints.
5683     *
5684     * @param fromElement the inclusive lower range of the subset.
5685     * @param toElement the exclusive upper range of the subset.
5686     * @return the subset.
5687     * @throws ClassCastException if fromElement or toElement is not comparable
5688     *         to the set contents.
5689     * @throws IllegalArgumentException if this is a subSet, and fromElement or
5690     *         toElement is out of range.
5691     * @throws NullPointerException if fromElement or toElement is null but the
5692     *         set does not allow null elements.
5693     */
5694    public SortedSet<T> subSet(T fromElement, T toElement)
5695    {
5696      return new UnmodifiableSortedSet<T>(ss.subSet(fromElement, toElement));
5697    }
5698
5699    /**
5700     * Returns a unmodifiable view of the portion of the set greater than or equal to
5701     * fromElement. The view is backed by the underlying set, so changes in one show up
5702     * in the other. The subset supports all optional operations of the original.
5703     * <p>
5704     *
5705     * The returned set throws an IllegalArgumentException any time an element is
5706     * used which is out of the range of fromElement. Note that the endpoint,
5707     * fromElement, is included; if you do not want this value to be included, pass its
5708     * successor object in to fromElement.  For example, for Integers, you could request
5709     * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
5710     *
5711     * @param fromElement the inclusive lower range of the subset
5712     * @return the subset.
5713     * @throws ClassCastException if fromElement is not comparable to the set
5714     *         contents.
5715     * @throws IllegalArgumentException if this is a subSet, and fromElement is
5716     *         out of range.
5717     * @throws NullPointerException if fromElement is null but the set does not
5718     *         allow null elements.
5719     */
5720    public SortedSet<T> tailSet(T fromElement)
5721    {
5722      return new UnmodifiableSortedSet<T>(ss.tailSet(fromElement));
5723    }
5724  } // class UnmodifiableSortedSet
5725
5726  /**
5727   * <p>
5728   * Returns a dynamically typesafe view of the given collection,
5729   * where any modification is first checked to ensure that the type
5730   * of the new data is appropriate.  Although the addition of
5731   * generics and parametrically-typed collections prevents an
5732   * incorrect type of element being added to a collection at
5733   * compile-time, via static type checking, this can be overridden by
5734   * casting.  In contrast, wrapping the collection within a
5735   * dynamically-typesafe wrapper, using this and associated methods,
5736   * <emph>guarantees</emph> that the collection will only contain
5737   * elements of an appropriate type (provided it only contains such
5738   * at the type of wrapping, and all subsequent access is via the
5739   * wrapper).  This can be useful for debugging the cause of a
5740   * <code>ClassCastException</code> caused by erroneous casting, or
5741   * for protecting collections from corruption by external libraries.
5742   * </p>
5743   * <p>
5744   * Since the collection might be a List or a Set, and those
5745   * have incompatible equals and hashCode requirements, this relies
5746   * on Object's implementation rather than passing those calls on to
5747   * the wrapped collection. The returned Collection implements
5748   * Serializable, but can only be serialized if the collection it
5749   * wraps is likewise Serializable.
5750   * </p>
5751   *
5752   * @param c the collection to wrap in a dynamically typesafe wrapper
5753   * @param type the type of elements the collection should hold.
5754   * @return a dynamically typesafe view of the collection.
5755   * @see Serializable
5756   * @since 1.5
5757   */
5758  public static <E> Collection<E> checkedCollection(Collection<E> c,
5759                                                    Class<E> type)
5760  {
5761    return new CheckedCollection<E>(c, type);
5762  }
5763
5764  /**
5765   * The implementation of {@link #checkedCollection(Collection,Class)}. This
5766   * class name is required for compatibility with Sun's JDK serializability.
5767   *
5768   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
5769   * @since 1.5
5770   */
5771  private static class CheckedCollection<E>
5772    implements Collection<E>, Serializable
5773  {
5774    /**
5775     * Compatible with JDK 1.5.
5776     */
5777    private static final long serialVersionUID = 1578914078182001775L;
5778
5779    /**
5780     * The wrapped collection. Package visible for use by subclasses.
5781     * @serial the real collection
5782     */
5783    final Collection<E> c;
5784
5785    /**
5786     * The type of the elements of this collection.
5787     * @serial the element type.
5788     */
5789    final Class<E> type;
5790
5791    /**
5792     * Wrap a given collection.
5793     * @param c the collection to wrap
5794     * @param type the type to wrap
5795     * @throws NullPointerException if c is null
5796     */
5797    CheckedCollection(Collection<E> c, Class<E> type)
5798    {
5799      this.c = c;
5800      this.type = type;
5801      if (c == null)
5802        throw new NullPointerException();
5803    }
5804
5805    /**
5806     * Adds the supplied object to the collection, on the condition that
5807     * it is of the correct type.
5808     *
5809     * @param o the object to add.
5810     * @return <code>true</code> if the collection was modified as a result
5811     *                           of this action.
5812     * @throws ClassCastException if the object is not of the correct type.
5813     */
5814    public boolean add(E o)
5815    {
5816      if (type.isInstance(o))
5817        return c.add(o);
5818      else
5819        throw new ClassCastException("The element is of the incorrect type.");
5820    }
5821
5822    /**
5823     * Adds the elements of the specified collection to the backing collection,
5824     * provided they are all of the correct type.
5825     *
5826     * @param coll the collection to add.
5827     * @return <code>true</code> if the collection was modified as a result
5828     *                           of this action.
5829     * @throws ClassCastException if <code>c</code> contained elements of an
5830     *                            incorrect type.
5831     */
5832    public boolean addAll(Collection<? extends E> coll)
5833    {
5834      Collection<E> typedColl = (Collection<E>) c;
5835      final Iterator<E> it = typedColl.iterator();
5836      while (it.hasNext())
5837        {
5838          final E element = it.next();
5839          if (!type.isInstance(element))
5840            throw new ClassCastException("A member of the collection is not of the correct type.");
5841        }
5842      return c.addAll(typedColl);
5843    }
5844
5845    /**
5846     * Removes all elements from the underlying collection.
5847     */
5848    public void clear()
5849    {
5850      c.clear();
5851    }
5852
5853    /**
5854     * Test whether the underlying collection contains a given object as one
5855     * of its elements.
5856     *
5857     * @param o the element to look for.
5858     * @return <code>true</code> if the underlying collection contains at least
5859     *         one element e such that
5860     *         <code>o == null ? e == null : o.equals(e)</code>.
5861     * @throws ClassCastException if the type of o is not a valid type for the
5862     *         underlying collection.
5863     * @throws NullPointerException if o is null and the underlying collection
5864     *         doesn't support null values.
5865     */
5866    public boolean contains(Object o)
5867    {
5868      return c.contains(o);
5869    }
5870
5871    /**
5872     * Test whether the underlying collection contains every element in a given
5873     * collection.
5874     *
5875     * @param coll the collection to test for.
5876     * @return <code>true</code> if for every element o in c, contains(o) would
5877     *         return <code>true</code>.
5878     * @throws ClassCastException if the type of any element in c is not a
5879     *                            valid type for the underlying collection.
5880     * @throws NullPointerException if some element of c is null and the
5881     *                              underlying collection does not support
5882     *                              null values.
5883     * @throws NullPointerException if c itself is null.
5884     */
5885    public boolean containsAll(Collection<?> coll)
5886    {
5887      return c.containsAll(coll);
5888    }
5889
5890    /**
5891     * Tests whether the underlying collection is empty, that is,
5892     * if size() == 0.
5893     *
5894     * @return <code>true</code> if this collection contains no elements.
5895     */
5896    public boolean isEmpty()
5897    {
5898      return c.isEmpty();
5899    }
5900
5901    /**
5902     * Obtain an Iterator over the underlying collection, which maintains
5903     * its checked nature.
5904     *
5905     * @return a Iterator over the elements of the underlying
5906     *         collection, in any order.
5907     */
5908    public Iterator<E> iterator()
5909    {
5910      return new CheckedIterator<E>(c.iterator(), type);
5911    }
5912
5913    /**
5914     * Removes the supplied object from the collection, if it exists.
5915     *
5916     * @param o The object to remove.
5917     * @return <code>true</code> if the object was removed (i.e. the underlying
5918     *         collection returned 1 or more instances of o).
5919     */
5920    public boolean remove(Object o)
5921    {
5922      return c.remove(o);
5923    }
5924
5925    /**
5926     * Removes all objects in the supplied collection from the backing
5927     * collection, if they exist within it.
5928     *
5929     * @param coll the collection of objects to remove.
5930     * @return <code>true</code> if the collection was modified.
5931     */
5932    public boolean removeAll(Collection<?> coll)
5933    {
5934      return c.removeAll(coll);
5935    }
5936
5937    /**
5938     * Retains all objects specified by the supplied collection which exist
5939     * within the backing collection, and removes all others.
5940     *
5941     * @param coll the collection of objects to retain.
5942     * @return <code>true</code> if the collection was modified.
5943     */
5944    public boolean retainAll(Collection<?> coll)
5945    {
5946      return c.retainAll(coll);
5947    }
5948
5949    /**
5950     * Retrieves the number of elements in the underlying collection.
5951     *
5952     * @return the number of elements in the collection.
5953     */
5954    public int size()
5955    {
5956      return c.size();
5957    }
5958
5959    /**
5960     * Copy the current contents of the underlying collection into an array.
5961     *
5962     * @return an array of type Object[] with a length equal to the size of the
5963     *         underlying collection and containing the elements currently in
5964     *         the underlying collection, in any order.
5965     */
5966    public Object[] toArray()
5967    {
5968      return c.toArray();
5969    }
5970
5971    /**
5972     * <p>
5973     * Copy the current contents of the underlying collection into an array. If
5974     * the array passed as an argument has length less than the size of the
5975     * underlying collection, an array of the same run-time type as a, with a
5976     * length equal to the size of the underlying collection, is allocated
5977     * using reflection.
5978     * </p>
5979     * <p>
5980     * Otherwise, a itself is used.  The elements of the underlying collection
5981     * are copied into it, and if there is space in the array, the following
5982     * element is set to null. The resultant array is returned.
5983     * </p>
5984     * <p>
5985     * <emph>Note</emph>: The fact that the following element is set to null
5986     * is only useful if it is known that this collection does not contain
5987     * any null elements.
5988     *
5989     * @param a the array to copy this collection into.
5990     * @return an array containing the elements currently in the underlying
5991     *         collection, in any order.
5992     * @throws ArrayStoreException if the type of any element of the
5993     *         collection is not a subtype of the element type of a.
5994     */
5995    public <S> S[] toArray(S[] a)
5996    {
5997      return c.toArray(a);
5998    }
5999
6000    /**
6001     * A textual representation of the unmodifiable collection.
6002     *
6003     * @return The checked collection in the form of a <code>String</code>.
6004     */
6005    public String toString()
6006    {
6007      return c.toString();
6008    }
6009  } // class CheckedCollection
6010
6011  /**
6012   * The implementation of the various iterator methods in the
6013   * checked classes.
6014   *
6015   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6016   * @since 1.5
6017   */
6018  private static class CheckedIterator<E>
6019    implements Iterator<E>
6020  {
6021    /**
6022     * The wrapped iterator.
6023     */
6024    private final Iterator<E> i;
6025
6026    /**
6027     * The type of the elements of this collection.
6028     * @serial the element type.
6029     */
6030    final Class<E> type;
6031
6032    /**
6033     * Only trusted code creates a wrapper.
6034     * @param i the wrapped iterator
6035     * @param type the type of the elements within the checked list.
6036     */
6037    CheckedIterator(Iterator<E> i, Class<E> type)
6038    {
6039      this.i = i;
6040      this.type = type;
6041    }
6042
6043    /**
6044     * Obtains the next element in the underlying collection.
6045     *
6046     * @return the next element in the collection.
6047     * @throws NoSuchElementException if there are no more elements.
6048     */
6049    public E next()
6050    {
6051      return i.next();
6052    }
6053
6054    /**
6055     * Tests whether there are still elements to be retrieved from the
6056     * underlying collection by <code>next()</code>.  When this method
6057     * returns <code>true</code>, an exception will not be thrown on calling
6058     * <code>next()</code>.
6059     *
6060     * @return <code>true</code> if there is at least one more element in the
6061     *         underlying collection.
6062     */
6063    public boolean hasNext()
6064    {
6065      return i.hasNext();
6066    }
6067
6068    /**
6069     * Removes the next element from the collection.
6070     */
6071    public void remove()
6072    {
6073      i.remove();
6074    }
6075  } // class CheckedIterator
6076
6077  /**
6078   * <p>
6079   * Returns a dynamically typesafe view of the given list,
6080   * where any modification is first checked to ensure that the type
6081   * of the new data is appropriate.  Although the addition of
6082   * generics and parametrically-typed collections prevents an
6083   * incorrect type of element being added to a collection at
6084   * compile-time, via static type checking, this can be overridden by
6085   * casting.  In contrast, wrapping the collection within a
6086   * dynamically-typesafe wrapper, using this and associated methods,
6087   * <emph>guarantees</emph> that the collection will only contain
6088   * elements of an appropriate type (provided it only contains such
6089   * at the type of wrapping, and all subsequent access is via the
6090   * wrapper).  This can be useful for debugging the cause of a
6091   * <code>ClassCastException</code> caused by erroneous casting, or
6092   * for protecting collections from corruption by external libraries.
6093   * </p>
6094   * <p>
6095   * The returned List implements Serializable, but can only be serialized if
6096   * the list it wraps is likewise Serializable. In addition, if the wrapped
6097   * list implements RandomAccess, this does too.
6098   * </p>
6099   *
6100   * @param l the list to wrap
6101   * @param type the type of the elements within the checked list.
6102   * @return a dynamically typesafe view of the list
6103   * @see Serializable
6104   * @see RandomAccess
6105   */
6106  public static <E> List<E> checkedList(List<E> l, Class<E> type)
6107  {
6108    if (l instanceof RandomAccess)
6109      return new CheckedRandomAccessList<E>(l, type);
6110    return new CheckedList<E>(l, type);
6111  }
6112
6113  /**
6114   * The implementation of {@link #checkedList(List,Class)} for sequential
6115   * lists. This class name is required for compatibility with Sun's JDK
6116   * serializability.
6117   *
6118   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6119   * @since 1.5
6120   */
6121  private static class CheckedList<E>
6122    extends CheckedCollection<E>
6123    implements List<E>
6124  {
6125    /**
6126     * Compatible with JDK 1.5.
6127     */
6128    private static final long serialVersionUID = 65247728283967356L;
6129
6130    /**
6131     * The wrapped list; stored both here and in the superclass to avoid
6132     * excessive casting. Package visible for use by subclass.
6133     * @serial the wrapped list
6134     */
6135    final List<E> list;
6136
6137    /**
6138     * Wrap a given list.
6139     * @param l the list to wrap
6140     * @param type the type of the elements within the checked list.
6141     * @throws NullPointerException if l is null
6142     */
6143    CheckedList(List<E> l, Class<E> type)
6144    {
6145      super(l, type);
6146      list = l;
6147    }
6148
6149    /**
6150     * Adds the supplied element to the underlying list at the specified
6151     * index, provided it is of the right type.
6152     *
6153     * @param index The index at which to place the new element.
6154     * @param o the object to add.
6155     * @throws ClassCastException if the type of the object is not a
6156     *                            valid type for the underlying collection.
6157     */
6158    public void add(int index, E o)
6159    {
6160      if (type.isInstance(o))
6161        list.add(index, o);
6162      else
6163        throw new ClassCastException("The object is of the wrong type.");
6164    }
6165
6166    /**
6167     * Adds the members of the supplied collection to the underlying
6168     * collection at the specified index, provided they are all of the
6169     * correct type.
6170     *
6171     * @param index the index at which to place the new element.
6172     * @param coll the collections of objects to add.
6173     * @throws ClassCastException if the type of any element in c is not a
6174     *                            valid type for the underlying collection.
6175     */
6176    public boolean addAll(int index, Collection<? extends E> coll)
6177    {
6178      Collection<E> typedColl = (Collection<E>) coll;
6179      final Iterator<E> it = typedColl.iterator();
6180      while (it.hasNext())
6181        {
6182          if (!type.isInstance(it.next()))
6183            throw new ClassCastException("A member of the collection is not of the correct type.");
6184        }
6185      return list.addAll(index, coll);
6186    }
6187
6188    /**
6189     * Returns <code>true</code> if the object, o, is an instance of
6190     * <code>List</code> with the same size and elements
6191     * as the underlying list.
6192     *
6193     * @param o The object to compare.
6194     * @return <code>true</code> if o is equivalent to the underlying list.
6195     */
6196    public boolean equals(Object o)
6197    {
6198      return list.equals(o);
6199    }
6200
6201    /**
6202     * Retrieves the element at a given index in the underlying list.
6203     *
6204     * @param index the index of the element to be returned
6205     * @return the element at the specified index in the underlying list
6206     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
6207     */
6208    public E get(int index)
6209    {
6210      return list.get(index);
6211    }
6212
6213    /**
6214     * Computes the hash code for the underlying list.
6215     * The exact computation is described in the documentation
6216     * of the <code>List</code> interface.
6217     *
6218     * @return The hash code of the underlying list.
6219     * @see List#hashCode()
6220     */
6221    public int hashCode()
6222    {
6223      return list.hashCode();
6224    }
6225
6226    /**
6227     * Obtain the first index at which a given object is to be found in the
6228     * underlying list.
6229     *
6230     * @param o the object to search for
6231     * @return the least integer n such that <code>o == null ? get(n) == null :
6232     *         o.equals(get(n))</code>, or -1 if there is no such index.
6233     * @throws ClassCastException if the type of o is not a valid
6234     *         type for the underlying list.
6235     * @throws NullPointerException if o is null and the underlying
6236     *         list does not support null values.
6237     */
6238    public int indexOf(Object o)
6239    {
6240      return list.indexOf(o);
6241    }
6242
6243    /**
6244     * Obtain the last index at which a given object is to be found in the
6245     * underlying list.
6246     *
6247     * @return the greatest integer n such that
6248     *         <code>o == null ? get(n) == null : o.equals(get(n))</code>,
6249     *         or -1 if there is no such index.
6250     * @throws ClassCastException if the type of o is not a valid
6251     *         type for the underlying list.
6252     * @throws NullPointerException if o is null and the underlying
6253     *         list does not support null values.
6254     */
6255    public int lastIndexOf(Object o)
6256    {
6257      return list.lastIndexOf(o);
6258    }
6259
6260    /**
6261     * Obtains a list iterator over the underlying list, starting at the
6262     * beginning and maintaining the checked nature of this list.
6263     *
6264     * @return a <code>CheckedListIterator</code> over the elements of the
6265     *         underlying list, in order, starting at the beginning.
6266     */
6267    public ListIterator<E> listIterator()
6268    {
6269      return new CheckedListIterator<E>(list.listIterator(), type);
6270    }
6271
6272  /**
6273   * Obtains a list iterator over the underlying list, starting at the
6274   * specified index and maintaining the checked nature of this list.  An
6275   * initial call to <code>next()</code> will retrieve the element at the
6276   * specified index, and an initial call to <code>previous()</code> will
6277   * retrieve the element at index - 1.
6278   *
6279   * @param index the position, between 0 and size() inclusive, to begin the
6280   *        iteration from.
6281   * @return a <code>CheckedListIterator</code> over the elements of the
6282   *         underlying list, in order, starting at the specified index.
6283   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
6284   */
6285    public ListIterator<E> listIterator(int index)
6286    {
6287      return new CheckedListIterator<E>(list.listIterator(index), type);
6288    }
6289
6290    /**
6291     * Removes the element at the specified index.
6292     *
6293     * @param index The index of the element to remove.
6294     * @return the removed element.
6295     */
6296    public E remove(int index)
6297    {
6298      return list.remove(index);
6299    }
6300
6301    /**
6302     * Replaces the element at the specified index in the underlying list
6303     * with that supplied.
6304     *
6305     * @param index the index of the element to replace.
6306     * @param o the new object to place at the specified index.
6307     * @return the replaced element.
6308     */
6309    public E set(int index, E o)
6310    {
6311      return list.set(index, o);
6312    }
6313
6314    /**
6315     * Obtain a List view of a subsection of the underlying list, from
6316     * fromIndex (inclusive) to toIndex (exclusive). If the two indices
6317     * are equal, the sublist is empty. The returned list will be
6318     * checked, like this list.  Changes to the elements of the
6319     * returned list will be reflected in the underlying list. The effect
6320     * of structural modifications is undefined.
6321     *
6322     * @param fromIndex the index that the returned list should start from
6323     *        (inclusive).
6324     * @param toIndex the index that the returned list should go
6325     *                to (exclusive).
6326     * @return a List backed by a subsection of the underlying list.
6327     * @throws IndexOutOfBoundsException if fromIndex &lt; 0
6328     *         || toIndex &gt; size() || fromIndex &gt; toIndex.
6329     */
6330    public List<E> subList(int fromIndex, int toIndex)
6331    {
6332      return checkedList(list.subList(fromIndex, toIndex), type);
6333    }
6334  } // class CheckedList
6335
6336  /**
6337   * The implementation of {@link #checkedList(List)} for random-access
6338   * lists. This class name is required for compatibility with Sun's JDK
6339   * serializability.
6340   *
6341   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6342   * @since 1.5
6343   */
6344  private static final class CheckedRandomAccessList<E>
6345    extends CheckedList<E>
6346    implements RandomAccess
6347  {
6348    /**
6349     * Compatible with JDK 1.5.
6350     */
6351    private static final long serialVersionUID = 1638200125423088369L;
6352
6353    /**
6354     * Wrap a given list.
6355     * @param l the list to wrap
6356     * @param type the type of the elements within the checked list.
6357     * @throws NullPointerException if l is null
6358     */
6359    CheckedRandomAccessList(List<E> l, Class<E> type)
6360    {
6361      super(l, type);
6362    }
6363  } // class CheckedRandomAccessList
6364
6365  /**
6366   * The implementation of {@link CheckedList#listIterator()}.
6367   *
6368   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6369   * @since 1.5
6370   */
6371  private static final class CheckedListIterator<E>
6372    extends CheckedIterator<E>
6373    implements ListIterator<E>
6374  {
6375    /**
6376     * The wrapped iterator, stored both here and in the superclass to
6377     * avoid excessive casting.
6378     */
6379    private final ListIterator<E> li;
6380
6381    /**
6382     * Only trusted code creates a wrapper.
6383     * @param li the wrapped iterator
6384     */
6385    CheckedListIterator(ListIterator<E> li, Class<E> type)
6386    {
6387      super(li, type);
6388      this.li = li;
6389    }
6390
6391    /**
6392     * Adds the supplied object at the current iterator position, provided
6393     * it is of the correct type.
6394     *
6395     * @param o the object to add.
6396     * @throws ClassCastException if the type of the object is not a
6397     *                            valid type for the underlying collection.
6398     */
6399    public void add(E o)
6400    {
6401      if (type.isInstance(o))
6402        li.add(o);
6403      else
6404        throw new ClassCastException("The object is of the wrong type.");
6405    }
6406
6407    /**
6408     * Tests whether there are still elements to be retrieved from the
6409     * underlying collection by <code>previous()</code>.  When this method
6410     * returns <code>true</code>, an exception will not be thrown on calling
6411     * <code>previous()</code>.
6412     *
6413     * @return <code>true</code> if there is at least one more element prior
6414     *         to the current position in the underlying list.
6415     */
6416    public boolean hasPrevious()
6417    {
6418      return li.hasPrevious();
6419    }
6420
6421    /**
6422     * Find the index of the element that would be returned by a call to next.
6423     * If <code>hasNext()</code> returns <code>false</code>, this returns the
6424     * list size.
6425     *
6426     * @return the index of the element that would be returned by
6427     *         <code>next()</code>.
6428     */
6429    public int nextIndex()
6430    {
6431      return li.nextIndex();
6432    }
6433
6434    /**
6435     * Obtains the previous element in the underlying list.
6436     *
6437     * @return the previous element in the list.
6438     * @throws NoSuchElementException if there are no more prior elements.
6439     */
6440    public E previous()
6441    {
6442      return li.previous();
6443    }
6444
6445    /**
6446     * Find the index of the element that would be returned by a call to
6447     * previous. If <code>hasPrevious()</code> returns <code>false</code>,
6448     * this returns -1.
6449     *
6450     * @return the index of the element that would be returned by
6451     *         <code>previous()</code>.
6452     */
6453    public int previousIndex()
6454    {
6455      return li.previousIndex();
6456    }
6457
6458    /**
6459     * Sets the next element to that supplied, provided that it is of the
6460     * correct type.
6461     *
6462     * @param o The new object to replace the existing one.
6463     * @throws ClassCastException if the type of the object is not a
6464     *                            valid type for the underlying collection.
6465     */
6466    public void set(E o)
6467    {
6468      if (type.isInstance(o))
6469        li.set(o);
6470      else
6471        throw new ClassCastException("The object is of the wrong type.");
6472    }
6473  } // class CheckedListIterator
6474
6475  /**
6476   * <p>
6477   * Returns a dynamically typesafe view of the given map,
6478   * where any modification is first checked to ensure that the type
6479   * of the new data is appropriate.  Although the addition of
6480   * generics and parametrically-typed collections prevents an
6481   * incorrect type of element being added to a collection at
6482   * compile-time, via static type checking, this can be overridden by
6483   * casting.  In contrast, wrapping the collection within a
6484   * dynamically-typesafe wrapper, using this and associated methods,
6485   * <emph>guarantees</emph> that the collection will only contain
6486   * elements of an appropriate type (provided it only contains such
6487   * at the type of wrapping, and all subsequent access is via the
6488   * wrapper).  This can be useful for debugging the cause of a
6489   * <code>ClassCastException</code> caused by erroneous casting, or
6490   * for protecting collections from corruption by external libraries.
6491   * </p>
6492   * <p>
6493   * The returned Map implements Serializable, but can only be serialized if
6494   * the map it wraps is likewise Serializable.
6495   * </p>
6496   *
6497   * @param m the map to wrap
6498   * @param keyType the dynamic type of the map's keys.
6499   * @param valueType the dynamic type of the map's values.
6500   * @return a dynamically typesafe view of the map
6501   * @see Serializable
6502   */
6503  public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType,
6504                                            Class<V> valueType)
6505  {
6506    return new CheckedMap<K, V>(m, keyType, valueType);
6507  }
6508
6509  /**
6510   * The implementation of {@link #checkedMap(Map)}. This
6511   * class name is required for compatibility with Sun's JDK serializability.
6512   *
6513   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6514   * @since 1.5
6515   */
6516  private static class CheckedMap<K, V>
6517    implements Map<K, V>, Serializable
6518  {
6519    /**
6520     * Compatible with JDK 1.5.
6521     */
6522    private static final long serialVersionUID = 5742860141034234728L;
6523
6524    /**
6525     * The wrapped map.
6526     * @serial the real map
6527     */
6528    private final Map<K, V> m;
6529
6530    /**
6531     * The type of the map's keys.
6532     * @serial the key type.
6533     */
6534    final Class<K> keyType;
6535
6536    /**
6537     * The type of the map's values.
6538     * @serial the value type.
6539     */
6540    final Class<V> valueType;
6541
6542    /**
6543     * Cache the entry set.
6544     */
6545    private transient Set<Map.Entry<K, V>> entries;
6546
6547    /**
6548     * Cache the key set.
6549     */
6550    private transient Set<K> keys;
6551
6552    /**
6553     * Cache the value collection.
6554     */
6555    private transient Collection<V> values;
6556
6557    /**
6558     * Wrap a given map.
6559     * @param m the map to wrap
6560     * @param keyType the dynamic type of the map's keys.
6561     * @param valueType the dynamic type of the map's values.
6562     * @throws NullPointerException if m is null
6563     */
6564    CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType)
6565    {
6566      this.m = m;
6567      this.keyType = keyType;
6568      this.valueType = valueType;
6569      if (m == null)
6570        throw new NullPointerException();
6571    }
6572
6573    /**
6574     * Clears all pairs from the map.
6575     */
6576    public void clear()
6577    {
6578      m.clear();
6579    }
6580
6581    /**
6582     * Returns <code>true</code> if the underlying map contains a mapping for
6583     * the given key.
6584     *
6585     * @param key the key to search for
6586     * @return <code>true</code> if the map contains the key
6587     * @throws ClassCastException if the key is of an inappropriate type
6588     * @throws NullPointerException if key is <code>null</code> but the map
6589     *         does not permit null keys
6590     */
6591    public boolean containsKey(Object key)
6592    {
6593      return m.containsKey(key);
6594    }
6595
6596    /**
6597     * Returns <code>true</code> if the underlying map contains at least one
6598     * mapping with the given value.  In other words, it returns
6599     * <code>true</code> if a value v exists where
6600     * <code>(value == null ? v == null : value.equals(v))</code>.
6601     * This usually requires linear time.
6602     *
6603     * @param value the value to search for
6604     * @return <code>true</code> if the map contains the value
6605     * @throws ClassCastException if the type of the value is not a valid type
6606     *         for this map.
6607     * @throws NullPointerException if the value is null and the map doesn't
6608     *         support null values.
6609     */
6610    public boolean containsValue(Object value)
6611    {
6612      return m.containsValue(value);
6613    }
6614
6615    /**
6616     * <p>
6617     * Returns a checked set view of the entries in the underlying map.
6618     * Each element in the set is a unmodifiable variant of
6619     * <code>Map.Entry</code>.
6620     * </p>
6621     * <p>
6622     * The set is backed by the map, so that changes in one show up in the
6623     * other.  Modifications made while an iterator is in progress cause
6624     * undefined behavior.
6625     * </p>
6626     *
6627     * @return the checked set view of all mapping entries.
6628     * @see Map.Entry
6629     */
6630    public Set<Map.Entry<K, V>> entrySet()
6631    {
6632      if (entries == null)
6633        {
6634          Class<Map.Entry<K,V>> klass =
6635            (Class<Map.Entry<K,V>>) (Class) Map.Entry.class;
6636          entries = new CheckedEntrySet<Map.Entry<K,V>,K,V>(m.entrySet(),
6637                                                            klass,
6638                                                            keyType,
6639                                                            valueType);
6640        }
6641      return entries;
6642    }
6643
6644    /**
6645     * The implementation of {@link CheckedMap#entrySet()}. This class
6646     * is <emph>not</emph> serializable.
6647     *
6648     * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6649     * @since 1.5
6650     */
6651    private static final class CheckedEntrySet<E,SK,SV>
6652      extends CheckedSet<E>
6653    {
6654      /**
6655       * The type of the map's keys.
6656       * @serial the key type.
6657       */
6658      private final Class<SK> keyType;
6659
6660      /**
6661       * The type of the map's values.
6662       * @serial the value type.
6663       */
6664      private final Class<SV> valueType;
6665
6666      /**
6667       * Wrap a given set of map entries.
6668       *
6669       * @param s the set to wrap.
6670       * @param type the type of the set's entries.
6671       * @param keyType the type of the map's keys.
6672       * @param valueType the type of the map's values.
6673       */
6674      CheckedEntrySet(Set<E> s, Class<E> type, Class<SK> keyType,
6675                      Class<SV> valueType)
6676      {
6677        super(s, type);
6678        this.keyType = keyType;
6679        this.valueType = valueType;
6680      }
6681
6682      // The iterator must return checked map entries.
6683      public Iterator<E> iterator()
6684      {
6685        return new CheckedIterator<E>(c.iterator(), type)
6686        {
6687          /**
6688           * Obtains the next element from the underlying set of
6689           * map entries.
6690           *
6691           * @return the next element in the collection.
6692           * @throws NoSuchElementException if there are no more elements.
6693           */
6694          public E next()
6695          {
6696            final Map.Entry e = (Map.Entry) super.next();
6697            return (E) new Map.Entry()
6698            {
6699              /**
6700               * Returns <code>true</code> if the object, o, is also a map
6701               * entry with an identical key and value.
6702               *
6703               * @param o the object to compare.
6704               * @return <code>true</code> if o is an equivalent map entry.
6705               */
6706              public boolean equals(Object o)
6707              {
6708                return e.equals(o);
6709              }
6710
6711              /**
6712               * Returns the key of this map entry.
6713               *
6714               * @return the key.
6715               */
6716              public Object getKey()
6717              {
6718                return e.getKey();
6719              }
6720
6721              /**
6722               * Returns the value of this map entry.
6723               *
6724               * @return the value.
6725               */
6726              public Object getValue()
6727              {
6728                return e.getValue();
6729              }
6730
6731              /**
6732               * Computes the hash code of this map entry.
6733               * The computation is described in the <code>Map</code>
6734               * interface documentation.
6735               *
6736               * @return the hash code of this entry.
6737               * @see Map#hashCode()
6738               */
6739              public int hashCode()
6740              {
6741                return e.hashCode();
6742              }
6743
6744              /**
6745               * Sets the value of this map entry, provided it is of the
6746               * right type.
6747               *
6748               * @param value The new value.
6749               * @throws ClassCastException if the type of the value is not
6750               *                            a valid type for the underlying
6751               *                             map.
6752               */
6753              public Object setValue(Object value)
6754              {
6755                if (valueType.isInstance(value))
6756                  return e.setValue(value);
6757                else
6758                  throw new ClassCastException("The value is of the wrong type.");
6759              }
6760
6761              /**
6762               * Returns a textual representation of the map entry.
6763               *
6764               * @return The map entry as a <code>String</code>.
6765               */
6766              public String toString()
6767              {
6768                return e.toString();
6769              }
6770            };
6771          }
6772        };
6773      }
6774    } // class CheckedEntrySet
6775
6776    /**
6777     * Returns <code>true</code> if the object, o, is also an instance
6778     * of <code>Map</code> with an equal set of map entries.
6779     *
6780     * @param o The object to compare.
6781     * @return <code>true</code> if o is an equivalent map.
6782     */
6783    public boolean equals(Object o)
6784    {
6785      return m.equals(o);
6786    }
6787
6788    /**
6789     * Returns the value associated with the supplied key or
6790     * null if no such mapping exists.  An ambiguity can occur
6791     * if null values are accepted by the underlying map.
6792     * In this case, <code>containsKey()</code> can be used
6793     * to separate the two possible cases of a null result.
6794     *
6795     * @param key The key to look up.
6796     * @return the value associated with the key, or null if key not in map.
6797     * @throws ClassCastException if the key is an inappropriate type.
6798     * @throws NullPointerException if this map does not accept null keys.
6799     * @see #containsKey(Object)
6800     */
6801    public V get(Object key)
6802    {
6803      return m.get(key);
6804    }
6805
6806    /**
6807     * Adds a new pair to the map, provided both the key and the value are
6808     * of the correct types.
6809     *
6810     * @param key The new key.
6811     * @param value The new value.
6812     * @return the previous value of the key, or null if there was no mapping.
6813     * @throws ClassCastException if the type of the key or the value is
6814     *                            not a valid type for the underlying map.
6815     */
6816    public V put(K key, V value)
6817    {
6818      if (keyType.isInstance(key))
6819        {
6820          if (valueType.isInstance(value))
6821            return m.put(key,value);
6822          else
6823            throw new ClassCastException("The value is of the wrong type.");
6824        }
6825      throw new ClassCastException("The key is of the wrong type.");
6826    }
6827
6828    /**
6829     * Computes the hash code for the underlying map, as the sum
6830     * of the hash codes of all entries.
6831     *
6832     * @return The hash code of the underlying map.
6833     * @see Map.Entry#hashCode()
6834     */
6835    public int hashCode()
6836    {
6837      return m.hashCode();
6838    }
6839
6840    /**
6841     * Returns <code>true</code> if the underlying map contains no entries.
6842     *
6843     * @return <code>true</code> if the map is empty.
6844     */
6845    public boolean isEmpty()
6846    {
6847      return m.isEmpty();
6848    }
6849
6850    /**
6851     * <p>
6852     * Returns a checked set view of the keys in the underlying map.
6853     * The set is backed by the map, so that changes in one show up in the
6854     * other.
6855     * </p>
6856     * <p>
6857     * Modifications made while an iterator is in progress cause undefined
6858     * behavior.  These modifications are again limited to the values of
6859     * the keys.
6860     * </p>
6861     *
6862     * @return the set view of all keys.
6863     */
6864    public Set<K> keySet()
6865    {
6866      if (keys == null)
6867        keys = new CheckedSet<K>(m.keySet(), keyType);
6868      return keys;
6869    }
6870
6871    /**
6872     * Adds all pairs within the supplied map to the underlying map,
6873     * provided they are all have the correct key and value types.
6874     *
6875     * @param map the map, the entries of which should be added
6876     *          to the underlying map.
6877     * @throws ClassCastException if the type of a key or value is
6878     *                            not a valid type for the underlying map.
6879     */
6880    public void putAll(Map<? extends K, ? extends V> map)
6881    {
6882      Map<K,V> typedMap = (Map<K,V>) map;
6883      final Iterator<Map.Entry<K,V>> it = typedMap.entrySet().iterator();
6884      while (it.hasNext())
6885        {
6886          final Map.Entry<K,V> entry = it.next();
6887          if (!keyType.isInstance(entry.getKey()))
6888            throw new ClassCastException("A key is of the wrong type.");
6889          if (!valueType.isInstance(entry.getValue()))
6890            throw new ClassCastException("A value is of the wrong type.");
6891        }
6892      m.putAll(typedMap);
6893    }
6894
6895    /**
6896     * Removes a pair from the map.
6897     *
6898     * @param o The key of the entry to remove.
6899     * @return The value the key was associated with, or null
6900     *         if no such mapping existed.  Null is also returned
6901     *         if the removed entry had a null key.
6902     * @throws UnsupportedOperationException as an unmodifiable
6903     *         map does not support the <code>remove</code> operation.
6904     */
6905    public V remove(Object o)
6906    {
6907      return m.remove(o);
6908    }
6909
6910
6911    /**
6912     * Returns the number of key-value mappings in the underlying map.
6913     * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
6914     * is returned.
6915     *
6916     * @return the number of mappings.
6917     */
6918    public int size()
6919    {
6920      return m.size();
6921    }
6922
6923    /**
6924     * Returns a textual representation of the map.
6925     *
6926     * @return The map in the form of a <code>String</code>.
6927     */
6928    public String toString()
6929    {
6930      return m.toString();
6931    }
6932
6933    /**
6934     * <p>
6935     * Returns a unmodifiable collection view of the values in the underlying
6936     * map.  The collection is backed by the map, so that changes in one show
6937     * up in the other.
6938     * </p>
6939     * <p>
6940     * Modifications made while an iterator is in progress cause undefined
6941     * behavior.  These modifications are again limited to the values of
6942     * the keys.
6943     * </p>
6944     *
6945     * @return the collection view of all values.
6946     */
6947    public Collection<V> values()
6948    {
6949      if (values == null)
6950        values = new CheckedCollection<V>(m.values(), valueType);
6951      return values;
6952    }
6953  } // class CheckedMap
6954
6955  /**
6956   * <p>
6957   * Returns a dynamically typesafe view of the given set,
6958   * where any modification is first checked to ensure that the type
6959   * of the new data is appropriate.  Although the addition of
6960   * generics and parametrically-typed collections prevents an
6961   * incorrect type of element being added to a collection at
6962   * compile-time, via static type checking, this can be overridden by
6963   * casting.  In contrast, wrapping the collection within a
6964   * dynamically-typesafe wrapper, using this and associated methods,
6965   * <emph>guarantees</emph> that the collection will only contain
6966   * elements of an appropriate type (provided it only contains such
6967   * at the type of wrapping, and all subsequent access is via the
6968   * wrapper).  This can be useful for debugging the cause of a
6969   * <code>ClassCastException</code> caused by erroneous casting, or
6970   * for protecting collections from corruption by external libraries.
6971   * </p>
6972   * <p>
6973   * The returned Set implements Serializable, but can only be serialized if
6974   * the set it wraps is likewise Serializable.
6975   * </p>
6976   *
6977   * @param s the set to wrap.
6978   * @param type the type of the elements within the checked list.
6979   * @return a dynamically typesafe view of the set
6980   * @see Serializable
6981   */
6982  public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)
6983  {
6984    return new CheckedSet<E>(s, type);
6985  }
6986
6987  /**
6988   * The implementation of {@link #checkedSet(Set)}. This class
6989   * name is required for compatibility with Sun's JDK serializability.
6990   *
6991   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6992   * @since 1.5
6993   */
6994  private static class CheckedSet<E>
6995    extends CheckedCollection<E>
6996    implements Set<E>
6997  {
6998    /**
6999     * Compatible with JDK 1.5.
7000     */
7001    private static final long serialVersionUID = 4694047833775013803L;
7002
7003    /**
7004     * Wrap a given set.
7005     *
7006     * @param s the set to wrap
7007     * @throws NullPointerException if s is null
7008     */
7009    CheckedSet(Set<E> s, Class<E> type)
7010    {
7011      super(s, type);
7012    }
7013
7014    /**
7015     * Returns <code>true</code> if the object, o, is also an instance of
7016     * <code>Set</code> of the same size and with the same entries.
7017     *
7018     * @return <code>true</code> if o is an equivalent set.
7019     */
7020    public boolean equals(Object o)
7021    {
7022      return c.equals(o);
7023    }
7024
7025    /**
7026     * Computes the hash code of this set, as the sum of the
7027     * hash codes of all elements within the set.
7028     *
7029     * @return the hash code of the set.
7030     */
7031    public int hashCode()
7032    {
7033      return c.hashCode();
7034    }
7035  } // class CheckedSet
7036
7037  /**
7038   * <p>
7039   * Returns a dynamically typesafe view of the given sorted map,
7040   * where any modification is first checked to ensure that the type
7041   * of the new data is appropriate.  Although the addition of
7042   * generics and parametrically-typed collections prevents an
7043   * incorrect type of element being added to a collection at
7044   * compile-time, via static type checking, this can be overridden by
7045   * casting.  In contrast, wrapping the collection within a
7046   * dynamically-typesafe wrapper, using this and associated methods,
7047   * <emph>guarantees</emph> that the collection will only contain
7048   * elements of an appropriate type (provided it only contains such
7049   * at the type of wrapping, and all subsequent access is via the
7050   * wrapper).  This can be useful for debugging the cause of a
7051   * <code>ClassCastException</code> caused by erroneous casting, or
7052   * for protecting collections from corruption by external libraries.
7053   * </p>
7054   * <p>
7055   * The returned SortedMap implements Serializable, but can only be
7056   * serialized if the map it wraps is likewise Serializable.
7057   * </p>
7058   *
7059   * @param m the map to wrap.
7060   * @param keyType the dynamic type of the map's keys.
7061   * @param valueType the dynamic type of the map's values.
7062   * @return a dynamically typesafe view of the map
7063   * @see Serializable
7064   */
7065  public static <K, V> SortedMap<K, V> checkedSortedMap(SortedMap<K, V> m,
7066                                                        Class<K> keyType,
7067                                                        Class<V> valueType)
7068  {
7069    return new CheckedSortedMap<K, V>(m, keyType, valueType);
7070  }
7071
7072  /**
7073   * The implementation of {@link #checkedSortedMap(SortedMap,Class,Class)}.
7074   * This class name is required for compatibility with Sun's JDK
7075   * serializability.
7076   *
7077   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7078   */
7079  private static class CheckedSortedMap<K, V>
7080    extends CheckedMap<K, V>
7081    implements SortedMap<K, V>
7082  {
7083    /**
7084     * Compatible with JDK 1.5.
7085     */
7086    private static final long serialVersionUID = 1599671320688067438L;
7087
7088    /**
7089     * The wrapped map; stored both here and in the superclass to avoid
7090     * excessive casting.
7091     * @serial the wrapped map
7092     */
7093    private final SortedMap<K, V> sm;
7094
7095    /**
7096     * Wrap a given map.
7097     *
7098     * @param sm the map to wrap
7099     * @param keyType the dynamic type of the map's keys.
7100     * @param valueType the dynamic type of the map's values.
7101     * @throws NullPointerException if sm is null
7102     */
7103    CheckedSortedMap(SortedMap<K, V> sm, Class<K> keyType, Class<V> valueType)
7104    {
7105      super(sm, keyType, valueType);
7106      this.sm = sm;
7107    }
7108
7109    /**
7110     * Returns the comparator used in sorting the underlying map,
7111     * or null if it is the keys' natural ordering.
7112     *
7113     * @return the sorting comparator.
7114     */
7115    public Comparator<? super K> comparator()
7116    {
7117      return sm.comparator();
7118    }
7119
7120    /**
7121     * Returns the first (lowest sorted) key in the map.
7122     *
7123     * @return the first key.
7124     * @throws NoSuchElementException if this map is empty.
7125     */
7126    public K firstKey()
7127    {
7128      return sm.firstKey();
7129    }
7130
7131    /**
7132     * <p>
7133     * Returns a checked view of the portion of the map strictly less
7134     * than toKey. The view is backed by the underlying map, so changes in
7135     * one show up in the other.  The submap supports all optional operations
7136     * of the original.  This operation is equivalent to
7137     * <code>subMap(firstKey(), toKey)</code>.
7138     * </p>
7139     * <p>
7140     * The returned map throws an IllegalArgumentException any time a key is
7141     * used which is out of the range of toKey. Note that the endpoint, toKey,
7142     * is not included; if you want this value to be included, pass its
7143     * successor object in to toKey.  For example, for Integers, you could
7144     * request <code>headMap(new Integer(limit.intValue() + 1))</code>.
7145     * </p>
7146     *
7147     * @param toKey the exclusive upper range of the submap.
7148     * @return the submap.
7149     * @throws ClassCastException if toKey is not comparable to the map
7150     *                            contents.
7151     * @throws IllegalArgumentException if this is a subMap, and toKey is out
7152     *         of range.
7153     * @throws NullPointerException if toKey is null but the map does not allow
7154     *         null keys.
7155     */
7156    public SortedMap<K, V> headMap(K toKey)
7157    {
7158      return new CheckedSortedMap<K, V>(sm.headMap(toKey), keyType, valueType);
7159    }
7160
7161    /**
7162     * Returns the last (highest sorted) key in the map.
7163     *
7164     * @return the last key.
7165     * @throws NoSuchElementException if this map is empty.
7166     */
7167    public K lastKey()
7168    {
7169      return sm.lastKey();
7170    }
7171
7172    /**
7173     * <p>
7174     * Returns a checked view of the portion of the map greater than or
7175     * equal to fromKey, and strictly less than toKey. The view is backed by
7176     * the underlying map, so changes in one show up in the other. The submap
7177     * supports all optional operations of the original.
7178     * </p>
7179     * <p>
7180     * The returned map throws an IllegalArgumentException any time a key is
7181     * used which is out of the range of fromKey and toKey. Note that the
7182     * lower endpoint is included, but the upper is not; if you want to
7183     * change the inclusion or exclusion of an endpoint, pass its successor
7184     * object in instead.  For example, for Integers, you could request
7185     * <code>subMap(new Integer(lowlimit.intValue() + 1),
7186     * new Integer(highlimit.intValue() + 1))</code> to reverse
7187     * the inclusiveness of both endpoints.
7188     * </p>
7189     *
7190     * @param fromKey the inclusive lower range of the submap.
7191     * @param toKey the exclusive upper range of the submap.
7192     * @return the submap.
7193     * @throws ClassCastException if fromKey or toKey is not comparable to
7194     *         the map contents.
7195     * @throws IllegalArgumentException if this is a subMap, and fromKey or
7196     *         toKey is out of range.
7197     * @throws NullPointerException if fromKey or toKey is null but the map
7198     *         does not allow null keys.
7199     */
7200    public SortedMap<K, V> subMap(K fromKey, K toKey)
7201    {
7202      return new CheckedSortedMap<K, V>(sm.subMap(fromKey, toKey), keyType,
7203                                        valueType);
7204    }
7205
7206    /**
7207     * <p>
7208     * Returns a checked view of the portion of the map greater than or
7209     * equal to fromKey. The view is backed by the underlying map, so changes
7210     * in one show up in the other. The submap supports all optional operations
7211     * of the original.
7212     * </p>
7213     * <p>
7214     * The returned map throws an IllegalArgumentException any time a key is
7215     * used which is out of the range of fromKey. Note that the endpoint,
7216     * fromKey, is included; if you do not want this value to be included,
7217     * pass its successor object in to fromKey.  For example, for Integers,
7218     * you could request
7219     * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
7220     * </p>
7221     *
7222     * @param fromKey the inclusive lower range of the submap
7223     * @return the submap
7224     * @throws ClassCastException if fromKey is not comparable to the map
7225     *         contents
7226     * @throws IllegalArgumentException if this is a subMap, and fromKey is out
7227     *         of range
7228     * @throws NullPointerException if fromKey is null but the map does not
7229     *                              allow null keys
7230     */
7231    public SortedMap<K, V> tailMap(K fromKey)
7232    {
7233      return new CheckedSortedMap<K, V>(sm.tailMap(fromKey), keyType,
7234                                        valueType);
7235    }
7236  } // class CheckedSortedMap
7237
7238  /**
7239   * <p>
7240   * Returns a dynamically typesafe view of the given sorted set,
7241   * where any modification is first checked to ensure that the type
7242   * of the new data is appropriate.  Although the addition of
7243   * generics and parametrically-typed collections prevents an
7244   * incorrect type of element being added to a collection at
7245   * compile-time, via static type checking, this can be overridden by
7246   * casting.  In contrast, wrapping the collection within a
7247   * dynamically-typesafe wrapper, using this and associated methods,
7248   * <emph>guarantees</emph> that the collection will only contain
7249   * elements of an appropriate type (provided it only contains such
7250   * at the type of wrapping, and all subsequent access is via the
7251   * wrapper).  This can be useful for debugging the cause of a
7252   * <code>ClassCastException</code> caused by erroneous casting, or
7253   * for protecting collections from corruption by external libraries.
7254   * </p>
7255   * <p>
7256   * The returned SortedSet implements Serializable, but can only be
7257   * serialized if the set it wraps is likewise Serializable.
7258   * </p>
7259   *
7260   * @param s the set to wrap.
7261   * @param type the type of the set's elements.
7262   * @return a dynamically typesafe view of the set
7263   * @see Serializable
7264   */
7265  public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
7266                                                  Class<E> type)
7267  {
7268    return new CheckedSortedSet<E>(s, type);
7269  }
7270
7271  /**
7272   * The implementation of {@link #checkedSortedSet(SortedSet,Class)}. This
7273   * class name is required for compatibility with Sun's JDK serializability.
7274   *
7275   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7276   * @since 1.5
7277   */
7278  private static class CheckedSortedSet<E>
7279    extends CheckedSet<E>
7280    implements SortedSet<E>
7281  {
7282    /**
7283     * Compatible with JDK 1.4.
7284     */
7285    private static final long serialVersionUID = 1599911165492914959L;
7286
7287    /**
7288     * The wrapped set; stored both here and in the superclass to avoid
7289     * excessive casting.
7290     *
7291     * @serial the wrapped set
7292     */
7293    private SortedSet<E> ss;
7294
7295    /**
7296     * Wrap a given set.
7297     *
7298     * @param ss the set to wrap.
7299     * @param type the type of the set's elements.
7300     * @throws NullPointerException if ss is null
7301     */
7302    CheckedSortedSet(SortedSet<E> ss, Class<E> type)
7303    {
7304      super(ss, type);
7305      this.ss = ss;
7306    }
7307
7308    /**
7309     * Returns the comparator used in sorting the underlying set,
7310     * or null if it is the elements' natural ordering.
7311     *
7312     * @return the sorting comparator
7313     */
7314    public Comparator<? super E> comparator()
7315    {
7316      return ss.comparator();
7317    }
7318
7319    /**
7320     * Returns the first (lowest sorted) element in the underlying
7321     * set.
7322     *
7323     * @return the first element.
7324     * @throws NoSuchElementException if the set is empty.
7325     */
7326    public E first()
7327    {
7328      return ss.first();
7329    }
7330
7331    /**
7332     * <p>
7333     * Returns a checked view of the portion of the set strictly
7334     * less than toElement. The view is backed by the underlying set,
7335     * so changes in one show up in the other.  The subset supports
7336     * all optional operations of the original.  This operation
7337     * is equivalent to <code>subSet(first(), toElement)</code>.
7338     * </p>
7339     * <p>
7340     * The returned set throws an IllegalArgumentException any time an
7341     * element is used which is out of the range of toElement. Note that
7342     * the endpoint, toElement, is not included; if you want this value
7343     * included, pass its successor object in to toElement.  For example,
7344     * for Integers, you could request
7345     * <code>headSet(new Integer(limit.intValue() + 1))</code>.
7346     * </p>
7347     *
7348     * @param toElement the exclusive upper range of the subset
7349     * @return the subset.
7350     * @throws ClassCastException if toElement is not comparable to the set
7351     *         contents.
7352     * @throws IllegalArgumentException if this is a subSet, and toElement is
7353     *                                  out of range.
7354     * @throws NullPointerException if toElement is null but the set does not
7355     *         allow null elements.
7356     */
7357    public SortedSet<E> headSet(E toElement)
7358    {
7359      return new CheckedSortedSet<E>(ss.headSet(toElement), type);
7360    }
7361
7362    /**
7363     * Returns the last (highest sorted) element in the underlying
7364     * set.
7365     *
7366     * @return the last element.
7367     * @throws NoSuchElementException if the set is empty.
7368     */
7369    public E last()
7370    {
7371      return ss.last();
7372    }
7373
7374    /**
7375     * <p>
7376     * Returns a checked view of the portion of the set greater than or
7377     * equal to fromElement, and strictly less than toElement. The view is
7378     * backed by the underlying set, so changes in one show up in the other.
7379     * The subset supports all optional operations of the original.
7380     * </p>
7381     * <p>
7382     * The returned set throws an IllegalArgumentException any time an
7383     * element is used which is out of the range of fromElement and toElement.
7384     * Note that the lower endpoint is included, but the upper is not; if you
7385     * want to change the inclusion or exclusion of an endpoint, pass its
7386     * successor object in instead.  For example, for Integers, you can request
7387     * <code>subSet(new Integer(lowlimit.intValue() + 1),
7388     * new Integer(highlimit.intValue() + 1))</code> to reverse
7389     * the inclusiveness of both endpoints.
7390     * </p>
7391     *
7392     * @param fromElement the inclusive lower range of the subset.
7393     * @param toElement the exclusive upper range of the subset.
7394     * @return the subset.
7395     * @throws ClassCastException if fromElement or toElement is not comparable
7396     *         to the set contents.
7397     * @throws IllegalArgumentException if this is a subSet, and fromElement or
7398     *         toElement is out of range.
7399     * @throws NullPointerException if fromElement or toElement is null but the
7400     *         set does not allow null elements.
7401     */
7402    public SortedSet<E> subSet(E fromElement, E toElement)
7403    {
7404      return new CheckedSortedSet<E>(ss.subSet(fromElement, toElement), type);
7405    }
7406
7407    /**
7408     * <p>
7409     * Returns a checked view of the portion of the set greater than or equal
7410     * to fromElement. The view is backed by the underlying set, so changes in
7411     * one show up in the other. The subset supports all optional operations
7412     * of the original.
7413     * </p>
7414     * <p>
7415     * The returned set throws an IllegalArgumentException any time an
7416     * element is used which is out of the range of fromElement. Note that
7417     * the endpoint, fromElement, is included; if you do not want this value
7418     * to be included, pass its successor object in to fromElement.  For
7419     * example, for Integers, you could request
7420     * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
7421     * </p>
7422     *
7423     * @param fromElement the inclusive lower range of the subset
7424     * @return the subset.
7425     * @throws ClassCastException if fromElement is not comparable to the set
7426     *         contents.
7427     * @throws IllegalArgumentException if this is a subSet, and fromElement is
7428     *         out of range.
7429     * @throws NullPointerException if fromElement is null but the set does not
7430     *         allow null elements.
7431     */
7432    public SortedSet<E> tailSet(E fromElement)
7433    {
7434      return new CheckedSortedSet<E>(ss.tailSet(fromElement), type);
7435    }
7436  } // class CheckedSortedSet
7437
7438  /**
7439   * Returns a view of a {@link Deque} as a stack or LIFO (Last-In-First-Out)
7440   * {@link Queue}.  Each call to the LIFO queue corresponds to one
7441   * equivalent method call to the underlying deque, with the exception
7442   * of {@link Collection#addAll(Collection)}, which is emulated by a series
7443   * of {@link Deque#push(E)} calls.
7444   *
7445   * @param deque the deque to convert to a LIFO queue.
7446   * @return a LIFO queue.
7447   * @since 1.6
7448   */
7449  public static <T> Queue<T> asLifoQueue(Deque<T> deque)
7450  {
7451    return new LIFOQueue<T>(deque);
7452  }
7453
7454  /**
7455   * Returns a set backed by the supplied map.  The resulting set
7456   * has the same performance, concurrency and ordering characteristics
7457   * as the original map.  The supplied map must be empty and should not
7458   * be used after the set is created.  Each call to the set corresponds
7459   * to one equivalent method call to the underlying map, with the exception
7460   * of {@link Set#addAll(Collection)} which is emulated by a series of
7461   * calls to <code>put</code>.
7462   *
7463   * @param map the map to convert to a set.
7464   * @return a set backed by the supplied map.
7465   * @throws IllegalArgumentException if the map is not empty.
7466   * @since 1.6
7467   */
7468  public static <E> Set<E> newSetFromMap(Map<E,Boolean> map)
7469  {
7470    return new MapSet<E>(map);
7471  }
7472
7473  /**
7474   * The implementation of {@link #asLIFOQueue(Deque)}.
7475   *
7476   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7477   * @since 1.6
7478   */
7479  private static class LIFOQueue<T>
7480    extends AbstractQueue<T>
7481  {
7482
7483    /**
7484     * The backing deque.
7485     */
7486    private Deque<T> deque;
7487
7488    /**
7489     * Constructs a new {@link LIFOQueue} with the specified
7490     * backing {@link Deque}.
7491     *
7492     * @param deque the backing deque.
7493     */
7494    public LIFOQueue(Deque<T> deque)
7495    {
7496      this.deque = deque;
7497    }
7498
7499    public boolean add(T e)
7500    {
7501      return deque.offerFirst(e);
7502    }
7503
7504    public boolean addAll(Collection<? extends T> c)
7505    {
7506      boolean result = false;
7507      final Iterator<? extends T> it = c.iterator();
7508      while (it.hasNext())
7509        result |= deque.offerFirst(it.next());
7510      return result;
7511    }
7512
7513    public void clear()
7514    {
7515      deque.clear();
7516    }
7517
7518    public boolean isEmpty()
7519    {
7520      return deque.isEmpty();
7521    }
7522
7523    public Iterator<T> iterator()
7524    {
7525      return deque.iterator();
7526    }
7527
7528    public boolean offer(T e)
7529    {
7530      return deque.offerFirst(e);
7531    }
7532
7533    public T peek()
7534    {
7535      return deque.peek();
7536    }
7537
7538    public T poll()
7539    {
7540      return deque.poll();
7541    }
7542
7543    public int size()
7544    {
7545      return deque.size();
7546    }
7547  } // class LIFOQueue
7548
7549  /**
7550   * The implementation of {@link #newSetFromMap(Map)}.
7551   *
7552   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7553   * @since 1.6
7554   */
7555  private static class MapSet<E>
7556    extends AbstractSet<E>
7557  {
7558
7559    /**
7560     * The backing map.
7561     */
7562    private Map<E,Boolean> map;
7563
7564    /**
7565     * Constructs a new {@link MapSet} using the specified
7566     * backing {@link Map}.
7567     *
7568     * @param map the backing map.
7569     * @throws IllegalArgumentException if the map is not empty.
7570     */
7571    public MapSet(Map<E,Boolean> map)
7572    {
7573      if (!map.isEmpty())
7574        throw new IllegalArgumentException("The map must be empty.");
7575      this.map = map;
7576    }
7577
7578    public boolean add(E e)
7579    {
7580      return map.put(e, true) == null;
7581    }
7582
7583    public boolean addAll(Collection<? extends E> c)
7584    {
7585      boolean result = false;
7586      final Iterator<? extends E> it = c.iterator();
7587      while (it.hasNext())
7588        result |= (map.put(it.next(), true) == null);
7589      return result;
7590    }
7591
7592    public void clear()
7593    {
7594      map.clear();
7595    }
7596
7597    public boolean contains(Object o)
7598    {
7599      return map.containsKey(o);
7600    }
7601
7602    public boolean isEmpty()
7603    {
7604      return map.isEmpty();
7605    }
7606
7607    public Iterator<E> iterator()
7608    {
7609      return map.keySet().iterator();
7610    }
7611
7612    public boolean remove(Object o)
7613    {
7614      return map.remove(o) != null;
7615    }
7616
7617    public int size()
7618    {
7619      return map.size();
7620    }
7621  } // class MapSet
7622
7623} // class Collections