--- jsr166/src/main/java/util/Collections.java 2005/12/05 02:56:59 1.18 +++ jsr166/src/main/java/util/Collections.java 2008/05/18 23:59:57 1.34 @@ -1,12 +1,29 @@ /* - * %W% %E% + * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * - * Copyright 2006 Sun Microsystems, Inc. All rights reserved. - * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + * 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. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. */ package java.util; -import java.util.*; // for javadoc (till 6280605 is fixed) import java.io.Serializable; import java.io.ObjectOutputStream; import java.io.IOException; @@ -39,16 +56,15 @@ import java.lang.reflect.Array; * already sorted may or may not throw UnsupportedOperationException. * *

This class is a member of the - * + * * Java Collections Framework. * * @author Josh Bloch * @author Neal Gafter - * @version %I%, %G% - * @see Collection - * @see Set - * @see List - * @see Map + * @see Collection + * @see Set + * @see List + * @see Map * @since 1.2 */ @@ -108,19 +124,19 @@ public class Collections { * * @param list the list to be sorted. * @throws ClassCastException if the list contains elements that are not - * mutually comparable (for example, strings and integers). + * mutually comparable (for example, strings and integers). * @throws UnsupportedOperationException if the specified list's - * list-iterator does not support the set operation. + * list-iterator does not support the set operation. * @see Comparable */ public static > void sort(List list) { - Object[] a = list.toArray(); - Arrays.sort(a); - ListIterator i = list.listIterator(); - for (int j=0; j i = list.listIterator(); + for (int j=0; jnull 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. + * mutually comparable using the specified comparator. * @throws UnsupportedOperationException if the specified list's - * list-iterator does not support the set operation. + * list-iterator does not support the set operation. * @see Comparator */ public static void sort(List list, Comparator c) { - Object[] a = list.toArray(); - Arrays.sort(a, (Comparator)c); - ListIterator i = list.listIterator(); - for (int j=0; jnatural ordering of its elements (as by the - * sort(List) method, above) 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.

+ * 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 + *

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 @@ -184,19 +200,17 @@ public class Collections { * @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. + * 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 in not mutually comparable - * with the elements of the list. - * @see Comparable - * @see #sort(List) + * 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) { @@ -209,33 +223,33 @@ public class Collections { private static int indexedBinarySearch(List> list, T key) { - int low = 0; - int high = list.size()-1; + 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); - 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 + 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; + int low = 0; + int high = list.size()-1; ListIterator> i = list.listIterator(); while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; Comparable midVal = get(i, mid); int cmp = midVal.compareTo(key); @@ -254,7 +268,7 @@ public class Collections { * list listIterator. */ private static T get(ListIterator i, int index) { - T obj = null; + T obj = null; int pos = i.nextIndex(); if (pos <= index) { do { @@ -271,13 +285,14 @@ public class Collections { /** * 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 Sort(List, - * Comparator) method, above), prior to making this call. If it is + * 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.

+ * will be found. * - * This method runs in log(n) time for a "random access" list (which + *

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 @@ -285,23 +300,21 @@ public class Collections { * * @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' natural - * ordering should be used. + * @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. + * 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 in not mutually comparable with the - * elements of the list using this comparator. - * @see Comparable - * @see #sort(List, Comparator) + * 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, Comparator c) { if (c==null) @@ -314,31 +327,31 @@ public class Collections { } private static int indexedBinarySearch(List l, T key, Comparator c) { - int low = 0; - int high = l.size()-1; + 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); - 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 + 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; + int low = 0; + int high = l.size()-1; ListIterator i = l.listIterator(); while (low <= high) { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; T midVal = get(i, mid); int cmp = c.compare(midVal, key); @@ -373,7 +386,7 @@ public class Collections { ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size); for (int i=0, mid=list.size()>>1; i list, int i, int j) { - final List l = list; - l.set(i, l.set(j, l.get(i))); + final List l = list; + l.set(i, l.set(j, l.get(i))); } /** @@ -496,7 +509,7 @@ public class Collections { * @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. + * list-iterator does not support the set operation. */ public static void fill(List list, T obj) { int size = list.size(); @@ -540,7 +553,7 @@ public class Collections { dest.set(i, src.get(i)); } else { ListIterator di=dest.listIterator(); - ListIterator si=src.listIterator(); + ListIterator si=src.listIterator(); for (int i=0; inatural ordering of its elements. * @throws ClassCastException if the collection contains elements that are - * not mutually comparable (for example, strings and - * integers). + * 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(); + Iterator i = coll.iterator(); + T candidate = i.next(); while (i.hasNext()) { - T next = i.next(); - if (next.compareTo(candidate) < 0) - candidate = next; - } - return candidate; + T next = i.next(); + if (next.compareTo(candidate) < 0) + candidate = next; + } + return candidate; } /** @@ -599,7 +612,7 @@ public class Collections { * @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. + * not mutually comparable using the specified comparator. * @throws NoSuchElementException if the collection is empty. * @see Comparable */ @@ -607,15 +620,15 @@ public class Collections { if (comp==null) return (T)min((Collection) (Collection) coll); - Iterator i = coll.iterator(); - T candidate = i.next(); + 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; + T next = i.next(); + if (comp.compare(next, candidate) < 0) + candidate = next; + } + return candidate; } /** @@ -634,21 +647,21 @@ public class Collections { * @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 + * 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(); + Iterator i = coll.iterator(); + T candidate = i.next(); while (i.hasNext()) { - T next = i.next(); - if (next.compareTo(candidate) > 0) - candidate = next; - } - return candidate; + T next = i.next(); + if (next.compareTo(candidate) > 0) + candidate = next; + } + return candidate; } /** @@ -669,7 +682,7 @@ public class Collections { * @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. + * not mutually comparable using the specified comparator. * @throws NoSuchElementException if the collection is empty. * @see Comparable */ @@ -677,15 +690,15 @@ public class Collections { if (comp==null) return (T)max((Collection) (Collection) coll); - Iterator i = coll.iterator(); - T candidate = i.next(); + 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; + T next = i.next(); + if (comp.compare(next, candidate) > 0) + candidate = next; + } + return candidate; } /** @@ -745,9 +758,9 @@ public class Collections { */ public static void rotate(List list, int distance) { if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) - rotate1((List)list, distance); + rotate1(list, distance); else - rotate2((List)list, distance); + rotate2(list, distance); } private static void rotate1(List list, int distance) { @@ -977,68 +990,67 @@ public class Collections { * is serializable. * * @param c the collection for which an unmodifiable view is to be - * returned. + * returned. * @return an unmodifiable view of the specified collection. */ public static Collection unmodifiableCollection(Collection c) { - return new UnmodifiableCollection(c); + return new UnmodifiableCollection(c); } /** * @serial include */ static class UnmodifiableCollection implements Collection, Serializable { - // use serialVersionUID from JDK 1.2.2 for interoperability - private static final long serialVersionUID = 1820017752578914078L; + private static final long serialVersionUID = 1820017752578914078L; - final Collection c; + final Collection c; - UnmodifiableCollection(Collection c) { + UnmodifiableCollection(Collection c) { if (c==null) throw new NullPointerException(); this.c = c; } - public int size() {return c.size();} - public boolean isEmpty() {return c.isEmpty();} - public boolean contains(Object o) {return c.contains(o);} - public Object[] toArray() {return c.toArray();} - public T[] toArray(T[] a) {return c.toArray(a);} + public 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 i = c.iterator(); - - public boolean hasNext() {return i.hasNext();} - public E next() {return i.next();} - public void remove() { - throw new UnsupportedOperationException(); + public Iterator iterator() { + return new Iterator() { + private final Iterator i = c.iterator(); + + public boolean hasNext() {return i.hasNext();} + public E next() {return i.next();} + public void remove() { + throw new UnsupportedOperationException(); } - }; + }; } - public boolean add(E e){ - throw new UnsupportedOperationException(); + public boolean add(E e) { + throw new UnsupportedOperationException(); } - public boolean remove(Object o) { - throw new UnsupportedOperationException(); + public boolean remove(Object o) { + throw new UnsupportedOperationException(); } - public boolean containsAll(Collection coll) { - return c.containsAll(coll); + public boolean containsAll(Collection coll) { + return c.containsAll(coll); } - public boolean addAll(Collection coll) { - throw new UnsupportedOperationException(); + public boolean addAll(Collection coll) { + throw new UnsupportedOperationException(); } - public boolean removeAll(Collection coll) { - throw new UnsupportedOperationException(); + public boolean removeAll(Collection coll) { + throw new UnsupportedOperationException(); } - public boolean retainAll(Collection coll) { - throw new UnsupportedOperationException(); + public boolean retainAll(Collection coll) { + throw new UnsupportedOperationException(); } - public void clear() { - throw new UnsupportedOperationException(); + public void clear() { + throw new UnsupportedOperationException(); } } @@ -1056,19 +1068,19 @@ public class Collections { * @return an unmodifiable view of the specified set. */ public static Set unmodifiableSet(Set s) { - return new UnmodifiableSet(s); + return new UnmodifiableSet(s); } /** * @serial include */ static class UnmodifiableSet extends UnmodifiableCollection - implements Set, Serializable { - private static final long serialVersionUID = -9215047833775013803L; + implements Set, Serializable { + private static final long serialVersionUID = -9215047833775013803L; - UnmodifiableSet(Set s) {super(s);} - public boolean equals(Object o) {return c.equals(o);} - public int hashCode() {return c.hashCode();} + UnmodifiableSet(Set s) {super(s);} + public boolean equals(Object o) {return o == this || c.equals(o);} + public int hashCode() {return c.hashCode();} } /** @@ -1088,19 +1100,19 @@ public class Collections { * @return an unmodifiable view of the specified sorted set. */ public static SortedSet unmodifiableSortedSet(SortedSet s) { - return new UnmodifiableSortedSet(s); + return new UnmodifiableSortedSet(s); } /** * @serial include */ static class UnmodifiableSortedSet - extends UnmodifiableSet - implements SortedSet, Serializable { - private static final long serialVersionUID = -4929149591599911165L; + extends UnmodifiableSet + implements SortedSet, Serializable { + private static final long serialVersionUID = -4929149591599911165L; private final SortedSet ss; - UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;} + UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;} public Comparator comparator() {return ss.comparator();} @@ -1114,8 +1126,8 @@ public class Collections { return new UnmodifiableSortedSet(ss.tailSet(fromElement)); } - public E first() {return ss.first();} - public E last() {return ss.last();} + public E first() {return ss.first();} + public E last() {return ss.last();} } /** @@ -1134,7 +1146,7 @@ public class Collections { * @return an unmodifiable view of the specified list. */ public static List unmodifiableList(List list) { - return (list instanceof RandomAccess ? + return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList(list) : new UnmodifiableList(list)); } @@ -1143,59 +1155,60 @@ public class Collections { * @serial include */ static class UnmodifiableList extends UnmodifiableCollection - implements List { - static final long serialVersionUID = -283967356065247728L; - final 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 E get(int index) {return list.get(index);} - public E set(int index, E element) { - throw new UnsupportedOperationException(); - } - public void add(int index, E element) { - throw new UnsupportedOperationException(); - } - public E remove(int index) { - throw new UnsupportedOperationException(); - } - public int indexOf(Object o) {return list.indexOf(o);} - public int lastIndexOf(Object o) {return list.lastIndexOf(o);} - public boolean addAll(int index, Collection c) { - throw new UnsupportedOperationException(); - } - public ListIterator listIterator() {return listIterator(0);} - - public ListIterator listIterator(final int index) { - return new ListIterator() { - ListIterator i = list.listIterator(index); - - public boolean hasNext() {return i.hasNext();} - public E next() {return i.next();} - public boolean hasPrevious() {return i.hasPrevious();} - public E previous() {return i.previous();} - public int nextIndex() {return i.nextIndex();} - public int previousIndex() {return i.previousIndex();} + implements List { + private static final long serialVersionUID = -283967356065247728L; + final List list; + + UnmodifiableList(List list) { + super(list); + this.list = list; + } - public void remove() { - throw new UnsupportedOperationException(); + public boolean equals(Object o) {return o == this || list.equals(o);} + public int hashCode() {return list.hashCode();} + + public E get(int index) {return list.get(index);} + public E set(int index, E element) { + throw new UnsupportedOperationException(); + } + public void add(int index, E element) { + throw new UnsupportedOperationException(); + } + public E remove(int index) { + throw new UnsupportedOperationException(); + } + public int indexOf(Object o) {return list.indexOf(o);} + public int lastIndexOf(Object o) {return list.lastIndexOf(o);} + public boolean addAll(int index, Collection c) { + throw new UnsupportedOperationException(); + } + public ListIterator listIterator() {return listIterator(0);} + + public ListIterator listIterator(final int index) { + return new ListIterator() { + private final ListIterator i + = list.listIterator(index); + + public boolean hasNext() {return i.hasNext();} + public E next() {return i.next();} + public boolean hasPrevious() {return i.hasPrevious();} + public E previous() {return i.previous();} + public int nextIndex() {return i.nextIndex();} + public int previousIndex() {return i.previousIndex();} + + public void remove() { + throw new UnsupportedOperationException(); } - public void set(E e) { - throw new UnsupportedOperationException(); + public void set(E e) { + throw new UnsupportedOperationException(); } - public void add(E e) { - throw new UnsupportedOperationException(); + public void add(E e) { + throw new UnsupportedOperationException(); } - }; - } + }; + } - public List subList(int fromIndex, int toIndex) { + public List subList(int fromIndex, int toIndex) { return new UnmodifiableList(list.subList(fromIndex, toIndex)); } @@ -1213,8 +1226,8 @@ public class Collections { */ private Object readResolve() { return (list instanceof RandomAccess - ? new UnmodifiableRandomAccessList(list) - : this); + ? new UnmodifiableRandomAccessList(list) + : this); } } @@ -1228,7 +1241,7 @@ public class Collections { super(list); } - public List subList(int fromIndex, int toIndex) { + public List subList(int fromIndex, int toIndex) { return new UnmodifiableRandomAccessList( list.subList(fromIndex, toIndex)); } @@ -1261,67 +1274,66 @@ public class Collections { * @return an unmodifiable view of the specified map. */ public static Map unmodifiableMap(Map m) { - return new UnmodifiableMap(m); + return new UnmodifiableMap(m); } /** * @serial include */ private static class UnmodifiableMap implements Map, Serializable { - // use serialVersionUID from JDK 1.2.2 for interoperability - private static final long serialVersionUID = -1034234728574286014L; + private static final long serialVersionUID = -1034234728574286014L; - private final Map m; + private final Map m; - UnmodifiableMap(Map m) { + UnmodifiableMap(Map m) { if (m==null) throw new NullPointerException(); this.m = m; } - public int size() {return m.size();} - public boolean isEmpty() {return m.isEmpty();} - public boolean containsKey(Object key) {return m.containsKey(key);} - public boolean containsValue(Object val) {return m.containsValue(val);} - public V get(Object key) {return m.get(key);} - - public V put(K key, V value) { - throw new UnsupportedOperationException(); - } - public V remove(Object key) { - throw new UnsupportedOperationException(); - } - public void putAll(Map m) { - throw new UnsupportedOperationException(); - } - public void clear() { - throw new UnsupportedOperationException(); - } - - private transient Set keySet = null; - private transient Set> entrySet = null; - private transient Collection values = null; - - public Set keySet() { - if (keySet==null) - keySet = unmodifiableSet(m.keySet()); - return keySet; - } - - public Set> entrySet() { - if (entrySet==null) - entrySet = new UnmodifiableEntrySet(m.entrySet()); - return entrySet; - } - - public Collection values() { - if (values==null) - values = unmodifiableCollection(m.values()); - return values; - } + public int size() {return m.size();} + public boolean isEmpty() {return m.isEmpty();} + public boolean containsKey(Object key) {return m.containsKey(key);} + public boolean containsValue(Object val) {return m.containsValue(val);} + public V get(Object key) {return m.get(key);} + + public V put(K key, V value) { + throw new UnsupportedOperationException(); + } + public V remove(Object key) { + throw new UnsupportedOperationException(); + } + public void putAll(Map m) { + throw new UnsupportedOperationException(); + } + public void clear() { + throw new UnsupportedOperationException(); + } + + private transient Set keySet = null; + private transient Set> entrySet = null; + private transient Collection values = null; + + public Set keySet() { + if (keySet==null) + keySet = unmodifiableSet(m.keySet()); + return keySet; + } + + public Set> entrySet() { + if (entrySet==null) + entrySet = new UnmodifiableEntrySet(m.entrySet()); + return entrySet; + } + + public Collection values() { + if (values==null) + values = unmodifiableCollection(m.values()); + return values; + } - public boolean equals(Object o) {return m.equals(o);} - public int hashCode() {return m.hashCode();} + public boolean equals(Object o) {return o == this || m.equals(o);} + public int hashCode() {return m.hashCode();} public String toString() {return m.toString();} /** @@ -1333,21 +1345,21 @@ public class Collections { * @serial include */ static class UnmodifiableEntrySet - extends UnmodifiableSet> { - private static final long serialVersionUID = 7854390611657943733L; + extends UnmodifiableSet> { + private static final long serialVersionUID = 7854390611657943733L; UnmodifiableEntrySet(Set> s) { super((Set)s); } public Iterator> iterator() { return new Iterator>() { - Iterator> i = c.iterator(); + private final Iterator> i = c.iterator(); public boolean hasNext() { return i.hasNext(); } - public Map.Entry next() { - return new UnmodifiableEntry(i.next()); + public Map.Entry next() { + return new UnmodifiableEntry(i.next()); } public void remove() { throw new UnsupportedOperationException(); @@ -1366,7 +1378,7 @@ public class Collections { // We don't pass a to c.toArray, to avoid window of // vulnerability wherein an unscrupulous multithreaded client // could get his hands on raw (unwrapped) Entries from c. - Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); + Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); for (int i=0; i((Map.Entry)arr[i]); @@ -1389,7 +1401,8 @@ public class Collections { public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; - return c.contains(new UnmodifiableEntry((Map.Entry) o)); + return c.contains( + new UnmodifiableEntry((Map.Entry) o)); } /** @@ -1428,12 +1441,12 @@ public class Collections { UnmodifiableEntry(Map.Entry e) {this.e = e;} - public K getKey() {return e.getKey();} + public K getKey() {return e.getKey();} public V getValue() {return e.getValue();} public V setValue(V value) { throw new UnsupportedOperationException(); } - public int hashCode() {return e.hashCode();} + public int hashCode() {return e.hashCode();} public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; @@ -1463,20 +1476,20 @@ public class Collections { * @return an unmodifiable view of the specified sorted map. */ public static SortedMap unmodifiableSortedMap(SortedMap m) { - return new UnmodifiableSortedMap(m); + return new UnmodifiableSortedMap(m); } /** * @serial include */ static class UnmodifiableSortedMap - extends UnmodifiableMap - implements SortedMap, Serializable { - private static final long serialVersionUID = -8806743815996713206L; + extends UnmodifiableMap + implements SortedMap, Serializable { + private static final long serialVersionUID = -8806743815996713206L; private final SortedMap sm; - UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;} + UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;} public Comparator comparator() {return sm.comparator();} @@ -1529,81 +1542,80 @@ public class Collections { * @return a synchronized view of the specified collection. */ public static Collection synchronizedCollection(Collection c) { - return new SynchronizedCollection(c); + return new SynchronizedCollection(c); } static Collection synchronizedCollection(Collection c, Object mutex) { - return new SynchronizedCollection(c, 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; + private static final long serialVersionUID = 3053995032091335093L; - final Collection c; // Backing Collection - final Object mutex; // Object on which to synchronize + final Collection c; // Backing Collection + final Object mutex; // Object on which to synchronize - SynchronizedCollection(Collection c) { + SynchronizedCollection(Collection c) { if (c==null) throw new NullPointerException(); - this.c = c; + this.c = c; mutex = this; } - SynchronizedCollection(Collection c, Object mutex) { - this.c = c; + SynchronizedCollection(Collection c, Object mutex) { + this.c = c; this.mutex = mutex; } - public int size() { - synchronized(mutex) {return c.size();} + public int size() { + synchronized(mutex) {return c.size();} } - public boolean isEmpty() { - synchronized(mutex) {return c.isEmpty();} + public boolean isEmpty() { + synchronized(mutex) {return c.isEmpty();} } - public boolean contains(Object o) { - synchronized(mutex) {return c.contains(o);} + public boolean contains(Object o) { + synchronized(mutex) {return c.contains(o);} } - public Object[] toArray() { - synchronized(mutex) {return c.toArray();} + public Object[] toArray() { + synchronized(mutex) {return c.toArray();} } - public T[] toArray(T[] a) { - synchronized(mutex) {return c.toArray(a);} + public T[] toArray(T[] a) { + synchronized(mutex) {return c.toArray(a);} } - public Iterator iterator() { + public Iterator iterator() { return c.iterator(); // Must be manually synched by user! } - public boolean add(E e) { - synchronized(mutex) {return c.add(e);} + public boolean add(E e) { + synchronized(mutex) {return c.add(e);} } - public boolean remove(Object o) { - synchronized(mutex) {return c.remove(o);} + public boolean remove(Object o) { + synchronized(mutex) {return c.remove(o);} } - public boolean containsAll(Collection coll) { - synchronized(mutex) {return c.containsAll(coll);} + public boolean containsAll(Collection coll) { + synchronized(mutex) {return c.containsAll(coll);} } - public boolean addAll(Collection coll) { - synchronized(mutex) {return c.addAll(coll);} + public boolean addAll(Collection coll) { + synchronized(mutex) {return c.addAll(coll);} } - public boolean removeAll(Collection coll) { - synchronized(mutex) {return c.removeAll(coll);} + public boolean removeAll(Collection coll) { + synchronized(mutex) {return c.removeAll(coll);} } - public boolean retainAll(Collection coll) { - synchronized(mutex) {return c.retainAll(coll);} + public boolean retainAll(Collection coll) { + synchronized(mutex) {return c.retainAll(coll);} } - public void clear() { - synchronized(mutex) {c.clear();} + public void clear() { + synchronized(mutex) {c.clear();} } - public String toString() { - synchronized(mutex) {return c.toString();} + public String toString() { + synchronized(mutex) {return c.toString();} } private void writeObject(ObjectOutputStream s) throws IOException { - synchronized(mutex) {s.defaultWriteObject();} + synchronized(mutex) {s.defaultWriteObject();} } } @@ -1633,33 +1645,33 @@ public class Collections { * @return a synchronized view of the specified set. */ public static Set synchronizedSet(Set s) { - return new SynchronizedSet(s); + return new SynchronizedSet(s); } static Set synchronizedSet(Set s, Object mutex) { - return new SynchronizedSet(s, mutex); + return new SynchronizedSet(s, mutex); } /** * @serial include */ static class SynchronizedSet - extends SynchronizedCollection - implements Set { - private static final long serialVersionUID = 487447009682186044L; + extends SynchronizedCollection + implements Set { + private static final long serialVersionUID = 487447009682186044L; - SynchronizedSet(Set s) { + SynchronizedSet(Set s) { super(s); } - SynchronizedSet(Set s, Object mutex) { + SynchronizedSet(Set s, Object mutex) { super(s, mutex); } - public boolean equals(Object o) { - synchronized(mutex) {return c.equals(o);} + public boolean equals(Object o) { + synchronized(mutex) {return c.equals(o);} } - public int hashCode() { - synchronized(mutex) {return c.hashCode();} + public int hashCode() { + synchronized(mutex) {return c.hashCode();} } } @@ -1701,55 +1713,55 @@ public class Collections { * @return a synchronized view of the specified sorted set. */ public static SortedSet synchronizedSortedSet(SortedSet s) { - return new SynchronizedSortedSet(s); + return new SynchronizedSortedSet(s); } /** * @serial include */ static class SynchronizedSortedSet - extends SynchronizedSet - implements SortedSet + extends SynchronizedSet + implements SortedSet { - private static final long serialVersionUID = 8695801310862127406L; + private static final long serialVersionUID = 8695801310862127406L; final private SortedSet ss; - SynchronizedSortedSet(SortedSet s) { + SynchronizedSortedSet(SortedSet s) { super(s); ss = s; } - SynchronizedSortedSet(SortedSet s, Object mutex) { + SynchronizedSortedSet(SortedSet s, Object mutex) { super(s, mutex); ss = s; } - public Comparator comparator() { - synchronized(mutex) {return ss.comparator();} + public Comparator comparator() { + synchronized(mutex) {return ss.comparator();} } public SortedSet subSet(E fromElement, E toElement) { - synchronized(mutex) { + synchronized(mutex) { return new SynchronizedSortedSet( ss.subSet(fromElement, toElement), mutex); } } public SortedSet headSet(E toElement) { - synchronized(mutex) { + synchronized(mutex) { return new SynchronizedSortedSet(ss.headSet(toElement), mutex); } } public SortedSet tailSet(E fromElement) { - synchronized(mutex) { + synchronized(mutex) { return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex); } } public E first() { - synchronized(mutex) {return ss.first();} + synchronized(mutex) {return ss.first();} } public E last() { - synchronized(mutex) {return ss.last();} + synchronized(mutex) {return ss.last();} } } @@ -1779,13 +1791,13 @@ public class Collections { * @return a synchronized view of the specified list. */ public static List synchronizedList(List list) { - return (list instanceof RandomAccess ? + return (list instanceof RandomAccess ? new SynchronizedRandomAccessList(list) : new SynchronizedList(list)); } static List synchronizedList(List list, Object mutex) { - return (list instanceof RandomAccess ? + return (list instanceof RandomAccess ? new SynchronizedRandomAccessList(list, mutex) : new SynchronizedList(list, mutex)); } @@ -1794,62 +1806,62 @@ public class Collections { * @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) { + 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; + this.list = list; } - public boolean equals(Object o) { - synchronized(mutex) {return list.equals(o);} + public boolean equals(Object o) { + synchronized(mutex) {return list.equals(o);} } - public int hashCode() { - synchronized(mutex) {return list.hashCode();} + public int hashCode() { + synchronized(mutex) {return list.hashCode();} } - public E get(int index) { - synchronized(mutex) {return list.get(index);} + 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 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 void add(int index, E element) { + synchronized(mutex) {list.add(index, element);} } - public E remove(int index) { - synchronized(mutex) {return list.remove(index);} + public E remove(int index) { + synchronized(mutex) {return list.remove(index);} } - public int indexOf(Object o) { - synchronized(mutex) {return list.indexOf(o);} + public int indexOf(Object o) { + synchronized(mutex) {return list.indexOf(o);} } - public int lastIndexOf(Object o) { - synchronized(mutex) {return list.lastIndexOf(o);} + public int lastIndexOf(Object o) { + synchronized(mutex) {return list.lastIndexOf(o);} } - public boolean addAll(int index, Collection c) { - synchronized(mutex) {return list.addAll(index, c);} + public boolean addAll(int index, Collection c) { + synchronized(mutex) {return list.addAll(index, c);} } - public ListIterator listIterator() { - return list.listIterator(); // Must be manually synched by user + public ListIterator listIterator() { + 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 ListIterator listIterator(int index) { + return list.listIterator(index); // Must be manually synched by user } - public List subList(int fromIndex, int toIndex) { - synchronized(mutex) { + public List subList(int fromIndex, int toIndex) { + synchronized(mutex) { return new SynchronizedList(list.subList(fromIndex, toIndex), mutex); } @@ -1869,8 +1881,8 @@ public class Collections { */ private Object readResolve() { return (list instanceof RandomAccess - ? new SynchronizedRandomAccessList(list) - : this); + ? new SynchronizedRandomAccessList(list) + : this); } } @@ -1878,25 +1890,25 @@ public class Collections { * @serial include */ static class SynchronizedRandomAccessList - extends SynchronizedList - implements RandomAccess { + extends SynchronizedList + implements RandomAccess { SynchronizedRandomAccessList(List list) { super(list); } - SynchronizedRandomAccessList(List list, Object mutex) { + SynchronizedRandomAccessList(List list, Object mutex) { super(list, mutex); } - public List subList(int fromIndex, int toIndex) { - synchronized(mutex) { + public List subList(int fromIndex, int toIndex) { + synchronized(mutex) { return new SynchronizedRandomAccessList( list.subList(fromIndex, toIndex), mutex); } } - static final long serialVersionUID = 1530674583602358482L; + private static final long serialVersionUID = 1530674583602358482L; /** * Allows instances to be deserialized in pre-1.4 JREs (which do @@ -1937,82 +1949,81 @@ public class Collections { * @return a synchronized view of the specified map. */ public static Map synchronizedMap(Map m) { - return new SynchronizedMap(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; + implements Map, Serializable { + private static final long serialVersionUID = 1978198479659022715L; - private final Map m; // Backing Map - final Object mutex; // Object on which to synchronize + private final Map m; // Backing Map + final Object mutex; // Object on which to synchronize - SynchronizedMap(Map m) { + SynchronizedMap(Map m) { if (m==null) throw new NullPointerException(); this.m = m; mutex = this; } - SynchronizedMap(Map m, Object mutex) { + SynchronizedMap(Map m, Object mutex) { this.m = m; this.mutex = mutex; } - public int size() { - synchronized(mutex) {return m.size();} + public int size() { + synchronized(mutex) {return m.size();} } - public boolean isEmpty(){ - synchronized(mutex) {return m.isEmpty();} + public boolean isEmpty() { + synchronized(mutex) {return m.isEmpty();} } - public boolean containsKey(Object key) { - synchronized(mutex) {return m.containsKey(key);} + public boolean containsKey(Object key) { + synchronized(mutex) {return m.containsKey(key);} } - public boolean containsValue(Object value){ - synchronized(mutex) {return m.containsValue(value);} + public boolean containsValue(Object value) { + synchronized(mutex) {return m.containsValue(value);} } - public V get(Object key) { - synchronized(mutex) {return m.get(key);} + 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 put(K key, V value) { + synchronized(mutex) {return m.put(key, value);} } - public V remove(Object key) { - synchronized(mutex) {return m.remove(key);} + public V remove(Object key) { + synchronized(mutex) {return m.remove(key);} } - public void putAll(Map map) { - synchronized(mutex) {m.putAll(map);} + public void putAll(Map map) { + synchronized(mutex) {m.putAll(map);} + } + public void clear() { + synchronized(mutex) {m.clear();} } - public void clear() { - synchronized(mutex) {m.clear();} - } - private transient Set keySet = null; - private transient Set> entrySet = null; - private transient Collection values = null; + private transient Set keySet = null; + private transient Set> entrySet = null; + private transient Collection values = null; - public Set keySet() { + public Set keySet() { synchronized(mutex) { if (keySet==null) keySet = new SynchronizedSet(m.keySet(), mutex); return keySet; } - } + } - public Set> entrySet() { + public Set> entrySet() { synchronized(mutex) { if (entrySet==null) entrySet = new SynchronizedSet>(m.entrySet(), mutex); return entrySet; } - } + } - public Collection values() { + public Collection values() { synchronized(mutex) { if (values==null) values = new SynchronizedCollection(m.values(), mutex); @@ -2020,17 +2031,17 @@ public class Collections { } } - public boolean equals(Object o) { + public boolean equals(Object o) { synchronized(mutex) {return m.equals(o);} } - public int hashCode() { + public int hashCode() { synchronized(mutex) {return m.hashCode();} } - public String toString() { - synchronized(mutex) {return m.toString();} + public String toString() { + synchronized(mutex) {return m.toString();} } private void writeObject(ObjectOutputStream s) throws IOException { - synchronized(mutex) {s.defaultWriteObject();} + synchronized(mutex) {s.defaultWriteObject();} } } @@ -2077,7 +2088,7 @@ public class Collections { * @return a synchronized view of the specified sorted map. */ public static SortedMap synchronizedSortedMap(SortedMap m) { - return new SynchronizedSortedMap(m); + return new SynchronizedSortedMap(m); } @@ -2085,61 +2096,62 @@ public class Collections { * @serial include */ static class SynchronizedSortedMap - extends SynchronizedMap - implements SortedMap + extends SynchronizedMap + implements SortedMap { - private static final long serialVersionUID = -8798146769416483793L; + private static final long serialVersionUID = -8798146769416483793L; private final SortedMap sm; - SynchronizedSortedMap(SortedMap m) { + SynchronizedSortedMap(SortedMap m) { super(m); sm = m; } - SynchronizedSortedMap(SortedMap m, Object mutex) { + SynchronizedSortedMap(SortedMap m, Object mutex) { super(m, mutex); sm = m; } - public Comparator comparator() { - synchronized(mutex) {return sm.comparator();} + public Comparator comparator() { + synchronized(mutex) {return sm.comparator();} } public SortedMap subMap(K fromKey, K toKey) { - synchronized(mutex) { + synchronized(mutex) { return new SynchronizedSortedMap( sm.subMap(fromKey, toKey), mutex); } } public SortedMap headMap(K toKey) { - synchronized(mutex) { + synchronized(mutex) { return new SynchronizedSortedMap(sm.headMap(toKey), mutex); } } public SortedMap tailMap(K fromKey) { - synchronized(mutex) { + synchronized(mutex) { return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex); } } public K firstKey() { - synchronized(mutex) {return sm.firstKey();} + synchronized(mutex) {return sm.firstKey();} } public K lastKey() { - synchronized(mutex) {return sm.lastKey();} + synchronized(mutex) {return sm.lastKey();} } } // Dynamically typesafe collection wrappers /** - * Returns a dynamically typesafe view of the specified collection. Any - * attempt to insert an element of the wrong type will result in an - * immediate ClassCastException. Assuming a collection contains - * no incorrectly typed elements prior to the time a dynamically typesafe - * view is generated, and that all subsequent access to the collection - * takes place through the view, it is guaranteed that the - * collection cannot contain an incorrectly typed element. + * Returns a dynamically typesafe view of the specified collection. + * Any attempt to insert an element of the wrong type will result in an + * immediate {@link ClassCastException}. Assuming a collection + * contains no incorrectly typed elements prior to the time a + * dynamically typesafe view is generated, and that all subsequent + * access to the collection takes place through the view, it is + * guaranteed that the collection cannot contain an incorrectly + * typed element. * *

The generics mechanism in the language provides compile-time * (static) type checking, but it is possible to defeat this mechanism @@ -2151,7 +2163,7 @@ public class Collections { * inserting an element of the wrong type. * *

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

-     *     Collection<String> c = new HashSet<String>();
-     *
+ * 
 {@code
+     *     Collection c = new HashSet();
+     * }
* may be replaced temporarily by this one: - * 
-     *     Collection<String> c = Collections.checkedCollection(
-     *         new HashSet<String>(), String.class);
-     *
+ * 
 {@code
+     *     Collection c = Collections.checkedCollection(
+     *         new HashSet(), String.class);
+     * }
* Running the program again will cause it to fail at the point where * an incorrectly typed element is inserted into the collection, clearly * identifying the source of the problem. Once the problem is fixed, the @@ -2174,16 +2186,20 @@ public class Collections { * *

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 + * {@code Object}'s {@code equals} and {@code hashCode} methods. This * is necessary to preserve the contracts of these operations in the case * that the backing collection is a set or a list. * *

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

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

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

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

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

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

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

Since {@code null} is considered to be a value of any reference + * type, the returned sorted set permits insertion of null elements + * whenever the backing sorted set does. + * * @param s the sorted set for which a dynamically typesafe view is to be - * returned - * @param type the type of element that s is permitted to hold + * returned + * @param type the type of element that {@code s} is permitted to hold * @return a dynamically typesafe view of the specified sorted set * @since 1.5 */ @@ -2361,36 +2405,39 @@ public class Collections { public E last() { return ss.last(); } public SortedSet subSet(E fromElement, E toElement) { - return new CheckedSortedSet(ss.subSet(fromElement,toElement), - type); + return checkedSortedSet(ss.subSet(fromElement,toElement), type); } public SortedSet headSet(E toElement) { - return new CheckedSortedSet(ss.headSet(toElement), type); + return checkedSortedSet(ss.headSet(toElement), type); } public SortedSet tailSet(E fromElement) { - return new CheckedSortedSet(ss.tailSet(fromElement), type); + return checkedSortedSet(ss.tailSet(fromElement), type); } } /** * Returns a dynamically typesafe view of the specified list. * Any attempt to insert an element of the wrong type will result in - * an immediate ClassCastException. Assuming a list contains + * an immediate {@link ClassCastException}. Assuming a list contains * no incorrectly typed elements prior to the time a dynamically typesafe * view is generated, and that all subsequent access to the list * takes place through the view, it is guaranteed that the * list cannot contain an incorrectly typed element. * *

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

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

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

Since {@code null} is considered to be a value of any reference + * type, the returned list permits insertion of null elements whenever + * the backing list does. * * @param list the list for which a dynamically typesafe view is to be * returned - * @param type the type of element that list is permitted to hold + * @param type the type of element that {@code list} is permitted to hold * @return a dynamically typesafe view of the specified list * @since 1.5 */ @@ -2403,10 +2450,11 @@ public class Collections { /** * @serial include */ - static class CheckedList extends CheckedCollection - implements List + static class CheckedList + extends CheckedCollection + implements List { - static final long serialVersionUID = 65247728283967356L; + private static final long serialVersionUID = 65247728283967356L; final List list; CheckedList(List list, Class type) { @@ -2414,7 +2462,7 @@ public class Collections { this.list = list; } - public boolean equals(Object o) { return list.equals(o); } + public boolean equals(Object o) { return o == this || list.equals(o); } public int hashCode() { return list.hashCode(); } public E get(int index) { return list.get(index); } public E remove(int index) { return list.remove(index); } @@ -2432,29 +2480,21 @@ public class Collections { } public boolean addAll(int index, Collection c) { - // See CheckCollection.addAll, above, for an explanation - E[] a = null; - try { - a = c.toArray(zeroLengthElementArray()); - } catch (ArrayStoreException e) { - throw new ClassCastException(); - } - - return list.addAll(index, Arrays.asList(a)); + return list.addAll(index, checkedCopyOf(c)); } public ListIterator listIterator() { return listIterator(0); } public ListIterator listIterator(final int index) { - return new ListIterator() { - ListIterator i = list.listIterator(index); + final ListIterator i = list.listIterator(index); + return new ListIterator() { public boolean hasNext() { return i.hasNext(); } public E next() { return i.next(); } public boolean hasPrevious() { return i.hasPrevious(); } public E previous() { return i.previous(); } public int nextIndex() { return i.nextIndex(); } public int previousIndex() { return i.previousIndex(); } - public void remove() { i.remove(); } + public void remove() { i.remove(); } public void set(E e) { typeCheck(e); @@ -2492,14 +2532,14 @@ public class Collections { } /** - * Returns a dynamically typesafe view of the specified map. Any attempt - * to insert a mapping whose key or value have the wrong type will result - * in an immediate ClassCastException. Similarly, any attempt to - * modify the value currently associated with a key will result in an - * immediate ClassCastException, whether the modification is - * attempted directly through the map itself, or through a {@link - * Map.Entry} instance obtained from the map's {@link Map#entrySet() - * entry set} view. + * Returns a dynamically typesafe view of the specified map. + * Any attempt to insert a mapping whose key or value have the wrong + * type will result in an immediate {@link ClassCastException}. + * Similarly, any attempt to modify the value currently associated with + * a key will result in an immediate {@link ClassCastException}, + * whether the modification is attempted directly through the map + * itself, or through a {@link Map.Entry} instance obtained from the + * map's {@link Map#entrySet() entry set} view. * *

Assuming a map contains no incorrectly typed keys or values * prior to the time a dynamically typesafe view is generated, and @@ -2508,20 +2548,25 @@ public class Collections { * map cannot contain an incorrectly typed key or value. * *

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

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

Since {@code null} is considered to be a value of any reference + * type, the returned map permits insertion of null keys or values + * whenever the backing map does. + * * @param m the map for which a dynamically typesafe view is to be - * returned - * @param keyType the type of key that m is permitted to hold - * @param valueType the type of value that m is permitted to hold + * returned + * @param keyType the type of key that {@code m} is permitted to hold + * @param valueType the type of value that {@code m} is permitted to hold * @return a dynamically typesafe view of the specified map * @since 1.5 */ - public static Map checkedMap(Map m, Class keyType, + public static Map checkedMap(Map m, + Class keyType, Class valueType) { return new CheckedMap(m, keyType, valueType); } @@ -2530,8 +2575,8 @@ public class Collections { /** * @serial include */ - private static class CheckedMap implements Map, - Serializable + private static class CheckedMap + implements Map, Serializable { private static final long serialVersionUID = 5742860141034234728L; @@ -2540,15 +2585,21 @@ public class Collections { final Class valueType; private void typeCheck(Object key, Object value) { - if (!keyType.isInstance(key)) - throw new ClassCastException("Attempt to insert " + - key.getClass() + " key into collection with key type " - + keyType); - - if (!valueType.isInstance(value)) - throw new ClassCastException("Attempt to insert " + - value.getClass() +" value into collection with value type " - + valueType); + if (key != null && !keyType.isInstance(key)) + throw new ClassCastException(badKeyMsg(key)); + + if (value != null && !valueType.isInstance(value)) + throw new ClassCastException(badValueMsg(value)); + } + + private String badKeyMsg(Object key) { + return "Attempt to insert " + key.getClass() + + " key into map with key type " + keyType; + } + + private String badValueMsg(Object value) { + return "Attempt to insert " + value.getClass() + + " value into map with value type " + valueType; } CheckedMap(Map m, Class keyType, Class valueType) { @@ -2568,7 +2619,7 @@ public class Collections { public void clear() { m.clear(); } public Set keySet() { return m.keySet(); } public Collection values() { return m.values(); } - public boolean equals(Object o) { return m.equals(o); } + public boolean equals(Object o) { return o == this || m.equals(o); } public int hashCode() { return m.hashCode(); } public String toString() { return m.toString(); } @@ -2577,45 +2628,26 @@ public class Collections { return m.put(key, value); } + @SuppressWarnings("unchecked") public void putAll(Map t) { - // See CheckCollection.addAll, above, for an explanation - K[] keys = null; - try { - keys = t.keySet().toArray(zeroLengthKeyArray()); - } catch (ArrayStoreException e) { - throw new ClassCastException(); - } - V[] values = null; - try { - values = t.values().toArray(zeroLengthValueArray()); - } catch (ArrayStoreException e) { - throw new ClassCastException(); + // Satisfy the following goals: + // - good diagnostics in case of type mismatch + // - all-or-nothing semantics + // - protection from malicious t + // - correct behavior if t is a concurrent map + Object[] entries = t.entrySet().toArray(); + List> checked = + new ArrayList>(entries.length); + for (Object o : entries) { + Map.Entry e = (Map.Entry) o; + Object k = e.getKey(); + Object v = e.getValue(); + typeCheck(k, v); + checked.add( + new AbstractMap.SimpleImmutableEntry((K) k, (V) v)); } - - if (keys.length != values.length) - throw new ConcurrentModificationException(); - - for (int i = 0; i < keys.length; i++) - m.put(keys[i], values[i]); - } - - // Lazily initialized - private K[] zeroLengthKeyArray = null; - private V[] zeroLengthValueArray = null; - - /* - * We don't need locking or volatile, because it's OK if we create - * several zeroLengthValueArrays, and they're immutable. - */ - private K[] zeroLengthKeyArray() { - if (zeroLengthKeyArray == null) - zeroLengthKeyArray = (K[]) Array.newInstance(keyType, 0); - return zeroLengthKeyArray; - } - private V[] zeroLengthValueArray() { - if (zeroLengthValueArray == null) - zeroLengthValueArray = (V[]) Array.newInstance(valueType, 0); - return zeroLengthValueArray; + for (Map.Entry e : checked) + m.put(e.getKey(), e.getValue()); } private transient Set> entrySet = null; @@ -2635,50 +2667,42 @@ public class Collections { * @serial exclude */ static class CheckedEntrySet implements Set> { - Set> s; - Class valueType; + private final Set> s; + private final Class valueType; CheckedEntrySet(Set> s, Class valueType) { this.s = s; this.valueType = valueType; } - public int size() { return s.size(); } - public boolean isEmpty() { return s.isEmpty(); } - public String toString() { return s.toString(); } - public int hashCode() { return s.hashCode(); } - public boolean remove(Object o) { return s.remove(o); } - public boolean removeAll(Collection coll) { - return s.removeAll(coll); - } - public boolean retainAll(Collection coll) { - return s.retainAll(coll); - } - public void clear() { - s.clear(); - } + public int size() { return s.size(); } + public boolean isEmpty() { return s.isEmpty(); } + public String toString() { return s.toString(); } + public int hashCode() { return s.hashCode(); } + public void clear() { s.clear(); } - public boolean add(Map.Entry e){ + public boolean add(Map.Entry e) { throw new UnsupportedOperationException(); } public boolean addAll(Collection> coll) { throw new UnsupportedOperationException(); } - public Iterator> iterator() { - return new Iterator>() { - Iterator> i = s.iterator(); + final Iterator> i = s.iterator(); + final Class valueType = this.valueType; + return new Iterator>() { public boolean hasNext() { return i.hasNext(); } public void remove() { i.remove(); } public Map.Entry next() { - return new CheckedEntry(i.next(), valueType); + return checkedEntry(i.next(), valueType); } }; } + @SuppressWarnings("unchecked") public Object[] toArray() { Object[] source = s.toArray(); @@ -2691,22 +2715,23 @@ public class Collections { new Object[source.length]); for (int i = 0; i < source.length; i++) - dest[i] = new CheckedEntry((Map.Entry)source[i], - valueType); + dest[i] = checkedEntry((Map.Entry)source[i], + valueType); return dest; } + @SuppressWarnings("unchecked") public T[] toArray(T[] a) { // We don't pass a to s.toArray, to avoid window of // vulnerability wherein an unscrupulous multithreaded client // could get his hands on raw (unwrapped) Entries from s. - Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); + T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); for (int i=0; i((Map.Entry)arr[i], - valueType); + arr[i] = (T) checkedEntry((Map.Entry)arr[i], + valueType); if (arr.length > a.length) - return (T[])arr; + return arr; System.arraycopy(arr, 0, a, 0, arr.length); if (a.length > arr.length) @@ -2723,32 +2748,61 @@ public class Collections { public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; + Map.Entry e = (Map.Entry) o; return s.contains( - new CheckedEntry((Map.Entry) o, valueType)); + (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType)); } /** - * The next two methods are overridden to protect against - * an unscrupulous collection whose contains(Object o) method - * senses when o is a Map.Entry, and calls o.setValue. + * The bulk collection methods are overridden to protect + * against an unscrupulous collection whose contains(Object o) + * method senses when o is a Map.Entry, and calls o.setValue. */ - public boolean containsAll(Collection coll) { - Iterator e = coll.iterator(); - while (e.hasNext()) - if (!contains(e.next())) // Invokes safe contains() above + public boolean containsAll(Collection c) { + for (Object o : c) + if (!contains(o)) // Invokes safe contains() above return false; return true; } + public boolean remove(Object o) { + if (!(o instanceof Map.Entry)) + return false; + return s.remove(new AbstractMap.SimpleImmutableEntry + ((Map.Entry)o)); + } + + public boolean removeAll(Collection c) { + return batchRemove(c, false); + } + public boolean retainAll(Collection c) { + return batchRemove(c, true); + } + private boolean batchRemove(Collection c, boolean complement) { + boolean modified = false; + Iterator> it = iterator(); + while (it.hasNext()) { + if (c.contains(it.next()) != complement) { + it.remove(); + modified = true; + } + } + return modified; + } + public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Set that = (Set) o; - if (that.size() != s.size()) - return false; - return containsAll(that); // Invokes safe containsAll() above + return that.size() == s.size() + && containsAll(that); // Invokes safe containsAll() above + } + + static CheckedEntry checkedEntry(Map.Entry e, + Class valueType) { + return new CheckedEntry(e, valueType); } /** @@ -2756,13 +2810,13 @@ public class Collections { * 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. + * Map.Entry when asked to perform an equality check. */ - private static class CheckedEntry implements Map.Entry { - private Map.Entry e; - private Class valueType; + private static class CheckedEntry implements Map.Entry { + private final Map.Entry e; + private final Class valueType; - CheckedEntry(Map.Entry e, Class valueType) { + CheckedEntry(Map.Entry e, Class valueType) { this.e = e; this.valueType = valueType; } @@ -2772,35 +2826,38 @@ public class Collections { public int hashCode() { return e.hashCode(); } public String toString() { return e.toString(); } - public V setValue(V value) { - if (!valueType.isInstance(value)) - throw new ClassCastException("Attempt to insert " + - value.getClass() + - " value into collection with value type " + valueType); + if (value != null && !valueType.isInstance(value)) + throw new ClassCastException(badValueMsg(value)); return e.setValue(value); } + private String badValueMsg(Object value) { + return "Attempt to insert " + value.getClass() + + " value into map with value type " + valueType; + } + public boolean equals(Object o) { + if (o == this) + return true; if (!(o instanceof Map.Entry)) return false; - Map.Entry t = (Map.Entry)o; - return eq(e.getKey(), t.getKey()) && - eq(e.getValue(), t.getValue()); + return e.equals(new AbstractMap.SimpleImmutableEntry + ((Map.Entry)o)); } } } } /** - * Returns a dynamically typesafe view of the specified sorted map. Any - * attempt to insert a mapping whose key or value have the wrong type will - * result in an immediate ClassCastException. Similarly, any - * attempt to modify the value currently associated with a key will result - * in an immediate ClassCastException, whether the modification - * is attempted directly through the map itself, or through a {@link - * Map.Entry} instance obtained from the map's {@link Map#entrySet() entry - * set} view. + * Returns a dynamically typesafe view of the specified sorted map. + * Any attempt to insert a mapping whose key or value have the wrong + * type will result in an immediate {@link ClassCastException}. + * Similarly, any attempt to modify the value currently associated with + * a key will result in an immediate {@link ClassCastException}, + * whether the modification is attempted directly through the map + * itself, or through a {@link Map.Entry} instance obtained from the + * map's {@link Map#entrySet() entry set} view. * *

Assuming a map contains no incorrectly typed keys or values * prior to the time a dynamically typesafe view is generated, and @@ -2809,16 +2866,20 @@ public class Collections { * map cannot contain an incorrectly typed key or value. * *

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

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

Since {@code null} is considered to be a value of any reference + * type, the returned map permits insertion of null keys or values + * whenever the backing map does. + * * @param m the map for which a dynamically typesafe view is to be - * returned - * @param keyType the type of key that m is permitted to hold - * @param valueType the type of value that m is permitted to hold + * returned + * @param keyType the type of key that {@code m} is permitted to hold + * @param valueType the type of value that {@code m} is permitted to hold * @return a dynamically typesafe view of the specified map * @since 1.5 */ @@ -2849,29 +2910,146 @@ public class Collections { public K lastKey() { return sm.lastKey(); } public SortedMap subMap(K fromKey, K toKey) { - return new CheckedSortedMap(sm.subMap(fromKey, toKey), - keyType, valueType); + return checkedSortedMap(sm.subMap(fromKey, toKey), + keyType, valueType); } - public SortedMap headMap(K toKey) { - return new CheckedSortedMap(sm.headMap(toKey), - keyType, valueType); + return checkedSortedMap(sm.headMap(toKey), keyType, valueType); } - public SortedMap tailMap(K fromKey) { - return new CheckedSortedMap(sm.tailMap(fromKey), - keyType, valueType); + return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType); } } - // Miscellaneous + // Empty collections + + /** + * Returns an iterator that has no elements. More precisely, + * + *

+ * + *

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

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

Implementations of this method are permitted, but not + * required, to return the same object from multiple invocations. + * + * @return an empty enumeration + * @since 1.7 + */ + @SuppressWarnings("unchecked") + public static Enumeration emptyEnumeration() { + return (Enumeration) EmptyEnumeration.EMPTY_ENUMERATION; + } + + private static class EmptyEnumeration implements Enumeration { + static final EmptyEnumeration EMPTY_ENUMERATION + = new EmptyEnumeration(); + + public boolean hasMoreElements() { return false; } + public E nextElement() { throw new NoSuchElementException(); } + } /** * The empty set (immutable). This set is serializable. * * @see #emptySet() */ - public static final Set EMPTY_SET = new EmptySet(); + @SuppressWarnings("unchecked") + public static final Set EMPTY_SET = new EmptySet(); /** * Returns the empty set (immutable). This set is serializable. @@ -2889,34 +3067,35 @@ public class Collections { * @see #EMPTY_SET * @since 1.5 */ + @SuppressWarnings("unchecked") public static final Set emptySet() { - return (Set) EMPTY_SET; + return (Set) EMPTY_SET; } /** * @serial include */ - private static class EmptySet extends AbstractSet implements Serializable { - // use serialVersionUID from JDK 1.2.2 for interoperability - private static final long serialVersionUID = 1582296315990362920L; + private static class EmptySet + extends AbstractSet + implements Serializable + { + private static final long serialVersionUID = 1582296315990362920L; - public Iterator iterator() { - return new Iterator() { - public boolean hasNext() { - return false; - } - public Object next() { - throw new NoSuchElementException(); - } - public void remove() { - throw new UnsupportedOperationException(); - } - }; - } + public Iterator iterator() { return emptyIterator(); } public int size() {return 0;} + public boolean isEmpty() {return true;} public boolean contains(Object obj) {return false;} + public boolean containsAll(Collection c) { return c.isEmpty(); } + + public Object[] toArray() { return new Object[0]; } + + public T[] toArray(T[] a) { + if (a.length > 0) + a[0] = null; + return a; + } // Preserves singleton property private Object readResolve() { @@ -2929,7 +3108,8 @@ public class Collections { * * @see #emptyList() */ - public static final List EMPTY_LIST = new EmptyList(); + @SuppressWarnings("unchecked") + public static final List EMPTY_LIST = new EmptyList(); /** * Returns the empty list (immutable). This list is serializable. @@ -2946,27 +3126,50 @@ public class Collections { * @see #EMPTY_LIST * @since 1.5 */ + @SuppressWarnings("unchecked") public static final List emptyList() { - return (List) EMPTY_LIST; + return (List) EMPTY_LIST; } /** * @serial include */ - private static class EmptyList - extends AbstractList - implements RandomAccess, Serializable { - // use serialVersionUID from JDK 1.2.2 for interoperability - private static final long serialVersionUID = 8842843931221139166L; + private static class EmptyList + extends AbstractList + implements RandomAccess, Serializable { + private static final long serialVersionUID = 8842843931221139166L; + + public Iterator iterator() { + return emptyIterator(); + } + public ListIterator listIterator() { + return emptyListIterator(); + } public int size() {return 0;} + public boolean isEmpty() {return true;} public boolean contains(Object obj) {return false;} + public boolean containsAll(Collection c) { return c.isEmpty(); } + + public Object[] toArray() { return new Object[0]; } + + public T[] toArray(T[] a) { + if (a.length > 0) + a[0] = null; + return a; + } - public Object get(int index) { + public E get(int index) { throw new IndexOutOfBoundsException("Index: "+index); } + public boolean equals(Object o) { + return (o instanceof List) && ((List)o).isEmpty(); + } + + public int hashCode() { return 1; } + // Preserves singleton property private Object readResolve() { return EMPTY_LIST; @@ -2979,7 +3182,8 @@ public class Collections { * @see #emptyMap() * @since 1.3 */ - public static final Map EMPTY_MAP = new EmptyMap(); + @SuppressWarnings("unchecked") + public static final Map EMPTY_MAP = new EmptyMap(); /** * Returns the empty map (immutable). This map is serializable. @@ -2996,36 +3200,31 @@ public class Collections { * @see #EMPTY_MAP * @since 1.5 */ + @SuppressWarnings("unchecked") public static final Map emptyMap() { - return (Map) EMPTY_MAP; + return (Map) EMPTY_MAP; } - private static class EmptyMap - extends AbstractMap - implements Serializable { - + /** + * @serial include + */ + private static class EmptyMap + extends AbstractMap + implements Serializable + { private static final long serialVersionUID = 6428348081105594320L; public int size() {return 0;} - public boolean isEmpty() {return true;} - public boolean containsKey(Object key) {return false;} - public boolean containsValue(Object value) {return false;} - - public Object get(Object key) {return null;} - - public Set keySet() {return Collections.emptySet();} - - public Collection values() {return Collections.emptySet();} - - public Set> entrySet() { - return Collections.emptySet(); - } + public V get(Object key) {return null;} + public Set keySet() {return emptySet();} + public Collection values() {return emptySet();} + public Set> entrySet() {return emptySet();} public boolean equals(Object o) { - return (o instanceof Map) && ((Map)o).size()==0; + return (o instanceof Map) && ((Map)o).isEmpty(); } public int hashCode() {return 0;} @@ -3036,6 +3235,8 @@ public class Collections { } } + // Singleton collections + /** * Returns an immutable set containing only the specified object. * The returned set is serializable. @@ -3044,40 +3245,43 @@ public class Collections { * @return an immutable set containing only the specified object. */ public static Set singleton(T o) { - return new SingletonSet(o); + return new SingletonSet(o); + } + + static Iterator singletonIterator(final E e) { + return new Iterator() { + private boolean hasNext = true; + public boolean hasNext() { + return hasNext; + } + public E next() { + if (hasNext) { + hasNext = false; + return e; + } + throw new NoSuchElementException(); + } + public void remove() { + throw new UnsupportedOperationException(); + } + }; } /** * @serial include */ private static class SingletonSet - extends AbstractSet - implements Serializable + extends AbstractSet + implements Serializable { - // use serialVersionUID from JDK 1.2.2 for interoperability - private static final long serialVersionUID = 3193687207550431679L; + private static final long serialVersionUID = 3193687207550431679L; final private E element; SingletonSet(E e) {element = e;} public Iterator iterator() { - return new Iterator() { - private boolean hasNext = true; - public boolean hasNext() { - return hasNext; - } - public E next() { - if (hasNext) { - hasNext = false; - return element; - } - throw new NoSuchElementException(); - } - public void remove() { - throw new UnsupportedOperationException(); - } - }; + return singletonIterator(element); } public int size() {return 1;} @@ -3094,19 +3298,26 @@ public class Collections { * @since 1.3 */ public static List singletonList(T o) { - return new SingletonList(o); + return new SingletonList(o); } + /** + * @serial include + */ private static class SingletonList - extends AbstractList - implements RandomAccess, Serializable { + extends AbstractList + implements RandomAccess, Serializable { - static final long serialVersionUID = 3093736618740652951L; + private static final long serialVersionUID = 3093736618740652951L; private final E element; SingletonList(E obj) {element = obj;} + public Iterator iterator() { + return singletonIterator(element); + } + public int size() {return 1;} public boolean contains(Object obj) {return eq(obj, element);} @@ -3129,16 +3340,19 @@ public class Collections { * @since 1.3 */ public static Map singletonMap(K key, V value) { - return new SingletonMap(key, value); + return new SingletonMap(key, value); } + /** + * @serial include + */ private static class SingletonMap - extends AbstractMap - implements Serializable { - private static final long serialVersionUID = -6979724477215052911L; + extends AbstractMap + implements Serializable { + private static final long serialVersionUID = -6979724477215052911L; private final K k; - private final V v; + private final V v; SingletonMap(K key, V value) { k = key; @@ -3159,27 +3373,29 @@ public class Collections { private transient Set> entrySet = null; private transient Collection values = null; - public Set keySet() { - if (keySet==null) - keySet = singleton(k); - return keySet; - } - - public Set> entrySet() { - if (entrySet==null) - entrySet = Collections.>singleton( - new SimpleImmutableEntry(k, v)); - return entrySet; - } - - public Collection values() { - if (values==null) - values = singleton(v); - return values; - } + public Set keySet() { + if (keySet==null) + keySet = singleton(k); + return keySet; + } + + public Set> entrySet() { + if (entrySet==null) + entrySet = Collections.>singleton( + new SimpleImmutableEntry(k, v)); + return entrySet; + } + + public Collection values() { + if (values==null) + values = singleton(v); + return values; + } } + // Miscellaneous + /** * Returns an immutable list consisting of n copies of the * specified object. The newly allocated data object is tiny (it contains @@ -3190,14 +3406,14 @@ public class Collections { * @param n the number of elements in the returned list. * @param o the element to appear repeatedly in the returned list. * @return an immutable list consisting of n copies of the - * specified object. + * specified object. * @throws IllegalArgumentException if n < 0. * @see List#addAll(Collection) * @see List#addAll(int, Collection) */ public static List nCopies(int n, T o) { - if (n < 0) - throw new IllegalArgumentException("List length = " + n); + if (n < 0) + throw new IllegalArgumentException("List length = " + n); return new CopiesList(n, o); } @@ -3205,16 +3421,16 @@ public class Collections { * @serial include */ private static class CopiesList - extends AbstractList - implements RandomAccess, Serializable + extends AbstractList + implements RandomAccess, Serializable { - static final long serialVersionUID = 2739099268398711800L; + private static final long serialVersionUID = 2739099268398711800L; final int n; final E element; CopiesList(int n, E e) { - assert n >= 0; + assert n >= 0; this.n = n; element = e; } @@ -3227,13 +3443,13 @@ public class Collections { return n != 0 && eq(obj, element); } - public int indexOf(Object o) { - return contains(o) ? 0 : -1; - } - - public int lastIndexOf(Object o) { - return contains(o) ? n - 1 : -1; - } + public int indexOf(Object o) { + return contains(o) ? 0 : -1; + } + + public int lastIndexOf(Object o) { + return contains(o) ? n - 1 : -1; + } public E get(int index) { if (index < 0 || index >= n) @@ -3242,38 +3458,38 @@ public class Collections { return element; } - public Object[] toArray() { - final Object[] a = new Object[n]; - if (element != null) - Arrays.fill(a, 0, n, element); - return a; - } - - public T[] toArray(T[] a) { - final int n = this.n; - if (a.length < n) { - a = (T[])java.lang.reflect.Array - .newInstance(a.getClass().getComponentType(), n); - if (element != null) - Arrays.fill(a, 0, n, element); - } else { - Arrays.fill(a, 0, n, element); - if (a.length > n) - a[n] = null; - } - return a; - } - - public List subList(int fromIndex, int toIndex) { - if (fromIndex < 0) - throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); - if (toIndex > n) - throw new IndexOutOfBoundsException("toIndex = " + toIndex); - if (fromIndex > toIndex) - throw new IllegalArgumentException("fromIndex(" + fromIndex + - ") > toIndex(" + toIndex + ")"); - return new CopiesList(toIndex - fromIndex, element); - } + public Object[] toArray() { + final Object[] a = new Object[n]; + if (element != null) + Arrays.fill(a, 0, n, element); + return a; + } + + public T[] toArray(T[] a) { + final int n = this.n; + if (a.length < n) { + a = (T[])java.lang.reflect.Array + .newInstance(a.getClass().getComponentType(), n); + if (element != null) + Arrays.fill(a, 0, n, element); + } else { + Arrays.fill(a, 0, n, element); + if (a.length > n) + a[n] = null; + } + return a; + } + + public List subList(int fromIndex, int toIndex) { + if (fromIndex < 0) + throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); + if (toIndex > n) + throw new IndexOutOfBoundsException("toIndex = " + toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex(" + fromIndex + + ") > toIndex(" + toIndex + ")"); + return new CopiesList(toIndex - fromIndex, element); + } } /** @@ -3285,34 +3501,36 @@ public class Collections { * objects that implement the Comparable interface in * reverse-natural-order. For example, suppose a is an array of * strings. Then: 
-     * 		Arrays.sort(a, Collections.reverseOrder());
+     *          Arrays.sort(a, Collections.reverseOrder());
      *
sorts the array in reverse-lexicographic (alphabetical) order.

* * The returned comparator is serializable. * * @return a comparator that imposes the reverse of the natural - * ordering on a collection of objects that implement - * the Comparable interface. + * ordering on a collection of objects that implement + * the Comparable interface. * @see Comparable */ public static Comparator reverseOrder() { - return (Comparator) REVERSE_ORDER; + return (Comparator) ReverseComparator.REVERSE_ORDER; } - private static final Comparator REVERSE_ORDER = new ReverseComparator(); - /** * @serial include */ - private static class ReverseComparator - implements Comparator>, Serializable { + private static class ReverseComparator + implements Comparator>, Serializable { + + private static final long serialVersionUID = 7207038068494060240L; - // use serialVersionUID from JDK 1.2.2 for interoperability - private static final long serialVersionUID = 7207038068494060240L; + static final ReverseComparator REVERSE_ORDER + = new ReverseComparator(); public int compare(Comparable c1, Comparable c2) { return c2.compareTo(c1); } + + private Object readResolve() { return reverseOrder(); } } /** @@ -3326,12 +3544,15 @@ public class Collections { * comparator is also serializable or null). * * @return a comparator that imposes the reverse ordering of the - * specified comparator. + * specified comparator * @since 1.5 */ public static Comparator reverseOrder(Comparator cmp) { if (cmp == null) - return new ReverseComparator(); // Unchecked warning!! + return reverseOrder(); + + if (cmp instanceof ReverseComparator2) + return ((ReverseComparator2)cmp).cmp; return new ReverseComparator2(cmp); } @@ -3351,7 +3572,7 @@ public class Collections { * * @serial */ - private Comparator cmp; + final Comparator cmp; ReverseComparator2(Comparator cmp) { assert cmp != null; @@ -3361,6 +3582,16 @@ public class Collections { public int compare(T t1, T t2) { return cmp.compare(t2, t1); } + + public boolean equals(Object o) { + return (o == this) || + (o instanceof ReverseComparator2 && + cmp.equals(((ReverseComparator2)o).cmp)); + } + + public int hashCode() { + return cmp.hashCode() ^ Integer.MIN_VALUE; + } } /** @@ -3373,16 +3604,16 @@ public class Collections { * @see Enumeration */ public static Enumeration enumeration(final Collection c) { - return new Enumeration() { - Iterator i = c.iterator(); + return new Enumeration() { + private final Iterator i = c.iterator(); - public boolean hasMoreElements() { - return i.hasNext(); - } - - public T nextElement() { - return i.next(); - } + public boolean hasMoreElements() { + return i.hasNext(); + } + + public T nextElement() { + return i.next(); + } }; } @@ -3411,8 +3642,8 @@ public class Collections { /** * Returns true if the specified arguments are equal, or both null. */ - private static boolean eq(Object o1, Object o2) { - return (o1==null ? o2==null : o1.equals(o2)); + static boolean eq(Object o1, Object o2) { + return o1==null ? o2==null : o1.equals(o2); } /** @@ -3498,10 +3729,10 @@ public class Collections { * * * @param c the collection into which elements are to be inserted - * @param a the elements to insert into c + * @param elements the elements to insert into c * @return true if the collection changed as a result of the call * @throws UnsupportedOperationException if c does not support - * the add operation. + * the add operation * @throws NullPointerException if elements contains one or more * null values and c does not permit null elements, or * if c or elements are null @@ -3510,10 +3741,10 @@ public class Collections { * @see Collection#addAll(Collection) * @since 1.5 */ - public static boolean addAll(Collection c, T... a) { + public static boolean addAll(Collection c, T... elements) { boolean result = false; - for (T e : a) - result |= c.add(e); + for (T element : elements) + result |= c.add(element); return result; } @@ -3550,47 +3781,46 @@ public class Collections { return new SetFromMap(map); } + /** + * @serial include + */ private static class SetFromMap extends AbstractSet implements Set, Serializable { private final Map m; // The backing map - private transient Set keySet; // Its keySet + private transient Set s; // Its keySet SetFromMap(Map map) { if (!map.isEmpty()) throw new IllegalArgumentException("Map is non-empty"); m = map; - keySet = map.keySet(); + s = map.keySet(); } + public void clear() { m.clear(); } public int size() { return m.size(); } public boolean isEmpty() { return m.isEmpty(); } public boolean contains(Object o) { return m.containsKey(o); } - public Iterator iterator() { return keySet.iterator(); } - public Object[] toArray() { return keySet.toArray(); } - public T[] toArray(T[] a) { return keySet.toArray(a); } - public boolean add(E e) { - return m.put(e, Boolean.TRUE) == null; - } public boolean remove(Object o) { return m.remove(o) != null; } - - public boolean removeAll(Collection c) { - return keySet.removeAll(c); - } - public boolean retainAll(Collection c) { - return keySet.retainAll(c); - } - public void clear() { m.clear(); } - public boolean equals(Object o) { return keySet.equals(o); } - public int hashCode() { return keySet.hashCode(); } + public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } + public Iterator iterator() { return s.iterator(); } + public Object[] toArray() { return s.toArray(); } + public T[] toArray(T[] a) { return s.toArray(a); } + public String toString() { return s.toString(); } + public int hashCode() { return s.hashCode(); } + public boolean equals(Object o) { return o == this || s.equals(o); } + public boolean containsAll(Collection c) {return s.containsAll(c);} + public boolean removeAll(Collection c) {return s.removeAll(c);} + public boolean retainAll(Collection c) {return s.retainAll(c);} + // addAll is the only inherited implementation private static final long serialVersionUID = 2454657854757543876L; - private void readObject(java.io.ObjectInputStream s) + private void readObject(java.io.ObjectInputStream stream) throws IOException, ClassNotFoundException { - s.defaultReadObject(); - keySet = m.keySet(); + stream.defaultReadObject(); + s = m.keySet(); } } @@ -3601,6 +3831,12 @@ public class Collections { * view can be useful when you would like to use a method * requiring a Queue but you need Lifo ordering. * + *

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