Source for java.util.Collections

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