src/share/classes/java/util/Collections.java

Print this page




 107      * must not throw a {@code ClassCastException} for any elements
 108      * {@code e1} and {@code e2} in the list).
 109      *
 110      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 111      * not be reordered as a result of the sort.
 112      *
 113      * <p>The specified list must be modifiable, but need not be resizable.
 114      *
 115      * <p>Implementation note: This implementation is a stable, adaptive,
 116      * iterative mergesort that requires far fewer than n lg(n) comparisons
 117      * when the input array is partially sorted, while offering the
 118      * performance of a traditional mergesort when the input array is
 119      * randomly ordered.  If the input array is nearly sorted, the
 120      * implementation requires approximately n comparisons.  Temporary
 121      * storage requirements vary from a small constant for nearly sorted
 122      * input arrays to n/2 object references for randomly ordered input
 123      * arrays.
 124      *
 125      * <p>The implementation takes equal advantage of ascending and
 126      * descending order in its input array, and can take advantage of
 127      * ascending and descending order in different parts of the the same
 128      * input array.  It is well-suited to merging two or more sorted arrays:
 129      * simply concatenate the arrays and sort the resulting array.
 130      *
 131      * <p>The implementation was adapted from Tim Peters's list sort for Python
 132      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 133      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 134      * Sorting and Information Theoretic Complexity", in Proceedings of the
 135      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 136      * January 1993.
 137      *
 138      * <p>This implementation dumps the specified list into an array, sorts
 139      * the array, and iterates over the list resetting each element
 140      * from the corresponding position in the array.  This avoids the
 141      * n<sup>2</sup> log(n) performance that would result from attempting
 142      * to sort a linked list in place.
 143      *
 144      * @param  list the list to be sorted.
 145      * @throws ClassCastException if the list contains elements that are not
 146      *         <i>mutually comparable</i> (for example, strings and integers).
 147      * @throws UnsupportedOperationException if the specified list's


 167      * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
 168      * for any elements {@code e1} and {@code e2} in the list).
 169      *
 170      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 171      * not be reordered as a result of the sort.
 172      *
 173      * <p>The specified list must be modifiable, but need not be resizable.
 174      *
 175      * <p>Implementation note: This implementation is a stable, adaptive,
 176      * iterative mergesort that requires far fewer than n lg(n) comparisons
 177      * when the input array is partially sorted, while offering the
 178      * performance of a traditional mergesort when the input array is
 179      * randomly ordered.  If the input array is nearly sorted, the
 180      * implementation requires approximately n comparisons.  Temporary
 181      * storage requirements vary from a small constant for nearly sorted
 182      * input arrays to n/2 object references for randomly ordered input
 183      * arrays.
 184      *
 185      * <p>The implementation takes equal advantage of ascending and
 186      * descending order in its input array, and can take advantage of
 187      * ascending and descending order in different parts of the the same
 188      * input array.  It is well-suited to merging two or more sorted arrays:
 189      * simply concatenate the arrays and sort the resulting array.
 190      *
 191      * <p>The implementation was adapted from Tim Peters's list sort for Python
 192      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 193      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 194      * Sorting and Information Theoretic Complexity", in Proceedings of the
 195      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 196      * January 1993.
 197      *
 198      * <p>This implementation dumps the specified list into an array, sorts
 199      * the array, and iterates over the list resetting each element
 200      * from the corresponding position in the array.  This avoids the
 201      * n<sup>2</sup> log(n) performance that would result from attempting
 202      * to sort a linked list in place.
 203      *
 204      * @param  list the list to be sorted.
 205      * @param  c the comparator to determine the order of the list.  A
 206      *        {@code null} value indicates that the elements' <i>natural
 207      *        ordering</i> should be used.


 806 
 807     private static <T> void rotate1(List<T> list, int distance) {
 808         int size = list.size();
 809         if (size == 0)
 810             return;
 811         distance = distance % size;
 812         if (distance < 0)
 813             distance += size;
 814         if (distance == 0)
 815             return;
 816 
 817         for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
 818             T displaced = list.get(cycleStart);
 819             int i = cycleStart;
 820             do {
 821                 i += distance;
 822                 if (i >= size)
 823                     i -= size;
 824                 displaced = list.set(i, displaced);
 825                 nMoved ++;
 826             } while(i != cycleStart);
 827         }
 828     }
 829 
 830     private static void rotate2(List<?> list, int distance) {
 831         int size = list.size();
 832         if (size == 0)
 833             return;
 834         int mid =  -distance % size;
 835         if (mid < 0)
 836             mid += size;
 837         if (mid == 0)
 838             return;
 839 
 840         reverse(list.subList(0, mid));
 841         reverse(list.subList(mid, size));
 842         reverse(list);
 843     }
 844 
 845     /**
 846      * Replaces all occurrences of one specified value in a list with another.


1435 
1436             /**
1437              * This method is overridden to protect the backing set against
1438              * an object with a nefarious equals function that senses
1439              * that the equality-candidate is Map.Entry and calls its
1440              * setValue method.
1441              */
1442             public boolean contains(Object o) {
1443                 if (!(o instanceof Map.Entry))
1444                     return false;
1445                 return c.contains(
1446                     new UnmodifiableEntry<Object,Object>((Map.Entry<?,?>) o));
1447             }
1448 
1449             /**
1450              * The next two methods are overridden to protect against
1451              * an unscrupulous List whose contains(Object o) method senses
1452              * when o is a Map.Entry, and calls o.setValue.
1453              */
1454             public boolean containsAll(Collection<?> coll) {
1455                 Iterator<?> e = coll.iterator();
1456                 while (e.hasNext())
1457                     if (!contains(e.next())) // Invokes safe contains() above
1458                         return false;
1459                 return true;
1460             }
1461             public boolean equals(Object o) {
1462                 if (o == this)
1463                     return true;
1464 
1465                 if (!(o instanceof Set))
1466                     return false;
1467                 Set s = (Set) o;
1468                 if (s.size() != c.size())
1469                     return false;
1470                 return containsAll(s); // Invokes safe containsAll() above
1471             }
1472 
1473             /**
1474              * This "wrapper class" serves two purposes: it prevents
1475              * the client from modifying the backing Map, by short-circuiting
1476              * the setValue method, and it protects the backing Map against
1477              * an ill-behaved Map.Entry that attempts to modify another


1545         }
1546 
1547         public K firstKey()           {return sm.firstKey();}
1548         public K lastKey()            {return sm.lastKey();}
1549     }
1550 
1551 
1552     // Synch Wrappers
1553 
1554     /**
1555      * Returns a synchronized (thread-safe) collection backed by the specified
1556      * collection.  In order to guarantee serial access, it is critical that
1557      * <strong>all</strong> access to the backing collection is accomplished
1558      * through the returned collection.<p>
1559      *
1560      * It is imperative that the user manually synchronize on the returned
1561      * collection when iterating over it:
1562      * <pre>
1563      *  Collection c = Collections.synchronizedCollection(myCollection);
1564      *     ...
1565      *  synchronized(c) {
1566      *      Iterator i = c.iterator(); // Must be in the synchronized block
1567      *      while (i.hasNext())
1568      *         foo(i.next());
1569      *  }
1570      * </pre>
1571      * Failure to follow this advice may result in non-deterministic behavior.
1572      *
1573      * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1574      * and <tt>equals</tt> operations through to the backing collection, but
1575      * relies on <tt>Object</tt>'s equals and hashCode methods.  This is
1576      * necessary to preserve the contracts of these operations in the case
1577      * that the backing collection is a set or a list.<p>
1578      *
1579      * The returned collection will be serializable if the specified collection
1580      * is serializable.
1581      *
1582      * @param  c the collection to be "wrapped" in a synchronized collection.
1583      * @return a synchronized view of the specified collection.
1584      */
1585     public static <T> Collection<T> synchronizedCollection(Collection<T> c) {


1594      * @serial include
1595      */
1596     static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1597         private static final long serialVersionUID = 3053995032091335093L;
1598 
1599         final Collection<E> c;  // Backing Collection
1600         final Object mutex;     // Object on which to synchronize
1601 
1602         SynchronizedCollection(Collection<E> c) {
1603             if (c==null)
1604                 throw new NullPointerException();
1605             this.c = c;
1606             mutex = this;
1607         }
1608         SynchronizedCollection(Collection<E> c, Object mutex) {
1609             this.c = c;
1610             this.mutex = mutex;
1611         }
1612 
1613         public int size() {
1614             synchronized(mutex) {return c.size();}
1615         }
1616         public boolean isEmpty() {
1617             synchronized(mutex) {return c.isEmpty();}
1618         }
1619         public boolean contains(Object o) {
1620             synchronized(mutex) {return c.contains(o);}
1621         }
1622         public Object[] toArray() {
1623             synchronized(mutex) {return c.toArray();}
1624         }
1625         public <T> T[] toArray(T[] a) {
1626             synchronized(mutex) {return c.toArray(a);}
1627         }
1628 
1629         public Iterator<E> iterator() {
1630             return c.iterator(); // Must be manually synched by user!
1631         }
1632 
1633         public boolean add(E e) {
1634             synchronized(mutex) {return c.add(e);}
1635         }
1636         public boolean remove(Object o) {
1637             synchronized(mutex) {return c.remove(o);}
1638         }
1639 
1640         public boolean containsAll(Collection<?> coll) {
1641             synchronized(mutex) {return c.containsAll(coll);}
1642         }
1643         public boolean addAll(Collection<? extends E> coll) {
1644             synchronized(mutex) {return c.addAll(coll);}
1645         }
1646         public boolean removeAll(Collection<?> coll) {
1647             synchronized(mutex) {return c.removeAll(coll);}
1648         }
1649         public boolean retainAll(Collection<?> coll) {
1650             synchronized(mutex) {return c.retainAll(coll);}
1651         }
1652         public void clear() {
1653             synchronized(mutex) {c.clear();}
1654         }
1655         public String toString() {
1656             synchronized(mutex) {return c.toString();}
1657         }
1658         private void writeObject(ObjectOutputStream s) throws IOException {
1659             synchronized(mutex) {s.defaultWriteObject();}
1660         }
1661     }
1662 
1663     /**
1664      * Returns a synchronized (thread-safe) set backed by the specified
1665      * set.  In order to guarantee serial access, it is critical that
1666      * <strong>all</strong> access to the backing set is accomplished
1667      * through the returned set.<p>
1668      *
1669      * It is imperative that the user manually synchronize on the returned
1670      * set when iterating over it:
1671      * <pre>
1672      *  Set s = Collections.synchronizedSet(new HashSet());
1673      *      ...
1674      *  synchronized(s) {
1675      *      Iterator i = s.iterator(); // Must be in the synchronized block
1676      *      while (i.hasNext())
1677      *          foo(i.next());
1678      *  }
1679      * </pre>
1680      * Failure to follow this advice may result in non-deterministic behavior.
1681      *
1682      * <p>The returned set will be serializable if the specified set is
1683      * serializable.
1684      *
1685      * @param  s the set to be "wrapped" in a synchronized set.
1686      * @return a synchronized view of the specified set.
1687      */
1688     public static <T> Set<T> synchronizedSet(Set<T> s) {
1689         return new SynchronizedSet<T>(s);
1690     }
1691 
1692     static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1693         return new SynchronizedSet<T>(s, mutex);
1694     }
1695 
1696     /**
1697      * @serial include
1698      */
1699     static class SynchronizedSet<E>
1700           extends SynchronizedCollection<E>
1701           implements Set<E> {
1702         private static final long serialVersionUID = 487447009682186044L;
1703 
1704         SynchronizedSet(Set<E> s) {
1705             super(s);
1706         }
1707         SynchronizedSet(Set<E> s, Object mutex) {
1708             super(s, mutex);
1709         }
1710 
1711         public boolean equals(Object o) {
1712             synchronized(mutex) {return c.equals(o);}
1713         }
1714         public int hashCode() {
1715             synchronized(mutex) {return c.hashCode();}
1716         }
1717     }
1718 
1719     /**
1720      * Returns a synchronized (thread-safe) sorted set backed by the specified
1721      * sorted set.  In order to guarantee serial access, it is critical that
1722      * <strong>all</strong> access to the backing sorted set is accomplished
1723      * through the returned sorted set (or its views).<p>
1724      *
1725      * It is imperative that the user manually synchronize on the returned
1726      * sorted set when iterating over it or any of its <tt>subSet</tt>,
1727      * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1728      * <pre>
1729      *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1730      *      ...
1731      *  synchronized(s) {
1732      *      Iterator i = s.iterator(); // Must be in the synchronized block
1733      *      while (i.hasNext())
1734      *          foo(i.next());
1735      *  }
1736      * </pre>
1737      * or:
1738      * <pre>
1739      *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1740      *  SortedSet s2 = s.headSet(foo);
1741      *      ...
1742      *  synchronized(s) {  // Note: s, not s2!!!
1743      *      Iterator i = s2.iterator(); // Must be in the synchronized block
1744      *      while (i.hasNext())
1745      *          foo(i.next());
1746      *  }
1747      * </pre>
1748      * Failure to follow this advice may result in non-deterministic behavior.
1749      *
1750      * <p>The returned sorted set will be serializable if the specified
1751      * sorted set is serializable.
1752      *
1753      * @param  s the sorted set to be "wrapped" in a synchronized sorted set.
1754      * @return a synchronized view of the specified sorted set.
1755      */
1756     public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1757         return new SynchronizedSortedSet<T>(s);
1758     }
1759 
1760     /**
1761      * @serial include
1762      */
1763     static class SynchronizedSortedSet<E>
1764         extends SynchronizedSet<E>
1765         implements SortedSet<E>
1766     {
1767         private static final long serialVersionUID = 8695801310862127406L;
1768 
1769         final private SortedSet<E> ss;
1770 
1771         SynchronizedSortedSet(SortedSet<E> s) {
1772             super(s);
1773             ss = s;
1774         }
1775         SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1776             super(s, mutex);
1777             ss = s;
1778         }
1779 
1780         public Comparator<? super E> comparator() {
1781             synchronized(mutex) {return ss.comparator();}
1782         }
1783 
1784         public SortedSet<E> subSet(E fromElement, E toElement) {
1785             synchronized(mutex) {
1786                 return new SynchronizedSortedSet<E>(
1787                     ss.subSet(fromElement, toElement), mutex);
1788             }
1789         }
1790         public SortedSet<E> headSet(E toElement) {
1791             synchronized(mutex) {
1792                 return new SynchronizedSortedSet<E>(ss.headSet(toElement), mutex);
1793             }
1794         }
1795         public SortedSet<E> tailSet(E fromElement) {
1796             synchronized(mutex) {
1797                return new SynchronizedSortedSet<E>(ss.tailSet(fromElement),mutex);
1798             }
1799         }
1800 
1801         public E first() {
1802             synchronized(mutex) {return ss.first();}
1803         }
1804         public E last() {
1805             synchronized(mutex) {return ss.last();}
1806         }
1807     }
1808 
1809     /**
1810      * Returns a synchronized (thread-safe) list backed by the specified
1811      * list.  In order to guarantee serial access, it is critical that
1812      * <strong>all</strong> access to the backing list is accomplished
1813      * through the returned list.<p>
1814      *
1815      * It is imperative that the user manually synchronize on the returned
1816      * list when iterating over it:
1817      * <pre>
1818      *  List list = Collections.synchronizedList(new ArrayList());
1819      *      ...
1820      *  synchronized(list) {
1821      *      Iterator i = list.iterator(); // Must be in synchronized block
1822      *      while (i.hasNext())
1823      *          foo(i.next());
1824      *  }
1825      * </pre>
1826      * Failure to follow this advice may result in non-deterministic behavior.
1827      *
1828      * <p>The returned list will be serializable if the specified list is
1829      * serializable.
1830      *
1831      * @param  list the list to be "wrapped" in a synchronized list.
1832      * @return a synchronized view of the specified list.
1833      */
1834     public static <T> List<T> synchronizedList(List<T> list) {
1835         return (list instanceof RandomAccess ?
1836                 new SynchronizedRandomAccessList<T>(list) :
1837                 new SynchronizedList<T>(list));
1838     }
1839 
1840     static <T> List<T> synchronizedList(List<T> list, Object mutex) {


1846     /**
1847      * @serial include
1848      */
1849     static class SynchronizedList<E>
1850         extends SynchronizedCollection<E>
1851         implements List<E> {
1852         private static final long serialVersionUID = -7754090372962971524L;
1853 
1854         final List<E> list;
1855 
1856         SynchronizedList(List<E> list) {
1857             super(list);
1858             this.list = list;
1859         }
1860         SynchronizedList(List<E> list, Object mutex) {
1861             super(list, mutex);
1862             this.list = list;
1863         }
1864 
1865         public boolean equals(Object o) {
1866             synchronized(mutex) {return list.equals(o);}
1867         }
1868         public int hashCode() {
1869             synchronized(mutex) {return list.hashCode();}
1870         }
1871 
1872         public E get(int index) {
1873             synchronized(mutex) {return list.get(index);}
1874         }
1875         public E set(int index, E element) {
1876             synchronized(mutex) {return list.set(index, element);}
1877         }
1878         public void add(int index, E element) {
1879             synchronized(mutex) {list.add(index, element);}
1880         }
1881         public E remove(int index) {
1882             synchronized(mutex) {return list.remove(index);}
1883         }
1884 
1885         public int indexOf(Object o) {
1886             synchronized(mutex) {return list.indexOf(o);}
1887         }
1888         public int lastIndexOf(Object o) {
1889             synchronized(mutex) {return list.lastIndexOf(o);}
1890         }
1891 
1892         public boolean addAll(int index, Collection<? extends E> c) {
1893             synchronized(mutex) {return list.addAll(index, c);}
1894         }
1895 
1896         public ListIterator<E> listIterator() {
1897             return list.listIterator(); // Must be manually synched by user
1898         }
1899 
1900         public ListIterator<E> listIterator(int index) {
1901             return list.listIterator(index); // Must be manually synched by user
1902         }
1903 
1904         public List<E> subList(int fromIndex, int toIndex) {
1905             synchronized(mutex) {
1906                 return new SynchronizedList<E>(list.subList(fromIndex, toIndex),
1907                                             mutex);
1908             }
1909         }
1910 
1911         /**
1912          * SynchronizedRandomAccessList instances are serialized as
1913          * SynchronizedList instances to allow them to be deserialized
1914          * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
1915          * This method inverts the transformation.  As a beneficial
1916          * side-effect, it also grafts the RandomAccess marker onto
1917          * SynchronizedList instances that were serialized in pre-1.4 JREs.
1918          *
1919          * Note: Unfortunately, SynchronizedRandomAccessList instances
1920          * serialized in 1.4.1 and deserialized in 1.4 will become
1921          * SynchronizedList instances, as this method was missing in 1.4.
1922          */
1923         private Object readResolve() {
1924             return (list instanceof RandomAccess
1925                     ? new SynchronizedRandomAccessList<E>(list)
1926                     : this);
1927         }
1928     }
1929 
1930     /**
1931      * @serial include
1932      */
1933     static class SynchronizedRandomAccessList<E>
1934         extends SynchronizedList<E>
1935         implements RandomAccess {
1936 
1937         SynchronizedRandomAccessList(List<E> list) {
1938             super(list);
1939         }
1940 
1941         SynchronizedRandomAccessList(List<E> list, Object mutex) {
1942             super(list, mutex);
1943         }
1944 
1945         public List<E> subList(int fromIndex, int toIndex) {
1946             synchronized(mutex) {
1947                 return new SynchronizedRandomAccessList<E>(
1948                     list.subList(fromIndex, toIndex), mutex);
1949             }
1950         }
1951 
1952         private static final long serialVersionUID = 1530674583602358482L;
1953 
1954         /**
1955          * Allows instances to be deserialized in pre-1.4 JREs (which do
1956          * not have SynchronizedRandomAccessList).  SynchronizedList has
1957          * a readResolve method that inverts this transformation upon
1958          * deserialization.
1959          */
1960         private Object writeReplace() {
1961             return new SynchronizedList<E>(list);
1962         }
1963     }
1964 
1965     /**
1966      * Returns a synchronized (thread-safe) map backed by the specified
1967      * map.  In order to guarantee serial access, it is critical that
1968      * <strong>all</strong> access to the backing map is accomplished
1969      * through the returned map.<p>
1970      *
1971      * It is imperative that the user manually synchronize on the returned
1972      * map when iterating over any of its collection views:
1973      * <pre>
1974      *  Map m = Collections.synchronizedMap(new HashMap());
1975      *      ...
1976      *  Set s = m.keySet();  // Needn't be in synchronized block
1977      *      ...
1978      *  synchronized(m) {  // Synchronizing on m, not s!
1979      *      Iterator i = s.iterator(); // Must be in synchronized block
1980      *      while (i.hasNext())
1981      *          foo(i.next());
1982      *  }
1983      * </pre>
1984      * Failure to follow this advice may result in non-deterministic behavior.
1985      *
1986      * <p>The returned map will be serializable if the specified map is
1987      * serializable.
1988      *
1989      * @param  m the map to be "wrapped" in a synchronized map.
1990      * @return a synchronized view of the specified map.
1991      */
1992     public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
1993         return new SynchronizedMap<K,V>(m);
1994     }
1995 
1996     /**
1997      * @serial include
1998      */
1999     private static class SynchronizedMap<K,V>
2000         implements Map<K,V>, Serializable {
2001         private static final long serialVersionUID = 1978198479659022715L;
2002 
2003         private final Map<K,V> m;     // Backing Map
2004         final Object      mutex;        // Object on which to synchronize
2005 
2006         SynchronizedMap(Map<K,V> m) {
2007             if (m==null)
2008                 throw new NullPointerException();
2009             this.m = m;
2010             mutex = this;
2011         }
2012 
2013         SynchronizedMap(Map<K,V> m, Object mutex) {
2014             this.m = m;
2015             this.mutex = mutex;
2016         }
2017 
2018         public int size() {
2019             synchronized(mutex) {return m.size();}
2020         }
2021         public boolean isEmpty() {
2022             synchronized(mutex) {return m.isEmpty();}
2023         }
2024         public boolean containsKey(Object key) {
2025             synchronized(mutex) {return m.containsKey(key);}
2026         }
2027         public boolean containsValue(Object value) {
2028             synchronized(mutex) {return m.containsValue(value);}
2029         }
2030         public V get(Object key) {
2031             synchronized(mutex) {return m.get(key);}
2032         }
2033 
2034         public V put(K key, V value) {
2035             synchronized(mutex) {return m.put(key, value);}
2036         }
2037         public V remove(Object key) {
2038             synchronized(mutex) {return m.remove(key);}
2039         }
2040         public void putAll(Map<? extends K, ? extends V> map) {
2041             synchronized(mutex) {m.putAll(map);}
2042         }
2043         public void clear() {
2044             synchronized(mutex) {m.clear();}
2045         }
2046 
2047         private transient Set<K> keySet = null;
2048         private transient Set<Map.Entry<K,V>> entrySet = null;
2049         private transient Collection<V> values = null;
2050 
2051         public Set<K> keySet() {
2052             synchronized(mutex) {
2053                 if (keySet==null)
2054                     keySet = new SynchronizedSet<K>(m.keySet(), mutex);
2055                 return keySet;
2056             }
2057         }
2058 
2059         public Set<Map.Entry<K,V>> entrySet() {
2060             synchronized(mutex) {
2061                 if (entrySet==null)
2062                     entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2063                 return entrySet;
2064             }
2065         }
2066 
2067         public Collection<V> values() {
2068             synchronized(mutex) {
2069                 if (values==null)
2070                     values = new SynchronizedCollection<V>(m.values(), mutex);
2071                 return values;
2072             }
2073         }
2074 
2075         public boolean equals(Object o) {
2076             synchronized(mutex) {return m.equals(o);}
2077         }
2078         public int hashCode() {
2079             synchronized(mutex) {return m.hashCode();}
2080         }
2081         public String toString() {
2082             synchronized(mutex) {return m.toString();}
2083         }
2084         private void writeObject(ObjectOutputStream s) throws IOException {
2085             synchronized(mutex) {s.defaultWriteObject();}
2086         }
2087     }
2088 
2089     /**
2090      * Returns a synchronized (thread-safe) sorted map backed by the specified
2091      * sorted map.  In order to guarantee serial access, it is critical that
2092      * <strong>all</strong> access to the backing sorted map is accomplished
2093      * through the returned sorted map (or its views).<p>
2094      *
2095      * It is imperative that the user manually synchronize on the returned
2096      * sorted map when iterating over any of its collection views, or the
2097      * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2098      * <tt>tailMap</tt> views.
2099      * <pre>
2100      *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2101      *      ...
2102      *  Set s = m.keySet();  // Needn't be in synchronized block
2103      *      ...
2104      *  synchronized(m) {  // Synchronizing on m, not s!
2105      *      Iterator i = s.iterator(); // Must be in synchronized block
2106      *      while (i.hasNext())
2107      *          foo(i.next());
2108      *  }
2109      * </pre>
2110      * or:
2111      * <pre>
2112      *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2113      *  SortedMap m2 = m.subMap(foo, bar);
2114      *      ...
2115      *  Set s2 = m2.keySet();  // Needn't be in synchronized block
2116      *      ...
2117      *  synchronized(m) {  // Synchronizing on m, not m2 or s2!
2118      *      Iterator i = s.iterator(); // Must be in synchronized block
2119      *      while (i.hasNext())
2120      *          foo(i.next());
2121      *  }
2122      * </pre>
2123      * Failure to follow this advice may result in non-deterministic behavior.
2124      *
2125      * <p>The returned sorted map will be serializable if the specified
2126      * sorted map is serializable.
2127      *
2128      * @param  m the sorted map to be "wrapped" in a synchronized sorted map.
2129      * @return a synchronized view of the specified sorted map.
2130      */
2131     public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2132         return new SynchronizedSortedMap<K,V>(m);
2133     }
2134 
2135 
2136     /**
2137      * @serial include
2138      */
2139     static class SynchronizedSortedMap<K,V>
2140         extends SynchronizedMap<K,V>
2141         implements SortedMap<K,V>
2142     {
2143         private static final long serialVersionUID = -8798146769416483793L;
2144 
2145         private final SortedMap<K,V> sm;
2146 
2147         SynchronizedSortedMap(SortedMap<K,V> m) {
2148             super(m);
2149             sm = m;
2150         }
2151         SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2152             super(m, mutex);
2153             sm = m;
2154         }
2155 
2156         public Comparator<? super K> comparator() {
2157             synchronized(mutex) {return sm.comparator();}
2158         }
2159 
2160         public SortedMap<K,V> subMap(K fromKey, K toKey) {
2161             synchronized(mutex) {
2162                 return new SynchronizedSortedMap<K,V>(
2163                     sm.subMap(fromKey, toKey), mutex);
2164             }
2165         }
2166         public SortedMap<K,V> headMap(K toKey) {
2167             synchronized(mutex) {
2168                 return new SynchronizedSortedMap<K,V>(sm.headMap(toKey), mutex);
2169             }
2170         }
2171         public SortedMap<K,V> tailMap(K fromKey) {
2172             synchronized(mutex) {
2173                return new SynchronizedSortedMap<K,V>(sm.tailMap(fromKey),mutex);
2174             }
2175         }
2176 
2177         public K firstKey() {
2178             synchronized(mutex) {return sm.firstKey();}
2179         }
2180         public K lastKey() {
2181             synchronized(mutex) {return sm.lastKey();}
2182         }
2183     }
2184 
2185     // Dynamically typesafe collection wrappers
2186 
2187     /**
2188      * Returns a dynamically typesafe view of the specified collection.
2189      * Any attempt to insert an element of the wrong type will result in an
2190      * immediate {@link ClassCastException}.  Assuming a collection
2191      * contains no incorrectly typed elements prior to the time a
2192      * dynamically typesafe view is generated, and that all subsequent
2193      * access to the collection takes place through the view, it is
2194      * <i>guaranteed</i> that the collection cannot contain an incorrectly
2195      * typed element.
2196      *
2197      * <p>The generics mechanism in the language provides compile-time
2198      * (static) type checking, but it is possible to defeat this mechanism
2199      * with unchecked casts.  Usually this is not a problem, as the compiler
2200      * issues warnings on all such unchecked operations.  There are, however,
2201      * times when static type checking alone is not sufficient.  For example,


3300                     hasNext = false;
3301                     return e;
3302                 }
3303                 throw new NoSuchElementException();
3304             }
3305             public void remove() {
3306                 throw new UnsupportedOperationException();
3307             }
3308         };
3309     }
3310 
3311     /**
3312      * @serial include
3313      */
3314     private static class SingletonSet<E>
3315         extends AbstractSet<E>
3316         implements Serializable
3317     {
3318         private static final long serialVersionUID = 3193687207550431679L;
3319 
3320         final private E element;
3321 
3322         SingletonSet(E e) {element = e;}
3323 
3324         public Iterator<E> iterator() {
3325             return singletonIterator(element);
3326         }
3327 
3328         public int size() {return 1;}
3329 
3330         public boolean contains(Object o) {return eq(o, element);}
3331     }
3332 
3333     /**
3334      * Returns an immutable list containing only the specified object.
3335      * The returned list is serializable.
3336      *
3337      * @param o the sole object to be stored in the returned list.
3338      * @return an immutable list containing only the specified object.
3339      * @since 1.3
3340      */


