package java.util;
import java.io.Serializable;public class Collections {
// Suppresses default constructor, ensuring non-instantiability.
private Collections() {
} 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; 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(a[j]);
}
} public static void sort(List list, Comparator c) {
Object a[] = list.toArray();
Arrays.sort(a, c);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set(a[j]);
}
}
public static int binarySearch(List list, Object key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return indexedBinarySearch(list, key);
else
return iteratorBinarySearch(list, key);
} private static int indexedBinarySearch(List list, Object key) {
int low = 0;
int high = list.size()-1; while (low <= high) {
int mid = (low + high) >> 1;
Object midVal = list.get(mid);
int cmp = ((Comparable)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, Object key) {
int low = 0;
int high = list.size()-1;
ListIterator i = list.listIterator(); while (low <= high) {
int mid = (low + high) >> 1;
Object midVal = get(i, mid);
int cmp = ((Comparable)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 Object get(ListIterator i, int index) {
Object 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;
} public static int binarySearch(List list, Object key, Comparator c) {
if (c==null)
return binarySearch(list, key); if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return indexedBinarySearch(list, key, c);
else
return iteratorBinarySearch(list, key, c);
} private static int indexedBinarySearch(List l, Object key, Comparator c) {
int low = 0;
int high = l.size()-1; while (low <= high) {
int mid = (low + high) >> 1;
Object 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, Object key, Comparator c) {
int low = 0;
int high = l.size()-1;
ListIterator i = l.listIterator(); while (low <= high) {
int mid = (low + high) >> 1;
Object 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
} 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);
}
}
} public static void shuffle(List list) {
shuffle(list, r);
}
private static Random r = new Random(); 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]);
}
}
}
public static void swap(List list, int i, int j) {
list.set(i, list.set(j, list.get(i)));
} private static void swap(Object[] arr, int i, int j) {
Object tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
} public static void fill(List list, Object 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);
}
}
} 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(), si=src.listIterator();
for (int i=0; i<srcSize; i++) {
di.next();
di.set(si.next());
}
}
} public static Object min(Collection coll) {
Iterator i = coll.iterator();
Comparable candidate = (Comparable)(i.next()); while(i.hasNext()) {
Comparable next = (Comparable)(i.next());
if (next.compareTo(candidate) < 0)
candidate = next;
}
return candidate;
} public static Object min(Collection coll, Comparator comp) {
if (comp==null)
return min(coll); Iterator i = coll.iterator();
Object candidate = i.next(); while(i.hasNext()) {
Object next = i.next();
if (comp.compare(next, candidate) < 0)
candidate = next;
}
return candidate;
} public static Object max(Collection coll) {
Iterator i = coll.iterator();
Comparable candidate = (Comparable)(i.next()); while(i.hasNext()) {
Comparable next = (Comparable)(i.next());
if (next.compareTo(candidate) > 0)
candidate = next;
}
return candidate;
} public static Object max(Collection coll, Comparator comp) {
if (comp==null)
return max(coll); Iterator i = coll.iterator();
Object candidate = i.next(); while(i.hasNext()) {
Object next = i.next();
if (comp.compare(next, candidate) > 0)
candidate = next;
}
return candidate;
} 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++) {
Object 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; Collections.reverse(list.subList(0, mid));
Collections.reverse(list.subList(mid, size));
Collections.reverse(list);
} public static boolean replaceAll(List list, Object oldVal, Object 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;
} 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
}
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
}
public static Collection unmodifiableCollection(Collection c) {
return new UnmodifiableCollection(c);
} static class UnmodifiableCollection implements Collection, Serializable {
// use serialVersionUID from JDK 1.2.2 for interoperability
private static final long serialVersionUID = 1820017752578914078L; 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 Object[] toArray(Object[] a) {return c.toArray(a);}
public String toString() {return c.toString();} public Iterator iterator() {
return new Iterator() {
Iterator i = c.iterator(); public boolean hasNext() {return i.hasNext();}
public Object next() {return i.next();}
public void remove() {
throw new UnsupportedOperationException();
}
};
} public boolean add(Object o){
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();
}
}
public static Set unmodifiableSet(Set s) {
return new UnmodifiableSet(s);
} /**
* @serial include
*/
static class UnmodifiableSet extends UnmodifiableCollection
implements Set, Serializable {
UnmodifiableSet(Set s) {super(s);} public boolean equals(Object o) {return c.equals(o);}
public int hashCode() {return c.hashCode();}
} public static SortedSet unmodifiableSortedSet(SortedSet s) {
return new UnmodifiableSortedSet(s);
} /**
* @serial include
*/
static class UnmodifiableSortedSet extends UnmodifiableSet
implements SortedSet, Serializable {
private SortedSet ss; UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;} public Comparator comparator() {return ss.comparator();} public SortedSet subSet(Object fromElement, Object toElement) {
return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement));
}
public SortedSet headSet(Object toElement) {
return new UnmodifiableSortedSet(ss.headSet(toElement));
}
public SortedSet tailSet(Object fromElement) {
return new UnmodifiableSortedSet(ss.tailSet(fromElement));
} public Object first() {return ss.first();}
public Object last() {return ss.last();}
} public static List unmodifiableList(List list) {
return (list instanceof RandomAccess ?
new UnmodifiableRandomAccessList(list) :
new UnmodifiableList(list));
} static class UnmodifiableList extends UnmodifiableCollection
implements List {
static final long serialVersionUID = -283967356065247728L;
List list; UnmodifiableList(List list) {
super(list);
this.list = list;
} public boolean equals(Object o) {return list.equals(o);}
public int hashCode() {return list.hashCode();} public Object get(int index) {return list.get(index);}
public Object set(int index, Object element) {
throw new UnsupportedOperationException();
}
public void add(int index, Object element) {
throw new UnsupportedOperationException();
}
public Object 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() {
ListIterator i = list.listIterator(index); public boolean hasNext() {return i.hasNext();}
public Object next() {return i.next();}
public boolean hasPrevious() {return i.hasPrevious();}
public Object 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(Object o) {
throw new UnsupportedOperationException();
}
public void add(Object o) {
throw new UnsupportedOperationException();
}
};
} public List subList(int fromIndex, int toIndex) {
return new UnmodifiableList(list.subList(fromIndex, toIndex));
} private Object readResolve() {
return (list instanceof RandomAccess ?
new UnmodifiableRandomAccessList(list) : this);
}
}