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