Source for java.util.Collections

   1: /* Collections.java -- Utility class with methods to operate on collections
   2:    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
   3:    Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: 
  40: package java.util;
  41: 
  42: import gnu.java.lang.CPStringBuilder;
  43: 
  44: import java.io.Serializable;
  45: 
  46: /**
  47:  * Utility class consisting of static methods that operate on, or return
  48:  * Collections. Contains methods to sort, search, reverse, fill and shuffle
  49:  * Collections, methods to facilitate interoperability with legacy APIs that
  50:  * are unaware of collections, a method to return a list which consists of
  51:  * multiple copies of one element, and methods which "wrap" collections to give
  52:  * them extra properties, such as thread-safety and unmodifiability.
  53:  * <p>
  54:  *
  55:  * All methods which take a collection throw a {@link NullPointerException} if
  56:  * that collection is null. Algorithms which can change a collection may, but
  57:  * are not required, to throw the {@link UnsupportedOperationException} that
  58:  * the underlying collection would throw during an attempt at modification.
  59:  * For example,
  60:  * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code>
  61:  * does not throw a exception, even though addAll is an unsupported operation
  62:  * on a singleton; the reason for this is that addAll did not attempt to
  63:  * modify the set.
  64:  *
  65:  * @author Original author unknown
  66:  * @author Eric Blake (ebb9@email.byu.edu)
  67:  * @author Tom Tromey (tromey@redhat.com)
  68:  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  69:  * @see Collection
  70:  * @see Set
  71:  * @see List
  72:  * @see Map
  73:  * @see Arrays
  74:  * @since 1.2
  75:  * @status updated to 1.5
  76:  */
  77: public class Collections
  78: {
  79:   /**
  80:    * Constant used to decide cutoff for when a non-RandomAccess list should
  81:    * be treated as sequential-access. Basically, quadratic behavior is
  82:    * acceptable for small lists when the overhead is so small in the first
  83:    * place. I arbitrarily set it to 16, so it may need some tuning.
  84:    */
  85:   private static final int LARGE_LIST_SIZE = 16;
  86: 
  87:   /**
  88:    * Determines if a list should be treated as a sequential-access one.
  89:    * Rather than the old method of JDK 1.3 of assuming only instanceof
  90:    * AbstractSequentialList should be sequential, this uses the new method
  91:    * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
  92:    * and exceeds a large (unspecified) size should be sequential.
  93:    *
  94:    * @param l the list to check
  95:    * @return <code>true</code> if it should be treated as sequential-access
  96:    */
  97:   private static boolean isSequential(List<?> l)
  98:   {
  99:     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