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