10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27 import java.io.Serializable;
28 import java.io.ObjectOutputStream;
29 import java.io.IOException;
30 import java.lang.reflect.Array;
31 import java.util.function.BiConsumer;
32 import java.util.function.BiFunction;
33 import java.util.function.Consumer;
34 import java.util.function.Function;
35 import java.util.function.Predicate;
36 import java.util.function.UnaryOperator;
37
38 /**
39 * This class consists exclusively of static methods that operate on or return
40 * collections. It contains polymorphic algorithms that operate on
41 * collections, "wrappers", which return a new collection backed by a
42 * specified collection, and a few other odds and ends.
43 *
44 * <p>The methods of this class all throw a <tt>NullPointerException</tt>
45 * if the collections or class objects provided to them are null.
46 *
47 * <p>The documentation for the polymorphic algorithms contained in this class
48 * generally includes a brief description of the <i>implementation</i>. Such
49 * descriptions should be regarded as <i>implementation notes</i>, rather than
119 * <p>The specified list must be modifiable, but need not be resizable.
120 *
121 * <p>Implementation note: This implementation is a stable, adaptive,
122 * iterative mergesort that requires far fewer than n lg(n) comparisons
123 * when the input array is partially sorted, while offering the
124 * performance of a traditional mergesort when the input array is
125 * randomly ordered. If the input array is nearly sorted, the
126 * implementation requires approximately n comparisons. Temporary
127 * storage requirements vary from a small constant for nearly sorted
128 * input arrays to n/2 object references for randomly ordered input
129 * arrays.
130 *
131 * <p>The implementation takes equal advantage of ascending and
132 * descending order in its input array, and can take advantage of
133 * ascending and descending order in different parts of the same
134 * input array. It is well-suited to merging two or more sorted arrays:
135 * simply concatenate the arrays and sort the resulting array.
136 *
137 * <p>The implementation was adapted from Tim Peters's list sort for Python
138 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
139 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
140 * Sorting and Information Theoretic Complexity", in Proceedings of the
141 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
142 * January 1993.
143 *
144 * <p>This implementation dumps the specified list into an array, sorts
145 * the array, and iterates over the list resetting each element
146 * from the corresponding position in the array. This avoids the
147 * n<sup>2</sup> log(n) performance that would result from attempting
148 * to sort a linked list in place.
149 *
150 * @param list the list to be sorted.
151 * @throws ClassCastException if the list contains elements that are not
152 * <i>mutually comparable</i> (for example, strings and integers).
153 * @throws UnsupportedOperationException if the specified list's
154 * list-iterator does not support the {@code set} operation.
155 * @throws IllegalArgumentException (optional) if the implementation
156 * detects that the natural ordering of the list elements is
157 * found to violate the {@link Comparable} contract
158 */
159 @SuppressWarnings("unchecked")
180 * <p>The specified list must be modifiable, but need not be resizable.
181 *
182 * <p>Implementation note: This implementation is a stable, adaptive,
183 * iterative mergesort that requires far fewer than n lg(n) comparisons
184 * when the input array is partially sorted, while offering the
185 * performance of a traditional mergesort when the input array is
186 * randomly ordered. If the input array is nearly sorted, the
187 * implementation requires approximately n comparisons. Temporary
188 * storage requirements vary from a small constant for nearly sorted
189 * input arrays to n/2 object references for randomly ordered input
190 * arrays.
191 *
192 * <p>The implementation takes equal advantage of ascending and
193 * descending order in its input array, and can take advantage of
194 * ascending and descending order in different parts of the same
195 * input array. It is well-suited to merging two or more sorted arrays:
196 * simply concatenate the arrays and sort the resulting array.
197 *
198 * <p>The implementation was adapted from Tim Peters's list sort for Python
199 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
200 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
201 * Sorting and Information Theoretic Complexity", in Proceedings of the
202 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
203 * January 1993.
204 *
205 * <p>This implementation dumps the specified list into an array, sorts
206 * the array, and iterates over the list resetting each element
207 * from the corresponding position in the array. This avoids the
208 * n<sup>2</sup> log(n) performance that would result from attempting
209 * to sort a linked list in place.
210 *
211 * @param list the list to be sorted.
212 * @param c the comparator to determine the order of the list. A
213 * {@code null} value indicates that the elements' <i>natural
214 * ordering</i> should be used.
215 * @throws ClassCastException if the list contains elements that are not
216 * <i>mutually comparable</i> using the specified comparator.
217 * @throws UnsupportedOperationException if the specified list's
218 * list-iterator does not support the {@code set} operation.
219 * @throws IllegalArgumentException (optional) if the comparator is
220 * found to violate the {@link Comparator} contract
1195
1196 UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1197
1198 public Comparator<? super E> comparator() {return ss.comparator();}
1199
1200 public SortedSet<E> subSet(E fromElement, E toElement) {
1201 return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement));
1202 }
1203 public SortedSet<E> headSet(E toElement) {
1204 return new UnmodifiableSortedSet<>(ss.headSet(toElement));
1205 }
1206 public SortedSet<E> tailSet(E fromElement) {
1207 return new UnmodifiableSortedSet<>(ss.tailSet(fromElement));
1208 }
1209
1210 public E first() {return ss.first();}
1211 public E last() {return ss.last();}
1212 }
1213
1214 /**
1215 * Returns an unmodifiable view of the specified list. This method allows
1216 * modules to provide users with "read-only" access to internal
1217 * lists. Query operations on the returned list "read through" to the
1218 * specified list, and attempts to modify the returned list, whether
1219 * direct or via its iterator, result in an
1220 * <tt>UnsupportedOperationException</tt>.<p>
1221 *
1222 * The returned list will be serializable if the specified list
1223 * is serializable. Similarly, the returned list will implement
1224 * {@link RandomAccess} if the specified list does.
1225 *
1226 * @param list the list for which an unmodifiable view is to be returned.
1227 * @return an unmodifiable view of the specified list.
1228 */
1229 public static <T> List<T> unmodifiableList(List<? extends T> list) {
1230 return (list instanceof RandomAccess ?
1231 new UnmodifiableRandomAccessList<>(list) :
1232 new UnmodifiableList<>(list));
1233 }
1234
1235 /**
1236 * @serial include
1237 */
1238 static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1239 implements List<E> {
1240 private static final long serialVersionUID = -283967356065247728L;
1241 final List<? extends E> list;
1242
1243 UnmodifiableList(List<? extends E> list) {
1244 super(list);
1245 this.list = list;
1246 }
1247
1248 public boolean equals(Object o) {return o == this || list.equals(o);}
1249 public int hashCode() {return list.hashCode();}
1250
1251 public E get(int index) {return list.get(index);}
1252 public E set(int index, E element) {
1253 throw new UnsupportedOperationException();
1254 }
1255 public void add(int index, E element) {
1256 throw new UnsupportedOperationException();
1257 }
1258 public E remove(int index) {
1259 throw new UnsupportedOperationException();
1260 }
1635 * is serializable.
1636 *
1637 * @param m the sorted map for which an unmodifiable view is to be
1638 * returned.
1639 * @return an unmodifiable view of the specified sorted map.
1640 */
1641 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1642 return new UnmodifiableSortedMap<>(m);
1643 }
1644
1645 /**
1646 * @serial include
1647 */
1648 static class UnmodifiableSortedMap<K,V>
1649 extends UnmodifiableMap<K,V>
1650 implements SortedMap<K,V>, Serializable {
1651 private static final long serialVersionUID = -8806743815996713206L;
1652
1653 private final SortedMap<K, ? extends V> sm;
1654
1655 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1656
1657 public Comparator<? super K> comparator() {return sm.comparator();}
1658
1659 public SortedMap<K,V> subMap(K fromKey, K toKey) {
1660 return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey));
1661 }
1662 public SortedMap<K,V> headMap(K toKey) {
1663 return new UnmodifiableSortedMap<>(sm.headMap(toKey));
1664 }
1665 public SortedMap<K,V> tailMap(K fromKey) {
1666 return new UnmodifiableSortedMap<>(sm.tailMap(fromKey));
1667 }
1668
1669 public K firstKey() {return sm.firstKey();}
1670 public K lastKey() {return sm.lastKey();}
1671 }
1672
1673
1674 // Synch Wrappers
1675
1676 /**
1677 * Returns a synchronized (thread-safe) collection backed by the specified
1678 * collection. In order to guarantee serial access, it is critical that
1679 * <strong>all</strong> access to the backing collection is accomplished
1680 * through the returned collection.<p>
1681 *
1682 * It is imperative that the user manually synchronize on the returned
1683 * collection when traversing it via {@link Iterator} or
1684 * {@link Spliterator}:
1685 * <pre>
1686 * Collection c = Collections.synchronizedCollection(myCollection);
1687 * ...
1688 * synchronized (c) {
1689 * Iterator i = c.iterator(); // Must be in the synchronized block
1690 * while (i.hasNext())
1691 * foo(i.next());
1692 * }
1706 * @return a synchronized view of the specified collection.
1707 */
1708 public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1709 return new SynchronizedCollection<>(c);
1710 }
1711
1712 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1713 return new SynchronizedCollection<>(c, mutex);
1714 }
1715
1716 /**
1717 * @serial include
1718 */
1719 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1720 private static final long serialVersionUID = 3053995032091335093L;
1721
1722 final Collection<E> c; // Backing Collection
1723 final Object mutex; // Object on which to synchronize
1724
1725 SynchronizedCollection(Collection<E> c) {
1726 if (c==null)
1727 throw new NullPointerException();
1728 this.c = c;
1729 mutex = this;
1730 }
1731 SynchronizedCollection(Collection<E> c, Object mutex) {
1732 this.c = c;
1733 this.mutex = mutex;
1734 }
1735
1736 public int size() {
1737 synchronized (mutex) {return c.size();}
1738 }
1739 public boolean isEmpty() {
1740 synchronized (mutex) {return c.isEmpty();}
1741 }
1742 public boolean contains(Object o) {
1743 synchronized (mutex) {return c.contains(o);}
1744 }
1745 public Object[] toArray() {
1746 synchronized (mutex) {return c.toArray();}
1747 }
1748 public <T> T[] toArray(T[] a) {
1749 synchronized (mutex) {return c.toArray(a);}
1750 }
1751
1752 public Iterator<E> iterator() {
1753 return c.iterator(); // Must be manually synched by user!
1928 public SortedSet<E> headSet(E toElement) {
1929 synchronized (mutex) {
1930 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex);
1931 }
1932 }
1933 public SortedSet<E> tailSet(E fromElement) {
1934 synchronized (mutex) {
1935 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex);
1936 }
1937 }
1938
1939 public E first() {
1940 synchronized (mutex) {return ss.first();}
1941 }
1942 public E last() {
1943 synchronized (mutex) {return ss.last();}
1944 }
1945 }
1946
1947 /**
1948 * Returns a synchronized (thread-safe) list backed by the specified
1949 * list. In order to guarantee serial access, it is critical that
1950 * <strong>all</strong> access to the backing list is accomplished
1951 * through the returned list.<p>
1952 *
1953 * It is imperative that the user manually synchronize on the returned
1954 * list when iterating over it:
1955 * <pre>
1956 * List list = Collections.synchronizedList(new ArrayList());
1957 * ...
1958 * synchronized (list) {
1959 * Iterator i = list.iterator(); // Must be in synchronized block
1960 * while (i.hasNext())
1961 * foo(i.next());
1962 * }
1963 * </pre>
1964 * Failure to follow this advice may result in non-deterministic behavior.
1965 *
1966 * <p>The returned list will be serializable if the specified list is
1967 * serializable.
2136 * serializable.
2137 *
2138 * @param m the map to be "wrapped" in a synchronized map.
2139 * @return a synchronized view of the specified map.
2140 */
2141 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
2142 return new SynchronizedMap<>(m);
2143 }
2144
2145 /**
2146 * @serial include
2147 */
2148 private static class SynchronizedMap<K,V>
2149 implements Map<K,V>, Serializable {
2150 private static final long serialVersionUID = 1978198479659022715L;
2151
2152 private final Map<K,V> m; // Backing Map
2153 final Object mutex; // Object on which to synchronize
2154
2155 SynchronizedMap(Map<K,V> m) {
2156 if (m==null)
2157 throw new NullPointerException();
2158 this.m = m;
2159 mutex = this;
2160 }
2161
2162 SynchronizedMap(Map<K,V> m, Object mutex) {
2163 this.m = m;
2164 this.mutex = mutex;
2165 }
2166
2167 public int size() {
2168 synchronized (mutex) {return m.size();}
2169 }
2170 public boolean isEmpty() {
2171 synchronized (mutex) {return m.isEmpty();}
2172 }
2173 public boolean containsKey(Object key) {
2174 synchronized (mutex) {return m.containsKey(key);}
2175 }
2176 public boolean containsValue(Object value) {
2177 synchronized (mutex) {return m.containsValue(value);}
2178 }
2317 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2318 * ...
2319 * synchronized (m) { // Synchronizing on m, not m2 or s2!
2320 * Iterator i = s.iterator(); // Must be in synchronized block
2321 * while (i.hasNext())
2322 * foo(i.next());
2323 * }
2324 * </pre>
2325 * Failure to follow this advice may result in non-deterministic behavior.
2326 *
2327 * <p>The returned sorted map will be serializable if the specified
2328 * sorted map is serializable.
2329 *
2330 * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2331 * @return a synchronized view of the specified sorted map.
2332 */
2333 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2334 return new SynchronizedSortedMap<>(m);
2335 }
2336
2337
2338 /**
2339 * @serial include
2340 */
2341 static class SynchronizedSortedMap<K,V>
2342 extends SynchronizedMap<K,V>
2343 implements SortedMap<K,V>
2344 {
2345 private static final long serialVersionUID = -8798146769416483793L;
2346
2347 private final SortedMap<K,V> sm;
2348
2349 SynchronizedSortedMap(SortedMap<K,V> m) {
2350 super(m);
2351 sm = m;
2352 }
2353 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2354 super(m, mutex);
2355 sm = m;
2356 }
2357
2367 }
2368 public SortedMap<K,V> headMap(K toKey) {
2369 synchronized (mutex) {
2370 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex);
2371 }
2372 }
2373 public SortedMap<K,V> tailMap(K fromKey) {
2374 synchronized (mutex) {
2375 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex);
2376 }
2377 }
2378
2379 public K firstKey() {
2380 synchronized (mutex) {return sm.firstKey();}
2381 }
2382 public K lastKey() {
2383 synchronized (mutex) {return sm.lastKey();}
2384 }
2385 }
2386
2387 // Dynamically typesafe collection wrappers
2388
2389 /**
2390 * Returns a dynamically typesafe view of the specified collection.
2391 * Any attempt to insert an element of the wrong type will result in an
2392 * immediate {@link ClassCastException}. Assuming a collection
2393 * contains no incorrectly typed elements prior to the time a
2394 * dynamically typesafe view is generated, and that all subsequent
2395 * access to the collection takes place through the view, it is
2396 * <i>guaranteed</i> that the collection cannot contain an incorrectly
2397 * typed element.
2398 *
2399 * <p>The generics mechanism in the language provides compile-time
2400 * (static) type checking, but it is possible to defeat this mechanism
2401 * with unchecked casts. Usually this is not a problem, as the compiler
2402 * issues warnings on all such unchecked operations. There are, however,
2403 * times when static type checking alone is not sufficient. For example,
2404 * suppose a collection is passed to a third-party library and it is
2405 * imperative that the library code not corrupt the collection by
2406 * inserting an element of the wrong type.
2407 *
2408 * <p>Another use of dynamically typesafe views is debugging. Suppose a
2409 * program fails with a {@code ClassCastException}, indicating that an
2410 * incorrectly typed element was put into a parameterized collection.
2411 * Unfortunately, the exception can occur at any time after the erroneous
2412 * element is inserted, so it typically provides little or no information
2413 * as to the real source of the problem. If the problem is reproducible,
2414 * one can quickly determine its source by temporarily modifying the
2415 * program to wrap the collection with a dynamically typesafe view.
2416 * For example, this declaration:
2417 * <pre> {@code
2418 * Collection<String> c = new HashSet<String>();
2419 * }</pre>
2420 * may be replaced temporarily by this one:
2421 * <pre> {@code
2422 * Collection<String> c = Collections.checkedCollection(
2423 * new HashSet<String>(), String.class);
2424 * }</pre>
2425 * Running the program again will cause it to fail at the point where
2426 * an incorrectly typed element is inserted into the collection, clearly
2427 * identifying the source of the problem. Once the problem is fixed, the
2428 * modified declaration may be reverted back to the original.
2429 *
2430 * <p>The returned collection does <i>not</i> pass the hashCode and equals
2431 * operations through to the backing collection, but relies on
2432 * {@code Object}'s {@code equals} and {@code hashCode} methods. This
2433 * is necessary to preserve the contracts of these operations in the case
2434 * that the backing collection is a set or a list.
2435 *
2436 * <p>The returned collection will be serializable if the specified
2437 * collection is serializable.
2438 *
2439 * <p>Since {@code null} is considered to be a value of any reference
2440 * type, the returned collection permits insertion of null elements
2441 * whenever the backing collection does.
2442 *
2443 * @param c the collection for which a dynamically typesafe view is to be
2689 * whenever the backing sorted set does.
2690 *
2691 * @param s the sorted set for which a dynamically typesafe view is to be
2692 * returned
2693 * @param type the type of element that {@code s} is permitted to hold
2694 * @return a dynamically typesafe view of the specified sorted set
2695 * @since 1.5
2696 */
2697 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
2698 Class<E> type) {
2699 return new CheckedSortedSet<>(s, type);
2700 }
2701
2702 /**
2703 * @serial include
2704 */
2705 static class CheckedSortedSet<E> extends CheckedSet<E>
2706 implements SortedSet<E>, Serializable
2707 {
2708 private static final long serialVersionUID = 1599911165492914959L;
2709 private final SortedSet<E> ss;
2710
2711 CheckedSortedSet(SortedSet<E> s, Class<E> type) {
2712 super(s, type);
2713 ss = s;
2714 }
2715
2716 public Comparator<? super E> comparator() { return ss.comparator(); }
2717 public E first() { return ss.first(); }
2718 public E last() { return ss.last(); }
2719
2720 public SortedSet<E> subSet(E fromElement, E toElement) {
2721 return checkedSortedSet(ss.subSet(fromElement,toElement), type);
2722 }
2723 public SortedSet<E> headSet(E toElement) {
2724 return checkedSortedSet(ss.headSet(toElement), type);
2725 }
2726 public SortedSet<E> tailSet(E fromElement) {
2727 return checkedSortedSet(ss.tailSet(fromElement), type);
2728 }
2729 }
2730
2731 /**
2732 * Returns a dynamically typesafe view of the specified list.
2733 * Any attempt to insert an element of the wrong type will result in
2734 * an immediate {@link ClassCastException}. Assuming a list contains
2735 * no incorrectly typed elements prior to the time a dynamically typesafe
2736 * view is generated, and that all subsequent access to the list
2737 * takes place through the view, it is <i>guaranteed</i> that the
2738 * list cannot contain an incorrectly typed element.
2739 *
2740 * <p>A discussion of the use of dynamically typesafe views may be
2741 * found in the documentation for the {@link #checkedCollection
2742 * checkedCollection} method.
2743 *
2744 * <p>The returned list will be serializable if the specified list
2745 * is serializable.
2746 *
2747 * <p>Since {@code null} is considered to be a value of any reference
2748 * type, the returned list permits insertion of null elements whenever
2749 * the backing list does.
2750 *
2923 BiFunction<? super K, ? super V, ? extends V> func) {
2924 Objects.requireNonNull(func);
2925 return (k, v) -> {
2926 V newValue = func.apply(k, v);
2927 typeCheck(k, newValue);
2928 return newValue;
2929 };
2930 }
2931
2932 private String badKeyMsg(Object key) {
2933 return "Attempt to insert " + key.getClass() +
2934 " key into map with key type " + keyType;
2935 }
2936
2937 private String badValueMsg(Object value) {
2938 return "Attempt to insert " + value.getClass() +
2939 " value into map with value type " + valueType;
2940 }
2941
2942 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
2943 if (m == null || keyType == null || valueType == null)
2944 throw new NullPointerException();
2945 this.m = m;
2946 this.keyType = keyType;
2947 this.valueType = valueType;
2948 }
2949
2950 public int size() { return m.size(); }
2951 public boolean isEmpty() { return m.isEmpty(); }
2952 public boolean containsKey(Object key) { return m.containsKey(key); }
2953 public boolean containsValue(Object v) { return m.containsValue(v); }
2954 public V get(Object key) { return m.get(key); }
2955 public V remove(Object key) { return m.remove(key); }
2956 public void clear() { m.clear(); }
2957 public Set<K> keySet() { return m.keySet(); }
2958 public Collection<V> values() { return m.values(); }
2959 public boolean equals(Object o) { return o == this || m.equals(o); }
2960 public int hashCode() { return m.hashCode(); }
2961 public String toString() { return m.toString(); }
2962
2963 public V put(K key, V value) {
2964 typeCheck(key, value);
2965 return m.put(key, value);
2966 }
2967
3308 super(m, keyType, valueType);
3309 sm = m;
3310 }
3311
3312 public Comparator<? super K> comparator() { return sm.comparator(); }
3313 public K firstKey() { return sm.firstKey(); }
3314 public K lastKey() { return sm.lastKey(); }
3315
3316 public SortedMap<K,V> subMap(K fromKey, K toKey) {
3317 return checkedSortedMap(sm.subMap(fromKey, toKey),
3318 keyType, valueType);
3319 }
3320 public SortedMap<K,V> headMap(K toKey) {
3321 return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
3322 }
3323 public SortedMap<K,V> tailMap(K fromKey) {
3324 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
3325 }
3326 }
3327
3328 // Empty collections
3329
3330 /**
3331 * Returns an iterator that has no elements. More precisely,
3332 *
3333 * <ul compact>
3334 *
3335 * <li>{@link Iterator#hasNext hasNext} always returns {@code
3336 * false}.
3337 *
3338 * <li>{@link Iterator#next next} always throws {@link
3339 * NoSuchElementException}.
3340 *
3341 * <li>{@link Iterator#remove remove} always throws {@link
3342 * IllegalStateException}.
3343 *
3344 * </ul>
3345 *
3346 * <p>Implementations of this method are permitted, but not
3347 * required, to return the same object from multiple invocations.
3348 *
3349 * @return an empty iterator
3350 * @since 1.7
3351 */
3352 @SuppressWarnings("unchecked")
3353 public static <T> Iterator<T> emptyIterator() {
3354 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
3450 public boolean hasMoreElements() { return false; }
3451 public E nextElement() { throw new NoSuchElementException(); }
3452 }
3453
3454 /**
3455 * The empty set (immutable). This set is serializable.
3456 *
3457 * @see #emptySet()
3458 */
3459 @SuppressWarnings("rawtypes")
3460 public static final Set EMPTY_SET = new EmptySet<>();
3461
3462 /**
3463 * Returns the empty set (immutable). This set is serializable.
3464 * Unlike the like-named field, this method is parameterized.
3465 *
3466 * <p>This example illustrates the type-safe way to obtain an empty set:
3467 * <pre>
3468 * Set<String> s = Collections.emptySet();
3469 * </pre>
3470 * Implementation note: Implementations of this method need not
3471 * create a separate <tt>Set</tt> object for each call. Using this
3472 * method is likely to have comparable cost to using the like-named
3473 * field. (Unlike this method, the field does not provide type safety.)
3474 *
3475 * @see #EMPTY_SET
3476 * @since 1.5
3477 */
3478 @SuppressWarnings("unchecked")
3479 public static final <T> Set<T> emptySet() {
3480 return (Set<T>) EMPTY_SET;
3481 }
3482
3483 /**
3484 * @serial include
3485 */
3486 private static class EmptySet<E>
3487 extends AbstractSet<E>
3488 implements Serializable
3489 {
3490 private static final long serialVersionUID = 1582296315990362920L;
3491
3492 public Iterator<E> iterator() { return emptyIterator(); }
3493
3494 public int size() {return 0;}
3508 // Override default methods in Collection
3509 @Override
3510 public void forEach(Consumer<? super E> action) {
3511 Objects.requireNonNull(action);
3512 }
3513 @Override
3514 public boolean removeIf(Predicate<? super E> filter) {
3515 Objects.requireNonNull(filter);
3516 return false;
3517 }
3518 @Override
3519 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
3520
3521 // Preserves singleton property
3522 private Object readResolve() {
3523 return EMPTY_SET;
3524 }
3525 }
3526
3527 /**
3528 * Returns the empty sorted set (immutable). This set is serializable.
3529 *
3530 * <p>This example illustrates the type-safe way to obtain an empty sorted
3531 * set:
3532 * <pre>
3533 * SortedSet<String> s = Collections.emptySortedSet();
3534 * </pre>
3535 * Implementation note: Implementations of this method need not
3536 * create a separate <tt>SortedSet</tt> object for each call.
3537 *
3538 * @since 1.8
3539 */
3540 @SuppressWarnings("unchecked")
3541 public static final <E> SortedSet<E> emptySortedSet() {
3542 return (SortedSet<E>) new EmptySortedSet<>();
3543 }
3544
3545 /**
3546 * @serial include
3547 */
3548 private static class EmptySortedSet<E>
3549 extends AbstractSet<E>
3550 implements SortedSet<E>, Serializable
3551 {
3552 private static final long serialVersionUID = 6316515401502265487L;
3553 public Iterator<E> iterator() { return emptyIterator(); }
3554 public int size() {return 0;}
3555 public boolean isEmpty() {return true;}
3556 public boolean contains(Object obj) {return false;}
3557 public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3558 public Object[] toArray() { return new Object[0]; }
3559
3560 public <E> E[] toArray(E[] a) {
3561 if (a.length > 0)
3562 a[0] = null;
3563 return a;
3564 }
3565
3566 // Preserves singleton property
3567 private Object readResolve() {
3568 return new EmptySortedSet<>();
3569 }
3570
3571 @Override
3572 public Comparator<? super E> comparator() {
3573 return null;
3574 }
3575
3576 @Override
3577 @SuppressWarnings("unchecked")
3578 public SortedSet<E> subSet(Object fromElement, Object toElement) {
3579 Objects.requireNonNull(fromElement);
3580 Objects.requireNonNull(toElement);
3581
3582 if (!(fromElement instanceof Comparable) ||
3583 !(toElement instanceof Comparable))
3584 {
3585 throw new ClassCastException();
3586 }
3587
3588 if ((((Comparable)fromElement).compareTo(toElement) >= 0) ||
3589 (((Comparable)toElement).compareTo(fromElement) < 0))
3590 {
3591 throw new IllegalArgumentException();
3592 }
3593
3594 return emptySortedSet();
3595 }
3596
3597 @Override
3598 public SortedSet<E> headSet(Object toElement) {
3599 Objects.requireNonNull(toElement);
3600
3601 if (!(toElement instanceof Comparable)) {
3602 throw new ClassCastException();
3603 }
3604
3605 return emptySortedSet();
3606 }
3607
3608 @Override
3609 public SortedSet<E> tailSet(Object fromElement) {
3610 Objects.requireNonNull(fromElement);
3611
3612 if (!(fromElement instanceof Comparable)) {
3613 throw new ClassCastException();
3614 }
3615
3616 return emptySortedSet();
3617 }
3618
3619 @Override
3620 public E first() {
3621 throw new NoSuchElementException();
3622 }
3623
3624 @Override
3625 public E last() {
3626 throw new NoSuchElementException();
3627 }
3628
3629 // Override default methods in Collection
3630 @Override
3631 public void forEach(Consumer<? super E> action) {
3632 Objects.requireNonNull(action);
3633 }
3634
3635 @Override
3636 public boolean removeIf(Predicate<? super E> filter) {
3637 Objects.requireNonNull(filter);
3638 return false;
3639 }
3640
3641 @Override
3642 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
3643 }
3644
3645 /**
3646 * The empty list (immutable). This list is serializable.
3647 *
3648 * @see #emptyList()
3649 */
3650 @SuppressWarnings("rawtypes")
3651 public static final List EMPTY_LIST = new EmptyList<>();
3652
3653 /**
3654 * Returns the empty list (immutable). This list is serializable.
3655 *
3656 * <p>This example illustrates the type-safe way to obtain an empty list:
3657 * <pre>
3658 * List<String> s = Collections.emptyList();
3659 * </pre>
3660 * Implementation note: Implementations of this method need not
3661 * create a separate <tt>List</tt> object for each call. Using this
3662 * method is likely to have comparable cost to using the like-named
3722 public void sort(Comparator<? super E> c) {
3723 Objects.requireNonNull(c);
3724 }
3725
3726 // Override default methods in Collection
3727 @Override
3728 public void forEach(Consumer<? super E> action) {
3729 Objects.requireNonNull(action);
3730 }
3731
3732 @Override
3733 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
3734
3735 // Preserves singleton property
3736 private Object readResolve() {
3737 return EMPTY_LIST;
3738 }
3739 }
3740
3741 /**
3742 * The empty map (immutable). This map is serializable.
3743 *
3744 * @see #emptyMap()
3745 * @since 1.3
3746 */
3747 @SuppressWarnings("rawtypes")
3748 public static final Map EMPTY_MAP = new EmptyMap<>();
3749
3750 /**
3751 * Returns the empty map (immutable). This map is serializable.
3752 *
3753 * <p>This example illustrates the type-safe way to obtain an empty set:
3754 * <pre>
3755 * Map<String, Date> s = Collections.emptyMap();
3756 * </pre>
3757 * Implementation note: Implementations of this method need not
3758 * create a separate <tt>Map</tt> object for each call. Using this
3759 * method is likely to have comparable cost to using the like-named
3760 * field. (Unlike this method, the field does not provide type safety.)
3761 *
3762 * @see #EMPTY_MAP
3763 * @since 1.5
3764 */
3765 @SuppressWarnings("unchecked")
3766 public static final <K,V> Map<K,V> emptyMap() {
3767 return (Map<K,V>) EMPTY_MAP;
3768 }
3769
3770 /**
3771 * @serial include
3772 */
3773 private static class EmptyMap<K,V>
3774 extends AbstractMap<K,V>
3775 implements Serializable
3776 {
3777 private static final long serialVersionUID = 6428348081105594320L;
3778
3779 public int size() {return 0;}
3780 public boolean isEmpty() {return true;}
3781 public boolean containsKey(Object key) {return false;}
3782 public boolean containsValue(Object value) {return false;}
3783 public V get(Object key) {return null;}
3784 public Set<K> keySet() {return emptySet();}
3785 public Collection<V> values() {return emptySet();}
3786 public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
3787
3788 public boolean equals(Object o) {
3789 return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
3790 }
3841 }
3842
3843 @Override
3844 public V compute(K key,
3845 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3846 throw new UnsupportedOperationException();
3847 }
3848
3849 @Override
3850 public V merge(K key, V value,
3851 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
3852 throw new UnsupportedOperationException();
3853 }
3854
3855 // Preserves singleton property
3856 private Object readResolve() {
3857 return EMPTY_MAP;
3858 }
3859 }
3860
3861 // Singleton collections
3862
3863 /**
3864 * Returns an immutable set containing only the specified object.
3865 * The returned set is serializable.
3866 *
3867 * @param o the sole object to be stored in the returned set.
3868 * @return an immutable set containing only the specified object.
3869 */
3870 public static <T> Set<T> singleton(T o) {
3871 return new SingletonSet<>(o);
3872 }
3873
3874 static <E> Iterator<E> singletonIterator(final E e) {
3875 return new Iterator<E>() {
3876 private boolean hasNext = true;
3877 public boolean hasNext() {
3878 return hasNext;
3879 }
3880 public E next() {
4055 return new SingletonMap<>(key, value);
4056 }
4057
4058 /**
4059 * @serial include
4060 */
4061 private static class SingletonMap<K,V>
4062 extends AbstractMap<K,V>
4063 implements Serializable {
4064 private static final long serialVersionUID = -6979724477215052911L;
4065
4066 private final K k;
4067 private final V v;
4068
4069 SingletonMap(K key, V value) {
4070 k = key;
4071 v = value;
4072 }
4073
4074 public int size() {return 1;}
4075
4076 public boolean isEmpty() {return false;}
4077
4078 public boolean containsKey(Object key) {return eq(key, k);}
4079
4080 public boolean containsValue(Object value) {return eq(value, v);}
4081
4082 public V get(Object key) {return (eq(key, k) ? v : null);}
4083
4084 private transient Set<K> keySet = null;
4085 private transient Set<Map.Entry<K,V>> entrySet = null;
4086 private transient Collection<V> values = null;
4087
4088 public Set<K> keySet() {
4089 if (keySet==null)
4090 keySet = singleton(k);
4091 return keySet;
4092 }
4093
4094 public Set<Map.Entry<K,V>> entrySet() {
4095 if (entrySet==null)
4096 entrySet = Collections.<Map.Entry<K,V>>singleton(
4097 new SimpleImmutableEntry<>(k, v));
4098 return entrySet;
4099 }
4100
4101 public Collection<V> values() {
4399 * legacy APIs that return enumerations and new APIs that require
4400 * collections.
4401 *
4402 * @param e enumeration providing elements for the returned
4403 * array list
4404 * @return an array list containing the elements returned
4405 * by the specified enumeration.
4406 * @since 1.4
4407 * @see Enumeration
4408 * @see ArrayList
4409 */
4410 public static <T> ArrayList<T> list(Enumeration<T> e) {
4411 ArrayList<T> l = new ArrayList<>();
4412 while (e.hasMoreElements())
4413 l.add(e.nextElement());
4414 return l;
4415 }
4416
4417 /**
4418 * Returns true if the specified arguments are equal, or both null.
4419 */
4420 static boolean eq(Object o1, Object o2) {
4421 return o1==null ? o2==null : o1.equals(o2);
4422 }
4423
4424 /**
4425 * Returns the number of elements in the specified collection equal to the
4426 * specified object. More formally, returns the number of elements
4427 * <tt>e</tt> in the collection such that
4428 * <tt>(o == null ? e == null : o.equals(e))</tt>.
4429 *
4430 * @param c the collection in which to determine the frequency
4431 * of <tt>o</tt>
4432 * @param o the object whose frequency is to be determined
4433 * @throws NullPointerException if <tt>c</tt> is null
4434 * @since 1.5
4435 */
4436 public static int frequency(Collection<?> c, Object o) {
4437 int result = 0;
4438 if (o == null) {
4641 @Override
4642 public void forEach(Consumer<? super E> action) {
4643 s.forEach(action);
4644 }
4645 @Override
4646 public boolean removeIf(Predicate<? super E> filter) {
4647 return s.removeIf(filter);
4648 }
4649
4650 @Override
4651 public Spliterator<E> spliterator() {return s.spliterator();}
4652
4653 private static final long serialVersionUID = 2454657854757543876L;
4654
4655 private void readObject(java.io.ObjectInputStream stream)
4656 throws IOException, ClassNotFoundException
4657 {
4658 stream.defaultReadObject();
4659 s = m.keySet();
4660 }
4661 }
4662
4663 /**
4664 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
4665 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
4666 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
4667 * view can be useful when you would like to use a method
4668 * requiring a <tt>Queue</tt> but you need Lifo ordering.
4669 *
4670 * <p>Each method invocation on the queue returned by this method
4671 * results in exactly one method invocation on the backing deque, with
4672 * one exception. The {@link Queue#addAll addAll} method is
4673 * implemented as a sequence of {@link Deque#addFirst addFirst}
4674 * invocations on the backing deque.
4675 *
4676 * @param deque the deque
4677 * @return the queue
4678 * @since 1.6
4679 */
4680 public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
|
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27 import java.io.Serializable;
28 import java.io.ObjectOutputStream;
29 import java.io.IOException;
30 import java.io.InvalidObjectException;
31 import java.lang.reflect.Array;
32 import java.util.function.BiConsumer;
33 import java.util.function.BiFunction;
34 import java.util.function.Consumer;
35 import java.util.function.Function;
36 import java.util.function.Predicate;
37 import java.util.function.UnaryOperator;
38
39 /**
40 * This class consists exclusively of static methods that operate on or return
41 * collections. It contains polymorphic algorithms that operate on
42 * collections, "wrappers", which return a new collection backed by a
43 * specified collection, and a few other odds and ends.
44 *
45 * <p>The methods of this class all throw a <tt>NullPointerException</tt>
46 * if the collections or class objects provided to them are null.
47 *
48 * <p>The documentation for the polymorphic algorithms contained in this class
49 * generally includes a brief description of the <i>implementation</i>. Such
50 * descriptions should be regarded as <i>implementation notes</i>, rather than
120 * <p>The specified list must be modifiable, but need not be resizable.
121 *
122 * <p>Implementation note: This implementation is a stable, adaptive,
123 * iterative mergesort that requires far fewer than n lg(n) comparisons
124 * when the input array is partially sorted, while offering the
125 * performance of a traditional mergesort when the input array is
126 * randomly ordered. If the input array is nearly sorted, the
127 * implementation requires approximately n comparisons. Temporary
128 * storage requirements vary from a small constant for nearly sorted
129 * input arrays to n/2 object references for randomly ordered input
130 * arrays.
131 *
132 * <p>The implementation takes equal advantage of ascending and
133 * descending order in its input array, and can take advantage of
134 * ascending and descending order in different parts of the same
135 * input array. It is well-suited to merging two or more sorted arrays:
136 * simply concatenate the arrays and sort the resulting array.
137 *
138 * <p>The implementation was adapted from Tim Peters's list sort for Python
139 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
140 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
141 * Sorting and Information Theoretic Complexity", in Proceedings of the
142 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
143 * January 1993.
144 *
145 * <p>This implementation dumps the specified list into an array, sorts
146 * the array, and iterates over the list resetting each element
147 * from the corresponding position in the array. This avoids the
148 * n<sup>2</sup> log(n) performance that would result from attempting
149 * to sort a linked list in place.
150 *
151 * @param list the list to be sorted.
152 * @throws ClassCastException if the list contains elements that are not
153 * <i>mutually comparable</i> (for example, strings and integers).
154 * @throws UnsupportedOperationException if the specified list's
155 * list-iterator does not support the {@code set} operation.
156 * @throws IllegalArgumentException (optional) if the implementation
157 * detects that the natural ordering of the list elements is
158 * found to violate the {@link Comparable} contract
159 */
160 @SuppressWarnings("unchecked")
181 * <p>The specified list must be modifiable, but need not be resizable.
182 *
183 * <p>Implementation note: This implementation is a stable, adaptive,
184 * iterative mergesort that requires far fewer than n lg(n) comparisons
185 * when the input array is partially sorted, while offering the
186 * performance of a traditional mergesort when the input array is
187 * randomly ordered. If the input array is nearly sorted, the
188 * implementation requires approximately n comparisons. Temporary
189 * storage requirements vary from a small constant for nearly sorted
190 * input arrays to n/2 object references for randomly ordered input
191 * arrays.
192 *
193 * <p>The implementation takes equal advantage of ascending and
194 * descending order in its input array, and can take advantage of
195 * ascending and descending order in different parts of the same
196 * input array. It is well-suited to merging two or more sorted arrays:
197 * simply concatenate the arrays and sort the resulting array.
198 *
199 * <p>The implementation was adapted from Tim Peters's list sort for Python
200 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
201 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
202 * Sorting and Information Theoretic Complexity", in Proceedings of the
203 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
204 * January 1993.
205 *
206 * <p>This implementation dumps the specified list into an array, sorts
207 * the array, and iterates over the list resetting each element
208 * from the corresponding position in the array. This avoids the
209 * n<sup>2</sup> log(n) performance that would result from attempting
210 * to sort a linked list in place.
211 *
212 * @param list the list to be sorted.
213 * @param c the comparator to determine the order of the list. A
214 * {@code null} value indicates that the elements' <i>natural
215 * ordering</i> should be used.
216 * @throws ClassCastException if the list contains elements that are not
217 * <i>mutually comparable</i> using the specified comparator.
218 * @throws UnsupportedOperationException if the specified list's
219 * list-iterator does not support the {@code set} operation.
220 * @throws IllegalArgumentException (optional) if the comparator is
221 * found to violate the {@link Comparator} contract
1196
1197 UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1198
1199 public Comparator<? super E> comparator() {return ss.comparator();}
1200
1201 public SortedSet<E> subSet(E fromElement, E toElement) {
1202 return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement));
1203 }
1204 public SortedSet<E> headSet(E toElement) {
1205 return new UnmodifiableSortedSet<>(ss.headSet(toElement));
1206 }
1207 public SortedSet<E> tailSet(E fromElement) {
1208 return new UnmodifiableSortedSet<>(ss.tailSet(fromElement));
1209 }
1210
1211 public E first() {return ss.first();}
1212 public E last() {return ss.last();}
1213 }
1214
1215 /**
1216 * Returns an unmodifiable view of the specified navigable set. This method
1217 * allows modules to provide users with "read-only" access to internal
1218 * navigable sets. Query operations on the returned navigable set "read
1219 * through" to the specified navigable set. Attempts to modify the returned
1220 * navigable set, whether direct, via its iterator, or via its
1221 * {@code subSet}, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1222 * an <tt>UnsupportedOperationException</tt>.<p>
1223 *
1224 * The returned navigable set will be serializable if the specified
1225 * navigable set is serializable.
1226 *
1227 * @param s the navigable set for which an unmodifiable view is to be
1228 * returned
1229 * @return an unmodifiable view of the specified navigable set
1230 * @since 1.8
1231 */
1232 public static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s) {
1233 return new UnmodifiableNavigableSet<>(s);
1234 }
1235
1236 /**
1237 * @serial include
1238 */
1239 static class UnmodifiableNavigableSet<E>
1240 extends UnmodifiableSortedSet<E>
1241 implements NavigableSet<E>, Serializable {
1242
1243 private static final long serialVersionUID = -6027448201786391929L;
1244
1245 private final NavigableSet<E> ns;
1246
1247 UnmodifiableNavigableSet(NavigableSet<E> s) {super(s); ns = s;}
1248
1249 @Override public E lower(E e) { return ns.lower(e); }
1250 @Override public E floor(E e) { return ns.floor(e); }
1251 @Override public E ceiling(E e) { return ns.ceiling(e); }
1252 @Override public E higher(E e) { return ns.higher(e); }
1253 @Override public E pollFirst() { throw new UnsupportedOperationException(); }
1254 @Override public E pollLast() { throw new UnsupportedOperationException(); }
1255 @Override
1256 public NavigableSet<E> descendingSet() {
1257 return new UnmodifiableNavigableSet<>(ns.descendingSet());
1258 }
1259
1260 @Override
1261 public Iterator<E> descendingIterator() {
1262 return descendingSet().iterator();
1263 }
1264
1265 @Override
1266 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1267 return new UnmodifiableNavigableSet<>(ns.subSet(fromElement, fromInclusive, toElement, toInclusive));
1268 }
1269
1270 @Override
1271 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1272 return new UnmodifiableNavigableSet<>(ns.headSet(toElement, inclusive));
1273 }
1274
1275 @Override
1276 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1277 return new UnmodifiableNavigableSet<>(ns.tailSet(fromElement, inclusive));
1278 }
1279 }
1280
1281 /**
1282 * Returns an unmodifiable view of the specified list. This method allows
1283 * modules to provide users with "read-only" access to internal
1284 * lists. Query operations on the returned list "read through" to the
1285 * specified list, and attempts to modify the returned list, whether
1286 * direct or via its iterator, result in an
1287 * <tt>UnsupportedOperationException</tt>.<p>
1288 *
1289 * The returned list will be serializable if the specified list
1290 * is serializable. Similarly, the returned list will implement
1291 * {@link RandomAccess} if the specified list does.
1292 *
1293 * @param list the list for which an unmodifiable view is to be returned.
1294 * @return an unmodifiable view of the specified list.
1295 */
1296 public static <T> List<T> unmodifiableList(List<? extends T> list) {
1297 return (list instanceof RandomAccess ?
1298 new UnmodifiableRandomAccessList<>(list) :
1299 new UnmodifiableList<>(list));
1300 }
1301
1302 /**
1303 * @serial include
1304 */
1305 static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1306 implements List<E> {
1307 private static final long serialVersionUID = -283967356065247728L;
1308
1309 final List<? extends E> list;
1310
1311 UnmodifiableList(List<? extends E> list) {
1312 super(list);
1313 this.list = list;
1314 }
1315
1316 public boolean equals(Object o) {return o == this || list.equals(o);}
1317 public int hashCode() {return list.hashCode();}
1318
1319 public E get(int index) {return list.get(index);}
1320 public E set(int index, E element) {
1321 throw new UnsupportedOperationException();
1322 }
1323 public void add(int index, E element) {
1324 throw new UnsupportedOperationException();
1325 }
1326 public E remove(int index) {
1327 throw new UnsupportedOperationException();
1328 }
1703 * is serializable.
1704 *
1705 * @param m the sorted map for which an unmodifiable view is to be
1706 * returned.
1707 * @return an unmodifiable view of the specified sorted map.
1708 */
1709 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1710 return new UnmodifiableSortedMap<>(m);
1711 }
1712
1713 /**
1714 * @serial include
1715 */
1716 static class UnmodifiableSortedMap<K,V>
1717 extends UnmodifiableMap<K,V>
1718 implements SortedMap<K,V>, Serializable {
1719 private static final long serialVersionUID = -8806743815996713206L;
1720
1721 private final SortedMap<K, ? extends V> sm;
1722
1723 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m; }
1724 public Comparator<? super K> comparator() { return sm.comparator(); }
1725 public SortedMap<K,V> subMap(K fromKey, K toKey)
1726 { return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey)); }
1727 public SortedMap<K,V> headMap(K toKey)
1728 { return new UnmodifiableSortedMap<>(sm.headMap(toKey)); }
1729 public SortedMap<K,V> tailMap(K fromKey)
1730 { return new UnmodifiableSortedMap<>(sm.tailMap(fromKey)); }
1731 public K firstKey() { return sm.firstKey(); }
1732 public K lastKey() { return sm.lastKey(); }
1733 }
1734
1735 /**
1736 * Returns an unmodifiable view of the specified navigable map. This method
1737 * allows modules to provide users with "read-only" access to internal
1738 * navigable maps. Query operations on the returned navigable map "read
1739 * through" to the specified navigable map. Attempts to modify the returned
1740 * navigable map, whether direct, via its collection views, or via its
1741 * {@code subMap}, {@code headMap}, or {@code tailMap} views, result in
1742 * an {@code UnsupportedOperationException}.<p>
1743 *
1744 * The returned navigable map will be serializable if the specified
1745 * navigable map is serializable.
1746 *
1747 * @param m the navigable map for which an unmodifiable view is to be
1748 * returned
1749 * @return an unmodifiable view of the specified navigable map
1750 * @since 1.8
1751 */
1752 public static <K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m) {
1753 return new UnmodifiableNavigableMap<>(m);
1754 }
1755
1756 /**
1757 * @serial include
1758 */
1759 static class UnmodifiableNavigableMap<K,V>
1760 extends UnmodifiableSortedMap<K,V>
1761 implements NavigableMap<K,V>, Serializable {
1762 private static final long serialVersionUID = -4858195264774772197L;
1763
1764 private final NavigableMap<K, ? extends V> nm;
1765
1766 UnmodifiableNavigableMap(NavigableMap<K, ? extends V> m)
1767 {super(m); nm = m;}
1768
1769 public Entry<K, V> lowerEntry(K key) {
1770 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.lowerEntry(key));
1771 }
1772
1773 public K lowerKey(K key) { return nm.lowerKey(key); }
1774
1775 public Entry<K, V> floorEntry(K key) {
1776 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.floorEntry(key));
1777 }
1778
1779 public K floorKey(K key) { return nm.floorKey(key); }
1780
1781 public Entry<K, V> ceilingEntry(K key) {
1782 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.ceilingEntry(key));
1783 }
1784
1785 public K ceilingKey(K key) { return nm.ceilingKey(key); }
1786
1787 public Entry<K, V> higherEntry(K key) {
1788 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.higherEntry(key));
1789 }
1790
1791 public K higherKey(K key) { return nm.higherKey(key); }
1792
1793 public Entry<K, V> firstEntry() {
1794 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.firstEntry());
1795 }
1796
1797 public Entry<K, V> lastEntry() {
1798 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.lastEntry());
1799 }
1800
1801 public Entry<K, V> pollFirstEntry()
1802 { throw new UnsupportedOperationException(); }
1803 public Entry<K, V> pollLastEntry()
1804 { throw new UnsupportedOperationException(); }
1805 public NavigableMap<K, V> descendingMap()
1806 { return unmodifiableNavigableMap(nm.descendingMap()); }
1807 public NavigableSet<K> navigableKeySet()
1808 { return unmodifiableNavigableSet(nm.navigableKeySet()); }
1809 public NavigableSet<K> descendingKeySet()
1810 { return unmodifiableNavigableSet(nm.descendingKeySet()); }
1811
1812 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1813 return unmodifiableNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive));
1814 }
1815
1816 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
1817 return unmodifiableNavigableMap(nm.headMap(toKey, inclusive));
1818 }
1819
1820 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
1821 return unmodifiableNavigableMap(nm.tailMap(fromKey, inclusive));
1822 }
1823 }
1824
1825 // Synch Wrappers
1826
1827 /**
1828 * Returns a synchronized (thread-safe) collection backed by the specified
1829 * collection. In order to guarantee serial access, it is critical that
1830 * <strong>all</strong> access to the backing collection is accomplished
1831 * through the returned collection.<p>
1832 *
1833 * It is imperative that the user manually synchronize on the returned
1834 * collection when traversing it via {@link Iterator} or
1835 * {@link Spliterator}:
1836 * <pre>
1837 * Collection c = Collections.synchronizedCollection(myCollection);
1838 * ...
1839 * synchronized (c) {
1840 * Iterator i = c.iterator(); // Must be in the synchronized block
1841 * while (i.hasNext())
1842 * foo(i.next());
1843 * }
1857 * @return a synchronized view of the specified collection.
1858 */
1859 public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1860 return new SynchronizedCollection<>(c);
1861 }
1862
1863 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1864 return new SynchronizedCollection<>(c, mutex);
1865 }
1866
1867 /**
1868 * @serial include
1869 */
1870 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1871 private static final long serialVersionUID = 3053995032091335093L;
1872
1873 final Collection<E> c; // Backing Collection
1874 final Object mutex; // Object on which to synchronize
1875
1876 SynchronizedCollection(Collection<E> c) {
1877 this.c = Objects.requireNonNull(c);
1878 mutex = this;
1879 }
1880
1881 SynchronizedCollection(Collection<E> c, Object mutex) {
1882 this.c = Objects.requireNonNull(c);
1883 this.mutex = Objects.requireNonNull(mutex);
1884 }
1885
1886 public int size() {
1887 synchronized (mutex) {return c.size();}
1888 }
1889 public boolean isEmpty() {
1890 synchronized (mutex) {return c.isEmpty();}
1891 }
1892 public boolean contains(Object o) {
1893 synchronized (mutex) {return c.contains(o);}
1894 }
1895 public Object[] toArray() {
1896 synchronized (mutex) {return c.toArray();}
1897 }
1898 public <T> T[] toArray(T[] a) {
1899 synchronized (mutex) {return c.toArray(a);}
1900 }
1901
1902 public Iterator<E> iterator() {
1903 return c.iterator(); // Must be manually synched by user!
2078 public SortedSet<E> headSet(E toElement) {
2079 synchronized (mutex) {
2080 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex);
2081 }
2082 }
2083 public SortedSet<E> tailSet(E fromElement) {
2084 synchronized (mutex) {
2085 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex);
2086 }
2087 }
2088
2089 public E first() {
2090 synchronized (mutex) {return ss.first();}
2091 }
2092 public E last() {
2093 synchronized (mutex) {return ss.last();}
2094 }
2095 }
2096
2097 /**
2098 * Returns a synchronized (thread-safe) navigable set backed by the
2099 * specified navigable set. In order to guarantee serial access, it is
2100 * critical that <strong>all</strong> access to the backing navigable set is
2101 * accomplished through the returned navigable set (or its views).<p>
2102 *
2103 * It is imperative that the user manually synchronize on the returned
2104 * navigable set when iterating over it or any of its {@code subSet},
2105 * {@code headSet}, or {@code tailSet} views.
2106 * <pre>
2107 * NavigableSet s = Collections.synchronizedNavigableSet(new TreeSet());
2108 * ...
2109 * synchronized (s) {
2110 * Iterator i = s.iterator(); // Must be in the synchronized block
2111 * while (i.hasNext())
2112 * foo(i.next());
2113 * }
2114 * </pre>
2115 * or:
2116 * <pre>
2117 * NavigableSet s = Collections.synchronizedNavigableSet(new TreeSet());
2118 * NavigableSet s2 = s.headSet(foo, true);
2119 * ...
2120 * synchronized (s) { // Note: s, not s2!!!
2121 * Iterator i = s2.iterator(); // Must be in the synchronized block
2122 * while (i.hasNext())
2123 * foo(i.next());
2124 * }
2125 * </pre>
2126 * Failure to follow this advice may result in non-deterministic behavior.
2127 *
2128 * <p>The returned navigable set will be serializable if the specified
2129 * navigable set is serializable.
2130 *
2131 * @param s the navigable set to be "wrapped" in a synchronized navigable
2132 * set
2133 * @return a synchronized view of the specified navigable set
2134 * @since 1.8
2135 */
2136 public static <T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s) {
2137 return new SynchronizedNavigableSet<>(s);
2138 }
2139
2140 /**
2141 * @serial include
2142 */
2143 static class SynchronizedNavigableSet<E>
2144 extends SynchronizedSortedSet<E>
2145 implements NavigableSet<E>
2146 {
2147 private static final long serialVersionUID = -5505529816273629798L;
2148
2149 private final NavigableSet<E> ns;
2150
2151 SynchronizedNavigableSet(NavigableSet<E> s) {
2152 super(s);
2153 ns = s;
2154 }
2155
2156 SynchronizedNavigableSet(NavigableSet<E> s, Object mutex) {
2157 super(s, mutex);
2158 ns = s;
2159 }
2160 public E lower(E e) { synchronized (mutex) {return ns.lower(e);} }
2161 public E floor(E e) { synchronized (mutex) {return ns.floor(e);} }
2162 public E ceiling(E e) { synchronized (mutex) {return ns.ceiling(e);} }
2163 public E higher(E e) { synchronized (mutex) {return ns.higher(e);} }
2164 public E pollFirst() { synchronized (mutex) {return ns.pollFirst();} }
2165 public E pollLast() { synchronized (mutex) {return ns.pollLast();} }
2166
2167 public NavigableSet<E> descendingSet() {
2168 synchronized (mutex) {
2169 return new SynchronizedNavigableSet<>(ns.descendingSet(), mutex);
2170 }
2171 }
2172
2173 public Iterator<E> descendingIterator()
2174 { synchronized (mutex) { return descendingSet().iterator(); } }
2175
2176 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
2177 synchronized (mutex) {
2178 return new SynchronizedNavigableSet<>(ns.subSet(fromElement, fromInclusive, toElement, toInclusive), mutex);
2179 }
2180 }
2181
2182 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2183 synchronized (mutex) {
2184 return new SynchronizedNavigableSet<>(ns.headSet(toElement, inclusive), mutex);
2185 }
2186 }
2187
2188 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2189 synchronized (mutex) {
2190 return new SynchronizedNavigableSet<>(ns.tailSet(fromElement, inclusive));
2191 }
2192 }
2193 }
2194
2195 /**
2196 * Returns a synchronized (thread-safe) list backed by the specified
2197 * list. In order to guarantee serial access, it is critical that
2198 * <strong>all</strong> access to the backing list is accomplished
2199 * through the returned list.<p>
2200 *
2201 * It is imperative that the user manually synchronize on the returned
2202 * list when iterating over it:
2203 * <pre>
2204 * List list = Collections.synchronizedList(new ArrayList());
2205 * ...
2206 * synchronized (list) {
2207 * Iterator i = list.iterator(); // Must be in synchronized block
2208 * while (i.hasNext())
2209 * foo(i.next());
2210 * }
2211 * </pre>
2212 * Failure to follow this advice may result in non-deterministic behavior.
2213 *
2214 * <p>The returned list will be serializable if the specified list is
2215 * serializable.
2384 * serializable.
2385 *
2386 * @param m the map to be "wrapped" in a synchronized map.
2387 * @return a synchronized view of the specified map.
2388 */
2389 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
2390 return new SynchronizedMap<>(m);
2391 }
2392
2393 /**
2394 * @serial include
2395 */
2396 private static class SynchronizedMap<K,V>
2397 implements Map<K,V>, Serializable {
2398 private static final long serialVersionUID = 1978198479659022715L;
2399
2400 private final Map<K,V> m; // Backing Map
2401 final Object mutex; // Object on which to synchronize
2402
2403 SynchronizedMap(Map<K,V> m) {
2404 this.m = Objects.requireNonNull(m);
2405 mutex = this;
2406 }
2407
2408 SynchronizedMap(Map<K,V> m, Object mutex) {
2409 this.m = m;
2410 this.mutex = mutex;
2411 }
2412
2413 public int size() {
2414 synchronized (mutex) {return m.size();}
2415 }
2416 public boolean isEmpty() {
2417 synchronized (mutex) {return m.isEmpty();}
2418 }
2419 public boolean containsKey(Object key) {
2420 synchronized (mutex) {return m.containsKey(key);}
2421 }
2422 public boolean containsValue(Object value) {
2423 synchronized (mutex) {return m.containsValue(value);}
2424 }
2563 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2564 * ...
2565 * synchronized (m) { // Synchronizing on m, not m2 or s2!
2566 * Iterator i = s.iterator(); // Must be in synchronized block
2567 * while (i.hasNext())
2568 * foo(i.next());
2569 * }
2570 * </pre>
2571 * Failure to follow this advice may result in non-deterministic behavior.
2572 *
2573 * <p>The returned sorted map will be serializable if the specified
2574 * sorted map is serializable.
2575 *
2576 * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2577 * @return a synchronized view of the specified sorted map.
2578 */
2579 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2580 return new SynchronizedSortedMap<>(m);
2581 }
2582
2583 /**
2584 * @serial include
2585 */
2586 static class SynchronizedSortedMap<K,V>
2587 extends SynchronizedMap<K,V>
2588 implements SortedMap<K,V>
2589 {
2590 private static final long serialVersionUID = -8798146769416483793L;
2591
2592 private final SortedMap<K,V> sm;
2593
2594 SynchronizedSortedMap(SortedMap<K,V> m) {
2595 super(m);
2596 sm = m;
2597 }
2598 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2599 super(m, mutex);
2600 sm = m;
2601 }
2602
2612 }
2613 public SortedMap<K,V> headMap(K toKey) {
2614 synchronized (mutex) {
2615 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex);
2616 }
2617 }
2618 public SortedMap<K,V> tailMap(K fromKey) {
2619 synchronized (mutex) {
2620 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex);
2621 }
2622 }
2623
2624 public K firstKey() {
2625 synchronized (mutex) {return sm.firstKey();}
2626 }
2627 public K lastKey() {
2628 synchronized (mutex) {return sm.lastKey();}
2629 }
2630 }
2631
2632 /**
2633 * Returns a synchronized (thread-safe) navigable map backed by the
2634 * specified navigable map. In order to guarantee serial access, it is
2635 * critical that <strong>all</strong> access to the backing navigable map is
2636 * accomplished through the returned navigable map (or its views).<p>
2637 *
2638 * It is imperative that the user manually synchronize on the returned
2639 * navigable map when iterating over any of its collection views, or the
2640 * collections views of any of its {@code subMap}, {@code headMap} or
2641 * {@code tailMap} views.
2642 * <pre>
2643 * NavigableMap m = Collections.synchronizedNavigableMap(new TreeMap());
2644 * ...
2645 * Set s = m.keySet(); // Needn't be in synchronized block
2646 * ...
2647 * synchronized (m) { // Synchronizing on m, not s!
2648 * Iterator i = s.iterator(); // Must be in synchronized block
2649 * while (i.hasNext())
2650 * foo(i.next());
2651 * }
2652 * </pre>
2653 * or:
2654 * <pre>
2655 * NavigableMap m = Collections.synchronizedNavigableMap(new TreeMap());
2656 * NavigableMap m2 = m.subMap(foo, true, bar, false);
2657 * ...
2658 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2659 * ...
2660 * synchronized (m) { // Synchronizing on m, not m2 or s2!
2661 * Iterator i = s.iterator(); // Must be in synchronized block
2662 * while (i.hasNext())
2663 * foo(i.next());
2664 * }
2665 * </pre>
2666 * Failure to follow this advice may result in non-deterministic behavior.
2667 *
2668 * <p>The returned navigable map will be serializable if the specified
2669 * navigable map is serializable.
2670 *
2671 * @param m the navigable map to be "wrapped" in a synchronized navigable
2672 * map
2673 * @return a synchronized view of the specified navigable map.
2674 * @since 1.8
2675 */
2676 public static <K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m) {
2677 return new SynchronizedNavigableMap<>(m);
2678 }
2679
2680 /**
2681 * A synchronized NavigableMap.
2682 *
2683 * @serial include
2684 */
2685 static class SynchronizedNavigableMap<K,V>
2686 extends SynchronizedSortedMap<K,V>
2687 implements NavigableMap<K,V>
2688 {
2689 private static final long serialVersionUID = 699392247599746807L;
2690
2691 private final NavigableMap<K,V> nm;
2692
2693 SynchronizedNavigableMap(NavigableMap<K,V> m) {
2694 super(m);
2695 nm = m;
2696 }
2697 SynchronizedNavigableMap(NavigableMap<K,V> m, Object mutex) {
2698 super(m, mutex);
2699 nm = m;
2700 }
2701
2702 public Entry<K, V> lowerEntry(K key)
2703 { synchronized (mutex) { return nm.lowerEntry(key); } }
2704 public K lowerKey(K key)
2705 { synchronized (mutex) { return nm.lowerKey(key); } }
2706 public Entry<K, V> floorEntry(K key)
2707 { synchronized (mutex) { return nm.floorEntry(key); } }
2708 public K floorKey(K key)
2709 { synchronized (mutex) { return nm.floorKey(key); } }
2710 public Entry<K, V> ceilingEntry(K key)
2711 { synchronized (mutex) { return nm.ceilingEntry(key); } }
2712 public K ceilingKey(K key)
2713 { synchronized (mutex) { return nm.ceilingKey(key); } }
2714 public Entry<K, V> higherEntry(K key)
2715 { synchronized (mutex) { return nm.higherEntry(key); } }
2716 public K higherKey(K key)
2717 { synchronized (mutex) { return nm.higherKey(key); } }
2718 public Entry<K, V> firstEntry()
2719 { synchronized (mutex) { return nm.firstEntry(); } }
2720 public Entry<K, V> lastEntry()
2721 { synchronized (mutex) { return nm.lastEntry(); } }
2722 public Entry<K, V> pollFirstEntry()
2723 { synchronized (mutex) { return nm.pollFirstEntry(); } }
2724 public Entry<K, V> pollLastEntry()
2725 { synchronized (mutex) { return nm.pollLastEntry(); } }
2726
2727 public NavigableMap<K, V> descendingMap() {
2728 synchronized (mutex) {
2729 return (NavigableMap<K,V>)
2730 new SynchronizedNavigableMap(nm.descendingMap(), mutex);
2731 }
2732 }
2733
2734 public NavigableSet<K> navigableKeySet() {
2735 synchronized (mutex) {
2736 return new SynchronizedNavigableSet(nm.navigableKeySet(), mutex);
2737 }
2738 }
2739
2740 public NavigableSet<K> descendingKeySet() {
2741 synchronized (mutex) {
2742 return new SynchronizedNavigableSet(nm.descendingKeySet(), mutex);
2743 }
2744 }
2745
2746 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2747 synchronized (mutex) {
2748 return (NavigableMap<K,V>) new SynchronizedNavigableMap(
2749 nm.subMap(fromKey, fromInclusive, toKey, toInclusive), mutex);
2750 }
2751 }
2752
2753 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
2754 synchronized (mutex) {
2755 return (NavigableMap<K,V>) new SynchronizedNavigableMap(
2756 nm.headMap(toKey, inclusive), mutex);
2757 }
2758 }
2759
2760 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
2761 synchronized (mutex) {
2762 return (NavigableMap<K,V>) new SynchronizedNavigableMap(
2763 nm.tailMap(fromKey, inclusive), mutex);
2764 }
2765 }
2766 }
2767
2768 // Dynamically typesafe collection wrappers
2769
2770 /**
2771 * Returns a dynamically typesafe view of the specified collection.
2772 * Any attempt to insert an element of the wrong type will result in an
2773 * immediate {@link ClassCastException}. Assuming a collection
2774 * contains no incorrectly typed elements prior to the time a
2775 * dynamically typesafe view is generated, and that all subsequent
2776 * access to the collection takes place through the view, it is
2777 * <i>guaranteed</i> that the collection cannot contain an incorrectly
2778 * typed element.
2779 *
2780 * <p>The generics mechanism in the language provides compile-time
2781 * (static) type checking, but it is possible to defeat this mechanism
2782 * with unchecked casts. Usually this is not a problem, as the compiler
2783 * issues warnings on all such unchecked operations. There are, however,
2784 * times when static type checking alone is not sufficient. For example,
2785 * suppose a collection is passed to a third-party library and it is
2786 * imperative that the library code not corrupt the collection by
2787 * inserting an element of the wrong type.
2788 *
2789 * <p>Another use of dynamically typesafe views is debugging. Suppose a
2790 * program fails with a {@code ClassCastException}, indicating that an
2791 * incorrectly typed element was put into a parameterized collection.
2792 * Unfortunately, the exception can occur at any time after the erroneous
2793 * element is inserted, so it typically provides little or no information
2794 * as to the real source of the problem. If the problem is reproducible,
2795 * one can quickly determine its source by temporarily modifying the
2796 * program to wrap the collection with a dynamically typesafe view.
2797 * For example, this declaration:
2798 * <pre> {@code
2799 * Collection<String> c = new HashSet<>();
2800 * }</pre>
2801 * may be replaced temporarily by this one:
2802 * <pre> {@code
2803 * Collection<String> c = Collections.checkedCollection(
2804 * new HashSet<>(), String.class);
2805 * }</pre>
2806 * Running the program again will cause it to fail at the point where
2807 * an incorrectly typed element is inserted into the collection, clearly
2808 * identifying the source of the problem. Once the problem is fixed, the
2809 * modified declaration may be reverted back to the original.
2810 *
2811 * <p>The returned collection does <i>not</i> pass the hashCode and equals
2812 * operations through to the backing collection, but relies on
2813 * {@code Object}'s {@code equals} and {@code hashCode} methods. This
2814 * is necessary to preserve the contracts of these operations in the case
2815 * that the backing collection is a set or a list.
2816 *
2817 * <p>The returned collection will be serializable if the specified
2818 * collection is serializable.
2819 *
2820 * <p>Since {@code null} is considered to be a value of any reference
2821 * type, the returned collection permits insertion of null elements
2822 * whenever the backing collection does.
2823 *
2824 * @param c the collection for which a dynamically typesafe view is to be
3070 * whenever the backing sorted set does.
3071 *
3072 * @param s the sorted set for which a dynamically typesafe view is to be
3073 * returned
3074 * @param type the type of element that {@code s} is permitted to hold
3075 * @return a dynamically typesafe view of the specified sorted set
3076 * @since 1.5
3077 */
3078 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
3079 Class<E> type) {
3080 return new CheckedSortedSet<>(s, type);
3081 }
3082
3083 /**
3084 * @serial include
3085 */
3086 static class CheckedSortedSet<E> extends CheckedSet<E>
3087 implements SortedSet<E>, Serializable
3088 {
3089 private static final long serialVersionUID = 1599911165492914959L;
3090
3091 private final SortedSet<E> ss;
3092
3093 CheckedSortedSet(SortedSet<E> s, Class<E> type) {
3094 super(s, type);
3095 ss = s;
3096 }
3097
3098 public Comparator<? super E> comparator() { return ss.comparator(); }
3099 public E first() { return ss.first(); }
3100 public E last() { return ss.last(); }
3101
3102 public SortedSet<E> subSet(E fromElement, E toElement) {
3103 return checkedSortedSet(ss.subSet(fromElement,toElement), type);
3104 }
3105 public SortedSet<E> headSet(E toElement) {
3106 return checkedSortedSet(ss.headSet(toElement), type);
3107 }
3108 public SortedSet<E> tailSet(E fromElement) {
3109 return checkedSortedSet(ss.tailSet(fromElement), type);
3110 }
3111 }
3112
3113 /**
3114 * Returns a dynamically typesafe view of the specified navigable set.
3115 * Any attempt to insert an element of the wrong type will result in an
3116 * immediate {@link ClassCastException}. Assuming a navigable set
3117 * contains no incorrectly typed elements prior to the time a
3118 * dynamically typesafe view is generated, and that all subsequent
3119 * access to the navigable set takes place through the view, it is
3120 * <em>guaranteed</em> that the navigable set cannot contain an incorrectly
3121 * typed element.
3122 *
3123 * <p>A discussion of the use of dynamically typesafe views may be
3124 * found in the documentation for the {@link #checkedCollection
3125 * checkedCollection} method.
3126 *
3127 * <p>The returned navigable set will be serializable if the specified
3128 * navigable set is serializable.
3129 *
3130 * <p>Since {@code null} is considered to be a value of any reference
3131 * type, the returned navigable set permits insertion of null elements
3132 * whenever the backing sorted set does.
3133 *
3134 * @param s the navigable set for which a dynamically typesafe view is to be
3135 * returned
3136 * @param type the type of element that {@code s} is permitted to hold
3137 * @return a dynamically typesafe view of the specified navigable set
3138 * @since 1.8
3139 */
3140 public static <E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s,
3141 Class<E> type) {
3142 return new CheckedNavigableSet<>(s, type);
3143 }
3144
3145 /**
3146 * @serial include
3147 */
3148 static class CheckedNavigableSet<E> extends CheckedSortedSet<E>
3149 implements NavigableSet<E>, Serializable
3150 {
3151 private static final long serialVersionUID = -5429120189805438922L;
3152
3153 private final NavigableSet<E> ns;
3154
3155 CheckedNavigableSet(NavigableSet<E> s, Class<E> type) {
3156 super(s, type);
3157 ns = s;
3158 }
3159
3160 public E lower(E e) { return ns.lower(e); }
3161 public E floor(E e) { return ns.floor(e); }
3162 public E ceiling(E e) { return ns.ceiling(e); }
3163 public E higher(E e) { return ns.higher(e); }
3164 public E pollFirst() { return ns.pollFirst(); }
3165 public E pollLast() {return ns.pollLast(); }
3166 public NavigableSet<E> descendingSet()
3167 { return checkedNavigableSet(ns.descendingSet(), type); }
3168 public Iterator<E> descendingIterator()
3169 {return checkedNavigableSet(ns.descendingSet(), type).iterator(); }
3170
3171 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
3172 return checkedNavigableSet(ns.subSet(fromElement, fromInclusive, toElement, toInclusive), type);
3173 }
3174
3175 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
3176 return checkedNavigableSet(ns.headSet(toElement, inclusive), type);
3177 }
3178
3179 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
3180 return checkedNavigableSet(ns.tailSet(fromElement, inclusive), type);
3181 }
3182 }
3183
3184 /**
3185 * Returns a dynamically typesafe view of the specified list.
3186 * Any attempt to insert an element of the wrong type will result in
3187 * an immediate {@link ClassCastException}. Assuming a list contains
3188 * no incorrectly typed elements prior to the time a dynamically typesafe
3189 * view is generated, and that all subsequent access to the list
3190 * takes place through the view, it is <i>guaranteed</i> that the
3191 * list cannot contain an incorrectly typed element.
3192 *
3193 * <p>A discussion of the use of dynamically typesafe views may be
3194 * found in the documentation for the {@link #checkedCollection
3195 * checkedCollection} method.
3196 *
3197 * <p>The returned list will be serializable if the specified list
3198 * is serializable.
3199 *
3200 * <p>Since {@code null} is considered to be a value of any reference
3201 * type, the returned list permits insertion of null elements whenever
3202 * the backing list does.
3203 *
3376 BiFunction<? super K, ? super V, ? extends V> func) {
3377 Objects.requireNonNull(func);
3378 return (k, v) -> {
3379 V newValue = func.apply(k, v);
3380 typeCheck(k, newValue);
3381 return newValue;
3382 };
3383 }
3384
3385 private String badKeyMsg(Object key) {
3386 return "Attempt to insert " + key.getClass() +
3387 " key into map with key type " + keyType;
3388 }
3389
3390 private String badValueMsg(Object value) {
3391 return "Attempt to insert " + value.getClass() +
3392 " value into map with value type " + valueType;
3393 }
3394
3395 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
3396 this.m = Objects.requireNonNull(m);
3397 this.keyType = Objects.requireNonNull(keyType);
3398 this.valueType = Objects.requireNonNull(valueType);
3399 }
3400
3401 public int size() { return m.size(); }
3402 public boolean isEmpty() { return m.isEmpty(); }
3403 public boolean containsKey(Object key) { return m.containsKey(key); }
3404 public boolean containsValue(Object v) { return m.containsValue(v); }
3405 public V get(Object key) { return m.get(key); }
3406 public V remove(Object key) { return m.remove(key); }
3407 public void clear() { m.clear(); }
3408 public Set<K> keySet() { return m.keySet(); }
3409 public Collection<V> values() { return m.values(); }
3410 public boolean equals(Object o) { return o == this || m.equals(o); }
3411 public int hashCode() { return m.hashCode(); }
3412 public String toString() { return m.toString(); }
3413
3414 public V put(K key, V value) {
3415 typeCheck(key, value);
3416 return m.put(key, value);
3417 }
3418
3759 super(m, keyType, valueType);
3760 sm = m;
3761 }
3762
3763 public Comparator<? super K> comparator() { return sm.comparator(); }
3764 public K firstKey() { return sm.firstKey(); }
3765 public K lastKey() { return sm.lastKey(); }
3766
3767 public SortedMap<K,V> subMap(K fromKey, K toKey) {
3768 return checkedSortedMap(sm.subMap(fromKey, toKey),
3769 keyType, valueType);
3770 }
3771 public SortedMap<K,V> headMap(K toKey) {
3772 return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
3773 }
3774 public SortedMap<K,V> tailMap(K fromKey) {
3775 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
3776 }
3777 }
3778
3779 /**
3780 * Returns a dynamically typesafe view of the specified navigable map.
3781 * Any attempt to insert a mapping whose key or value have the wrong
3782 * type will result in an immediate {@link ClassCastException}.
3783 * Similarly, any attempt to modify the value currently associated with
3784 * a key will result in an immediate {@link ClassCastException},
3785 * whether the modification is attempted directly through the map
3786 * itself, or through a {@link Map.Entry} instance obtained from the
3787 * map's {@link Map#entrySet() entry set} view.
3788 *
3789 * <p>Assuming a map contains no incorrectly typed keys or values
3790 * prior to the time a dynamically typesafe view is generated, and
3791 * that all subsequent access to the map takes place through the view
3792 * (or one of its collection views), it is <em>guaranteed</em> that the
3793 * map cannot contain an incorrectly typed key or value.
3794 *
3795 * <p>A discussion of the use of dynamically typesafe views may be
3796 * found in the documentation for the {@link #checkedCollection
3797 * checkedCollection} method.
3798 *
3799 * <p>The returned map will be serializable if the specified map is
3800 * serializable.
3801 *
3802 * <p>Since {@code null} is considered to be a value of any reference
3803 * type, the returned map permits insertion of null keys or values
3804 * whenever the backing map does.
3805 *
3806 * @param <K> type of map keys
3807 * @param <V> type of map values
3808 * @param m the map for which a dynamically typesafe view is to be
3809 * returned
3810 * @param keyType the type of key that {@code m} is permitted to hold
3811 * @param valueType the type of value that {@code m} is permitted to hold
3812 * @return a dynamically typesafe view of the specified map
3813 * @since 1.8
3814 */
3815 public static <K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K, V> m,
3816 Class<K> keyType,
3817 Class<V> valueType) {
3818 return new CheckedNavigableMap<>(m, keyType, valueType);
3819 }
3820
3821 /**
3822 * @serial include
3823 */
3824 static class CheckedNavigableMap<K,V> extends CheckedSortedMap<K,V>
3825 implements NavigableMap<K,V>, Serializable
3826 {
3827 private static final long serialVersionUID = -4852462692372534096L;
3828
3829 private final NavigableMap<K, V> nm;
3830
3831 CheckedNavigableMap(NavigableMap<K, V> m,
3832 Class<K> keyType, Class<V> valueType) {
3833 super(m, keyType, valueType);
3834 nm = m;
3835 }
3836
3837 public Comparator<? super K> comparator() { return nm.comparator(); }
3838 public K firstKey() { return nm.firstKey(); }
3839 public K lastKey() { return nm.lastKey(); }
3840
3841 public NavigableMap<K,V> subMap(K fromKey, K toKey) {
3842 return checkedNavigableMap(
3843 (NavigableMap<K,V>)
3844 nm.subMap(fromKey, toKey), keyType, valueType);
3845 }
3846 public NavigableMap<K,V> headMap(K toKey) {
3847 return checkedNavigableMap(
3848 (NavigableMap<K,V>)
3849 nm.headMap(toKey), keyType, valueType);
3850 }
3851 public NavigableMap<K,V> tailMap(K fromKey) {
3852 return checkedNavigableMap(
3853 (NavigableMap<K,V>)
3854 nm.tailMap(fromKey), keyType, valueType);
3855 }
3856
3857 public Entry<K, V> lowerEntry(K key) {
3858 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lowerEntry(key), valueType);
3859 }
3860
3861 public K lowerKey(K key) { return nm.lowerKey(key); }
3862
3863 public Entry<K, V> floorEntry(K key) {
3864 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lowerEntry(key), valueType);
3865 }
3866
3867 public K floorKey(K key) { return nm.floorKey(key); }
3868
3869 public Entry<K, V> ceilingEntry(K key) {
3870 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.ceilingEntry(key), valueType);
3871 }
3872
3873 public K ceilingKey(K key) { return nm.ceilingKey(key); }
3874
3875 public Entry<K, V> higherEntry(K key) {
3876 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.higherEntry(key), valueType);
3877 }
3878
3879 public K higherKey(K key) { return nm.higherKey(key); }
3880
3881 public Entry<K, V> firstEntry() {
3882 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.firstEntry(), valueType);
3883 }
3884
3885 public Entry<K, V> lastEntry() {
3886 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lastEntry(), valueType);
3887 }
3888
3889 public Entry<K, V> pollFirstEntry() {
3890 Entry<K,V> entry = nm.pollFirstEntry();
3891 return (null == entry) ? null : new CheckedMap.CheckedEntrySet.CheckedEntry(entry, valueType);
3892 }
3893
3894 public Entry<K, V> pollLastEntry() {
3895 Entry<K,V> entry = nm.pollLastEntry();
3896 return (null == entry) ? null : new CheckedMap.CheckedEntrySet.CheckedEntry(entry, valueType);
3897 }
3898
3899 public NavigableMap<K, V> descendingMap() {
3900 return checkedNavigableMap(nm.descendingMap(), keyType, valueType);
3901 }
3902
3903 public NavigableSet<K> navigableKeySet() {
3904 return checkedNavigableSet(nm.navigableKeySet(), keyType);
3905 }
3906
3907 public NavigableSet<K> descendingKeySet() {
3908 return checkedNavigableSet(nm.descendingKeySet(), keyType);
3909 }
3910
3911 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3912 return checkedNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive), keyType, valueType);
3913 }
3914
3915 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3916 return checkedNavigableMap(nm.headMap(toKey, inclusive), keyType, valueType);
3917 }
3918
3919 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3920 return checkedNavigableMap(nm.tailMap(fromKey, inclusive), keyType, valueType);
3921 }
3922 }
3923
3924 // Empty collections
3925
3926 /**
3927 * Returns an iterator that has no elements. More precisely,
3928 *
3929 * <ul compact>
3930 *
3931 * <li>{@link Iterator#hasNext hasNext} always returns {@code
3932 * false}.
3933 *
3934 * <li>{@link Iterator#next next} always throws {@link
3935 * NoSuchElementException}.
3936 *
3937 * <li>{@link Iterator#remove remove} always throws {@link
3938 * IllegalStateException}.
3939 *
3940 * </ul>
3941 *
3942 * <p>Implementations of this method are permitted, but not
3943 * required, to return the same object from multiple invocations.
3944 *
3945 * @return an empty iterator
3946 * @since 1.7
3947 */
3948 @SuppressWarnings("unchecked")
3949 public static <T> Iterator<T> emptyIterator() {
3950 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
4046 public boolean hasMoreElements() { return false; }
4047 public E nextElement() { throw new NoSuchElementException(); }
4048 }
4049
4050 /**
4051 * The empty set (immutable). This set is serializable.
4052 *
4053 * @see #emptySet()
4054 */
4055 @SuppressWarnings("rawtypes")
4056 public static final Set EMPTY_SET = new EmptySet<>();
4057
4058 /**
4059 * Returns the empty set (immutable). This set is serializable.
4060 * Unlike the like-named field, this method is parameterized.
4061 *
4062 * <p>This example illustrates the type-safe way to obtain an empty set:
4063 * <pre>
4064 * Set<String> s = Collections.emptySet();
4065 * </pre>
4066 * @implNote Implementations of this method need not create a separate
4067 * {@code Set} object for each call. Using this method is likely to have
4068 * comparable cost to using the like-named field. (Unlike this method, the
4069 * field does not provide type safety.)
4070 *
4071 * @return the empty set
4072 * @see #EMPTY_SET
4073 * @since 1.5
4074 */
4075 @SuppressWarnings("unchecked")
4076 public static final <T> Set<T> emptySet() {
4077 return (Set<T>) EMPTY_SET;
4078 }
4079
4080 /**
4081 * @serial include
4082 */
4083 private static class EmptySet<E>
4084 extends AbstractSet<E>
4085 implements Serializable
4086 {
4087 private static final long serialVersionUID = 1582296315990362920L;
4088
4089 public Iterator<E> iterator() { return emptyIterator(); }
4090
4091 public int size() {return 0;}
4105 // Override default methods in Collection
4106 @Override
4107 public void forEach(Consumer<? super E> action) {
4108 Objects.requireNonNull(action);
4109 }
4110 @Override
4111 public boolean removeIf(Predicate<? super E> filter) {
4112 Objects.requireNonNull(filter);
4113 return false;
4114 }
4115 @Override
4116 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
4117
4118 // Preserves singleton property
4119 private Object readResolve() {
4120 return EMPTY_SET;
4121 }
4122 }
4123
4124 /**
4125 * Returns an empty sorted set (immutable). This set is serializable.
4126 *
4127 * <p>This example illustrates the type-safe way to obtain an empty
4128 * sorted set:
4129 * <pre> {@code
4130 * SortedSet<String> s = Collections.emptySortedSet();
4131 * }</pre>
4132 *
4133 * @implNote Implementations of this method need not create a separate
4134 * {@code SortedSet} object for each call.
4135 *
4136 * @param <E> type of elements, if there were any, in the set
4137 * @return the empty sorted set
4138 * @since 1.8
4139 */
4140 @SuppressWarnings("unchecked")
4141 public static <E> SortedSet<E> emptySortedSet() {
4142 return (SortedSet<E>) EmptyNavigableSet.EMPTY_NAVIGABLE_SET;
4143 }
4144
4145 /**
4146 * Returns an empty navigable set (immutable). This set is serializable.
4147 *
4148 * <p>This example illustrates the type-safe way to obtain an empty
4149 * navigable set:
4150 * <pre> {@code
4151 * NavigableSet<String> s = Collections.emptyNavigableSet();
4152 * }</pre>
4153 *
4154 * @implNote Implementations of this method need not
4155 * create a separate {@code NavigableSet} object for each call.
4156 *
4157 * @param <E> type of elements, if there were any, in the set
4158 * @return the empty navigable set
4159 * @since 1.8
4160 */
4161 @SuppressWarnings("unchecked")
4162 public static <E> NavigableSet<E> emptyNavigableSet() {
4163 return (NavigableSet<E>) EmptyNavigableSet.EMPTY_NAVIGABLE_SET;
4164 }
4165
4166 /**
4167 * The empty list (immutable). This list is serializable.
4168 *
4169 * @see #emptyList()
4170 */
4171 @SuppressWarnings("rawtypes")
4172 public static final List EMPTY_LIST = new EmptyList<>();
4173
4174 /**
4175 * Returns the empty list (immutable). This list is serializable.
4176 *
4177 * <p>This example illustrates the type-safe way to obtain an empty list:
4178 * <pre>
4179 * List<String> s = Collections.emptyList();
4180 * </pre>
4181 * Implementation note: Implementations of this method need not
4182 * create a separate <tt>List</tt> object for each call. Using this
4183 * method is likely to have comparable cost to using the like-named
4243 public void sort(Comparator<? super E> c) {
4244 Objects.requireNonNull(c);
4245 }
4246
4247 // Override default methods in Collection
4248 @Override
4249 public void forEach(Consumer<? super E> action) {
4250 Objects.requireNonNull(action);
4251 }
4252
4253 @Override
4254 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
4255
4256 // Preserves singleton property
4257 private Object readResolve() {
4258 return EMPTY_LIST;
4259 }
4260 }
4261
4262 /**
4263 * An empty navigable map with enforced bounds upon the key set. The bounds
4264 * are generated via the various sub-map operations and enforced on
4265 * subsequent sub-map operations.
4266 *
4267 * @serial include
4268 *
4269 * @param <K> type of keys, if there were any, and bounds
4270 * @param <V> type of values, if there were any
4271 */
4272 private static class BoundedEmptyNavigableMap<K,V> extends EmptyNavigableMap<K,V>
4273 implements Serializable {
4274
4275 private static final long serialVersionUID = 5065418537829651507L;
4276
4277 /**
4278 * Our bounded keyset.
4279 */
4280 final BoundedEmptyNavigableSet keySet;
4281
4282 private BoundedEmptyNavigableMap(BoundedEmptyNavigableSet keySet) {
4283 this.keySet = Objects.requireNonNull(keySet);
4284 }
4285
4286 public Comparator<? super K> comparator()
4287 { return keySet.comparator(); }
4288
4289 @Override
4290 public NavigableMap<K, V> descendingMap() {
4291 NavigableSet<K> descending = keySet.descendingSet();
4292
4293 if(descending == Collections.emptyNavigableSet()) {
4294 return Collections.emptyNavigableMap();
4295 } else {
4296 return new BoundedEmptyNavigableMap((BoundedEmptyNavigableSet<K>) descending);
4297 }
4298 }
4299
4300 public BoundedEmptyNavigableSet<K> navigableKeySet() { return keySet; }
4301 public EmptyNavigableSet<K> descendingKeySet()
4302 { return keySet.descendingSet(); }
4303
4304 @Override
4305 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
4306 return new BoundedEmptyNavigableMap(keySet.subSet(
4307 fromKey, fromInclusive,
4308 toKey, toInclusive));
4309 }
4310
4311 @Override
4312 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
4313 return new BoundedEmptyNavigableMap(
4314 keySet.headSet(toKey, inclusive));
4315 }
4316
4317 @Override
4318 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
4319 return new BoundedEmptyNavigableMap(
4320 keySet.tailSet(fromKey, inclusive));
4321 }
4322 }
4323
4324 /**
4325 * @serial include
4326 *
4327 * @param <E> type of elements, if there were any
4328 */
4329 private static class EmptyNavigableSet<E> extends EmptySet<E>
4330 implements NavigableSet<E>, Serializable {
4331 private static final long serialVersionUID = -6291252904449939134L;
4332
4333 @SuppressWarnings("rawtypes")
4334 private static final NavigableSet EMPTY_NAVIGABLE_SET =
4335 new EmptyNavigableSet();
4336
4337 EmptyNavigableSet() { }
4338
4339 @Override
4340 public boolean contains(Object obj) {
4341 if( !(Objects.requireNonNull(obj) instanceof Comparable)) {
4342 throw new ClassCastException("Not Comparable");
4343 }
4344
4345 return false;
4346 }
4347
4348 // Preserves singleton property
4349 private Object readResolve()
4350 { return Collections.emptyNavigableSet(); }
4351 public E lower(E e) { return null; }
4352 public E floor(E e) { return null; }
4353 public E ceiling(E e) { return null; }
4354 public E higher(E e) { return null; }
4355 public E pollFirst() { throw new UnsupportedOperationException(); }
4356 public E pollLast() { throw new UnsupportedOperationException(); }
4357
4358 public EmptyNavigableSet<E> descendingSet() {
4359 return new BoundedEmptyNavigableSet(null, false, null, false, true);
4360 }
4361
4362 public Iterator<E> descendingIterator()
4363 { return Collections.emptyIterator(); }
4364
4365 public BoundedEmptyNavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
4366 return new BoundedEmptyNavigableSet<>(
4367 checkComparable(fromElement), fromInclusive,
4368 checkComparable(toElement), toInclusive,
4369 false);
4370 }
4371
4372 public BoundedEmptyNavigableSet<E> headSet(E toElement, boolean inclusive) {
4373 return new BoundedEmptyNavigableSet<>(
4374 null, false,
4375 checkComparable(toElement), inclusive,
4376 false);
4377 }
4378
4379 public BoundedEmptyNavigableSet<E> tailSet(E fromElement, boolean inclusive) {
4380 return new BoundedEmptyNavigableSet<>(
4381 checkComparable(fromElement), inclusive,
4382 null, false,
4383 false);
4384 }
4385
4386 public final SortedSet<E> subSet(E fromElement, E toElement)
4387 { return subSet(fromElement, true, toElement, false); }
4388 public final SortedSet<E> headSet(E toElement)
4389 { return headSet(toElement, false); }
4390 public final SortedSet<E> tailSet(E fromElement)
4391 { return tailSet(fromElement, true); }
4392
4393 public Comparator<? super E> comparator() { return null; }
4394 public E first() { throw new NoSuchElementException(); }
4395 public E last() { throw new NoSuchElementException(); }
4396
4397 /**
4398 * Ensures that the specified object is non-null and Comparable.
4399 * @param <E> type of references
4400 * @param obj the instance to check
4401 * @return the reference as a Comparable
4402 */
4403 static <E> Comparable<E> checkComparable(E obj) {
4404 return (Comparable<E>) Objects.requireNonNull(obj);
4405 }
4406 }
4407
4408 /**
4409 * An empty NavigableSet but bounds are maintained. If you try to sub-set
4410 * outside the bounds you will get an IllegalArgumentException.
4411 *
4412 * @serial include
4413 *
4414 * @param <E> type of elements, if there were any, and bounds
4415 */
4416 private static class BoundedEmptyNavigableSet<E> extends EmptyNavigableSet<E>
4417 implements Serializable {
4418 private static final long serialVersionUID = 3393358742248855583L;
4419
4420 /**
4421 * {@code true} if lowerBound is "greater" than upperBound.
4422 */
4423 final boolean descending;
4424 /**
4425 * {@code true} if lowerBound is inclusive.
4426 */
4427 final boolean lowerInclusive;
4428 /**
4429 * {@code true} if upperBound is inclusive.
4430 */
4431 final boolean upperInclusive;
4432 /**
4433 * The lower bound of the set.
4434 */
4435 final Comparable<E> lowerBound;
4436 /**
4437 * The upper bound of the set.
4438 */
4439 final Comparable<E> upperBound;
4440
4441 public BoundedEmptyNavigableSet(
4442 Comparable<E> fromElement, boolean lowerInclusive,
4443 Comparable<E> toElement, boolean upperInclusive,
4444 boolean descending) {
4445 this.descending = descending;
4446
4447 if ((fromElement != null) && (toElement != null)) {
4448 // both bounds are present we need to ensure that they make
4449 // sense.
4450 int fromCompared = Integer.signum(fromElement.compareTo((E)toElement));
4451 int toCompared = Integer.signum(toElement.compareTo((E)fromElement));
4452
4453 if(fromCompared != -toCompared) {
4454 throw new IllegalArgumentException("inconsistent compareTo");
4455 }
4456
4457 if (descending) {
4458 if (fromCompared < 0) {
4459 throw new IllegalArgumentException();
4460 }
4461 } else {
4462 if (fromCompared > 0) {
4463 throw new IllegalArgumentException();
4464 }
4465 }
4466 }
4467
4468 this.lowerBound = fromElement;
4469 this.lowerInclusive = lowerInclusive;
4470 this.upperBound = toElement;
4471 this.upperInclusive = upperInclusive;
4472 }
4473
4474 @Override
4475 public Comparator<? super E> comparator()
4476 { return descending ? Collections.reverseOrder() : null; }
4477
4478 private Comparable<E> inBounds(E element) {
4479 if (!descending) {
4480 if (null != lowerBound) {
4481 if (lowerInclusive) {
4482 if (lowerBound.compareTo(element) > 0) {
4483 throw new IllegalArgumentException("out of bounds");
4484 }
4485 } else {
4486 if (lowerBound.compareTo(element) >= 0) {
4487 throw new IllegalArgumentException("out of bounds");
4488 }
4489 }
4490 }
4491
4492 if (null != upperBound) {
4493 if (upperInclusive) {
4494 if (upperBound.compareTo(element) < 0) {
4495 throw new IllegalArgumentException("out of bounds");
4496 }
4497 } else {
4498 if (upperBound.compareTo(element) <= 0) {
4499 throw new IllegalArgumentException("out of bounds");
4500 }
4501 }
4502 }
4503 } else {
4504 if (null != lowerBound) {
4505 if (lowerInclusive) {
4506 if (lowerBound.compareTo(element) < 0) {
4507 throw new IllegalArgumentException("out of bounds");
4508 }
4509 } else {
4510 if (lowerBound.compareTo(element) <= 0) {
4511 throw new IllegalArgumentException("out of bounds");
4512 }
4513 }
4514 }
4515
4516 if (null != upperBound) {
4517 if (upperInclusive) {
4518 if (upperBound.compareTo(element) > 0) {
4519 throw new IllegalArgumentException("out of bounds");
4520 }
4521 } else {
4522 if (upperBound.compareTo(element) >= 0) {
4523 throw new IllegalArgumentException("out of bounds");
4524 }
4525 }
4526 }
4527 }
4528
4529 return EmptyNavigableSet.checkComparable(element);
4530 }
4531
4532 @Override
4533 public EmptyNavigableSet<E> descendingSet() {
4534 if (upperBound == null && lowerBound == null && descending) {
4535 return (EmptyNavigableSet) Collections.emptyNavigableSet();
4536 }
4537 return new BoundedEmptyNavigableSet(
4538 upperBound, upperInclusive,
4539 lowerBound, lowerInclusive,
4540 !descending);
4541 }
4542
4543 @Override
4544 public BoundedEmptyNavigableSet<E> subSet(E fromKey, boolean fromInclusive, E toKey, boolean toInclusive) {
4545 return new BoundedEmptyNavigableSet(
4546 inBounds(fromKey), fromInclusive,
4547 inBounds(toKey), toInclusive,
4548 descending);
4549 }
4550
4551 @Override
4552 public BoundedEmptyNavigableSet<E> headSet(E toKey, boolean inclusive) {
4553 return new BoundedEmptyNavigableSet(
4554 lowerBound, lowerInclusive,
4555 inBounds(Objects.requireNonNull(toKey)), inclusive,
4556 descending);
4557 }
4558
4559 @Override
4560 public BoundedEmptyNavigableSet<E> tailSet(E fromKey, boolean inclusive) {
4561 return new BoundedEmptyNavigableSet(
4562 inBounds(Objects.requireNonNull(fromKey)), inclusive,
4563 upperBound, upperInclusive,
4564 descending);
4565 }
4566 }
4567
4568 /**
4569 * The empty map (immutable). This map is serializable.
4570 *
4571 * @see #emptyMap()
4572 * @since 1.3
4573 */
4574 @SuppressWarnings("rawtypes")
4575 public static final Map EMPTY_MAP = new EmptyMap<>();
4576
4577 /**
4578 * Returns the empty map (immutable). This map is serializable.
4579 *
4580 * <p>This example illustrates the type-safe way to obtain an empty map:
4581 * <pre>
4582 * Map<String, Date> s = Collections.emptyMap();
4583 * </pre>
4584 * @implNote Implementations of this method need not create a separate
4585 * {@code Map} object for each call. Using this method is likely to have
4586 * comparable cost to using the like-named field. (Unlike this method, the
4587 * field does not provide type safety.)
4588 *
4589 * @return an empty map
4590 * @see #EMPTY_MAP
4591 * @since 1.5
4592 */
4593 @SuppressWarnings("unchecked")
4594 public static final <K,V> Map<K,V> emptyMap() {
4595 return (Map<K,V>) EMPTY_MAP;
4596 }
4597
4598 /**
4599 * Returns an empty sorted map (immutable). This map is serializable.
4600 *
4601 * <p>This example illustrates the type-safe way to obtain an empty map:
4602 * <pre> {@code
4603 * SortedMap<String, Date> s = Collections.emptySortedMap();
4604 * }</pre>
4605 *
4606 * @implNote Implementations of this method need not create a separate
4607 * {@code SortedMap} object for each call.
4608 *
4609 * @return an empty sorted map
4610 * @since 1.8
4611 */
4612 @SuppressWarnings("unchecked")
4613 public static final <K,V> SortedMap<K,V> emptySortedMap() {
4614 return (SortedMap<K,V>) EmptyNavigableMap.EMPTY_NAVIGABLE_MAP;
4615 }
4616
4617 /**
4618 * Returns an empty navigable map (immutable). This map is serializable.
4619 *
4620 * <p>This example illustrates the type-safe way to obtain an empty map:
4621 * <pre> {@code
4622 * NavigableMap<String, Date> s = Collections.emptyNavigableMap();
4623 * }</pre>
4624 *
4625 * @implNote Implementations of this method need not create a separate
4626 * {@code NavigableMap} object for each call.
4627 *
4628 * @return an empty navigable map
4629 * @since 1.8
4630 */
4631 @SuppressWarnings("unchecked")
4632 public static final <K,V> NavigableMap<K,V> emptyNavigableMap() {
4633 return (NavigableMap<K,V>) EmptyNavigableMap.EMPTY_NAVIGABLE_MAP;
4634 }
4635
4636 /**
4637 * @serial include
4638 */
4639 private static class EmptyMap<K,V>
4640 extends AbstractMap<K,V>
4641 implements Serializable
4642 {
4643 private static final long serialVersionUID = 6428348081105594320L;
4644
4645 public int size() {return 0;}
4646 public boolean isEmpty() {return true;}
4647 public boolean containsKey(Object key) {return false;}
4648 public boolean containsValue(Object value) {return false;}
4649 public V get(Object key) {return null;}
4650 public Set<K> keySet() {return emptySet();}
4651 public Collection<V> values() {return emptySet();}
4652 public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
4653
4654 public boolean equals(Object o) {
4655 return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
4656 }
4707 }
4708
4709 @Override
4710 public V compute(K key,
4711 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
4712 throw new UnsupportedOperationException();
4713 }
4714
4715 @Override
4716 public V merge(K key, V value,
4717 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
4718 throw new UnsupportedOperationException();
4719 }
4720
4721 // Preserves singleton property
4722 private Object readResolve() {
4723 return EMPTY_MAP;
4724 }
4725 }
4726
4727 /**
4728 * An empty navigable map.
4729 *
4730 * @param <K> type of keys, if there were any in this map
4731 * @param <V> type of values, if there were any in this map
4732 *
4733 * @serial include
4734 */
4735 private static class EmptyNavigableMap<K,V> extends EmptyMap<K,V>
4736 implements NavigableMap<K,V>, Serializable {
4737 private static final long serialVersionUID = -2239321462712562324L;
4738
4739 @SuppressWarnings("rawtypes")
4740 private static final NavigableMap EMPTY_NAVIGABLE_MAP =
4741 new EmptyNavigableMap();
4742
4743 EmptyNavigableMap() {}
4744
4745 @Override
4746 public boolean containsKey(Object obj) {
4747 checkComparable(obj);
4748 return false;
4749 }
4750
4751 // Preserves singleton property
4752 private Object readResolve() { return Collections.emptyNavigableMap();}
4753
4754 public final K firstKey() { throw new NoSuchElementException(); }
4755 public final K lastKey() { throw new NoSuchElementException(); }
4756
4757 public Entry<K, V> lowerEntry(K key) {
4758 checkComparable(key);
4759 return null;
4760 }
4761
4762 public K lowerKey(K key) {
4763 checkComparable(key);
4764 return null;
4765 }
4766
4767 public Entry<K, V> floorEntry(K key) {
4768 checkComparable(key);
4769 return null;
4770 }
4771
4772 public K floorKey(K key) {
4773 checkComparable(key);
4774 return null;
4775 }
4776
4777 public Entry<K, V> ceilingEntry(K key) {
4778 checkComparable(key);
4779 return null;
4780 }
4781
4782 public K ceilingKey(K key) {
4783 checkComparable(key);
4784 return null;
4785 }
4786
4787 public Entry<K, V> higherEntry(K key) {
4788 checkComparable(key);
4789 return null;
4790 }
4791
4792 public K higherKey(K key) {
4793 checkComparable(key);
4794 return null;
4795 }
4796
4797 public Entry<K, V> firstEntry() { return null; }
4798 public Entry<K, V> lastEntry() { return null; }
4799 public Entry<K, V> pollFirstEntry()
4800 { throw new UnsupportedOperationException(); }
4801 public Entry<K, V> pollLastEntry()
4802 { throw new UnsupportedOperationException(); }
4803
4804 public NavigableMap<K, V> descendingMap() {
4805 EmptyNavigableSet<K> descendingKeys = descendingKeySet();
4806
4807 if(descendingKeys == emptyNavigableSet()) {
4808 return emptyNavigableMap();
4809 } else {
4810 return new BoundedEmptyNavigableMap<>((BoundedEmptyNavigableSet<K>) descendingKeys);
4811 }
4812 }
4813
4814 public EmptyNavigableSet<K> navigableKeySet()
4815 { return (EmptyNavigableSet<K>) Collections.emptyNavigableSet(); }
4816 public EmptyNavigableSet<K> descendingKeySet() {
4817 return navigableKeySet().descendingSet();
4818 }
4819
4820 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
4821 return new BoundedEmptyNavigableMap<>(
4822 ((EmptyNavigableSet<K>) Collections.emptyNavigableSet()).subSet(
4823 fromKey, fromInclusive,
4824 toKey, toInclusive));
4825 }
4826
4827 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
4828 return new BoundedEmptyNavigableMap<>(
4829 ((EmptyNavigableSet<K>) Collections.emptyNavigableSet())
4830 .headSet(toKey, inclusive));
4831 }
4832
4833 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
4834 return new BoundedEmptyNavigableMap<>(
4835 ((EmptyNavigableSet<K>) Collections.emptyNavigableSet())
4836 .tailSet(fromKey, inclusive));
4837 }
4838
4839 public final SortedMap<K, V> subMap(K fromKey, K toKey)
4840 { return subMap(fromKey, true, toKey, false); }
4841 public final SortedMap<K, V> headMap(K toKey)
4842 { return headMap(toKey, false); }
4843 public final SortedMap<K, V> tailMap(K fromKey)
4844 { return tailMap(fromKey, true); }
4845 public Comparator<? super K> comparator() { return null; }
4846
4847 /**
4848 * Ensures that the specified object is non-null and Comparable.
4849 * @param <E> type of references
4850 * @param obj the instance to check
4851 * @return the reference as a Comparable
4852 */
4853 static <E> Comparable<E> checkComparable(E obj) {
4854 return (Comparable<E>) Objects.requireNonNull(obj);
4855 }
4856
4857 }
4858
4859 // Singleton collections
4860
4861 /**
4862 * Returns an immutable set containing only the specified object.
4863 * The returned set is serializable.
4864 *
4865 * @param o the sole object to be stored in the returned set.
4866 * @return an immutable set containing only the specified object.
4867 */
4868 public static <T> Set<T> singleton(T o) {
4869 return new SingletonSet<>(o);
4870 }
4871
4872 static <E> Iterator<E> singletonIterator(final E e) {
4873 return new Iterator<E>() {
4874 private boolean hasNext = true;
4875 public boolean hasNext() {
4876 return hasNext;
4877 }
4878 public E next() {
5053 return new SingletonMap<>(key, value);
5054 }
5055
5056 /**
5057 * @serial include
5058 */
5059 private static class SingletonMap<K,V>
5060 extends AbstractMap<K,V>
5061 implements Serializable {
5062 private static final long serialVersionUID = -6979724477215052911L;
5063
5064 private final K k;
5065 private final V v;
5066
5067 SingletonMap(K key, V value) {
5068 k = key;
5069 v = value;
5070 }
5071
5072 public int size() {return 1;}
5073 public boolean isEmpty() {return false;}
5074 public boolean containsKey(Object key) {return eq(key, k);}
5075 public boolean containsValue(Object value) {return eq(value, v);}
5076 public V get(Object key) {return (eq(key, k) ? v : null);}
5077
5078 private transient Set<K> keySet = null;
5079 private transient Set<Map.Entry<K,V>> entrySet = null;
5080 private transient Collection<V> values = null;
5081
5082 public Set<K> keySet() {
5083 if (keySet==null)
5084 keySet = singleton(k);
5085 return keySet;
5086 }
5087
5088 public Set<Map.Entry<K,V>> entrySet() {
5089 if (entrySet==null)
5090 entrySet = Collections.<Map.Entry<K,V>>singleton(
5091 new SimpleImmutableEntry<>(k, v));
5092 return entrySet;
5093 }
5094
5095 public Collection<V> values() {
5393 * legacy APIs that return enumerations and new APIs that require
5394 * collections.
5395 *
5396 * @param e enumeration providing elements for the returned
5397 * array list
5398 * @return an array list containing the elements returned
5399 * by the specified enumeration.
5400 * @since 1.4
5401 * @see Enumeration
5402 * @see ArrayList
5403 */
5404 public static <T> ArrayList<T> list(Enumeration<T> e) {
5405 ArrayList<T> l = new ArrayList<>();
5406 while (e.hasMoreElements())
5407 l.add(e.nextElement());
5408 return l;
5409 }
5410
5411 /**
5412 * Returns true if the specified arguments are equal, or both null.
5413 *
5414 * NB: Do not replace with Object.equals until JDK-8015417 is resolved.
5415 */
5416 static boolean eq(Object o1, Object o2) {
5417 return o1==null ? o2==null : o1.equals(o2);
5418 }
5419
5420 /**
5421 * Returns the number of elements in the specified collection equal to the
5422 * specified object. More formally, returns the number of elements
5423 * <tt>e</tt> in the collection such that
5424 * <tt>(o == null ? e == null : o.equals(e))</tt>.
5425 *
5426 * @param c the collection in which to determine the frequency
5427 * of <tt>o</tt>
5428 * @param o the object whose frequency is to be determined
5429 * @throws NullPointerException if <tt>c</tt> is null
5430 * @since 1.5
5431 */
5432 public static int frequency(Collection<?> c, Object o) {
5433 int result = 0;
5434 if (o == null) {
5637 @Override
5638 public void forEach(Consumer<? super E> action) {
5639 s.forEach(action);
5640 }
5641 @Override
5642 public boolean removeIf(Predicate<? super E> filter) {
5643 return s.removeIf(filter);
5644 }
5645
5646 @Override
5647 public Spliterator<E> spliterator() {return s.spliterator();}
5648
5649 private static final long serialVersionUID = 2454657854757543876L;
5650
5651 private void readObject(java.io.ObjectInputStream stream)
5652 throws IOException, ClassNotFoundException
5653 {
5654 stream.defaultReadObject();
5655 s = m.keySet();
5656 }
5657 }
5658
5659 /**
5660 * Returns a navigable set backed by the specified navigable map. The
5661 * resulting navigable set displays the same ordering, concurrency, and
5662 * performance characteristics as the backing map. In essence, this factory
5663 * method provides a {@link NavigableSet} implementation corresponding to
5664 * any {@link NavigableMap} implementation. There is no need to use this
5665 * method on a {@link NavigableMap} implementation that already has a
5666 * corresponding {@link NavigableSet} implementation
5667 * (such as {@link TreeMap}).
5668 *
5669 * <p>Each method invocation on the set returned by this method results in
5670 * exactly one method invocation on the backing map or its {@code keySet}
5671 * view, with one exception. The {@code addAll} method is implemented
5672 * as a sequence of {@code put} invocations on the backing map.
5673 *
5674 * <p>The specified map must be empty at the time this method is invoked,
5675 * and should not be accessed directly after this method returns. These
5676 * conditions are ensured if the map is created empty, passed directly
5677 * to this method, and no reference to the map is retained, as illustrated
5678 * in the following code fragment:
5679 * <pre> {@code
5680 * Set<Object> weakHashSet = Collections.newNavigableSetFromNavigableMap(
5681 * new WeakHashMap<Object, Boolean>());
5682 * }</pre>
5683 *
5684 * @param map the backing navigable map
5685 * @return the navigable set backed by the map
5686 * @throws IllegalArgumentException if {@code map} is not empty
5687 * @throws NullPointerException if {@code map} is null
5688 * @since 1.8
5689 */
5690 public static <E> NavigableSet<E> newNavigableSetFromNavigableMap(NavigableMap<E, Boolean> map) {
5691 return new NavigableSetFromNavigableMap<>(map);
5692 }
5693
5694 /**
5695 * @serial include
5696 */
5697 private static class NavigableSetFromNavigableMap<E> extends AbstractSet<E>
5698 implements NavigableSet<E>, Serializable
5699 {
5700 private static final long serialVersionUID = -7303807726339382839L;
5701
5702 private final NavigableMap<E, Boolean> m; // The backing map
5703 private transient NavigableSet<E> s; // Its keySet
5704
5705 NavigableSetFromNavigableMap(NavigableMap<E, Boolean> map) {
5706 if (!map.isEmpty())
5707 throw new IllegalArgumentException("Map is non-empty");
5708 m = map;
5709 s = map.navigableKeySet();
5710 }
5711
5712 public void clear() { m.clear(); }
5713 public int size() { return m.size(); }
5714 public boolean isEmpty() { return m.isEmpty(); }
5715 public boolean contains(Object o) { return m.containsKey(o); }
5716 public boolean remove(Object o) { return m.remove(o) != null; }
5717 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
5718 public Iterator<E> iterator() { return s.iterator(); }
5719 public Object[] toArray() { return s.toArray(); }
5720 public <T> T[] toArray(T[] a) { return s.toArray(a); }
5721 public String toString() { return s.toString(); }
5722 public int hashCode() { return s.hashCode(); }
5723 public boolean equals(Object o) { return o == this || s.equals(o); }
5724 public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
5725 public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
5726 public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
5727 // addAll is the only inherited implementation
5728
5729 // Override default methods in Collection
5730 @Override
5731 public void forEach(Consumer<? super E> action) { s.forEach(action); }
5732 @Override
5733 public boolean removeIf(Predicate<? super E> filter) {
5734 return s.removeIf(filter);
5735 }
5736
5737 @Override
5738 public Spliterator<E> spliterator() {return s.spliterator();}
5739
5740 private void readObject(java.io.ObjectInputStream stream)
5741 throws IOException, ClassNotFoundException {
5742 stream.defaultReadObject();
5743 if (null == m) {
5744 throw new InvalidObjectException("null map");
5745 }
5746 s = m.navigableKeySet();
5747 }
5748
5749 public E lower(E e) { return m.lowerKey(e); }
5750 public E floor(E e) { return m.floorKey(e); }
5751 public E ceiling(E e) { return m.ceilingKey(e); }
5752 public E higher(E e) { return m.higherKey(e); }
5753 public E pollFirst() { return s.pollFirst(); }
5754 public E pollLast() { return s.pollLast(); }
5755 public NavigableSet<E> descendingSet() { return s.descendingSet(); }
5756 public Iterator<E> descendingIterator(){return s.descendingIterator();}
5757
5758 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
5759 return s.subSet(fromElement, fromInclusive, toElement, toInclusive);
5760 }
5761
5762 public NavigableSet<E> headSet(E toElement, boolean inclusive)
5763 { return s.headSet(toElement, inclusive); }
5764 public NavigableSet<E> tailSet(E fromElement, boolean inclusive)
5765 { return s.tailSet(fromElement, inclusive); }
5766 public SortedSet<E> subSet(E fromElement, E toElement)
5767 { return s.subSet(fromElement, toElement); }
5768 public SortedSet<E> headSet(E toElement)
5769 { return s.headSet(toElement); }
5770 public SortedSet<E> tailSet(E fromElement)
5771 { return s.tailSet(fromElement); }
5772 public Comparator<? super E> comparator() { return s.comparator(); }
5773 public E first() { return s.first(); }
5774 public E last() { return s.last(); }
5775 }
5776
5777 /**
5778 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
5779 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
5780 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
5781 * view can be useful when you would like to use a method
5782 * requiring a <tt>Queue</tt> but you need Lifo ordering.
5783 *
5784 * <p>Each method invocation on the queue returned by this method
5785 * results in exactly one method invocation on the backing deque, with
5786 * one exception. The {@link Queue#addAll addAll} method is
5787 * implemented as a sequence of {@link Deque#addFirst addFirst}
5788 * invocations on the backing deque.
5789 *
5790 * @param deque the deque
5791 * @return the queue
5792 * @since 1.6
5793 */
5794 public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
|