コレクションのソースコード
44285 ワード
Collection類は主に二つの主要機能を完成しました。 1.いくつかの簡単で有用なアルゴリズムを提供しています。例えば、並べ替え、二分検索、最大最小値を求めるなどです。 2.集合を包装する静的方法を提供する。例えば指定された集合をスレッド安全の集合に包装したり、修正不可の集合に包装したり、安全な型の集合に包装したりする。
package Java.util;
import java.io.Serializable;
import java.io.ObjectOutputStream;
import java.io.IOException;
import java.lang.reflect.Array;
public class Collections {
// Suppresses default constructor, ensuring non-instantiability.
private Collections() {
}
//
/*
*
* 。 List , List, 。
*/
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;
/**
*
* List Compareable , 。
*
* : List , , List ,
*/
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]);
//
}
}
/**
* Comparator 。 c.compare(o1,o2);
*/
public static void sort(List list, Comparator super T> 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]);
}
}
/**
*
* List key。 List 。 List key, key 。
* List ,
*
* , O(log(n)), 1024 log2(1024)=10 ,
* log2(n) , 10
* , O(n), O(log(n))
*
* @return 。 ,
* key , ( key )。 :point = -i - 1
*
*/
public static int binarySearch(List extends Comparable super T>> list, T key) {
if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
/**
* 。 size 5000
*/
private static int indexedBinarySearch(List extends Comparable super T>> list, T key) {
int low = 0; //
int high = list.size() - 1;
//
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable super T> 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 extends Comparable super T>> list, T key) {
int low = 0;
int high = list.size() - 1;
ListIterator extends Comparable super T>> i = list.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable super T> 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
}
private static T get(ListIterator extends T> 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;
}
/**
* Comparator
*/
public static int binarySearch(List extends T> list, T key, Comparator super T> 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 extends T> l, T key, Comparator super T> 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 extends T> l, T key, Comparator super T> c) {
int low = 0;
int high = l.size() - 1;
ListIterator extends T> 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 {
}
/**
*
*
*/
public static void reverse(List> list) {
int size = list.size();
// size 18
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); // 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) {
if (r == null) {
r = new Random();
}
shuffle(list, r);
}
private static Random r;
/**
*
* List
*
* : list, , 。
*
* list size>5, List , , List 。
*
*/
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--) // i-1
swap(list, i - 1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray(); //
//
for (int i = size; i > 1; i--)
swap(arr, i - 1, rnd.nextInt(i));
// List
ListIterator it = list.listIterator();
for (int i = 0; i < arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
/**
* List
*/
public static void swap(List> list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
// i j
}
/**
* 。
*/
private static void swap(Object[] arr, int i, int j) {
Object tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
*
* obj List
*/
public static void fill(List super T> 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 super T> itr = list.listIterator();
for (int i = 0; i < size; i++) {
itr.next();
itr.set(obj);
}
}
}
/**
*
* , src.size > dest.size src.size < dest.size
* dest
*/
public static void copy(List super T> dest, List extends T> 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 super T> di = dest.listIterator();
ListIterator extends T> si = src.listIterator();
for (int i = 0; i < srcSize; i++) {
di.next();
di.set(si.next());
}
}
}
/**
*
* 。 , Comparable , 。
* ,
*/
public static > T min(Collection extends T> coll) {
Iterator extends T> i = coll.iterator();
T candidate = i.next();
while (i.hasNext()) {
T next = i.next();
if (next.compareTo(candidate) < 0)
candidate = next;
}
return candidate;
}
/**
*
*/
public static T min(Collection extends T> coll, Comparator super T> comp) {
if (comp == null)
// , , Comparable ,
// ClassCastException
return (T) min((Collection) (Collection) coll);
Iterator extends T> i = coll.iterator();
T candidate = i.next();
//
while (i.hasNext()) {
T next = i.next();
if (comp.compare(next, candidate) < 0)
candidate = next;
}
return candidate;
}
/**
*
*/
public static > T max(Collection extends T> coll) {
Iterator extends T> i = coll.iterator();
T candidate = i.next();
while (i.hasNext()) {
T next = i.next();
if (next.compareTo(candidate) > 0)
candidate = next;
}
return candidate;
}
/**
*
*/
public static T max(Collection extends T> coll, Comparator super T> comp) {
if (comp == null)
return (T) max((Collection) (Collection) coll);
Iterator extends T> i = coll.iterator();
T candidate = i.next();
while (i.hasNext()) {
T next = i.next();
if (comp.compare(next, candidate) > 0)
candidate = next;
}
return candidate;
}
/**
*
* List distance。 : (i +
* distance)%list.size.
*
* , : [t, a, n, k, s , w] Collections.rotate(list, 2)
* Collections.rotate(list, -4) , list [s, w, t, a, n ,
* k]。 : ,
*
*/
public static void rotate(List> list, int distance) {
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1((List) list, distance);
else
rotate2((List) list, distance);
}
private static void rotate1(List list, int distance) {
int size = list.size();
if (size == 0)
return;
distance = distance % size; // distance 0 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; // size size
displaced = list.set(i, displaced);
//
nMoved++; // size
} 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);
}
/**
*
* oladVal newVal list true
*/
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;
}
/**
*
* target source , target , -1。
* 。 。
*
*/
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; // ,
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())) {
// ,
for (int j = 0; j < i; j++)
si.previous();
continue nextCand;
}
}
return candidate;
}
}
return -1; // -1
}
/**
* ,
*/
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)))
// source maxCandidate 。 maxCandidate-1,
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
/**
*
* 。 UnsupportedOperationException
*
* Collection equals equals
* Object equals 。hashCode 。 Set List equals 。
*/
public static Collection unmodifiableCollection(Collection extends T> 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;
final Collection extends E> c;
UnmodifiableCollection(Collection extends E> 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() {
Iterator extends E> 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 extends E> 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();
}
}
/**
* Set。 equals
*/
public static Set unmodifiableSet(Set extends T> s) {
return new UnmodifiableSet(s);
}
/**
* @serial include
*/
static class UnmodifiableSet extends UnmodifiableCollection implements Set, Serializable {
private static final long serialVersionUID = -9215047833775013803L;
UnmodifiableSet(Set extends E> s) {
super(s);
}
public boolean equals(Object o) {
return o == this || c.equals(o);
}
public int hashCode() {
return c.hashCode();
}
}
/**
* Sort Set
*/
public static SortedSet unmodifiableSortedSet(SortedSet s) {
return new UnmodifiableSortedSet(s);
}
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 super E> 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();
}
}
/**
* List List RandomAccess , List
*/
public static List unmodifiableList(List extends T> list) {
return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList(list)
: new UnmodifiableList(list));
}
static class UnmodifiableList extends UnmodifiableCollection implements List {
static final long serialVersionUID = -283967356065247728L;
final List extends E> list;
UnmodifiableList(List extends E> 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 extends E> c) {
throw new UnsupportedOperationException();
}
public ListIterator listIterator() {
return listIterator(0);
}
public ListIterator listIterator(final int index) {
return new ListIterator() {
ListIterator extends E> 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);
}
}
static class UnmodifiableRandomAccessList extends UnmodifiableList implements RandomAccess {
UnmodifiableRandomAccessList(List extends E> 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);
}
}
/**
* map
*/
public static Map unmodifiableMap(Map extends K, ? extends V> m) {
return new UnmodifiableMap(m);
}
private static class UnmodifiableMap implements Map, Serializable {
// use serialVersionUID from JDK 1.2.2 for interoperability
private static final long serialVersionUID = -1034234728574286014L;
private final Map extends K, ? extends V> m;
UnmodifiableMap(Map extends K, ? extends V> 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 extends K, ? extends V> 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;
// key
public Set keySet() {
if (keySet == null)
keySet = unmodifiableSet(m.keySet());
return keySet;
}
// EntrySet
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();
}
/**
*
* EntrySet
*/
static class UnmodifiableEntrySet extends UnmodifiableSet> {
private static final long serialVersionUID = 7854390611657943733L;
UnmodifiableEntrySet(Set extends Map.Entry extends K, ? extends V>> s) {
super((Set) s);
}
public Iterator> iterator() {
return new Iterator>() {
// UnmodifiableColletion c
Iterator extends Map.Entry extends K, ? extends V>> i = c.iterator();
public boolean hasNext() {
return i.hasNext();
}
public Map.Entry next() {
return new UnmodifiableEntry(i.next());
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
public Object[] toArray() {
Object[] a = c.toArray();
for (int i = 0; i < a.length; i++)
a[i] = new UnmodifiableEntry((Map.Entry) a[i]);
return a;
}
public T[] toArray(T[] a) {
Object[] arr = c.toArray(a.length == 0 ? a : Arrays.copyOf(a, 0));
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;
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
return c.contains(new UnmodifiableEntry((Map.Entry) o));
}
public boolean containsAll(Collection> coll) {
Iterator> e = coll.iterator();
while (e.hasNext())
if (!contains(e.next())) // 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
}
/**
* Entry。
*/
private static class UnmodifiableEntry implements Map.Entry {
private Map.Entry extends K, ? extends V> e;
UnmodifiableEntry(Map.Entry extends K, ? extends V> e) {
this.e = e;
}
public K getKey() {
return e.getKey();
}
public V getValue() {
return e.getValue();
}
public V setValue(V value) { // set
throw new UnsupportedOperationException();
}
public int hashCode() {
return e.hashCode();
}
public boolean equals(Object o) {
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();
}
}
}
}
/**
* SortedMap
*/
public static SortedMap unmodifiableSortedMap(SortedMap m) {
return new UnmodifiableSortedMap(m);
}
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 super K> 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();
}
}
//
/**
*
* , Collection c =
* Collections.synchronizedCollection(myCollection); ... synchronized(c) {
* Iterator i = c.iterator(); // Must be in the synchronized block while
* (i.hasNext()) foo(i.next()); }
*
*/
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 {
// use serialVersionUID from JDK 1.2.2 for interoperability
private static final long serialVersionUID = 3053995032091335093L;
final Collection c; //
final Object mutex; //
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(); //
}
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 extends E> 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();
}
}
}
/**
* 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) {
synchronized (mutex) {
return c.equals(o);
}
}
public int hashCode() {
synchronized (mutex) {
return c.hashCode();
}
}
}
/**
* SortedSet
*/
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;
final private SortedSet ss;
SynchronizedSortedSet(SortedSet s) {
super(s);
ss = s;
}
SynchronizedSortedSet(SortedSet s, Object mutex) {
super(s, mutex);
ss = s;
}
public Comparator super E> 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();
}
}
}
/**
* List, List , List RandomAccess
*/
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 {
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) {
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 extends E> 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);
}
}
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);
}
}
static final long serialVersionUID = 1530674583602358482L;
private Object writeReplace() {
return new SynchronizedList(list);
}
}
/**
* map
*/
public static Map synchronizedMap(Map m) {
return new SynchronizedMap(m);
}
/**
* @serial include
*/
private static class SynchronizedMap implements Map, Serializable {
// use serialVersionUID from JDK 1.2.2 for interoperability
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 extends K, ? extends V> 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) {
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();
}
}
}
/**
* SortedSet
*/
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 super K> 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
/**
*
* 。 ClassCastException
* debug , 。 :ArrayList strings =
* new ArrayList(); ArrayList rawList = strings; rawList.add(new
* Date()); add , String 。 String 。
* add ClassCastException。
*
*
*/
public static Collection checkedCollection(Collection c, Class type) {
return new CheckedCollection(c, type);
}
/**
* @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 (!type.isInstance(o)) // o type
throw new ClassCastException(
"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 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 void clear() {
c.clear();
}
public Iterator iterator() {
return new Iterator() {
private final Iterator it = c.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);
}
public boolean addAll(Collection extends E> coll) {
E[] a = null;
try {
a = coll.toArray(zeroLengthElementArray());
// zero 。 coll
} catch (ArrayStoreException e) {
throw new ClassCastException();
}
boolean result = false;
for (E e : a)
result |= c.add(e); // true
return result;
}
private E[] zeroLengthElementArray = null; // Lazily initialized
/*
* We don't need locking or volatile, because it's OK if we create
* several zeroLengthElementArrays, and they're immutable.
*/
E[] zeroLengthElementArray() {
if (zeroLengthElementArray == null)
zeroLengthElementArray = (E[]) Array.newInstance(type, 0);
return zeroLengthElementArray;
}
}
/**
* Set
*/
public static Set checkedSet(Set s, Class type) {
return new CheckedSet(s, type);
}
/**
* @serial include
*/
static class CheckedSet extends CheckedCollection