/* * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package java.util; import java.io.Serializable; import java.io.ObjectOutputStream; import java.io.IOException; import java.lang.reflect.Array; /** * This class consists exclusively of static methods that operate on or return * collections. It contains polymorphic algorithms that operate on * collections, "wrappers", which return a new collection backed by a * specified collection, and a few other odds and ends. * *

The methods of this class all throw a NullPointerException * if the collections or class objects provided to them are null. * *

The documentation for the polymorphic algorithms contained in this class * generally includes a brief description of the implementation. Such * descriptions should be regarded as implementation notes, rather than * parts of the specification. Implementors should feel free to * substitute other algorithms, so long as the specification itself is adhered * to. (For example, the algorithm used by sort does not have to be * a mergesort, but it does have to be stable.) * *

The "destructive" algorithms contained in this class, that is, the * algorithms that modify the collection on which they operate, are specified * to throw UnsupportedOperationException if the collection does not * support the appropriate mutation primitive(s), such as the set * method. These algorithms may, but are not required to, throw this * exception if an invocation would have no effect on the collection. For * example, invoking the sort method on an unmodifiable list that is * already sorted may or may not throw UnsupportedOperationException. * *

This class is a member of the * * Java Collections Framework. * * @author Josh Bloch * @author Neal Gafter * @see Collection * @see Set * @see List * @see Map * @since 1.2 */ public class Collections { // Suppresses default constructor, ensuring non-instantiability. private Collections() { } // Algorithms /* * Tuning parameters for algorithms - Many of the List algorithms have * two implementations, one of which is appropriate for RandomAccess * lists, the other for "sequential." Often, the random access variant * yields better performance on small sequential access lists. The * tuning parameters below determine the cutoff point for what constitutes * a "small" sequential access list for each algorithm. The values below * were empirically determined to work well for LinkedList. Hopefully * they should be reasonable for other sequential access List * implementations. Those doing performance work on this code would * do well to validate the values of these parameters from time to time. * (The first word of each tuning parameter name is the algorithm to which * it applies.) */ private static final int BINARYSEARCH_THRESHOLD = 5000; private static final int REVERSE_THRESHOLD = 18; private static final int SHUFFLE_THRESHOLD = 5; private static final int FILL_THRESHOLD = 25; private static final int ROTATE_THRESHOLD = 100; private static final int COPY_THRESHOLD = 10; private static final int REPLACEALL_THRESHOLD = 11; private static final int INDEXOFSUBLIST_THRESHOLD = 35; /** * Sorts the specified list into ascending order, according to the * {@linkplain Comparable natural ordering} of its elements. * All elements in the list must implement the {@link Comparable} * interface. Furthermore, all elements in the list must be * mutually comparable (that is, {@code e1.compareTo(e2)} * must not throw a {@code ClassCastException} for any elements * {@code e1} and {@code e2} in the list). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * *

The specified list must be modifiable, but need not be resizable. * *

Implementation note: This implementation is a stable, adaptive, * iterative mergesort that requires far fewer than n lg(n) comparisons * when the input array is partially sorted, while offering the * performance of a traditional mergesort when the input array is * randomly ordered. If the input array is nearly sorted, the * implementation requires approximately n comparisons. Temporary * storage requirements vary from a small constant for nearly sorted * input arrays to n/2 object references for randomly ordered input * arrays. * *

The implementation takes equal advantage of ascending and * descending order in its input array, and can take advantage of * ascending and descending order in different parts of the same * input array. It is well-suited to merging two or more sorted arrays: * simply concatenate the arrays and sort the resulting array. * *

The implementation was adapted from Tim Peters's list sort for Python * ( * TimSort). It uses techiques from Peter McIlroy's "Optimistic * Sorting and Information Theoretic Complexity", in Proceedings of the * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, * January 1993. * *

This implementation dumps the specified list into an array, sorts * the array, and iterates over the list resetting each element * from the corresponding position in the array. This avoids the * n2 log(n) performance that would result from attempting * to sort a linked list in place. * * @param list the list to be sorted. * @throws ClassCastException if the list contains elements that are not * mutually comparable (for example, strings and integers). * @throws UnsupportedOperationException if the specified list's * list-iterator does not support the {@code set} operation. * @throws IllegalArgumentException (optional) if the implementation * detects that the natural ordering of the list elements is * found to violate the {@link Comparable} contract */ @SuppressWarnings("unchecked") public static > void sort(List list) { Object[] a = list.toArray(); Arrays.sort(a); ListIterator i = list.listIterator(); for (int j=0; jmutually * comparable using the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the list). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * *

The specified list must be modifiable, but need not be resizable. * *

Implementation note: This implementation is a stable, adaptive, * iterative mergesort that requires far fewer than n lg(n) comparisons * when the input array is partially sorted, while offering the * performance of a traditional mergesort when the input array is * randomly ordered. If the input array is nearly sorted, the * implementation requires approximately n comparisons. Temporary * storage requirements vary from a small constant for nearly sorted * input arrays to n/2 object references for randomly ordered input * arrays. * *

The implementation takes equal advantage of ascending and * descending order in its input array, and can take advantage of * ascending and descending order in different parts of the same * input array. It is well-suited to merging two or more sorted arrays: * simply concatenate the arrays and sort the resulting array. * *

The implementation was adapted from Tim Peters's list sort for Python * ( * TimSort). It uses techiques from Peter McIlroy's "Optimistic * Sorting and Information Theoretic Complexity", in Proceedings of the * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, * January 1993. * *

This implementation dumps the specified list into an array, sorts * the array, and iterates over the list resetting each element * from the corresponding position in the array. This avoids the * n2 log(n) performance that would result from attempting * to sort a linked list in place. * * @param list the list to be sorted. * @param c the comparator to determine the order of the list. A * {@code null} value indicates that the elements' natural * ordering should be used. * @throws ClassCastException if the list contains elements that are not * mutually comparable using the specified comparator. * @throws UnsupportedOperationException if the specified list's * list-iterator does not support the {@code set} operation. * @throws IllegalArgumentException (optional) if the comparator is * found to violate the {@link Comparator} contract */ @SuppressWarnings({ "unchecked", "rawtypes" }) public static void sort(List list, Comparator c) { Object[] a = list.toArray(); Arrays.sort(a, (Comparator)c); ListIterator i = list.listIterator(); for (int j=0; jThis method runs in log(n) time for a "random access" list (which * provides near-constant-time positional access). If the specified list * does not implement the {@link RandomAccess} interface and is large, * this method will do an iterator-based binary search that performs * O(n) link traversals and O(log n) element comparisons. * * @param list the list to be searched. * @param key the key to be searched for. * @return the index of the search key, if it is contained in the list; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the list: the index of the first * element greater than the key, or list.size() if all * elements in the list are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the list contains elements that are not * mutually comparable (for example, strings and * integers), or the search key is not mutually comparable * with the elements of the list. */ public static int binarySearch(List> list, T key) { if (list instanceof RandomAccess || list.size() int indexedBinarySearch(List> list, T key) { int low = 0; int high = list.size()-1; while (low <= high) { int mid = (low + high) >>> 1; Comparable midVal = list.get(mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } private static int iteratorBinarySearch(List> list, T key) { int low = 0; int high = list.size()-1; ListIterator> i = list.listIterator(); while (low <= high) { int mid = (low + high) >>> 1; Comparable midVal = get(i, mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } /** * Gets the ith element from the given list by repositioning the specified * list listIterator. */ private static T get(ListIterator i, int index) { T obj = null; int pos = i.nextIndex(); if (pos <= index) { do { obj = i.next(); } while (pos++ < index); } else { do { obj = i.previous(); } while (--pos > index); } return obj; } /** * Searches the specified list for the specified object using the binary * search algorithm. The list must be sorted into ascending order * according to the specified comparator (as by the * {@link #sort(List, Comparator) sort(List, Comparator)} * method), prior to making this call. If it is * not sorted, the results are undefined. If the list contains multiple * elements equal to the specified object, there is no guarantee which one * will be found. * *

This method runs in log(n) time for a "random access" list (which * provides near-constant-time positional access). If the specified list * does not implement the {@link RandomAccess} interface and is large, * this method will do an iterator-based binary search that performs * O(n) link traversals and O(log n) element comparisons. * * @param list the list to be searched. * @param key the key to be searched for. * @param c the comparator by which the list is ordered. * A null value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @return the index of the search key, if it is contained in the list; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the list: the index of the first * element greater than the key, or list.size() if all * elements in the list are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the list contains elements that are not * mutually comparable using the specified comparator, * or the search key is not mutually comparable with the * elements of the list using this comparator. */ @SuppressWarnings("unchecked") public static int binarySearch(List list, T key, Comparator c) { if (c==null) return binarySearch((List>) list, key); if (list instanceof RandomAccess || list.size() int indexedBinarySearch(List l, T key, Comparator c) { int low = 0; int high = l.size()-1; while (low <= high) { int mid = (low + high) >>> 1; T midVal = l.get(mid); int cmp = c.compare(midVal, key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } private static int iteratorBinarySearch(List l, T key, Comparator c) { int low = 0; int high = l.size()-1; ListIterator i = l.listIterator(); while (low <= high) { int mid = (low + high) >>> 1; T midVal = get(i, mid); int cmp = c.compare(midVal, key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } /** * Reverses the order of the elements in the specified list.

* * This method runs in linear time. * * @param list the list whose elements are to be reversed. * @throws UnsupportedOperationException if the specified list or * its list-iterator does not support the set operation. */ @SuppressWarnings({ "rawtypes", "unchecked" }) public static void reverse(List list) { int size = list.size(); if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { for (int i=0, mid=size>>1, j=size-1; i>1; i * * The hedge "approximately" is used in the foregoing description because * default source of randomness is only approximately an unbiased source * of independently chosen bits. If it were a perfect source of randomly * chosen bits, then the algorithm would choose permutations with perfect * uniformity.

* * This implementation traverses the list backwards, from the last element * up to the second, repeatedly swapping a randomly selected element into * the "current position". Elements are randomly selected from the * portion of the list that runs from the first element to the current * position, inclusive.

* * This method runs in linear time. If the specified list does not * implement the {@link RandomAccess} interface and is large, this * implementation dumps the specified list into an array before shuffling * it, and dumps the shuffled array back into the list. This avoids the * quadratic behavior that would result from shuffling a "sequential * access" list in place. * * @param list the list to be shuffled. * @throws UnsupportedOperationException if the specified list or * its list-iterator does not support the set operation. */ public static void shuffle(List list) { Random rnd = r; if (rnd == null) r = rnd = new Random(); shuffle(list, rnd); } private static Random r; /** * Randomly permute the specified list using the specified source of * randomness. All permutations occur with equal likelihood * assuming that the source of randomness is fair.

* * This implementation traverses the list backwards, from the last element * up to the second, repeatedly swapping a randomly selected element into * the "current position". Elements are randomly selected from the * portion of the list that runs from the first element to the current * position, inclusive.

* * This method runs in linear time. If the specified list does not * implement the {@link RandomAccess} interface and is large, this * implementation dumps the specified list into an array before shuffling * it, and dumps the shuffled array back into the list. This avoids the * quadratic behavior that would result from shuffling a "sequential * access" list in place. * * @param list the list to be shuffled. * @param rnd the source of randomness to use to shuffle the list. * @throws UnsupportedOperationException if the specified list or its * list-iterator does not support the set operation. */ @SuppressWarnings({ "rawtypes", "unchecked" }) public static void shuffle(List list, Random rnd) { int size = list.size(); if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { for (int i=size; i>1; i--) swap(list, i-1, rnd.nextInt(i)); } else { Object arr[] = list.toArray(); // Shuffle array for (int i=size; i>1; i--) swap(arr, i-1, rnd.nextInt(i)); // Dump array back into list // instead of using a raw type here, it's possible to capture // the wildcard but it will require a call to a supplementary // private method ListIterator it = list.listIterator(); for (int i=0; ii or j * is out of range (i < 0 || i >= list.size() * || j < 0 || j >= list.size()). * @since 1.4 */ @SuppressWarnings({ "rawtypes", "unchecked" }) public static void swap(List list, int i, int j) { // instead of using a raw type here, it's possible to capture // the wildcard but it will require a call to a supplementary // private method final List l = list; l.set(i, l.set(j, l.get(i))); } /** * Swaps the two specified elements in the specified array. */ private static void swap(Object[] arr, int i, int j) { Object tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /** * Replaces all of the elements of the specified list with the specified * element.

* * This method runs in linear time. * * @param list the list to be filled with the specified element. * @param obj The element with which to fill the specified list. * @throws UnsupportedOperationException if the specified list or its * list-iterator does not support the set operation. */ public static void fill(List list, T obj) { int size = list.size(); if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i itr = list.listIterator(); for (int i=0; i * * This method runs in linear time. * * @param dest The destination list. * @param src The source list. * @throws IndexOutOfBoundsException if the destination list is too small * to contain the entire source List. * @throws UnsupportedOperationException if the destination list's * list-iterator does not support the set operation. */ public static void copy(List dest, List src) { int srcSize = src.size(); if (srcSize > dest.size()) throw new IndexOutOfBoundsException("Source does not fit in dest"); if (srcSize < COPY_THRESHOLD || (src instanceof RandomAccess && dest instanceof RandomAccess)) { for (int i=0; i di=dest.listIterator(); ListIterator si=src.listIterator(); for (int i=0; inatural ordering of its elements. All elements in the * collection must implement the Comparable interface. * Furthermore, all elements in the collection must be mutually * comparable (that is, e1.compareTo(e2) must not throw a * ClassCastException for any elements e1 and * e2 in the collection).

* * This method iterates over the entire collection, hence it requires * time proportional to the size of the collection. * * @param coll the collection whose minimum element is to be determined. * @return the minimum element of the given collection, according * to the natural ordering of its elements. * @throws ClassCastException if the collection contains elements that are * not mutually comparable (for example, strings and * integers). * @throws NoSuchElementException if the collection is empty. * @see Comparable */ public static > T min(Collection coll) { Iterator i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (next.compareTo(candidate) < 0) candidate = next; } return candidate; } /** * Returns the minimum element of the given collection, according to the * order induced by the specified comparator. All elements in the * collection must be mutually comparable by the specified * comparator (that is, comp.compare(e1, e2) must not throw a * ClassCastException for any elements e1 and * e2 in the collection).

* * This method iterates over the entire collection, hence it requires * time proportional to the size of the collection. * * @param coll the collection whose minimum element is to be determined. * @param comp the comparator with which to determine the minimum element. * A null value indicates that the elements' natural * ordering should be used. * @return the minimum element of the given collection, according * to the specified comparator. * @throws ClassCastException if the collection contains elements that are * not mutually comparable using the specified comparator. * @throws NoSuchElementException if the collection is empty. * @see Comparable */ @SuppressWarnings({ "unchecked", "rawtypes" }) public static T min(Collection coll, Comparator comp) { if (comp==null) return (T)min((Collection) coll); Iterator i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (comp.compare(next, candidate) < 0) candidate = next; } return candidate; } /** * Returns the maximum element of the given collection, according to the * natural ordering of its elements. All elements in the * collection must implement the Comparable interface. * Furthermore, all elements in the collection must be mutually * comparable (that is, e1.compareTo(e2) must not throw a * ClassCastException for any elements e1 and * e2 in the collection).

* * This method iterates over the entire collection, hence it requires * time proportional to the size of the collection. * * @param coll the collection whose maximum element is to be determined. * @return the maximum element of the given collection, according * to the natural ordering of its elements. * @throws ClassCastException if the collection contains elements that are * not mutually comparable (for example, strings and * integers). * @throws NoSuchElementException if the collection is empty. * @see Comparable */ public static > T max(Collection coll) { Iterator i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (next.compareTo(candidate) > 0) candidate = next; } return candidate; } /** * Returns the maximum element of the given collection, according to the * order induced by the specified comparator. All elements in the * collection must be mutually comparable by the specified * comparator (that is, comp.compare(e1, e2) must not throw a * ClassCastException for any elements e1 and * e2 in the collection).

* * This method iterates over the entire collection, hence it requires * time proportional to the size of the collection. * * @param coll the collection whose maximum element is to be determined. * @param comp the comparator with which to determine the maximum element. * A null value indicates that the elements' natural * ordering should be used. * @return the maximum element of the given collection, according * to the specified comparator. * @throws ClassCastException if the collection contains elements that are * not mutually comparable using the specified comparator. * @throws NoSuchElementException if the collection is empty. * @see Comparable */ @SuppressWarnings({ "unchecked", "rawtypes" }) public static T max(Collection coll, Comparator comp) { if (comp==null) return (T)max((Collection) coll); Iterator i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (comp.compare(next, candidate) > 0) candidate = next; } return candidate; } /** * Rotates the elements in the specified list by the specified distance. * After calling this method, the element at index i will be * the element previously at index (i - distance) mod * list.size(), for all values of i between 0 * and list.size()-1, inclusive. (This method has no effect on * the size of the list.) * *

For example, suppose list comprises [t, a, n, k, s]. * After invoking Collections.rotate(list, 1) (or * Collections.rotate(list, -4)), list will comprise * [s, t, a, n, k]. * *

Note that this method can usefully be applied to sublists to * move one or more elements within a list while preserving the * order of the remaining elements. For example, the following idiom * moves the element at index j forward to position * k (which must be greater than or equal to j): *

     *     Collections.rotate(list.subList(j, k+1), -1);
     * 
* To make this concrete, suppose list comprises * [a, b, c, d, e]. To move the element at index 1 * (b) forward two positions, perform the following invocation: *
     *     Collections.rotate(l.subList(1, 4), -1);
     * 
* The resulting list is [a, c, d, b, e]. * *

To move more than one element forward, increase the absolute value * of the rotation distance. To move elements backward, use a positive * shift distance. * *

If the specified list is small or implements the {@link * RandomAccess} interface, this implementation exchanges the first * element into the location it should go, and then repeatedly exchanges * the displaced element into the location it should go until a displaced * element is swapped into the first element. If necessary, the process * is repeated on the second and successive elements, until the rotation * is complete. If the specified list is large and doesn't implement the * RandomAccess interface, this implementation breaks the * list into two sublist views around index -distance mod size. * Then the {@link #reverse(List)} method is invoked on each sublist view, * and finally it is invoked on the entire list. For a more complete * description of both algorithms, see Section 2.3 of Jon Bentley's * Programming Pearls (Addison-Wesley, 1986). * * @param list the list to be rotated. * @param distance the distance to rotate the list. There are no * constraints on this value; it may be zero, negative, or * greater than list.size(). * @throws UnsupportedOperationException if the specified list or * its list-iterator does not support the set operation. * @since 1.4 */ public static void rotate(List list, int distance) { if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) rotate1(list, distance); else rotate2(list, distance); } private static void rotate1(List list, int distance) { int size = list.size(); if (size == 0) return; distance = distance % size; if (distance < 0) distance += size; if (distance == 0) return; for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { T displaced = list.get(cycleStart); int i = cycleStart; do { i += distance; if (i >= size) i -= size; displaced = list.set(i, displaced); nMoved ++; } while (i != cycleStart); } } private static void rotate2(List list, int distance) { int size = list.size(); if (size == 0) return; int mid = -distance % size; if (mid < 0) mid += size; if (mid == 0) return; reverse(list.subList(0, mid)); reverse(list.subList(mid, size)); reverse(list); } /** * Replaces all occurrences of one specified value in a list with another. * More formally, replaces with newVal each element e * in list such that * (oldVal==null ? e==null : oldVal.equals(e)). * (This method has no effect on the size of the list.) * * @param list the list in which replacement is to occur. * @param oldVal the old value to be replaced. * @param newVal the new value with which oldVal is to be * replaced. * @return true if list contained one or more elements * e such that * (oldVal==null ? e==null : oldVal.equals(e)). * @throws UnsupportedOperationException if the specified list or * its list-iterator does not support the set operation. * @since 1.4 */ public static boolean replaceAll(List list, T oldVal, T newVal) { boolean result = false; int size = list.size(); if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { if (oldVal==null) { for (int i=0; i itr=list.listIterator(); if (oldVal==null) { for (int i=0; ii * such that source.subList(i, i+target.size()).equals(target), * or -1 if there is no such index. (Returns -1 if * target.size() > source.size().) * *

This implementation uses the "brute force" technique of scanning * over the source list, looking for a match with the target at each * location in turn. * * @param source the list in which to search for the first occurrence * of target. * @param target the list to search for as a subList of source. * @return the starting position of the first occurrence of the specified * target list within the specified source list, or -1 if there * is no such occurrence. * @since 1.4 */ public static int indexOfSubList(List source, List target) { int sourceSize = source.size(); int targetSize = target.size(); int maxCandidate = sourceSize - targetSize; if (sourceSize < INDEXOFSUBLIST_THRESHOLD || (source instanceof RandomAccess&&target instanceof RandomAccess)) { nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) { for (int i=0, j=candidate; i si = source.listIterator(); nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) { ListIterator ti = target.listIterator(); for (int i=0; ii * such that source.subList(i, i+target.size()).equals(target), * or -1 if there is no such index. (Returns -1 if * target.size() > source.size().) * *

This implementation uses the "brute force" technique of iterating * over the source list, looking for a match with the target at each * location in turn. * * @param source the list in which to search for the last occurrence * of target. * @param target the list to search for as a subList of source. * @return the starting position of the last occurrence of the specified * target list within the specified source list, or -1 if there * is no such occurrence. * @since 1.4 */ public static int lastIndexOfSubList(List source, List target) { int sourceSize = source.size(); int targetSize = target.size(); int maxCandidate = sourceSize - targetSize; if (sourceSize < INDEXOFSUBLIST_THRESHOLD || source instanceof RandomAccess) { // Index access version nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) { for (int i=0, j=candidate; i si = source.listIterator(maxCandidate); nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) { ListIterator ti = target.listIterator(); for (int i=0; iUnsupportedOperationException.

* * The returned collection does not pass the hashCode and equals * operations through to the backing collection, but relies on * Object's equals and hashCode methods. This * is necessary to preserve the contracts of these operations in the case * that the backing collection is a set or a list.

* * The returned collection will be serializable if the specified collection * is serializable. * * @param c the collection for which an unmodifiable view is to be * returned. * @return an unmodifiable view of the specified collection. */ public static Collection unmodifiableCollection(Collection c) { return new UnmodifiableCollection<>(c); } /** * @serial include */ static class UnmodifiableCollection implements Collection, Serializable { private static final long serialVersionUID = 1820017752578914078L; final Collection c; UnmodifiableCollection(Collection c) { if (c==null) throw new NullPointerException(); this.c = c; } public int size() {return c.size();} public boolean isEmpty() {return c.isEmpty();} public boolean contains(Object o) {return c.contains(o);} public Object[] toArray() {return c.toArray();} public T[] toArray(T[] a) {return c.toArray(a);} public String toString() {return c.toString();} public Iterator iterator() { return new Iterator() { private final Iterator i = c.iterator(); public boolean hasNext() {return i.hasNext();} public E next() {return i.next();} public void remove() { throw new UnsupportedOperationException(); } }; } public boolean add(E e) { throw new UnsupportedOperationException(); } public boolean remove(Object o) { throw new UnsupportedOperationException(); } public boolean containsAll(Collection coll) { return c.containsAll(coll); } public boolean addAll(Collection coll) { throw new UnsupportedOperationException(); } public boolean removeAll(Collection coll) { throw new UnsupportedOperationException(); } public boolean retainAll(Collection coll) { throw new UnsupportedOperationException(); } public void clear() { throw new UnsupportedOperationException(); } } /** * Returns an unmodifiable view of the specified set. This method allows * modules to provide users with "read-only" access to internal sets. * Query operations on the returned set "read through" to the specified * set, and attempts to modify the returned set, whether direct or via its * iterator, result in an UnsupportedOperationException.

* * The returned set will be serializable if the specified set * is serializable. * * @param s the set for which an unmodifiable view is to be returned. * @return an unmodifiable view of the specified set. */ public static Set unmodifiableSet(Set s) { return new UnmodifiableSet<>(s); } /** * @serial include */ static class UnmodifiableSet extends UnmodifiableCollection implements Set, Serializable { private static final long serialVersionUID = -9215047833775013803L; UnmodifiableSet(Set s) {super(s);} public boolean equals(Object o) {return o == this || c.equals(o);} public int hashCode() {return c.hashCode();} } /** * Returns an unmodifiable view of the specified sorted set. This method * allows modules to provide users with "read-only" access to internal * sorted sets. Query operations on the returned sorted set "read * through" to the specified sorted set. Attempts to modify the returned * sorted set, whether direct, via its iterator, or via its * subSet, headSet, or tailSet views, result in * an UnsupportedOperationException.

* * The returned sorted set will be serializable if the specified sorted set * is serializable. * * @param s the sorted set for which an unmodifiable view is to be * returned. * @return an unmodifiable view of the specified sorted set. */ public static SortedSet unmodifiableSortedSet(SortedSet s) { return new UnmodifiableSortedSet<>(s); } /** * @serial include */ static class UnmodifiableSortedSet extends UnmodifiableSet implements SortedSet, Serializable { private static final long serialVersionUID = -4929149591599911165L; private final SortedSet ss; UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;} public Comparator comparator() {return ss.comparator();} public SortedSet subSet(E fromElement, E toElement) { return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement)); } public SortedSet headSet(E toElement) { return new UnmodifiableSortedSet<>(ss.headSet(toElement)); } public SortedSet tailSet(E fromElement) { return new UnmodifiableSortedSet<>(ss.tailSet(fromElement)); } public E first() {return ss.first();} public E last() {return ss.last();} } /** * Returns an unmodifiable view of the specified list. This method allows * modules to provide users with "read-only" access to internal * lists. Query operations on the returned list "read through" to the * specified list, and attempts to modify the returned list, whether * direct or via its iterator, result in an * UnsupportedOperationException.

* * The returned list will be serializable if the specified list * is serializable. Similarly, the returned list will implement * {@link RandomAccess} if the specified list does. * * @param list the list for which an unmodifiable view is to be returned. * @return an unmodifiable view of the specified list. */ public static List unmodifiableList(List list) { return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList<>(list) : new UnmodifiableList<>(list)); } /** * @serial include */ static class UnmodifiableList extends UnmodifiableCollection implements List { private static final long serialVersionUID = -283967356065247728L; final List list; UnmodifiableList(List list) { super(list); this.list = list; } public boolean equals(Object o) {return o == this || list.equals(o);} public int hashCode() {return list.hashCode();} public E get(int index) {return list.get(index);} public E set(int index, E element) { throw new UnsupportedOperationException(); } public void add(int index, E element) { throw new UnsupportedOperationException(); } public E remove(int index) { throw new UnsupportedOperationException(); } public int indexOf(Object o) {return list.indexOf(o);} public int lastIndexOf(Object o) {return list.lastIndexOf(o);} public boolean addAll(int index, Collection c) { throw new UnsupportedOperationException(); } public ListIterator listIterator() {return listIterator(0);} public ListIterator listIterator(final int index) { return new ListIterator() { private final ListIterator i = list.listIterator(index); public boolean hasNext() {return i.hasNext();} public E next() {return i.next();} public boolean hasPrevious() {return i.hasPrevious();} public E previous() {return i.previous();} public int nextIndex() {return i.nextIndex();} public int previousIndex() {return i.previousIndex();} public void remove() { throw new UnsupportedOperationException(); } public void set(E e) { throw new UnsupportedOperationException(); } public void add(E e) { throw new UnsupportedOperationException(); } }; } public List subList(int fromIndex, int toIndex) { return new UnmodifiableList<>(list.subList(fromIndex, toIndex)); } /** * UnmodifiableRandomAccessList instances are serialized as * UnmodifiableList instances to allow them to be deserialized * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList). * This method inverts the transformation. As a beneficial * side-effect, it also grafts the RandomAccess marker onto * UnmodifiableList instances that were serialized in pre-1.4 JREs. * * Note: Unfortunately, UnmodifiableRandomAccessList instances * serialized in 1.4.1 and deserialized in 1.4 will become * UnmodifiableList instances, as this method was missing in 1.4. */ private Object readResolve() { return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList<>(list) : this); } } /** * @serial include */ static class UnmodifiableRandomAccessList extends UnmodifiableList implements RandomAccess { UnmodifiableRandomAccessList(List list) { super(list); } public List subList(int fromIndex, int toIndex) { return new UnmodifiableRandomAccessList<>( list.subList(fromIndex, toIndex)); } private static final long serialVersionUID = -2542308836966382001L; /** * Allows instances to be deserialized in pre-1.4 JREs (which do * not have UnmodifiableRandomAccessList). UnmodifiableList has * a readResolve method that inverts this transformation upon * deserialization. */ private Object writeReplace() { return new UnmodifiableList<>(list); } } /** * Returns an unmodifiable view of the specified map. This method * allows modules to provide users with "read-only" access to internal * maps. Query operations on the returned map "read through" * to the specified map, and attempts to modify the returned * map, whether direct or via its collection views, result in an * UnsupportedOperationException.

* * The returned map will be serializable if the specified map * is serializable. * * @param m the map for which an unmodifiable view is to be returned. * @return an unmodifiable view of the specified map. */ public static Map unmodifiableMap(Map m) { return new UnmodifiableMap<>(m); } /** * @serial include */ private static class UnmodifiableMap implements Map, Serializable { private static final long serialVersionUID = -1034234728574286014L; private final Map m; UnmodifiableMap(Map m) { if (m==null) throw new NullPointerException(); this.m = m; } public int size() {return m.size();} public boolean isEmpty() {return m.isEmpty();} public boolean containsKey(Object key) {return m.containsKey(key);} public boolean containsValue(Object val) {return m.containsValue(val);} public V get(Object key) {return m.get(key);} public V put(K key, V value) { throw new UnsupportedOperationException(); } public V remove(Object key) { throw new UnsupportedOperationException(); } public void putAll(Map m) { throw new UnsupportedOperationException(); } public void clear() { throw new UnsupportedOperationException(); } private transient Set keySet = null; private transient Set> entrySet = null; private transient Collection values = null; public Set keySet() { if (keySet==null) keySet = unmodifiableSet(m.keySet()); return keySet; } public Set> entrySet() { if (entrySet==null) entrySet = new UnmodifiableEntrySet<>(m.entrySet()); return entrySet; } public Collection values() { if (values==null) values = unmodifiableCollection(m.values()); return values; } public boolean equals(Object o) {return o == this || m.equals(o);} public int hashCode() {return m.hashCode();} public String toString() {return m.toString();} /** * We need this class in addition to UnmodifiableSet as * Map.Entries themselves permit modification of the backing Map * via their setValue operation. This class is subtle: there are * many possible attacks that must be thwarted. * * @serial include */ static class UnmodifiableEntrySet extends UnmodifiableSet> { private static final long serialVersionUID = 7854390611657943733L; @SuppressWarnings({ "unchecked", "rawtypes" }) UnmodifiableEntrySet(Set> s) { // Need to cast to raw in order to work around a limitation in the type system super((Set)s); } public Iterator> iterator() { return new Iterator>() { private final Iterator> i = c.iterator(); public boolean hasNext() { return i.hasNext(); } public Map.Entry next() { return new UnmodifiableEntry<>(i.next()); } public void remove() { throw new UnsupportedOperationException(); } }; } @SuppressWarnings("unchecked") public Object[] toArray() { Object[] a = c.toArray(); for (int i=0; i((Map.Entry)a[i]); return a; } @SuppressWarnings("unchecked") public T[] toArray(T[] a) { // We don't pass a to c.toArray, to avoid window of // vulnerability wherein an unscrupulous multithreaded client // could get his hands on raw (unwrapped) Entries from c. Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); for (int i=0; i((Map.Entry)arr[i]); if (arr.length > a.length) return (T[])arr; System.arraycopy(arr, 0, a, 0, arr.length); if (a.length > arr.length) a[arr.length] = null; return a; } /** * This method is overridden to protect the backing set against * an object with a nefarious equals function that senses * that the equality-candidate is Map.Entry and calls its * setValue method. */ public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; return c.contains( new UnmodifiableEntry<>((Map.Entry) o)); } /** * The next two methods are overridden to protect against * an unscrupulous List whose contains(Object o) method senses * when o is a Map.Entry, and calls o.setValue. */ public boolean containsAll(Collection coll) { for (Object e : coll) { if (!contains(e)) // Invokes safe contains() above return false; } return true; } public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Set s = (Set) o; if (s.size() != c.size()) return false; return containsAll(s); // Invokes safe containsAll() above } /** * This "wrapper class" serves two purposes: it prevents * the client from modifying the backing Map, by short-circuiting * the setValue method, and it protects the backing Map against * an ill-behaved Map.Entry that attempts to modify another * Map Entry when asked to perform an equality check. */ private static class UnmodifiableEntry implements Map.Entry { private Map.Entry e; UnmodifiableEntry(Map.Entry e) {this.e = e;} public K getKey() {return e.getKey();} public V getValue() {return e.getValue();} public V setValue(V value) { throw new UnsupportedOperationException(); } public int hashCode() {return e.hashCode();} public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Map.Entry)) return false; Map.Entry t = (Map.Entry)o; return eq(e.getKey(), t.getKey()) && eq(e.getValue(), t.getValue()); } public String toString() {return e.toString();} } } } /** * Returns an unmodifiable view of the specified sorted map. This method * allows modules to provide users with "read-only" access to internal * sorted maps. Query operations on the returned sorted map "read through" * to the specified sorted map. Attempts to modify the returned * sorted map, whether direct, via its collection views, or via its * subMap, headMap, or tailMap views, result in * an UnsupportedOperationException.

* * The returned sorted map will be serializable if the specified sorted map * is serializable. * * @param m the sorted map for which an unmodifiable view is to be * returned. * @return an unmodifiable view of the specified sorted map. */ public static SortedMap unmodifiableSortedMap(SortedMap m) { return new UnmodifiableSortedMap<>(m); } /** * @serial include */ static class UnmodifiableSortedMap extends UnmodifiableMap implements SortedMap, Serializable { private static final long serialVersionUID = -8806743815996713206L; private final SortedMap sm; UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;} public Comparator comparator() {return sm.comparator();} public SortedMap subMap(K fromKey, K toKey) { return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey)); } public SortedMap headMap(K toKey) { return new UnmodifiableSortedMap<>(sm.headMap(toKey)); } public SortedMap tailMap(K fromKey) { return new UnmodifiableSortedMap<>(sm.tailMap(fromKey)); } public K firstKey() {return sm.firstKey();} public K lastKey() {return sm.lastKey();} } // Synch Wrappers /** * Returns a synchronized (thread-safe) collection backed by the specified * collection. In order to guarantee serial access, it is critical that * all access to the backing collection is accomplished * through the returned collection.

* * It is imperative that the user manually synchronize on the returned * collection when iterating over it: *

     *  Collection c = Collections.synchronizedCollection(myCollection);
     *     ...
     *  synchronized (c) {
     *      Iterator i = c.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *         foo(i.next());
     *  }
     * 
* Failure to follow this advice may result in non-deterministic behavior. * *

The returned collection does not pass the hashCode * and equals operations through to the backing collection, but * relies on Object's equals and hashCode methods. This is * necessary to preserve the contracts of these operations in the case * that the backing collection is a set or a list.

* * The returned collection will be serializable if the specified collection * is serializable. * * @param c the collection to be "wrapped" in a synchronized collection. * @return a synchronized view of the specified collection. */ public static Collection synchronizedCollection(Collection c) { return new SynchronizedCollection<>(c); } static Collection synchronizedCollection(Collection c, Object mutex) { return new SynchronizedCollection<>(c, mutex); } /** * @serial include */ static class SynchronizedCollection implements Collection, Serializable { private static final long serialVersionUID = 3053995032091335093L; final Collection c; // Backing Collection final Object mutex; // Object on which to synchronize SynchronizedCollection(Collection c) { if (c==null) throw new NullPointerException(); this.c = c; mutex = this; } SynchronizedCollection(Collection c, Object mutex) { this.c = c; this.mutex = mutex; } public int size() { synchronized (mutex) {return c.size();} } public boolean isEmpty() { synchronized (mutex) {return c.isEmpty();} } public boolean contains(Object o) { synchronized (mutex) {return c.contains(o);} } public Object[] toArray() { synchronized (mutex) {return c.toArray();} } public T[] toArray(T[] a) { synchronized (mutex) {return c.toArray(a);} } public Iterator iterator() { return c.iterator(); // Must be manually synched by user! } public boolean add(E e) { synchronized (mutex) {return c.add(e);} } public boolean remove(Object o) { synchronized (mutex) {return c.remove(o);} } public boolean containsAll(Collection coll) { synchronized (mutex) {return c.containsAll(coll);} } public boolean addAll(Collection coll) { synchronized (mutex) {return c.addAll(coll);} } public boolean removeAll(Collection coll) { synchronized (mutex) {return c.removeAll(coll);} } public boolean retainAll(Collection coll) { synchronized (mutex) {return c.retainAll(coll);} } public void clear() { synchronized (mutex) {c.clear();} } public String toString() { synchronized (mutex) {return c.toString();} } private void writeObject(ObjectOutputStream s) throws IOException { synchronized (mutex) {s.defaultWriteObject();} } } /** * Returns a synchronized (thread-safe) set backed by the specified * set. In order to guarantee serial access, it is critical that * all access to the backing set is accomplished * through the returned set.

* * It is imperative that the user manually synchronize on the returned * set when iterating over it: *

     *  Set s = Collections.synchronizedSet(new HashSet());
     *      ...
     *  synchronized (s) {
     *      Iterator i = s.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* Failure to follow this advice may result in non-deterministic behavior. * *

The returned set will be serializable if the specified set is * serializable. * * @param s the set to be "wrapped" in a synchronized set. * @return a synchronized view of the specified set. */ public static Set synchronizedSet(Set s) { return new SynchronizedSet<>(s); } static Set synchronizedSet(Set s, Object mutex) { return new SynchronizedSet<>(s, mutex); } /** * @serial include */ static class SynchronizedSet extends SynchronizedCollection implements Set { private static final long serialVersionUID = 487447009682186044L; SynchronizedSet(Set s) { super(s); } SynchronizedSet(Set s, Object mutex) { super(s, mutex); } public boolean equals(Object o) { if (this == o) return true; synchronized (mutex) {return c.equals(o);} } public int hashCode() { synchronized (mutex) {return c.hashCode();} } } /** * Returns a synchronized (thread-safe) sorted set backed by the specified * sorted set. In order to guarantee serial access, it is critical that * all access to the backing sorted set is accomplished * through the returned sorted set (or its views).

* * It is imperative that the user manually synchronize on the returned * sorted set when iterating over it or any of its subSet, * headSet, or tailSet views. *

     *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
     *      ...
     *  synchronized (s) {
     *      Iterator i = s.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* or: *
     *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
     *  SortedSet s2 = s.headSet(foo);
     *      ...
     *  synchronized (s) {  // Note: s, not s2!!!
     *      Iterator i = s2.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* Failure to follow this advice may result in non-deterministic behavior. * *

The returned sorted set will be serializable if the specified * sorted set is serializable. * * @param s the sorted set to be "wrapped" in a synchronized sorted set. * @return a synchronized view of the specified sorted set. */ public static SortedSet synchronizedSortedSet(SortedSet s) { return new SynchronizedSortedSet<>(s); } /** * @serial include */ static class SynchronizedSortedSet extends SynchronizedSet implements SortedSet { private static final long serialVersionUID = 8695801310862127406L; private final SortedSet ss; SynchronizedSortedSet(SortedSet s) { super(s); ss = s; } SynchronizedSortedSet(SortedSet s, Object mutex) { super(s, mutex); ss = s; } public Comparator comparator() { synchronized (mutex) {return ss.comparator();} } public SortedSet subSet(E fromElement, E toElement) { synchronized (mutex) { return new SynchronizedSortedSet<>( ss.subSet(fromElement, toElement), mutex); } } public SortedSet headSet(E toElement) { synchronized (mutex) { return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex); } } public SortedSet tailSet(E fromElement) { synchronized (mutex) { return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex); } } public E first() { synchronized (mutex) {return ss.first();} } public E last() { synchronized (mutex) {return ss.last();} } } /** * Returns a synchronized (thread-safe) list backed by the specified * list. In order to guarantee serial access, it is critical that * all access to the backing list is accomplished * through the returned list.

* * It is imperative that the user manually synchronize on the returned * list when iterating over it: *

     *  List list = Collections.synchronizedList(new ArrayList());
     *      ...
     *  synchronized (list) {
     *      Iterator i = list.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* Failure to follow this advice may result in non-deterministic behavior. * *

The returned list will be serializable if the specified list is * serializable. * * @param list the list to be "wrapped" in a synchronized list. * @return a synchronized view of the specified list. */ public static List synchronizedList(List list) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list)); } static List synchronizedList(List list, Object mutex) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list, mutex) : new SynchronizedList<>(list, mutex)); } /** * @serial include */ static class SynchronizedList extends SynchronizedCollection implements List { private static final long serialVersionUID = -7754090372962971524L; final List list; SynchronizedList(List list) { super(list); this.list = list; } SynchronizedList(List list, Object mutex) { super(list, mutex); this.list = list; } public boolean equals(Object o) { if (this == o) return true; synchronized (mutex) {return list.equals(o);} } public int hashCode() { synchronized (mutex) {return list.hashCode();} } public E get(int index) { synchronized (mutex) {return list.get(index);} } public E set(int index, E element) { synchronized (mutex) {return list.set(index, element);} } public void add(int index, E element) { synchronized (mutex) {list.add(index, element);} } public E remove(int index) { synchronized (mutex) {return list.remove(index);} } public int indexOf(Object o) { synchronized (mutex) {return list.indexOf(o);} } public int lastIndexOf(Object o) { synchronized (mutex) {return list.lastIndexOf(o);} } public boolean addAll(int index, Collection c) { synchronized (mutex) {return list.addAll(index, c);} } public ListIterator listIterator() { return list.listIterator(); // Must be manually synched by user } public ListIterator listIterator(int index) { return list.listIterator(index); // Must be manually synched by user } public List subList(int fromIndex, int toIndex) { synchronized (mutex) { return new SynchronizedList<>(list.subList(fromIndex, toIndex), mutex); } } /** * SynchronizedRandomAccessList instances are serialized as * SynchronizedList instances to allow them to be deserialized * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList). * This method inverts the transformation. As a beneficial * side-effect, it also grafts the RandomAccess marker onto * SynchronizedList instances that were serialized in pre-1.4 JREs. * * Note: Unfortunately, SynchronizedRandomAccessList instances * serialized in 1.4.1 and deserialized in 1.4 will become * SynchronizedList instances, as this method was missing in 1.4. */ private Object readResolve() { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : this); } } /** * @serial include */ static class SynchronizedRandomAccessList extends SynchronizedList implements RandomAccess { SynchronizedRandomAccessList(List list) { super(list); } SynchronizedRandomAccessList(List list, Object mutex) { super(list, mutex); } public List subList(int fromIndex, int toIndex) { synchronized (mutex) { return new SynchronizedRandomAccessList<>( list.subList(fromIndex, toIndex), mutex); } } private static final long serialVersionUID = 1530674583602358482L; /** * Allows instances to be deserialized in pre-1.4 JREs (which do * not have SynchronizedRandomAccessList). SynchronizedList has * a readResolve method that inverts this transformation upon * deserialization. */ private Object writeReplace() { return new SynchronizedList<>(list); } } /** * Returns a synchronized (thread-safe) map backed by the specified * map. In order to guarantee serial access, it is critical that * all access to the backing map is accomplished * through the returned map.

* * It is imperative that the user manually synchronize on the returned * map when iterating over any of its collection views: *

     *  Map m = Collections.synchronizedMap(new HashMap());
     *      ...
     *  Set s = m.keySet();  // Needn't be in synchronized block
     *      ...
     *  synchronized (m) {  // Synchronizing on m, not s!
     *      Iterator i = s.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* Failure to follow this advice may result in non-deterministic behavior. * *

The returned map will be serializable if the specified map is * serializable. * * @param m the map to be "wrapped" in a synchronized map. * @return a synchronized view of the specified map. */ public static Map synchronizedMap(Map m) { return new SynchronizedMap<>(m); } /** * @serial include */ private static class SynchronizedMap implements Map, Serializable { private static final long serialVersionUID = 1978198479659022715L; private final Map m; // Backing Map final Object mutex; // Object on which to synchronize SynchronizedMap(Map m) { if (m==null) throw new NullPointerException(); this.m = m; mutex = this; } SynchronizedMap(Map m, Object mutex) { this.m = m; this.mutex = mutex; } public int size() { synchronized (mutex) {return m.size();} } public boolean isEmpty() { synchronized (mutex) {return m.isEmpty();} } public boolean containsKey(Object key) { synchronized (mutex) {return m.containsKey(key);} } public boolean containsValue(Object value) { synchronized (mutex) {return m.containsValue(value);} } public V get(Object key) { synchronized (mutex) {return m.get(key);} } public V put(K key, V value) { synchronized (mutex) {return m.put(key, value);} } public V remove(Object key) { synchronized (mutex) {return m.remove(key);} } public void putAll(Map map) { synchronized (mutex) {m.putAll(map);} } public void clear() { synchronized (mutex) {m.clear();} } private transient Set keySet = null; private transient Set> entrySet = null; private transient Collection values = null; public Set keySet() { synchronized (mutex) { if (keySet==null) keySet = new SynchronizedSet<>(m.keySet(), mutex); return keySet; } } public Set> entrySet() { synchronized (mutex) { if (entrySet==null) entrySet = new SynchronizedSet<>(m.entrySet(), mutex); return entrySet; } } public Collection values() { synchronized (mutex) { if (values==null) values = new SynchronizedCollection<>(m.values(), mutex); return values; } } public boolean equals(Object o) { if (this == o) return true; synchronized (mutex) {return m.equals(o);} } public int hashCode() { synchronized (mutex) {return m.hashCode();} } public String toString() { synchronized (mutex) {return m.toString();} } private void writeObject(ObjectOutputStream s) throws IOException { synchronized (mutex) {s.defaultWriteObject();} } } /** * Returns a synchronized (thread-safe) sorted map backed by the specified * sorted map. In order to guarantee serial access, it is critical that * all access to the backing sorted map is accomplished * through the returned sorted map (or its views).

* * It is imperative that the user manually synchronize on the returned * sorted map when iterating over any of its collection views, or the * collections views of any of its subMap, headMap or * tailMap views. *

     *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
     *      ...
     *  Set s = m.keySet();  // Needn't be in synchronized block
     *      ...
     *  synchronized (m) {  // Synchronizing on m, not s!
     *      Iterator i = s.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* or: *
     *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
     *  SortedMap m2 = m.subMap(foo, bar);
     *      ...
     *  Set s2 = m2.keySet();  // Needn't be in synchronized block
     *      ...
     *  synchronized (m) {  // Synchronizing on m, not m2 or s2!
     *      Iterator i = s.iterator(); // Must be in synchronized block
     *      while (i.hasNext())
     *          foo(i.next());
     *  }
     * 
* Failure to follow this advice may result in non-deterministic behavior. * *

The returned sorted map will be serializable if the specified * sorted map is serializable. * * @param m the sorted map to be "wrapped" in a synchronized sorted map. * @return a synchronized view of the specified sorted map. */ public static SortedMap synchronizedSortedMap(SortedMap m) { return new SynchronizedSortedMap<>(m); } /** * @serial include */ static class SynchronizedSortedMap extends SynchronizedMap implements SortedMap { private static final long serialVersionUID = -8798146769416483793L; private final SortedMap sm; SynchronizedSortedMap(SortedMap m) { super(m); sm = m; } SynchronizedSortedMap(SortedMap m, Object mutex) { super(m, mutex); sm = m; } public Comparator comparator() { synchronized (mutex) {return sm.comparator();} } public SortedMap subMap(K fromKey, K toKey) { synchronized (mutex) { return new SynchronizedSortedMap<>( sm.subMap(fromKey, toKey), mutex); } } public SortedMap headMap(K toKey) { synchronized (mutex) { return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex); } } public SortedMap tailMap(K fromKey) { synchronized (mutex) { return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex); } } public K firstKey() { synchronized (mutex) {return sm.firstKey();} } public K lastKey() { synchronized (mutex) {return sm.lastKey();} } } // Dynamically typesafe collection wrappers /** * Returns a dynamically typesafe view of the specified collection. * Any attempt to insert an element of the wrong type will result in an * immediate {@link ClassCastException}. Assuming a collection * contains no incorrectly typed elements prior to the time a * dynamically typesafe view is generated, and that all subsequent * access to the collection takes place through the view, it is * guaranteed that the collection cannot contain an incorrectly * typed element. * *

The generics mechanism in the language provides compile-time * (static) type checking, but it is possible to defeat this mechanism * with unchecked casts. Usually this is not a problem, as the compiler * issues warnings on all such unchecked operations. There are, however, * times when static type checking alone is not sufficient. For example, * suppose a collection is passed to a third-party library and it is * imperative that the library code not corrupt the collection by * inserting an element of the wrong type. * *

Another use of dynamically typesafe views is debugging. Suppose a * program fails with a {@code ClassCastException}, indicating that an * incorrectly typed element was put into a parameterized collection. * Unfortunately, the exception can occur at any time after the erroneous * element is inserted, so it typically provides little or no information * as to the real source of the problem. If the problem is reproducible, * one can quickly determine its source by temporarily modifying the * program to wrap the collection with a dynamically typesafe view. * For example, this declaration: *

 {@code
     *     Collection c = new HashSet();
     * }
* may be replaced temporarily by this one: *
 {@code
     *     Collection c = Collections.checkedCollection(
     *         new HashSet(), String.class);
     * }
* Running the program again will cause it to fail at the point where * an incorrectly typed element is inserted into the collection, clearly * identifying the source of the problem. Once the problem is fixed, the * modified declaration may be reverted back to the original. * *

The returned collection does not pass the hashCode and equals * operations through to the backing collection, but relies on * {@code Object}'s {@code equals} and {@code hashCode} methods. This * is necessary to preserve the contracts of these operations in the case * that the backing collection is a set or a list. * *

The returned collection will be serializable if the specified * collection is serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned collection permits insertion of null elements * whenever the backing collection does. * * @param c the collection for which a dynamically typesafe view is to be * returned * @param type the type of element that {@code c} is permitted to hold * @return a dynamically typesafe view of the specified collection * @since 1.5 */ public static Collection checkedCollection(Collection c, Class type) { return new CheckedCollection<>(c, type); } @SuppressWarnings("unchecked") static T[] zeroLengthArray(Class type) { return (T[]) Array.newInstance(type, 0); } /** * @serial include */ static class CheckedCollection implements Collection, Serializable { private static final long serialVersionUID = 1578914078182001775L; final Collection c; final Class type; void typeCheck(Object o) { if (o != null && !type.isInstance(o)) throw new ClassCastException(badElementMsg(o)); } private String badElementMsg(Object o) { return "Attempt to insert " + o.getClass() + " element into collection with element type " + type; } CheckedCollection(Collection c, Class type) { if (c==null || type == null) throw new NullPointerException(); this.c = c; this.type = type; } public int size() { return c.size(); } public boolean isEmpty() { return c.isEmpty(); } public boolean contains(Object o) { return c.contains(o); } public Object[] toArray() { return c.toArray(); } public T[] toArray(T[] a) { return c.toArray(a); } public String toString() { return c.toString(); } public boolean remove(Object o) { return c.remove(o); } public void clear() { c.clear(); } public boolean containsAll(Collection coll) { return c.containsAll(coll); } public boolean removeAll(Collection coll) { return c.removeAll(coll); } public boolean retainAll(Collection coll) { return c.retainAll(coll); } public Iterator iterator() { final Iterator it = c.iterator(); return new Iterator() { public boolean hasNext() { return it.hasNext(); } public E next() { return it.next(); } public void remove() { it.remove(); }}; } public boolean add(E e) { typeCheck(e); return c.add(e); } private E[] zeroLengthElementArray = null; // Lazily initialized private E[] zeroLengthElementArray() { return zeroLengthElementArray != null ? zeroLengthElementArray : (zeroLengthElementArray = zeroLengthArray(type)); } @SuppressWarnings("unchecked") Collection checkedCopyOf(Collection coll) { Object[] a = null; try { E[] z = zeroLengthElementArray(); a = coll.toArray(z); // Defend against coll violating the toArray contract if (a.getClass() != z.getClass()) a = Arrays.copyOf(a, a.length, z.getClass()); } catch (ArrayStoreException ignore) { // To get better and consistent diagnostics, // we call typeCheck explicitly on each element. // We call clone() to defend against coll retaining a // reference to the returned array and storing a bad // element into it after it has been type checked. a = coll.toArray().clone(); for (Object o : a) typeCheck(o); } // A slight abuse of the type system, but safe here. return (Collection) Arrays.asList(a); } public boolean addAll(Collection coll) { // Doing things this way insulates us from concurrent changes // in the contents of coll and provides all-or-nothing // semantics (which we wouldn't get if we type-checked each // element as we added it) return c.addAll(checkedCopyOf(coll)); } } /** * Returns a dynamically typesafe view of the specified queue. * Any attempt to insert an element of the wrong type will result in * an immediate {@link ClassCastException}. Assuming a queue contains * no incorrectly typed elements prior to the time a dynamically typesafe * view is generated, and that all subsequent access to the queue * takes place through the view, it is guaranteed that the * queue cannot contain an incorrectly typed element. * *

A discussion of the use of dynamically typesafe views may be * found in the documentation for the {@link #checkedCollection * checkedCollection} method. * *

The returned queue will be serializable if the specified queue * is serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned queue permits insertion of {@code null} elements * whenever the backing queue does. * * @param queue the queue for which a dynamically typesafe view is to be * returned * @param type the type of element that {@code queue} is permitted to hold * @return a dynamically typesafe view of the specified queue * @since 1.8 */ public static Queue checkedQueue(Queue queue, Class type) { return new CheckedQueue<>(queue, type); } /** * @serial include */ static class CheckedQueue extends CheckedCollection implements Queue, Serializable { private static final long serialVersionUID = 1433151992604707767L; final Queue queue; CheckedQueue(Queue queue, Class elementType) { super(queue, elementType); this.queue = queue; } public E element() {return queue.element();} public boolean equals(Object o) {return o == this || c.equals(o);} public int hashCode() {return c.hashCode();} public E peek() {return queue.peek();} public E poll() {return queue.poll();} public E remove() {return queue.remove();} public boolean offer(E e) { typeCheck(e); return add(e); } } /** * Returns a dynamically typesafe view of the specified set. * Any attempt to insert an element of the wrong type will result in * an immediate {@link ClassCastException}. Assuming a set contains * no incorrectly typed elements prior to the time a dynamically typesafe * view is generated, and that all subsequent access to the set * takes place through the view, it is guaranteed that the * set cannot contain an incorrectly typed element. * *

A discussion of the use of dynamically typesafe views may be * found in the documentation for the {@link #checkedCollection * checkedCollection} method. * *

The returned set will be serializable if the specified set is * serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned set permits insertion of null elements whenever * the backing set does. * * @param s the set for which a dynamically typesafe view is to be * returned * @param type the type of element that {@code s} is permitted to hold * @return a dynamically typesafe view of the specified set * @since 1.5 */ public static Set checkedSet(Set s, Class type) { return new CheckedSet<>(s, type); } /** * @serial include */ static class CheckedSet extends CheckedCollection implements Set, Serializable { private static final long serialVersionUID = 4694047833775013803L; CheckedSet(Set s, Class elementType) { super(s, elementType); } public boolean equals(Object o) { return o == this || c.equals(o); } public int hashCode() { return c.hashCode(); } } /** * Returns a dynamically typesafe view of the specified sorted set. * Any attempt to insert an element of the wrong type will result in an * immediate {@link ClassCastException}. Assuming a sorted set * contains no incorrectly typed elements prior to the time a * dynamically typesafe view is generated, and that all subsequent * access to the sorted set takes place through the view, it is * guaranteed that the sorted set cannot contain an incorrectly * typed element. * *

A discussion of the use of dynamically typesafe views may be * found in the documentation for the {@link #checkedCollection * checkedCollection} method. * *

The returned sorted set will be serializable if the specified sorted * set is serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned sorted set permits insertion of null elements * whenever the backing sorted set does. * * @param s the sorted set for which a dynamically typesafe view is to be * returned * @param type the type of element that {@code s} is permitted to hold * @return a dynamically typesafe view of the specified sorted set * @since 1.5 */ public static SortedSet checkedSortedSet(SortedSet s, Class type) { return new CheckedSortedSet<>(s, type); } /** * @serial include */ static class CheckedSortedSet extends CheckedSet implements SortedSet, Serializable { private static final long serialVersionUID = 1599911165492914959L; private final SortedSet ss; CheckedSortedSet(SortedSet s, Class type) { super(s, type); ss = s; } public Comparator comparator() { return ss.comparator(); } public E first() { return ss.first(); } public E last() { return ss.last(); } public SortedSet subSet(E fromElement, E toElement) { return checkedSortedSet(ss.subSet(fromElement,toElement), type); } public SortedSet headSet(E toElement) { return checkedSortedSet(ss.headSet(toElement), type); } public SortedSet tailSet(E fromElement) { return checkedSortedSet(ss.tailSet(fromElement), type); } } /** * Returns a dynamically typesafe view of the specified list. * Any attempt to insert an element of the wrong type will result in * an immediate {@link ClassCastException}. Assuming a list contains * no incorrectly typed elements prior to the time a dynamically typesafe * view is generated, and that all subsequent access to the list * takes place through the view, it is guaranteed that the * list cannot contain an incorrectly typed element. * *

A discussion of the use of dynamically typesafe views may be * found in the documentation for the {@link #checkedCollection * checkedCollection} method. * *

The returned list will be serializable if the specified list * is serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned list permits insertion of null elements whenever * the backing list does. * * @param list the list for which a dynamically typesafe view is to be * returned * @param type the type of element that {@code list} is permitted to hold * @return a dynamically typesafe view of the specified list * @since 1.5 */ public static List checkedList(List list, Class type) { return (list instanceof RandomAccess ? new CheckedRandomAccessList<>(list, type) : new CheckedList<>(list, type)); } /** * @serial include */ static class CheckedList extends CheckedCollection implements List { private static final long serialVersionUID = 65247728283967356L; final List list; CheckedList(List list, Class type) { super(list, type); this.list = list; } public boolean equals(Object o) { return o == this || list.equals(o); } public int hashCode() { return list.hashCode(); } public E get(int index) { return list.get(index); } public E remove(int index) { return list.remove(index); } public int indexOf(Object o) { return list.indexOf(o); } public int lastIndexOf(Object o) { return list.lastIndexOf(o); } public E set(int index, E element) { typeCheck(element); return list.set(index, element); } public void add(int index, E element) { typeCheck(element); list.add(index, element); } public boolean addAll(int index, Collection c) { return list.addAll(index, checkedCopyOf(c)); } public ListIterator listIterator() { return listIterator(0); } public ListIterator listIterator(final int index) { final ListIterator i = list.listIterator(index); return new ListIterator() { public boolean hasNext() { return i.hasNext(); } public E next() { return i.next(); } public boolean hasPrevious() { return i.hasPrevious(); } public E previous() { return i.previous(); } public int nextIndex() { return i.nextIndex(); } public int previousIndex() { return i.previousIndex(); } public void remove() { i.remove(); } public void set(E e) { typeCheck(e); i.set(e); } public void add(E e) { typeCheck(e); i.add(e); } }; } public List subList(int fromIndex, int toIndex) { return new CheckedList<>(list.subList(fromIndex, toIndex), type); } } /** * @serial include */ static class CheckedRandomAccessList extends CheckedList implements RandomAccess { private static final long serialVersionUID = 1638200125423088369L; CheckedRandomAccessList(List list, Class type) { super(list, type); } public List subList(int fromIndex, int toIndex) { return new CheckedRandomAccessList<>( list.subList(fromIndex, toIndex), type); } } /** * Returns a dynamically typesafe view of the specified map. * Any attempt to insert a mapping whose key or value have the wrong * type will result in an immediate {@link ClassCastException}. * Similarly, any attempt to modify the value currently associated with * a key will result in an immediate {@link ClassCastException}, * whether the modification is attempted directly through the map * itself, or through a {@link Map.Entry} instance obtained from the * map's {@link Map#entrySet() entry set} view. * *

Assuming a map contains no incorrectly typed keys or values * prior to the time a dynamically typesafe view is generated, and * that all subsequent access to the map takes place through the view * (or one of its collection views), it is guaranteed that the * map cannot contain an incorrectly typed key or value. * *

A discussion of the use of dynamically typesafe views may be * found in the documentation for the {@link #checkedCollection * checkedCollection} method. * *

The returned map will be serializable if the specified map is * serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned map permits insertion of null keys or values * whenever the backing map does. * * @param m the map for which a dynamically typesafe view is to be * returned * @param keyType the type of key that {@code m} is permitted to hold * @param valueType the type of value that {@code m} is permitted to hold * @return a dynamically typesafe view of the specified map * @since 1.5 */ public static Map checkedMap(Map m, Class keyType, Class valueType) { return new CheckedMap<>(m, keyType, valueType); } /** * @serial include */ private static class CheckedMap implements Map, Serializable { private static final long serialVersionUID = 5742860141034234728L; private final Map m; final Class keyType; final Class valueType; private void typeCheck(Object key, Object value) { if (key != null && !keyType.isInstance(key)) throw new ClassCastException(badKeyMsg(key)); if (value != null && !valueType.isInstance(value)) throw new ClassCastException(badValueMsg(value)); } private String badKeyMsg(Object key) { return "Attempt to insert " + key.getClass() + " key into map with key type " + keyType; } private String badValueMsg(Object value) { return "Attempt to insert " + value.getClass() + " value into map with value type " + valueType; } CheckedMap(Map m, Class keyType, Class valueType) { if (m == null || keyType == null || valueType == null) throw new NullPointerException(); this.m = m; this.keyType = keyType; this.valueType = valueType; } public int size() { return m.size(); } public boolean isEmpty() { return m.isEmpty(); } public boolean containsKey(Object key) { return m.containsKey(key); } public boolean containsValue(Object v) { return m.containsValue(v); } public V get(Object key) { return m.get(key); } public V remove(Object key) { return m.remove(key); } public void clear() { m.clear(); } public Set keySet() { return m.keySet(); } public Collection values() { return m.values(); } public boolean equals(Object o) { return o == this || m.equals(o); } public int hashCode() { return m.hashCode(); } public String toString() { return m.toString(); } public V put(K key, V value) { typeCheck(key, value); return m.put(key, value); } @SuppressWarnings("unchecked") public void putAll(Map t) { // Satisfy the following goals: // - good diagnostics in case of type mismatch // - all-or-nothing semantics // - protection from malicious t // - correct behavior if t is a concurrent map Object[] entries = t.entrySet().toArray(); List> checked = new ArrayList<>(entries.length); for (Object o : entries) { Map.Entry e = (Map.Entry) o; Object k = e.getKey(); Object v = e.getValue(); typeCheck(k, v); checked.add( new AbstractMap.SimpleImmutableEntry<>((K) k, (V) v)); } for (Map.Entry e : checked) m.put(e.getKey(), e.getValue()); } private transient Set> entrySet = null; public Set> entrySet() { if (entrySet==null) entrySet = new CheckedEntrySet<>(m.entrySet(), valueType); return entrySet; } /** * We need this class in addition to CheckedSet as Map.Entry permits * modification of the backing Map via the setValue operation. This * class is subtle: there are many possible attacks that must be * thwarted. * * @serial exclude */ static class CheckedEntrySet implements Set> { private final Set> s; private final Class valueType; CheckedEntrySet(Set> s, Class valueType) { this.s = s; this.valueType = valueType; } public int size() { return s.size(); } public boolean isEmpty() { return s.isEmpty(); } public String toString() { return s.toString(); } public int hashCode() { return s.hashCode(); } public void clear() { s.clear(); } public boolean add(Map.Entry e) { throw new UnsupportedOperationException(); } public boolean addAll(Collection> coll) { throw new UnsupportedOperationException(); } public Iterator> iterator() { final Iterator> i = s.iterator(); final Class valueType = this.valueType; return new Iterator>() { public boolean hasNext() { return i.hasNext(); } public void remove() { i.remove(); } public Map.Entry next() { return checkedEntry(i.next(), valueType); } }; } @SuppressWarnings("unchecked") public Object[] toArray() { Object[] source = s.toArray(); /* * Ensure that we don't get an ArrayStoreException even if * s.toArray returns an array of something other than Object */ Object[] dest = (CheckedEntry.class.isInstance( source.getClass().getComponentType()) ? source : new Object[source.length]); for (int i = 0; i < source.length; i++) dest[i] = checkedEntry((Map.Entry)source[i], valueType); return dest; } @SuppressWarnings("unchecked") public T[] toArray(T[] a) { // We don't pass a to s.toArray, to avoid window of // vulnerability wherein an unscrupulous multithreaded client // could get his hands on raw (unwrapped) Entries from s. T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); for (int i=0; i)arr[i], valueType); if (arr.length > a.length) return arr; System.arraycopy(arr, 0, a, 0, arr.length); if (a.length > arr.length) a[arr.length] = null; return a; } /** * This method is overridden to protect the backing set against * an object with a nefarious equals function that senses * that the equality-candidate is Map.Entry and calls its * setValue method. */ public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry) o; return s.contains( (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType)); } /** * The bulk collection methods are overridden to protect * against an unscrupulous collection whose contains(Object o) * method senses when o is a Map.Entry, and calls o.setValue. */ public boolean containsAll(Collection c) { for (Object o : c) if (!contains(o)) // Invokes safe contains() above return false; return true; } public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false; return s.remove(new AbstractMap.SimpleImmutableEntry <>((Map.Entry)o)); } public boolean removeAll(Collection c) { return batchRemove(c, false); } public boolean retainAll(Collection c) { return batchRemove(c, true); } private boolean batchRemove(Collection c, boolean complement) { boolean modified = false; Iterator> it = iterator(); while (it.hasNext()) { if (c.contains(it.next()) != complement) { it.remove(); modified = true; } } return modified; } public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Set that = (Set) o; return that.size() == s.size() && containsAll(that); // Invokes safe containsAll() above } static CheckedEntry checkedEntry(Map.Entry e, Class valueType) { return new CheckedEntry<>(e, valueType); } /** * This "wrapper class" serves two purposes: it prevents * the client from modifying the backing Map, by short-circuiting * the setValue method, and it protects the backing Map against * an ill-behaved Map.Entry that attempts to modify another * Map.Entry when asked to perform an equality check. */ private static class CheckedEntry implements Map.Entry { private final Map.Entry e; private final Class valueType; CheckedEntry(Map.Entry e, Class valueType) { this.e = e; this.valueType = valueType; } public K getKey() { return e.getKey(); } public V getValue() { return e.getValue(); } public int hashCode() { return e.hashCode(); } public String toString() { return e.toString(); } public V setValue(V value) { if (value != null && !valueType.isInstance(value)) throw new ClassCastException(badValueMsg(value)); return e.setValue(value); } private String badValueMsg(Object value) { return "Attempt to insert " + value.getClass() + " value into map with value type " + valueType; } public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Map.Entry)) return false; return e.equals(new AbstractMap.SimpleImmutableEntry <>((Map.Entry)o)); } } } } /** * Returns a dynamically typesafe view of the specified sorted map. * Any attempt to insert a mapping whose key or value have the wrong * type will result in an immediate {@link ClassCastException}. * Similarly, any attempt to modify the value currently associated with * a key will result in an immediate {@link ClassCastException}, * whether the modification is attempted directly through the map * itself, or through a {@link Map.Entry} instance obtained from the * map's {@link Map#entrySet() entry set} view. * *

Assuming a map contains no incorrectly typed keys or values * prior to the time a dynamically typesafe view is generated, and * that all subsequent access to the map takes place through the view * (or one of its collection views), it is guaranteed that the * map cannot contain an incorrectly typed key or value. * *

A discussion of the use of dynamically typesafe views may be * found in the documentation for the {@link #checkedCollection * checkedCollection} method. * *

The returned map will be serializable if the specified map is * serializable. * *

Since {@code null} is considered to be a value of any reference * type, the returned map permits insertion of null keys or values * whenever the backing map does. * * @param m the map for which a dynamically typesafe view is to be * returned * @param keyType the type of key that {@code m} is permitted to hold * @param valueType the type of value that {@code m} is permitted to hold * @return a dynamically typesafe view of the specified map * @since 1.5 */ public static SortedMap checkedSortedMap(SortedMap m, Class keyType, Class valueType) { return new CheckedSortedMap<>(m, keyType, valueType); } /** * @serial include */ static class CheckedSortedMap extends CheckedMap implements SortedMap, Serializable { private static final long serialVersionUID = 1599671320688067438L; private final SortedMap sm; CheckedSortedMap(SortedMap m, Class keyType, Class valueType) { super(m, keyType, valueType); sm = m; } public Comparator comparator() { return sm.comparator(); } public K firstKey() { return sm.firstKey(); } public K lastKey() { return sm.lastKey(); } public SortedMap subMap(K fromKey, K toKey) { return checkedSortedMap(sm.subMap(fromKey, toKey), keyType, valueType); } public SortedMap headMap(K toKey) { return checkedSortedMap(sm.headMap(toKey), keyType, valueType); } public SortedMap tailMap(K fromKey) { return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType); } } // Empty collections /** * Returns an iterator that has no elements. More precisely, * *

* *

Implementations of this method are permitted, but not * required, to return the same object from multiple invocations. * * @return an empty iterator * @since 1.7 */ @SuppressWarnings("unchecked") public static Iterator emptyIterator() { return (Iterator) EmptyIterator.EMPTY_ITERATOR; } private static class EmptyIterator implements Iterator { static final EmptyIterator EMPTY_ITERATOR = new EmptyIterator<>(); public boolean hasNext() { return false; } public E next() { throw new NoSuchElementException(); } public void remove() { throw new IllegalStateException(); } } /** * Returns a list iterator that has no elements. More precisely, * *
    * *
  • {@link Iterator#hasNext hasNext} and {@link * ListIterator#hasPrevious hasPrevious} always return {@code * false}. * *
  • {@link Iterator#next next} and {@link ListIterator#previous * previous} always throw {@link NoSuchElementException}. * *
  • {@link Iterator#remove remove} and {@link ListIterator#set * set} always throw {@link IllegalStateException}. * *
  • {@link ListIterator#add add} always throws {@link * UnsupportedOperationException}. * *
  • {@link ListIterator#nextIndex nextIndex} always returns * {@code 0} . * *
  • {@link ListIterator#previousIndex previousIndex} always * returns {@code -1}. * *
* *

Implementations of this method are permitted, but not * required, to return the same object from multiple invocations. * * @return an empty list iterator * @since 1.7 */ @SuppressWarnings("unchecked") public static ListIterator emptyListIterator() { return (ListIterator) EmptyListIterator.EMPTY_ITERATOR; } private static class EmptyListIterator extends EmptyIterator implements ListIterator { static final EmptyListIterator EMPTY_ITERATOR = new EmptyListIterator<>(); public boolean hasPrevious() { return false; } public E previous() { throw new NoSuchElementException(); } public int nextIndex() { return 0; } public int previousIndex() { return -1; } public void set(E e) { throw new IllegalStateException(); } public void add(E e) { throw new UnsupportedOperationException(); } } /** * Returns an enumeration that has no elements. More precisely, * *
    * *
  • {@link Enumeration#hasMoreElements hasMoreElements} always * returns {@code false}. * *
  • {@link Enumeration#nextElement nextElement} always throws * {@link NoSuchElementException}. * *
* *

Implementations of this method are permitted, but not * required, to return the same object from multiple invocations. * * @return an empty enumeration * @since 1.7 */ @SuppressWarnings("unchecked") public static Enumeration emptyEnumeration() { return (Enumeration) EmptyEnumeration.EMPTY_ENUMERATION; } private static class EmptyEnumeration implements Enumeration { static final EmptyEnumeration EMPTY_ENUMERATION = new EmptyEnumeration<>(); public boolean hasMoreElements() { return false; } public E nextElement() { throw new NoSuchElementException(); } } /** * The empty set (immutable). This set is serializable. * * @see #emptySet() */ @SuppressWarnings("unchecked") public static final Set EMPTY_SET = new EmptySet<>(); /** * Returns the empty set (immutable). This set is serializable. * Unlike the like-named field, this method is parameterized. * *

This example illustrates the type-safe way to obtain an empty set: *

     *     Set<String> s = Collections.emptySet();
     * 
* Implementation note: Implementations of this method need not * create a separate Set object for each call. Using this * method is likely to have comparable cost to using the like-named * field. (Unlike this method, the field does not provide type safety.) * * @see #EMPTY_SET * @since 1.5 */ @SuppressWarnings("unchecked") public static final Set emptySet() { return (Set) EMPTY_SET; } /** * @serial include */ private static class EmptySet extends AbstractSet implements Serializable { private static final long serialVersionUID = 1582296315990362920L; public Iterator iterator() { return emptyIterator(); } public int size() {return 0;} public boolean isEmpty() {return true;} public boolean contains(Object obj) {return false;} public boolean containsAll(Collection c) { return c.isEmpty(); } public Object[] toArray() { return new Object[0]; } public T[] toArray(T[] a) { if (a.length > 0) a[0] = null; return a; } // Preserves singleton property private Object readResolve() { return EMPTY_SET; } } /** * Returns the empty sorted set (immutable). This set is serializable. * *

This example illustrates the type-safe way to obtain an empty sorted * set: *

     *     SortedSet<String> s = Collections.emptySortedSet();
     * 
* Implementation note: Implementations of this method need not * create a separate SortedSet object for each call. * * @since 1.8 */ @SuppressWarnings("unchecked") public static final SortedSet emptySortedSet() { return (SortedSet) new EmptySortedSet<>(); } /** * @serial include */ private static class EmptySortedSet extends AbstractSet implements SortedSet, Serializable { private static final long serialVersionUID = 6316515401502265487L; public Iterator iterator() { return emptyIterator(); } public int size() {return 0;} public boolean isEmpty() {return true;} public boolean contains(Object obj) {return false;} public boolean containsAll(Collection c) { return c.isEmpty(); } public Object[] toArray() { return new Object[0]; } public E[] toArray(E[] a) { if (a.length > 0) a[0] = null; return a; } // Preserves singleton property private Object readResolve() { return new EmptySortedSet<>(); } public Comparator comparator() { return null; } public SortedSet subSet(Object fromElement, Object toElement) { Objects.requireNonNull(fromElement); Objects.requireNonNull(toElement); if (!(fromElement instanceof Comparable) || !(toElement instanceof Comparable)) { throw new ClassCastException(); } if ((((Comparable)fromElement).compareTo(toElement) >= 0) || (((Comparable)toElement).compareTo(fromElement) < 0)) { throw new IllegalArgumentException(); } return emptySortedSet(); } public SortedSet headSet(Object toElement) { Objects.requireNonNull(toElement); if (!(toElement instanceof Comparable)) { throw new ClassCastException(); } return emptySortedSet(); } public SortedSet tailSet(Object fromElement) { Objects.requireNonNull(fromElement); if (!(fromElement instanceof Comparable)) { throw new ClassCastException(); } return emptySortedSet(); } public E first() { throw new NoSuchElementException(); } public E last() { throw new NoSuchElementException(); } } /** * The empty list (immutable). This list is serializable. * * @see #emptyList() */ @SuppressWarnings("unchecked") public static final List EMPTY_LIST = new EmptyList<>(); /** * Returns the empty list (immutable). This list is serializable. * *

This example illustrates the type-safe way to obtain an empty list: *

     *     List<String> s = Collections.emptyList();
     * 
* Implementation note: Implementations of this method need not * create a separate List object for each call. Using this * method is likely to have comparable cost to using the like-named * field. (Unlike this method, the field does not provide type safety.) * * @see #EMPTY_LIST * @since 1.5 */ @SuppressWarnings("unchecked") public static final List emptyList() { return (List) EMPTY_LIST; } /** * @serial include */ private static class EmptyList extends AbstractList implements RandomAccess, Serializable { private static final long serialVersionUID = 8842843931221139166L; public Iterator iterator() { return emptyIterator(); } public ListIterator listIterator() { return emptyListIterator(); } public int size() {return 0;} public boolean isEmpty() {return true;} public boolean contains(Object obj) {return false;} public boolean containsAll(Collection c) { return c.isEmpty(); } public Object[] toArray() { return new Object[0]; } public T[] toArray(T[] a) { if (a.length > 0) a[0] = null; return a; } public E get(int index) { throw new IndexOutOfBoundsException("Index: "+index); } public boolean equals(Object o) { return (o instanceof List) && ((List)o).isEmpty(); } public int hashCode() { return 1; } // Preserves singleton property private Object readResolve() { return EMPTY_LIST; } } /** * The empty map (immutable). This map is serializable. * * @see #emptyMap() * @since 1.3 */ @SuppressWarnings("unchecked") public static final Map EMPTY_MAP = new EmptyMap<>(); /** * Returns the empty map (immutable). This map is serializable. * *

This example illustrates the type-safe way to obtain an empty set: *

     *     Map<String, Date> s = Collections.emptyMap();
     * 
* Implementation note: Implementations of this method need not * create a separate Map object for each call. Using this * method is likely to have comparable cost to using the like-named * field. (Unlike this method, the field does not provide type safety.) * * @see #EMPTY_MAP * @since 1.5 */ @SuppressWarnings("unchecked") public static final Map emptyMap() { return (Map) EMPTY_MAP; } /** * @serial include */ private static class EmptyMap extends AbstractMap implements Serializable { private static final long serialVersionUID = 6428348081105594320L; public int size() {return 0;} public boolean isEmpty() {return true;} public boolean containsKey(Object key) {return false;} public boolean containsValue(Object value) {return false;} public V get(Object key) {return null;} public Set keySet() {return emptySet();} public Collection values() {return emptySet();} public Set> entrySet() {return emptySet();} public boolean equals(Object o) { return (o instanceof Map) && ((Map)o).isEmpty(); } public int hashCode() {return 0;} // Preserves singleton property private Object readResolve() { return EMPTY_MAP; } } // Singleton collections /** * Returns an immutable set containing only the specified object. * The returned set is serializable. * * @param o the sole object to be stored in the returned set. * @return an immutable set containing only the specified object. */ public static Set singleton(T o) { return new SingletonSet<>(o); } static Iterator singletonIterator(final E e) { return new Iterator() { private boolean hasNext = true; public boolean hasNext() { return hasNext; } public E next() { if (hasNext) { hasNext = false; return e; } throw new NoSuchElementException(); } public void remove() { throw new UnsupportedOperationException(); } }; } /** * @serial include */ private static class SingletonSet extends AbstractSet implements Serializable { private static final long serialVersionUID = 3193687207550431679L; private final E element; SingletonSet(E e) {element = e;} public Iterator iterator() { return singletonIterator(element); } public int size() {return 1;} public boolean contains(Object o) {return eq(o, element);} } /** * Returns an immutable list containing only the specified object. * The returned list is serializable. * * @param o the sole object to be stored in the returned list. * @return an immutable list containing only the specified object. * @since 1.3 */ public static List singletonList(T o) { return new SingletonList<>(o); } /** * @serial include */ private static class SingletonList extends AbstractList implements RandomAccess, Serializable { private static final long serialVersionUID = 3093736618740652951L; private final E element; SingletonList(E obj) {element = obj;} public Iterator iterator() { return singletonIterator(element); } public int size() {return 1;} public boolean contains(Object obj) {return eq(obj, element);} public E get(int index) { if (index != 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); return element; } } /** * Returns an immutable map, mapping only the specified key to the * specified value. The returned map is serializable. * * @param key the sole key to be stored in the returned map. * @param value the value to which the returned map maps key. * @return an immutable map containing only the specified key-value * mapping. * @since 1.3 */ public static Map singletonMap(K key, V value) { return new SingletonMap<>(key, value); } /** * @serial include */ private static class SingletonMap extends AbstractMap implements Serializable { private static final long serialVersionUID = -6979724477215052911L; private final K k; private final V v; SingletonMap(K key, V value) { k = key; v = value; } public int size() {return 1;} public boolean isEmpty() {return false;} public boolean containsKey(Object key) {return eq(key, k);} public boolean containsValue(Object value) {return eq(value, v);} public V get(Object key) {return (eq(key, k) ? v : null);} private transient Set keySet = null; private transient Set> entrySet = null; private transient Collection values = null; public Set keySet() { if (keySet==null) keySet = singleton(k); return keySet; } public Set> entrySet() { if (entrySet==null) entrySet = Collections.>singleton( new SimpleImmutableEntry<>(k, v)); return entrySet; } public Collection values() { if (values==null) values = singleton(v); return values; } } // Miscellaneous /** * Returns an immutable list consisting of n copies of the * specified object. The newly allocated data object is tiny (it contains * a single reference to the data object). This method is useful in * combination with the List.addAll method to grow lists. * The returned list is serializable. * * @param n the number of elements in the returned list. * @param o the element to appear repeatedly in the returned list. * @return an immutable list consisting of n copies of the * specified object. * @throws IllegalArgumentException if {@code n < 0} * @see List#addAll(Collection) * @see List#addAll(int, Collection) */ public static List nCopies(int n, T o) { if (n < 0) throw new IllegalArgumentException("List length = " + n); return new CopiesList<>(n, o); } /** * @serial include */ private static class CopiesList extends AbstractList implements RandomAccess, Serializable { private static final long serialVersionUID = 2739099268398711800L; final int n; final E element; CopiesList(int n, E e) { assert n >= 0; this.n = n; element = e; } public int size() { return n; } public boolean contains(Object obj) { return n != 0 && eq(obj, element); } public int indexOf(Object o) { return contains(o) ? 0 : -1; } public int lastIndexOf(Object o) { return contains(o) ? n - 1 : -1; } public E get(int index) { if (index < 0 || index >= n) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+n); return element; } public Object[] toArray() { final Object[] a = new Object[n]; if (element != null) Arrays.fill(a, 0, n, element); return a; } public T[] toArray(T[] a) { final int n = this.n; if (a.length < n) { a = (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), n); if (element != null) Arrays.fill(a, 0, n, element); } else { Arrays.fill(a, 0, n, element); if (a.length > n) a[n] = null; } return a; } public List subList(int fromIndex, int toIndex) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); if (toIndex > n) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); return new CopiesList<>(toIndex - fromIndex, element); } } /** * Returns a comparator that imposes the reverse of the natural * ordering on a collection of objects that implement the * {@code Comparable} interface. (The natural ordering is the ordering * imposed by the objects' own {@code compareTo} method.) This enables a * simple idiom for sorting (or maintaining) collections (or arrays) of * objects that implement the {@code Comparable} interface in * reverse-natural-order. For example, suppose {@code a} is an array of * strings. Then:
     *          Arrays.sort(a, Collections.reverseOrder());
     * 
sorts the array in reverse-lexicographic (alphabetical) order.

* * The returned comparator is serializable. * * @return A comparator that imposes the reverse of the natural * ordering on a collection of objects that implement * the Comparable interface. * @see Comparable */ public static Comparator reverseOrder() { return (Comparator) ReverseComparator.REVERSE_ORDER; } /** * @serial include */ private static class ReverseComparator implements Comparator>, Serializable { private static final long serialVersionUID = 7207038068494060240L; static final ReverseComparator REVERSE_ORDER = new ReverseComparator(); public int compare(Comparable c1, Comparable c2) { return c2.compareTo(c1); } private Object readResolve() { return reverseOrder(); } } /** * Returns a comparator that imposes the reverse ordering of the specified * comparator. If the specified comparator is {@code null}, this method is * equivalent to {@link #reverseOrder()} (in other words, it returns a * comparator that imposes the reverse of the natural ordering on * a collection of objects that implement the Comparable interface). * *

The returned comparator is serializable (assuming the specified * comparator is also serializable or {@code null}). * * @param cmp a comparator who's ordering is to be reversed by the returned * comparator or {@code null} * @return A comparator that imposes the reverse ordering of the * specified comparator. * @since 1.5 */ public static Comparator reverseOrder(Comparator cmp) { if (cmp == null) return reverseOrder(); if (cmp instanceof ReverseComparator2) return ((ReverseComparator2)cmp).cmp; return new ReverseComparator2<>(cmp); } /** * @serial include */ private static class ReverseComparator2 implements Comparator, Serializable { private static final long serialVersionUID = 4374092139857L; /** * The comparator specified in the static factory. This will never * be null, as the static factory returns a ReverseComparator * instance if its argument is null. * * @serial */ final Comparator cmp; ReverseComparator2(Comparator cmp) { assert cmp != null; this.cmp = cmp; } public int compare(T t1, T t2) { return cmp.compare(t2, t1); } public boolean equals(Object o) { return (o == this) || (o instanceof ReverseComparator2 && cmp.equals(((ReverseComparator2)o).cmp)); } public int hashCode() { return cmp.hashCode() ^ Integer.MIN_VALUE; } } /** * Returns an enumeration over the specified collection. This provides * interoperability with legacy APIs that require an enumeration * as input. * * @param c the collection for which an enumeration is to be returned. * @return an enumeration over the specified collection. * @see Enumeration */ public static Enumeration enumeration(final Collection c) { return new Enumeration() { private final Iterator i = c.iterator(); public boolean hasMoreElements() { return i.hasNext(); } public T nextElement() { return i.next(); } }; } /** * Returns an array list containing the elements returned by the * specified enumeration in the order they are returned by the * enumeration. This method provides interoperability between * legacy APIs that return enumerations and new APIs that require * collections. * * @param e enumeration providing elements for the returned * array list * @return an array list containing the elements returned * by the specified enumeration. * @since 1.4 * @see Enumeration * @see ArrayList */ public static ArrayList list(Enumeration e) { ArrayList l = new ArrayList<>(); while (e.hasMoreElements()) l.add(e.nextElement()); return l; } /** * Returns true if the specified arguments are equal, or both null. */ static boolean eq(Object o1, Object o2) { return o1==null ? o2==null : o1.equals(o2); } /** * Returns the number of elements in the specified collection equal to the * specified object. More formally, returns the number of elements * e in the collection such that * (o == null ? e == null : o.equals(e)). * * @param c the collection in which to determine the frequency * of o * @param o the object whose frequency is to be determined * @throws NullPointerException if c is null * @since 1.5 */ public static int frequency(Collection c, Object o) { int result = 0; if (o == null) { for (Object e : c) if (e == null) result++; } else { for (Object e : c) if (o.equals(e)) result++; } return result; } /** * Returns {@code true} if the two specified collections have no * elements in common. * *

Care must be exercised if this method is used on collections that * do not comply with the general contract for {@code Collection}. * Implementations may elect to iterate over either collection and test * for containment in the other collection (or to perform any equivalent * computation). If either collection uses a nonstandard equality test * (as does a {@link SortedSet} whose ordering is not compatible with * equals, or the key set of an {@link IdentityHashMap}), both * collections must use the same nonstandard equality test, or the * result of this method is undefined. * *

Care must also be exercised when using collections that have * restrictions on the elements that they may contain. Collection * implementations are allowed to throw exceptions for any operation * involving elements they deem ineligible. For absolute safety the * specified collections should contain only elements which are * eligible elements for both collections. * *

Note that it is permissible to pass the same collection in both * parameters, in which case the method will return {@code true} if and * only if the collection is empty. * * @param c1 a collection * @param c2 a collection * @return {@code true} if the two specified collections have no * elements in common. * @throws NullPointerException if either collection is {@code null}. * @throws NullPointerException if one collection contains a {@code null} * element and {@code null} is not an eligible element for the other collection. * (optional) * @throws ClassCastException if one collection contains an element that is * of a type which is ineligible for the other collection. * (optional) * @since 1.5 */ public static boolean disjoint(Collection c1, Collection c2) { // The collection to be used for contains(). Preference is given to // the collection who's contains() has lower O() complexity. Collection contains = c2; // The collection to be iterated. If the collections' contains() impl // are of different O() complexity, the collection with slower // contains() will be used for iteration. For collections who's // contains() are of the same complexity then best performance is // achieved by iterating the smaller collection. Collection iterate = c1; // Performance optimization cases. The heuristics: // 1. Generally iterate over c1. // 2. If c1 is a Set then iterate over c2. // 3. If either collection is empty then result is always true. // 4. Iterate over the smaller Collection. if (c1 instanceof Set) { // Use c1 for contains as a Set's contains() is expected to perform // better than O(N/2) iterate = c2; contains = c1; } else if (!(c2 instanceof Set)) { // Both are mere Collections. Iterate over smaller collection. // Example: If c1 contains 3 elements and c2 contains 50 elements and // assuming contains() requires ceiling(N/2) comparisons then // checking for all c1 elements in c2 would require 75 comparisons // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring // 100 comparisons (50 * ceiling(3/2)). int c1size = c1.size(); int c2size = c2.size(); if (c1size == 0 || c2size == 0) { // At least one collection is empty. Nothing will match. return true; } if (c1size > c2size) { iterate = c2; contains = c1; } } for (Object e : iterate) { if (contains.contains(e)) { // Found a common element. Collections are not disjoint. return false; } } // No common elements were found. return true; } /** * Adds all of the specified elements to the specified collection. * Elements to be added may be specified individually or as an array. * The behavior of this convenience method is identical to that of * c.addAll(Arrays.asList(elements)), but this method is likely * to run significantly faster under most implementations. * *

When elements are specified individually, this method provides a * convenient way to add a few elements to an existing collection: *

     *     Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
     * 
* * @param c the collection into which elements are to be inserted * @param elements the elements to insert into c * @return true if the collection changed as a result of the call * @throws UnsupportedOperationException if c does not support * the add operation * @throws NullPointerException if elements contains one or more * null values and c does not permit null elements, or * if c or elements are null * @throws IllegalArgumentException if some property of a value in * elements prevents it from being added to c * @see Collection#addAll(Collection) * @since 1.5 */ @SafeVarargs public static boolean addAll(Collection c, T... elements) { boolean result = false; for (T element : elements) result |= c.add(element); return result; } /** * Returns a set backed by the specified map. The resulting set displays * the same ordering, concurrency, and performance characteristics as the * backing map. In essence, this factory method provides a {@link Set} * implementation corresponding to any {@link Map} implementation. There * is no need to use this method on a {@link Map} implementation that * already has a corresponding {@link Set} implementation (such as {@link * HashMap} or {@link TreeMap}). * *

Each method invocation on the set returned by this method results in * exactly one method invocation on the backing map or its keySet * view, with one exception. The addAll method is implemented * as a sequence of put invocations on the backing map. * *

The specified map must be empty at the time this method is invoked, * and should not be accessed directly after this method returns. These * conditions are ensured if the map is created empty, passed directly * to this method, and no reference to the map is retained, as illustrated * in the following code fragment: *

     *    Set<Object> weakHashSet = Collections.newSetFromMap(
     *        new WeakHashMap<Object, Boolean>());
     * 
* * @param map the backing map * @return the set backed by the map * @throws IllegalArgumentException if map is not empty * @since 1.6 */ public static Set newSetFromMap(Map map) { return new SetFromMap<>(map); } /** * @serial include */ private static class SetFromMap extends AbstractSet implements Set, Serializable { private final Map m; // The backing map private transient Set s; // Its keySet SetFromMap(Map map) { if (!map.isEmpty()) throw new IllegalArgumentException("Map is non-empty"); m = map; s = map.keySet(); } public void clear() { m.clear(); } public int size() { return m.size(); } public boolean isEmpty() { return m.isEmpty(); } public boolean contains(Object o) { return m.containsKey(o); } public boolean remove(Object o) { return m.remove(o) != null; } public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } public Iterator iterator() { return s.iterator(); } public Object[] toArray() { return s.toArray(); } public T[] toArray(T[] a) { return s.toArray(a); } public String toString() { return s.toString(); } public int hashCode() { return s.hashCode(); } public boolean equals(Object o) { return o == this || s.equals(o); } public boolean containsAll(Collection c) {return s.containsAll(c);} public boolean removeAll(Collection c) {return s.removeAll(c);} public boolean retainAll(Collection c) {return s.retainAll(c);} // addAll is the only inherited implementation private static final long serialVersionUID = 2454657854757543876L; private void readObject(java.io.ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); s = m.keySet(); } } /** * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo) * {@link Queue}. Method add is mapped to push, * remove is mapped to pop and so on. This * view can be useful when you would like to use a method * requiring a Queue but you need Lifo ordering. * *

Each method invocation on the queue returned by this method * results in exactly one method invocation on the backing deque, with * one exception. The {@link Queue#addAll addAll} method is * implemented as a sequence of {@link Deque#addFirst addFirst} * invocations on the backing deque. * * @param deque the deque * @return the queue * @since 1.6 */ public static Queue asLifoQueue(Deque deque) { return new AsLIFOQueue<>(deque); } /** * @serial include */ static class AsLIFOQueue extends AbstractQueue implements Queue, Serializable { private static final long serialVersionUID = 1802017725587941708L; private final Deque q; AsLIFOQueue(Deque q) { this.q = q; } public boolean add(E e) { q.addFirst(e); return true; } public boolean offer(E e) { return q.offerFirst(e); } public E poll() { return q.pollFirst(); } public E remove() { return q.removeFirst(); } public E peek() { return q.peekFirst(); } public E element() { return q.getFirst(); } public void clear() { q.clear(); } public int size() { return q.size(); } public boolean isEmpty() { return q.isEmpty(); } public boolean contains(Object o) { return q.contains(o); } public boolean remove(Object o) { return q.remove(o); } public Iterator iterator() { return q.iterator(); } public Object[] toArray() { return q.toArray(); } public T[] toArray(T[] a) { return q.toArray(a); } public String toString() { return q.toString(); } public boolean containsAll(Collection c) {return q.containsAll(c);} public boolean removeAll(Collection c) {return q.removeAll(c);} public boolean retainAll(Collection c) {return q.retainAll(c);} // We use inherited addAll; forwarding addAll would be wrong } }