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