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(key, o, 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(key, l.get(pos), 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)}. This class name
1735:    * 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 an element to the end of the underlying list (optional operation).
2522:    * If the list imposes restraints on what can be inserted, such as no null
2523:    * elements, this should be documented.  A lock is obtained on the mutex before
2524:    * any of the elements are added.
2525:    *
2526:    * @param o the object to add
2527:    * @return <code>true</code>, as defined by Collection for a modified list
2528:    * @throws UnsupportedOperationException if this list does not support the
2529:    *         add operation
2530:    * @throws ClassCastException if o cannot be added to this list due to its
2531:    *         type
2532:    * @throws IllegalArgumentException if o cannot be added to this list for
2533:    *         some other reason
2534:    * @throws NullPointerException if o is null and this list doesn't support
2535:    *         the addition of null values.
2536:    */
2537:     public boolean addAll(int index, Collection c)
2538:     {
2539:       synchronized (mutex)
2540:         {
2541:           return list.addAll(index, c);
2542:         }
2543:     }
2544: 
2545:    /**
2546:     * Tests whether the underlying list is equal to the supplied object.
2547:     * The object is deemed to be equal if it is also a <code>List</code>
2548:     * of equal size and with the same elements (i.e. each element, e1,
2549:     * in list, l1, and each element, e2, in l2, must return <code>true</code> for
2550:     * <code>e1 == null ? e2 == null : e1.equals(e2)</code>.  Before the
2551:     * comparison is made, a lock is obtained on the mutex.
2552:     *
2553:     * @param o The object to test for equality with the underlying list.
2554:     * @return <code>true</code> if o is equal to the underlying list under the above
2555:     *         definition.
2556:     */
2557:     public boolean equals(Object o)
2558:     {
2559:       synchronized (mutex)
2560:         {
2561:           return list.equals(o);
2562:         }
2563:     }
2564: 
2565:     /**
2566:      * Retrieves the object at the specified index.  A lock
2567:      * is obtained on the mutex before the list is accessed.
2568:      *
2569:      * @param index the index of the element to be returned
2570:      * @return the element at index index in this list
2571:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2572:      */
2573:     public Object get(int index)
2574:     {
2575:       synchronized (mutex)
2576:         {
2577:           return list.get(index);
2578:         }
2579:     }
2580: 
2581:     /**
2582:      * Obtains a hashcode for the underlying list, first obtaining
2583:      * a lock on the mutex.  The calculation of the hashcode is
2584:      * detailed in the documentation for the <code>List</code>
2585:      * interface.
2586:      *
2587:      * @return The hashcode of the underlying list.
2588:      * @see List#hashCode()
2589:      */
2590:     public int hashCode()
2591:     {
2592:       synchronized (mutex)
2593:         {
2594:           return list.hashCode();
2595:         }
2596:     }
2597: 
2598:     /**
2599:      * Obtain the first index at which a given object is to be found in the
2600:      * underlying list.  A lock is obtained on the mutex before the list is
2601:      * accessed.
2602:      *
2603:      * @param o the object to search for
2604:      * @return the least integer n such that <code>o == null ? get(n) == null :
2605:      *         o.equals(get(n))</code>, or -1 if there is no such index.
2606:      * @throws ClassCastException if the type of o is not a valid
2607:      *         type for this list.
2608:      * @throws NullPointerException if o is null and this
2609:      *         list does not support null values.
2610:      */
2611: 
2612:     public int indexOf(Object o)
2613:     {
2614:       synchronized (mutex)
2615:         {
2616:           return list.indexOf(o);
2617:         }
2618:     }
2619: 
2620:     /**
2621:      * Obtain the last index at which a given object is to be found in this
2622:      * underlying list.  A lock is obtained on the mutex before the list
2623:      * is accessed.
2624:      *
2625:      * @return the greatest integer n such that <code>o == null ? get(n) == null
2626:      *         : o.equals(get(n))</code>, or -1 if there is no such index.
2627:      * @throws ClassCastException if the type of o is not a valid
2628:      *         type for this list.
2629:      * @throws NullPointerException if o is null and this
2630:      *         list does not support null values.
2631:      */
2632:     public int lastIndexOf(Object o)
2633:     {
2634:       synchronized (mutex)
2635:         {
2636:           return list.lastIndexOf(o);
2637:         }
2638:     }
2639: 
2640:     /**
2641:      * Retrieves a synchronized wrapper around the underlying list's
2642:      * list iterator.  A lock is obtained on the mutex before the
2643:      * list iterator is retrieved.
2644:      *
2645:      * @return A list iterator over the elements in the underlying list.
2646:      *         The list iterator allows additional list-specific operations
2647:      *         to be performed, in addition to those supplied by the
2648:      *         standard iterator.
2649:      */
2650:     public ListIterator listIterator()
2651:     {
2652:       synchronized (mutex)
2653:         {
2654:           return new SynchronizedListIterator(mutex, list.listIterator());
2655:         }
2656:     }
2657: 
2658:     /**
2659:      * Retrieves a synchronized wrapper around the underlying list's
2660:      * list iterator.  A lock is obtained on the mutex before the
2661:      * list iterator is retrieved.  The iterator starts at the
2662:      * index supplied, leading to the element at that index being
2663:      * the first one returned by <code>next()</code>.  Calling
2664:      * <code>previous()</code> from this initial position returns
2665:      * index - 1.
2666:      *
2667:      * @param index the position, between 0 and size() inclusive, to begin the
2668:      *        iteration from
2669:      * @return A list iterator over the elements in the underlying list.
2670:      *         The list iterator allows additional list-specific operations
2671:      *         to be performed, in addition to those supplied by the
2672:      *         standard iterator.
2673:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
2674:      */
2675:     public ListIterator listIterator(int index)
2676:     {
2677:       synchronized (mutex)
2678:         {
2679:           return new SynchronizedListIterator(mutex, list.listIterator(index));
2680:         }
2681:     }
2682: 
2683:     /**
2684:      * Remove the element at a given position in the underlying list (optional
2685:      * operation).  All remaining elements are shifted to the left to fill the gap.
2686:      * A lock on the mutex is obtained before the element is removed.
2687:      *
2688:      * @param index the position within the list of the object to remove
2689:      * @return the object that was removed
2690:      * @throws UnsupportedOperationException if this list does not support the
2691:      *         remove operation
2692:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2693:      */
2694:     public Object remove(int index)
2695:     {
2696:       synchronized (mutex)
2697:         {
2698:           return list.remove(index);
2699:         }
2700:     }
2701: 
2702:   /**
2703:    * Replace an element of the underlying list with another object (optional
2704:    * operation).  A lock is obtained on the mutex before the element is
2705:    * replaced.
2706:    *
2707:    * @param index the position within this list of the element to be replaced
2708:    * @param o the object to replace it with
2709:    * @return the object that was replaced
2710:    * @throws UnsupportedOperationException if this list does not support the
2711:    *         set operation.
2712:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
2713:    * @throws ClassCastException if o cannot be added to this list due to its
2714:    *         type
2715:    * @throws IllegalArgumentException if o cannot be added to this list for
2716:    *         some other reason
2717:    * @throws NullPointerException if o is null and this
2718:    *         list does not support null values.
2719:    */
2720:     public Object set(int index, Object o)
2721:     {
2722:       synchronized (mutex)
2723:         {
2724:           return list.set(index, o);
2725:         }
2726:     }
2727: 
2728:     /**
2729:      * Obtain a List view of a subsection of the underlying list, from fromIndex
2730:      * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2731:      * sublist is empty. The returned list should be modifiable if and only
2732:      * if this list is modifiable. Changes to the returned list should be
2733:      * reflected in this list. If this list is structurally modified in
2734:      * any way other than through the returned list, the result of any subsequent
2735:      * operations on the returned list is undefined.  A lock is obtained
2736:      * on the mutex before the creation of the sublist.  The returned list
2737:      * is also synchronized, using the same mutex.
2738:      *
2739:      * @param fromIndex the index that the returned list should start from
2740:      *        (inclusive)
2741:      * @param toIndex the index that the returned list should go to (exclusive)
2742:      * @return a List backed by a subsection of this list
2743:      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
2744:      *         || toIndex &gt; size() || fromIndex &gt; toIndex
2745:      */
2746:     public List subList(int fromIndex, int toIndex)
2747:     {
2748:       synchronized (mutex)
2749:         {
2750:           return new SynchronizedList(mutex, list.subList(fromIndex, toIndex));
2751:         }
2752:     }
2753:   } // class SynchronizedList
2754: 
2755:   /**
2756:    * The implementation of {@link #synchronizedList(List)} for random-access
2757:    * lists. This class name is required for compatibility with Sun's JDK
2758:    * serializability.
2759:    *
2760:    * @author Eric Blake (ebb9@email.byu.edu)
2761:    */
2762:   private static final class SynchronizedRandomAccessList
2763:     extends SynchronizedList implements RandomAccess
2764:   {
2765:     /**
2766:      * Compatible with JDK 1.4.
2767:      */
2768:     private static final long serialVersionUID = 1530674583602358482L;
2769: 
2770:     /**
2771:      * Wrap a given list.
2772:      * @param l the list to wrap
2773:      * @throws NullPointerException if l is null
2774:      */
2775:     SynchronizedRandomAccessList(List l)
2776:     {
2777:       super(l);
2778:     }
2779: 
2780:     /**
2781:      * Called only by trusted code to specify the mutex as well as the
2782:      * collection.
2783:      * @param sync the mutex
2784:      * @param l the list
2785:      */
2786:     SynchronizedRandomAccessList(Object sync, List l)
2787:     {
2788:       super(sync, l);
2789:     }
2790: 
2791:     /**
2792:      * Obtain a List view of a subsection of the underlying list, from fromIndex
2793:      * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2794:      * sublist is empty. The returned list should be modifiable if and only
2795:      * if this list is modifiable. Changes to the returned list should be
2796:      * reflected in this list. If this list is structurally modified in
2797:      * any way other than through the returned list, the result of any subsequent
2798:      * operations on the returned list is undefined.    A lock is obtained
2799:      * on the mutex before the creation of the sublist.  The returned list
2800:      * is also synchronized, using the same mutex.  Random accessibility
2801:      * is also extended to the new list.
2802:      *
2803:      * @param fromIndex the index that the returned list should start from
2804:      *        (inclusive)
2805:      * @param toIndex the index that the returned list should go to (exclusive)
2806:      * @return a List backed by a subsection of this list
2807:      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
2808:      *         || toIndex &gt; size() || fromIndex &gt; toIndex
2809:      */
2810:     public List subList(int fromIndex, int toIndex)
2811:     {
2812:       synchronized (mutex)
2813:         {
2814:           return new SynchronizedRandomAccessList(mutex,
2815:                                                   list.subList(fromIndex,
2816:                                                                toIndex));
2817:         }
2818:     }
2819:   } // class SynchronizedRandomAccessList
2820: 
2821:   /**
2822:    * The implementation of {@link SynchronizedList#listIterator()}. This
2823:    * iterator must "sync" on the same object as the list it iterates over.
2824:    *
2825:    * @author Eric Blake (ebb9@email.byu.edu)
2826:    */
2827:   private static final class SynchronizedListIterator
2828:     extends SynchronizedIterator implements ListIterator
2829:   {
2830:     /**
2831:      * The wrapped iterator, stored both here and in the superclass to
2832:      * avoid excessive casting.
2833:      */
2834:     private final ListIterator li;
2835: 
2836:     /**
2837:      * Only trusted code creates a wrapper, with the specified sync.
2838:      * @param sync the mutex
2839:      * @param li the wrapped iterator
2840:      */
2841:     SynchronizedListIterator(Object sync, ListIterator li)
2842:     {
2843:       super(sync, li);
2844:       this.li = li;
2845:     }
2846: 
2847:     /**
2848:      * Insert an element into the underlying list at the current position of
2849:      * the iterator (optional operation). The element is inserted in between
2850:      * the element that would be returned by <code>previous()</code> and the
2851:      * element that would be returned by <code>next()</code>. After the
2852:      * insertion, a subsequent call to next is unaffected, but
2853:      * a call to previous returns the item that was added. The values returned
2854:      * by nextIndex() and previousIndex() are incremented.  A lock is obtained
2855:      * on the mutex before the addition takes place.
2856:      *
2857:      * @param o the object to insert into the list
2858:      * @throws ClassCastException if the object is of a type which cannot be added
2859:      *         to this list.
2860:      * @throws IllegalArgumentException if some other aspect of the object stops
2861:      *         it being added to this list.
2862:      * @throws UnsupportedOperationException if this ListIterator does not
2863:      *         support the add operation.
2864:      */
2865:     public void add(Object o)
2866:     {
2867:       synchronized (mutex)
2868:         {
2869:           li.add(o);
2870:         }
2871:     }
2872: 
2873:     /**
2874:      * Tests whether there are elements remaining in the underlying list
2875:      * in the reverse direction. In other words, <code>previous()</code>
2876:      * will not fail with a NoSuchElementException.  A lock is obtained
2877:      * on the mutex before the check takes place.
2878:      *
2879:      * @return <code>true</code> if the list continues in the reverse direction
2880:      */
2881:     public boolean hasPrevious()
2882:     {
2883:       synchronized (mutex)
2884:         {
2885:           return li.hasPrevious();
2886:         }
2887:     }
2888: 
2889:     /**
2890:       * Find the index of the element that would be returned by a call to
2891:       * <code>next()</code>.  If hasNext() returns <code>false</code>, this
2892:       * returns the list size.  A lock is obtained on the mutex before the
2893:       * query takes place.
2894:       *
2895:       * @return the index of the element that would be returned by next()
2896:       */
2897:     public int nextIndex()
2898:     {
2899:       synchronized (mutex)
2900:         {
2901:           return li.nextIndex();
2902:         }
2903:     }
2904: 
2905:     /**
2906:      * Obtain the previous element from the underlying list. Repeated
2907:      * calls to previous may be used to iterate backwards over the entire list,
2908:      * or calls to next and previous may be used together to go forwards and
2909:      * backwards. Alternating calls to next and previous will return the same
2910:      * element.  A lock is obtained on the mutex before the object is retrieved.
2911:      *
2912:      * @return the next element in the list in the reverse direction
2913:      * @throws NoSuchElementException if there are no more elements
2914:      */
2915:     public Object previous()
2916:     {
2917:       synchronized (mutex)
2918:         {
2919:           return li.previous();
2920:         }
2921:     }
2922: 
2923:     /**
2924:      * Find the index of the element that would be returned by a call to
2925:      * previous. If hasPrevious() returns <code>false</code>, this returns -1.
2926:      * A lock is obtained on the mutex before the query takes place.
2927:      *
2928:      * @return the index of the element that would be returned by previous()
2929:      */
2930:     public int previousIndex()
2931:     {
2932:       synchronized (mutex)
2933:         {
2934:           return li.previousIndex();
2935:         }
2936:     }
2937: 
2938:     /**
2939:      * Replace the element last returned by a call to <code>next()</code> or
2940:      * <code>previous()</code> with a given object (optional operation).  This
2941:      * method may only be called if neither <code>add()</code> nor
2942:      * <code>remove()</code> have been called since the last call to
2943:      * <code>next()</code> or <code>previous</code>.  A lock is obtained
2944:      * on the mutex before the list is modified.
2945:      *
2946:      * @param o the object to replace the element with
2947:      * @throws ClassCastException the object is of a type which cannot be added
2948:      *         to this list
2949:      * @throws IllegalArgumentException some other aspect of the object stops
2950:      *         it being added to this list
2951:      * @throws IllegalStateException if neither next or previous have been
2952:      *         called, or if add or remove has been called since the last call
2953:      *         to next or previous
2954:      * @throws UnsupportedOperationException if this ListIterator does not
2955:      *         support the set operation
2956:      */
2957:     public void set(Object o)
2958:     {
2959:       synchronized (mutex)
2960:         {
2961:           li.set(o);
2962:         }
2963:     }
2964:   } // class SynchronizedListIterator
2965: 
2966:   /**
2967:    * Returns a synchronized (thread-safe) map wrapper backed by the given
2968:    * map. Notice that element access through the collection views and their
2969:    * iterators are thread-safe, but if the map can be structurally modified
2970:    * (adding or removing elements) then you should synchronize around the
2971:    * iteration to avoid non-deterministic behavior:<br>
2972:    * <pre>
2973:    * Map m = Collections.synchronizedMap(new Map(...));
2974:    * ...
2975:    * Set s = m.keySet(); // safe outside a synchronized block
2976:    * synchronized (m) // synch on m, not s
2977:    *   {
2978:    *     Iterator i = s.iterator();
2979:    *     while (i.hasNext())
2980:    *       foo(i.next());
2981:    *   }
2982:    * </pre><p>
2983:    *
2984:    * The returned Map implements Serializable, but can only be serialized if
2985:    * the map it wraps is likewise Serializable.
2986:    *
2987:    * @param m the map to wrap
2988:    * @return a synchronized view of the map
2989:    * @see Serializable
2990:    */
2991:   public static Map synchronizedMap(Map m)
2992:   {
2993:     return new SynchronizedMap(m);
2994:   }
2995: 
2996:   /**
2997:    * The implementation of {@link #synchronizedMap(Map)}. This
2998:    * class name is required for compatibility with Sun's JDK serializability.
2999:    *
3000:    * @author Eric Blake (ebb9@email.byu.edu)
3001:    */
3002:   private static class SynchronizedMap implements Map, Serializable
3003:   {
3004:     /**
3005:      * Compatible with JDK 1.4.
3006:      */
3007:     private static final long serialVersionUID = 1978198479659022715L;
3008: 
3009:     /**
3010:      * The wrapped map.
3011:      * @serial the real map
3012:      */
3013:     private final Map m;
3014: 
3015:     /**
3016:      * The object to synchronize on.  When an instance is created via public
3017:      * methods, it will be this; but other uses like
3018:      * SynchronizedSortedMap.subMap() must specify another mutex. Package
3019:      * visible for use by subclass.
3020:      * @serial the lock
3021:      */
3022:     final Object mutex;
3023: 
3024:     /**
3025:      * Cache the entry set.
3026:      */
3027:     private transient Set entries;
3028: 
3029:     /**
3030:      * Cache the key set.
3031:      */
3032:     private transient Set keys;
3033: 
3034:     /**
3035:      * Cache the value collection.
3036:      */
3037:     private transient Collection values;
3038: 
3039:     /**
3040:      * Wrap a given map.
3041:      * @param m the map to wrap
3042:      * @throws NullPointerException if m is null
3043:      */
3044:     SynchronizedMap(Map m)
3045:     {
3046:       this.m = m;
3047:       mutex = this;
3048:       if (m == null)
3049:         throw new NullPointerException();
3050:     }
3051: 
3052:     /**
3053:      * Called only by trusted code to specify the mutex as well as the map.
3054:      * @param sync the mutex
3055:      * @param m the map
3056:      */
3057:     SynchronizedMap(Object sync, Map m)
3058:     {
3059:       this.m = m;
3060:       mutex = sync;
3061:     }
3062: 
3063:     /**
3064:      * Clears all the entries from the underlying map.  A lock is obtained
3065:      * on the mutex before the map is cleared.
3066:      *
3067:      * @throws UnsupportedOperationException if clear is not supported
3068:      */
3069:     public void clear()
3070:     {
3071:       synchronized (mutex)
3072:         {
3073:           m.clear();
3074:         }
3075:     }
3076: 
3077:     /**
3078:      * Returns <code>true</code> if the underlying map contains a entry for the given key.
3079:      * A lock is obtained on the mutex before the map is queried.
3080:      *
3081:      * @param key the key to search for.
3082:      * @return <code>true</code> if the underlying map contains the key.
3083:      * @throws ClassCastException if the key is of an inappropriate type.
3084:      * @throws NullPointerException if key is <code>null</code> but the map
3085:      *         does not permit null keys.
3086:      */
3087:     public boolean containsKey(Object key)
3088:     {
3089:       synchronized (mutex)
3090:         {
3091:           return m.containsKey(key);
3092:         }
3093:     }
3094: 
3095:   /**
3096:    * Returns <code>true</code> if the underlying map contains at least one entry with the
3097:    * given value.  In other words, returns <code>true</code> if a value v exists where
3098:    * <code>(value == null ? v == null : value.equals(v))</code>. This usually
3099:    * requires linear time.  A lock is obtained on the mutex before the map
3100:    * is queried.
3101:    *
3102:    * @param value the value to search for
3103:    * @return <code>true</code> if the map contains the value
3104:    * @throws ClassCastException if the type of the value is not a valid type
3105:    *         for this map.
3106:    * @throws NullPointerException if the value is null and the map doesn't
3107:    *         support null values.
3108:    */
3109:     public boolean containsValue(Object value)
3110:     {
3111:       synchronized (mutex)
3112:         {
3113:           return m.containsValue(value);
3114:         }
3115:     }
3116: 
3117:     // This is one of the ickiest cases of nesting I've ever seen. It just
3118:     // means "return a SynchronizedSet, except that the iterator() method
3119:     // returns an SynchronizedIterator whose next() method returns a
3120:     // synchronized wrapper around its normal return value".
3121:     public Set entrySet()
3122:     {
3123:       // Define this here to spare some nesting.
3124:       class SynchronizedMapEntry implements Map.Entry
3125:       {
3126:         final Map.Entry e;
3127:         SynchronizedMapEntry(Object o)
3128:         {
3129:           e = (Map.Entry) o;
3130:         }
3131: 
3132:     /**
3133:      * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code>
3134:      * with the same key and value as the underlying entry.  A lock is
3135:      * obtained on the mutex before the comparison takes place.
3136:      *
3137:      * @param o The object to compare with this entry.
3138:      * @return <code>true</code> if o is equivalent to the underlying map entry.
3139:      */
3140:         public boolean equals(Object o)
3141:         {
3142:           synchronized (mutex)
3143:             {
3144:               return e.equals(o);
3145:             }
3146:         }
3147: 
3148:     /**
3149:      * Returns the key used in the underlying map entry.  A lock is obtained
3150:      * on the mutex before the key is retrieved.
3151:      *
3152:      * @return The key of the underlying map entry.
3153:      */
3154:         public Object getKey()
3155:         {
3156:           synchronized (mutex)
3157:             {
3158:               return e.getKey();
3159:             }
3160:         }
3161: 
3162:     /**
3163:      * Returns the value used in the underlying map entry.  A lock is obtained
3164:      * on the mutex before the value is retrieved.
3165:      *
3166:      * @return The value of the underlying map entry.
3167:      */
3168:         public Object getValue()
3169:         {
3170:           synchronized (mutex)
3171:             {
3172:               return e.getValue();
3173:             }
3174:         }
3175: 
3176:     /**
3177:      * Computes the hash code for the underlying map entry.
3178:      * This computation is described in the documentation for the
3179:      * <code>Map</code> interface.  A lock is obtained on the mutex
3180:      * before the underlying map is accessed.
3181:      *
3182:      * @return The hash code of the underlying map entry.
3183:      * @see Map#hashCode()
3184:      */
3185:         public int hashCode()
3186:         {
3187:           synchronized (mutex)
3188:             {
3189:               return e.hashCode();
3190:             }
3191:         }
3192: 
3193:     /**
3194:      * Replaces the value in the underlying map entry with the specified
3195:      * object (optional operation).  A lock is obtained on the mutex
3196:      * before the map is altered.  The map entry, in turn, will alter
3197:      * the underlying map object.  The operation is undefined if the
3198:      * <code>remove()</code> method of the iterator has been called
3199:      * beforehand.
3200:      *
3201:      * @param value the new value to store
3202:      * @return the old value
3203:      * @throws UnsupportedOperationException if the operation is not supported.
3204:      * @throws ClassCastException if the value is of the wrong type.
3205:      * @throws IllegalArgumentException if something about the value
3206:      *         prevents it from existing in this map.
3207:      * @throws NullPointerException if the map forbids null values.
3208:      */
3209:         public Object setValue(Object value)
3210:         {
3211:           synchronized (mutex)
3212:             {
3213:               return e.setValue(value);
3214:             }
3215:         }
3216: 
3217:     /**
3218:      * Returns a textual representation of the underlying map entry.
3219:      * A lock is obtained on the mutex before the entry is accessed.
3220:      *
3221:      * @return The contents of the map entry in <code>String</code> form.
3222:      */
3223:         public String toString()
3224:         {
3225:           synchronized (mutex)
3226:             {
3227:               return e.toString();
3228:             }
3229:         }
3230:       } // class SynchronizedMapEntry
3231: 
3232:       // Now the actual code.
3233:       if (entries == null)
3234:         synchronized (mutex)
3235:           {
3236:             entries = new SynchronizedSet(mutex, m.entrySet())
3237:             {
3238:           /**
3239:            * Returns an iterator over the set.  The iterator has no specific order,
3240:            * unless further specified.  A lock is obtained on the set's mutex
3241:            * before the iterator is created.  The created iterator is also
3242:            * thread-safe.
3243:            *
3244:            * @return A synchronized set iterator.
3245:            */
3246:           public Iterator iterator()
3247:               {
3248:                 synchronized (super.mutex)
3249:                   {
3250:                     return new SynchronizedIterator(super.mutex, c.iterator())
3251:                     {
3252:               /**
3253:                * Retrieves the next map entry from the iterator.
3254:                * A lock is obtained on the iterator's mutex before
3255:                * the entry is created.  The new map entry is enclosed in
3256:                * a thread-safe wrapper.
3257:                *
3258:                * @return A synchronized map entry.
3259:                */
3260:                       public Object next()
3261:                       {
3262:                         synchronized (super.mutex)
3263:                           {
3264:                             return new SynchronizedMapEntry(super.next());
3265:                           }
3266:                       }
3267:                     };
3268:                   }
3269:               }
3270:             };
3271:           }
3272:       return entries;
3273:     }
3274: 
3275:     /**
3276:      * Returns <code>true</code> if the object, o, is also an instance
3277:      * of <code>Map</code> and contains an equivalent
3278:      * entry set to that of the underlying map.  A lock
3279:      * is obtained on the mutex before the objects are
3280:      * compared.
3281:      *
3282:      * @param o The object to compare.
3283:      * @return <code>true</code> if o and the underlying map are equivalent.
3284:      */
3285:     public boolean equals(Object o)
3286:     {
3287:       synchronized (mutex)
3288:         {
3289:           return m.equals(o);
3290:         }
3291:     }
3292: 
3293:     /**
3294:      * Returns the value associated with the given key, or null
3295:      * if no such mapping exists.  An ambiguity exists with maps
3296:      * that accept null values as a return value of null could
3297:      * be due to a non-existent mapping or simply a null value
3298:      * for that key.  To resolve this, <code>containsKey</code>
3299:      * should be used.  A lock is obtained on the mutex before
3300:      * the value is retrieved from the underlying map.
3301:      *
3302:      * @param key The key of the required mapping.
3303:      * @return The value associated with the given key, or
3304:      *         null if no such mapping exists.
3305:      * @throws ClassCastException if the key is an inappropriate type.
3306:      * @throws NullPointerException if this map does not accept null keys.
3307:      */
3308:     public Object get(Object key)
3309:     {
3310:       synchronized (mutex)
3311:         {
3312:           return m.get(key);
3313:         }
3314:     }
3315: 
3316:     /**
3317:      * Calculates the hash code of the underlying map as the
3318:      * sum of the hash codes of all entries.  A lock is obtained
3319:      * on the mutex before the hash code is computed.
3320:      *
3321:      * @return The hash code of the underlying map.
3322:      */
3323:     public int hashCode()
3324:     {
3325:       synchronized (mutex)
3326:         {
3327:           return m.hashCode();
3328:         }
3329:     }
3330: 
3331:     /**
3332:      * Returns <code>true</code> if the underlying map contains no entries.
3333:      * A lock is obtained on the mutex before the map is examined.
3334:      *
3335:      * @return <code>true</code> if the map is empty.
3336:      */
3337:     public boolean isEmpty()
3338:     {
3339:       synchronized (mutex)
3340:         {
3341:           return m.isEmpty();
3342:         }
3343:     }
3344: 
3345:     /**
3346:      * Returns a thread-safe set view of the keys in the underlying map.  The
3347:      * set is backed by the map, so that changes in one show up in the other.
3348:      * Modifications made while an iterator is in progress cause undefined
3349:      * behavior.  If the set supports removal, these methods remove the
3350:      * underlying mapping from the map: <code>Iterator.remove</code>,
3351:      * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
3352:      * and <code>clear</code>.  Element addition, via <code>add</code> or
3353:      * <code>addAll</code>, is not supported via this set.  A lock is obtained
3354:      * on the mutex before the set is created.
3355:      *
3356:      * @return A synchronized set containing the keys of the underlying map.
3357:      */
3358:     public Set keySet()
3359:     {
3360:       if (keys == null)
3361:         synchronized (mutex)
3362:           {
3363:             keys = new SynchronizedSet(mutex, m.keySet());
3364:           }
3365:       return keys;
3366:     }
3367: 
3368:     /**
3369:      * Associates the given key to the given value (optional operation). If the
3370:      * underlying map already contains the key, its value is replaced. Be aware
3371:      * that in a map that permits <code>null</code> values, a null return does not
3372:      * always imply that the mapping was created.  A lock is obtained on the mutex
3373:      * before the modification is made.
3374:      *
3375:      * @param key the key to map.
3376:      * @param value the value to be mapped.
3377:      * @return the previous value of the key, or null if there was no mapping
3378:      * @throws UnsupportedOperationException if the operation is not supported
3379:      * @throws ClassCastException if the key or value is of the wrong type
3380:      * @throws IllegalArgumentException if something about this key or value
3381:      *         prevents it from existing in this map
3382:      * @throws NullPointerException if either the key or the value is null,
3383:      *         and the map forbids null keys or values
3384:      * @see #containsKey(Object)
3385:      */
3386:     public Object put(Object key, Object value)
3387:     {
3388:       synchronized (mutex)
3389:         {
3390:           return m.put(key, value);
3391:         }
3392:     }
3393: 
3394:     /**
3395:      * Copies all entries of the given map to the underlying one (optional
3396:      * operation). If the map already contains a key, its value is replaced.
3397:      * A lock is obtained on the mutex before the operation proceeds.
3398:      *
3399:      * @param map the mapping to load into this map
3400:      * @throws UnsupportedOperationException if the operation is not supported
3401:      * @throws ClassCastException if a key or value is of the wrong type
3402:      * @throws IllegalArgumentException if something about a key or value
3403:      *         prevents it from existing in this map
3404:      * @throws NullPointerException if the map forbids null keys or values, or
3405:      *         if <code>m</code> is null.
3406:      * @see #put(Object, Object)
3407:      */
3408:     public void putAll(Map map)
3409:     {
3410:       synchronized (mutex)
3411:         {
3412:           m.putAll(map);
3413:         }
3414:     }
3415: 
3416:     /**
3417:      * Removes the mapping for the key, o, if present (optional operation). If
3418:      * the key is not present, this returns null. Note that maps which permit
3419:      * null values may also return null if the key was removed.  A prior
3420:      * <code>containsKey()</code> check is required to avoid this ambiguity.
3421:      * Before the mapping is removed, a lock is obtained on the mutex.
3422:      *
3423:      * @param o the key to remove
3424:      * @return the value the key mapped to, or null if not present
3425:      * @throws UnsupportedOperationException if deletion is unsupported
3426:      * @throws NullPointerException if the key is null and this map doesn't
3427:      *         support null keys.
3428:      * @throws ClassCastException if the type of the key is not a valid type
3429:      *         for this map.
3430:      */
3431:     public Object remove(Object o)
3432:     {
3433:       synchronized (mutex)
3434:         {
3435:           return m.remove(o);
3436:         }
3437:     }
3438: 
3439:     /**
3440:      * Retrieves the size of the underlying map.  A lock
3441:      * is obtained on the mutex before access takes place.
3442:      * Maps with a size greater than <code>Integer.MAX_VALUE</code>
3443:      * return <code>Integer.MAX_VALUE</code> instead.
3444:      *
3445:      * @return The size of the underlying map.
3446:      */
3447:     public int size()
3448:     {
3449:       synchronized (mutex)
3450:         {
3451:           return m.size();
3452:         }
3453:     }
3454: 
3455:     /**
3456:      * Returns a textual representation of the underlying
3457:      * map.  A lock is obtained on the mutex before the map
3458:      * is accessed.
3459:      *
3460:      * @return The map in <code>String</code> form.
3461:      */
3462:     public String toString()
3463:     {
3464:       synchronized (mutex)
3465:         {
3466:           return m.toString();
3467:         }
3468:     }
3469: 
3470:     /**
3471:      * Returns a synchronized collection view of the values in the underlying
3472:      * map.  The collection is backed by the map, so that changes in one show up in
3473:      * the other.  Modifications made while an iterator is in progress cause
3474:      * undefined behavior.  If the collection supports removal, these methods
3475:      * remove the underlying mapping from the map: <code>Iterator.remove</code>,
3476:      * <code>Collection.remove</code>, <code>removeAll</code>,
3477:      * <code>retainAll</code>, and <code>clear</code>. Element addition, via
3478:      * <code>add</code> or <code>addAll</code>, is not supported via this
3479:      * collection.  A lock is obtained on the mutex before the collection
3480:      * is created.
3481:      * 
3482:      * @return the collection of all values in the underlying map.
3483:      */
3484:     public Collection values()
3485:     {
3486:       if (values == null)
3487:         synchronized (mutex)
3488:           {
3489:             values = new SynchronizedCollection(mutex, m.values());
3490:           }
3491:       return values;
3492:     }
3493:   } // class SynchronizedMap
3494: 
3495:   /**
3496:    * Returns a synchronized (thread-safe) set wrapper backed by the given
3497:    * set. Notice that element access through the iterator is thread-safe, but
3498:    * if the set can be structurally modified (adding or removing elements)
3499:    * then you should synchronize around the iteration to avoid
3500:    * non-deterministic behavior:<br>
3501:    * <pre>
3502:    * Set s = Collections.synchronizedSet(new Set(...));
3503:    * ...
3504:    * synchronized (s)
3505:    *   {
3506:    *     Iterator i = s.iterator();
3507:    *     while (i.hasNext())
3508:    *       foo(i.next());
3509:    *   }
3510:    * </pre><p>
3511:    *
3512:    * The returned Set implements Serializable, but can only be serialized if
3513:    * the set it wraps is likewise Serializable.
3514:    *
3515:    * @param s the set to wrap
3516:    * @return a synchronized view of the set
3517:    * @see Serializable
3518:    */
3519:   public static Set synchronizedSet(Set s)
3520:   {
3521:     return new SynchronizedSet(s);
3522:   }
3523: 
3524:   /**
3525:    * The implementation of {@link #synchronizedSet(Set)}. This class
3526:    * name is required for compatibility with Sun's JDK serializability.
3527:    * Package visible, so that sets such as Hashtable.keySet()
3528:    * can specify which object to synchronize on.
3529:    *
3530:    * @author Eric Blake (ebb9@email.byu.edu)
3531:    */
3532:   static class SynchronizedSet extends SynchronizedCollection
3533:     implements Set
3534:   {
3535:     /**
3536:      * Compatible with JDK 1.4.
3537:      */
3538:     private static final long serialVersionUID = 487447009682186044L;
3539: 
3540:     /**
3541:      * Wrap a given set.
3542:      * @param s the set to wrap
3543:      * @throws NullPointerException if s is null
3544:      */
3545:     SynchronizedSet(Set s)
3546:     {
3547:       super(s);
3548:     }
3549: 
3550:     /**
3551:      * Called only by trusted code to specify the mutex as well as the set.
3552:      * @param sync the mutex
3553:      * @param s the set
3554:      */
3555:     SynchronizedSet(Object sync, Set s)
3556:     {
3557:       super(sync, s);
3558:     }
3559: 
3560:     /**
3561:      * Returns <code>true</code> if the object, o, is a <code>Set</code>
3562:      * of the same size as the underlying set, and contains
3563:      * each element, e, which occurs in the underlying set.
3564:      * A lock is obtained on the mutex before the comparison
3565:      * takes place.
3566:      *
3567:      * @param o The object to compare against.
3568:      * @return <code>true</code> if o is an equivalent set.
3569:      */
3570:     public boolean equals(Object o)
3571:     {
3572:       synchronized (mutex)
3573:         {
3574:           return c.equals(o);
3575:         }
3576:     }
3577: 
3578:     /**
3579:      * Computes the hash code for the underlying set as the
3580:      * sum of the hash code of all elements within the set.
3581:      * A lock is obtained on the mutex before the computation
3582:      * occurs.
3583:      *
3584:      * @return The hash code for the underlying set.
3585:      */
3586:     public int hashCode()
3587:     {
3588:       synchronized (mutex)
3589:         {
3590:           return c.hashCode();
3591:         }
3592:     }
3593:   } // class SynchronizedSet
3594: 
3595:   /**
3596:    * Returns a synchronized (thread-safe) sorted map wrapper backed by the
3597:    * given map. Notice that element access through the collection views,
3598:    * subviews, and their iterators are thread-safe, but if the map can be
3599:    * structurally modified (adding or removing elements) then you should
3600:    * synchronize around the iteration to avoid non-deterministic behavior:<br>
3601:    * <pre>
3602:    * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
3603:    * ...
3604:    * Set s = m.keySet(); // safe outside a synchronized block
3605:    * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
3606:    * Set s2 = m2.keySet(); // safe outside a synchronized block
3607:    * synchronized (m) // synch on m, not m2, s or s2
3608:    *   {
3609:    *     Iterator i = s.iterator();
3610:    *     while (i.hasNext())
3611:    *       foo(i.next());
3612:    *     i = s2.iterator();
3613:    *     while (i.hasNext())
3614:    *       bar(i.next());
3615:    *   }
3616:    * </pre><p>
3617:    *
3618:    * The returned SortedMap implements Serializable, but can only be
3619:    * serialized if the map it wraps is likewise Serializable.
3620:    *
3621:    * @param m the sorted map to wrap
3622:    * @return a synchronized view of the sorted map
3623:    * @see Serializable
3624:    */
3625:   public static SortedMap synchronizedSortedMap(SortedMap m)
3626:   {
3627:     return new SynchronizedSortedMap(m);
3628:   }
3629: 
3630:   /**
3631:    * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
3632:    * class name is required for compatibility with Sun's JDK serializability.
3633:    *
3634:    * @author Eric Blake (ebb9@email.byu.edu)
3635:    */
3636:   private static final class SynchronizedSortedMap extends SynchronizedMap
3637:     implements SortedMap
3638:   {
3639:     /**
3640:      * Compatible with JDK 1.4.
3641:      */
3642:     private static final long serialVersionUID = -8798146769416483793L;
3643: 
3644:     /**
3645:      * The wrapped map; stored both here and in the superclass to avoid
3646:      * excessive casting.
3647:      * @serial the wrapped map
3648:      */
3649:     private final SortedMap sm;
3650: 
3651:     /**
3652:      * Wrap a given map.
3653:      * @param sm the map to wrap
3654:      * @throws NullPointerException if sm is null
3655:      */
3656:     SynchronizedSortedMap(SortedMap sm)
3657:     {
3658:       super(sm);
3659:       this.sm = sm;
3660:     }
3661: 
3662:     /**
3663:      * Called only by trusted code to specify the mutex as well as the map.
3664:      * @param sync the mutex
3665:      * @param sm the map
3666:      */
3667:     SynchronizedSortedMap(Object sync, SortedMap sm)
3668:     {
3669:       super(sync, sm);
3670:       this.sm = sm;
3671:     }
3672: 
3673:     /**
3674:      * Returns the comparator used in sorting the underlying map, or null if
3675:      * it is the keys' natural ordering.  A lock is obtained on the mutex
3676:      * before the comparator is retrieved.
3677:      *
3678:      * @return the sorting comparator.
3679:      */
3680:     public Comparator comparator()
3681:     {
3682:       synchronized (mutex)
3683:         {
3684:           return sm.comparator();
3685:         }
3686:     }
3687: 
3688:     /**
3689:      * Returns the first, lowest sorted, key from the underlying map.
3690:      * A lock is obtained on the mutex before the map is accessed.
3691:      *
3692:      * @return the first key.
3693:      * @throws NoSuchElementException if this map is empty.
3694:      */
3695:     public Object firstKey()
3696:     {
3697:       synchronized (mutex)
3698:         {
3699:           return sm.firstKey();
3700:         }
3701:     }
3702: 
3703:     /**
3704:      * Returns a submap containing the keys from the first
3705:      * key (as returned by <code>firstKey()</code>) to
3706:      * the key before that specified.  The submap supports all
3707:      * operations supported by the underlying map and all actions
3708:      * taking place on the submap are also reflected in the underlying
3709:      * map.  A lock is obtained on the mutex prior to submap creation.
3710:      * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>.
3711:      * The submap retains the thread-safe status of this map.
3712:      *
3713:      * @param toKey the exclusive upper range of the submap.
3714:      * @return a submap from <code>firstKey()</code> to the
3715:      *         the key preceding toKey.
3716:      * @throws ClassCastException if toKey is not comparable to the underlying
3717:      *         map's contents.
3718:      * @throws IllegalArgumentException if toKey is outside the map's range.
3719:      * @throws NullPointerException if toKey is null. but the map does not allow
3720:      *         null keys.
3721:      */
3722:     public SortedMap headMap(Object toKey)
3723:     {
3724:       synchronized (mutex)
3725:         {
3726:           return new SynchronizedSortedMap(mutex, sm.headMap(toKey));
3727:         }
3728:     }
3729: 
3730:     /**
3731:      * Returns the last, highest sorted, key from the underlying map.
3732:      * A lock is obtained on the mutex before the map is accessed.
3733:      *
3734:      * @return the last key.
3735:      * @throws NoSuchElementException if this map is empty.
3736:      */
3737:     public Object lastKey()
3738:     {
3739:       synchronized (mutex)
3740:         {
3741:           return sm.lastKey();
3742:         }
3743:     }
3744: 
3745:     /**
3746:      * Returns a submap containing the keys from fromKey to
3747:      * the key before toKey.  The submap supports all
3748:      * operations supported by the underlying map and all actions
3749:      * taking place on the submap are also reflected in the underlying
3750:      * map.  A lock is obtained on the mutex prior to submap creation.
3751:      * The submap retains the thread-safe status of this map.
3752:      *
3753:      * @param fromKey the inclusive lower range of the submap.
3754:      * @param toKey the exclusive upper range of the submap.
3755:      * @return a submap from fromKey to the key preceding toKey.
3756:      * @throws ClassCastException if fromKey or toKey is not comparable
3757:      *         to the underlying map's contents.
3758:      * @throws IllegalArgumentException if fromKey or toKey is outside the map's
3759:      *         range.
3760:      * @throws NullPointerException if fromKey or toKey is null. but the map does
3761:      *         not allow  null keys.
3762:      */
3763:     public SortedMap subMap(Object fromKey, Object toKey)
3764:     {
3765:       synchronized (mutex)
3766:         {
3767:           return new SynchronizedSortedMap(mutex, sm.subMap(fromKey, toKey));
3768:         }
3769:     }
3770: 
3771:     /**
3772:      * Returns a submap containing all the keys from fromKey onwards.
3773:      * The submap supports all operations supported by the underlying
3774:      * map and all actions taking place on the submap are also reflected
3775:      * in the underlying map.  A lock is obtained on the mutex prior to
3776:      * submap creation.  The submap retains the thread-safe status of
3777:      * this map.
3778:      *
3779:      * @param fromKey the inclusive lower range of the submap.
3780:      * @return a submap from fromKey to <code>lastKey()</code>.
3781:      * @throws ClassCastException if fromKey is not comparable to the underlying
3782:      *         map's contents.
3783:      * @throws IllegalArgumentException if fromKey is outside the map's range.
3784:      * @throws NullPointerException if fromKey is null. but the map does not allow
3785:      *         null keys.
3786:      */
3787:     public SortedMap tailMap(Object fromKey)
3788:     {
3789:       synchronized (mutex)
3790:         {
3791:           return new SynchronizedSortedMap(mutex, sm.tailMap(fromKey));
3792:         }
3793:     }
3794:   } // class SynchronizedSortedMap
3795: 
3796:   /**
3797:    * Returns a synchronized (thread-safe) sorted set wrapper backed by the
3798:    * given set. Notice that element access through the iterator and through
3799:    * subviews are thread-safe, but if the set can be structurally modified
3800:    * (adding or removing elements) then you should synchronize around the
3801:    * iteration to avoid non-deterministic behavior:<br>
3802:    * <pre>
3803:    * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
3804:    * ...
3805:    * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
3806:    * synchronized (s) // synch on s, not s2
3807:    *   {
3808:    *     Iterator i = s2.iterator();
3809:    *     while (i.hasNext())
3810:    *       foo(i.next());
3811:    *   }
3812:    * </pre><p>
3813:    *
3814:    * The returned SortedSet implements Serializable, but can only be
3815:    * serialized if the set it wraps is likewise Serializable.
3816:    *
3817:    * @param s the sorted set to wrap
3818:    * @return a synchronized view of the sorted set
3819:    * @see Serializable
3820:    */
3821:   public static SortedSet synchronizedSortedSet(SortedSet s)
3822:   {
3823:     return new SynchronizedSortedSet(s);
3824:   }
3825: 
3826:   /**
3827:    * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
3828:    * class name is required for compatibility with Sun's JDK serializability.
3829:    *
3830:    * @author Eric Blake (ebb9@email.byu.edu)
3831:    */
3832:   private static final class SynchronizedSortedSet extends SynchronizedSet
3833:     implements SortedSet
3834:   {
3835:     /**
3836:      * Compatible with JDK 1.4.
3837:      */
3838:     private static final long serialVersionUID = 8695801310862127406L;
3839: 
3840:     /**
3841:      * The wrapped set; stored both here and in the superclass to avoid
3842:      * excessive casting.
3843:      * @serial the wrapped set
3844:      */
3845:     private final SortedSet ss;
3846: 
3847:     /**
3848:      * Wrap a given set.
3849:      * @param ss the set to wrap
3850:      * @throws NullPointerException if ss is null
3851:      */
3852:     SynchronizedSortedSet(SortedSet ss)
3853:     {
3854:       super(ss);
3855:       this.ss = ss;
3856:     }
3857: 
3858:     /**
3859:      * Called only by trusted code to specify the mutex as well as the set.
3860:      * @param sync the mutex
3861:      * @param l the list
3862:      */
3863:     SynchronizedSortedSet(Object sync, SortedSet ss)
3864:     {
3865:       super(sync, ss);
3866:       this.ss = ss;
3867:     }
3868: 
3869:     /**
3870:      * Returns the comparator used in sorting the underlying set, or null if
3871:      * it is the elements' natural ordering.  A lock is obtained on the mutex
3872:      * before the comparator is retrieved.
3873:      *
3874:      * @return the sorting comparator.
3875:      */
3876:     public Comparator comparator()
3877:     {
3878:       synchronized (mutex)
3879:         {
3880:           return ss.comparator();
3881:         }
3882:     }
3883: 
3884:     /**
3885:      * Returns the first, lowest sorted, element from the underlying set.
3886:      * A lock is obtained on the mutex before the set is accessed.
3887:      *
3888:      * @return the first element.
3889:      * @throws NoSuchElementException if this set is empty.
3890:      */
3891:     public Object first()
3892:     {
3893:       synchronized (mutex)
3894:         {
3895:           return ss.first();
3896:         }
3897:     }
3898: 
3899:     /**
3900:      * Returns a subset containing the element from the first
3901:      * element (as returned by <code>first()</code>) to
3902:      * the element before that specified.  The subset supports all
3903:      * operations supported by the underlying set and all actions
3904:      * taking place on the subset are also reflected in the underlying
3905:      * set.  A lock is obtained on the mutex prior to subset creation.
3906:      * This operation is equivalent to <code>subSet(first(), toElement)</code>.
3907:      * The subset retains the thread-safe status of this set.
3908:      *
3909:      * @param toElement the exclusive upper range of the subset.
3910:      * @return a subset from <code>first()</code> to the
3911:      *         the element preceding toElement.
3912:      * @throws ClassCastException if toElement is not comparable to the underlying
3913:      *         set's contents.
3914:      * @throws IllegalArgumentException if toElement is outside the set's range.
3915:      * @throws NullPointerException if toElement is null. but the set does not allow
3916:      *         null elements.
3917:      */
3918:     public SortedSet headSet(Object toElement)
3919:     {
3920:       synchronized (mutex)
3921:         {
3922:           return new SynchronizedSortedSet(mutex, ss.headSet(toElement));
3923:         }
3924:     }
3925: 
3926:     /**
3927:      * Returns the last, highest sorted, element from the underlying set.
3928:      * A lock is obtained on the mutex before the set is accessed.
3929:      *
3930:      * @return the last element.
3931:      * @throws NoSuchElementException if this set is empty.
3932:      */
3933:     public Object last()
3934:     {
3935:       synchronized (mutex)
3936:         {
3937:           return ss.last();
3938:         }
3939:     }
3940: 
3941:     /**
3942:      * Returns a subset containing the elements from fromElement to
3943:      * the element before toElement.  The subset supports all
3944:      * operations supported by the underlying set and all actions
3945:      * taking place on the subset are also reflected in the underlying
3946:      * set.  A lock is obtained on the mutex prior to subset creation.
3947:      * The subset retains the thread-safe status of this set.
3948:      *
3949:      * @param fromElement the inclusive lower range of the subset.
3950:      * @param toElement the exclusive upper range of the subset.
3951:      * @return a subset from fromElement to the element preceding toElement.
3952:      * @throws ClassCastException if fromElement or toElement is not comparable
3953:      *         to the underlying set's contents.
3954:      * @throws IllegalArgumentException if fromElement or toElement is outside the set's
3955:      *         range.
3956:      * @throws NullPointerException if fromElement or toElement is null. but the set does
3957:      *         not allow null elements.
3958:      */
3959:     public SortedSet subSet(Object fromElement, Object toElement)
3960:     {
3961:       synchronized (mutex)
3962:         {
3963:           return new SynchronizedSortedSet(mutex,
3964:                                            ss.subSet(fromElement, toElement));
3965:         }
3966:     }
3967: 
3968:     /**
3969:      * Returns a subset containing all the elements from fromElement onwards.
3970:      * The subset supports all operations supported by the underlying
3971:      * set and all actions taking place on the subset are also reflected
3972:      * in the underlying set.  A lock is obtained on the mutex prior to
3973:      * subset creation.  The subset retains the thread-safe status of
3974:      * this set.
3975:      *
3976:      * @param fromElement the inclusive lower range of the subset.
3977:      * @return a subset from fromElement to <code>last()</code>.
3978:      * @throws ClassCastException if fromElement is not comparable to the underlying
3979:      *         set's contents.
3980:      * @throws IllegalArgumentException if fromElement is outside the set's range.
3981:      * @throws NullPointerException if fromElement is null. but the set does not allow
3982:      *         null elements.
3983:      */
3984:     public SortedSet tailSet(Object fromElement)
3985:     {
3986:       synchronized (mutex)
3987:         {
3988:           return new SynchronizedSortedSet(mutex, ss.tailSet(fromElement));
3989:         }
3990:     }
3991:   } // class SynchronizedSortedSet
3992: 
3993: 
3994:   /**
3995:    * Returns an unmodifiable view of the given collection. This allows
3996:    * "read-only" access, although changes in the backing collection show up
3997:    * in this view. Attempts to modify the collection directly or via iterators
3998:    * will fail with {@link UnsupportedOperationException}.  Although this view
3999:    * prevents changes to the structure of the collection and its elements, the values
4000:    * referenced by the objects in the collection can still be modified.
4001:    * <p>
4002:    *
4003:    * Since the collection might be a List or a Set, and those have incompatible
4004:    * equals and hashCode requirements, this relies on Object's implementation
4005:    * rather than passing those calls on to the wrapped collection. The returned
4006:    * Collection implements Serializable, but can only be serialized if
4007:    * the collection it wraps is likewise Serializable.
4008:    *
4009:    * @param c the collection to wrap
4010:    * @return a read-only view of the collection
4011:    * @see Serializable
4012:    */
4013:   public static Collection unmodifiableCollection(Collection c)
4014:   {
4015:     return new UnmodifiableCollection(c);
4016:   }
4017: 
4018:   /**
4019:    * The implementation of {@link #unmodifiableCollection(Collection)}. This
4020:    * class name is required for compatibility with Sun's JDK serializability.
4021:    *
4022:    * @author Eric Blake (ebb9@email.byu.edu)
4023:    */
4024:   private static class UnmodifiableCollection
4025:     implements Collection, Serializable
4026:   {
4027:     /**
4028:      * Compatible with JDK 1.4.
4029:      */
4030:     private static final long serialVersionUID = 1820017752578914078L;
4031: 
4032:     /**
4033:      * The wrapped collection. Package visible for use by subclasses.
4034:      * @serial the real collection
4035:      */
4036:     final Collection c;
4037: 
4038:     /**
4039:      * Wrap a given collection.
4040:      * @param c the collection to wrap
4041:      * @throws NullPointerException if c is null
4042:      */
4043:     UnmodifiableCollection(Collection c)
4044:     {
4045:       this.c = c;
4046:       if (c == null)
4047:         throw new NullPointerException();
4048:     }
4049: 
4050:     /**
4051:      * Blocks the addition of elements to the underlying collection.
4052:      * This method never returns, throwing an exception instead.
4053:      *
4054:      * @param o the object to add.
4055:      * @return <code>true</code> if the collection was modified as a result of this action.
4056:      * @throws UnsupportedOperationException as an unmodifiable collection does not
4057:      *         support the add operation.
4058:      */
4059:     public boolean add(Object o)
4060:     {
4061:       throw new UnsupportedOperationException();
4062:     }
4063: 
4064:     /**
4065:      * Blocks the addition of a collection of elements to the underlying
4066:      * collection.  This method never returns, throwing an exception instead.
4067:      *
4068:      * @param c the collection to add.
4069:      * @return <code>true</code> if the collection was modified as a result of this action.
4070:      * @throws UnsupportedOperationException as an unmodifiable collection does not
4071:      *         support the <code>addAll</code> operation.
4072:      */
4073:     public boolean addAll(Collection c)
4074:     {
4075:       throw new UnsupportedOperationException();
4076:     }
4077: 
4078:     /**
4079:      * Blocks the clearing of the underlying collection.  This method never
4080:      * returns, throwing an exception instead.
4081:      *
4082:      * @throws UnsupportedOperationException as an unmodifiable collection does
4083:      *         not support the <code>clear()</code> operation.
4084:      */
4085:     public void clear()
4086:     {
4087:       throw new UnsupportedOperationException();
4088:     }
4089: 
4090:     /**
4091:      * Test whether the underlying collection contains a given object as one of its
4092:      * elements.
4093:      *
4094:      * @param o the element to look for.
4095:      * @return <code>true</code> if the underlying collection contains at least
4096:      *         one element e such that
4097:      *         <code>o == null ? e == null : o.equals(e)</code>.
4098:      * @throws ClassCastException if the type of o is not a valid type for the
4099:      *         underlying collection.
4100:      * @throws NullPointerException if o is null and the underlying collection
4101:      *         doesn't support null values.
4102:      */
4103:     public boolean contains(Object o)
4104:     {
4105:       return c.contains(o);
4106:     }
4107: 
4108:     /**
4109:      * Test whether the underlying collection contains every element in a given
4110:      * collection.
4111:      *
4112:      * @param c1 the collection to test for.
4113:      * @return <code>true</code> if for every element o in c, contains(o) would
4114:      *         return <code>true</code>.
4115:      * @throws ClassCastException if the type of any element in c is not a valid
4116:      *   type for the underlying collection.
4117:      * @throws NullPointerException if some element of c is null and the underlying
4118:      *   collection does not support null values.
4119:      * @throws NullPointerException if c itself is null.
4120:      */
4121:     public boolean containsAll(Collection c1)
4122:     {
4123:       return c.containsAll(c1);
4124:     }
4125: 
4126:     /**
4127:      * Tests whether the underlying collection is empty, that is,
4128:      * if size() == 0.
4129:      *
4130:      * @return <code>true</code> if this collection contains no elements.
4131:      */
4132:     public boolean isEmpty()
4133:     {
4134:       return c.isEmpty();
4135:     }
4136: 
4137:     /**
4138:      * Obtain an Iterator over the underlying collection, which maintains
4139:      * its unmodifiable nature.
4140:      *
4141:      * @return an UnmodifiableIterator over the elements of the underlying
4142:      *         collection, in any order.
4143:      */
4144:     public Iterator iterator()
4145:     {
4146:       return new UnmodifiableIterator(c.iterator());
4147:     }
4148: 
4149:     /**
4150:      * Blocks the removal of an object from the underlying collection.
4151:      * This method never returns, throwing an exception instead.
4152:      *
4153:      * @param o The object to remove.
4154:      * @return <code>true</code> if the object was removed (i.e. the underlying
4155:      *         collection returned 1 or more instances of o).
4156:      * @throws UnsupportedOperationException as an unmodifiable collection
4157:      *         does not support the <code>remove()</code> operation.
4158:      */
4159:     public boolean remove(Object o)
4160:     {
4161:       throw new UnsupportedOperationException();
4162:     }
4163: 
4164:     /**
4165:      * Blocks the removal of a collection of objects from the underlying
4166:      * collection.  This method never returns, throwing an exception
4167:      * instead.
4168:      *
4169:      * @param c The collection of objects to remove.
4170:      * @return <code>true</code> if the collection was modified.
4171:      * @throws UnsupportedOperationException as an unmodifiable collection
4172:      *         does not support the <code>removeAll()</code> operation.
4173:      */
4174:     public boolean removeAll(Collection c)
4175:     {
4176:       throw new UnsupportedOperationException();
4177:     }
4178: 
4179:     /**
4180:      * Blocks the removal of all elements from the underlying collection,
4181:      * except those in the supplied collection.  This method never returns,
4182:      * throwing an exception instead.
4183:      *
4184:      * @param c The collection of objects to retain.
4185:      * @return <code>true</code> if the collection was modified.
4186:      * @throws UnsupportedOperationException as an unmodifiable collection
4187:      *         does not support the <code>retainAll()</code> operation.
4188:      */
4189:     public boolean retainAll(Collection c)
4190:     {
4191:       throw new UnsupportedOperationException();
4192:     }
4193: 
4194:     /**
4195:      * Retrieves the number of elements in the underlying collection.
4196:      *
4197:      * @return the number of elements in the collection.
4198:      */
4199:     public int size()
4200:     {
4201:       return c.size();
4202:     }
4203: 
4204:     /**
4205:      * Copy the current contents of the underlying collection into an array.
4206:      *
4207:      * @return an array of type Object[] with a length equal to the size of the
4208:      *         underlying collection and containing the elements currently in
4209:      *         the underlying collection, in any order.
4210:      */
4211:     public Object[] toArray()
4212:     {
4213:       return c.toArray();
4214:     }
4215: 
4216:     /**
4217:      * Copy the current contents of the underlying collection into an array.  If
4218:      * the array passed as an argument has length less than the size of the
4219:      * underlying collection, an array of the same run-time type as a, with a length
4220:      * equal to the size of the underlying collection, is allocated using reflection.
4221:      * Otherwise, a itself is used.  The elements of the underlying collection are
4222:      * copied into it, and if there is space in the array, the following element is
4223:      * set to null. The resultant array is returned.
4224:      * Note: The fact that the following element is set to null is only useful
4225:      * if it is known that this collection does not contain any null elements.
4226:      *
4227:      * @param a the array to copy this collection into.
4228:      * @return an array containing the elements currently in the underlying
4229:      *         collection, in any order.
4230:      * @throws ArrayStoreException if the type of any element of the
4231:      *         collection is not a subtype of the element type of a.
4232:      */
4233:     public Object[] toArray(Object[] a)
4234:     {
4235:       return c.toArray(a);
4236:     }
4237: 
4238:     /**
4239:      * A textual representation of the unmodifiable collection.
4240:      *
4241:      * @return The unmodifiable collection in the form of a <code>String</code>.
4242:      */
4243:     public String toString()
4244:     {
4245:       return c.toString();
4246:     }
4247:   } // class UnmodifiableCollection
4248: 
4249:   /**
4250:    * The implementation of the various iterator methods in the
4251:    * unmodifiable classes.
4252:    *
4253:    * @author Eric Blake (ebb9@email.byu.edu)
4254:    */
4255:   private static class UnmodifiableIterator implements Iterator
4256:   {
4257:     /**
4258:      * The wrapped iterator.
4259:      */
4260:     private final Iterator i;
4261: 
4262:     /**
4263:      * Only trusted code creates a wrapper.
4264:      * @param i the wrapped iterator
4265:      */
4266:     UnmodifiableIterator(Iterator i)
4267:     {
4268:       this.i = i;
4269:     }
4270: 
4271:     /**
4272:      * Obtains the next element in the underlying collection.
4273:      *
4274:      * @return the next element in the collection.
4275:      * @throws NoSuchElementException if there are no more elements.
4276:      */
4277:     public Object next()
4278:     {
4279:       return i.next();
4280:     }
4281:     /**
4282:      * Tests whether there are still elements to be retrieved from the
4283:      * underlying collection by <code>next()</code>.  When this method
4284:      * returns <code>true</code>, an exception will not be thrown on calling
4285:      * <code>next()</code>.
4286:      *
4287:      * @return <code>true</code> if there is at least one more element in the underlying
4288:      *         collection.
4289:      */
4290:     public boolean hasNext()
4291:     {
4292:       return i.hasNext();
4293:     }
4294: 
4295:     /**
4296:      * Blocks the removal of elements from the underlying collection by the
4297:      * iterator.
4298:      *
4299:      * @throws UnsupportedOperationException as an unmodifiable collection
4300:      *         does not support the removal of elements by its iterator.
4301:      */
4302:     public void remove()
4303:     {
4304:       throw new UnsupportedOperationException();
4305:     }
4306:   } // class UnmodifiableIterator
4307: 
4308:   /**
4309:    * Returns an unmodifiable view of the given list. This allows
4310:    * "read-only" access, although changes in the backing list show up
4311:    * in this view. Attempts to modify the list directly, via iterators, or
4312:    * via sublists, will fail with {@link UnsupportedOperationException}.
4313:    * Although this view prevents changes to the structure of the list and
4314:    * its elements, the values referenced by the objects in the list can
4315:    * still be modified.   
4316:    * <p>
4317:    *
4318:    * The returned List implements Serializable, but can only be serialized if
4319:    * the list it wraps is likewise Serializable. In addition, if the wrapped
4320:    * list implements RandomAccess, this does too.
4321:    *
4322:    * @param l the list to wrap
4323:    * @return a read-only view of the list
4324:    * @see Serializable
4325:    * @see RandomAccess
4326:    */
4327:   public static List unmodifiableList(List l)
4328:   {
4329:     if (l instanceof RandomAccess)
4330:       return new UnmodifiableRandomAccessList(l);
4331:     return new UnmodifiableList(l);
4332:   }
4333: 
4334:   /**
4335:    * The implementation of {@link #unmodifiableList(List)} for sequential
4336:    * lists. This class name is required for compatibility with Sun's JDK
4337:    * serializability.
4338:    *
4339:    * @author Eric Blake (ebb9@email.byu.edu)
4340:    */
4341:   private static class UnmodifiableList extends UnmodifiableCollection
4342:     implements List
4343:   {
4344:     /**
4345:      * Compatible with JDK 1.4.
4346:      */
4347:     private static final long serialVersionUID = -283967356065247728L;
4348: 
4349: 
4350:     /**
4351:      * The wrapped list; stored both here and in the superclass to avoid
4352:      * excessive casting. Package visible for use by subclass.
4353:      * @serial the wrapped list
4354:      */
4355:     final List list;
4356: 
4357:     /**
4358:      * Wrap a given list.
4359:      * @param l the list to wrap
4360:      * @throws NullPointerException if l is null
4361:      */
4362:     UnmodifiableList(List l)
4363:     {
4364:       super(l);
4365:       list = l;
4366:     }
4367: 
4368:     /**
4369:      * Blocks the addition of an element to the underlying
4370:      * list at a specific index.  This method never returns,
4371:      * throwing an exception instead.
4372:      *
4373:      * @param index The index at which to place the new element.
4374:      * @param o the object to add.
4375:      * @throws UnsupportedOperationException as an unmodifiable
4376:      *         list doesn't support the <code>add()</code> operation.
4377:      */
4378:     public void add(int index, Object o)
4379:     {
4380:       throw new UnsupportedOperationException();
4381:     }
4382: 
4383:     /**
4384:      * Blocks the addition of a collection of elements to the
4385:      * underlying list at a specific index.  This method never
4386:      * returns, throwing an exception instead.
4387:      *
4388:      * @param index The index at which to place the new element.
4389:      * @param c the collections of objects to add.
4390:      * @throws UnsupportedOperationException as an unmodifiable
4391:      *         list doesn't support the <code>addAll()</code> operation.
4392:      */
4393:     public boolean addAll(int index, Collection c)
4394:     {
4395:       throw new UnsupportedOperationException();
4396:     }
4397: 
4398:     /**
4399:      * Returns <code>true</code> if the object, o, is an instance of
4400:      * <code>List</code> with the same size and elements
4401:      * as the underlying list.
4402:      *
4403:      * @param o The object to compare.
4404:      * @return <code>true</code> if o is equivalent to the underlying list.
4405:      */
4406:     public boolean equals(Object o)
4407:     {
4408:       return list.equals(o);
4409:     }
4410: 
4411:     /**
4412:      * Retrieves the element at a given index in the underlying list.
4413:      *
4414:      * @param index the index of the element to be returned
4415:      * @return the element at index index in this list
4416:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
4417:      */
4418:     public Object get(int index)
4419:     {
4420:       return list.get(index);
4421:     }
4422: 
4423:     /**
4424:      * Computes the hash code for the underlying list.
4425:      * The exact computation is described in the documentation
4426:      * of the <code>List</code> interface.
4427:      *
4428:      * @return The hash code of the underlying list.
4429:      * @see List#hashCode()
4430:      */
4431:     public int hashCode()
4432:     {
4433:       return list.hashCode();
4434:     }
4435: 
4436:     /**
4437:      * Obtain the first index at which a given object is to be found in the
4438:      * underlying list.
4439:      *
4440:      * @param o the object to search for
4441:      * @return the least integer n such that <code>o == null ? get(n) == null :
4442:      *         o.equals(get(n))</code>, or -1 if there is no such index.
4443:      * @throws ClassCastException if the type of o is not a valid
4444:      *         type for the underlying list.
4445:      * @throws NullPointerException if o is null and the underlying
4446:      *         list does not support null values.
4447:      */
4448:     public int indexOf(Object o)
4449:     {
4450:       return list.indexOf(o);
4451:     }
4452: 
4453:     /**
4454:      * Obtain the last index at which a given object is to be found in the
4455:      * underlying list.
4456:      *
4457:      * @return the greatest integer n such that <code>o == null ? get(n) == null
4458:      *         : o.equals(get(n))</code>, or -1 if there is no such index.
4459:      * @throws ClassCastException if the type of o is not a valid
4460:      *         type for the underlying list.
4461:      * @throws NullPointerException if o is null and the underlying
4462:      *         list does not support null values.
4463:      */
4464:     public int lastIndexOf(Object o)
4465:     {
4466:       return list.lastIndexOf(o);
4467:     }
4468: 
4469:   /**
4470:    * Obtains a list iterator over the underlying list, starting at the beginning
4471:    * and maintaining the unmodifiable nature of this list.
4472:    *
4473:    * @return a <code>UnmodifiableListIterator</code> over the elements of the
4474:    *         underlying list, in order, starting at the beginning.
4475:    */
4476:     public ListIterator listIterator()
4477:     {
4478:       return new UnmodifiableListIterator(list.listIterator());
4479:     }
4480: 
4481:   /**
4482:    * Obtains a list iterator over the underlying list, starting at the specified
4483:    * index and maintaining the unmodifiable nature of this list.  An initial call
4484:    * to <code>next()</code> will retrieve the element at the specified index,
4485:    * and an initial call to <code>previous()</code> will retrieve the element
4486:    * at index - 1.
4487:    *
4488:    *
4489:    * @param index the position, between 0 and size() inclusive, to begin the
4490:    *        iteration from.
4491:    * @return a <code>UnmodifiableListIterator</code> over the elements of the
4492:    *         underlying list, in order, starting at the specified index.
4493:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
4494:    */
4495:     public ListIterator listIterator(int index)
4496:     {
4497:       return new UnmodifiableListIterator(list.listIterator(index));
4498:     }
4499: 
4500:     /**
4501:      * Blocks the removal of the element at the specified index.
4502:      * This method never returns, throwing an exception instead.
4503:      *
4504:      * @param index The index of the element to remove.
4505:      * @return the removed element.
4506:      * @throws UnsupportedOperationException as an unmodifiable
4507:      *         list does not support the <code>remove()</code>
4508:      *         operation.
4509:      */
4510:     public Object remove(int index)
4511:     {
4512:       throw new UnsupportedOperationException();
4513:     }
4514: 
4515:     /**
4516:      * Blocks the replacement of the element at the specified index.
4517:      * This method never returns, throwing an exception instead.
4518:      *
4519:      * @param index The index of the element to replace.
4520:      * @param o The new object to place at the specified index.
4521:      * @return the replaced element.
4522:      * @throws UnsupportedOperationException as an unmodifiable
4523:      *         list does not support the <code>set()</code>
4524:      *         operation.
4525:      */
4526:     public Object set(int index, Object o)
4527:     {
4528:       throw new UnsupportedOperationException();
4529:     }
4530: 
4531:     /**
4532:      * Obtain a List view of a subsection of the underlying list, from
4533:      * fromIndex (inclusive) to toIndex (exclusive). If the two indices
4534:      * are equal, the sublist is empty. The returned list will be
4535:      * unmodifiable, like this list.  Changes to the elements of the
4536:      * returned list will be reflected in the underlying list. No structural
4537:      * modifications can take place in either list.
4538:      *
4539:      * @param fromIndex the index that the returned list should start from
4540:      *        (inclusive).
4541:      * @param toIndex the index that the returned list should go to (exclusive).
4542:      * @return a List backed by a subsection of the underlying list.
4543:      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
4544:      *         || toIndex &gt; size() || fromIndex &gt; toIndex.
4545:      */
4546:     public List subList(int fromIndex, int toIndex)
4547:     {
4548:       return unmodifiableList(list.subList(fromIndex, toIndex));
4549:     }
4550:   } // class UnmodifiableList
4551: 
4552:   /**
4553:    * The implementation of {@link #unmodifiableList(List)} for random-access
4554:    * lists. This class name is required for compatibility with Sun's JDK
4555:    * serializability.
4556:    *
4557:    * @author Eric Blake (ebb9@email.byu.edu)
4558:    */
4559:   private static final class UnmodifiableRandomAccessList
4560:     extends UnmodifiableList implements RandomAccess
4561:   {
4562:     /**
4563:      * Compatible with JDK 1.4.
4564:      */
4565:     private static final long serialVersionUID = -2542308836966382001L;
4566: 
4567:     /**
4568:      * Wrap a given list.
4569:      * @param l the list to wrap
4570:      * @throws NullPointerException if l is null
4571:      */
4572:     UnmodifiableRandomAccessList(List l)
4573:     {
4574:       super(l);
4575:     }
4576:   } // class UnmodifiableRandomAccessList
4577: 
4578:   /**
4579:    * The implementation of {@link UnmodifiableList#listIterator()}.
4580:    *
4581:    * @author Eric Blake (ebb9@email.byu.edu)
4582:    */
4583:   private static final class UnmodifiableListIterator
4584:     extends UnmodifiableIterator implements ListIterator
4585:   {
4586:     /**
4587:      * The wrapped iterator, stored both here and in the superclass to
4588:      * avoid excessive casting.
4589:      */
4590:     private final ListIterator li;
4591: 
4592:     /**
4593:      * Only trusted code creates a wrapper.
4594:      * @param li the wrapped iterator
4595:      */
4596:     UnmodifiableListIterator(ListIterator li)
4597:     {
4598:       super(li);
4599:       this.li = li;
4600:     }
4601: 
4602:     /**
4603:      * Blocks the addition of an object to the list underlying this iterator.
4604:      * This method never returns, throwing an exception instead.
4605:      *
4606:      * @param o The object to add.
4607:      * @throws UnsupportedOperationException as the iterator of an unmodifiable
4608:      *         list does not support the <code>add()</code> operation.
4609:      */
4610:     public void add(Object o)
4611:     {
4612:       throw new UnsupportedOperationException();
4613:     }
4614: 
4615:     /**
4616:      * Tests whether there are still elements to be retrieved from the
4617:      * underlying collection by <code>previous()</code>.  When this method
4618:      * returns <code>true</code>, an exception will not be thrown on calling
4619:      * <code>previous()</code>.
4620:      *
4621:      * @return <code>true</code> if there is at least one more element prior to the
4622:      *         current position in the underlying list.
4623:      */
4624:     public boolean hasPrevious()
4625:     {
4626:       return li.hasPrevious();
4627:     }
4628: 
4629:     /**
4630:      * Find the index of the element that would be returned by a call to next.
4631:      * If <code>hasNext()</code> returns <code>false</code>, this returns the list size.
4632:      *
4633:      * @return the index of the element that would be returned by
4634:      *         <code>next()</code>.
4635:      */
4636:     public int nextIndex()
4637:     {
4638:       return li.nextIndex();
4639:     }
4640: 
4641:     /**
4642:      * Obtains the previous element in the underlying list.
4643:      *
4644:      * @return the previous element in the list.
4645:      * @throws NoSuchElementException if there are no more prior elements.
4646:      */
4647:     public Object previous()
4648:     {
4649:       return li.previous();
4650:     }
4651: 
4652:     /**
4653:      * Find the index of the element that would be returned by a call to
4654:      * previous. If <code>hasPrevious()</code> returns <code>false</code>,
4655:      * this returns -1.
4656:      *
4657:      * @return the index of the element that would be returned by
4658:      *         <code>previous()</code>.
4659:      */
4660:     public int previousIndex()
4661:     {
4662:       return li.previousIndex();
4663:     }
4664: 
4665:     /**
4666:      * Blocks the replacement of an element in the list underlying this
4667:      * iterator.  This method never returns, throwing an exception instead.
4668:      *
4669:      * @param o The new object to replace the existing one.
4670:      * @throws UnsupportedOperationException as the iterator of an unmodifiable
4671:      *         list does not support the <code>set()</code> operation.
4672:      */
4673:     public void set(Object o)
4674:     {
4675:       throw new UnsupportedOperationException();
4676:     }
4677:   } // class UnmodifiableListIterator
4678: 
4679:   /**
4680:    * Returns an unmodifiable view of the given map. This allows "read-only"
4681:    * access, although changes in the backing map show up in this view.
4682:    * Attempts to modify the map directly, or via collection views or their
4683:    * iterators will fail with {@link UnsupportedOperationException}.
4684:    * Although this view prevents changes to the structure of the map and its
4685:    * entries, the values referenced by the objects in the map can still be
4686:    * modified.   
4687:    * <p>
4688:    *
4689:    * The returned Map implements Serializable, but can only be serialized if
4690:    * the map it wraps is likewise Serializable.
4691:    *
4692:    * @param m the map to wrap
4693:    * @return a read-only view of the map
4694:    * @see Serializable
4695:    */
4696:   public static Map unmodifiableMap(Map m)
4697:   {
4698:     return new UnmodifiableMap(m);
4699:   }
4700: 
4701:   /**
4702:    * The implementation of {@link #unmodifiableMap(Map)}. This
4703:    * class name is required for compatibility with Sun's JDK serializability.
4704:    *
4705:    * @author Eric Blake (ebb9@email.byu.edu)
4706:    */
4707:   private static class UnmodifiableMap implements Map, Serializable
4708:   {
4709:     /**
4710:      * Compatible with JDK 1.4.
4711:      */
4712:     private static final long serialVersionUID = -1034234728574286014L;
4713: 
4714:     /**
4715:      * The wrapped map.
4716:      * @serial the real map
4717:      */
4718:     private final Map m;
4719: 
4720:     /**
4721:      * Cache the entry set.
4722:      */
4723:     private transient Set entries;
4724: 
4725:     /**
4726:      * Cache the key set.
4727:      */
4728:     private transient Set keys;
4729: 
4730:     /**
4731:      * Cache the value collection.
4732:      */
4733:     private transient Collection values;
4734: 
4735:     /**
4736:      * Wrap a given map.
4737:      * @param m the map to wrap
4738:      * @throws NullPointerException if m is null
4739:      */
4740:     UnmodifiableMap(Map m)
4741:     {
4742:       this.m = m;
4743:       if (m == null)
4744:         throw new NullPointerException();
4745:     }
4746: 
4747:     /**
4748:      * Blocks the clearing of entries from the underlying map.
4749:      * This method never returns, throwing an exception instead.
4750:      *
4751:      * @throws UnsupportedOperationException as an unmodifiable
4752:      *         map does not support the <code>clear()</code> operation.
4753:      */
4754:     public void clear()
4755:     {
4756:       throw new UnsupportedOperationException();
4757:     }
4758: 
4759:     /**
4760:      * Returns <code>true</code> if the underlying map contains a mapping for
4761:      * the given key.
4762:      *
4763:      * @param key the key to search for
4764:      * @return <code>true</code> if the map contains the key
4765:      * @throws ClassCastException if the key is of an inappropriate type
4766:      * @throws NullPointerException if key is <code>null</code> but the map
4767:      *         does not permit null keys
4768:      */
4769:     public boolean containsKey(Object key)
4770:     {
4771:       return m.containsKey(key);
4772:     }
4773: 
4774:     /**
4775:      * Returns <code>true</code> if the underlying map contains at least one mapping with
4776:      * the given value.  In other words, it returns <code>true</code> if a value v exists where
4777:      * <code>(value == null ? v == null : value.equals(v))</code>. This usually
4778:      * requires linear time.
4779:      *
4780:      * @param value the value to search for
4781:      * @return <code>true</code> if the map contains the value
4782:      * @throws ClassCastException if the type of the value is not a valid type
4783:      *         for this map.
4784:      * @throws NullPointerException if the value is null and the map doesn't
4785:      *         support null values.
4786:      */
4787:     public boolean containsValue(Object value)
4788:     {
4789:       return m.containsValue(value);
4790:     }
4791: 
4792:     /**
4793:      * Returns a unmodifiable set view of the entries in the underlying map.
4794:      * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>.
4795:      * The set is backed by the map, so that changes in one show up in the other.
4796:      * Modifications made while an iterator is in progress cause undefined
4797:      * behavior.  These modifications are again limited to the values of
4798:      * the objects.
4799:      *
4800:      * @return the unmodifiable set view of all mapping entries.
4801:      * @see Map.Entry
4802:      */
4803:     public Set entrySet()
4804:     {
4805:       if (entries == null)
4806:         entries = new UnmodifiableEntrySet(m.entrySet());
4807:       return entries;
4808:     }
4809: 
4810:     /**
4811:      * The implementation of {@link UnmodifiableMap#entrySet()}. This class
4812:      * name is required for compatibility with Sun's JDK serializability.
4813:      *
4814:      * @author Eric Blake (ebb9@email.byu.edu)
4815:      */
4816:     private static final class UnmodifiableEntrySet extends UnmodifiableSet
4817:       implements Serializable
4818:     {
4819:       /**
4820:        * Compatible with JDK 1.4.
4821:        */
4822:       private static final long serialVersionUID = 7854390611657943733L;
4823: 
4824:       /**
4825:        * Wrap a given set.
4826:        * @param s the set to wrap
4827:        */
4828:       UnmodifiableEntrySet(Set s)
4829:       {
4830:         super(s);
4831:       }
4832: 
4833:       // The iterator must return unmodifiable map entries.
4834:       public Iterator iterator()
4835:       {
4836:         return new UnmodifiableIterator(c.iterator())
4837:     {
4838:       /**
4839:        * Obtains the next element from the underlying set of
4840:        * map entries.
4841:        *
4842:        * @return the next element in the collection.
4843:        * @throws NoSuchElementException if there are no more elements.
4844:        */
4845:           public Object next()
4846:           {
4847:             final Map.Entry e = (Map.Entry) super.next();
4848:             return new Map.Entry()
4849:         {
4850:           /**
4851:            * Returns <code>true</code> if the object, o, is also a map entry with an
4852:            * identical key and value.
4853:            *
4854:            * @param o the object to compare.
4855:            * @return <code>true</code> if o is an equivalent map entry.
4856:            */
4857:               public boolean equals(Object o)
4858:               {
4859:                 return e.equals(o);
4860:               }
4861:           
4862:           /**
4863:            * Returns the key of this map entry.
4864:            *
4865:            * @return the key.
4866:            */
4867:               public Object getKey()
4868:               {
4869:                 return e.getKey();
4870:               }
4871: 
4872:           /**
4873:            * Returns the value of this map entry.
4874:            *
4875:            * @return the value.
4876:            */
4877:               public Object getValue()
4878:               {
4879:                 return e.getValue();
4880:               }
4881: 
4882:           /**
4883:            * Computes the hash code of this map entry.
4884:            * The computation is described in the <code>Map</code>
4885:            * interface documentation.
4886:            *
4887:            * @return the hash code of this entry.
4888:            * @see Map#hashCode()
4889:            */
4890:               public int hashCode()
4891:               {
4892:                 return e.hashCode();
4893:               }
4894: 
4895:           /**
4896:            * Blocks the alteration of the value of this map entry.
4897:            * This method never returns, throwing an exception instead.
4898:            *
4899:            * @param value The new value.
4900:            * @throws UnsupportedOperationException as an unmodifiable
4901:            *         map entry does not support the <code>setValue()</code>
4902:            *         operation.
4903:            */
4904:               public Object setValue(Object value)
4905:               {
4906:                 throw new UnsupportedOperationException();
4907:               }
4908: 
4909:           /**
4910:            * Returns a textual representation of the map entry.
4911:            *
4912:            * @return The map entry as a <code>String</code>.
4913:            */
4914:               public String toString()
4915:               {
4916:                 return e.toString();
4917:               }
4918:         };
4919:           }
4920:     };
4921:       }
4922:     } // class UnmodifiableEntrySet
4923: 
4924:     /**
4925:      * Returns <code>true</code> if the object, o, is also an instance
4926:      * of <code>Map</code> with an equal set of map entries.
4927:      *
4928:      * @param o The object to compare.
4929:      * @return <code>true</code> if o is an equivalent map.
4930:      */
4931:     public boolean equals(Object o)
4932:     {
4933:       return m.equals(o);
4934:     }
4935: 
4936:     /**
4937:      * Returns the value associated with the supplied key or
4938:      * null if no such mapping exists.  An ambiguity can occur
4939:      * if null values are accepted by the underlying map.
4940:      * In this case, <code>containsKey()</code> can be used
4941:      * to separate the two possible cases of a null result.
4942:      *
4943:      * @param key The key to look up.
4944:      * @return the value associated with the key, or null if key not in map.
4945:      * @throws ClassCastException if the key is an inappropriate type.
4946:      * @throws NullPointerException if this map does not accept null keys.
4947:      * @see #containsKey(Object)
4948:      */
4949:     public Object get(Object key)
4950:     {
4951:       return m.get(key);
4952:     }
4953: 
4954:     /**
4955:      * Blocks the addition of a new entry to the underlying map.
4956:      * This method never returns, throwing an exception instead.
4957:      *
4958:      * @param key The new key.
4959:      * @param value The new value.
4960:      * @return the previous value of the key, or null if there was no mapping.
4961:      * @throws UnsupportedOperationException as an unmodifiable
4962:      *         map does not support the <code>put()</code> operation.
4963:      */
4964:     public Object put(Object key, Object value)
4965:     {
4966:       throw new UnsupportedOperationException();
4967:     }
4968: 
4969:     /**
4970:      * Computes the hash code for the underlying map, as the sum
4971:      * of the hash codes of all entries.
4972:      *
4973:      * @return The hash code of the underlying map.
4974:      * @see Map.Entry#hashCode()
4975:      */
4976:     public int hashCode()
4977:     {
4978:       return m.hashCode();
4979:     }
4980: 
4981:     /**
4982:      * Returns <code>true</code> if the underlying map contains no entries.
4983:      *
4984:      * @return <code>true</code> if the map is empty.
4985:      */
4986:     public boolean isEmpty()
4987:     {
4988:       return m.isEmpty();
4989:     }
4990: 
4991:     /**
4992:      * Returns a unmodifiable set view of the keys in the underlying map.
4993:      * The set is backed by the map, so that changes in one show up in the other.
4994:      * Modifications made while an iterator is in progress cause undefined
4995:      * behavior.  These modifications are again limited to the values of
4996:      * the keys.
4997:      *
4998:      * @return the set view of all keys.
4999:      */
5000:     public Set keySet()
5001:     {
5002:       if (keys == null)
5003:         keys = new UnmodifiableSet(m.keySet());
5004:       return keys;
5005:     }
5006: 
5007:     /**
5008:      * Blocks the addition of the entries in the supplied map.
5009:      * This method never returns, throwing an exception instead.
5010:      *
5011:      * @param m The map, the entries of which should be added
5012:      *          to the underlying map.
5013:      * @throws UnsupportedOperationException as an unmodifiable
5014:      *         map does not support the <code>putAll</code> operation.
5015:      */
5016:     public void putAll(Map m)
5017:     {
5018:       throw new UnsupportedOperationException();
5019:     }
5020: 
5021:     /**
5022:      * Blocks the removal of an entry from the map.
5023:      * This method never returns, throwing an exception instead.
5024:      *
5025:      * @param o The key of the entry to remove.
5026:      * @return The value the key was associated with, or null
5027:      *         if no such mapping existed.  Null is also returned
5028:      *         if the removed entry had a null key.
5029:      * @throws UnsupportedOperationException as an unmodifiable
5030:      *         map does not support the <code>remove</code> operation.
5031:      */
5032:     public Object remove(Object o)
5033:     {
5034:       throw new UnsupportedOperationException();
5035:     }
5036: 
5037: 
5038:     /**
5039:      * Returns the number of key-value mappings in the underlying map.
5040:      * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
5041:      * is returned.
5042:      *
5043:      * @return the number of mappings.
5044:      */
5045:     public int size()
5046:     {
5047:       return m.size();
5048:     }
5049: 
5050:     /**
5051:      * Returns a textual representation of the map.
5052:      *
5053:      * @return The map in the form of a <code>String</code>.
5054:      */
5055:     public String toString()
5056:     {
5057:       return m.toString();
5058:     }
5059: 
5060:     /**
5061:      * Returns a unmodifiable collection view of the values in the underlying map.
5062:      * The collection is backed by the map, so that changes in one show up in the other.
5063:      * Modifications made while an iterator is in progress cause undefined
5064:      * behavior.  These modifications are again limited to the values of
5065:      * the keys.
5066:      *
5067:      * @return the collection view of all values.
5068:      */
5069:     public Collection values()
5070:     {
5071:       if (values == null)
5072:         values = new UnmodifiableCollection(m.values());
5073:       return values;
5074:     }
5075:   } // class UnmodifiableMap
5076: 
5077:   /**
5078:    * Returns an unmodifiable view of the given set. This allows
5079:    * "read-only" access, although changes in the backing set show up
5080:    * in this view. Attempts to modify the set directly or via iterators
5081:    * will fail with {@link UnsupportedOperationException}.
5082:    * Although this view prevents changes to the structure of the set and its
5083:    * entries, the values referenced by the objects in the set can still be
5084:    * modified.   
5085:    * <p>
5086:    *
5087:    * The returned Set implements Serializable, but can only be serialized if
5088:    * the set it wraps is likewise Serializable.
5089:    *
5090:    * @param s the set to wrap
5091:    * @return a read-only view of the set
5092:    * @see Serializable
5093:    */
5094:   public static Set unmodifiableSet(Set s)
5095:   {
5096:     return new UnmodifiableSet(s);
5097:   }
5098: 
5099:   /**
5100:    * The implementation of {@link #unmodifiableSet(Set)}. This class
5101:    * name is required for compatibility with Sun's JDK serializability.
5102:    *
5103:    * @author Eric Blake (ebb9@email.byu.edu)
5104:    */
5105:   private static class UnmodifiableSet extends UnmodifiableCollection
5106:     implements Set
5107:   {
5108:     /**
5109:      * Compatible with JDK 1.4.
5110:      */
5111:     private static final long serialVersionUID = -9215047833775013803L;
5112: 
5113:     /**
5114:      * Wrap a given set.
5115:      * @param s the set to wrap
5116:      * @throws NullPointerException if s is null
5117:      */
5118:     UnmodifiableSet(Set s)
5119:     {
5120:       super(s);
5121:     }
5122: 
5123:     /**
5124:      * Returns <code>true</code> if the object, o, is also an instance of
5125:      * <code>Set</code> of the same size and with the same entries.
5126:      *
5127:      * @return <code>true</code> if o is an equivalent set.
5128:      */
5129:     public boolean equals(Object o)
5130:     {
5131:       return c.equals(o);
5132:     }
5133: 
5134:     /**
5135:      * Computes the hash code of this set, as the sum of the
5136:      * hash codes of all elements within the set.
5137:      *
5138:      * @return the hash code of the set.
5139:      */ 
5140:     public int hashCode()
5141:     {
5142:       return c.hashCode();
5143:     }
5144:   } // class UnmodifiableSet
5145: 
5146:   /**
5147:    * Returns an unmodifiable view of the given sorted map. This allows
5148:    * "read-only" access, although changes in the backing map show up in this
5149:    * view. Attempts to modify the map directly, via subviews, via collection
5150:    * views, or iterators, will fail with {@link UnsupportedOperationException}.
5151:    * Although this view prevents changes to the structure of the map and its
5152:    * entries, the values referenced by the objects in the map can still be
5153:    * modified.   
5154:    * <p>
5155:    *
5156:    * The returned SortedMap implements Serializable, but can only be
5157:    * serialized if the map it wraps is likewise Serializable.
5158:    *
5159:    * @param m the map to wrap
5160:    * @return a read-only view of the map
5161:    * @see Serializable
5162:    */
5163:   public static SortedMap unmodifiableSortedMap(SortedMap m)
5164:   {
5165:     return new UnmodifiableSortedMap(m);
5166:   }
5167: 
5168:   /**
5169:    * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
5170:    * class name is required for compatibility with Sun's JDK serializability.
5171:    *
5172:    * @author Eric Blake (ebb9@email.byu.edu)
5173:    */
5174:   private static class UnmodifiableSortedMap extends UnmodifiableMap
5175:     implements SortedMap
5176:   {
5177:     /**
5178:      * Compatible with JDK 1.4.
5179:      */
5180:     private static final long serialVersionUID = -8806743815996713206L;
5181: 
5182:     /**
5183:      * The wrapped map; stored both here and in the superclass to avoid
5184:      * excessive casting.
5185:      * @serial the wrapped map
5186:      */
5187:     private final SortedMap sm;
5188: 
5189:     /**
5190:      * Wrap a given map.
5191:      * @param sm the map to wrap
5192:      * @throws NullPointerException if sm is null
5193:      */
5194:     UnmodifiableSortedMap(SortedMap sm)
5195:     {
5196:       super(sm);
5197:       this.sm = sm;
5198:     }
5199: 
5200:     /**
5201:      * Returns the comparator used in sorting the underlying map,
5202:      * or null if it is the keys' natural ordering.
5203:      *
5204:      * @return the sorting comparator.
5205:      */
5206:     public Comparator comparator()
5207:     {
5208:       return sm.comparator();
5209:     }
5210: 
5211:     /**
5212:      * Returns the first (lowest sorted) key in the map.
5213:      *
5214:      * @return the first key.
5215:      * @throws NoSuchElementException if this map is empty.
5216:      */
5217:     public Object firstKey()
5218:     {
5219:       return sm.firstKey();
5220:     }
5221: 
5222:     /**
5223:      * Returns a unmodifiable view of the portion of the map strictly less
5224:      * than toKey. The view is backed by the underlying map, so changes in
5225:      * one show up in the other.  The submap supports all optional operations
5226:      * of the original.  This operation is equivalent to
5227:      * <code>subMap(firstKey(), toKey)</code>.
5228:      * <p>
5229:      *
5230:      * The returned map throws an IllegalArgumentException any time a key is
5231:      * used which is out of the range of toKey. Note that the endpoint, toKey,
5232:      * is not included; if you want this value to be included, pass its successor
5233:      * object in to toKey.  For example, for Integers, you could request
5234:      * <code>headMap(new Integer(limit.intValue() + 1))</code>.
5235:      *
5236:      * @param toKey the exclusive upper range of the submap.
5237:      * @return the submap.
5238:      * @throws ClassCastException if toKey is not comparable to the map contents.
5239:      * @throws IllegalArgumentException if this is a subMap, and toKey is out
5240:      *         of range.
5241:      * @throws NullPointerException if toKey is null but the map does not allow
5242:      *         null keys.
5243:      */
5244:     public SortedMap headMap(Object toKey)
5245:     {
5246:       return new UnmodifiableSortedMap(sm.headMap(toKey));
5247:     }
5248: 
5249:     /**
5250:      * Returns the last (highest sorted) key in the map.
5251:      *
5252:      * @return the last key.
5253:      * @throws NoSuchElementException if this map is empty.
5254:      */
5255:     public Object lastKey()
5256:     {
5257:       return sm.lastKey();
5258:     }
5259: 
5260:     /**
5261:      * Returns a unmodifiable view of the portion of the map greater than or
5262:      * equal to fromKey, and strictly less than toKey. The view is backed by
5263:      * the underlying map, so changes in one show up in the other. The submap
5264:      * supports all optional operations of the original.
5265:      * <p>
5266:      *
5267:      * The returned map throws an IllegalArgumentException any time a key is
5268:      * used which is out of the range of fromKey and toKey. Note that the
5269:      * lower endpoint is included, but the upper is not; if you want to
5270:      * change the inclusion or exclusion of an endpoint, pass its successor
5271:      * object in instead.  For example, for Integers, you could request
5272:      * <code>subMap(new Integer(lowlimit.intValue() + 1),
5273:      * new Integer(highlimit.intValue() + 1))</code> to reverse
5274:      * the inclusiveness of both endpoints.
5275:      *
5276:      * @param fromKey the inclusive lower range of the submap.
5277:      * @param toKey the exclusive upper range of the submap.
5278:      * @return the submap.
5279:      * @throws ClassCastException if fromKey or toKey is not comparable to
5280:      *         the map contents.
5281:      * @throws IllegalArgumentException if this is a subMap, and fromKey or
5282:      *         toKey is out of range.
5283:      * @throws NullPointerException if fromKey or toKey is null but the map
5284:      *         does not allow null keys.
5285:      */
5286:     public SortedMap subMap(Object fromKey, Object toKey)
5287:     {
5288:       return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
5289:     }
5290: 
5291:     /**
5292:      * Returns a unmodifiable view of the portion of the map greater than or
5293:      * equal to fromKey. The view is backed by the underlying map, so changes
5294:      * in one show up in the other. The submap supports all optional operations
5295:      * of the original.
5296:      * <p>
5297:      *
5298:      * The returned map throws an IllegalArgumentException any time a key is
5299:      * used which is out of the range of fromKey. Note that the endpoint, fromKey, is
5300:      * included; if you do not want this value to be included, pass its successor object in
5301:      * to fromKey.  For example, for Integers, you could request
5302:      * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
5303:      *
5304:      * @param fromKey the inclusive lower range of the submap
5305:      * @return the submap
5306:      * @throws ClassCastException if fromKey is not comparable to the map
5307:      *         contents
5308:      * @throws IllegalArgumentException if this is a subMap, and fromKey is out
5309:      *         of range
5310:      * @throws NullPointerException if fromKey is null but the map does not allow
5311:      *         null keys
5312:      */
5313:     public SortedMap tailMap(Object fromKey)
5314:     {
5315:       return new UnmodifiableSortedMap(sm.tailMap(fromKey));
5316:     }
5317:   } // class UnmodifiableSortedMap
5318: 
5319:   /**
5320:    * Returns an unmodifiable view of the given sorted set. This allows
5321:    * "read-only" access, although changes in the backing set show up
5322:    * in this view. Attempts to modify the set directly, via subsets, or via
5323:    * iterators, will fail with {@link UnsupportedOperationException}.
5324:    * Although this view prevents changes to the structure of the set and its
5325:    * entries, the values referenced by the objects in the set can still be
5326:    * modified.   
5327:    * <p>
5328:    *
5329:    * The returns SortedSet implements Serializable, but can only be
5330:    * serialized if the set it wraps is likewise Serializable.
5331:    *
5332:    * @param s the set to wrap
5333:    * @return a read-only view of the set
5334:    * @see Serializable
5335:    */
5336:   public static SortedSet unmodifiableSortedSet(SortedSet s)
5337:   {
5338:     return new UnmodifiableSortedSet(s);
5339:   }
5340: 
5341:   /**
5342:    * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
5343:    * class name is required for compatibility with Sun's JDK serializability.
5344:    *
5345:    * @author Eric Blake (ebb9@email.byu.edu)
5346:    */
5347:   private static class UnmodifiableSortedSet extends UnmodifiableSet
5348:     implements SortedSet
5349:   {
5350:     /**
5351:      * Compatible with JDK 1.4.
5352:      */
5353:     private static final long serialVersionUID = -4929149591599911165L;
5354: 
5355:     /**
5356:      * The wrapped set; stored both here and in the superclass to avoid
5357:      * excessive casting.
5358:      * @serial the wrapped set
5359:      */
5360:     private SortedSet ss;
5361: 
5362:     /**
5363:      * Wrap a given set.
5364:      * @param ss the set to wrap
5365:      * @throws NullPointerException if ss is null
5366:      */
5367:     UnmodifiableSortedSet(SortedSet ss)
5368:     {
5369:       super(ss);
5370:       this.ss = ss;
5371:     }
5372: 
5373:     /**
5374:      * Returns the comparator used in sorting the underlying set,
5375:      * or null if it is the elements' natural ordering.
5376:      *
5377:      * @return the sorting comparator
5378:      */
5379:     public Comparator comparator()
5380:     {
5381:       return ss.comparator();
5382:     }
5383: 
5384:     /**
5385:      * Returns the first (lowest sorted) element in the underlying
5386:      * set.
5387:      *
5388:      * @return the first element.
5389:      * @throws NoSuchElementException if the set is empty.
5390:      */
5391:     public Object first()
5392:     {
5393:       return ss.first();
5394:     }
5395: 
5396:     /**
5397:      * Returns a unmodifiable view of the portion of the set strictly
5398:      * less than toElement. The view is backed by the underlying set,
5399:      * so changes in one show up in the other.  The subset supports
5400:      * all optional operations of the original.  This operation
5401:      * is equivalent to <code>subSet(first(), toElement)</code>.
5402:      * <p>
5403:      *
5404:      * The returned set throws an IllegalArgumentException any time an element is
5405:      * used which is out of the range of toElement. Note that the endpoint, toElement,
5406:      * is not included; if you want this value included, pass its successor object in to
5407:      * toElement.  For example, for Integers, you could request
5408:      * <code>headSet(new Integer(limit.intValue() + 1))</code>.
5409:      *
5410:      * @param toElement the exclusive upper range of the subset
5411:      * @return the subset.
5412:      * @throws ClassCastException if toElement is not comparable to the set
5413:      *         contents.
5414:      * @throws IllegalArgumentException if this is a subSet, and toElement is out
5415:      *         of range.
5416:      * @throws NullPointerException if toElement is null but the set does not
5417:      *         allow null elements.
5418:      */
5419:     public SortedSet headSet(Object toElement)
5420:     {
5421:       return new UnmodifiableSortedSet(ss.headSet(toElement));
5422:     }
5423: 
5424:     /**
5425:      * Returns the last (highest sorted) element in the underlying
5426:      * set.
5427:      *
5428:      * @return the last element.
5429:      * @throws NoSuchElementException if the set is empty.
5430:      */
5431:     public Object last()
5432:     {
5433:       return ss.last();
5434:     }
5435: 
5436:     /**
5437:      * Returns a unmodifiable view of the portion of the set greater than or
5438:      * equal to fromElement, and strictly less than toElement. The view is backed by
5439:      * the underlying set, so changes in one show up in the other. The subset
5440:      * supports all optional operations of the original.
5441:      * <p>
5442:      *
5443:      * The returned set throws an IllegalArgumentException any time an element is
5444:      * used which is out of the range of fromElement and toElement. Note that the
5445:      * lower endpoint is included, but the upper is not; if you want to
5446:      * change the inclusion or exclusion of an endpoint, pass its successor
5447:      * object in instead.  For example, for Integers, you can request
5448:      * <code>subSet(new Integer(lowlimit.intValue() + 1),
5449:      * new Integer(highlimit.intValue() + 1))</code> to reverse
5450:      * the inclusiveness of both endpoints.
5451:      *
5452:      * @param fromElement the inclusive lower range of the subset.
5453:      * @param toElement the exclusive upper range of the subset.
5454:      * @return the subset.
5455:      * @throws ClassCastException if fromElement or toElement is not comparable
5456:      *         to the set contents.
5457:      * @throws IllegalArgumentException if this is a subSet, and fromElement or
5458:      *         toElement is out of range.
5459:      * @throws NullPointerException if fromElement or toElement is null but the
5460:      *         set does not allow null elements.
5461:      */
5462:     public SortedSet subSet(Object fromElement, Object toElement)
5463:     {
5464:       return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement));
5465:     }
5466: 
5467:     /**
5468:      * Returns a unmodifiable view of the portion of the set greater than or equal to
5469:      * fromElement. The view is backed by the underlying set, so changes in one show up
5470:      * in the other. The subset supports all optional operations of the original.
5471:      * <p>
5472:      *
5473:      * The returned set throws an IllegalArgumentException any time an element is
5474:      * used which is out of the range of fromElement. Note that the endpoint,
5475:      * fromElement, is included; if you do not want this value to be included, pass its
5476:      * successor object in to fromElement.  For example, for Integers, you could request
5477:      * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
5478:      *
5479:      * @param fromElement the inclusive lower range of the subset
5480:      * @return the subset.
5481:      * @throws ClassCastException if fromElement is not comparable to the set
5482:      *         contents.
5483:      * @throws IllegalArgumentException if this is a subSet, and fromElement is
5484:      *         out of range.
5485:      * @throws NullPointerException if fromElement is null but the set does not
5486:      *         allow null elements.
5487:      */
5488:     public SortedSet tailSet(Object fromElement)
5489:     {
5490:       return new UnmodifiableSortedSet(ss.tailSet(fromElement));
5491:     }
5492:   } // class UnmodifiableSortedSet
5493: } // class Collections