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