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
   3:    Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: 
  40: package java.util;
  41: 
  42: import java.io.Serializable;
  43: 
  44: /**
  45:  * Utility class consisting of static methods that operate on, or return
  46:  * Collections. Contains methods to sort, search, reverse, fill and shuffle
  47:  * Collections, methods to facilitate interoperability with legacy APIs that
  48:  * are unaware of collections, a method to return a list which consists of
  49:  * multiple copies of one element, and methods which "wrap" collections to give
  50:  * them extra properties, such as thread-safety and unmodifiability.
  51:  * <p>
  52:  *
  53:  * All methods which take a collection throw a {@link NullPointerException} if
  54:  * that collection is null. Algorithms which can change a collection may, but
  55:  * are not required, to throw the {@link UnsupportedOperationException} that
  56:  * the underlying collection would throw during an attempt at modification.
  57:  * For example,
  58:  * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code>
  59:  * does not throw a exception, even though addAll is an unsupported operation
  60:  * on a singleton; the reason for this is that addAll did not attempt to
  61:  * modify the set.
  62:  *
  63:  * @author Original author unknown
  64:  * @author Eric Blake (ebb9@email.byu.edu)
  65:  * @see Collection
  66:  * @see Set
  67:  * @see List
  68:  * @see Map
  69:  * @see Arrays
  70:  * @since 1.2
  71:  * @status updated to 1.4
  72:  */
  73: public class Collections
  74: {
  75:   /**
  76:    * Constant used to decide cutoff for when a non-RandomAccess list should
  77:    * be treated as sequential-access. Basically, quadratic behavior is
  78:    * acceptable for small lists when the overhead is so small in the first
  79:    * place. I arbitrarily set it to 16, so it may need some tuning.
  80:    */
  81:   private static final int LARGE_LIST_SIZE = 16;
  82: 
  83:   /**
  84:    * Determines if a list should be treated as a sequential-access one.
  85:    * Rather than the old method of JDK 1.3 of assuming only instanceof
  86:    * AbstractSequentialList should be sequential, this uses the new method
  87:    * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
  88:    * and exceeds a large (unspecified) size should be sequential.
  89:    *
  90:    * @param l the list to check
  91:    * @return <code>true</code> if it should be treated as sequential-access
  92:    */
  93:   private static boolean isSequential(List l)
  94:   {
  95:     return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
  96:   }
  97: 
  98:   /**
  99:    * This class is non-instantiable.
 100:    */
 101:   private Collections()
 102:   {
 103:   }
 104: 
 105:   /**
 106:    * An immutable, serializable, empty Set.
 107:    * @see Serializable
 108:    */
 109:   public static final Set EMPTY_SET = new EmptySet();
 110: 
 111:   /**
 112:    * The implementation of {@link #EMPTY_SET}. This class name is required
 113:    * for compatibility with Sun's JDK serializability.
 114:    *
 115:    * @author Eric Blake (ebb9@email.byu.edu)
 116:    */
 117:   private static final class EmptySet extends AbstractSet
 118:     implements Serializable
 119:   {
 120:     /**
 121:      * Compatible with JDK 1.4.
 122:      */
 123:     private static final long serialVersionUID = 1582296315990362920L;
 124: 
 125:     /**
 126:      * A private constructor adds overhead.
 127:      */
 128:     EmptySet()
 129:     {
 130:     }
 131: 
 132:     /**
 133:      * The size: always 0!
 134:      * @return 0.
 135:      */
 136:     public int size()
 137:     {
 138:       return 0;
 139:     }
 140: 
 141:     /**
 142:      * Returns an iterator that does not iterate.
 143:      * @return A non-iterating iterator.
 144:      */
 145:     // This is really cheating! I think it's perfectly valid, though.
 146:     public Iterator iterator()
 147:     {
 148:       return EMPTY_LIST.iterator();
 149:     }
 150: 
 151:     // The remaining methods are optional, but provide a performance
 152:     // advantage by not allocating unnecessary iterators in AbstractSet.
 153:     /**
 154:      * The empty set never contains anything.
 155:      * @param o The object to search for.
 156:      * @return <code>false</code>.
 157:      */
 158:     public boolean contains(Object o)
 159:     {
 160:       return false;
 161:     }
 162: 
 163:     /**
 164:      * This is true only if the given collection is also empty.
 165:      * @param c The collection of objects which are to be compared
 166:      *          against the members of this set.
 167:      * @return <code>true</code> if c is empty.
 168:      */
 169:     public boolean containsAll(Collection c)
 170:     {
 171:       return c.isEmpty();
 172:     }
 173: 
 174:     /**
 175:      * Equal only if the other set is empty.
 176:      * @param o The object to compare with this set.
 177:      * @return <code>true</code> if o is an empty instance of <code>Set</code>.
 178:      */
 179:     public boolean equals(Object o)
 180:     {
 181:       return o instanceof Set && ((Set) o).isEmpty();
 182:     }
 183: 
 184:     /**
 185:      * The hashcode is always 0.
 186:      * @return 0.
 187:      */
 188:     public int hashCode()
 189:     {
 190:       return 0;
 191:     }
 192: 
 193:     /**
 194:      * Always succeeds with a <code>false</code> result.
 195:      * @param o The object to remove.
 196:      * @return <code>false</code>.
 197:      */
 198:     public boolean remove(Object o)
 199:     {
 200:       return false;
 201:     }
 202: 
 203:     /**
 204:      * Always succeeds with a <code>false</code> result.
 205:      * @param c The collection of objects which should
 206:      *          all be removed from this set.
 207:      * @return <code>false</code>.
 208:      */
 209:     public boolean removeAll(Collection c)
 210:     {
 211:       return false;
 212:     }
 213: 
 214:     /**
 215:      * Always succeeds with a <code>false</code> result.
 216:      * @param c The collection of objects which should
 217:      *          all be retained within this set.
 218:      * @return <code>false</code>.
 219:      */
 220:     public boolean retainAll(Collection c)
 221:     {
 222:       return false;
 223:     }
 224: 
 225:     /**
 226:      * The array is always empty.
 227:      * @return A new array with a size of 0.
 228:      */
 229:     public Object[] toArray()
 230:     {
 231:       return new Object[0];
 232:     }
 233: 
 234:     /**
 235:      * We don't even need to use reflection!
 236:      * @param a An existing array, which can be empty.
 237:      * @return The original array with any existing
 238:      *         initial element set to null.
 239:      */
 240:     public Object[] toArray(Object[] a)
 241:     {
 242:       if (a.length > 0)
 243:         a[0] = null;
 244:       return a;
 245:     }
 246: 
 247:     /**
 248:      * The string never changes.
 249:      *
 250:      * @return the string "[]".
 251:      */
 252:     public String toString()
 253:     {
 254:       return "[]";
 255:     }
 256:   } // class EmptySet
 257: 
 258:   /**
 259:    * An immutable, serializable, empty List, which implements RandomAccess.
 260:    * @see Serializable
 261:    * @see RandomAccess
 262:    */
 263:   public static final List EMPTY_LIST = new EmptyList();
 264: 
 265:   /**
 266:    * The implementation of {@link #EMPTY_LIST}. This class name is required
 267:    * for compatibility with Sun's JDK serializability.
 268:    *
 269:    * @author Eric Blake (ebb9@email.byu.edu)
 270:    */
 271:   private static final class EmptyList extends AbstractList
 272:     implements Serializable, RandomAccess
 273:   {
 274:     /**
 275:      * Compatible with JDK 1.4.
 276:      */
 277:     private static final long serialVersionUID = 8842843931221139166L;
 278: 
 279:     /**
 280:      * A private constructor adds overhead.
 281:      */
 282:     EmptyList()
 283:     {
 284:     }
 285: 
 286:     /**
 287:      * The size is always 0.
 288:      * @return 0.
 289:      */
 290:     public int size()
 291:     {
 292:       return 0;
 293:     }
 294: 
 295:     /**
 296:      * No matter the index, it is out of bounds.  This
 297:      * method never returns, throwing an exception instead.
 298:      *
 299:      * @param index The index of the element to retrieve.
 300:      * @return the object at the specified index.
 301:      * @throws IndexOutOfBoundsException as any given index
 302:      *         is outside the bounds of an empty array.
 303:      */
 304:     public Object get(int index)
 305:     {
 306:       throw new IndexOutOfBoundsException();
 307:     }
 308: 
 309:     // The remaining methods are optional, but provide a performance
 310:     // advantage by not allocating unnecessary iterators in AbstractList.
 311:     /**
 312:      * Never contains anything.
 313:      * @param o The object to search for.
 314:      * @return <code>false</code>.
 315:      */
 316:     public boolean contains(Object o)
 317:     {
 318:       return false;
 319:     }
 320: 
 321:     /**
 322:      * This is true only if the given collection is also empty.
 323:      * @param c The collection of objects, which should be compared
 324:      *          against the members of this list.
 325:      * @return <code>true</code> if c is also empty. 
 326:      */
 327:     public boolean containsAll(Collection c)
 328:     {
 329:       return c.isEmpty();
 330:     }
 331: 
 332:     /**
 333:      * Equal only if the other list is empty.
 334:      * @param o The object to compare against this list.
 335:      * @return <code>true</code> if o is also an empty instance of
 336:      *         <code>List</code>.
 337:      */
 338:     public boolean equals(Object o)
 339:     {
 340:       return o instanceof List && ((List) o).isEmpty();
 341:     }
 342: 
 343:     /**
 344:      * The hashcode is always 1.
 345:      * @return 1.
 346:      */
 347:     public int hashCode()
 348:     {
 349:       return 1;
 350:     }
 351: 
 352:     /**
 353:      * Returns -1.
 354:      * @param o The object to search for.
 355:      * @return -1.
 356:      */
 357:     public int indexOf(Object o)
 358:     {
 359:       return -1;
 360:     }
 361: 
 362:     /**
 363:      * Returns -1.
 364:      * @param o The object to search for.
 365:      * @return -1.
 366:      */
 367:     public int lastIndexOf(Object o)
 368:     {
 369:       return -1;
 370:     }
 371: 
 372:     /**
 373:      * Always succeeds with <code>false</code> result.
 374:      * @param o The object to remove.
 375:      * @return -1.
 376:      */
 377:     public boolean remove(Object o)
 378:     {
 379:       return false;
 380:     }
 381: 
 382:     /**
 383:      * Always succeeds with <code>false</code> result.
 384:      * @param c The collection of objects which should
 385:      *          all be removed from this list.
 386:      * @return <code>false</code>.
 387:      */
 388:     public boolean removeAll(Collection c)
 389:     {
 390:       return false;
 391:     }
 392: 
 393:     /**
 394:      * Always succeeds with <code>false</code> result.
 395:      * @param c The collection of objects which should
 396:      *          all be retained within this list.
 397:      * @return <code>false</code>.
 398:      */
 399:     public boolean retainAll(Collection c)
 400:     {
 401:       return false;
 402:     }
 403: 
 404:     /**
 405:      * The array is always empty.
 406:      * @return A new array with a size of 0.
 407:      */
 408:     public Object[] toArray()
 409:     {
 410:       return new Object[0];
 411:     }
 412: 
 413:     /**
 414:      * We don't even need to use reflection!
 415:      * @param a An existing array, which can be empty.
 416:      * @return The original array with any existing
 417:      *         initial element set to null.
 418:      */
 419:     public Object[] toArray(Object[] a)
 420:     {
 421:       if (a.length > 0)
 422:         a[0] = null;
 423:       return a;
 424:     }
 425: 
 426:     /**
 427:      * The string never changes.
 428:      *
 429:      * @return the string "[]".
 430:      */
 431:     public String toString()
 432:     {
 433:       return "[]";
 434:     }
 435:   } // class EmptyList
 436: 
 437:   /**
 438:    * An immutable, serializable, empty Map.
 439:    * @see Serializable
 440:    */
 441:   public static final Map EMPTY_MAP = new EmptyMap();
 442: 
 443:   /**
 444:    * The implementation of {@link #EMPTY_MAP}. This class name is required
 445:    * for compatibility with Sun's JDK serializability.
 446:    *
 447:    * @author Eric Blake (ebb9@email.byu.edu)
 448:    */
 449:   private static final class EmptyMap extends AbstractMap
 450:     implements Serializable
 451:   {
 452:     /**
 453:      * Compatible with JDK 1.4.
 454:      */
 455:     private static final long serialVersionUID = 6428348081105594320L;
 456: 
 457:     /**
 458:      * A private constructor adds overhead.
 459:      */
 460:     EmptyMap()
 461:     {
 462:     }
 463: 
 464:     /**
 465:      * There are no entries.
 466:      * @return The empty set.
 467:      */
 468:     public Set entrySet()
 469:     {
 470:       return EMPTY_SET;
 471:     }
 472: 
 473:     // The remaining methods are optional, but provide a performance
 474:     // advantage by not allocating unnecessary iterators in AbstractMap.
 475:     /**
 476:      * No entries!
 477:      * @param key The key to search for.
 478:      * @return <code>false</code>.
 479:      */
 480:     public boolean containsKey(Object key)
 481:     {
 482:       return false;
 483:     }
 484: 
 485:     /**
 486:      * No entries!
 487:      * @param value The value to search for.
 488:      * @return <code>false</code>.
 489:      */
 490:     public boolean containsValue(Object value)
 491:     {
 492:       return false;
 493:     }
 494: 
 495:     /**
 496:      * Equal to all empty maps.
 497:      * @param o The object o to compare against this map.
 498:      * @return <code>true</code> if o is also an empty instance of
 499:      *         <code>Map</code>.
 500:      */
 501:     public boolean equals(Object o)
 502:     {
 503:       return o instanceof Map && ((Map) o).isEmpty();
 504:     }
 505: 
 506:     /**
 507:      * No mappings, so this returns null.
 508:      * @param o The key of the object to retrieve.
 509:      * @return null. 
 510:      */
 511:     public Object get(Object o)
 512:     {
 513:       return null;
 514:     }
 515: 
 516:     /**
 517:      * The hashcode is always 0.
 518:      * @return 0.
 519:      */
 520:     public int hashCode()
 521:     {
 522:       return 0;
 523:     }
 524: 
 525:     /**
 526:      * No entries.
 527:      * @return The empty set.
 528:      */
 529:     public Set keySet()
 530:     {
 531:       return EMPTY_SET;
 532:     }
 533: 
 534:     /**
 535:      * Remove always succeeds, with null result.
 536:      * @param o The key of the mapping to remove.
 537:      * @return null, as there is never a mapping for o.
 538:      */
 539:     public Object remove(Object o)
 540:     {
 541:       return null;
 542:     }
 543: 
 544:     /**
 545:      * Size is always 0.
 546:      * @return 0.
 547:      */
 548:     public int size()
 549:     {
 550:       return 0;
 551:     }
 552: 
 553:     /**
 554:      * No entries. Technically, EMPTY_SET, while more specific than a general
 555:      * Collection, will work. Besides, that's what the JDK uses!
 556:      * @return The empty set.
 557:      */
 558:     public Collection values()
 559:     {
 560:       return EMPTY_SET;
 561:     }
 562: 
 563:     /**
 564:      * The string never changes.
 565:      *
 566:      * @return the string "[]".
 567:      */
 568:     public String toString()
 569:     {
 570:       return "[]";
 571:     }
 572:   } // class EmptyMap
 573: 
 574: 
 575:   /**
 576:    * Compare two objects with or without a Comparator. If c is null, uses the
 577:    * natural ordering. Slightly slower than doing it inline if the JVM isn't
 578:    * clever, but worth it for removing a duplicate of the search code.
 579:    * Note: This code is also used in Arrays (for sort as well as search).
 580:    */
 581:   static final int compare(Object o1, Object o2, Comparator c)
 582:   {
 583:     return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
 584:   }
 585: 
 586:   /**
 587:    * Perform a binary search of a List for a key, using the natural ordering of
 588:    * the elements. The list must be sorted (as by the sort() method) - if it is
 589:    * not, the behavior of this method is undefined, and may be an infinite
 590:    * loop. Further, the key must be comparable with every item in the list. If
 591:    * the list contains the key more than once, any one of them may be found.
 592:    * <p>
 593:    *
 594:    * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
 595:    * and uses a linear search with O(n) link traversals and log(n) comparisons
 596:    * with {@link AbstractSequentialList} lists. Note: although the
 597:    * specification allows for an infinite loop if the list is unsorted, it will
 598:    * not happen in this (Classpath) implementation.
 599:    *
 600:    * @param l the list to search (must be sorted)
 601:    * @param key the value to search for
 602:    * @return the index at which the key was found, or -n-1 if it was not
 603:    *         found, where n is the index of the first value higher than key or
 604:    *         a.length if there is no such value
 605:    * @throws ClassCastException if key could not be compared with one of the
 606:    *         elements of l
 607:    * @throws NullPointerException if a null element has compareTo called
 608:    * @see #sort(List)
 609:    */
 610:   public static int binarySearch(List l, Object key)
 611:   {
 612:     return binarySearch(l, key, null);
 613:   }
 614: 
 615:   /**
 616:    * Perform a binary search of a List for a key, using a supplied Comparator.
 617:    * The list must be sorted (as by the sort() method with the same Comparator)
 618:    * - if it is not, the behavior of this method is undefined, and may be an
 619:    * infinite loop. Further, the key must be comparable with every item in the
 620:    * list. If the list contains the key more than once, any one of them may be
 621:    * found. If the comparator is null, the elements' natural ordering is used.
 622:    * <p>
 623:    *
 624:    * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
 625:    * and uses a linear search with O(n) link traversals and log(n) comparisons
 626:    * with {@link AbstractSequentialList} lists. Note: although the
 627:    * specification allows for an infinite loop if the list is unsorted, it will
 628:    * not happen in this (Classpath) implementation.
 629:    *
 630:    * @param l the list to search (must be sorted)
 631:    * @param key the value to search for
 632:    * @param c the comparator by which the list is sorted
 633:    * @return the index at which the key was found, or -n-1 if it was not
 634:    *         found, where n is the index of the first value higher than key or
 635:    *         a.length if there is no such value
 636:    * @throws ClassCastException if key could not be compared with one of the
 637:    *         elements of l
 638:    * @throws NullPointerException if a null element is compared with natural
 639:    *         ordering (only possible when c is null)
 640:    * @see #sort(List, Comparator)
 641:    */
 642:   public static int binarySearch(List l, Object key, Comparator c)
 643:   {
 644:     int pos = 0;
 645:     int low = 0;
 646:     int hi = l.size() - 1;
 647: 
 648:     // We use a linear search with log(n) comparisons using an iterator
 649:     // if the list is sequential-access.
 650:     if (isSequential(l))
 651:       {
 652:     ListIterator itr = l.listIterator();
 653:         int i = 0;
 654:     Object o = itr.next(); // Assumes list is not empty (see isSequential)
 655:     boolean forward = true;
 656:         while (low <= hi)
 657:           {
 658:             pos = (low + hi) >> 1;
 659:             if (i < pos)
 660:           {
 661:         if (!forward)
 662:           itr.next(); // Changing direction first.
 663:         for ( ; i != pos; i++, o = itr.next());
 664:         forward = true;
 665:           }
 666:             else
 667:           {
 668:         if (forward)
 669:           itr.previous(); // Changing direction first.
 670:         for ( ; i != pos; i--, o = itr.previous());
 671:         forward = false;
 672:           }
 673:         final int d = compare(o, key, c);
 674:         if (d == 0)
 675:               return pos;
 676:         else if (d > 0)
 677:               hi = pos - 1;
 678:         else
 679:               // This gets the insertion point right on the last loop
 680:               low = ++pos;
 681:           }
 682:       }
 683:     else
 684:       {
 685:     while (low <= hi)
 686:       {
 687:         pos = (low + hi) >> 1;
 688:         final int d = compare(l.get(pos), key, c);
 689:         if (d == 0)
 690:               return pos;
 691:         else if (d > 0)
 692:               hi = pos - 1;
 693:         else
 694:               // This gets the insertion point right on the last loop
 695:               low = ++pos;
 696:       }
 697:       }
 698: 
 699:     // If we failed to find it, we do the same whichever search we did.
 700:     return -pos - 1;
 701:   }
 702: 
 703:   /**
 704:    * Copy one list to another. If the destination list is longer than the
 705:    * source list, the remaining elements are unaffected. This method runs in
 706:    * linear time.
 707:    *
 708:    * @param dest the destination list
 709:    * @param source the source list
 710:    * @throws IndexOutOfBoundsException if the destination list is shorter
 711:    *         than the source list (the destination will be unmodified)
 712:    * @throws UnsupportedOperationException if dest.listIterator() does not
 713:    *         support the set operation
 714:    */
 715:   public static void copy(List dest, List source)
 716:   {
 717:     int pos = source.size();
 718:     if (dest.size() < pos)
 719:       throw new IndexOutOfBoundsException("Source does not fit in dest");
 720: 
 721:     Iterator i1 = source.iterator();
 722:     ListIterator i2 = dest.listIterator();
 723: 
 724:     while (--pos >= 0)
 725:       {
 726:         i2.next();
 727:         i2.set(i1.next());
 728:       }
 729:   }
 730: 
 731:   /**
 732:    * Returns an Enumeration over a collection. This allows interoperability
 733:    * with legacy APIs that require an Enumeration as input.
 734:    *
 735:    * @param c the Collection to iterate over
 736:    * @return an Enumeration backed by an Iterator over c
 737:    */
 738:   public static Enumeration enumeration(Collection c)
 739:   {
 740:     final Iterator i = c.iterator();
 741:     return new Enumeration()
 742:     {
 743:       /**
 744:        * Returns <code>true</code> if there are more elements to
 745:        * be enumerated.
 746:        *
 747:        * @return The result of <code>hasNext()</code>
 748:        *         called on the underlying iterator.
 749:        */
 750:       public final boolean hasMoreElements()
 751:       {
 752:     return i.hasNext();
 753:       }
 754: 
 755:       /**
 756:        * Returns the next element to be enumerated.
 757:        *
 758:        * @return The result of <code>next()</code>
 759:        *         called on the underlying iterator.
 760:        */
 761:       public final Object nextElement()
 762:       {
 763:     return i.next();
 764:       }
 765:     };
 766:   }
 767: 
 768:   /**
 769:    * Replace every element of a list with a given value. This method runs in
 770:    * linear time.
 771:    *
 772:    * @param l the list to fill.
 773:    * @param val the object to vill the list with.
 774:    * @throws UnsupportedOperationException if l.listIterator() does not
 775:    *         support the set operation.
 776:    */
 777:   public static void fill(List l, Object val)
 778:   {
 779:     ListIterator itr = l.listIterator();
 780:     for (int i = l.size() - 1; i >= 0; --i)
 781:       {
 782:     itr.next();
 783:     itr.set(val);
 784:       }
 785:   }
 786: 
 787:   /**
 788:    * Returns the starting index where the specified sublist first occurs
 789:    * in a larger list, or -1 if there is no matching position. If
 790:    * <code>target.size() &gt; source.size()</code>, this returns -1,
 791:    * otherwise this implementation uses brute force, checking for
 792:    * <code>source.sublist(i, i + target.size()).equals(target)</code>
 793:    * for all possible i.
 794:    *
 795:    * @param source the list to search
 796:    * @param target the sublist to search for
 797:    * @return the index where found, or -1
 798:    * @since 1.4
 799:    */
 800:   public static int indexOfSubList(List source, List target)
 801:   {
 802:     int ssize = source.size();
 803:     for (int i = 0, j = target.size(); j <= ssize; i++, j++)
 804:       if (source.subList(i, j).equals(target))
 805:         return i;
 806:     return -1;
 807:   }
 808: 
 809:   /**
 810:    * Returns the starting index where the specified sublist last occurs
 811:    * in a larger list, or -1 if there is no matching position. If
 812:    * <code>target.size() &gt; source.size()</code>, this returns -1,
 813:    * otherwise this implementation uses brute force, checking for
 814:    * <code>source.sublist(i, i + target.size()).equals(target)</code>
 815:    * for all possible i.
 816:    *
 817:    * @param source the list to search
 818:    * @param target the sublist to search for
 819:    * @return the index where found, or -1
 820:    * @since 1.4
 821:    */
 822:   public static int lastIndexOfSubList(List source, List target)
 823:   {
 824:     int ssize = source.size();
 825:     for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--)
 826:       if (source.subList(i, j).equals(target))
 827:         return i;
 828:     return -1;
 829:   }
 830: 
 831:   /**
 832:    * Returns an ArrayList holding the elements visited by a given
 833:    * Enumeration. This method exists for interoperability between legacy
 834:    * APIs and the new Collection API.
 835:    *
 836:    * @param e the enumeration to put in a list
 837:    * @return a list containing the enumeration elements
 838:    * @see ArrayList
 839:    * @since 1.4
 840:    */
 841:   public static ArrayList list(Enumeration e)
 842:   {
 843:     ArrayList l = new ArrayList();
 844:     while (e.hasMoreElements())
 845:       l.add(e.nextElement());
 846:     return l;
 847:   }
 848: 
 849:   /**
 850:    * Find the maximum element in a Collection, according to the natural
 851:    * ordering of the elements. This implementation iterates over the
 852:    * Collection, so it works in linear time.
 853:    *
 854:    * @param c the Collection to find the maximum element of
 855:    * @return the maximum element of c
 856:    * @exception NoSuchElementException if c is empty
 857:    * @exception ClassCastException if elements in c are not mutually comparable
 858:    * @exception NullPointerException if null.compareTo is called
 859:    */
 860:   public static Object max(Collection c)
 861:   {
 862:     return max(c, null);
 863:   }
 864: 
 865:   /**
 866:    * Find the maximum element in a Collection, according to a specified
 867:    * Comparator. This implementation iterates over the Collection, so it
 868:    * works in linear time.
 869:    *
 870:    * @param c the Collection to find the maximum element of
 871:    * @param order the Comparator to order the elements by, or null for natural
 872:    *        ordering
 873:    * @return the maximum element of c
 874:    * @throws NoSuchElementException if c is empty
 875:    * @throws ClassCastException if elements in c are not mutually comparable
 876:    * @throws NullPointerException if null is compared by natural ordering
 877:    *        (only possible when order is null)
 878:    */
 879:   public static Object max(Collection c, Comparator order)
 880:   {
 881:     Iterator itr = c.iterator();
 882:     Object max = itr.next(); // throws NoSuchElementException
 883:     int csize = c.size();
 884:     for (int i = 1; i < csize; i++)
 885:       {
 886:     Object o = itr.next();
 887:     if (compare(max, o, order) < 0)
 888:       max = o;
 889:       }
 890:     return max;
 891:   }
 892: 
 893:   /**
 894:    * Find the minimum element in a Collection, according to the natural
 895:    * ordering of the elements. This implementation iterates over the
 896:    * Collection, so it works in linear time.
 897:    *
 898:    * @param c the Collection to find the minimum element of
 899:    * @return the minimum element of c
 900:    * @throws NoSuchElementException if c is empty
 901:    * @throws ClassCastException if elements in c are not mutually comparable
 902:    * @throws NullPointerException if null.compareTo is called
 903:    */
 904:   public static Object min(Collection c)
 905:   {
 906:     return min(c, null);
 907:   }
 908: 
 909:   /**
 910:    * Find the minimum element in a Collection, according to a specified
 911:    * Comparator. This implementation iterates over the Collection, so it
 912:    * works in linear time.
 913:    *
 914:    * @param c the Collection to find the minimum element of
 915:    * @param order the Comparator to order the elements by, or null for natural
 916:    *        ordering
 917:    * @return the minimum element of c
 918:    * @throws NoSuchElementException if c is empty
 919:    * @throws ClassCastException if elements in c are not mutually comparable
 920:    * @throws NullPointerException if null is compared by natural ordering
 921:    *        (only possible when order is null)
 922:    */
 923:   public static Object min(Collection c, Comparator order)
 924:   {
 925:     Iterator itr = c.iterator();
 926:     Object min = itr.next();    // throws NoSuchElementExcception
 927:     int csize = c.size();
 928:     for (int i = 1; i < csize; i++)
 929:       {
 930:     Object o = itr.next();
 931:     if (compare(min, o, order) > 0)
 932:       min = o;
 933:       }
 934:     return min;
 935:   }
 936: 
 937:   /**
 938:    * Creates an immutable list consisting of the same object repeated n times.
 939:    * The returned object is tiny, consisting of only a single reference to the
 940:    * object and a count of the number of elements. It is Serializable, and
 941:    * implements RandomAccess. You can use it in tandem with List.addAll for
 942:    * fast list construction.
 943:    *
 944:    * @param n the number of times to repeat the object
 945:    * @param o the object to repeat
 946:    * @return a List consisting of n copies of o
 947:    * @throws IllegalArgumentException if n &lt; 0
 948:    * @see List#addAll(Collection)
 949:    * @see Serializable
 950:    * @see RandomAccess
 951:    */
 952:   public static List nCopies(final int n, final Object o)
 953:   {
 954:     return new CopiesList(n, o);
 955:   }
 956: 
 957:   /**
 958:    * The implementation of {@link #nCopies(int, Object)}. This class name
 959:    * is required for compatibility with Sun's JDK serializability.
 960:    *
 961:    * @author Eric Blake (ebb9@email.byu.edu)
 962:    */
 963:   private static final class CopiesList extends AbstractList
 964:     implements Serializable, RandomAccess
 965:   {
 966:     /**
 967:      * Compatible with JDK 1.4.
 968:      */
 969:     private static final long serialVersionUID = 2739099268398711800L;
 970: 
 971:     /**
 972:      * The count of elements in this list.
 973:      * @serial the list size
 974:      */
 975:     private final int n;
 976: 
 977:     /**
 978:      * The repeated list element.
 979:      * @serial the list contents
 980:      */
 981:     private final Object element;
 982: 
 983:     /**
 984:      * Constructs the list.
 985:      *
 986:      * @param n the count
 987:      * @param o the object
 988:      * @throws IllegalArgumentException if n &lt; 0
 989:      */
 990:     CopiesList(int n, Object o)
 991:     {
 992:       if (n < 0)
 993:     throw new IllegalArgumentException();
 994:       this.n = n;
 995:       element = o;
 996:     }
 997: 
 998:     /**
 999:      * The size is fixed.
1000:      * @return The size of the list.
1001:      */
1002:     public int size()
1003:     {
1004:       return n;
1005:     }
1006: 
1007:     /**
1008:      * The same element is returned.
1009:      * @param index The index of the element to be returned (irrelevant
1010:      *        as the list contains only copies of <code>element</code>).
1011:      * @return The element used by this list.
1012:      */
1013:     public Object get(int index)
1014:     {
1015:       if (index < 0 || index >= n)
1016:         throw new IndexOutOfBoundsException();
1017:       return element;
1018:     }
1019: 
1020:     // The remaining methods are optional, but provide a performance
1021:     // advantage by not allocating unnecessary iterators in AbstractList.
1022:     /**
1023:      * This list only contains one element.
1024:      * @param o The object to search for.
1025:      * @return <code>true</code> if o is the element used by this list.
1026:      */
1027:     public boolean contains(Object o)
1028:     {
1029:       return n > 0 && equals(o, element);
1030:     }
1031: 
1032:     /**
1033:      * The index is either 0 or -1.
1034:      * @param o The object to find the index of.
1035:      * @return 0 if <code>o == element</code>, -1 if not.
1036:      */
1037:     public int indexOf(Object o)
1038:     {
1039:       return (n > 0 && equals(o, element)) ? 0 : -1;
1040:     }
1041: 
1042:     /**
1043:      * The index is either n-1 or -1.
1044:      * @param o The object to find the last index of.
1045:      * @return The last index in the list if <code>o == element</code>,
1046:      *         -1 if not.
1047:      */
1048:     public int lastIndexOf(Object o)
1049:     {
1050:       return equals(o, element) ? n - 1 : -1;
1051:     }
1052: 
1053:     /**
1054:      * A subList is just another CopiesList.
1055:      * @param from The starting bound of the sublist.
1056:      * @param to The ending bound of the sublist.
1057:      * @return A list of copies containing <code>from - to</code>
1058:      *         elements, all of which are equal to the element
1059:      *         used by this list.
1060:      */
1061:     public List subList(int from, int to)
1062:     {
1063:       if (from < 0 || to > n)
1064:         throw new IndexOutOfBoundsException();
1065:       return new CopiesList(to - from, element);
1066:     }
1067: 
1068:     /**
1069:      * The array is easy.
1070:      * @return An array of size n filled with copies of
1071:      *         the element used by this list.
1072:      */
1073:     public Object[] toArray()
1074:     {
1075:       Object[] a = new Object[n];
1076:       Arrays.fill(a, element);
1077:       return a;
1078:     }
1079: 
1080:     /**
1081:      * The string is easy to generate.
1082:      * @return A string representation of the list.
1083:      */
1084:     public String toString()
1085:     {
1086:       StringBuffer r = new StringBuffer("{");
1087:       for (int i = n - 1; --i > 0; )
1088:         r.append(element).append(", ");
1089:       r.append(element).append("}");
1090:       return r.toString();
1091:     }
1092:   } // class CopiesList
1093: 
1094:   /**
1095:    * Replace all instances of one object with another in the specified list.
1096:    * The list does not change size. An element e is replaced if
1097:    * <code>oldval == null ? e == null : oldval.equals(e)</code>.
1098:    *
1099:    * @param list the list to iterate over
1100:    * @param oldval the element to replace
1101:    * @param newval the new value for the element
1102:    * @return <code>true</code> if a replacement occurred.
1103:    * @throws UnsupportedOperationException if the list iterator does not allow
1104:    *         for the set operation
1105:    * @throws ClassCastException if newval is of a type which cannot be added
1106:    *         to the list
1107:    * @throws IllegalArgumentException if some other aspect of newval stops
1108:    *         it being added to the list
1109:    * @since 1.4
1110:    */
1111:   public static boolean replaceAll(List list, Object oldval, Object newval)
1112:   {
1113:     ListIterator itr = list.listIterator();
1114:     boolean replace_occured = false;
1115:     for (int i = list.size(); --i >= 0; )
1116:       if (AbstractCollection.equals(oldval, itr.next()))
1117:         {
1118:           itr.set(newval);
1119:           replace_occured = true;
1120:         }
1121:     return replace_occured;
1122:   }
1123: 
1124:   /**
1125:    * Reverse a given list. This method works in linear time.
1126:    *
1127:    * @param l the list to reverse
1128:    * @throws UnsupportedOperationException if l.listIterator() does not
1129:    *         support the set operation
1130:    */
1131:   public static void reverse(List l)
1132:   {
1133:     ListIterator i1 = l.listIterator();
1134:     int pos1 = 1;
1135:     int pos2 = l.size();
1136:     ListIterator i2 = l.listIterator(pos2);
1137:     while (pos1 < pos2)
1138:       {
1139:     Object o = i1.next();
1140:     i1.set(i2.previous());
1141:     i2.set(o);
1142:     ++pos1;
1143:     --pos2;
1144:       }
1145:   }
1146: 
1147:   /**
1148:    * Get a comparator that implements the reverse of natural ordering. In
1149:    * other words, this sorts Comparable objects opposite of how their
1150:    * compareTo method would sort. This makes it easy to sort into reverse
1151:    * order, by simply passing Collections.reverseOrder() to the sort method.
1152:    * The return value of this method is Serializable.
1153:    *
1154:    * @return a comparator that imposes reverse natural ordering
1155:    * @see Comparable
1156:    * @see Serializable
1157:    */
1158:   public static Comparator reverseOrder()
1159:   {
1160:     return rcInstance;
1161:   }
1162: 
1163:   /**
1164:    * The object for {@link #reverseOrder()}.
1165:    */
1166:   private static final ReverseComparator rcInstance = new ReverseComparator();
1167: 
1168:   /**
1169:    * The implementation of {@link #reverseOrder()}. This class name
1170:    * is required for compatibility with Sun's JDK serializability.
1171:    *
1172:    * @author Eric Blake (ebb9@email.byu.edu)
1173:    */
1174:   private static final class ReverseComparator
1175:     implements Comparator, Serializable
1176:   {
1177:     /**
1178:      * Compatible with JDK 1.4.
1179:      */
1180:     private static final long serialVersionUID = 7207038068494060240L;
1181: 
1182:     /**
1183:      * A private constructor adds overhead.
1184:      */
1185:     ReverseComparator()
1186:     {
1187:     }
1188: 
1189:     /**
1190:      * Compare two objects in reverse natural order.
1191:      *
1192:      * @param a the first object
1193:      * @param b the second object
1194:      * @return &lt;, ==, or &gt; 0 according to b.compareTo(a)
1195:      */
1196:     public int compare(Object a, Object b)
1197:     {
1198:       return ((Comparable) b).compareTo(a);
1199:     }
1200:   }
1201: 
1202:   /**
1203:    * Rotate the elements in a list by a specified distance. After calling this
1204:    * method, the element now at index <code>i</code> was formerly at index
1205:    * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
1206:    * <p>
1207:    *
1208:    * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
1209:    * either <code>Collections.rotate(l, 4)</code> or
1210:    * <code>Collections.rotate(l, -1)</code>, the new contents are
1211:    * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
1212:    * just a portion of the list. For example, to move element <code>a</code>
1213:    * forward two positions in the original example, use
1214:    * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
1215:    * result in <code>[t, n, k, a, s]</code>.
1216:    * <p>
1217:    *
1218:    * If the list is small or implements {@link RandomAccess}, the
1219:    * implementation exchanges the first element to its destination, then the
1220:    * displaced element, and so on until a circuit has been completed. The
1221:    * process is repeated if needed on the second element, and so forth, until
1222:    * all elements have been swapped.  For large non-random lists, the
1223:    * implementation breaks the list into two sublists at index
1224:    * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
1225:    * pieces, then reverses the overall list.
1226:    *
1227:    * @param list the list to rotate
1228:    * @param distance the distance to rotate by; unrestricted in value
1229:    * @throws UnsupportedOperationException if the list does not support set
1230:    * @since 1.4
1231:    */
1232:   public static void rotate(List list, int distance)
1233:   {
1234:     int size = list.size();
1235:     if (size == 0)
1236:       return;
1237:     distance %= size;
1238:     if (distance == 0)
1239:       return;
1240:     if (distance < 0)
1241:       distance += size;
1242: 
1243:     if (isSequential(list))
1244:       {
1245:         reverse(list);
1246:         reverse(list.subList(0, distance));
1247:         reverse(list.subList(distance, size));
1248:       }
1249:     else
1250:       {
1251:         // Determine the least common multiple of distance and size, as there
1252:         // are (distance / LCM) loops to cycle through.
1253:         int a = size;
1254:         int lcm = distance;
1255:         int b = a % lcm;
1256:         while (b != 0)
1257:           {
1258:             a = lcm;
1259:             lcm = b;
1260:             b = a % lcm;
1261:           }
1262: 
1263:         // Now, make the swaps. We must take the remainder every time through
1264:         // the inner loop so that we don't overflow i to negative values.
1265:         while (--lcm >= 0)
1266:           {
1267:             Object o = list.get(lcm);
1268:             for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
1269:               o = list.set(i, o);
1270:             list.set(lcm, o);
1271:           }
1272:       }
1273:   }
1274: 
1275:   /**
1276:    * Shuffle a list according to a default source of randomness. The algorithm
1277:    * used iterates backwards over the list, swapping each element with an
1278:    * element randomly selected from the elements in positions less than or
1279:    * equal to it (using r.nextInt(int)).
1280:    * <p>
1281:    *
1282:    * This algorithm would result in a perfectly fair shuffle (that is, each
1283:    * element would have an equal chance of ending up in any position) if r were
1284:    * a perfect source of randomness. In practice the results are merely very
1285:    * close to perfect.
1286:    * <p>
1287:    *
1288:    * This method operates in linear time. To do this on large lists which do
1289:    * not implement {@link RandomAccess}, a temporary array is used to acheive
1290:    * this speed, since it would be quadratic access otherwise.
1291:    *
1292:    * @param l the list to shuffle
1293:    * @throws UnsupportedOperationException if l.listIterator() does not
1294:    *         support the set operation
1295:    */
1296:   public static void shuffle(List l)
1297:   {
1298:     if (defaultRandom == null)
1299:       {
1300:         synchronized (Collections.class)
1301:     {
1302:       if (defaultRandom == null)
1303:             defaultRandom = new Random();
1304:     }
1305:       }
1306:     shuffle(l, defaultRandom);
1307:   }
1308: 
1309:   /**
1310:    * Cache a single Random object for use by shuffle(List). This improves
1311:    * performance as well as ensuring that sequential calls to shuffle() will
1312:    * not result in the same shuffle order occurring: the resolution of
1313:    * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
1314:    */
1315:   private static Random defaultRandom = null;
1316: 
1317:   /**
1318:    * Shuffle a list according to a given source of randomness. The algorithm
1319:    * used iterates backwards over the list, swapping each element with an
1320:    * element randomly selected from the elements in positions less than or
1321:    * equal to it (using r.nextInt(int)).
1322:    * <p>
1323:    *
1324:    * This algorithm would result in a perfectly fair shuffle (that is, each
1325:    * element would have an equal chance of ending up in any position) if r were
1326:    * a perfect source of randomness. In practise (eg if r = new Random()) the
1327:    * results are merely very close to perfect.
1328:    * <p>
1329:    *
1330:    * This method operates in linear time. To do this on large lists which do
1331:    * not implement {@link RandomAccess}, a temporary array is used to acheive
1332:    * this speed, since it would be quadratic access otherwise.
1333:    *
1334:    * @param l the list to shuffle
1335:    * @param r the source of randomness to use for the shuffle
1336:    * @throws UnsupportedOperationException if l.listIterator() does not
1337:    *         support the set operation
1338:    */
1339:   public static void shuffle(List l, Random r)
1340:   {
1341:     int lsize = l.size();
1342:     ListIterator i = l.listIterator(lsize);
1343:     boolean sequential = isSequential(l);
1344:     Object[] a = null; // stores a copy of the list for the sequential case
1345: 
1346:     if (sequential)
1347:       a = l.toArray();
1348: 
1349:     for (int pos = lsize - 1; pos > 0; --pos)
1350:       {
1351:     // Obtain a random position to swap with. pos + 1 is used so that the
1352:     // range of the random number includes the current position.
1353:     int swap = r.nextInt(pos + 1);
1354: 
1355:     // Swap the desired element.
1356:     Object o;
1357:         if (sequential)
1358:           {
1359:             o = a[swap];
1360:             a[swap] = i.previous();
1361:           }
1362:         else
1363:           o = l.set(swap, i.previous());
1364: 
1365:     i.set(o);
1366:       }
1367:   }
1368: 
1369: 
1370:   /**
1371:    * Obtain an immutable Set consisting of a single element. The return value
1372:    * of this method is Serializable.
1373:    *
1374:    * @param o the single element
1375:    * @return an immutable Set containing only o
1376:    * @see Serializable
1377:    */
1378:   public static Set singleton(Object o)
1379:   {
1380:     return new SingletonSet(o);
1381:   }
1382: 
1383:   /**
1384:    * The implementation of {@link #singleton(Object)}. This class name
1385:    * is required for compatibility with Sun's JDK serializability.
1386:    *
1387:    * @author Eric Blake (ebb9@email.byu.edu)
1388:    */
1389:   private static final class SingletonSet extends AbstractSet
1390:     implements Serializable
1391:   {
1392:     /**
1393:      * Compatible with JDK 1.4.
1394:      */
1395:     private static final long serialVersionUID = 3193687207550431679L;
1396: 
1397: 
1398:     /**
1399:      * The single element; package visible for use in nested class.
1400:      * @serial the singleton
1401:      */
1402:     final Object element;
1403: 
1404:     /**
1405:      * Construct a singleton.
1406:      * @param o the element
1407:      */
1408:     SingletonSet(Object o)
1409:     {
1410:       element = o;
1411:     }
1412: 
1413:     /**
1414:      * The size: always 1!
1415:      * @return 1.
1416:      */
1417:     public int size()
1418:     {
1419:       return 1;
1420:     }
1421: 
1422:     /**
1423:      * Returns an iterator over the lone element.
1424:      */
1425:     public Iterator iterator()
1426:     {
1427:       return new Iterator()
1428:       {
1429:     /**
1430:      * Flag to indicate whether or not the element has
1431:      * been retrieved.
1432:      */
1433:         private boolean hasNext = true;
1434: 
1435:     /**
1436:      * Returns <code>true</code> if elements still remain to be
1437:      * iterated through.
1438:      *
1439:      * @return <code>true</code> if the element has not yet been returned.
1440:      */
1441:         public boolean hasNext()
1442:         {
1443:           return hasNext;
1444:         }
1445: 
1446:     /**
1447:      * Returns the element.
1448:      *
1449:      * @return The element used by this singleton.
1450:      * @throws NoSuchElementException if the object
1451:      *         has already been retrieved.
1452:      */ 
1453:         public Object next()
1454:         {
1455:           if (hasNext)
1456:           {
1457:             hasNext = false;
1458:             return element;
1459:           }
1460:           else
1461:             throw new NoSuchElementException();
1462:         }
1463: 
1464:     /**
1465:      * Removes the element from the singleton.
1466:      * As this set is immutable, this will always
1467:      * throw an exception.
1468:      *
1469:      * @throws UnsupportedOperationException as the
1470:      *         singleton set doesn't support
1471:      *         <code>remove()</code>.
1472:      */
1473:         public void remove()
1474:         {
1475:           throw new UnsupportedOperationException();
1476:         }
1477:       };
1478:     }
1479: 
1480:     // The remaining methods are optional, but provide a performance
1481:     // advantage by not allocating unnecessary iterators in AbstractSet.
1482:     /**
1483:      * The set only contains one element.
1484:      *
1485:      * @param o The object to search for.
1486:      * @return <code>true</code> if o == the element of the singleton.
1487:      */
1488:     public boolean contains(Object o)
1489:     {
1490:       return equals(o, element);
1491:     }
1492: 
1493:     /**
1494:      * This is true if the other collection only contains the element.
1495:      *
1496:      * @param c A collection to compare against this singleton.
1497:      * @return <code>true</code> if c only contains either no elements or
1498:      *         elements equal to the element in this singleton.
1499:      */
1500:     public boolean containsAll(Collection c)
1501:     {
1502:       Iterator i = c.iterator();
1503:       int pos = c.size();
1504:       while (--pos >= 0)
1505:         if (! equals(i.next(), element))
1506:           return false;
1507:       return true;
1508:     }
1509: 
1510:     /**
1511:      * The hash is just that of the element.
1512:      * 
1513:      * @return The hashcode of the element.
1514:      */
1515:     public int hashCode()
1516:     {
1517:       return hashCode(element);
1518:     }
1519: 
1520:     /**
1521:      * Returning an array is simple.
1522:      *
1523:      * @return An array containing the element.
1524:      */
1525:     public Object[] toArray()
1526:     {
1527:       return new Object[] {element};
1528:     }
1529: 
1530:     /**
1531:      * Obvious string.
1532:      *
1533:      * @return The string surrounded by enclosing
1534:      *         square brackets.
1535:      */
1536:     public String toString()
1537:     {
1538:       return "[" + element + "]";
1539:     }
1540:   } // class SingletonSet
1541: 
1542:   /**
1543:    * Obtain an immutable List consisting of a single element. The return value
1544:    * of this method is Serializable, and implements RandomAccess.
1545:    *
1546:    * @param o the single element
1547:    * @return an immutable List containing only o
1548:    * @see Serializable
1549:    * @see RandomAccess
1550:    * @since 1.3
1551:    */
1552:   public static List singletonList(Object o)
1553:   {
1554:     return new SingletonList(o);
1555:   }
1556: 
1557:   /**
1558:    * The implementation of {@link #singletonList(Object)}. This class name
1559:    * is required for compatibility with Sun's JDK serializability.
1560:    *
1561:    * @author Eric Blake (ebb9@email.byu.edu)
1562:    */
1563:   private static final class SingletonList extends AbstractList
1564:     implements Serializable, RandomAccess
1565:   {
1566:     /**
1567:      * Compatible with JDK 1.4.
1568:      */
1569:     private static final long serialVersionUID = 3093736618740652951L;
1570: 
1571:     /**
1572:      * The single element.
1573:      * @serial the singleton
1574:      */
1575:     private final Object element;
1576: 
1577:     /**
1578:      * Construct a singleton.
1579:      * @param o the element
1580:      */
1581:     SingletonList(Object 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:      * Only index 0 is valid.
1597:      * @param index The index of the element
1598:      *        to retrieve.
1599:      * @return The singleton's element if the
1600:      *         index is 0.
1601:      * @throws IndexOutOfBoundsException if
1602:      *         index is not 0.
1603:      */
1604:     public Object get(int index)
1605:     {
1606:       if (index == 0)
1607:         return element;
1608:       throw new IndexOutOfBoundsException();
1609:     }
1610: 
1611:     // The remaining methods are optional, but provide a performance
1612:     // advantage by not allocating unnecessary iterators in AbstractList.
1613:     /**
1614:      * The set only contains one element.
1615:      *
1616:      * @param o The object to search for.
1617:      * @return <code>true</code> if o == the singleton element.
1618:      */
1619:     public boolean contains(Object o)
1620:     {
1621:       return equals(o, element);
1622:     }
1623: 
1624:     /**
1625:      * This is true if the other collection only contains the element.
1626:      *
1627:      * @param c A collection to compare against this singleton.
1628:      * @return <code>true</code> if c only contains either no elements or
1629:      *         elements equal to the element in this singleton.
1630:      */
1631:     public boolean containsAll(Collection c)
1632:     {
1633:       Iterator i = c.iterator();
1634:       int pos = c.size();
1635:       while (--pos >= 0)
1636:         if (! equals(i.next(), element))
1637:           return false;
1638:       return true;
1639:     }
1640: 
1641:     /**
1642:      * Speed up the hashcode computation.
1643:      *
1644:      * @return The hashcode of the list, based
1645:      *         on the hashcode of the singleton element.
1646:      */
1647:     public int hashCode()
1648:     {
1649:       return 31 + hashCode(element);
1650:     }
1651: 
1652:     /**
1653:      * Either the list has it or not.
1654:      *
1655:      * @param o The object to find the first index of.
1656:      * @return 0 if o is the singleton element, -1 if not.
1657:      */
1658:     public int indexOf(Object o)
1659:     {
1660:       return equals(o, element) ? 0 : -1;
1661:     }
1662: 
1663:     /**
1664:      * Either the list has it or not.
1665:      *
1666:      * @param o The object to find the last index of.
1667:      * @return 0 if o is the singleton element, -1 if not.
1668:      */
1669:     public int lastIndexOf(Object o)
1670:     {
1671:       return equals(o, element) ? 0 : -1;
1672:     }
1673: 
1674:     /**
1675:      * Sublists are limited in scope.
1676:      * 
1677:      * @param from The starting bound for the sublist.
1678:      * @param to The ending bound for the sublist.
1679:      * @return Either an empty list if both bounds are
1680:      *         0 or 1, or this list if the bounds are 0 and 1.
1681:      * @throws IllegalArgumentException if <code>from > to</code>
1682:      * @throws IndexOutOfBoundsException if either bound is greater
1683:      *         than 1.
1684:      */
1685:     public List subList(int from, int to)
1686:     {
1687:       if (from == to && (to == 0 || to == 1))
1688:         return EMPTY_LIST;
1689:       if (from == 0 && to == 1)
1690:         return this;
1691:       if (from > to)
1692:         throw new IllegalArgumentException();
1693:       throw new IndexOutOfBoundsException();
1694:     }
1695: 
1696:     /**
1697:      * Returning an array is simple.
1698:      *
1699:      * @return An array containing the element.
1700:      */
1701:     public Object[] toArray()
1702:     {
1703:       return new Object[] {element};
1704:     }
1705: 
1706:     /**
1707:      * Obvious string.
1708:      *
1709:      * @return The string surrounded by enclosing
1710:      *         square brackets. 
1711:      */
1712:     public String toString()
1713:     {
1714:       return "[" + element + "]";
1715:     }
1716:   } // class SingletonList
1717: 
1718:   /**
1719:    * Obtain an immutable Map consisting of a single key-value pair.
1720:    * The return value of this method is Serializable.
1721:    *
1722:    * @param key the single key
1723:    * @param value the single value
1724:    * @return an immutable Map containing only the single key-value pair
1725:    * @see Serializable
1726:    * @since 1.3
1727:    */
1728:   public static Map singletonMap(Object key, Object value)
1729:   {
1730:     return new SingletonMap(key, value);
1731:   }
1732: 
1733:   /**
1734:    * The implementation of {@link #singletonMap(Object, Object)}. This class
1735:    * name is required for compatibility with Sun's JDK serializability.
1736:    *
1737:    * @author Eric Blake (ebb9@email.byu.edu)
1738:    */
1739:   private static final class SingletonMap extends AbstractMap
1740:     implements Serializable
1741:   {
1742:     /**
1743:      * Compatible with JDK 1.4.
1744:      */
1745:     private static final long serialVersionUID = -6979724477215052911L;
1746: 
1747:     /**
1748:      * The single key.
1749:      * @serial the singleton key
1750:      */
1751:     private final Object k;
1752: 
1753:     /**
1754:      * The corresponding value.
1755:      * @serial the singleton value
1756:      */
1757:     private final Object v;
1758: 
1759:     /**
1760:      * Cache the entry set.
1761:      */
1762:     private transient Set entries;
1763: 
1764:     /**
1765:      * Construct a singleton.
1766:      * @param key the key
1767:      * @param value the value
1768:      */
1769:     SingletonMap(Object key, Object value)
1770:     {
1771:       k = key;
1772:       v = value;
1773:     }
1774: 
1775:     /**
1776:      * There is a single immutable entry.
1777:      *
1778:      * @return A singleton containing the map entry.
1779:      */
1780:     public Set entrySet()
1781:     {
1782:       if (entries == null)
1783:         entries = singleton(new AbstractMap.BasicMapEntry(k, v)
1784:         {
1785:       /**
1786:        * Sets the value of the map entry to the supplied value.
1787:        * An exception is always thrown, as the map is immutable.
1788:        *
1789:        * @param o The new value.
1790:        * @return The old value.
1791:        * @throws UnsupportedOperationException as setting the value
1792:        *         is not supported.
1793:        */
1794:           public Object setValue(Object o)
1795:           {
1796:             throw new UnsupportedOperationException();
1797:           }
1798:         });
1799:       return entries;
1800:     }
1801: 
1802:     // The remaining methods are optional, but provide a performance
1803:     // advantage by not allocating unnecessary iterators in AbstractMap.
1804:     /**
1805:      * Single entry.
1806:      *
1807:      * @param key The key to look for.
1808:      * @return <code>true</code> if the key is the same as the one used by
1809:      *         this map.
1810:      */
1811:     public boolean containsKey(Object key)
1812:     {
1813:       return equals(key, k);
1814:     }
1815: 
1816:     /**
1817:      * Single entry.
1818:      *
1819:      * @param value The value to look for.
1820:      * @return <code>true</code> if the value is the same as the one used by
1821:      *         this map.
1822:      */
1823:     public boolean containsValue(Object value)
1824:     {
1825:       return equals(value, v);
1826:     }
1827: 
1828:     /**
1829:      * Single entry.
1830:      *
1831:      * @param key The key of the value to be retrieved.
1832:      * @return The singleton value if the key is the same as the
1833:      *         singleton key, null otherwise.
1834:      */
1835:     public Object get(Object key)
1836:     {
1837:       return equals(key, k) ? v : null;
1838:     }
1839: 
1840:     /**
1841:      * Calculate the hashcode directly.
1842:      *
1843:      * @return The hashcode computed from the singleton key
1844:      *         and the singleton value.
1845:      */
1846:     public int hashCode()
1847:     {
1848:       return hashCode(k) ^ hashCode(v);
1849:     }
1850: 
1851:     /**
1852:      * Return the keyset.
1853:      *
1854:      * @return A singleton containing the key.
1855:      */
1856:     public Set keySet()
1857:     {
1858:       if (keys == null)
1859:         keys = singleton(k);
1860:       return keys;
1861:     }
1862: 
1863:     /**
1864:      * The size: always 1!
1865:      *
1866:      * @return 1.
1867:      */
1868:     public int size()
1869:     {
1870:       return 1;
1871:     }
1872: 
1873:     /**
1874:      * Return the values. Technically, a singleton, while more specific than
1875:      * a general Collection, will work. Besides, that's what the JDK uses!
1876:      *
1877:      * @return A singleton containing the value.
1878:      */
1879:     public Collection values()
1880:     {
1881:       if (values == null)
1882:         values = singleton(v);
1883:       return values;
1884:     }
1885: 
1886:     /**
1887:      * Obvious string.
1888:      *
1889:      * @return A string containing the string representations of the key
1890:      *         and its associated value.
1891:      */
1892:     public String toString()
1893:     {
1894:       return "{" + k + "=" + v + "}";
1895:     }
1896:   } // class SingletonMap
1897: 
1898:   /**
1899:    * Sort a list according to the natural ordering of its elements. The list
1900:    * must be modifiable, but can be of fixed size. The sort algorithm is
1901:    * precisely that used by Arrays.sort(Object[]), which offers guaranteed
1902:    * nlog(n) performance. This implementation dumps the list into an array,
1903:    * sorts the array, and then iterates over the list setting each element from
1904:    * the array.
1905:    *
1906:    * @param l the List to sort
1907:    * @throws ClassCastException if some items are not mutually comparable
1908:    * @throws UnsupportedOperationException if the List is not modifiable
1909:    * @throws NullPointerException if some element is null
1910:    * @see Arrays#sort(Object[])
1911:    */
1912:   public static void sort(List l)
1913:   {
1914:     sort(l, null);
1915:   }
1916: 
1917:   /**
1918:    * Sort a list according to a specified Comparator. The list must be
1919:    * modifiable, but can be of fixed size. The sort algorithm is precisely that
1920:    * used by Arrays.sort(Object[], Comparator), which offers guaranteed
1921:    * nlog(n) performance. This implementation dumps the list into an array,
1922:    * sorts the array, and then iterates over the list setting each element from
1923:    * the array.
1924:    *
1925:    * @param l the List to sort
1926:    * @param c the Comparator specifying the ordering for the elements, or
1927:    *        null for natural ordering
1928:    * @throws ClassCastException if c will not compare some pair of items
1929:    * @throws UnsupportedOperationException if the List is not modifiable
1930:    * @throws NullPointerException if null is compared by natural ordering
1931:    *        (only possible when c is null)
1932:    * @see Arrays#sort(Object[], Comparator)
1933:    */
1934:   public static void sort(List l, Comparator c)
1935:   {
1936:     Object[] a = l.toArray();
1937:     Arrays.sort(a, c);
1938:     ListIterator i = l.listIterator();
1939:     for (int pos = 0, alen = a.length;  pos < alen;  pos++)
1940:       {
1941:         i.next();
1942:         i.set(a[pos]);
1943:       }
1944:   }
1945: 
1946:   /**
1947:    * Swaps the elements at the specified positions within the list. Equal
1948:    * positions have no effect.
1949:    *
1950:    * @param l the list to work on
1951:    * @param i the first index to swap
1952:    * @param j the second index
1953:    * @throws UnsupportedOperationException if list.set is not supported
1954:    * @throws IndexOutOfBoundsException if either i or j is &lt; 0 or &gt;=
1955:    *         list.size()
1956:    * @since 1.4
1957:    */
1958:   public static void swap(List l, int i, int j)
1959:   {
1960:     l.set(i, l.set(j, l.get(i)));
1961:   }
1962: 
1963: 
1964:   /**
1965:    * Returns a synchronized (thread-safe) collection wrapper backed by the
1966:    * given collection. Notice that element access through the iterators
1967:    * is thread-safe, but if the collection can be structurally modified
1968:    * (adding or removing elements) then you should synchronize around the
1969:    * iteration to avoid non-deterministic behavior:<br>
1970:    * <pre>
1971:    * Collection c = Collections.synchronizedCollection(new Collection(...));
1972:    * ...
1973:    * synchronized (c)
1974:    *   {
1975:    *     Iterator i = c.iterator();
1976:    *     while (i.hasNext())
1977:    *       foo(i.next());
1978:    *   }
1979:    * </pre><p>
1980:    *
1981:    * Since the collection might be a List or a Set, and those have incompatible
1982:    * equals and hashCode requirements, this relies on Object's implementation
1983:    * rather than passing those calls on to the wrapped collection. The returned
1984:    * Collection implements Serializable, but can only be serialized if
1985:    * the collection it wraps is likewise Serializable.
1986:    *
1987:    * @param c the collection to wrap
1988:    * @return a synchronized view of the collection
1989:    * @see Serializable
1990:    */
1991:   public static Collection synchronizedCollection(Collection c)
1992:   {
1993:     return new SynchronizedCollection(c);
1994:   }
1995: 
1996:   /**
1997:    * The implementation of {@link #synchronizedCollection(Collection)}. This
1998:    * class name is required for compatibility with Sun's JDK serializability.
1999:    * Package visible, so that collections such as the one for
2000:    * Hashtable.values() can specify which object to synchronize on.
2001:    *
2002:    * @author Eric Blake (ebb9@email.byu.edu)
2003:    */
2004:   static class SynchronizedCollection
2005:     implements Collection, Serializable
2006:   {
2007:     /**
2008:      * Compatible with JDK 1.4.
2009:      */
2010:     private static final long serialVersionUID = 3053995032091335093L;
2011: 
2012:     /**
2013:      * The wrapped collection. Package visible for use by subclasses.
2014:      * @serial the real collection
2015:      */
2016:     final Collection c;
2017: 
2018:     /**
2019:      * The object to synchronize on.  When an instance is created via public
2020:      * methods, it will be this; but other uses like SynchronizedMap.values()
2021:      * must specify another mutex. Package visible for use by subclasses.
2022:      * @serial the lock
2023:      */
2024:     final Object mutex;
2025: 
2026:     /**
2027:      * Wrap a given collection.
2028:      * @param c the collection to wrap
2029:      * @throws NullPointerException if c is null
2030:      */
2031:     SynchronizedCollection(Collection c)
2032:     {
2033:       this.c = c;
2034:       mutex = this;
2035:       if (c == null)
2036:         throw new NullPointerException();
2037:     }
2038: 
2039:     /**
2040:      * Called only by trusted code to specify the mutex as well as the
2041:      * collection.
2042:      * @param sync the mutex
2043:      * @param c the collection
2044:      */
2045:     SynchronizedCollection(Object sync, Collection c)
2046:     {
2047:       this.c = c;
2048:       mutex = sync;
2049:     }
2050: 
2051:     /**
2052:      * Adds the object to the underlying collection, first
2053:      * obtaining a lock on the mutex.
2054:      *
2055:      * @param o The object to add.
2056:      * @return <code>true</code> if the collection was modified as a result
2057:      *         of this action.
2058:      * @throws UnsupportedOperationException if this collection does not
2059:      *         support the add operation.
2060:      * @throws ClassCastException if o cannot be added to this collection due
2061:      *         to its type.
2062:      * @throws NullPointerException if o is null and this collection doesn't
2063:      *         support the addition of null values.
2064:      * @throws IllegalArgumentException if o cannot be added to this
2065:      *         collection for some other reason.
2066:      */
2067:     public boolean add(Object o)
2068:     {
2069:       synchronized (mutex)
2070:         {
2071:           return c.add(o);
2072:         }
2073:     }
2074: 
2075:     /**
2076:      * Adds the objects in col to the underlying collection, first
2077:      * obtaining a lock on the mutex.
2078:      *
2079:      * @param col The collection to take the new objects from.
2080:      * @return <code>true</code> if the collection was modified as a result
2081:      *          of this action.
2082:      * @throws UnsupportedOperationException if this collection does not
2083:      *         support the addAll operation.
2084:      * @throws ClassCastException if some element of col cannot be added to this
2085:      *         collection due to its type.
2086:      * @throws NullPointerException if some element of col is null and this
2087:      *         collection does not support the addition of null values.
2088:      * @throws NullPointerException if col itself is null.
2089:      * @throws IllegalArgumentException if some element of col cannot be added
2090:      *         to this collection for some other reason.
2091:      */
2092:     public boolean addAll(Collection col)
2093:     {
2094:       synchronized (mutex)
2095:         {
2096:           return c.addAll(col);
2097:         }
2098:     }
2099: 
2100:     /**
2101:      * Removes all objects from the underlying collection,
2102:      * first obtaining a lock on the mutex.
2103:      *
2104:      * @throws UnsupportedOperationException if this collection does not
2105:      *         support the clear operation.
2106:      */
2107:     public void clear()
2108:     {
2109:       synchronized (mutex)
2110:         {
2111:           c.clear();
2112:         }
2113:     }
2114: 
2115:     /**
2116:      * Checks for the existence of o within the underlying
2117:      * collection, first obtaining a lock on the mutex.
2118:      *
2119:      * @param o the element to look for.
2120:      * @return <code>true</code> if this collection contains at least one
2121:      *         element e such that <code>o == null ? e == null : o.equals(e)</code>.
2122:      * @throws ClassCastException if the type of o is not a valid type for this
2123:      *         collection.
2124:      * @throws NullPointerException if o is null and this collection doesn't
2125:      *         support null values.
2126:      */
2127:     public boolean contains(Object o)
2128:     {
2129:       synchronized (mutex)
2130:         {
2131:           return c.contains(o);
2132:         }
2133:     }
2134: 
2135:     /**
2136:      * Checks for the existence of each object in cl
2137:      * within the underlying collection, first obtaining
2138:      * a lock on the mutex.
2139:      *
2140:      * @param c1 the collection to test for.
2141:      * @return <code>true</code> if for every element o in c, contains(o)
2142:      *         would return <code>true</code>.
2143:      * @throws ClassCastException if the type of any element in cl is not a valid
2144:      *         type for this collection.
2145:      * @throws NullPointerException if some element of cl is null and this
2146:      *         collection does not support null values.
2147:      * @throws NullPointerException if cl itself is null.
2148:      */
2149:     public boolean containsAll(Collection c1)
2150:     {
2151:       synchronized (mutex)
2152:         {
2153:           return c.containsAll(c1);
2154:         }
2155:     }
2156: 
2157:     /**
2158:      * Returns <code>true</code> if there are no objects in the underlying
2159:      * collection.  A lock on the mutex is obtained before the
2160:      * check is performed.
2161:      *
2162:      * @return <code>true</code> if this collection contains no elements.
2163:      */
2164:     public boolean isEmpty()
2165:     {
2166:       synchronized (mutex)
2167:         {
2168:           return c.isEmpty();
2169:         }
2170:     }
2171: 
2172:     /**
2173:      * Returns a synchronized iterator wrapper around the underlying
2174:      * collection's iterator.  A lock on the mutex is obtained before
2175:      * retrieving the collection's iterator.
2176:      *
2177:      * @return An iterator over the elements in the underlying collection,
2178:      *         which returns each element in any order.
2179:      */
2180:     public Iterator iterator()
2181:     {
2182:       synchronized (mutex)
2183:         {
2184:           return new SynchronizedIterator(mutex, c.iterator());
2185:         }
2186:     }
2187: 
2188:     /**
2189:      * Removes the specified object from the underlying collection,
2190:      * first obtaining a lock on the mutex.
2191:      *
2192:      * @param o The object to remove.
2193:      * @return <code>true</code> if the collection changed as a result of this call, that is,
2194:      *         if the collection contained at least one occurrence of o.
2195:      * @throws UnsupportedOperationException if this collection does not
2196:      *         support the remove operation.
2197:      * @throws ClassCastException if the type of o is not a valid type
2198:      *         for this collection.
2199:      * @throws NullPointerException if o is null and the collection doesn't
2200:      *         support null values.
2201:      */
2202:     public boolean remove(Object o)
2203:     {
2204:       synchronized (mutex)
2205:         {
2206:           return c.remove(o);
2207:         }
2208:     }
2209: 
2210:     /**
2211:      * Removes all elements, e, of the underlying
2212:      * collection for which <code>col.contains(e)</code>
2213:      * returns <code>true</code>.  A lock on the mutex is obtained
2214:      * before the operation proceeds.
2215:      *
2216:      * @param col The collection of objects to be removed.
2217:      * @return <code>true</code> if this collection was modified as a result of this call.
2218:      * @throws UnsupportedOperationException if this collection does not
2219:      *   support the removeAll operation.
2220:      * @throws ClassCastException if the type of any element in c is not a valid
2221:      *   type for this collection.
2222:      * @throws NullPointerException if some element of c is null and this
2223:      *   collection does not support removing null values.
2224:      * @throws NullPointerException if c itself is null.
2225:      */
2226:     public boolean removeAll(Collection col)
2227:     {
2228:       synchronized (mutex)
2229:         {
2230:           return c.removeAll(col);
2231:         }
2232:     }
2233: 
2234:     /**
2235:      * Retains all elements, e, of the underlying
2236:      * collection for which <code>col.contains(e)</code>
2237:      * returns <code>true</code>.  That is, every element that doesn't
2238:      * exist in col is removed.  A lock on the mutex is obtained
2239:      * before the operation proceeds.
2240:      *
2241:      * @param col The collection of objects to be removed.
2242:      * @return <code>true</code> if this collection was modified as a result of this call.
2243:      * @throws UnsupportedOperationException if this collection does not
2244:      *   support the removeAll operation.
2245:      * @throws ClassCastException if the type of any element in c is not a valid
2246:      *   type for this collection.
2247:      * @throws NullPointerException if some element of c is null and this
2248:      *   collection does not support removing null values.
2249:      * @throws NullPointerException if c itself is null.
2250:      */
2251:     public boolean retainAll(Collection col)
2252:     {
2253:       synchronized (mutex)
2254:         {
2255:           return c.retainAll(col);
2256:         }
2257:     }
2258: 
2259:     /**
2260:      * Retrieves the size of the underlying collection.
2261:      * A lock on the mutex is obtained before the collection
2262:      * is accessed.
2263:      *
2264:      * @return The size of the collection.
2265:      */
2266:     public int size()
2267:     {
2268:       synchronized (mutex)
2269:         {
2270:           return c.size();
2271:         }
2272:     }
2273: 
2274:     /**
2275:      * Returns an array containing each object within the underlying
2276:      * collection.  A lock is obtained on the mutex before the collection
2277:      * is accessed.
2278:      *
2279:      * @return An array of objects, matching the collection in size.  The
2280:      *         elements occur in any order.
2281:      */
2282:     public Object[] toArray()
2283:     {
2284:       synchronized (mutex)
2285:         {
2286:           return c.toArray();
2287:         }
2288:     }
2289: 
2290:     /**
2291:      * Copies the elements in the underlying collection to the supplied
2292:      * array.  If <code>a.length < size()</code>, a new array of the
2293:      * same run-time type is created, with a size equal to that of
2294:      * the collection.  If <code>a.length > size()</code>, then the
2295:      * elements from 0 to <code>size() - 1</code> contain the elements
2296:      * from this collection.  The following element is set to null
2297:      * to indicate the end of the collection objects.  However, this
2298:      * only makes a difference if null is not a permitted value within
2299:      * the collection.
2300:      * Before the copying takes place, a lock is obtained on the mutex.
2301:      *
2302:      * @param a An array to copy elements to.
2303:      * @return An array containing the elements of the underlying collection.
2304:      * @throws ArrayStoreException if the type of any element of the
2305:      *         collection is not a subtype of the element type of a.
2306:      */
2307:     public Object[] toArray(Object[] a)
2308:     {
2309:       synchronized (mutex)
2310:         {
2311:           return c.toArray(a);
2312:         }
2313:     }
2314: 
2315:     /**
2316:      * Returns a string representation of the underlying collection.
2317:      * A lock is obtained on the mutex before the string is created.
2318:      *
2319:      * @return A string representation of the collection.
2320:      */
2321:     public String toString()
2322:     {
2323:       synchronized (mutex)
2324:         {
2325:           return c.toString();
2326:         }
2327:     }
2328:   } // class SynchronizedCollection
2329: 
2330:   /**
2331:    * The implementation of the various iterator methods in the
2332:    * synchronized classes. These iterators must "sync" on the same object
2333:    * as the collection they iterate over.
2334:    *
2335:    * @author Eric Blake (ebb9@email.byu.edu)
2336:    */
2337:   private static class SynchronizedIterator implements Iterator
2338:   {
2339:     /**
2340:      * The object to synchronize on. Package visible for use by subclass.
2341:      */
2342:     final Object mutex;
2343: 
2344:     /**
2345:      * The wrapped iterator.
2346:      */
2347:     private final Iterator i;
2348: 
2349:     /**
2350:      * Only trusted code creates a wrapper, with the specified sync.
2351:      * @param sync the mutex
2352:      * @param i the wrapped iterator
2353:      */
2354:     SynchronizedIterator(Object sync, Iterator i)
2355:     {
2356:       this.i = i;
2357:       mutex = sync;
2358:     }
2359: 
2360:     /**
2361:      * Retrieves the next object in the underlying collection.
2362:      * A lock is obtained on the mutex before the collection is accessed.
2363:      * 
2364:      * @return The next object in the collection.
2365:      * @throws NoSuchElementException if there are no more elements
2366:      */
2367:     public Object next()
2368:     {
2369:       synchronized (mutex)
2370:         {
2371:           return i.next();
2372:         }
2373:     }
2374: 
2375:     /**
2376:      * Returns <code>true</code> if objects can still be retrieved from the iterator
2377:      * using <code>next()</code>.  A lock is obtained on the mutex before
2378:      * the collection is accessed.
2379:      *
2380:      * @return <code>true</code> if at least one element is still to be returned by
2381:      *         <code>next()</code>.
2382:      */
2383:     public boolean hasNext()
2384:     {
2385:       synchronized (mutex)
2386:         {
2387:           return i.hasNext();
2388:         }
2389:     }
2390: 
2391:     /**
2392:      * Removes the object that was last returned by <code>next()</code>
2393:      * from the underlying collection.  Only one call to this method is
2394:      * allowed per call to the <code>next()</code> method, and it does
2395:      * not affect the value that will be returned by <code>next()</code>.
2396:      * Thus, if element n was retrieved from the collection by
2397:      * <code>next()</code>, it is this element that gets removed.
2398:      * Regardless of whether this takes place or not, element n+1 is
2399:      * still returned on the subsequent <code>next()</code> call.
2400:      *
2401:      * @throws IllegalStateException if next has not yet been called or remove
2402:      *         has already been called since the last call to next.
2403:      * @throws UnsupportedOperationException if this Iterator does not support
2404:      *         the remove operation.
2405:      */
2406:     public void remove()
2407:     {
2408:       synchronized (mutex)
2409:         {
2410:           i.remove();
2411:         }
2412:     }
2413:   } // class SynchronizedIterator
2414: 
2415:   /**
2416:    * Returns a synchronized (thread-safe) list wrapper backed by the
2417:    * given list. Notice that element access through the iterators
2418:    * is thread-safe, but if the list can be structurally modified
2419:    * (adding or removing elements) then you should synchronize around the
2420:    * iteration to avoid non-deterministic behavior:<br>
2421:    * <pre>
2422:    * List l = Collections.synchronizedList(new List(...));
2423:    * ...
2424:    * synchronized (l)
2425:    *   {
2426:    *     Iterator i = l.iterator();
2427:    *     while (i.hasNext())
2428:    *       foo(i.next());
2429:    *   }
2430:    * </pre><p>
2431:    *
2432:    * The returned List implements Serializable, but can only be serialized if
2433:    * the list it wraps is likewise Serializable. In addition, if the wrapped
2434:    * list implements RandomAccess, this does too.
2435:    *
2436:    * @param l the list to wrap
2437:    * @return a synchronized view of the list
2438:    * @see Serializable
2439:    * @see RandomAccess
2440:    */
2441:   public static List synchronizedList(List l)
2442:   {
2443:     if (l instanceof RandomAccess)
2444:       return new SynchronizedRandomAccessList(l);
2445:     return new SynchronizedList(l);
2446:   }
2447: 
2448:   /**
2449:    * The implementation of {@link #synchronizedList(List)} for sequential
2450:    * lists. This class name is required for compatibility with Sun's JDK
2451:    * serializability. Package visible, so that lists such as Vector.subList()
2452:    * can specify which object to synchronize on.
2453:    *
2454:    * @author Eric Blake (ebb9@email.byu.edu)
2455:    */
2456:   static class SynchronizedList extends SynchronizedCollection
2457:     implements List
2458:   {
2459:     /**
2460:      * Compatible with JDK 1.4.
2461:      */
2462:     private static final long serialVersionUID = -7754090372962971524L;
2463: 
2464:     /**
2465:      * The wrapped list; stored both here and in the superclass to avoid
2466:      * excessive casting. Package visible for use by subclass.
2467:      * @serial the wrapped list
2468:      */
2469:     final List list;
2470: 
2471:     /**
2472:      * Wrap a given list.
2473:      * @param l the list to wrap
2474:      * @throws NullPointerException if l is null
2475:      */
2476:     SynchronizedList(List l)
2477:     {
2478:       super(l);
2479:       list = l;
2480:     }
2481: 
2482:     /**
2483:      * Called only by trusted code to specify the mutex as well as the list.
2484:      * @param sync the mutex
2485:      * @param l the list
2486:      */
2487:     SynchronizedList(Object sync, List l)
2488:     {
2489:       super(sync, l);
2490:       list = l;
2491:     }
2492: 
2493:   /**
2494:    * Insert an element into the underlying list at a given position (optional
2495:    * operation).  This shifts all existing elements from that position to the
2496:    * end one index to the right. This version of add has no return, since it is
2497:    * assumed to always succeed if there is no exception.  Before the
2498:    * addition takes place, a lock is obtained on the mutex.
2499:    *
2500:    * @param index the location to insert the item
2501:    * @param o the object to insert
2502:    * @throws UnsupportedOperationException if this list does not support the
2503:    *         add operation
2504:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
2505:    * @throws ClassCastException if o cannot be added to this list due to its
2506:    *         type
2507:    * @throws IllegalArgumentException if o cannot be added to this list for
2508:    *         some other reason
2509:    * @throws NullPointerException if o is null and this list doesn't support
2510:    *         the addition of null values.
2511:    */
2512:     public void add(int index, Object o)
2513:     {
2514:       synchronized (mutex)
2515:         {
2516:           list.add(index, o);
2517:         }
2518:     }
2519: 
2520:   /**
2521:    * Add the contents of a collection to the underlying list at the given
2522:    * index (optional operation).  If the list imposes restraints on what 
2523:    * can be inserted, such as no null elements, this should be documented.
2524:    * A lock is obtained on the mutex before any of the elements are added.
2525:    *
2526:    * @param index the index at which to insert
2527:    * @param c the collection to add
2528:    * @return <code>true</code>, as defined by Collection for a modified list
2529:    * @throws UnsupportedOperationException if this list does not support the
2530:    *         add operation
2531:    * @throws ClassCastException if o cannot be added to this list due to its
2532:    *         type
2533:    * @throws IllegalArgumentException if o cannot be added to this list for
2534:    *         some other reason
2535:    * @throws NullPointerException if o is null and this list doesn't support
2536:    *         the addition of null values.
2537:    */
2538:     public boolean addAll(int index, Collection c)
2539:     {
2540:       synchronized (mutex)
2541:         {
2542:           return list.addAll(index, c);
2543:         }
2544:     }
2545: 
2546:    /**
2547:     * Tests whether the underlying list is equal to the supplied object.
2548:     * The object is deemed to be equal if it is also a <code>List</code>
2549:     * of equal size and with the same elements (i.e. each element, e1,
2550:     * in list, l1, and each element, e2, in l2, must return <code>true</code> for
2551:     * <code>e1 == null ? e2 == null : e1.equals(e2)</code>.  Before the
2552:     * comparison is made, a lock is obtained on the mutex.
2553:     *
2554:     * @param o The object to test for equality with the underlying list.
2555:     * @return <code>true</code> if o is equal to the underlying list under the above
2556:     *         definition.
2557:     */
2558:     public boolean equals(Object o)
2559:     {
2560:       synchronized (mutex)
2561:         {
2562:           return list.equals(o);
2563:         }
2564:     }
2565: 
2566:     /**
2567:      * Retrieves the object at the specified index.  A lock
2568:      * is obtained on the mutex before the list is accessed.
2569:      *
2570:      * @param index the index of the element to be returned
2571:      * @return the element at index index in this list
2572:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2573:      */
2574:     public Object get(int index)
2575:     {
2576:       synchronized (mutex)
2577:         {
2578:           return list.get(index);
2579:         }
2580:     }
2581: 
2582:     /**
2583:      * Obtains a hashcode for the underlying list, first obtaining
2584:      * a lock on the mutex.  The calculation of the hashcode is
2585:      * detailed in the documentation for the <code>List</code>
2586:      * interface.
2587:      *
2588:      * @return The hashcode of the underlying list.
2589:      * @see List#hashCode()
2590:      */
2591:     public int hashCode()
2592:     {
2593:       synchronized (mutex)
2594:         {
2595:           return list.hashCode();
2596:         }
2597:     }
2598: 
2599:     /**
2600:      * Obtain the first index at which a given object is to be found in the
2601:      * underlying list.  A lock is obtained on the mutex before the list is
2602:      * accessed.
2603:      *
2604:      * @param o the object to search for
2605:      * @return the least integer n such that <code>o == null ? get(n) == null :
2606:      *         o.equals(get(n))</code>, or -1 if there is no such index.
2607:      * @throws ClassCastException if the type of o is not a valid
2608:      *         type for this list.
2609:      * @throws NullPointerException if o is null and this
2610:      *         list does not support null values.
2611:      */
2612: 
2613:     public int indexOf(Object o)
2614:     {
2615:       synchronized (mutex)
2616:         {
2617:           return list.indexOf(o);
2618:         }
2619:     }
2620: 
2621:     /**
2622:      * Obtain the last index at which a given object is to be found in this
2623:      * underlying list.  A lock is obtained on the mutex before the list
2624:      * is accessed.
2625:      *
2626:      * @return the greatest integer n such that <code>o == null ? get(n) == null
2627:      *         : o.equals(get(n))</code>, or -1 if there is no such index.
2628:      * @throws ClassCastException if the type of o is not a valid
2629:      *         type for this list.
2630:      * @throws NullPointerException if o is null and this
2631:      *         list does not support null values.
2632:      */
2633:     public int lastIndexOf(Object o)
2634:     {
2635:       synchronized (mutex)
2636:         {
2637:           return list.lastIndexOf(o);
2638:         }
2639:     }
2640: 
2641:     /**
2642:      * Retrieves a synchronized wrapper around the underlying list's
2643:      * list iterator.  A lock is obtained on the mutex before the
2644:      * list iterator is retrieved.
2645:      *
2646:      * @return A list iterator over the elements in the underlying list.
2647:      *         The list iterator allows additional list-specific operations
2648:      *         to be performed, in addition to those supplied by the
2649:      *         standard iterator.
2650:      */
2651:     public ListIterator listIterator()
2652:     {
2653:       synchronized (mutex)
2654:         {
2655:           return new SynchronizedListIterator(mutex, list.listIterator());
2656:         }
2657:     }
2658: 
2659:     /**
2660:      * Retrieves a synchronized wrapper around the underlying list's
2661:      * list iterator.  A lock is obtained on the mutex before the
2662:      * list iterator is retrieved.  The iterator starts at the
2663:      * index supplied, leading to the element at that index being
2664:      * the first one returned by <code>next()</code>.  Calling
2665:      * <code>previous()</code> from this initial position returns
2666:      * index - 1.
2667:      *
2668:      * @param index the position, between 0 and size() inclusive, to begin the
2669:      *        iteration from
2670:      * @return A list iterator over the elements in the underlying list.
2671:      *         The list iterator allows additional list-specific operations
2672:      *         to be performed, in addition to those supplied by the
2673:      *         standard iterator.
2674:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
2675:      */
2676:     public ListIterator listIterator(int index)
2677:     {
2678:       synchronized (mutex)
2679:         {
2680:           return new SynchronizedListIterator(mutex, list.listIterator(index));
2681:         }
2682:     }
2683: 
2684:     /**
2685:      * Remove the element at a given position in the underlying list (optional
2686:      * operation).  All remaining elements are shifted to the left to fill the gap.
2687:      * A lock on the mutex is obtained before the element is removed.
2688:      *
2689:      * @param index the position within the list of the object to remove
2690:      * @return the object that was removed
2691:      * @throws UnsupportedOperationException if this list does not support the
2692:      *         remove operation
2693:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2694:      */
2695:     public Object remove(int index)
2696:     {
2697:       synchronized (mutex)
2698:         {
2699:           return list.remove(index);
2700:         }
2701:     }
2702: 
2703:   /**
2704:    * Replace an element of the underlying list with another object (optional
2705:    * operation).  A lock is obtained on the mutex before the element is
2706:    * replaced.
2707:    *
2708:    * @param index the position within this list of the element to be replaced
2709:    * @param o the object to replace it with
2710:    * @return the object that was replaced
2711:    * @throws UnsupportedOperationException if this list does not support the
2712:    *         set operation.
2713:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2714:    * @throws ClassCastException if o cannot be added to this list due to its
2715:    *         type
2716:    * @throws IllegalArgumentException if o cannot be added to this list for
2717:    *         some other reason
2718:    * @throws NullPointerException if o is null and this
2719:    *         list does not support null values.
2720:    */
2721:     public Object set(int index, Object o)
2722:     {
2723:       synchronized (mutex)
2724:         {
2725:           return list.set(index, o);
2726:         }
2727:     }
2728: 
2729:     /**
2730:      * Obtain a List view of a subsection of the underlying list, from fromIndex
2731:      * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2732:      * sublist is empty. The returned list should be modifiable if and only
2733:      * if this list is modifiable. Changes to the returned list should be
2734:      * reflected in this list. If this list is structurally modified in
2735:      * any way other than through the returned list, the result of any subsequent
2736:      * operations on the returned list is undefined.  A lock is obtained
2737:      * on the mutex before the creation of the sublist.  The returned list
2738:      * is also synchronized, using the same mutex.
2739:      *
2740:      * @param fromIndex the index that the returned list should start from
2741:      *        (inclusive)
2742:      * @param toIndex the index that the returned list should go to (exclusive)
2743:      * @return a List backed by a subsection of this list
2744:      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
2745:      *         || toIndex &gt; size() || fromIndex &gt; toIndex
2746:      */
2747:     public List subList(int fromIndex, int toIndex)
2748:     {
2749:       synchronized (mutex)
2750:         {
2751:           return new SynchronizedList(mutex, list.subList(fromIndex, toIndex));
2752:         }
2753:     }
2754:   } // class SynchronizedList
2755: 
2756:   /**
2757:    * The implementation of {@link #synchronizedList(List)} for random-access
2758:    * lists. This class name is required for compatibility with Sun's JDK
2759:    * serializability.
2760:    *
2761:    * @author Eric Blake (ebb9@email.byu.edu)
2762:    */
2763:   private static final class SynchronizedRandomAccessList
2764:     extends SynchronizedList implements RandomAccess
2765:   {
2766:     /**
2767:      * Compatible with JDK 1.4.
2768:      */
2769:     private static final long serialVersionUID = 1530674583602358482L;
2770: 
2771:     /**
2772:      * Wrap a given list.
2773:      * @param l the list to wrap
2774:      * @throws NullPointerException if l is null
2775:      */
2776:     SynchronizedRandomAccessList(List l)
2777:     {
2778:       super(l);
2779:     }
2780: 
2781:     /**
2782:      * Called only by trusted code to specify the mutex as well as the
2783:      * collection.
2784:      * @param sync the mutex
2785:      * @param l the list
2786:      */
2787:     SynchronizedRandomAccessList(Object sync, List l)
2788:     {
2789:       super(sync, l);
2790:     }
2791: 
2792:     /**
2793:      * Obtain a List view of a subsection of the underlying list, from fromIndex
2794:      * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2795:      * sublist is empty. The returned list should be modifiable if and only
2796:      * if this list is modifiable. Changes to the returned list should be
2797:      * reflected in this list. If this list is structurally modified in
2798:      * any way other than through the returned list, the result of any subsequent
2799:      * operations on the returned list is undefined.    A lock is obtained
2800:      * on the mutex before the creation of the sublist.  The returned list
2801:      * is also synchronized, using the same mutex.  Random accessibility
2802:      * is also extended to the new list.
2803:      *
2804:      * @param fromIndex the index that the returned list should start from
2805:      *        (inclusive)
2806:      * @param toIndex the index that the returned list should go to (exclusive)
2807:      * @return a List backed by a subsection of this list
2808:      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
2809:      *         || toIndex &gt; size() || fromIndex &gt; toIndex
2810:      */
2811:     public List subList(int fromIndex, int toIndex)
2812:     {
2813:       synchronized (mutex)
2814:         {
2815:           return new SynchronizedRandomAccessList(mutex,
2816:                                                   list.subList(fromIndex,
2817:                                                                toIndex));
2818:         }
2819:     }
2820:   } // class SynchronizedRandomAccessList
2821: 
2822:   /**
2823:    * The implementation of {@link SynchronizedList#listIterator()}. This
2824:    * iterator must "sync" on the same object as the list it iterates over.
2825:    *
2826:    * @author Eric Blake (ebb9@email.byu.edu)
2827:    */
2828:   private static final class SynchronizedListIterator
2829:     extends SynchronizedIterator implements ListIterator
2830:   {
2831:     /**
2832:      * The wrapped iterator, stored both here and in the superclass to
2833:      * avoid excessive casting.
2834:      */
2835:     private final ListIterator li;
2836: 
2837:     /**
2838:      * Only trusted code creates a wrapper, with the specified sync.
2839:      * @param sync the mutex
2840:      * @param li the wrapped iterator
2841:      */
2842:     SynchronizedListIterator(Object sync, ListIterator li)
2843:     {
2844:       super(sync, li);
2845:       this.li = li;
2846:     }
2847: 
2848:     /**
2849:      * Insert an element into the underlying list at the current position of
2850:      * the iterator (optional operation). The element is inserted in between
2851:      * the element that would be returned by <code>previous()</code> and the
2852:      * element that would be returned by <code>next()</code>. After the
2853:      * insertion, a subsequent call to next is unaffected, but
2854:      * a call to previous returns the item that was added. The values returned
2855:      * by nextIndex() and previousIndex() are incremented.  A lock is obtained
2856:      * on the mutex before the addition takes place.
2857:      *
2858:      * @param o the object to insert into the list
2859:      * @throws ClassCastException if the object is of a type which cannot be added
2860:      *         to this list.
2861:      * @throws IllegalArgumentException if some other aspect of the object stops
2862:      *         it being added to this list.
2863:      * @throws UnsupportedOperationException if this ListIterator does not
2864:      *         support the add operation.
2865:      */
2866:     public void add(Object o)
2867:     {
2868:       synchronized (mutex)
2869:         {
2870:           li.add(o);
2871:         }
2872:     }
2873: 
2874:     /**
2875:      * Tests whether there are elements remaining in the underlying list
2876:      * in the reverse direction. In other words, <code>previous()</code>
2877:      * will not fail with a NoSuchElementException.  A lock is obtained
2878:      * on the mutex before the check takes place.
2879:      *
2880:      * @return <code>true</code> if the list continues in the reverse direction
2881:      */
2882:     public boolean hasPrevious()
2883:     {
2884:       synchronized (mutex)
2885:         {
2886:           return li.hasPrevious();
2887:         }
2888:     }
2889: 
2890:     /**
2891:       * Find the index of the element that would be returned by a call to
2892:       * <code>next()</code>.  If hasNext() returns <code>false</code>, this
2893:       * returns the list size.  A lock is obtained on the mutex before the
2894:       * query takes place.
2895:       *
2896:       * @return the index of the element that would be returned by next()
2897:       */
2898:     public int nextIndex()
2899:     {
2900:       synchronized (mutex)
2901:         {
2902:           return li.nextIndex();
2903:         }
2904:     }
2905: 
2906:     /**
2907:      * Obtain the previous element from the underlying list. Repeated
2908:      * calls to previous may be used to iterate backwards over the entire list,
2909:      * or calls to next and previous may be used together to go forwards and
2910:      * backwards. Alternating calls to next and previous will return the same
2911:      * element.  A lock is obtained on the mutex before the object is retrieved.
2912:      *
2913:      * @return the next element in the list in the reverse direction
2914:      * @throws NoSuchElementException if there are no more elements
2915:      */
2916:     public Object previous()
2917:     {
2918:       synchronized (mutex)
2919:         {
2920:           return li.previous();
2921:         }
2922:     }
2923: 
2924:     /**
2925:      * Find the index of the element that would be returned by a call to
2926:      * previous. If hasPrevious() returns <code>false</code>, this returns -1.
2927:      * A lock is obtained on the mutex before the query takes place.
2928:      *
2929:      * @return the index of the element that would be returned by previous()
2930:      */
2931:     public int previousIndex()
2932:     {
2933:       synchronized (mutex)
2934:         {
2935:           return li.previousIndex();
2936:         }
2937:     }
2938: 
2939:     /**
2940:      * Replace the element last returned by a call to <code>next()</code> or
2941:      * <code>previous()</code> with a given object (optional operation).  This
2942:      * method may only be called if neither <code>add()</code> nor
2943:      * <code>remove()</code> have been called since the last call to
2944:      * <code>next()</code> or <code>previous</code>.  A lock is obtained
2945:      * on the mutex before the list is modified.
2946:      *
2947:      * @param o the object to replace the element with
2948:      * @throws ClassCastException the object is of a type which cannot be added
2949:      *         to this list
2950:      * @throws IllegalArgumentException some other aspect of the object stops
2951:      *         it being added to this list
2952:      * @throws IllegalStateException if neither next or previous have been
2953:      *         called, or if add or remove has been called since the last call
2954:      *         to next or previous
2955:      * @throws UnsupportedOperationException if this ListIterator does not
2956:      *         support the set operation
2957:      */
2958:     public void set(Object o)
2959:     {
2960:       synchronized (mutex)
2961:         {
2962:           li.set(o);
2963:         }
2964:     }
2965:   } // class SynchronizedListIterator
2966: 
2967:   /**
2968:    * Returns a synchronized (thread-safe) map wrapper backed by the given
2969:    * map. Notice that element access through the collection views and their
2970:    * iterators are thread-safe, but if the map can be structurally modified
2971:    * (adding or removing elements) then you should synchronize around the
2972:    * iteration to avoid non-deterministic behavior:<br>
2973:    * <pre>
2974:    * Map m = Collections.synchronizedMap(new Map(...));
2975:    * ...
2976:    * Set s = m.keySet(); // safe outside a synchronized block
2977:    * synchronized (m) // synch on m, not s
2978:    *   {
2979:    *     Iterator i = s.iterator();
2980:    *     while (i.hasNext())
2981:    *       foo(i.next());
2982:    *   }
2983:    * </pre><p>
2984:    *
2985:    * The returned Map implements Serializable, but can only be serialized if
2986:    * the map it wraps is likewise Serializable.
2987:    *
2988:    * @param m the map to wrap
2989:    * @return a synchronized view of the map
2990:    * @see Serializable
2991:    */
2992:   public static Map synchronizedMap(Map m)
2993:   {
2994:     return new SynchronizedMap(m);
2995:   }
2996: 
2997:   /**
2998:    * The implementation of {@link #synchronizedMap(Map)}. This
2999:    * class name is required for compatibility with Sun's JDK serializability.
3000:    *
3001:    * @author Eric Blake (ebb9@email.byu.edu)
3002:    */
3003:   private static class SynchronizedMap implements Map, Serializable
3004:   {
3005:     /**
3006:      * Compatible with JDK 1.4.
3007:      */
3008:     private static final long serialVersionUID = 1978198479659022715L;
3009: 
3010:     /**
3011:      * The wrapped map.
3012:      * @serial the real map
3013:      */
3014:     private final Map m;
3015: 
3016:     /**
3017:      * The object to synchronize on.  When an instance is created via public
3018:      * methods, it will be this; but other uses like
3019:      * SynchronizedSortedMap.subMap() must specify another mutex. Package
3020:      * visible for use by subclass.
3021:      * @serial the lock
3022:      */
3023:     final Object mutex;
3024: 
3025:     /**
3026:      * Cache the entry set.
3027:      */
3028:     private transient Set entries;
3029: 
3030:     /**
3031:      * Cache the key set.
3032:      */
3033:     private transient Set keys;
3034: 
3035:     /**
3036:      * Cache the value collection.
3037:      */
3038:     private transient Collection values;
3039: 
3040:     /**
3041:      * Wrap a given map.
3042:      * @param m the map to wrap
3043:      * @throws NullPointerException if m is null
3044:      */
3045:     SynchronizedMap(Map m)
3046:     {
3047:       this.m = m;
3048:       mutex = this;
3049:       if (m == null)
3050:         throw new NullPointerException();
3051:     }
3052: 
3053:     /**
3054:      * Called only by trusted code to specify the mutex as well as the map.
3055:      * @param sync the mutex
3056:      * @param m the map
3057:      */
3058:     SynchronizedMap(Object sync, Map m)
3059:     {
3060:       this.m = m;
3061:       mutex = sync;
3062:     }
3063: 
3064:     /**
3065:      * Clears all the entries from the underlying map.  A lock is obtained
3066:      * on the mutex before the map is cleared.
3067:      *
3068:      * @throws UnsupportedOperationException if clear is not supported
3069:      */
3070:     public void clear()
3071:     {
3072:       synchronized (mutex)
3073:         {
3074:           m.clear();
3075:         }
3076:     }
3077: 
3078:     /**
3079:      * Returns <code>true</code> if the underlying map contains a entry for the given key.
3080:      * A lock is obtained on the mutex before the map is queried.
3081:      *
3082:      * @param key the key to search for.
3083:      * @return <code>true</code> if the underlying map contains the key.
3084:      * @throws ClassCastException if the key is of an inappropriate type.
3085:      * @throws NullPointerException if key is <code>null</code> but the map
3086:      *         does not permit null keys.
3087:      */
3088:     public boolean containsKey(Object key)
3089:     {
3090:       synchronized (mutex)
3091:         {
3092:           return m.containsKey(key);
3093:         }
3094:     }
3095: 
3096:   /**
3097:    * Returns <code>true</code> if the underlying map contains at least one entry with the
3098:    * given value.  In other words, returns <code>true</code> if a value v exists where
3099:    * <code>(value == null ? v == null : value.equals(v))</code>. This usually
3100:    * requires linear time.  A lock is obtained on the mutex before the map
3101:    * is queried.
3102:    *
3103:    * @param value the value to search for
3104:    * @return <code>true</code> if the map contains the value
3105:    * @throws ClassCastException if the type of the value is not a valid type
3106:    *         for this map.
3107:    * @throws NullPointerException if the value is null and the map doesn't
3108:    *         support null values.
3109:    */
3110:     public boolean containsValue(Object value)
3111:     {
3112:       synchronized (mutex)
3113:         {
3114:           return m.containsValue(value);
3115:         }
3116:     }
3117: 
3118:     // This is one of the ickiest cases of nesting I've ever seen. It just
3119:     // means "return a SynchronizedSet, except that the iterator() method
3120:     // returns an SynchronizedIterator whose next() method returns a
3121:     // synchronized wrapper around its normal return value".
3122:     public Set entrySet()
3123:     {
3124:       // Define this here to spare some nesting.
3125:       class SynchronizedMapEntry implements Map.Entry
3126:       {
3127:         final Map.Entry e;
3128:         SynchronizedMapEntry(Object o)
3129:         {
3130:           e = (Map.Entry) o;
3131:         }
3132: 
3133:     /**
3134:      * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code>
3135:      * with the same key and value as the underlying entry.  A lock is
3136:      * obtained on the mutex before the comparison takes place.
3137:      *
3138:      * @param o The object to compare with this entry.
3139:      * @return <code>true</code> if o is equivalent to the underlying map entry.
3140:      */
3141:         public boolean equals(Object o)
3142:         {
3143:           synchronized (mutex)
3144:             {
3145:               return e.equals(o);
3146:             }
3147:         }
3148: 
3149:     /**
3150:      * Returns the key used in the underlying map entry.  A lock is obtained
3151:      * on the mutex before the key is retrieved.
3152:      *
3153:      * @return The key of the underlying map entry.
3154:      */
3155:         public Object getKey()
3156:         {
3157:           synchronized (mutex)
3158:             {
3159:               return e.getKey();
3160:             }
3161:         }
3162: 
3163:     /**
3164:      * Returns the value used in the underlying map entry.  A lock is obtained
3165:      * on the mutex before the value is retrieved.
3166:      *
3167:      * @return The value of the underlying map entry.
3168:      */
3169:         public Object getValue()
3170:         {
3171:           synchronized (mutex)
3172:             {
3173:               return e.getValue();
3174:             }
3175:         }
3176: 
3177:     /**
3178:      * Computes the hash code for the underlying map entry.
3179:      * This computation is described in the documentation for the
3180:      * <code>Map</code> interface.  A lock is obtained on the mutex
3181:      * before the underlying map is accessed.
3182:      *
3183:      * @return The hash code of the underlying map entry.
3184:      * @see Map#hashCode()
3185:      */
3186:         public int hashCode()
3187:         {
3188:           synchronized (mutex)
3189:             {
3190:               return e.hashCode();
3191:             }
3192:         }
3193: 
3194:     /**
3195:      * Replaces the value in the underlying map entry with the specified
3196:      * object (optional operation).  A lock is obtained on the mutex
3197:      * before the map is altered.  The map entry, in turn, will alter
3198:      * the underlying map object.  The operation is undefined if the
3199:      * <code>remove()</code> method of the iterator has been called
3200:      * beforehand.
3201:      *
3202:      * @param value the new value to store
3203:      * @return the old value
3204:      * @throws UnsupportedOperationException if the operation is not supported.
3205:      * @throws ClassCastException if the value is of the wrong type.
3206:      * @throws IllegalArgumentException if something about the value
3207:      *         prevents it from existing in this map.
3208:      * @throws NullPointerException if the map forbids null values.
3209:      */
3210:         public Object setValue(Object value)
3211:         {
3212:           synchronized (mutex)
3213:             {
3214:               return e.setValue(value);
3215:             }
3216:         }
3217: 
3218:     /**
3219:      * Returns a textual representation of the underlying map entry.
3220:      * A lock is obtained on the mutex before the entry is accessed.
3221:      *
3222:      * @return The contents of the map entry in <code>String</code> form.
3223:      */
3224:         public String toString()
3225:         {
3226:           synchronized (mutex)
3227:             {
3228:               return e.toString();
3229:             }
3230:         }
3231:       } // class SynchronizedMapEntry
3232: 
3233:       // Now the actual code.
3234:       if (entries == null)
3235:         synchronized (mutex)
3236:           {
3237:             entries = new SynchronizedSet(mutex, m.entrySet())
3238:             {
3239:           /**
3240:            * Returns an iterator over the set.  The iterator has no specific order,
3241:            * unless further specified.  A lock is obtained on the set's mutex
3242:            * before the iterator is created.  The created iterator is also
3243:            * thread-safe.
3244:            *
3245:            * @return A synchronized set iterator.
3246:            */
3247:           public Iterator iterator()
3248:               {
3249:                 synchronized (super.mutex)
3250:                   {
3251:                     return new SynchronizedIterator(super.mutex, c.iterator())
3252:                     {
3253:               /**
3254:                * Retrieves the next map entry from the iterator.
3255:                * A lock is obtained on the iterator's mutex before
3256:                * the entry is created.  The new map entry is enclosed in
3257:                * a thread-safe wrapper.
3258:                *
3259:                * @return A synchronized map entry.
3260:                */
3261:                       public Object next()
3262:                       {
3263:                         synchronized (super.mutex)
3264:                           {
3265:                             return new SynchronizedMapEntry(super.next());
3266:                           }
3267:                       }
3268:                     };
3269:                   }
3270:               }
3271:             };
3272:           }
3273:       return entries;
3274:     }
3275: 
3276:     /**
3277:      * Returns <code>true</code> if the object, o, is also an instance
3278:      * of <code>Map</code> and contains an equivalent
3279:      * entry set to that of the underlying map.  A lock
3280:      * is obtained on the mutex before the objects are
3281:      * compared.
3282:      *
3283:      * @param o The object to compare.
3284:      * @return <code>true</code> if o and the underlying map are equivalent.
3285:      */
3286:     public boolean equals(Object o)
3287:     {
3288:       synchronized (mutex)
3289:         {
3290:           return m.equals(o);
3291:         }
3292:     }
3293: 
3294:     /**
3295:      * Returns the value associated with the given key, or null
3296:      * if no such mapping exists.  An ambiguity exists with maps
3297:      * that accept null values as a return value of null could
3298:      * be due to a non-existent mapping or simply a null value
3299:      * for that key.  To resolve this, <code>containsKey</code>
3300:      * should be used.  A lock is obtained on the mutex before
3301:      * the value is retrieved from the underlying map.
3302:      *
3303:      * @param key The key of the required mapping.
3304:      * @return The value associated with the given key, or
3305:      *         null if no such mapping exists.
3306:      * @throws ClassCastException if the key is an inappropriate type.
3307:      * @throws NullPointerException if this map does not accept null keys.
3308:      */
3309:     public Object get(Object key)
3310:     {
3311:       synchronized (mutex)
3312:         {
3313:           return m.get(key);
3314:         }
3315:     }
3316: 
3317:     /**
3318:      * Calculates the hash code of the underlying map as the
3319:      * sum of the hash codes of all entries.  A lock is obtained
3320:      * on the mutex before the hash code is computed.
3321:      *
3322:      * @return The hash code of the underlying map.
3323:      */
3324:     public int hashCode()
3325:     {
3326:       synchronized (mutex)
3327:         {
3328:           return m.hashCode();
3329:         }
3330:     }
3331: 
3332:     /**
3333:      * Returns <code>true</code> if the underlying map contains no entries.
3334:      * A lock is obtained on the mutex before the map is examined.
3335:      *
3336:      * @return <code>true</code> if the map is empty.
3337:      */
3338:     public boolean isEmpty()
3339:     {
3340:       synchronized (mutex)
3341:         {
3342:           return m.isEmpty();
3343:         }
3344:     }
3345: 
3346:     /**
3347:      * Returns a thread-safe set view of the keys in the underlying map.  The
3348:      * set is backed by the map, so that changes in one show up in the other.
3349:      * Modifications made while an iterator is in progress cause undefined
3350:      * behavior.  If the set supports removal, these methods remove the
3351:      * underlying mapping from the map: <code>Iterator.remove</code>,
3352:      * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
3353:      * and <code>clear</code>.  Element addition, via <code>add</code> or
3354:      * <code>addAll</code>, is not supported via this set.  A lock is obtained
3355:      * on the mutex before the set is created.
3356:      *
3357:      * @return A synchronized set containing the keys of the underlying map.
3358:      */
3359:     public Set keySet()
3360:     {
3361:       if (keys == null)
3362:         synchronized (mutex)
3363:           {
3364:             keys = new SynchronizedSet(mutex, m.keySet());
3365:           }
3366:       return keys;
3367:     }
3368: 
3369:     /**
3370:      * Associates the given key to the given value (optional operation). If the
3371:      * underlying map already contains the key, its value is replaced. Be aware
3372:      * that in a map that permits <code>null</code> values, a null return does not
3373:      * always imply that the mapping was created.  A lock is obtained on the mutex
3374:      * before the modification is made.
3375:      *
3376:      * @param key the key to map.
3377:      * @param value the value to be mapped.
3378:      * @return the previous value of the key, or null if there was no mapping
3379:      * @throws UnsupportedOperationException if the operation is not supported
3380:      * @throws ClassCastException if the key or value is of the wrong type
3381:      * @throws IllegalArgumentException if something about this key or value
3382:      *         prevents it from existing in this map
3383:      * @throws NullPointerException if either the key or the value is null,
3384:      *         and the map forbids null keys or values
3385:      * @see #containsKey(Object)
3386:      */
3387:     public Object put(Object key, Object value)
3388:     {
3389:       synchronized (mutex)
3390:         {
3391:           return m.put(key, value);
3392:         }
3393:     }
3394: 
3395:     /**
3396:      * Copies all entries of the given map to the underlying one (optional
3397:      * operation). If the map already contains a key, its value is replaced.
3398:      * A lock is obtained on the mutex before the operation proceeds.
3399:      *
3400:      * @param map the mapping to load into this map
3401:      * @throws UnsupportedOperationException if the operation is not supported
3402:      * @throws ClassCastException if a key or value is of the wrong type
3403:      * @throws IllegalArgumentException if something about a key or value
3404:      *         prevents it from existing in this map
3405:      * @throws NullPointerException if the map forbids null keys or values, or
3406:      *         if <code>m</code> is null.
3407:      * @see #put(Object, Object)
3408:      */
3409:     public void putAll(Map map)
3410:     {
3411:       synchronized (mutex)
3412:         {
3413:           m.putAll(map);
3414:         }
3415:     }
3416: 
3417:     /**
3418:      * Removes the mapping for the key, o, if present (optional operation). If
3419:      * the key is not present, this returns null. Note that maps which permit
3420:      * null values may also return null if the key was removed.  A prior
3421:      * <code>containsKey()</code> check is required to avoid this ambiguity.
3422:      * Before the mapping is removed, a lock is obtained on the mutex.
3423:      *
3424:      * @param o the key to remove
3425:      * @return the value the key mapped to, or null if not present
3426:      * @throws UnsupportedOperationException if deletion is unsupported
3427:      * @throws NullPointerException if the key is null and this map doesn't
3428:      *         support null keys.
3429:      * @throws ClassCastException if the type of the key is not a valid type
3430:      *         for this map.
3431:      */
3432:     public Object remove(Object o)
3433:     {
3434:       synchronized (mutex)
3435:         {
3436:           return m.remove(o);
3437:         }
3438:     }
3439: 
3440:     /**
3441:      * Retrieves the size of the underlying map.  A lock
3442:      * is obtained on the mutex before access takes place.
3443:      * Maps with a size greater than <code>Integer.MAX_VALUE</code>
3444:      * return <code>Integer.MAX_VALUE</code> instead.
3445:      *
3446:      * @return The size of the underlying map.
3447:      */
3448:     public int size()
3449:     {
3450:       synchronized (mutex)
3451:         {
3452:           return m.size();
3453:         }
3454:     }
3455: 
3456:     /**
3457:      * Returns a textual representation of the underlying
3458:      * map.  A lock is obtained on the mutex before the map
3459:      * is accessed.
3460:      *
3461:      * @return The map in <code>String</code> form.
3462:      */
3463:     public String toString()
3464:     {
3465:       synchronized (mutex)
3466:         {
3467:           return m.toString();
3468:         }
3469:     }
3470: 
3471:     /**
3472:      * Returns a synchronized collection view of the values in the underlying
3473:      * map.  The collection is backed by the map, so that changes in one show up in
3474:      * the other.  Modifications made while an iterator is in progress cause
3475:      * undefined behavior.  If the collection supports removal, these methods
3476:      * remove the underlying mapping from the map: <code>Iterator.remove</code>,
3477:      * <code>Collection.remove</code>, <code>removeAll</code>,
3478:      * <code>retainAll</code>, and <code>clear</code>. Element addition, via
3479:      * <code>add</code> or <code>addAll</code>, is not supported via this
3480:      * collection.  A lock is obtained on the mutex before the collection
3481:      * is created.
3482:      * 
3483:      * @return the collection of all values in the underlying map.
3484:      */
3485:     public Collection values()
3486:     {
3487:       if (values == null)
3488:         synchronized (mutex)
3489:           {
3490:             values = new SynchronizedCollection(mutex, m.values());
3491:           }
3492:       return values;
3493:     }
3494:   } // class SynchronizedMap
3495: 
3496:   /**
3497:    * Returns a synchronized (thread-safe) set wrapper backed by the given
3498:    * set. Notice that element access through the iterator is thread-safe, but
3499:    * if the set can be structurally modified (adding or removing elements)
3500:    * then you should synchronize around the iteration to avoid
3501:    * non-deterministic behavior:<br>
3502:    * <pre>
3503:    * Set s = Collections.synchronizedSet(new Set(...));
3504:    * ...
3505:    * synchronized (s)
3506:    *   {
3507:    *     Iterator i = s.iterator();
3508:    *     while (i.hasNext())
3509:    *       foo(i.next());
3510:    *   }
3511:    * </pre><p>
3512:    *
3513:    * The returned Set implements Serializable, but can only be serialized if
3514:    * the set it wraps is likewise Serializable.
3515:    *
3516:    * @param s the set to wrap
3517:    * @return a synchronized view of the set
3518:    * @see Serializable
3519:    */
3520:   public static Set synchronizedSet(Set s)
3521:   {
3522:     return new SynchronizedSet(s);
3523:   }
3524: 
3525:   /**
3526:    * The implementation of {@link #synchronizedSet(Set)}. This class
3527:    * name is required for compatibility with Sun's JDK serializability.
3528:    * Package visible, so that sets such as Hashtable.keySet()
3529:    * can specify which object to synchronize on.
3530:    *
3531:    * @author Eric Blake (ebb9@email.byu.edu)
3532:    */
3533:   static class SynchronizedSet extends SynchronizedCollection
3534:     implements Set
3535:   {
3536:     /**
3537:      * Compatible with JDK 1.4.
3538:      */
3539:     private static final long serialVersionUID = 487447009682186044L;
3540: 
3541:     /**
3542:      * Wrap a given set.
3543:      * @param s the set to wrap
3544:      * @throws NullPointerException if s is null
3545:      */
3546:     SynchronizedSet(Set s)
3547:     {
3548:       super(s);
3549:     }
3550: 
3551:     /**
3552:      * Called only by trusted code to specify the mutex as well as the set.
3553:      * @param sync the mutex
3554:      * @param s the set
3555:      */
3556:     SynchronizedSet(Object sync, Set s)
3557:     {
3558:       super(sync, s);
3559:     }
3560: 
3561:     /**
3562:      * Returns <code>true</code> if the object, o, is a <code>Set</code>
3563:      * of the same size as the underlying set, and contains
3564:      * each element, e, which occurs in the underlying set.
3565:      * A lock is obtained on the mutex before the comparison
3566:      * takes place.
3567:      *
3568:      * @param o The object to compare against.
3569:      * @return <code>true</code> if o is an equivalent set.
3570:      */
3571:     public boolean equals(Object o)
3572:     {
3573:       synchronized (mutex)
3574:         {
3575:           return c.equals(o);
3576:         }
3577:     }
3578: 
3579:     /**
3580:      * Computes the hash code for the underlying set as the
3581:      * sum of the hash code of all elements within the set.
3582:      * A lock is obtained on the mutex before the computation
3583:      * occurs.
3584:      *
3585:      * @return The hash code for the underlying set.
3586:      */
3587:     public int hashCode()
3588:     {
3589:       synchronized (mutex)
3590:         {
3591:           return c.hashCode();
3592:         }
3593:     }
3594:   } // class SynchronizedSet
3595: 
3596:   /**
3597:    * Returns a synchronized (thread-safe) sorted map wrapper backed by the
3598:    * given map. Notice that element access through the collection views,
3599:    * subviews, and their iterators are thread-safe, but if the map can be
3600:    * structurally modified (adding or removing elements) then you should
3601:    * synchronize around the iteration to avoid non-deterministic behavior:<br>
3602:    * <pre>
3603:    * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
3604:    * ...
3605:    * Set s = m.keySet(); // safe outside a synchronized block
3606:    * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
3607:    * Set s2 = m2.keySet(); // safe outside a synchronized block
3608:    * synchronized (m) // synch on m, not m2, s or s2
3609:    *   {
3610:    *     Iterator i = s.iterator();
3611:    *     while (i.hasNext())
3612:    *       foo(i.next());
3613:    *     i = s2.iterator();
3614:    *     while (i.hasNext())
3615:    *       bar(i.next());
3616:    *   }
3617:    * </pre><p>
3618:    *
3619:    * The returned SortedMap implements Serializable, but can only be
3620:    * serialized if the map it wraps is likewise Serializable.
3621:    *
3622:    * @param m the sorted map to wrap
3623:    * @return a synchronized view of the sorted map
3624:    * @see Serializable
3625:    */
3626:   public static SortedMap synchronizedSortedMap(SortedMap m)
3627:   {
3628:     return new SynchronizedSortedMap(m);
3629:   }
3630: 
3631:   /**
3632:    * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
3633:    * class name is required for compatibility with Sun's JDK serializability.
3634:    *
3635:    * @author Eric Blake (ebb9@email.byu.edu)
3636:    */
3637:   private static final class SynchronizedSortedMap extends SynchronizedMap
3638:     implements SortedMap
3639:   {
3640:     /**
3641:      * Compatible with JDK 1.4.
3642:      */
3643:     private static final long serialVersionUID = -8798146769416483793L;
3644: 
3645:     /**
3646:      * The wrapped map; stored both here and in the superclass to avoid
3647:      * excessive casting.
3648:      * @serial the wrapped map
3649:      */
3650:     private final SortedMap sm;
3651: 
3652:     /**
3653:      * Wrap a given map.
3654:      * @param sm the map to wrap
3655:      * @throws NullPointerException if sm is null
3656:      */
3657:     SynchronizedSortedMap(SortedMap sm)
3658:     {
3659:       super(sm);
3660:       this.sm = sm;
3661:     }
3662: 
3663:     /**
3664:      * Called only by trusted code to specify the mutex as well as the map.
3665:      * @param sync the mutex
3666:      * @param sm the map
3667:      */
3668:     SynchronizedSortedMap(Object sync, SortedMap sm)
3669:     {
3670:       super(sync, sm);
3671:       this.sm = sm;
3672:     }
3673: 
3674:     /**
3675:      * Returns the comparator used in sorting the underlying map, or null if
3676:      * it is the keys' natural ordering.  A lock is obtained on the mutex
3677:      * before the comparator is retrieved.
3678:      *
3679:      * @return the sorting comparator.
3680:      */
3681:     public Comparator comparator()
3682:     {
3683:       synchronized (mutex)
3684:         {
3685:           return sm.comparator();
3686:         }
3687:     }
3688: 
3689:     /**
3690:      * Returns the first, lowest sorted, key from the underlying map.
3691:      * A lock is obtained on the mutex before the map is accessed.
3692:      *
3693:      * @return the first key.
3694:      * @throws NoSuchElementException if this map is empty.
3695:      */
3696:     public Object firstKey()
3697:     {
3698:       synchronized (mutex)
3699:         {
3700:           return sm.firstKey();
3701:         }
3702:     }
3703: 
3704:     /**
3705:      * Returns a submap containing the keys from the first
3706:      * key (as returned by <code>firstKey()</code>) to
3707:      * the key before that specified.  The submap supports all
3708:      * operations supported by the underlying map and all actions
3709:      * taking place on the submap are also reflected in the underlying
3710:      * map.  A lock is obtained on the mutex prior to submap creation.
3711:      * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>.
3712:      * The submap retains the thread-safe status of this map.
3713:      *
3714:      * @param toKey the exclusive upper range of the submap.
3715:      * @return a submap from <code>firstKey()</code> to the
3716:      *         the key preceding toKey.
3717:      * @throws ClassCastException if toKey is not comparable to the underlying
3718:      *         map's contents.
3719:      * @throws IllegalArgumentException if toKey is outside the map's range.
3720:      * @throws NullPointerException if toKey is null. but the map does not allow
3721:      *         null keys.
3722:      */
3723:     public SortedMap headMap(Object toKey)
3724:     {
3725:       synchronized (mutex)
3726:         {
3727:           return new SynchronizedSortedMap(mutex, sm.headMap(toKey));
3728:         }
3729:     }
3730: 
3731:     /**
3732:      * Returns the last, highest sorted, key from the underlying map.
3733:      * A lock is obtained on the mutex before the map is accessed.
3734:      *
3735:      * @return the last key.
3736:      * @throws NoSuchElementException if this map is empty.
3737:      */
3738:     public Object lastKey()
3739:     {
3740:       synchronized (mutex)
3741:         {
3742:           return sm.lastKey();
3743:         }
3744:     }
3745: 
3746:     /**
3747:      * Returns a submap containing the keys from fromKey to
3748:      * the key before toKey.  The submap supports all
3749:      * operations supported by the underlying map and all actions
3750:      * taking place on the submap are also reflected in the underlying
3751:      * map.  A lock is obtained on the mutex prior to submap creation.
3752:      * The submap retains the thread-safe status of this map.
3753:      *
3754:      * @param fromKey the inclusive lower range of the submap.
3755:      * @param toKey the exclusive upper range of the submap.
3756:      * @return a submap from fromKey to the key preceding toKey.
3757:      * @throws ClassCastException if fromKey or toKey is not comparable
3758:      *         to the underlying map's contents.
3759:      * @throws IllegalArgumentException if fromKey or toKey is outside the map's
3760:      *         range.
3761:      * @throws NullPointerException if fromKey or toKey is null. but the map does
3762:      *         not allow  null keys.
3763:      */
3764:     public SortedMap subMap(Object fromKey, Object toKey)
3765:     {
3766:       synchronized (mutex)
3767:         {
3768:           return new SynchronizedSortedMap(mutex, sm.subMap(fromKey, toKey));
3769:         }
3770:     }
3771: 
3772:     /**
3773:      * Returns a submap containing all the keys from fromKey onwards.
3774:      * The submap supports all operations supported by the underlying
3775:      * map and all actions taking place on the submap are also reflected
3776:      * in the underlying map.  A lock is obtained on the mutex prior to
3777:      * submap creation.  The submap retains the thread-safe status of
3778:      * this map.
3779:      *
3780:      * @param fromKey the inclusive lower range of the submap.
3781:      * @return a submap from fromKey to <code>lastKey()</code>.
3782:      * @throws ClassCastException if fromKey is not comparable to the underlying
3783:      *         map's contents.
3784:      * @throws IllegalArgumentException if fromKey is outside the map's range.
3785:      * @throws NullPointerException if fromKey is null. but the map does not allow
3786:      *         null keys.
3787:      */
3788:     public SortedMap tailMap(Object fromKey)
3789:     {
3790:       synchronized (mutex)
3791:         {
3792:           return new SynchronizedSortedMap(mutex, sm.tailMap(fromKey));
3793:         }
3794:     }
3795:   } // class SynchronizedSortedMap
3796: 
3797:   /**
3798:    * Returns a synchronized (thread-safe) sorted set wrapper backed by the
3799:    * given set. Notice that element access through the iterator and through
3800:    * subviews are thread-safe, but if the set can be structurally modified
3801:    * (adding or removing elements) then you should synchronize around the
3802:    * iteration to avoid non-deterministic behavior:<br>
3803:    * <pre>
3804:    * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
3805:    * ...
3806:    * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
3807:    * synchronized (s) // synch on s, not s2
3808:    *   {
3809:    *     Iterator i = s2.iterator();
3810:    *     while (i.hasNext())
3811:    *       foo(i.next());
3812:    *   }
3813:    * </pre><p>
3814:    *
3815:    * The returned SortedSet implements Serializable, but can only be
3816:    * serialized if the set it wraps is likewise Serializable.
3817:    *
3818:    * @param s the sorted set to wrap
3819:    * @return a synchronized view of the sorted set
3820:    * @see Serializable
3821:    */
3822:   public static SortedSet synchronizedSortedSet(SortedSet s)
3823:   {
3824:     return new SynchronizedSortedSet(s);
3825:   }
3826: 
3827:   /**
3828:    * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
3829:    * class name is required for compatibility with Sun's JDK serializability.
3830:    *
3831:    * @author Eric Blake (ebb9@email.byu.edu)
3832:    */
3833:   private static final class SynchronizedSortedSet extends SynchronizedSet
3834:     implements SortedSet
3835:   {
3836:     /**
3837:      * Compatible with JDK 1.4.
3838:      */
3839:     private static final long serialVersionUID = 8695801310862127406L;
3840: 
3841:     /**
3842:      * The wrapped set; stored both here and in the superclass to avoid
3843:      * excessive casting.
3844:      * @serial the wrapped set
3845:      */
3846:     private final SortedSet ss;
3847: 
3848:     /**
3849:      * Wrap a given set.
3850:      * @param ss the set to wrap
3851:      * @throws NullPointerException if ss is null
3852:      */
3853:     SynchronizedSortedSet(SortedSet ss)
3854:     {
3855:       super(ss);
3856:       this.ss = ss;
3857:     }
3858: 
3859:     /**
3860:      * Called only by trusted code to specify the mutex as well as the set.
3861:      * @param sync the mutex
3862:      * @param ss the set
3863:      */
3864:     SynchronizedSortedSet(Object sync, SortedSet ss)
3865:     {
3866:       super(sync, ss);
3867:       this.ss = ss;
3868:     }
3869: 
3870:     /**
3871:      * Returns the comparator used in sorting the underlying set, or null if
3872:      * it is the elements' natural ordering.  A lock is obtained on the mutex
3873:      * before the comparator is retrieved.
3874:      *
3875:      * @return the sorting comparator.
3876:      */
3877:     public Comparator comparator()
3878:     {
3879:       synchronized (mutex)
3880:         {
3881:           return ss.comparator();
3882:         }
3883:     }
3884: 
3885:     /**
3886:      * Returns the first, lowest sorted, element from the underlying set.
3887:      * A lock is obtained on the mutex before the set is accessed.
3888:      *
3889:      * @return the first element.
3890:      * @throws NoSuchElementException if this set is empty.
3891:      */
3892:     public Object first()
3893:     {
3894:       synchronized (mutex)
3895:         {
3896:           return ss.first();
3897:         }
3898:     }
3899: 
3900:     /**
3901:      * Returns a subset containing the element from the first
3902:      * element (as returned by <code>first()</code>) to
3903:      * the element before that specified.  The subset supports all
3904:      * operations supported by the underlying set and all actions
3905:      * taking place on the subset are also reflected in the underlying
3906:      * set.  A lock is obtained on the mutex prior to subset creation.
3907:      * This operation is equivalent to <code>subSet(first(), toElement)</code>.
3908:      * The subset retains the thread-safe status of this set.
3909:      *
3910:      * @param toElement the exclusive upper range of the subset.
3911:      * @return a subset from <code>first()</code> to the
3912:      *         the element preceding toElement.
3913:      * @throws ClassCastException if toElement is not comparable to the underlying
3914:      *         set's contents.
3915:      * @throws IllegalArgumentException if toElement is outside the set's range.
3916:      * @throws NullPointerException if toElement is null. but the set does not allow
3917:      *         null elements.
3918:      */
3919:     public SortedSet headSet(Object toElement)
3920:     {
3921:       synchronized (mutex)
3922:         {
3923:           return new SynchronizedSortedSet(mutex, ss.headSet(toElement));
3924:         }
3925:     }
3926: 
3927:     /**
3928:      * Returns the last, highest sorted, element from the underlying set.
3929:      * A lock is obtained on the mutex before the set is accessed.
3930:      *
3931:      * @return the last element.
3932:      * @throws NoSuchElementException if this set is empty.
3933:      */
3934:     public Object last()
3935:     {
3936:       synchronized (mutex)
3937:         {
3938:           return ss.last();
3939:         }
3940:     }
3941: 
3942:     /**
3943:      * Returns a subset containing the elements from fromElement to
3944:      * the element before toElement.  The subset supports all
3945:      * operations supported by the underlying set and all actions
3946:      * taking place on the subset are also reflected in the underlying
3947:      * set.  A lock is obtained on the mutex prior to subset creation.
3948:      * The subset retains the thread-safe status of this set.
3949:      *
3950:      * @param fromElement the inclusive lower range of the subset.
3951:      * @param toElement the exclusive upper range of the subset.
3952:      * @return a subset from fromElement to the element preceding toElement.
3953:      * @throws ClassCastException if fromElement or toElement is not comparable
3954:      *         to the underlying set's contents.
3955:      * @throws IllegalArgumentException if fromElement or toElement is outside the set's
3956:      *         range.
3957:      * @throws NullPointerException if fromElement or toElement is null. but the set does
3958:      *         not allow null elements.
3959:      */
3960:     public SortedSet subSet(Object fromElement, Object toElement)
3961:     {
3962:       synchronized (mutex)
3963:         {
3964:           return new SynchronizedSortedSet(mutex,
3965:                                            ss.subSet(fromElement, toElement));
3966:         }
3967:     }
3968: 
3969:     /**
3970:      * Returns a subset containing all the elements from fromElement onwards.
3971:      * The subset supports all operations supported by the underlying
3972:      * set and all actions taking place on the subset are also reflected
3973:      * in the underlying set.  A lock is obtained on the mutex prior to
3974:      * subset creation.  The subset retains the thread-safe status of
3975:      * this set.
3976:      *
3977:      * @param fromElement the inclusive lower range of the subset.
3978:      * @return a subset from fromElement to <code>last()</code>.
3979:      * @throws ClassCastException if fromElement is not comparable to the underlying
3980:      *         set's contents.
3981:      * @throws IllegalArgumentException if fromElement is outside the set's range.
3982:      * @throws NullPointerException if fromElement is null. but the set does not allow
3983:      *         null elements.
3984:      */
3985:     public SortedSet tailSet(Object fromElement)
3986:     {
3987:       synchronized (mutex)
3988:         {
3989:           return new SynchronizedSortedSet(mutex, ss.tailSet(fromElement));
3990:         }
3991:     }
3992:   } // class SynchronizedSortedSet
3993: 
3994: 
3995:   /**
3996:    * Returns an unmodifiable view of the given collection. This allows
3997:    * "read-only" access, although changes in the backing collection show up
3998:    * in this view. Attempts to modify the collection directly or via iterators
3999:    * will fail with {@link UnsupportedOperationException}.  Although this view
4000:    * prevents changes to the structure of the collection and its elements, the values
4001:    * referenced by the objects in the collection can still be modified.
4002:    * <p>
4003:    *
4004:    * Since the collection might be a List or a Set, and those have incompatible
4005:    * equals and hashCode requirements, this relies on Object's implementation
4006:    * rather than passing those calls on to the wrapped collection. The returned
4007:    * Collection implements Serializable, but can only be serialized if
4008:    * the collection it wraps is likewise Serializable.
4009:    *
4010:    * @param c the collection to wrap
4011:    * @return a read-only view of the collection
4012:    * @see Serializable
4013:    */
4014:   public static Collection unmodifiableCollection(Collection c)
4015:   {
4016:     return new UnmodifiableCollection(c);
4017:   }
4018: 
4019:   /**
4020:    * The implementation of {@link #unmodifiableCollection(Collection)}. This
4021:    * class name is required for compatibility with Sun's JDK serializability.
4022:    *
4023:    * @author Eric Blake (ebb9@email.byu.edu)
4024:    */
4025:   private static class UnmodifiableCollection
4026:     implements Collection, Serializable
4027:   {
4028:     /**
4029:      * Compatible with JDK 1.4.
4030:      */
4031:     private static final long serialVersionUID = 1820017752578914078L;
4032: 
4033:     /**
4034:      * The wrapped collection. Package visible for use by subclasses.
4035:      * @serial the real collection
4036:      */
4037:     final Collection c;
4038: 
4039:     /**
4040:      * Wrap a given collection.
4041:      * @param c the collection to wrap
4042:      * @throws NullPointerException if c is null
4043:      */
4044:     UnmodifiableCollection(Collection c)
4045:     {
4046:       this.c = c;
4047:       if (c == null)
4048:         throw new NullPointerException();
4049:     }
4050: 
4051:     /**
4052:      * Blocks the addition of elements to the underlying collection.
4053:      * This method never returns, throwing an exception instead.
4054:      *
4055:      * @param o the object to add.
4056:      * @return <code>true</code> if the collection was modified as a result of this action.
4057:      * @throws UnsupportedOperationException as an unmodifiable collection does not
4058:      *         support the add operation.
4059:      */
4060:     public boolean add(Object o)
4061:     {
4062:       throw new UnsupportedOperationException();
4063:     }
4064: 
4065:     /**
4066:      * Blocks the addition of a collection of elements to the underlying
4067:      * collection.  This method never returns, throwing an exception instead.
4068:      *
4069:      * @param c the collection to add.
4070:      * @return <code>true</code> if the collection was modified as a result of this action.
4071:      * @throws UnsupportedOperationException as an unmodifiable collection does not
4072:      *         support the <code>addAll</code> operation.
4073:      */
4074:     public boolean addAll(Collection c)
4075:     {
4076:       throw new UnsupportedOperationException();
4077:     }
4078: 
4079:     /**
4080:      * Blocks the clearing of the underlying collection.  This method never
4081:      * returns, throwing an exception instead.
4082:      *
4083:      * @throws UnsupportedOperationException as an unmodifiable collection does
4084:      *         not support the <code>clear()</code> operation.
4085:      */
4086:     public void clear()
4087:     {
4088:       throw new UnsupportedOperationException();
4089:     }
4090: 
4091:     /**
4092:      * Test whether the underlying collection contains a given object as one of its
4093:      * elements.
4094:      *
4095:      * @param o the element to look for.
4096:      * @return <code>true</code> if the underlying collection contains at least
4097:      *         one element e such that
4098:      *         <code>o == null ? e == null : o.equals(e)</code>.
4099:      * @throws ClassCastException if the type of o is not a valid type for the
4100:      *         underlying collection.
4101:      * @throws NullPointerException if o is null and the underlying collection
4102:      *         doesn't support null values.
4103:      */
4104:     public boolean contains(Object o)
4105:     {
4106:       return c.contains(o);
4107:     }
4108: 
4109:     /**
4110:      * Test whether the underlying collection contains every element in a given
4111:      * collection.
4112:      *
4113:      * @param c1 the collection to test for.
4114:      * @return <code>true</code> if for every element o in c, contains(o) would
4115:      *         return <code>true</code>.
4116:      * @throws ClassCastException if the type of any element in c is not a valid
4117:      *   type for the underlying collection.
4118:      * @throws NullPointerException if some element of c is null and the underlying
4119:      *   collection does not support null values.
4120:      * @throws NullPointerException if c itself is null.
4121:      */
4122:     public boolean containsAll(Collection c1)
4123:     {
4124:       return c.containsAll(c1);
4125:     }
4126: 
4127:     /**
4128:      * Tests whether the underlying collection is empty, that is,
4129:      * if size() == 0.
4130:      *
4131:      * @return <code>true</code> if this collection contains no elements.
4132:      */
4133:     public boolean isEmpty()
4134:     {
4135:       return c.isEmpty();
4136:     }
4137: 
4138:     /**
4139:      * Obtain an Iterator over the underlying collection, which maintains
4140:      * its unmodifiable nature.
4141:      *
4142:      * @return an UnmodifiableIterator over the elements of the underlying
4143:      *         collection, in any order.
4144:      */
4145:     public Iterator iterator()
4146:     {
4147:       return new UnmodifiableIterator(c.iterator());
4148:     }
4149: 
4150:     /**
4151:      * Blocks the removal of an object from the underlying collection.
4152:      * This method never returns, throwing an exception instead.
4153:      *
4154:      * @param o The object to remove.
4155:      * @return <code>true</code> if the object was removed (i.e. the underlying
4156:      *         collection returned 1 or more instances of o).
4157:      * @throws UnsupportedOperationException as an unmodifiable collection
4158:      *         does not support the <code>remove()</code> operation.
4159:      */
4160:     public boolean remove(Object o)
4161:     {
4162:       throw new UnsupportedOperationException();
4163:     }
4164: 
4165:     /**
4166:      * Blocks the removal of a collection of objects from the underlying
4167:      * collection.  This method never returns, throwing an exception
4168:      * instead.
4169:      *
4170:      * @param c The collection of objects to remove.
4171:      * @return <code>true</code> if the collection was modified.
4172:      * @throws UnsupportedOperationException as an unmodifiable collection
4173:      *         does not support the <code>removeAll()</code> operation.
4174:      */
4175:     public boolean removeAll(Collection c)
4176:     {
4177:       throw new UnsupportedOperationException();
4178:     }
4179: 
4180:     /**
4181:      * Blocks the removal of all elements from the underlying collection,
4182:      * except those in the supplied collection.  This method never returns,
4183:      * throwing an exception instead.
4184:      *
4185:      * @param c The collection of objects to retain.
4186:      * @return <code>true</code> if the collection was modified.
4187:      * @throws UnsupportedOperationException as an unmodifiable collection
4188:      *         does not support the <code>retainAll()</code> operation.
4189:      */
4190:     public boolean retainAll(Collection c)
4191:     {
4192:       throw new UnsupportedOperationException();
4193:     }
4194: 
4195:     /**
4196:      * Retrieves the number of elements in the underlying collection.
4197:      *
4198:      * @return the number of elements in the collection.
4199:      */
4200:     public int size()
4201:     {
4202:       return c.size();
4203:     }
4204: 
4205:     /**
4206:      * Copy the current contents of the underlying collection into an array.
4207:      *
4208:      * @return an array of type Object[] with a length equal to the size of the
4209:      *         underlying collection and containing the elements currently in
4210:      *         the underlying collection, in any order.
4211:      */
4212:     public Object[] toArray()
4213:     {
4214:       return c.toArray();
4215:     }
4216: 
4217:     /**
4218:      * Copy the current contents of the underlying collection into an array.  If
4219:      * the array passed as an argument has length less than the size of the
4220:      * underlying collection, an array of the same run-time type as a, with a length
4221:      * equal to the size of the underlying collection, is allocated using reflection.
4222:      * Otherwise, a itself is used.  The elements of the underlying collection are
4223:      * copied into it, and if there is space in the array, the following element is
4224:      * set to null. The resultant array is returned.
4225:      * Note: The fact that the following element is set to null is only useful
4226:      * if it is known that this collection does not contain any null elements.
4227:      *
4228:      * @param a the array to copy this collection into.
4229:      * @return an array containing the elements currently in the underlying
4230:      *         collection, in any order.
4231:      * @throws ArrayStoreException if the type of any element of the
4232:      *         collection is not a subtype of the element type of a.
4233:      */
4234:     public Object[] toArray(Object[] a)
4235:     {
4236:       return c.toArray(a);
4237:     }
4238: 
4239:     /**
4240:      * A textual representation of the unmodifiable collection.
4241:      *
4242:      * @return The unmodifiable collection in the form of a <code>String</code>.
4243:      */
4244:     public String toString()
4245:     {
4246:       return c.toString();
4247:     }
4248:   } // class UnmodifiableCollection
4249: 
4250:   /**
4251:    * The implementation of the various iterator methods in the
4252:    * unmodifiable classes.
4253:    *
4254:    * @author Eric Blake (ebb9@email.byu.edu)
4255:    */
4256:   private static class UnmodifiableIterator implements Iterator
4257:   {
4258:     /**
4259:      * The wrapped iterator.
4260:      */
4261:     private final Iterator i;
4262: 
4263:     /**
4264:      * Only trusted code creates a wrapper.
4265:      * @param i the wrapped iterator
4266:      */
4267:     UnmodifiableIterator(Iterator i)
4268:     {
4269:       this.i = i;
4270:     }
4271: 
4272:     /**
4273:      * Obtains the next element in the underlying collection.
4274:      *
4275:      * @return the next element in the collection.
4276:      * @throws NoSuchElementException if there are no more elements.
4277:      */
4278:     public Object next()
4279:     {
4280:       return i.next();
4281:     }
4282:     /**
4283:      * Tests whether there are still elements to be retrieved from the
4284:      * underlying collection by <code>next()</code>.  When this method
4285:      * returns <code>true</code>, an exception will not be thrown on calling
4286:      * <code>next()</code>.
4287:      *
4288:      * @return <code>true</code> if there is at least one more element in the underlying
4289:      *         collection.
4290:      */
4291:     public boolean hasNext()
4292:     {
4293:       return i.hasNext();
4294:     }
4295: 
4296:     /**
4297:      * Blocks the removal of elements from the underlying collection by the
4298:      * iterator.
4299:      *
4300:      * @throws UnsupportedOperationException as an unmodifiable collection
4301:      *         does not support the removal of elements by its iterator.
4302:      */
4303:     public void remove()
4304:     {
4305:       throw new UnsupportedOperationException();
4306:     }
4307:   } // class UnmodifiableIterator
4308: 
4309:   /**
4310:    * Returns an unmodifiable view of the given list. This allows
4311:    * "read-only" access, although changes in the backing list show up
4312:    * in this view. Attempts to modify the list directly, via iterators, or
4313:    * via sublists, will fail with {@link UnsupportedOperationException}.
4314:    * Although this view prevents changes to the structure of the list and
4315:    * its elements, the values referenced by the objects in the list can
4316:    * still be modified.   
4317:    * <p>
4318:    *
4319:    * The returned List implements Serializable, but can only be serialized if
4320:    * the list it wraps is likewise Serializable. In addition, if the wrapped
4321:    * list implements RandomAccess, this does too.
4322:    *
4323:    * @param l the list to wrap
4324:    * @return a read-only view of the list
4325:    * @see Serializable
4326:    * @see RandomAccess
4327:    */
4328:   public static List unmodifiableList(List l)
4329:   {
4330:     if (l instanceof RandomAccess)
4331:       return new UnmodifiableRandomAccessList(l);
4332:     return new UnmodifiableList(l);
4333:   }
4334: 
4335:   /**
4336:    * The implementation of {@link #unmodifiableList(List)} for sequential
4337:    * lists. This class name is required for compatibility with Sun's JDK
4338:    * serializability.
4339:    *
4340:    * @author Eric Blake (ebb9@email.byu.edu)
4341:    */
4342:   private static class UnmodifiableList extends UnmodifiableCollection
4343:     implements List
4344:   {
4345:     /**
4346:      * Compatible with JDK 1.4.
4347:      */
4348:     private static final long serialVersionUID = -283967356065247728L;
4349: 
4350: 
4351:     /**
4352:      * The wrapped list; stored both here and in the superclass to avoid
4353:      * excessive casting. Package visible for use by subclass.
4354:      * @serial the wrapped list
4355:      */
4356:     final List list;
4357: 
4358:     /**
4359:      * Wrap a given list.
4360:      * @param l the list to wrap
4361:      * @throws NullPointerException if l is null
4362:      */
4363:     UnmodifiableList(List l)
4364:     {
4365:       super(l);
4366:       list = l;
4367:     }
4368: 
4369:     /**
4370:      * Blocks the addition of an element to the underlying
4371:      * list at a specific index.  This method never returns,
4372:      * throwing an exception instead.
4373:      *
4374:      * @param index The index at which to place the new element.
4375:      * @param o the object to add.
4376:      * @throws UnsupportedOperationException as an unmodifiable
4377:      *         list doesn't support the <code>add()</code> operation.
4378:      */
4379:     public void add(int index, Object o)
4380:     {
4381:       throw new UnsupportedOperationException();
4382:     }
4383: 
4384:     /**
4385:      * Blocks the addition of a collection of elements to the
4386:      * underlying list at a specific index.  This method never
4387:      * returns, throwing an exception instead.
4388:      *
4389:      * @param index The index at which to place the new element.
4390:      * @param c the collections of objects to add.
4391:      * @throws UnsupportedOperationException as an unmodifiable
4392:      *         list doesn't support the <code>addAll()</code> operation.
4393:      */
4394:     public boolean addAll(int index, Collection c)
4395:     {
4396:       throw new UnsupportedOperationException();
4397:     }
4398: 
4399:     /**
4400:      * Returns <code>true</code> if the object, o, is an instance of
4401:      * <code>List</code> with the same size and elements
4402:      * as the underlying list.
4403:      *
4404:      * @param o The object to compare.
4405:      * @return <code>true</code> if o is equivalent to the underlying list.
4406:      */
4407:     public boolean equals(Object o)
4408:     {
4409:       return list.equals(o);
4410:     }
4411: 
4412:     /**
4413:      * Retrieves the element at a given index in the underlying list.
4414:      *
4415:      * @param index the index of the element to be returned
4416:      * @return the element at index index in this list
4417:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
4418:      */
4419:     public Object get(int index)
4420:     {
4421:       return list.get(index);
4422:     }
4423: 
4424:     /**
4425:      * Computes the hash code for the underlying list.
4426:      * The exact computation is described in the documentation
4427:      * of the <code>List</code> interface.
4428:      *
4429:      * @return The hash code of the underlying list.
4430:      * @see List#hashCode()
4431:      */
4432:     public int hashCode()
4433:     {
4434:       return list.hashCode();
4435:     }
4436: 
4437:     /**
4438:      * Obtain the first index at which a given object is to be found in the
4439:      * underlying list.
4440:      *
4441:      * @param o the object to search for
4442:      * @return the least integer n such that <code>o == null ? get(n) == null :
4443:      *         o.equals(get(n))</code>, or -1 if there is no such index.
4444:      * @throws ClassCastException if the type of o is not a valid
4445:      *         type for the underlying list.
4446:      * @throws NullPointerException if o is null and the underlying
4447:      *         list does not support null values.
4448:      */
4449:     public int indexOf(Object o)
4450:     {
4451:       return list.indexOf(o);
4452:     }
4453: 
4454:     /**
4455:      * Obtain the last index at which a given object is to be found in the
4456:      * underlying list.
4457:      *
4458:      * @return the greatest integer n such that <code>o == null ? get(n) == null
4459:      *         : o.equals(get(n))</code>, or -1 if there is no such index.
4460:      * @throws ClassCastException if the type of o is not a valid
4461:      *         type for the underlying list.
4462:      * @throws NullPointerException if o is null and the underlying
4463:      *         list does not support null values.
4464:      */
4465:     public int lastIndexOf(Object o)
4466:     {
4467:       return list.lastIndexOf(o);
4468:     }
4469: 
4470:   /**
4471:    * Obtains a list iterator over the underlying list, starting at the beginning
4472:    * and maintaining the unmodifiable nature of this list.
4473:    *
4474:    * @return a <code>UnmodifiableListIterator</code> over the elements of the
4475:    *         underlying list, in order, starting at the beginning.
4476:    */
4477:     public ListIterator listIterator()
4478:     {
4479:       return new UnmodifiableListIterator(list.listIterator());
4480:     }
4481: 
4482:   /**
4483:    * Obtains a list iterator over the underlying list, starting at the specified
4484:    * index and maintaining the unmodifiable nature of this list.  An initial call
4485:    * to <code>next()</code> will retrieve the element at the specified index,
4486:    * and an initial call to <code>previous()</code> will retrieve the element
4487:    * at index - 1.
4488:    *
4489:    *
4490:    * @param index the position, between 0 and size() inclusive, to begin the
4491:    *        iteration from.
4492:    * @return a <code>UnmodifiableListIterator</code> over the elements of the
4493:    *         underlying list, in order, starting at the specified index.
4494:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
4495:    */
4496:     public ListIterator listIterator(int index)
4497:     {
4498:       return new UnmodifiableListIterator(list.listIterator(index));
4499:     }
4500: 
4501:     /**
4502:      * Blocks the removal of the element at the specified index.
4503:      * This method never returns, throwing an exception instead.
4504:      *
4505:      * @param index The index of the element to remove.
4506:      * @return the removed element.
4507:      * @throws UnsupportedOperationException as an unmodifiable
4508:      *         list does not support the <code>remove()</code>
4509:      *         operation.
4510:      */
4511:     public Object remove(int index)
4512:     {
4513:       throw new UnsupportedOperationException();
4514:     }
4515: 
4516:     /**
4517:      * Blocks the replacement of the element at the specified index.
4518:      * This method never returns, throwing an exception instead.
4519:      *
4520:      * @param index The index of the element to replace.
4521:      * @param o The new object to place at the specified index.
4522:      * @return the replaced element.
4523:      * @throws UnsupportedOperationException as an unmodifiable
4524:      *         list does not support the <code>set()</code>
4525:      *         operation.
4526:      */
4527:     public Object set(int index, Object o)
4528:     {
4529:       throw new UnsupportedOperationException();
4530:     }
4531: 
4532:     /**
4533:      * Obtain a List view of a subsection of the underlying list, from
4534:      * fromIndex (inclusive) to toIndex (exclusive). If the two indices
4535:      * are equal, the sublist is empty. The returned list will be
4536:      * unmodifiable, like this list.  Changes to the elements of the
4537:      * returned list will be reflected in the underlying list. No structural
4538:      * modifications can take place in either list.
4539:      *
4540:      * @param fromIndex the index that the returned list should start from
4541:      *        (inclusive).
4542:      * @param toIndex the index that the returned list should go to (exclusive).
4543:      * @return a List backed by a subsection of the underlying list.
4544:      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
4545:      *         || toIndex &gt; size() || fromIndex &gt; toIndex.
4546:      */
4547:     public List subList(int fromIndex, int toIndex)
4548:     {
4549:       return unmodifiableList(list.subList(fromIndex, toIndex));
4550:     }
4551:   } // class UnmodifiableList
4552: 
4553:   /**
4554:    * The implementation of {@link #unmodifiableList(List)} for random-access
4555:    * lists. This class name is required for compatibility with Sun's JDK
4556:    * serializability.
4557:    *
4558:    * @author Eric Blake (ebb9@email.byu.edu)
4559:    */
4560:   private static final class UnmodifiableRandomAccessList
4561:     extends UnmodifiableList implements RandomAccess
4562:   {
4563:     /**
4564:      * Compatible with JDK 1.4.
4565:      */
4566:     private static final long serialVersionUID = -2542308836966382001L;
4567: 
4568:     /**
4569:      * Wrap a given list.
4570:      * @param l the list to wrap
4571:      * @throws NullPointerException if l is null
4572:      */
4573:     UnmodifiableRandomAccessList(List l)
4574:     {
4575:       super(l);
4576:     }
4577:   } // class UnmodifiableRandomAccessList
4578: 
4579:   /**
4580:    * The implementation of {@link UnmodifiableList#listIterator()}.
4581:    *
4582:    * @author Eric Blake (ebb9@email.byu.edu)
4583:    */
4584:   private static final class UnmodifiableListIterator
4585:     extends UnmodifiableIterator implements ListIterator
4586:   {
4587:     /**
4588:      * The wrapped iterator, stored both here and in the superclass to
4589:      * avoid excessive casting.
4590:      */
4591:     private final ListIterator li;
4592: 
4593:     /**
4594:      * Only trusted code creates a wrapper.
4595:      * @param li the wrapped iterator
4596:      */
4597:     UnmodifiableListIterator(ListIterator li)
4598:     {
4599:       super(li);
4600:       this.li = li;
4601:     }
4602: 
4603:     /**
4604:      * Blocks the addition of an object to the list underlying this iterator.
4605:      * This method never returns, throwing an exception instead.
4606:      *
4607:      * @param o The object to add.
4608:      * @throws UnsupportedOperationException as the iterator of an unmodifiable
4609:      *         list does not support the <code>add()</code> operation.
4610:      */
4611:     public void add(Object o)
4612:     {
4613:       throw new UnsupportedOperationException();
4614:     }
4615: 
4616:     /**
4617:      * Tests whether there are still elements to be retrieved from the
4618:      * underlying collection by <code>previous()</code>.  When this method
4619:      * returns <code>true</code>, an exception will not be thrown on calling
4620:      * <code>previous()</code>.
4621:      *
4622:      * @return <code>true</code> if there is at least one more element prior to the
4623:      *         current position in the underlying list.
4624:      */
4625:     public boolean hasPrevious()
4626:     {
4627:       return li.hasPrevious();
4628:     }
4629: 
4630:     /**
4631:      * Find the index of the element that would be returned by a call to next.
4632:      * If <code>hasNext()</code> returns <code>false</code>, this returns the list size.
4633:      *
4634:      * @return the index of the element that would be returned by
4635:      *         <code>next()</code>.
4636:      */
4637:     public int nextIndex()
4638:     {
4639:       return li.nextIndex();
4640:     }
4641: 
4642:     /**
4643:      * Obtains the previous element in the underlying list.
4644:      *
4645:      * @return the previous element in the list.
4646:      * @throws NoSuchElementException if there are no more prior elements.
4647:      */
4648:     public Object previous()
4649:     {
4650:       return li.previous();
4651:     }
4652: 
4653:     /**
4654:      * Find the index of the element that would be returned by a call to
4655:      * previous. If <code>hasPrevious()</code> returns <code>false</code>,
4656:      * this returns -1.
4657:      *
4658:      * @return the index of the element that would be returned by
4659:      *         <code>previous()</code>.
4660:      */
4661:     public int previousIndex()
4662:     {
4663:       return li.previousIndex();
4664:     }
4665: 
4666:     /**
4667:      * Blocks the replacement of an element in the list underlying this
4668:      * iterator.  This method never returns, throwing an exception instead.
4669:      *
4670:      * @param o The new object to replace the existing one.
4671:      * @throws UnsupportedOperationException as the iterator of an unmodifiable
4672:      *         list does not support the <code>set()</code> operation.
4673:      */
4674:     public void set(Object o)
4675:     {
4676:       throw new UnsupportedOperationException();
4677:     }
4678:   } // class UnmodifiableListIterator
4679: 
4680:   /**
4681:    * Returns an unmodifiable view of the given map. This allows "read-only"
4682:    * access, although changes in the backing map show up in this view.
4683:    * Attempts to modify the map directly, or via collection views or their
4684:    * iterators will fail with {@link UnsupportedOperationException}.
4685:    * Although this view prevents changes to the structure of the map and its
4686:    * entries, the values referenced by the objects in the map can still be
4687:    * modified.   
4688:    * <p>
4689:    *
4690:    * The returned Map implements Serializable, but can only be serialized if
4691:    * the map it wraps is likewise Serializable.
4692:    *
4693:    * @param m the map to wrap
4694:    * @return a read-only view of the map
4695:    * @see Serializable
4696:    */
4697:   public static Map unmodifiableMap(Map m)
4698:   {
4699:     return new UnmodifiableMap(m);
4700:   }
4701: 
4702:   /**
4703:    * The implementation of {@link #unmodifiableMap(Map)}. This
4704:    * class name is required for compatibility with Sun's JDK serializability.
4705:    *
4706:    * @author Eric Blake (ebb9@email.byu.edu)
4707:    */
4708:   private static class UnmodifiableMap implements Map, Serializable
4709:   {
4710:     /**
4711:      * Compatible with JDK 1.4.
4712:      */
4713:     private static final long serialVersionUID = -1034234728574286014L;
4714: 
4715:     /**
4716:      * The wrapped map.
4717:      * @serial the real map
4718:      */
4719:     private final Map m;
4720: 
4721:     /**
4722:      * Cache the entry set.
4723:      */
4724:     private transient Set entries;
4725: 
4726:     /**
4727:      * Cache the key set.
4728:      */
4729:     private transient Set keys;
4730: 
4731:     /**
4732:      * Cache the value collection.
4733:      */
4734:     private transient Collection values;
4735: 
4736:     /**
4737:      * Wrap a given map.
4738:      * @param m the map to wrap
4739:      * @throws NullPointerException if m is null
4740:      */
4741:     UnmodifiableMap(Map m)
4742:     {
4743:       this.m = m;
4744:       if (m == null)
4745:         throw new NullPointerException();
4746:     }
4747: 
4748:     /**
4749:      * Blocks the clearing of entries from the underlying map.
4750:      * This method never returns, throwing an exception instead.
4751:      *
4752:      * @throws UnsupportedOperationException as an unmodifiable
4753:      *         map does not support the <code>clear()</code> operation.
4754:      */
4755:     public void clear()
4756:     {
4757:       throw new UnsupportedOperationException();
4758:     }
4759: 
4760:     /**
4761:      * Returns <code>true</code> if the underlying map contains a mapping for
4762:      * the given key.
4763:      *
4764:      * @param key the key to search for
4765:      * @return <code>true</code> if the map contains the key
4766:      * @throws ClassCastException if the key is of an inappropriate type
4767:      * @throws NullPointerException if key is <code>null</code> but the map
4768:      *         does not permit null keys
4769:      */
4770:     public boolean containsKey(Object key)
4771:     {
4772:       return m.containsKey(key);
4773:     }
4774: 
4775:     /**
4776:      * Returns <code>true</code> if the underlying map contains at least one mapping with
4777:      * the given value.  In other words, it returns <code>true</code> if a value v exists where
4778:      * <code>(value == null ? v == null : value.equals(v))</code>. This usually
4779:      * requires linear time.
4780:      *
4781:      * @param value the value to search for
4782:      * @return <code>true</code> if the map contains the value
4783:      * @throws ClassCastException if the type of the value is not a valid type
4784:      *         for this map.
4785:      * @throws NullPointerException if the value is null and the map doesn't
4786:      *         support null values.
4787:      */
4788:     public boolean containsValue(Object value)
4789:     {
4790:       return m.containsValue(value);
4791:     }
4792: 
4793:     /**
4794:      * Returns a unmodifiable set view of the entries in the underlying map.
4795:      * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>.
4796:      * The set is backed by the map, so that changes in one show up in the other.
4797:      * Modifications made while an iterator is in progress cause undefined
4798:      * behavior.  These modifications are again limited to the values of
4799:      * the objects.
4800:      *
4801:      * @return the unmodifiable set view of all mapping entries.
4802:      * @see Map.Entry
4803:      */
4804:     public Set entrySet()
4805:     {
4806:       if (entries == null)
4807:         entries = new UnmodifiableEntrySet(m.entrySet());
4808:       return entries;
4809:     }
4810: 
4811:     /**
4812:      * The implementation of {@link UnmodifiableMap#entrySet()}. This class
4813:      * name is required for compatibility with Sun's JDK serializability.
4814:      *
4815:      * @author Eric Blake (ebb9@email.byu.edu)
4816:      */
4817:     private static final class UnmodifiableEntrySet extends UnmodifiableSet
4818:       implements Serializable
4819:     {
4820:       /**
4821:        * Compatible with JDK 1.4.
4822:        */
4823:       private static final long serialVersionUID = 7854390611657943733L;
4824: 
4825:       /**
4826:        * Wrap a given set.
4827:        * @param s the set to wrap
4828:        */
4829:       UnmodifiableEntrySet(Set s)
4830:       {
4831:         super(s);
4832:       }
4833: 
4834:       // The iterator must return unmodifiable map entries.
4835:       public Iterator iterator()
4836:       {
4837:         return new UnmodifiableIterator(c.iterator())
4838:     {
4839:       /**
4840:        * Obtains the next element from the underlying set of
4841:        * map entries.
4842:        *
4843:        * @return the next element in the collection.
4844:        * @throws NoSuchElementException if there are no more elements.
4845:        */
4846:           public Object next()
4847:           {
4848:             final Map.Entry e = (Map.Entry) super.next();
4849:             return new Map.Entry()
4850:         {
4851:           /**
4852:            * Returns <code>true</code> if the object, o, is also a map entry with an
4853:            * identical key and value.
4854:            *
4855:            * @param o the object to compare.
4856:            * @return <code>true</code> if o is an equivalent map entry.
4857:            */
4858:               public boolean equals(Object o)
4859:               {
4860:                 return e.equals(o);
4861:               }
4862:           
4863:           /**
4864:            * Returns the key of this map entry.
4865:            *
4866:            * @return the key.
4867:            */
4868:               public Object getKey()
4869:               {
4870:                 return e.getKey();
4871:               }
4872: 
4873:           /**
4874:            * Returns the value of this map entry.
4875:            *
4876:            * @return the value.
4877:            */
4878:               public Object getValue()
4879:               {
4880:                 return e.getValue();
4881:               }
4882: 
4883:           /**
4884:            * Computes the hash code of this map entry.
4885:            * The computation is described in the <code>Map</code>
4886:            * interface documentation.
4887:            *
4888:            * @return the hash code of this entry.
4889:            * @see Map#hashCode()
4890:            */
4891:               public int hashCode()
4892:               {
4893:                 return e.hashCode();
4894:               }
4895: 
4896:           /**
4897:            * Blocks the alteration of the value of this map entry.
4898:            * This method never returns, throwing an exception instead.
4899:            *
4900:            * @param value The new value.
4901:            * @throws UnsupportedOperationException as an unmodifiable
4902:            *         map entry does not support the <code>setValue()</code>
4903:            *         operation.
4904:            */
4905:               public Object setValue(Object value)
4906:               {
4907:                 throw new UnsupportedOperationException();
4908:               }
4909: 
4910:           /**
4911:            * Returns a textual representation of the map entry.
4912:            *
4913:            * @return The map entry as a <code>String</code>.
4914:            */
4915:               public String toString()
4916:               {
4917:                 return e.toString();
4918:               }
4919:         };
4920:           }
4921:     };
4922:       }
4923:     } // class UnmodifiableEntrySet
4924: 
4925:     /**
4926:      * Returns <code>true</code> if the object, o, is also an instance
4927:      * of <code>Map</code> with an equal set of map entries.
4928:      *
4929:      * @param o The object to compare.
4930:      * @return <code>true</code> if o is an equivalent map.
4931:      */
4932:     public boolean equals(Object o)
4933:     {
4934:       return m.equals(o);
4935:     }
4936: 
4937:     /**
4938:      * Returns the value associated with the supplied key or
4939:      * null if no such mapping exists.  An ambiguity can occur
4940:      * if null values are accepted by the underlying map.
4941:      * In this case, <code>containsKey()</code> can be used
4942:      * to separate the two possible cases of a null result.
4943:      *
4944:      * @param key The key to look up.
4945:      * @return the value associated with the key, or null if key not in map.
4946:      * @throws ClassCastException if the key is an inappropriate type.
4947:      * @throws NullPointerException if this map does not accept null keys.
4948:      * @see #containsKey(Object)
4949:      */
4950:     public Object get(Object key)
4951:     {
4952:       return m.get(key);
4953:     }
4954: 
4955:     /**
4956:      * Blocks the addition of a new entry to the underlying map.
4957:      * This method never returns, throwing an exception instead.
4958:      *
4959:      * @param key The new key.
4960:      * @param value The new value.
4961:      * @return the previous value of the key, or null if there was no mapping.
4962:      * @throws UnsupportedOperationException as an unmodifiable
4963:      *         map does not support the <code>put()</code> operation.
4964:      */
4965:     public Object put(Object key, Object value)
4966:     {
4967:       throw new UnsupportedOperationException();
4968:     }
4969: 
4970:     /**
4971:      * Computes the hash code for the underlying map, as the sum
4972:      * of the hash codes of all entries.
4973:      *
4974:      * @return The hash code of the underlying map.
4975:      * @see Map.Entry#hashCode()
4976:      */
4977:     public int hashCode()
4978:     {
4979:       return m.hashCode();
4980:     }
4981: 
4982:     /**
4983:      * Returns <code>true</code> if the underlying map contains no entries.
4984:      *
4985:      * @return <code>true</code> if the map is empty.
4986:      */
4987:     public boolean isEmpty()
4988:     {
4989:       return m.isEmpty();
4990:     }
4991: 
4992:     /**
4993:      * Returns a unmodifiable set view of the keys in the underlying map.
4994:      * The set is backed by the map, so that changes in one show up in the other.
4995:      * Modifications made while an iterator is in progress cause undefined
4996:      * behavior.  These modifications are again limited to the values of
4997:      * the keys.
4998:      *
4999:      * @return the set view of all keys.
5000:      */
5001:     public Set keySet()
5002:     {
5003:       if (keys == null)
5004:         keys = new UnmodifiableSet(m.keySet());
5005:       return keys;
5006:     }
5007: 
5008:     /**
5009:      * Blocks the addition of the entries in the supplied map.
5010:      * This method never returns, throwing an exception instead.
5011:      *
5012:      * @param m The map, the entries of which should be added
5013:      *          to the underlying map.
5014:      * @throws UnsupportedOperationException as an unmodifiable
5015:      *         map does not support the <code>putAll</code> operation.
5016:      */
5017:     public void putAll(Map m)
5018:     {
5019:       throw new UnsupportedOperationException();
5020:     }
5021: 
5022:     /**
5023:      * Blocks the removal of an entry from the map.
5024:      * This method never returns, throwing an exception instead.
5025:      *
5026:      * @param o The key of the entry to remove.
5027:      * @return The value the key was associated with, or null
5028:      *         if no such mapping existed.  Null is also returned
5029:      *         if the removed entry had a null key.
5030:      * @throws UnsupportedOperationException as an unmodifiable
5031:      *         map does not support the <code>remove</code> operation.
5032:      */
5033:     public Object remove(Object o)
5034:     {
5035:       throw new UnsupportedOperationException();
5036:     }
5037: 
5038: 
5039:     /**
5040:      * Returns the number of key-value mappings in the underlying map.
5041:      * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
5042:      * is returned.
5043:      *
5044:      * @return the number of mappings.
5045:      */
5046:     public int size()
5047:     {
5048:       return m.size();
5049:     }
5050: 
5051:     /**
5052:      * Returns a textual representation of the map.
5053:      *
5054:      * @return The map in the form of a <code>String</code>.
5055:      */
5056:     public String toString()
5057:     {
5058:       return m.toString();
5059:     }
5060: 
5061:     /**
5062:      * Returns a unmodifiable collection view of the values in the underlying map.
5063:      * The collection is backed by the map, so that changes in one show up in the other.
5064:      * Modifications made while an iterator is in progress cause undefined
5065:      * behavior.  These modifications are again limited to the values of
5066:      * the keys.
5067:      *
5068:      * @return the collection view of all values.
5069:      */
5070:     public Collection values()
5071:     {
5072:       if (values == null)
5073:         values = new UnmodifiableCollection(m.values());
5074:       return values;
5075:     }
5076:   } // class UnmodifiableMap
5077: 
5078:   /**
5079:    * Returns an unmodifiable view of the given set. This allows
5080:    * "read-only" access, although changes in the backing set show up
5081:    * in this view. Attempts to modify the set directly or via iterators
5082:    * will fail with {@link UnsupportedOperationException}.
5083:    * Although this view prevents changes to the structure of the set and its
5084:    * entries, the values referenced by the objects in the set can still be
5085:    * modified.   
5086:    * <p>
5087:    *
5088:    * The returned Set implements Serializable, but can only be serialized if
5089:    * the set it wraps is likewise Serializable.
5090:    *
5091:    * @param s the set to wrap
5092:    * @return a read-only view of the set
5093:    * @see Serializable
5094:    */
5095:   public static Set unmodifiableSet(Set s)
5096:   {
5097:     return new UnmodifiableSet(s);
5098:   }
5099: 
5100:   /**
5101:    * The implementation of {@link #unmodifiableSet(Set)}. This class
5102:    * name is required for compatibility with Sun's JDK serializability.
5103:    *
5104:    * @author Eric Blake (ebb9@email.byu.edu)
5105:    */
5106:   private static class UnmodifiableSet extends UnmodifiableCollection
5107:     implements Set
5108:   {
5109:     /**
5110:      * Compatible with JDK 1.4.
5111:      */
5112:     private static final long serialVersionUID = -9215047833775013803L;
5113: 
5114:     /**
5115:      * Wrap a given set.
5116:      * @param s the set to wrap
5117:      * @throws NullPointerException if s is null
5118:      */
5119:     UnmodifiableSet(Set s)
5120:     {
5121:       super(s);
5122:     }
5123: 
5124:     /**
5125:      * Returns <code>true</code> if the object, o, is also an instance of
5126:      * <code>Set</code> of the same size and with the same entries.
5127:      *
5128:      * @return <code>true</code> if o is an equivalent set.
5129:      */
5130:     public boolean equals(Object o)
5131:     {
5132:       return c.equals(o);
5133:     }
5134: 
5135:     /**
5136:      * Computes the hash code of this set, as the sum of the
5137:      * hash codes of all elements within the set.
5138:      *
5139:      * @return the hash code of the set.
5140:      */ 
5141:     public int hashCode()
5142:     {
5143:       return c.hashCode();
5144:     }
5145:   } // class UnmodifiableSet
5146: 
5147:   /**
5148:    * Returns an unmodifiable view of the given sorted map. This allows
5149:    * "read-only" access, although changes in the backing map show up in this
5150:    * view. Attempts to modify the map directly, via subviews, via collection
5151:    * views, or iterators, will fail with {@link UnsupportedOperationException}.
5152:    * Although this view prevents changes to the structure of the map and its
5153:    * entries, the values referenced by the objects in the map can still be
5154:    * modified.   
5155:    * <p>
5156:    *
5157:    * The returned SortedMap implements Serializable, but can only be
5158:    * serialized if the map it wraps is likewise Serializable.
5159:    *
5160:    * @param m the map to wrap
5161:    * @return a read-only view of the map
5162:    * @see Serializable
5163:    */
5164:   public static SortedMap unmodifiableSortedMap(SortedMap m)
5165:   {
5166:     return new UnmodifiableSortedMap(m);
5167:   }
5168: 
5169:   /**
5170:    * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
5171:    * class name is required for compatibility with Sun's JDK serializability.
5172:    *
5173:    * @author Eric Blake (ebb9@email.byu.edu)
5174:    */
5175:   private static class UnmodifiableSortedMap extends UnmodifiableMap
5176:     implements SortedMap
5177:   {
5178:     /**
5179:      * Compatible with JDK 1.4.
5180:      */
5181:     private static final long serialVersionUID = -8806743815996713206L;
5182: 
5183:     /**
5184:      * The wrapped map; stored both here and in the superclass to avoid
5185:      * excessive casting.
5186:      * @serial the wrapped map
5187:      */
5188:     private final SortedMap sm;
5189: 
5190:     /**
5191:      * Wrap a given map.
5192:      * @param sm the map to wrap
5193:      * @throws NullPointerException if sm is null
5194:      */
5195:     UnmodifiableSortedMap(SortedMap sm)
5196:     {
5197:       super(sm);
5198:       this.sm = sm;
5199:     }
5200: 
5201:     /**
5202:      * Returns the comparator used in sorting the underlying map,
5203:      * or null if it is the keys' natural ordering.
5204:      *
5205:      * @return the sorting comparator.
5206:      */
5207:     public Comparator comparator()
5208:     {
5209:       return sm.comparator();
5210:     }
5211: 
5212:     /**
5213:      * Returns the first (lowest sorted) key in the map.
5214:      *
5215:      * @return the first key.
5216:      * @throws NoSuchElementException if this map is empty.
5217:      */
5218:     public Object firstKey()
5219:     {
5220:       return sm.firstKey();
5221:     }
5222: 
5223:     /**
5224:      * Returns a unmodifiable view of the portion of the map strictly less
5225:      * than toKey. The view is backed by the underlying map, so changes in
5226:      * one show up in the other.  The submap supports all optional operations
5227:      * of the original.  This operation is equivalent to
5228:      * <code>subMap(firstKey(), toKey)</code>.
5229:      * <p>
5230:      *
5231:      * The returned map throws an IllegalArgumentException any time a key is
5232:      * used which is out of the range of toKey. Note that the endpoint, toKey,
5233:      * is not included; if you want this value to be included, pass its successor
5234:      * object in to toKey.  For example, for Integers, you could request
5235:      * <code>headMap(new Integer(limit.intValue() + 1))</code>.
5236:      *
5237:      * @param toKey the exclusive upper range of the submap.
5238:      * @return the submap.
5239:      * @throws ClassCastException if toKey is not comparable to the map contents.
5240:      * @throws IllegalArgumentException if this is a subMap, and toKey is out
5241:      *         of range.
5242:      * @throws NullPointerException if toKey is null but the map does not allow
5243:      *         null keys.
5244:      */
5245:     public SortedMap headMap(Object toKey)
5246:     {
5247:       return new UnmodifiableSortedMap(sm.headMap(toKey));
5248:     }
5249: 
5250:     /**
5251:      * Returns the last (highest sorted) key in the map.
5252:      *
5253:      * @return the last key.
5254:      * @throws NoSuchElementException if this map is empty.
5255:      */
5256:     public Object lastKey()
5257:     {
5258:       return sm.lastKey();
5259:     }
5260: 
5261:     /**
5262:      * Returns a unmodifiable view of the portion of the map greater than or
5263:      * equal to fromKey, and strictly less than toKey. The view is backed by
5264:      * the underlying map, so changes in one show up in the other. The submap
5265:      * supports all optional operations of the original.
5266:      * <p>
5267:      *
5268:      * The returned map throws an IllegalArgumentException any time a key is
5269:      * used which is out of the range of fromKey and toKey. Note that the
5270:      * lower endpoint is included, but the upper is not; if you want to
5271:      * change the inclusion or exclusion of an endpoint, pass its successor
5272:      * object in instead.  For example, for Integers, you could request
5273:      * <code>subMap(new Integer(lowlimit.intValue() + 1),
5274:      * new Integer(highlimit.intValue() + 1))</code> to reverse
5275:      * the inclusiveness of both endpoints.
5276:      *
5277:      * @param fromKey the inclusive lower range of the submap.
5278:      * @param toKey the exclusive upper range of the submap.
5279:      * @return the submap.
5280:      * @throws ClassCastException if fromKey or toKey is not comparable to
5281:      *         the map contents.
5282:      * @throws IllegalArgumentException if this is a subMap, and fromKey or
5283:      *         toKey is out of range.
5284:      * @throws NullPointerException if fromKey or toKey is null but the map
5285:      *         does not allow null keys.
5286:      */
5287:     public SortedMap subMap(Object fromKey, Object toKey)
5288:     {
5289:       return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
5290:     }
5291: 
5292:     /**
5293:      * Returns a unmodifiable view of the portion of the map greater than or
5294:      * equal to fromKey. The view is backed by the underlying map, so changes
5295:      * in one show up in the other. The submap supports all optional operations
5296:      * of the original.
5297:      * <p>
5298:      *
5299:      * The returned map throws an IllegalArgumentException any time a key is
5300:      * used which is out of the range of fromKey. Note that the endpoint, fromKey, is
5301:      * included; if you do not want this value to be included, pass its successor object in
5302:      * to fromKey.  For example, for Integers, you could request
5303:      * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
5304:      *
5305:      * @param fromKey the inclusive lower range of the submap
5306:      * @return the submap
5307:      * @throws ClassCastException if fromKey is not comparable to the map
5308:      *         contents
5309:      * @throws IllegalArgumentException if this is a subMap, and fromKey is out
5310:      *         of range
5311:      * @throws NullPointerException if fromKey is null but the map does not allow
5312:      *         null keys
5313:      */
5314:     public SortedMap tailMap(Object fromKey)
5315:     {
5316:       return new UnmodifiableSortedMap(sm.tailMap(fromKey));
5317:     }
5318:   } // class UnmodifiableSortedMap
5319: 
5320:   /**
5321:    * Returns an unmodifiable view of the given sorted set. This allows
5322:    * "read-only" access, although changes in the backing set show up
5323:    * in this view. Attempts to modify the set directly, via subsets, or via
5324:    * iterators, will fail with {@link UnsupportedOperationException}.
5325:    * Although this view prevents changes to the structure of the set and its
5326:    * entries, the values referenced by the objects in the set can still be
5327:    * modified.   
5328:    * <p>
5329:    *
5330:    * The returns SortedSet implements Serializable, but can only be
5331:    * serialized if the set it wraps is likewise Serializable.
5332:    *
5333:    * @param s the set to wrap
5334:    * @return a read-only view of the set
5335:    * @see Serializable
5336:    */
5337:   public static SortedSet unmodifiableSortedSet(SortedSet s)
5338:   {
5339:     return new UnmodifiableSortedSet(s);
5340:   }
5341: 
5342:   /**
5343:    * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
5344:    * class name is required for compatibility with Sun's JDK serializability.
5345:    *
5346:    * @author Eric Blake (ebb9@email.byu.edu)
5347:    */
5348:   private static class UnmodifiableSortedSet extends UnmodifiableSet
5349:     implements SortedSet
5350:   {
5351:     /**
5352:      * Compatible with JDK 1.4.
5353:      */
5354:     private static final long serialVersionUID = -4929149591599911165L;
5355: 
5356:     /**
5357:      * The wrapped set; stored both here and in the superclass to avoid
5358:      * excessive casting.
5359:      * @serial the wrapped set
5360:      */
5361:     private SortedSet ss;
5362: 
5363:     /**
5364:      * Wrap a given set.
5365:      * @param ss the set to wrap
5366:      * @throws NullPointerException if ss is null
5367:      */
5368:     UnmodifiableSortedSet(SortedSet ss)
5369:     {
5370:       super(ss);
5371:       this.ss = ss;
5372:     }
5373: 
5374:     /**
5375:      * Returns the comparator used in sorting the underlying set,
5376:      * or null if it is the elements' natural ordering.
5377:      *
5378:      * @return the sorting comparator
5379:      */
5380:     public Comparator comparator()
5381:     {
5382:       return ss.comparator();
5383:     }
5384: 
5385:     /**
5386:      * Returns the first (lowest sorted) element in the underlying
5387:      * set.
5388:      *
5389:      * @return the first element.
5390:      * @throws NoSuchElementException if the set is empty.
5391:      */
5392:     public Object first()
5393:     {
5394:       return ss.first();
5395:     }
5396: 
5397:     /**
5398:      * Returns a unmodifiable view of the portion of the set strictly
5399:      * less than toElement. The view is backed by the underlying set,
5400:      * so changes in one show up in the other.  The subset supports
5401:      * all optional operations of the original.  This operation
5402:      * is equivalent to <code>subSet(first(), toElement)</code>.
5403:      * <p>
5404:      *
5405:      * The returned set throws an IllegalArgumentException any time an element is
5406:      * used which is out of the range of toElement. Note that the endpoint, toElement,
5407:      * is not included; if you want this value included, pass its successor object in to
5408:      * toElement.  For example, for Integers, you could request
5409:      * <code>headSet(new Integer(limit.intValue() + 1))</code>.
5410:      *
5411:      * @param toElement the exclusive upper range of the subset
5412:      * @return the subset.
5413:      * @throws ClassCastException if toElement is not comparable to the set
5414:      *         contents.
5415:      * @throws IllegalArgumentException if this is a subSet, and toElement is out
5416:      *         of range.
5417:      * @throws NullPointerException if toElement is null but the set does not
5418:      *         allow null elements.
5419:      */
5420:     public SortedSet headSet(Object toElement)
5421:     {
5422:       return new UnmodifiableSortedSet(ss.headSet(toElement));
5423:     }
5424: 
5425:     /**
5426:      * Returns the last (highest sorted) element in the underlying
5427:      * set.
5428:      *
5429:      * @return the last element.
5430:      * @throws NoSuchElementException if the set is empty.
5431:      */
5432:     public Object last()
5433:     {
5434:       return ss.last();
5435:     }
5436: 
5437:     /**
5438:      * Returns a unmodifiable view of the portion of the set greater than or
5439:      * equal to fromElement, and strictly less than toElement. The view is backed by
5440:      * the underlying set, so changes in one show up in the other. The subset
5441:      * supports all optional operations of the original.
5442:      * <p>
5443:      *
5444:      * The returned set throws an IllegalArgumentException any time an element is
5445:      * used which is out of the range of fromElement and toElement. Note that the
5446:      * lower endpoint is included, but the upper is not; if you want to
5447:      * change the inclusion or exclusion of an endpoint, pass its successor
5448:      * object in instead.  For example, for Integers, you can request
5449:      * <code>subSet(new Integer(lowlimit.intValue() + 1),
5450:      * new Integer(highlimit.intValue() + 1))</code> to reverse
5451:      * the inclusiveness of both endpoints.
5452:      *
5453:      * @param fromElement the inclusive lower range of the subset.
5454:      * @param toElement the exclusive upper range of the subset.
5455:      * @return the subset.
5456:      * @throws ClassCastException if fromElement or toElement is not comparable
5457:      *         to the set contents.
5458:      * @throws IllegalArgumentException if this is a subSet, and fromElement or
5459:      *         toElement is out of range.
5460:      * @throws NullPointerException if fromElement or toElement is null but the
5461:      *         set does not allow null elements.
5462:      */
5463:     public SortedSet subSet(Object fromElement, Object toElement)
5464:     {
5465:       return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement));
5466:     }
5467: 
5468:     /**
5469:      * Returns a unmodifiable view of the portion of the set greater than or equal to
5470:      * fromElement. The view is backed by the underlying set, so changes in one show up
5471:      * in the other. The subset supports all optional operations of the original.
5472:      * <p>
5473:      *
5474:      * The returned set throws an IllegalArgumentException any time an element is
5475:      * used which is out of the range of fromElement. Note that the endpoint,
5476:      * fromElement, is included; if you do not want this value to be included, pass its
5477:      * successor object in to fromElement.  For example, for Integers, you could request
5478:      * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
5479:      *
5480:      * @param fromElement the inclusive lower range of the subset
5481:      * @return the subset.
5482:      * @throws ClassCastException if fromElement is not comparable to the set
5483:      *         contents.
5484:      * @throws IllegalArgumentException if this is a subSet, and fromElement is
5485:      *         out of range.
5486:      * @throws NullPointerException if fromElement is null but the set does not
5487:      *         allow null elements.
5488:      */
5489:     public SortedSet tailSet(Object fromElement)
5490:     {
5491:       return new UnmodifiableSortedSet(ss.tailSet(fromElement));
5492:     }
5493:   } // class UnmodifiableSortedSet
5494: } // class Collections