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 < 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;
|