3431             if (values==null)
3432                 values = singleton(v);
3433             return values;
3434         }
3435 
3436     }
3437 
3438     // Miscellaneous
3439 
3440     /**
3441      * Returns an immutable list consisting of <tt>n</tt> copies of the
3442      * specified object.  The newly allocated data object is tiny (it contains
3443      * a single reference to the data object).  This method is useful in
3444      * combination with the <tt>List.addAll</tt> method to grow lists.
3445      * The returned list is serializable.
3446      *
3447      * @param  n the number of elements in the returned list.
3448      * @param  o the element to appear repeatedly in the returned list.
3449      * @return an immutable list consisting of <tt>n</tt> copies of the
3450      *         specified object.
3451      * @throws IllegalArgumentException if n &lt; 0.
3452      * @see    List#addAll(Collection)
3453      * @see    List#addAll(int, Collection)
3454      */
3455     public static <T> List<T> nCopies(int n, T o) {
3456         if (n < 0)
3457             throw new IllegalArgumentException("List length = " + n);
3458         return new CopiesList<T>(n, o);
3459     }
3460 
3461     /**
3462      * @serial include
3463      */
3464     private static class CopiesList<E>
3465         extends AbstractList<E>
3466         implements RandomAccess, Serializable
3467     {
3468         private static final long serialVersionUID = 2739099268398711800L;
3469 
3470         final int n;
3471         final E element;




 107      * must not throw a {@code ClassCastException} for any elements
 108      * {@code e1} and {@code e2} in the list).
 109      *
 110      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 111      * not be reordered as a result of the sort.
 112      *
 113      * <p>The specified list must be modifiable, but need not be resizable.
 114      *
 115      * <p>Implementation note: This implementation is a stable, adaptive,
 116      * iterative mergesort that requires far fewer than n lg(n) comparisons
 117      * when the input array is partially sorted, while offering the
 118      * performance of a traditional mergesort when the input array is
 119      * randomly ordered.  If the input array is nearly sorted, the
 120      * implementation requires approximately n comparisons.  Temporary
 121      * storage requirements vary from a small constant for nearly sorted
 122      * input arrays to n/2 object references for randomly ordered input
 123      * arrays.
 124      *
 125      * <p>The implementation takes equal advantage of ascending and
 126      * descending order in its input array, and can take advantage of
 127      * ascending and descending order in different parts of the same
 128      * input array.  It is well-suited to merging two or more sorted arrays:
 129      * simply concatenate the arrays and sort the resulting array.
 130      *
 131      * <p>The implementation was adapted from Tim Peters's list sort for Python
 132      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 133      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 134      * Sorting and Information Theoretic Complexity", in Proceedings of the
 135      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 136      * January 1993.
 137      *
 138      * <p>This implementation dumps the specified list into an array, sorts
 139      * the array, and iterates over the list resetting each element
 140      * from the corresponding position in the array.  This avoids the
 141      * n<sup>2</sup> log(n) performance that would result from attempting
 142      * to sort a linked list in place.
 143      *
 144      * @param  list the list to be sorted.
 145      * @throws ClassCastException if the list contains elements that are not
 146      *         <i>mutually comparable</i> (for example, strings and integers).
 147      * @throws UnsupportedOperationException if the specified list's


 167      * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
 168      * for any elements {@code e1} and {@code e2} in the list).
 169      *
 170      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 171      * not be reordered as a result of the sort.
 172      *
 173      * <p>The specified list must be modifiable, but need not be resizable.
 174      *
 175      * <p>Implementation note: This implementation is a stable, adaptive,
 176      * iterative mergesort that requires far fewer than n lg(n) comparisons
 177      * when the input array is partially sorted, while offering the
 178      * performance of a traditional mergesort when the input array is
 179      * randomly ordered.  If the input array is nearly sorted, the
 180      * implementation requires approximately n comparisons.  Temporary
 181      * storage requirements vary from a small constant for nearly sorted
 182      * input arrays to n/2 object references for randomly ordered input
 183      * arrays.
 184      *
 185      * <p>The implementation takes equal advantage of ascending and
 186      * descending order in its input array, and can take advantage of
 187      * ascending and descending order in different parts of the same
 188      * input array.  It is well-suited to merging two or more sorted arrays:
 189      * simply concatenate the arrays and sort the resulting array.
 190      *
 191      * <p>The implementation was adapted from Tim Peters's list sort for Python
 192      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 193      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 194      * Sorting and Information Theoretic Complexity", in Proceedings of the
 195      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 196      * January 1993.
 197      *
 198      * <p>This implementation dumps the specified list into an array, sorts
 199      * the array, and iterates over the list resetting each element
 200      * from the corresponding position in the array.  This avoids the
 201      * n<sup>2</sup> log(n) performance that would result from attempting
 202      * to sort a linked list in place.
 203      *
 204      * @param  list the list to be sorted.
 205      * @param  c the comparator to determine the order of the list.  A
 206      *        {@code null} value indicates that the elements' <i>natural
 207      *        ordering</i> should be used.


 806 
 807     private static <T> void rotate1(List<T> list, int distance) {
 808         int size = list.size();
 809         if (size == 0)
 810             return;
 811         distance = distance % size;
 812         if (distance < 0)
 813             distance += size;
 814         if (distance == 0)
 815             return;
 816 
 817         for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
 818             T displaced = list.get(cycleStart);
 819             int i = cycleStart;
 820             do {
 821                 i += distance;
 822                 if (i >= size)
 823                     i -= size;
 824                 displaced = list.set(i, displaced);
 825                 nMoved ++;
 826             } while (i != cycleStart);
 827         }
 828     }
 829 
 830     private static void rotate2(List<?> list, int distance) {
 831         int size = list.size();
 832         if (size == 0)
 833             return;
 834         int mid =  -distance % size;
 835         if (mid < 0)
 836             mid += size;
 837         if (mid == 0)
 838             return;
 839 
 840         reverse(list.subList(0, mid));
 841         reverse(list.subList(mid, size));
 842         reverse(list);
 843     }
 844 
 845     /**
 846      * Replaces all occurrences of one specified value in a list with another.


1435 
1436             /**
1437              * This method is overridden to protect the backing set against
1438              * an object with a nefarious equals function that senses
1439              * that the equality-candidate is Map.Entry and calls its
1440              * setValue method.
1441              */
1442             public boolean contains(Object o) {
1443                 if (!(o instanceof Map.Entry))
1444                     return false;
1445                 return c.contains(
1446                     new UnmodifiableEntry<Object,Object>((Map.Entry<?,?>) o));
1447             }
1448 
1449             /**
1450              * The next two methods are overridden to protect against
1451              * an unscrupulous List whose contains(Object o) method senses
1452              * when o is a Map.Entry, and calls o.setValue.
1453              */
1454             public boolean containsAll(Collection<?> coll) {
1455                 Iterator<?> it = coll.iterator();
1456                 while (it.hasNext())
1457                     if (!contains(it.next())) // Invokes safe contains() above
1458                         return false;
1459                 return true;
1460             }
1461             public boolean equals(Object o) {
1462                 if (o == this)
1463                     return true;
1464 
1465                 if (!(o instanceof Set))
1466                     return false;
1467                 Set s = (Set) o;
1468                 if (s.size() != c.size())
1469                     return false;
1470                 return containsAll(s); // Invokes safe containsAll() above
1471             }
1472 
1473             /**
1474              * This "wrapper class" serves two purposes: it prevents
1475              * the client from modifying the backing Map, by short-circuiting
1476              * the setValue method, and it protects the backing Map against
1477              * an ill-behaved Map.Entry that attempts to modify another


1545         }
1546 
1547         public K firstKey()           {return sm.firstKey();}
1548         public K lastKey()            {return sm.lastKey();}
1549     }
1550 
1551 
1552     // Synch Wrappers
1553 
1554     /**
1555      * Returns a synchronized (thread-safe) collection backed by the specified
1556      * collection.  In order to guarantee serial access, it is critical that
1557      * <strong>all</strong> access to the backing collection is accomplished
1558      * through the returned collection.<p>
1559      *
1560      * It is imperative that the user manually synchronize on the returned
1561      * collection when iterating over it:
1562      * <pre>
1563      *  Collection c = Collections.synchronizedCollection(myCollection);
1564      *     ...
1565      *  synchronized (c) {
1566      *      Iterator i = c.iterator(); // Must be in the synchronized block
1567      *      while (i.hasNext())
1568      *         foo(i.next());
1569      *  }
1570      * </pre>
1571      * Failure to follow this advice may result in non-deterministic behavior.
1572      *
1573      * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1574      * and <tt>equals</tt> operations through to the backing collection, but
1575      * relies on <tt>Object</tt>'s equals and hashCode methods.  This is
1576      * necessary to preserve the contracts of these operations in the case
1577      * that the backing collection is a set or a list.<p>
1578      *
1579      * The returned collection will be serializable if the specified collection
1580      * is serializable.
1581      *
1582      * @param  c the collection to be "wrapped" in a synchronized collection.
1583      * @return a synchronized view of the specified collection.
1584      */
1585     public static <T> Collection<T> synchronizedCollection(Collection<T> c) {


1594      * @serial include
1595      */
1596     static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1597         private static final long serialVersionUID = 3053995032091335093L;
1598 
1599         final Collection<E> c;  // Backing Collection
1600         final Object mutex;     // Object on which to synchronize
1601 
1602         SynchronizedCollection(Collection<E> c) {
1603             if (c==null)
1604                 throw new NullPointerException();
1605             this.c = c;
1606             mutex = this;
1607         }
1608         SynchronizedCollection(Collection<E> c, Object mutex) {
1609             this.c = c;
1610             this.mutex = mutex;
1611         }
1612 
1613         public int size() {
1614             synchronized (mutex) {return c.size();}
1615         }
1616         public boolean isEmpty() {
1617             synchronized (mutex) {return c.isEmpty();}
1618         }
1619         public boolean contains(Object o) {
1620             synchronized (mutex) {return c.contains(o);}
1621         }
1622         public Object[] toArray() {
1623             synchronized (mutex) {return c.toArray();}
1624         }
1625         public <T> T[] toArray(T[] a) {
1626             synchronized (mutex) {return c.toArray(a);}
1627         }
1628 
1629         public Iterator<E> iterator() {
1630             return c.iterator(); // Must be manually synched by user!
1631         }
1632 
1633         public boolean add(E e) {
1634             synchronized (mutex) {return c.add(e);}
1635         }
1636         public boolean remove(Object o) {
1637             synchronized (mutex) {return c.remove(o);}
1638         }
1639 
1640         public boolean containsAll(Collection<?> coll) {
1641             synchronized (mutex) {return c.containsAll(coll);}
1642         }
1643         public boolean addAll(Collection<? extends E> coll) {
1644             synchronized (mutex) {return c.addAll(coll);}
1645         }
1646         public boolean removeAll(Collection<?> coll) {
1647             synchronized (mutex) {return c.removeAll(coll);}
1648         }
1649         public boolean retainAll(Collection<?> coll) {
1650             synchronized (mutex) {return c.retainAll(coll);}
1651         }
1652         public void clear() {
1653             synchronized (mutex) {c.clear();}
1654         }
1655         public String toString() {
1656             synchronized (mutex) {return c.toString();}
1657         }
1658         private void writeObject(ObjectOutputStream s) throws IOException {
1659             synchronized (mutex) {s.defaultWriteObject();}
1660         }
1661     }
1662 
1663     /**
1664      * Returns a synchronized (thread-safe) set backed by the specified
1665      * set.  In order to guarantee serial access, it is critical that
1666      * <strong>all</strong> access to the backing set is accomplished
1667      * through the returned set.<p>
1668      *
1669      * It is imperative that the user manually synchronize on the returned
1670      * set when iterating over it:
1671      * <pre>
1672      *  Set s = Collections.synchronizedSet(new HashSet());
1673      *      ...
1674      *  synchronized (s) {
1675      *      Iterator i = s.iterator(); // Must be in the synchronized block
1676      *      while (i.hasNext())
1677      *          foo(i.next());
1678      *  }
1679      * </pre>
1680      * Failure to follow this advice may result in non-deterministic behavior.
1681      *
1682      * <p>The returned set will be serializable if the specified set is
1683      * serializable.
1684      *
1685      * @param  s the set to be "wrapped" in a synchronized set.
1686      * @return a synchronized view of the specified set.
1687      */
1688     public static <T> Set<T> synchronizedSet(Set<T> s) {
1689         return new SynchronizedSet<T>(s);
1690     }
1691 
1692     static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1693         return new SynchronizedSet<T>(s, mutex);
1694     }
1695 
1696     /**
1697      * @serial include
1698      */
1699     static class SynchronizedSet<E>
1700           extends SynchronizedCollection<E>
1701           implements Set<E> {
1702         private static final long serialVersionUID = 487447009682186044L;
1703 
1704         SynchronizedSet(Set<E> s) {
1705             super(s);
1706         }
1707         SynchronizedSet(Set<E> s, Object mutex) {
1708             super(s, mutex);
1709         }
1710 
1711         public boolean equals(Object o) {
1712             synchronized (mutex) {return c.equals(o);}
1713         }
1714         public int hashCode() {
1715             synchronized (mutex) {return c.hashCode();}
1716         }
1717     }
1718 
1719     /**
1720      * Returns a synchronized (thread-safe) sorted set backed by the specified
1721      * sorted set.  In order to guarantee serial access, it is critical that
1722      * <strong>all</strong> access to the backing sorted set is accomplished
1723      * through the returned sorted set (or its views).<p>
1724      *
1725      * It is imperative that the user manually synchronize on the returned
1726      * sorted set when iterating over it or any of its <tt>subSet</tt>,
1727      * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1728      * <pre>
1729      *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1730      *      ...
1731      *  synchronized (s) {
1732      *      Iterator i = s.iterator(); // Must be in the synchronized block
1733      *      while (i.hasNext())
1734      *          foo(i.next());
1735      *  }
1736      * </pre>
1737      * or:
1738      * <pre>
1739      *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1740      *  SortedSet s2 = s.headSet(foo);
1741      *      ...
1742      *  synchronized (s) {  // Note: s, not s2!!!
1743      *      Iterator i = s2.iterator(); // Must be in the synchronized block
1744      *      while (i.hasNext())
1745      *          foo(i.next());
1746      *  }
1747      * </pre>
1748      * Failure to follow this advice may result in non-deterministic behavior.
1749      *
1750      * <p>The returned sorted set will be serializable if the specified
1751      * sorted set is serializable.
1752      *
1753      * @param  s the sorted set to be "wrapped" in a synchronized sorted set.
1754      * @return a synchronized view of the specified sorted set.
1755      */
1756     public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1757         return new SynchronizedSortedSet<T>(s);
1758     }
1759 
1760     /**
1761      * @serial include
1762      */
1763     static class SynchronizedSortedSet<E>
1764         extends SynchronizedSet<E>
1765         implements SortedSet<E>
1766     {
1767         private static final long serialVersionUID = 8695801310862127406L;
1768 
1769         private final SortedSet<E> ss;
1770 
1771         SynchronizedSortedSet(SortedSet<E> s) {
1772             super(s);
1773             ss = s;
1774         }
1775         SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1776             super(s, mutex);
1777             ss = s;
1778         }
1779 
1780         public Comparator<? super E> comparator() {
1781             synchronized (mutex) {return ss.comparator();}
1782         }
1783 
1784         public SortedSet<E> subSet(E fromElement, E toElement) {
1785             synchronized (mutex) {
1786                 return new SynchronizedSortedSet<E>(
1787                     ss.subSet(fromElement, toElement), mutex);
1788             }
1789         }
1790         public SortedSet<E> headSet(E toElement) {
1791             synchronized (mutex) {
1792                 return new SynchronizedSortedSet<E>(ss.headSet(toElement), mutex);
1793             }
1794         }
1795         public SortedSet<E> tailSet(E fromElement) {
1796             synchronized (mutex) {
1797                return new SynchronizedSortedSet<E>(ss.tailSet(fromElement),mutex);
1798             }
1799         }
1800 
1801         public E first() {
1802             synchronized (mutex) {return ss.first();}
1803         }
1804         public E last() {
1805             synchronized (mutex) {return ss.last();}
1806         }
1807     }
1808 
1809     /**
1810      * Returns a synchronized (thread-safe) list backed by the specified
1811      * list.  In order to guarantee serial access, it is critical that
1812      * <strong>all</strong> access to the backing list is accomplished
1813      * through the returned list.<p>
1814      *
1815      * It is imperative that the user manually synchronize on the returned
1816      * list when iterating over it:
1817      * <pre>
1818      *  List list = Collections.synchronizedList(new ArrayList());
1819      *      ...
1820      *  synchronized (list) {
1821      *      Iterator i = list.iterator(); // Must be in synchronized block
1822      *      while (i.hasNext())
1823      *          foo(i.next());
1824      *  }
1825      * </pre>
1826      * Failure to follow this advice may result in non-deterministic behavior.
1827      *
1828      * <p>The returned list will be serializable if the specified list is
1829      * serializable.
1830      *
1831      * @param  list the list to be "wrapped" in a synchronized list.
1832      * @return a synchronized view of the specified list.
1833      */
1834     public static <T> List<T> synchronizedList(List<T> list) {
1835         return (list instanceof RandomAccess ?
1836                 new SynchronizedRandomAccessList<T>(list) :
1837                 new SynchronizedList<T>(list));
1838     }
1839 
1840     static <T> List<T> synchronizedList(List<T> list, Object mutex) {


1846     /**
1847      * @serial include
1848      */
1849     static class SynchronizedList<E>
1850         extends SynchronizedCollection<E>
1851         implements List<E> {
1852         private static final long serialVersionUID = -7754090372962971524L;
1853 
1854         final List<E> list;
1855 
1856         SynchronizedList(List<E> list) {
1857             super(list);
1858             this.list = list;
1859         }
1860         SynchronizedList(List<E> list, Object mutex) {
1861             super(list, mutex);
1862             this.list = list;
1863         }
1864 
1865         public boolean equals(Object o) {
1866             synchronized (mutex) {return list.equals(o);}
1867         }
1868         public int hashCode() {
1869             synchronized (mutex) {return list.hashCode();}
1870         }
1871 
1872         public E get(int index) {
1873             synchronized (mutex) {return list.get(index);}
1874         }
1875         public E set(int index, E element) {
1876             synchronized (mutex) {return list.set(index, element);}
1877         }
1878         public void add(int index, E element) {
1879             synchronized (mutex) {list.add(index, element);}
1880         }
1881         public E remove(int index) {
1882             synchronized (mutex) {return list.remove(index);}
1883         }
1884 
1885         public int indexOf(Object o) {
1886             synchronized (mutex) {return list.indexOf(o);}
1887         }
1888         public int lastIndexOf(Object o) {
1889             synchronized (mutex) {return list.lastIndexOf(o);}
1890         }
1891 
1892         public boolean addAll(int index, Collection<? extends E> c) {
1893             synchronized (mutex) {return list.addAll(index, c);}
1894         }
1895 
1896         public ListIterator<E> listIterator() {
1897             return list.listIterator(); // Must be manually synched by user
1898         }
1899 
1900         public ListIterator<E> listIterator(int index) {
1901             return list.listIterator(index); // Must be manually synched by user
1902         }
1903 
1904         public List<E> subList(int fromIndex, int toIndex) {
1905             synchronized (mutex) {
1906                 return new SynchronizedList<E>(list.subList(fromIndex, toIndex),
1907                                             mutex);
1908             }
1909         }
1910 
1911         /**
1912          * SynchronizedRandomAccessList instances are serialized as
1913          * SynchronizedList instances to allow them to be deserialized
1914          * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
1915          * This method inverts the transformation.  As a beneficial
1916          * side-effect, it also grafts the RandomAccess marker onto
1917          * SynchronizedList instances that were serialized in pre-1.4 JREs.
1918          *
1919          * Note: Unfortunately, SynchronizedRandomAccessList instances
1920          * serialized in 1.4.1 and deserialized in 1.4 will become
1921          * SynchronizedList instances, as this method was missing in 1.4.
1922          */
1923         private Object readResolve() {
1924             return (list instanceof RandomAccess
1925                     ? new SynchronizedRandomAccessList<E>(list)
1926                     : this);
1927         }
1928     }
1929 
1930     /**
1931      * @serial include
1932      */
1933     static class SynchronizedRandomAccessList<E>
1934         extends SynchronizedList<E>
1935         implements RandomAccess {
1936 
1937         SynchronizedRandomAccessList(List<E> list) {
1938             super(list);
1939         }
1940 
1941         SynchronizedRandomAccessList(List<E> list, Object mutex) {
1942             super(list, mutex);
1943         }
1944 
1945         public List<E> subList(int fromIndex, int toIndex) {
1946             synchronized (mutex) {
1947                 return new SynchronizedRandomAccessList<E>(
1948                     list.subList(fromIndex, toIndex), mutex);
1949             }
1950         }
1951 
1952         private static final long serialVersionUID = 1530674583602358482L;
1953 
1954         /**
1955          * Allows instances to be deserialized in pre-1.4 JREs (which do
1956          * not have SynchronizedRandomAccessList).  SynchronizedList has
1957          * a readResolve method that inverts this transformation upon
1958          * deserialization.
1959          */
1960         private Object writeReplace() {
1961             return new SynchronizedList<E>(list);
1962         }
1963     }
1964 
1965     /**
1966      * Returns a synchronized (thread-safe) map backed by the specified
1967      * map.  In order to guarantee serial access, it is critical that
1968      * <strong>all</strong> access to the backing map is accomplished
1969      * through the returned map.<p>
1970      *
1971      * It is imperative that the user manually synchronize on the returned
1972      * map when iterating over any of its collection views:
1973      * <pre>
1974      *  Map m = Collections.synchronizedMap(new HashMap());
1975      *      ...
1976      *  Set s = m.keySet();  // Needn't be in synchronized block
1977      *      ...
1978      *  synchronized (m) {  // Synchronizing on m, not s!
1979      *      Iterator i = s.iterator(); // Must be in synchronized block
1980      *      while (i.hasNext())
1981      *          foo(i.next());
1982      *  }
1983      * </pre>
1984      * Failure to follow this advice may result in non-deterministic behavior.
1985      *
1986      * <p>The returned map will be serializable if the specified map is
1987      * serializable.
1988      *
1989      * @param  m the map to be "wrapped" in a synchronized map.
1990      * @return a synchronized view of the specified map.
1991      */
1992     public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
1993         return new SynchronizedMap<K,V>(m);
1994     }
1995 
1996     /**
1997      * @serial include
1998      */
1999     private static class SynchronizedMap<K,V>
2000         implements Map<K,V>, Serializable {
2001         private static final long serialVersionUID = 1978198479659022715L;
2002 
2003         private final Map<K,V> m;     // Backing Map
2004         final Object      mutex;        // Object on which to synchronize
2005 
2006         SynchronizedMap(Map<K,V> m) {
2007             if (m==null)
2008                 throw new NullPointerException();
2009             this.m = m;
2010             mutex = this;
2011         }
2012 
2013         SynchronizedMap(Map<K,V> m, Object mutex) {
2014             this.m = m;
2015             this.mutex = mutex;
2016         }
2017 
2018         public int size() {
2019             synchronized (mutex) {return m.size();}
2020         }
2021         public boolean isEmpty() {
2022             synchronized (mutex) {return m.isEmpty();}
2023         }
2024         public boolean containsKey(Object key) {
2025             synchronized (mutex) {return m.containsKey(key);}
2026         }
2027         public boolean containsValue(Object value) {
2028             synchronized (mutex) {return m.containsValue(value);}
2029         }
2030         public V get(Object key) {
2031             synchronized (mutex) {return m.get(key);}
2032         }
2033 
2034         public V put(K key, V value) {
2035             synchronized (mutex) {return m.put(key, value);}
2036         }
2037         public V remove(Object key) {
2038             synchronized (mutex) {return m.remove(key);}
2039         }
2040         public void putAll(Map<? extends K, ? extends V> map) {
2041             synchronized (mutex) {m.putAll(map);}
2042         }
2043         public void clear() {
2044             synchronized (mutex) {m.clear();}
2045         }
2046 
2047         private transient Set<K> keySet = null;
2048         private transient Set<Map.Entry<K,V>> entrySet = null;
2049         private transient Collection<V> values = null;
2050 
2051         public Set<K> keySet() {
2052             synchronized (mutex) {
2053                 if (keySet==null)
2054                     keySet = new SynchronizedSet<K>(m.keySet(), mutex);
2055                 return keySet;
2056             }
2057         }
2058 
2059         public Set<Map.Entry<K,V>> entrySet() {
2060             synchronized (mutex) {
2061                 if (entrySet==null)
2062                     entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2063                 return entrySet;
2064             }
2065         }
2066 
2067         public Collection<V> values() {
2068             synchronized (mutex) {
2069                 if (values==null)
2070                     values = new SynchronizedCollection<V>(m.values(), mutex);
2071                 return values;
2072             }
2073         }
2074 
2075         public boolean equals(Object o) {
2076             synchronized (mutex) {return m.equals(o);}
2077         }
2078         public int hashCode() {
2079             synchronized (mutex) {return m.hashCode();}
2080         }
2081         public String toString() {
2082             synchronized (mutex) {return m.toString();}
2083         }
2084         private void writeObject(ObjectOutputStream s) throws IOException {
2085             synchronized (mutex) {s.defaultWriteObject();}
2086         }
2087     }
2088 
2089     /**
2090      * Returns a synchronized (thread-safe) sorted map backed by the specified
2091      * sorted map.  In order to guarantee serial access, it is critical that
2092      * <strong>all</strong> access to the backing sorted map is accomplished
2093      * through the returned sorted map (or its views).<p>
2094      *
2095      * It is imperative that the user manually synchronize on the returned
2096      * sorted map when iterating over any of its collection views, or the
2097      * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2098      * <tt>tailMap</tt> views.
2099      * <pre>
2100      *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2101      *      ...
2102      *  Set s = m.keySet();  // Needn't be in synchronized block
2103      *      ...
2104      *  synchronized (m) {  // Synchronizing on m, not s!
2105      *      Iterator i = s.iterator(); // Must be in synchronized block
2106      *      while (i.hasNext())
2107      *          foo(i.next());
2108      *  }
2109      * </pre>
2110      * or:
2111      * <pre>
2112      *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2113      *  SortedMap m2 = m.subMap(foo, bar);
2114      *      ...
2115      *  Set s2 = m2.keySet();  // Needn't be in synchronized block
2116      *      ...
2117      *  synchronized (m) {  // Synchronizing on m, not m2 or s2!
2118      *      Iterator i = s.iterator(); // Must be in synchronized block
2119      *      while (i.hasNext())
2120      *          foo(i.next());
2121      *  }
2122      * </pre>
2123      * Failure to follow this advice may result in non-deterministic behavior.
2124      *
2125      * <p>The returned sorted map will be serializable if the specified
2126      * sorted map is serializable.
2127      *
2128      * @param  m the sorted map to be "wrapped" in a synchronized sorted map.
2129      * @return a synchronized view of the specified sorted map.
2130      */
2131     public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2132         return new SynchronizedSortedMap<K,V>(m);
2133     }
2134 
2135 
2136     /**
2137      * @serial include
2138      */
2139     static class SynchronizedSortedMap<K,V>
2140         extends SynchronizedMap<K,V>
2141         implements SortedMap<K,V>
2142     {
2143         private static final long serialVersionUID = -8798146769416483793L;
2144 
2145         private final SortedMap<K,V> sm;
2146 
2147         SynchronizedSortedMap(SortedMap<K,V> m) {
2148             super(m);
2149             sm = m;
2150         }
2151         SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2152             super(m, mutex);
2153             sm = m;
2154         }
2155 
2156         public Comparator<? super K> comparator() {
2157             synchronized (mutex) {return sm.comparator();}
2158         }
2159 
2160         public SortedMap<K,V> subMap(K fromKey, K toKey) {
2161             synchronized (mutex) {
2162                 return new SynchronizedSortedMap<K,V>(
2163                     sm.subMap(fromKey, toKey), mutex);
2164             }
2165         }
2166         public SortedMap<K,V> headMap(K toKey) {
2167             synchronized (mutex) {
2168                 return new SynchronizedSortedMap<K,V>(sm.headMap(toKey), mutex);
2169             }
2170         }
2171         public SortedMap<K,V> tailMap(K fromKey) {
2172             synchronized (mutex) {
2173                return new SynchronizedSortedMap<K,V>(sm.tailMap(fromKey),mutex);
2174             }
2175         }
2176 
2177         public K firstKey() {
2178             synchronized (mutex) {return sm.firstKey();}
2179         }
2180         public K lastKey() {
2181             synchronized (mutex) {return sm.lastKey();}
2182         }
2183     }
2184 
2185     // Dynamically typesafe collection wrappers
2186 
2187     /**
2188      * Returns a dynamically typesafe view of the specified collection.
2189      * Any attempt to insert an element of the wrong type will result in an
2190      * immediate {@link ClassCastException}.  Assuming a collection
2191      * contains no incorrectly typed elements prior to the time a
2192      * dynamically typesafe view is generated, and that all subsequent
2193      * access to the collection takes place through the view, it is
2194      * <i>guaranteed</i> that the collection cannot contain an incorrectly
2195      * typed element.
2196      *
2197      * <p>The generics mechanism in the language provides compile-time
2198      * (static) type checking, but it is possible to defeat this mechanism
2199      * with unchecked casts.  Usually this is not a problem, as the compiler
2200      * issues warnings on all such unchecked operations.  There are, however,
2201      * times when static type checking alone is not sufficient.  For example,


3300                     hasNext = false;
3301                     return e;
3302                 }
3303                 throw new NoSuchElementException();
3304             }
3305             public void remove() {
3306                 throw new UnsupportedOperationException();
3307             }
3308         };
3309     }
3310 
3311     /**
3312      * @serial include
3313      */
3314     private static class SingletonSet<E>
3315         extends AbstractSet<E>
3316         implements Serializable
3317     {
3318         private static final long serialVersionUID = 3193687207550431679L;
3319 
3320         private final E element;
3321 
3322         SingletonSet(E e) {element = e;}
3323 
3324         public Iterator<E> iterator() {
3325             return singletonIterator(element);
3326         }
3327 
3328         public int size() {return 1;}
3329 
3330         public boolean contains(Object o) {return eq(o, element);}
3331     }
3332 
3333     /**
3334      * Returns an immutable list containing only the specified object.
3335      * The returned list is serializable.
3336      *
3337      * @param o the sole object to be stored in the returned list.
3338      * @return an immutable list containing only the specified object.
3339      * @since 1.3
3340      */


