/*
* Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
* Copyright (C) 2014-2020 MicroEJ Corp. - EDC compliance and optimizations.
* 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 ej.annotation.Nullable;
/**
* 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
*/
public static > void sort(List list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator i = list.listIterator();
for (int j = 0; j < a.length; j++) {
i.next();
i.set((T) a[j]);
}
}
/**
* Sorts the specified list according to the order induced by the specified comparator. All elements in the list
* must be mutually 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
*/
public static void sort(List list, @Nullable Comparator c) {
Object[] a = list.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator i = list.listIterator();
for (int j = 0; j < a.length; j++) {
i.next();
i.set(a[j]);
}
}
/**
* Searches the specified list for the specified object using the binary search algorithm. The list must be sorted
* into ascending order according to the {@linkplain Comparable natural ordering} of its elements (as by the
* {@link #sort(List)} 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.
* @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() < BINARYSEARCH_THRESHOLD) {
return Collections.indexedBinarySearch(list, key);
} else {
return Collections.iteratorBinarySearch(list, key);
}
}
private static 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.
*/
public static int binarySearch(List list, T key, @Nullable Comparator c) {
if (c == null) {
return binarySearch((List) list, key);
}
if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD) {
return Collections.indexedBinarySearch(list, key, c);
} else {
return Collections.iteratorBinarySearch(list, key, c);
}
}
private static 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
}
private interface SelfComparable extends Comparable {
}
/**
* 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.
*/
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 < mid; i++, j--) {
swap(list, i, j);
}
} else {
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i = 0, mid = list.size() >> 1; i < mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}
/**
* Randomly permutes the specified list using a default source of randomness. All permutations occur with
* approximately equal likelihood.
*
*
* 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);
}
@Nullable
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.
*/
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
ListIterator it = list.listIterator();
for (int i = 0; i < arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
/**
* Swaps the elements at the specified positions in the specified list. (If the specified positions are equal,
* invoking this method leaves the list unchanged.)
*
* @param list
* The list in which to swap elements.
* @param i
* the index of one element to be swapped.
* @param j
* the index of the other element to be swapped.
* @throws IndexOutOfBoundsException
* if either i or j is out of range (i < 0 || i >= list.size() || j < 0 || j
* >= list.size()).
* @since 1.4
*/
public static void swap(List list, int i, int j) {
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 < size; i++) {
list.set(i, obj);
}
} else {
ListIterator itr = list.listIterator();
for (int i = 0; i < size; i++) {
itr.next();
itr.set(obj);
}
}
}
/**
* Copies all of the elements from one list into another. After the operation, the index of each copied element in
* the destination list will be identical to its index in the source list. The destination list must be at least as
* long as the source list. If it is longer, the remaining elements in the destination list are unaffected.
*
*
* 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 < srcSize; i++) {
dest.set(i, src.get(i));
}
} else {
ListIterator di = dest.listIterator();
ListIterator si = src.listIterator();
for (int i = 0; i < srcSize; i++) {
di.next();
di.set(si.next());
}
}
}
/**
* Returns the minimum 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 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
*/
public static T min(Collection coll, @Nullable Comparator comp) {
if (comp == null) {
return (T) min((Collection) (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
*/
public static T max(Collection coll, @Nullable Comparator comp) {
if (comp == null) {
return (T) max((Collection) (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 < size; i++) {
if (list.get(i) == null) {
list.set(i, newVal);
result = true;
}
}
} else {
for (int i = 0; i < size; i++) {
if (oldVal.equals(list.get(i))) {
list.set(i, newVal);
result = true;
}
}
}
} else {
ListIterator itr = list.listIterator();
if (oldVal == null) {
for (int i = 0; i < size; i++) {
if (itr.next() == null) {
itr.set(newVal);
result = true;
}
}
} else {
for (int i = 0; i < size; i++) {
if (oldVal.equals(itr.next())) {
itr.set(newVal);
result = true;
}
}
}
}
return result;
}
/**
* Returns 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. More formally, returns the lowest index i 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 < targetSize; i++, j++) {
if (!eq(target.get(i), source.get(j))) {
continue nextCand; // Element mismatch, try next cand
}
}
return candidate; // All elements of candidate matched target
}
} else { // Iterator version of above algorithm
ListIterator si = source.listIterator();
nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
ListIterator ti = target.listIterator();
for (int i = 0; i < targetSize; i++) {
if (!eq(ti.next(), si.next())) {
// Back up source iterator to next candidate
for (int j = 0; j < i; j++) {
si.previous();
}
continue nextCand;
}
}
return candidate;
}
}
return -1; // No candidate matched the target
}
/**
* Returns 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. More formally, returns the highest index i 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 < targetSize; i++, j++) {
if (!eq(target.get(i), source.get(j))) {
continue nextCand; // Element mismatch, try next cand
}
}
return candidate; // All elements of candidate matched target
}
} else { // Iterator version of above algorithm
if (maxCandidate < 0) {
return -1;
}
ListIterator si = source.listIterator(maxCandidate);
nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) {
ListIterator ti = target.listIterator();
for (int i = 0; i < targetSize; i++) {
if (!eq(ti.next(), si.next())) {
if (candidate != 0) {
// Back up source iterator to next candidate
for (int j = 0; j <= i + 1; j++) {
si.previous();
}
}
continue nextCand;
}
}
return candidate;
}
}
return -1; // No candidate matched the target
}
// Unmodifiable Wrappers
/**
* Returns an unmodifiable view of the specified collection. This method allows modules to provide users with
* "read-only" access to internal collections. Query operations on the returned collection "read through" to the
* specified collection, and attempts to modify the returned collection, whether direct or via its iterator, result
* in an UnsupportedOperationException.
*
*
* 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;
}
@Override
public int size() {
return this.c.size();
}
@Override
public boolean isEmpty() {
return this.c.isEmpty();
}
@Override
public boolean contains(Object o) {
return this.c.contains(o);
}
@Override
public Object[] toArray() {
return this.c.toArray();
}
@Override
public T[] toArray(T[] a) {
return this.c.toArray(a);
}
@Override
public String toString() {
return this.c.toString();
}
@Override
public Iterator iterator() {
return new Iterator() {
private final Iterator i = UnmodifiableCollection.this.c.iterator();
@Override
public boolean hasNext() {
return this.i.hasNext();
}
@Override
public E next() {
return this.i.next();
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override
public boolean add(E e) {
throw new UnsupportedOperationException();
}
@Override
public boolean remove(Object o) {
throw new UnsupportedOperationException();
}
@Override
public boolean containsAll(Collection coll) {
return this.c.containsAll(coll);
}
@Override
public boolean addAll(Collection coll) {
throw new UnsupportedOperationException();
}
@Override
public boolean removeAll(Collection coll) {
throw new UnsupportedOperationException();
}
@Override
public boolean retainAll(Collection coll) {
throw new UnsupportedOperationException();
}
@Override
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);
}
@Override
public boolean equals(Object o) {
return o == this || this.c.equals(o);
}
@Override
public int hashCode() {
return this.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);
this.ss = s;
}
@Override
@Nullable
public Comparator comparator() {
return this.ss.comparator();
}
@Override
public SortedSet subSet(E fromElement, E toElement) {
return new UnmodifiableSortedSet<>(this.ss.subSet(fromElement, toElement));
}
@Override
public SortedSet headSet(E toElement) {
return new UnmodifiableSortedSet<>(this.ss.headSet(toElement));
}
@Override
public SortedSet tailSet(E fromElement) {
return new UnmodifiableSortedSet<>(this.ss.tailSet(fromElement));
}
@Override
public E first() {
return this.ss.first();
}
@Override
public E last() {
return this.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;
}
@Override
public boolean equals(Object o) {
return o == this || this.list.equals(o);
}
@Override
public int hashCode() {
return this.list.hashCode();
}
@Override
@Nullable
public E get(int index) {
return this.list.get(index);
}
@Override
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
@Override
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
@Override
public E remove(int index) {
throw new UnsupportedOperationException();
}
@Override
public int indexOf(Object o) {
return this.list.indexOf(o);
}
@Override
public int lastIndexOf(Object o) {
return this.list.lastIndexOf(o);
}
@Override
public boolean addAll(int index, Collection c) {
throw new UnsupportedOperationException();
}
@Override
public ListIterator listIterator() {
return listIterator(0);
}
@Override
public ListIterator listIterator(final int index) {
return new ListIterator() {
private final ListIterator i = UnmodifiableList.this.list.listIterator(index);
@Override
public boolean hasNext() {
return this.i.hasNext();
}
@Override
public E next() {
return this.i.next();
}
@Override
public boolean hasPrevious() {
return this.i.hasPrevious();
}
@Override
public E previous() {
return this.i.previous();
}
@Override
public int nextIndex() {
return this.i.nextIndex();
}
@Override
public int previousIndex() {
return this.i.previousIndex();
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
@Override
public void set(E e) {
throw new UnsupportedOperationException();
}
@Override
public void add(E e) {
throw new UnsupportedOperationException();
}
};
}
@Override
public List subList(int fromIndex, int toIndex) {
return new UnmodifiableList<>(this.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 (this.list instanceof RandomAccess ? new UnmodifiableRandomAccessList<>(this.list) : this);
}
}
/**
* @serial include
*/
static class UnmodifiableRandomAccessList extends UnmodifiableList implements RandomAccess {
UnmodifiableRandomAccessList(List list) {
super(list);
}
@Override
public List subList(int fromIndex, int toIndex) {
return new UnmodifiableRandomAccessList<>(this.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<>(this.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;
}
@Override
public int size() {
return this.m.size();
}
@Override
public boolean isEmpty() {
return this.m.isEmpty();
}
@Override
public boolean containsKey(Object key) {
return this.m.containsKey(key);
}
@Override
public boolean containsValue(Object val) {
return this.m.containsValue(val);
}
@Override
@Nullable
public V get(Object key) {
return this.m.get(key);
}
@Override
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
@Override
public V remove(Object key) {
throw new UnsupportedOperationException();
}
@Override
public void putAll(Map m) {
throw new UnsupportedOperationException();
}
@Override
public void clear() {
throw new UnsupportedOperationException();
}
@Nullable
private transient Set keySet = null;
@Nullable
private transient Set> entrySet = null;
@Nullable
private transient Collection values = null;
@Override
public Set keySet() {
if (this.keySet == null) {
this.keySet = unmodifiableSet(this.m.keySet());
}
return this.keySet;
}
@Override
public Set> entrySet() {
if (this.entrySet == null) {
this.entrySet = new UnmodifiableEntrySet<>(this.m.entrySet());
}
return this.entrySet;
}
@Override
public Collection values() {
if (this.values == null) {
this.values = unmodifiableCollection(this.m.values());
}
return this.values;
}
@Override
public boolean equals(Object o) {
return o == this || this.m.equals(o);
}
@Override
public int hashCode() {
return this.m.hashCode();
}
@Override
public String toString() {
return this.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;
UnmodifiableEntrySet(Set> s) {
super((Set) s);
}
@Override
public Iterator> iterator() {
return new Iterator>() {
private final Iterator> i = UnmodifiableEntrySet.this.c
.iterator();
@Override
public boolean hasNext() {
return this.i.hasNext();
}
@Override
public Map.Entry next() {
return new UnmodifiableEntry<>(this.i.next());
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override
public Object[] toArray() {
Object[] a = this.c.toArray();
for (int i = 0; i < a.length; i++) {
a[i] = new UnmodifiableEntry<>((Map.Entry) a[i]);
}
return a;
}
@Override
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 tmpArray = new Object[this.c.size()];
Object[] arr = this.c.toArray((T[]) tmpArray);
for (int i = 0; i < arr.length; i++) {
arr[i] = new UnmodifiableEntry<>((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.
*/
@Override
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
return this.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.
*/
@Override
public boolean containsAll(Collection coll) {
for (Object e : coll) {
if (!contains(e)) {
return false;
}
}
return true;
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Set)) {
return false;
}
Set s = (Set) o;
if (s.size() != this.c.size()) {
return false;
}
return containsAll(s); // Invokes safe containsAll() above
}
// redefine hashcode to match IS2T rules.
@Override
public int hashCode() {
return this.c.hashCode();
}
/**
* 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 final Map.Entry e;
UnmodifiableEntry(Map.Entry e) {
this.e = e;
}
@Override
public K getKey() {
return this.e.getKey();
}
@Override
public V getValue() {
return this.e.getValue();
}
@Override
public V setValue(V value) {
throw new UnsupportedOperationException();
}
@Override
public int hashCode() {
return this.e.hashCode();
}
@Override
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(this.e.getKey(), t.getKey()) && eq(this.e.getValue(), t.getValue());
}
@Override
public String toString() {
return this.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);
this.sm = m;
}
@Override
@Nullable
public Comparator comparator() {
return this.sm.comparator();
}
@Override
public SortedMap subMap(K fromKey, K toKey) {
return new UnmodifiableSortedMap<>(this.sm.subMap(fromKey, toKey));
}
@Override
public SortedMap headMap(K toKey) {
return new UnmodifiableSortedMap<>(this.sm.headMap(toKey));
}
@Override
public SortedMap tailMap(K fromKey) {
return new UnmodifiableSortedMap<>(this.sm.tailMap(fromKey));
}
@Override
public K firstKey() {
return this.sm.firstKey();
}
@Override
public K lastKey() {
return this.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;
this.mutex = this;
}
SynchronizedCollection(Collection c, Object mutex) {
this.c = c;
this.mutex = mutex;
}
@Override
public int size() {
synchronized (this.mutex) {
return this.c.size();
}
}
@Override
public boolean isEmpty() {
synchronized (this.mutex) {
return this.c.isEmpty();
}
}
@Override
public boolean contains(Object o) {
synchronized (this.mutex) {
return this.c.contains(o);
}
}
@Override
public Object[] toArray() {
synchronized (this.mutex) {
return this.c.toArray();
}
}
@Override
public T[] toArray(T[] a) {
synchronized (this.mutex) {
return this.c.toArray(a);
}
}
@Override
public Iterator iterator() {
return this.c.iterator(); // Must be manually synched by user!
}
@Override
public boolean add(E e) {
synchronized (this.mutex) {
return this.c.add(e);
}
}
@Override
public boolean remove(Object o) {
synchronized (this.mutex) {
return this.c.remove(o);
}
}
@Override
public boolean containsAll(Collection coll) {
synchronized (this.mutex) {
return this.c.containsAll(coll);
}
}
@Override
public boolean addAll(Collection coll) {
synchronized (this.mutex) {
return this.c.addAll(coll);
}
}
@Override
public boolean removeAll(Collection coll) {
synchronized (this.mutex) {
return this.c.removeAll(coll);
}
}
@Override
public boolean retainAll(Collection coll) {
synchronized (this.mutex) {
return this.c.retainAll(coll);
}
}
@Override
public void clear() {
synchronized (this.mutex) {
this.c.clear();
}
}
@Override
public String toString() {
synchronized (this.mutex) {
return this.c.toString();
}
}
}
/**
* 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);
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
synchronized (this.mutex) {
return this.c.equals(o);
}
}
@Override
public int hashCode() {
synchronized (this.mutex) {
return this.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);
this.ss = s;
}
SynchronizedSortedSet(SortedSet s, Object mutex) {
super(s, mutex);
this.ss = s;
}
@Override
@Nullable
public Comparator comparator() {
synchronized (this.mutex) {
return this.ss.comparator();
}
}
@Override
public SortedSet subSet(E fromElement, E toElement) {
synchronized (this.mutex) {
return new SynchronizedSortedSet<>(this.ss.subSet(fromElement, toElement), this.mutex);
}
}
@Override
public SortedSet headSet(E toElement) {
synchronized (this.mutex) {
return new SynchronizedSortedSet<>(this.ss.headSet(toElement), this.mutex);
}
}
@Override
public SortedSet tailSet(E fromElement) {
synchronized (this.mutex) {
return new SynchronizedSortedSet<>(this.ss.tailSet(fromElement), this.mutex);
}
}
@Override
public E first() {
synchronized (this.mutex) {
return this.ss.first();
}
}
@Override
public E last() {
synchronized (this.mutex) {
return this.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;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
synchronized (this.mutex) {
return this.list.equals(o);
}
}
@Override
public int hashCode() {
synchronized (this.mutex) {
return this.list.hashCode();
}
}
@Override
public E get(int index) {
synchronized (this.mutex) {
return this.list.get(index);
}
}
@Override
public E set(int index, E element) {
synchronized (this.mutex) {
return this.list.set(index, element);
}
}
@Override
public void add(int index, E element) {
synchronized (this.mutex) {
this.list.add(index, element);
}
}
@Override
public E remove(int index) {
synchronized (this.mutex) {
return this.list.remove(index);
}
}
@Override
public int indexOf(Object o) {
synchronized (this.mutex) {
return this.list.indexOf(o);
}
}
@Override
public int lastIndexOf(Object o) {
synchronized (this.mutex) {
return this.list.lastIndexOf(o);
}
}
@Override
public boolean addAll(int index, Collection c) {
synchronized (this.mutex) {
return this.list.addAll(index, c);
}
}
@Override
public ListIterator listIterator() {
return this.list.listIterator(); // Must be manually synched by user
}
@Override
public ListIterator listIterator(int index) {
return this.list.listIterator(index); // Must be manually synched by user
}
@Override
public List subList(int fromIndex, int toIndex) {
synchronized (this.mutex) {
return new SynchronizedList<>(this.list.subList(fromIndex, toIndex), this.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 (this.list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(this.list) : this);
}
}
/**
* @serial include
*/
static class SynchronizedRandomAccessList extends SynchronizedList implements RandomAccess {
SynchronizedRandomAccessList(List list) {
super(list);
}
SynchronizedRandomAccessList(List list, Object mutex) {
super(list, mutex);
}
@Override
public List subList(int fromIndex, int toIndex) {
synchronized (this.mutex) {
return new SynchronizedRandomAccessList<>(this.list.subList(fromIndex, toIndex), this.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<>(this.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;
this.mutex = this;
}
SynchronizedMap(Map m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
@Override
public int size() {
synchronized (this.mutex) {
return this.m.size();
}
}
@Override
public boolean isEmpty() {
synchronized (this.mutex) {
return this.m.isEmpty();
}
}
@Override
public boolean containsKey(Object key) {
synchronized (this.mutex) {
return this.m.containsKey(key);
}
}
@Override
public boolean containsValue(Object value) {
synchronized (this.mutex) {
return this.m.containsValue(value);
}
}
@Override
@Nullable
public V get(Object key) {
synchronized (this.mutex) {
return this.m.get(key);
}
}
@Override
@Nullable
public V put(K key, V value) {
synchronized (this.mutex) {
return this.m.put(key, value);
}
}
@Override
@Nullable
public V remove(Object key) {
synchronized (this.mutex) {
return this.m.remove(key);
}
}
@Override
public void putAll(Map map) {
synchronized (this.mutex) {
this.m.putAll(map);
}
}
@Override
public void clear() {
synchronized (this.mutex) {
this.m.clear();
}
}
@Nullable
private transient Set keySet = null;
@Nullable
private transient Set> entrySet = null;
@Nullable
private transient Collection values = null;
@Override
public Set keySet() {
synchronized (this.mutex) {
if (this.keySet == null) {
this.keySet = new SynchronizedSet<>(this.m.keySet(), this.mutex);
}
return this.keySet;
}
}
@Override
public Set> entrySet() {
synchronized (this.mutex) {
if (this.entrySet == null) {
this.entrySet = new SynchronizedSet<>(this.m.entrySet(), this.mutex);
}
return this.entrySet;
}
}
@Override
public Collection values() {
synchronized (this.mutex) {
if (this.values == null) {
this.values = new SynchronizedCollection<>(this.m.values(), this.mutex);
}
return this.values;
}
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
synchronized (this.mutex) {
return this.m.equals(o);
}
}
@Override
public int hashCode() {
synchronized (this.mutex) {
return this.m.hashCode();
}
}
@Override
public String toString() {
synchronized (this.mutex) {
return this.m.toString();
}
}
}
/**
* 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);
this.sm = m;
}
SynchronizedSortedMap(SortedMap m, Object mutex) {
super(m, mutex);
this.sm = m;
}
@Override
@Nullable
public Comparator comparator() {
synchronized (this.mutex) {
return this.sm.comparator();
}
}
@Override
public SortedMap subMap(K fromKey, K toKey) {
synchronized (this.mutex) {
return new SynchronizedSortedMap<>(this.sm.subMap(fromKey, toKey), this.mutex);
}
}
@Override
public SortedMap headMap(K toKey) {
synchronized (this.mutex) {
return new SynchronizedSortedMap<>(this.sm.headMap(toKey), this.mutex);
}
}
@Override
public SortedMap tailMap(K fromKey) {
synchronized (this.mutex) {
return new SynchronizedSortedMap<>(this.sm.tailMap(fromKey), this.mutex);
}
}
@Override
public K firstKey() {
synchronized (this.mutex) {
return this.sm.firstKey();
}
}
@Override
public K lastKey() {
synchronized (this.mutex) {
return this.sm.lastKey();
}
}
}
// Dynamically typesafe collection wrappers
// 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