3431             if (values==null)
3432                 values = singleton(v);
3433             return values;
3434         }
3435 
3436     }
3437 
3438     // Miscellaneous
3439 
3440     /**
3441      * Returns an immutable list consisting of <tt>n</tt> copies of the
3442      * specified object.  The newly allocated data object is tiny (it contains
3443      * a single reference to the data object).  This method is useful in
3444      * combination with the <tt>List.addAll</tt> method to grow lists.
3445      * The returned list is serializable.
3446      *
3447      * @param  n the number of elements in the returned list.
3448      * @param  o the element to appear repeatedly in the returned list.
3449      * @return an immutable list consisting of <tt>n</tt> copies of the
3450      *         specified object.
3451      * @throws IllegalArgumentException if {@code n < 0}
3452      * @see    List#addAll(Collection)
3453      * @see    List#addAll(int, Collection)
3454      */
3455     public static <T> List<T> nCopies(int n, T o) {
3456         if (n < 0)
3457             throw new IllegalArgumentException("List length = " + n);
3458         return new CopiesList<T>(n, o);
3459     }
3460 
3461     /**
3462      * @serial include
3463      */
3464     private static class CopiesList<E>
3465         extends AbstractList<E>
3466         implements RandomAccess, Serializable
3467     {
3468         private static final long serialVersionUID = 2739099268398711800L;
3469 
3470         final int n;
3471         final E element;