1 |
|
/* |
2 |
|
* %W% %E% |
3 |
|
* |
4 |
< |
* Copyright 2005 Sun Microsystems, Inc. All rights reserved. |
4 |
> |
* Copyright 2006 Sun Microsystems, Inc. All rights reserved. |
5 |
|
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. |
6 |
|
*/ |
7 |
|
|
43 |
|
* |
44 |
|
* @author Josh Bloch |
45 |
|
* @author Neal Gafter |
46 |
< |
* @version %I%, %G% |
46 |
> |
* @version 1.104, 03/21/06 |
47 |
|
* @see Collection |
48 |
|
* @see Set |
49 |
|
* @see List |
63 |
|
* two implementations, one of which is appropriate for RandomAccess |
64 |
|
* lists, the other for "sequential." Often, the random access variant |
65 |
|
* yields better performance on small sequential access lists. The |
66 |
< |
* tuning parameters below determine the cutoff point for what constitutes |
66 |
> |
* tuning parameters below determine the cutoff point for what constitutes |
67 |
|
* a "small" sequential access list for each algorithm. The values below |
68 |
|
* were empirically determined to work well for LinkedList. Hopefully |
69 |
|
* they should be reasonable for other sequential access List |
168 |
|
/** |
169 |
|
* Searches the specified list for the specified object using the binary |
170 |
|
* search algorithm. The list must be sorted into ascending order |
171 |
< |
* according to the <i>natural ordering</i> of its elements (as by the |
172 |
< |
* <tt>sort(List)</tt> method, above) prior to making this call. If it is |
173 |
< |
* not sorted, the results are undefined. If the list contains multiple |
174 |
< |
* elements equal to the specified object, there is no guarantee which one |
175 |
< |
* will be found.<p> |
171 |
> |
* according to the {@linkplain Comparable natural ordering} of its |
172 |
> |
* elements (as by the {@link #sort(List)} method) prior to making this |
173 |
> |
* call. If it is not sorted, the results are undefined. If the list |
174 |
> |
* contains multiple elements equal to the specified object, there is no |
175 |
> |
* guarantee which one will be found. |
176 |
|
* |
177 |
< |
* This method runs in log(n) time for a "random access" list (which |
177 |
> |
* <p>This method runs in log(n) time for a "random access" list (which |
178 |
|
* provides near-constant-time positional access). If the specified list |
179 |
|
* does not implement the {@link RandomAccess} interface and is large, |
180 |
|
* this method will do an iterator-based binary search that performs |
186 |
|
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The |
187 |
|
* <i>insertion point</i> is defined as the point at which the |
188 |
|
* key would be inserted into the list: the index of the first |
189 |
< |
* element greater than the key, or <tt>list.size()</tt>, if all |
189 |
> |
* element greater than the key, or <tt>list.size()</tt> if all |
190 |
|
* elements in the list are less than the specified key. Note |
191 |
|
* that this guarantees that the return value will be >= 0 if |
192 |
|
* and only if the key is found. |
193 |
|
* @throws ClassCastException if the list contains elements that are not |
194 |
|
* <i>mutually comparable</i> (for example, strings and |
195 |
< |
* integers), or the search key in not mutually comparable |
195 |
> |
* integers), or the search key is not mutually comparable |
196 |
|
* with the elements of the list. |
197 |
– |
* @see Comparable |
198 |
– |
* @see #sort(List) |
197 |
|
*/ |
198 |
|
public static <T> |
199 |
|
int binarySearch(List<? extends Comparable<? super T>> list, T key) { |
210 |
|
int high = list.size()-1; |
211 |
|
|
212 |
|
while (low <= high) { |
213 |
< |
int mid = (low + high) >> 1; |
213 |
> |
int mid = (low + high) >>> 1; |
214 |
|
Comparable<? super T> midVal = list.get(mid); |
215 |
|
int cmp = midVal.compareTo(key); |
216 |
|
|
232 |
|
ListIterator<? extends Comparable<? super T>> i = list.listIterator(); |
233 |
|
|
234 |
|
while (low <= high) { |
235 |
< |
int mid = (low + high) >> 1; |
235 |
> |
int mid = (low + high) >>> 1; |
236 |
|
Comparable<? super T> midVal = get(i, mid); |
237 |
|
int cmp = midVal.compareTo(key); |
238 |
|
|
268 |
|
/** |
269 |
|
* Searches the specified list for the specified object using the binary |
270 |
|
* search algorithm. The list must be sorted into ascending order |
271 |
< |
* according to the specified comparator (as by the <tt>Sort(List, |
272 |
< |
* Comparator)</tt> method, above), prior to making this call. If it is |
271 |
> |
* according to the specified comparator (as by the |
272 |
> |
* {@link #sort(List, Comparator) sort(List, Comparator)} |
273 |
> |
* method), prior to making this call. If it is |
274 |
|
* not sorted, the results are undefined. If the list contains multiple |
275 |
|
* elements equal to the specified object, there is no guarantee which one |
276 |
< |
* will be found.<p> |
276 |
> |
* will be found. |
277 |
|
* |
278 |
< |
* This method runs in log(n) time for a "random access" list (which |
278 |
> |
* <p>This method runs in log(n) time for a "random access" list (which |
279 |
|
* provides near-constant-time positional access). If the specified list |
280 |
|
* does not implement the {@link RandomAccess} interface and is large, |
281 |
|
* this method will do an iterator-based binary search that performs |
283 |
|
* |
284 |
|
* @param list the list to be searched. |
285 |
|
* @param key the key to be searched for. |
286 |
< |
* @param c the comparator by which the list is ordered. A |
287 |
< |
* <tt>null</tt> value indicates that the elements' <i>natural |
288 |
< |
* ordering</i> should be used. |
286 |
> |
* @param c the comparator by which the list is ordered. |
287 |
> |
* A <tt>null</tt> value indicates that the elements' |
288 |
> |
* {@linkplain Comparable natural ordering} should be used. |
289 |
|
* @return the index of the search key, if it is contained in the list; |
290 |
|
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The |
291 |
|
* <i>insertion point</i> is defined as the point at which the |
292 |
|
* key would be inserted into the list: the index of the first |
293 |
< |
* element greater than the key, or <tt>list.size()</tt>, if all |
293 |
> |
* element greater than the key, or <tt>list.size()</tt> if all |
294 |
|
* elements in the list are less than the specified key. Note |
295 |
|
* that this guarantees that the return value will be >= 0 if |
296 |
|
* and only if the key is found. |
297 |
|
* @throws ClassCastException if the list contains elements that are not |
298 |
|
* <i>mutually comparable</i> using the specified comparator, |
299 |
< |
* or the search key in not mutually comparable with the |
299 |
> |
* or the search key is not mutually comparable with the |
300 |
|
* elements of the list using this comparator. |
302 |
– |
* @see Comparable |
303 |
– |
* @see #sort(List, Comparator) |
301 |
|
*/ |
302 |
|
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { |
303 |
|
if (c==null) |
314 |
|
int high = l.size()-1; |
315 |
|
|
316 |
|
while (low <= high) { |
317 |
< |
int mid = (low + high) >> 1; |
317 |
> |
int mid = (low + high) >>> 1; |
318 |
|
T midVal = l.get(mid); |
319 |
|
int cmp = c.compare(midVal, key); |
320 |
|
|
334 |
|
ListIterator<? extends T> i = l.listIterator(); |
335 |
|
|
336 |
|
while (low <= high) { |
337 |
< |
int mid = (low + high) >> 1; |
337 |
> |
int mid = (low + high) >>> 1; |
338 |
|
T midVal = get(i, mid); |
339 |
|
int cmp = c.compare(midVal, key); |
340 |
|
|
405 |
|
* its list-iterator does not support the <tt>set</tt> operation. |
406 |
|
*/ |
407 |
|
public static void shuffle(List<?> list) { |
408 |
+ |
if (r == null) { |
409 |
+ |
r = new Random(); |
410 |
+ |
} |
411 |
|
shuffle(list, r); |
412 |
|
} |
413 |
< |
private static Random r = new Random(); |
413 |
> |
private static Random r; |
414 |
|
|
415 |
|
/** |
416 |
|
* Randomly permute the specified list using the specified source of |
569 |
|
Iterator<? extends T> i = coll.iterator(); |
570 |
|
T candidate = i.next(); |
571 |
|
|
572 |
< |
while(i.hasNext()) { |
572 |
> |
while (i.hasNext()) { |
573 |
|
T next = i.next(); |
574 |
|
if (next.compareTo(candidate) < 0) |
575 |
|
candidate = next; |
606 |
|
Iterator<? extends T> i = coll.iterator(); |
607 |
|
T candidate = i.next(); |
608 |
|
|
609 |
< |
while(i.hasNext()) { |
609 |
> |
while (i.hasNext()) { |
610 |
|
T next = i.next(); |
611 |
|
if (comp.compare(next, candidate) < 0) |
612 |
|
candidate = next; |
639 |
|
Iterator<? extends T> i = coll.iterator(); |
640 |
|
T candidate = i.next(); |
641 |
|
|
642 |
< |
while(i.hasNext()) { |
642 |
> |
while (i.hasNext()) { |
643 |
|
T next = i.next(); |
644 |
|
if (next.compareTo(candidate) > 0) |
645 |
|
candidate = next; |
676 |
|
Iterator<? extends T> i = coll.iterator(); |
677 |
|
T candidate = i.next(); |
678 |
|
|
679 |
< |
while(i.hasNext()) { |
679 |
> |
while (i.hasNext()) { |
680 |
|
T next = i.next(); |
681 |
|
if (comp.compare(next, candidate) > 0) |
682 |
|
candidate = next; |
1051 |
|
* @param s the set for which an unmodifiable view is to be returned. |
1052 |
|
* @return an unmodifiable view of the specified set. |
1053 |
|
*/ |
1054 |
– |
|
1054 |
|
public static <T> Set<T> unmodifiableSet(Set<? extends T> s) { |
1055 |
|
return new UnmodifiableSet<T>(s); |
1056 |
|
} |
1063 |
|
private static final long serialVersionUID = -9215047833775013803L; |
1064 |
|
|
1065 |
|
UnmodifiableSet(Set<? extends E> s) {super(s);} |
1066 |
< |
public boolean equals(Object o) {return c.equals(o);} |
1066 |
> |
public boolean equals(Object o) {return o == this || c.equals(o);} |
1067 |
|
public int hashCode() {return c.hashCode();} |
1068 |
|
} |
1069 |
|
|
1148 |
|
this.list = list; |
1149 |
|
} |
1150 |
|
|
1151 |
< |
public boolean equals(Object o) {return list.equals(o);} |
1151 |
> |
public boolean equals(Object o) {return o == this || list.equals(o);} |
1152 |
|
public int hashCode() {return list.hashCode();} |
1153 |
|
|
1154 |
|
public E get(int index) {return list.get(index);} |
1287 |
|
public V remove(Object key) { |
1288 |
|
throw new UnsupportedOperationException(); |
1289 |
|
} |
1290 |
< |
public void putAll(Map<? extends K, ? extends V> t) { |
1290 |
> |
public void putAll(Map<? extends K, ? extends V> m) { |
1291 |
|
throw new UnsupportedOperationException(); |
1292 |
|
} |
1293 |
|
public void clear() { |
1316 |
|
return values; |
1317 |
|
} |
1318 |
|
|
1319 |
< |
public boolean equals(Object o) {return m.equals(o);} |
1319 |
> |
public boolean equals(Object o) {return o == this || m.equals(o);} |
1320 |
|
public int hashCode() {return m.hashCode();} |
1321 |
|
public String toString() {return m.toString();} |
1322 |
|
|
1362 |
|
// We don't pass a to c.toArray, to avoid window of |
1363 |
|
// vulnerability wherein an unscrupulous multithreaded client |
1364 |
|
// could get his hands on raw (unwrapped) Entries from c. |
1365 |
< |
Object[] arr = |
1367 |
< |
c.toArray( |
1368 |
< |
a.length==0 ? a : |
1369 |
< |
(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), 0)); |
1365 |
> |
Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); |
1366 |
|
|
1367 |
|
for (int i=0; i<arr.length; i++) |
1368 |
|
arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]); |
1539 |
|
// use serialVersionUID from JDK 1.2.2 for interoperability |
1540 |
|
private static final long serialVersionUID = 3053995032091335093L; |
1541 |
|
|
1542 |
< |
final Collection<E> c; // Backing Collection |
1543 |
< |
final Object mutex; // Object on which to synchronize |
1542 |
> |
final Collection<E> c; // Backing Collection |
1543 |
> |
final Object mutex; // Object on which to synchronize |
1544 |
|
|
1545 |
|
SynchronizedCollection(Collection<E> c) { |
1546 |
|
if (c==null) |
2217 |
|
public Object[] toArray() { return c.toArray(); } |
2218 |
|
public <T> T[] toArray(T[] a) { return c.toArray(a); } |
2219 |
|
public String toString() { return c.toString(); } |
2224 |
– |
public Iterator<E> iterator() { return c.iterator(); } |
2220 |
|
public boolean remove(Object o) { return c.remove(o); } |
2221 |
|
public boolean containsAll(Collection<?> coll) { |
2222 |
|
return c.containsAll(coll); |
2231 |
|
c.clear(); |
2232 |
|
} |
2233 |
|
|
2234 |
< |
public boolean add(E e){ |
2234 |
> |
public Iterator<E> iterator() { |
2235 |
> |
return new Iterator<E>() { |
2236 |
> |
private final Iterator<E> it = c.iterator(); |
2237 |
> |
public boolean hasNext() { return it.hasNext(); } |
2238 |
> |
public E next() { return it.next(); } |
2239 |
> |
public void remove() { it.remove(); }}; |
2240 |
> |
} |
2241 |
> |
|
2242 |
> |
public boolean add(E e){ |
2243 |
|
typeCheck(e); |
2244 |
|
return c.add(e); |
2245 |
|
} |
2249 |
|
* Dump coll into an array of the required type. This serves |
2250 |
|
* three purposes: it insulates us from concurrent changes in |
2251 |
|
* the contents of coll, it type-checks all of the elements in |
2252 |
< |
* coll, and it provides all-or-nothing semantics(which we |
2252 |
> |
* coll, and it provides all-or-nothing semantics (which we |
2253 |
|
* wouldn't get if we type-checked each element as we added it). |
2254 |
|
*/ |
2255 |
|
E[] a = null; |
2256 |
|
try { |
2257 |
|
a = coll.toArray(zeroLengthElementArray()); |
2258 |
< |
} catch(ArrayStoreException e) { |
2258 |
> |
} catch (ArrayStoreException e) { |
2259 |
|
throw new ClassCastException(); |
2260 |
|
} |
2261 |
|
|
2314 |
|
|
2315 |
|
CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); } |
2316 |
|
|
2317 |
< |
public boolean equals(Object o) { return c.equals(o); } |
2317 |
> |
public boolean equals(Object o) { return o == this || c.equals(o); } |
2318 |
|
public int hashCode() { return c.hashCode(); } |
2319 |
|
} |
2320 |
|
|
2417 |
|
this.list = list; |
2418 |
|
} |
2419 |
|
|
2420 |
< |
public boolean equals(Object o) { return list.equals(o); } |
2420 |
> |
public boolean equals(Object o) { return o == this || list.equals(o); } |
2421 |
|
public int hashCode() { return list.hashCode(); } |
2422 |
|
public E get(int index) { return list.get(index); } |
2423 |
|
public E remove(int index) { return list.remove(index); } |
2439 |
|
E[] a = null; |
2440 |
|
try { |
2441 |
|
a = c.toArray(zeroLengthElementArray()); |
2442 |
< |
} catch(ArrayStoreException e) { |
2442 |
> |
} catch (ArrayStoreException e) { |
2443 |
|
throw new ClassCastException(); |
2444 |
|
} |
2445 |
|
|
2571 |
|
public void clear() { m.clear(); } |
2572 |
|
public Set<K> keySet() { return m.keySet(); } |
2573 |
|
public Collection<V> values() { return m.values(); } |
2574 |
< |
public boolean equals(Object o) { return m.equals(o); } |
2574 |
> |
public boolean equals(Object o) { return o == this || m.equals(o); } |
2575 |
|
public int hashCode() { return m.hashCode(); } |
2576 |
|
public String toString() { return m.toString(); } |
2577 |
|
|
2585 |
|
K[] keys = null; |
2586 |
|
try { |
2587 |
|
keys = t.keySet().toArray(zeroLengthKeyArray()); |
2588 |
< |
} catch(ArrayStoreException e) { |
2588 |
> |
} catch (ArrayStoreException e) { |
2589 |
|
throw new ClassCastException(); |
2590 |
|
} |
2591 |
|
V[] values = null; |
2592 |
|
try { |
2593 |
|
values = t.values().toArray(zeroLengthValueArray()); |
2594 |
< |
} catch(ArrayStoreException e) { |
2594 |
> |
} catch (ArrayStoreException e) { |
2595 |
|
throw new ClassCastException(); |
2596 |
|
} |
2597 |
|
|
2703 |
|
// We don't pass a to s.toArray, to avoid window of |
2704 |
|
// vulnerability wherein an unscrupulous multithreaded client |
2705 |
|
// could get his hands on raw (unwrapped) Entries from s. |
2706 |
< |
Object[] arr = s.toArray(a.length==0 ? a : |
2704 |
< |
(T[])Array.newInstance(a.getClass().getComponentType(), 0)); |
2706 |
> |
Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); |
2707 |
|
|
2708 |
|
for (int i=0; i<arr.length; i++) |
2709 |
|
arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i], |
3199 |
|
* @see List#addAll(int, Collection) |
3200 |
|
*/ |
3201 |
|
public static <T> List<T> nCopies(int n, T o) { |
3202 |
+ |
if (n < 0) |
3203 |
+ |
throw new IllegalArgumentException("List length = " + n); |
3204 |
|
return new CopiesList<T>(n, o); |
3205 |
|
} |
3206 |
|
|
3213 |
|
{ |
3214 |
|
static final long serialVersionUID = 2739099268398711800L; |
3215 |
|
|
3216 |
< |
int n; |
3217 |
< |
E element; |
3216 |
> |
final int n; |
3217 |
> |
final E element; |
3218 |
|
|
3219 |
|
CopiesList(int n, E e) { |
3220 |
< |
if (n < 0) |
3217 |
< |
throw new IllegalArgumentException("List length = " + n); |
3220 |
> |
assert n >= 0; |
3221 |
|
this.n = n; |
3222 |
|
element = e; |
3223 |
|
} |
3230 |
|
return n != 0 && eq(obj, element); |
3231 |
|
} |
3232 |
|
|
3233 |
+ |
public int indexOf(Object o) { |
3234 |
+ |
return contains(o) ? 0 : -1; |
3235 |
+ |
} |
3236 |
+ |
|
3237 |
+ |
public int lastIndexOf(Object o) { |
3238 |
+ |
return contains(o) ? n - 1 : -1; |
3239 |
+ |
} |
3240 |
+ |
|
3241 |
|
public E get(int index) { |
3242 |
< |
if (index<0 || index>=n) |
3242 |
> |
if (index < 0 || index >= n) |
3243 |
|
throw new IndexOutOfBoundsException("Index: "+index+ |
3244 |
|
", Size: "+n); |
3245 |
|
return element; |
3246 |
|
} |
3247 |
+ |
|
3248 |
+ |
public Object[] toArray() { |
3249 |
+ |
final Object[] a = new Object[n]; |
3250 |
+ |
if (element != null) |
3251 |
+ |
Arrays.fill(a, 0, n, element); |
3252 |
+ |
return a; |
3253 |
+ |
} |
3254 |
+ |
|
3255 |
+ |
public <T> T[] toArray(T[] a) { |
3256 |
+ |
final int n = this.n; |
3257 |
+ |
if (a.length < n) { |
3258 |
+ |
a = (T[])java.lang.reflect.Array |
3259 |
+ |
.newInstance(a.getClass().getComponentType(), n); |
3260 |
+ |
if (element != null) |
3261 |
+ |
Arrays.fill(a, 0, n, element); |
3262 |
+ |
} else { |
3263 |
+ |
Arrays.fill(a, 0, n, element); |
3264 |
+ |
if (a.length > n) |
3265 |
+ |
a[n] = null; |
3266 |
+ |
} |
3267 |
+ |
return a; |
3268 |
+ |
} |
3269 |
+ |
|
3270 |
+ |
public List<E> subList(int fromIndex, int toIndex) { |
3271 |
+ |
if (fromIndex < 0) |
3272 |
+ |
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); |
3273 |
+ |
if (toIndex > n) |
3274 |
+ |
throw new IndexOutOfBoundsException("toIndex = " + toIndex); |
3275 |
+ |
if (fromIndex > toIndex) |
3276 |
+ |
throw new IllegalArgumentException("fromIndex(" + fromIndex + |
3277 |
+ |
") > toIndex(" + toIndex + ")"); |
3278 |
+ |
return new CopiesList(toIndex - fromIndex, element); |
3279 |
+ |
} |
3280 |
|
} |
3281 |
|
|
3282 |
|
/** |
3316 |
|
public int compare(Comparable<Object> c1, Comparable<Object> c2) { |
3317 |
|
return c2.compareTo(c1); |
3318 |
|
} |
3319 |
+ |
|
3320 |
+ |
private Object readResolve() { return reverseOrder(); } |
3321 |
|
} |
3322 |
|
|
3323 |
|
/** |
3336 |
|
*/ |
3337 |
|
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) { |
3338 |
|
if (cmp == null) |
3339 |
< |
return new ReverseComparator(); // Unchecked warning!! |
3339 |
> |
return reverseOrder(); |
3340 |
|
|
3341 |
|
return new ReverseComparator2<T>(cmp); |
3342 |
|
} |
3503 |
|
* </pre> |
3504 |
|
* |
3505 |
|
* @param c the collection into which <tt>elements</tt> are to be inserted |
3506 |
< |
* @param a the elements to insert into <tt>c</tt> |
3506 |
> |
* @param elements the elements to insert into <tt>c</tt> |
3507 |
|
* @return <tt>true</tt> if the collection changed as a result of the call |
3508 |
|
* @throws UnsupportedOperationException if <tt>c</tt> does not support |
3509 |
< |
* the <tt>add</tt> operation. |
3509 |
> |
* the <tt>add</tt> operation |
3510 |
|
* @throws NullPointerException if <tt>elements</tt> contains one or more |
3511 |
< |
* null values and <tt>c</tt> does not support null elements, or |
3511 |
> |
* null values and <tt>c</tt> does not permit null elements, or |
3512 |
|
* if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt> |
3513 |
< |
* @throws IllegalArgumentException if some aspect of a value in |
3513 |
> |
* @throws IllegalArgumentException if some property of a value in |
3514 |
|
* <tt>elements</tt> prevents it from being added to <tt>c</tt> |
3515 |
|
* @see Collection#addAll(Collection) |
3516 |
|
* @since 1.5 |
3517 |
|
*/ |
3518 |
< |
public static <T> boolean addAll(Collection<? super T> c, T... a) { |
3518 |
> |
public static <T> boolean addAll(Collection<? super T> c, T... elements) { |
3519 |
|
boolean result = false; |
3520 |
< |
for (T e : a) |
3521 |
< |
result |= c.add(e); |
3520 |
> |
for (T element : elements) |
3521 |
> |
result |= c.add(element); |
3522 |
|
return result; |
3523 |
|
} |
3524 |
|
|
3542 |
|
* to this method, and no reference to the map is retained, as illustrated |
3543 |
|
* in the following code fragment: |
3544 |
|
* <pre> |
3545 |
< |
* Set<Object> weakHashSet = Collections.asSet( |
3545 |
> |
* Set<Object> weakHashSet = Collections.newSetFromMap( |
3546 |
|
* new WeakHashMap<Object, Boolean>()); |
3547 |
|
* </pre> |
3548 |
|
* |
3549 |
|
* @param map the backing map |
3550 |
|
* @return the set backed by the map |
3551 |
|
* @throws IllegalArgumentException if <tt>map</tt> is not empty |
3552 |
+ |
* @since 1.6 |
3553 |
|
*/ |
3554 |
< |
public static <E> Set<E> asSet(Map<E, Boolean> map) { |
3555 |
< |
return new MapAsSet<E>(map); |
3554 |
> |
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { |
3555 |
> |
return new SetFromMap<E>(map); |
3556 |
|
} |
3557 |
|
|
3558 |
< |
private static class MapAsSet<E> extends AbstractSet<E> |
3558 |
> |
private static class SetFromMap<E> extends AbstractSet<E> |
3559 |
|
implements Set<E>, Serializable |
3560 |
|
{ |
3561 |
|
private final Map<E, Boolean> m; // The backing map |
3562 |
< |
private transient Set<E> keySet; // Its keySet |
3562 |
> |
private transient Set<E> s; // Its keySet |
3563 |
|
|
3564 |
< |
MapAsSet(Map<E, Boolean> map) { |
3564 |
> |
SetFromMap(Map<E, Boolean> map) { |
3565 |
|
if (!map.isEmpty()) |
3566 |
|
throw new IllegalArgumentException("Map is non-empty"); |
3567 |
|
m = map; |
3568 |
< |
keySet = map.keySet(); |
3568 |
> |
s = map.keySet(); |
3569 |
|
} |
3570 |
|
|
3571 |
+ |
public void clear() { m.clear(); } |
3572 |
|
public int size() { return m.size(); } |
3573 |
|
public boolean isEmpty() { return m.isEmpty(); } |
3574 |
|
public boolean contains(Object o) { return m.containsKey(o); } |
3527 |
– |
public Iterator<E> iterator() { return keySet.iterator(); } |
3528 |
– |
public Object[] toArray() { return keySet.toArray(); } |
3529 |
– |
public <T> T[] toArray(T[] a) { return keySet.toArray(a); } |
3530 |
– |
public boolean add(E e) { |
3531 |
– |
return m.put(e, Boolean.TRUE) == null; |
3532 |
– |
} |
3575 |
|
public boolean remove(Object o) { return m.remove(o) != null; } |
3576 |
< |
|
3577 |
< |
public boolean removeAll(Collection<?> c) { |
3578 |
< |
return keySet.removeAll(c); |
3579 |
< |
} |
3580 |
< |
public boolean retainAll(Collection<?> c) { |
3581 |
< |
return keySet.retainAll(c); |
3582 |
< |
} |
3583 |
< |
public void clear() { m.clear(); } |
3584 |
< |
public boolean equals(Object o) { return keySet.equals(o); } |
3585 |
< |
public int hashCode() { return keySet.hashCode(); } |
3576 |
> |
public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } |
3577 |
> |
public Iterator<E> iterator() { return s.iterator(); } |
3578 |
> |
public Object[] toArray() { return s.toArray(); } |
3579 |
> |
public <T> T[] toArray(T[] a) { return s.toArray(a); } |
3580 |
> |
public String toString() { return s.toString(); } |
3581 |
> |
public int hashCode() { return s.hashCode(); } |
3582 |
> |
public boolean equals(Object o) { return o == this || s.equals(o); } |
3583 |
> |
public boolean containsAll(Collection<?> c) {return s.containsAll(c);} |
3584 |
> |
public boolean removeAll(Collection<?> c) {return s.removeAll(c);} |
3585 |
> |
public boolean retainAll(Collection<?> c) {return s.retainAll(c);} |
3586 |
> |
// addAll is the only inherited implementation |
3587 |
|
|
3588 |
|
private static final long serialVersionUID = 2454657854757543876L; |
3589 |
|
|
3590 |
< |
private void readObject(java.io.ObjectInputStream s) |
3590 |
> |
private void readObject(java.io.ObjectInputStream stream) |
3591 |
|
throws IOException, ClassNotFoundException |
3592 |
|
{ |
3593 |
< |
s.defaultReadObject(); |
3594 |
< |
keySet = m.keySet(); |
3593 |
> |
stream.defaultReadObject(); |
3594 |
> |
s = m.keySet(); |
3595 |
|
} |
3596 |
|
} |
3597 |
|
|
3601 |
|
* <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This |
3602 |
|
* view can be useful when you would like to use a method |
3603 |
|
* requiring a <tt>Queue</tt> but you need Lifo ordering. |
3604 |
< |
* @param deque the Deque |
3604 |
> |
* |
3605 |
> |
* <p>Each method invocation on the queue returned by this method |
3606 |
> |
* results in exactly one method invocation on the backing deque, with |
3607 |
> |
* one exception. The {@link Queue#addAll addAll} method is |
3608 |
> |
* implemented as a sequence of {@link Deque#addFirst addFirst} |
3609 |
> |
* invocations on the backing deque. |
3610 |
> |
* |
3611 |
> |
* @param deque the deque |
3612 |
|
* @return the queue |
3613 |
|
* @since 1.6 |
3614 |
|
*/ |
3618 |
|
|
3619 |
|
static class AsLIFOQueue<E> extends AbstractQueue<E> |
3620 |
|
implements Queue<E>, Serializable { |
3621 |
+ |
private static final long serialVersionUID = 1802017725587941708L; |
3622 |
|
private final Deque<E> q; |
3623 |
< |
AsLIFOQueue(Deque<E> q) { this.q = q; } |
3624 |
< |
public boolean offer(E e) { return q.offerFirst(e); } |
3625 |
< |
public E poll() { return q.pollFirst(); } |
3626 |
< |
public E remove() { return q.removeFirst(); } |
3627 |
< |
public E peek() { return q.peekFirst(); } |
3628 |
< |
public E element() { return q.getFirst(); } |
3629 |
< |
public int size() { return q.size(); } |
3630 |
< |
public boolean isEmpty() { return q.isEmpty(); } |
3631 |
< |
public boolean contains(Object o) { return q.contains(o); } |
3632 |
< |
public Iterator<E> iterator() { return q.iterator(); } |
3633 |
< |
public Object[] toArray() { return q.toArray(); } |
3634 |
< |
public <T> T[] toArray(T[] a) { return q.toArray(a); } |
3635 |
< |
public boolean add(E e) { return q.offerFirst(e); } |
3636 |
< |
public boolean remove(Object o) { return q.remove(o); } |
3637 |
< |
public void clear() { q.clear(); } |
3623 |
> |
AsLIFOQueue(Deque<E> q) { this.q = q; } |
3624 |
> |
public boolean add(E e) { q.addFirst(e); return true; } |
3625 |
> |
public boolean offer(E e) { return q.offerFirst(e); } |
3626 |
> |
public E poll() { return q.pollFirst(); } |
3627 |
> |
public E remove() { return q.removeFirst(); } |
3628 |
> |
public E peek() { return q.peekFirst(); } |
3629 |
> |
public E element() { return q.getFirst(); } |
3630 |
> |
public void clear() { q.clear(); } |
3631 |
> |
public int size() { return q.size(); } |
3632 |
> |
public boolean isEmpty() { return q.isEmpty(); } |
3633 |
> |
public boolean contains(Object o) { return q.contains(o); } |
3634 |
> |
public boolean remove(Object o) { return q.remove(o); } |
3635 |
> |
public Iterator<E> iterator() { return q.iterator(); } |
3636 |
> |
public Object[] toArray() { return q.toArray(); } |
3637 |
> |
public <T> T[] toArray(T[] a) { return q.toArray(a); } |
3638 |
> |
public String toString() { return q.toString(); } |
3639 |
> |
public boolean containsAll(Collection<?> c) {return q.containsAll(c);} |
3640 |
> |
public boolean removeAll(Collection<?> c) {return q.removeAll(c);} |
3641 |
> |
public boolean retainAll(Collection<?> c) {return q.retainAll(c);} |
3642 |
> |
// We use inherited addAll; forwarding addAll would be wrong |
3643 |
|
} |
3644 |
|
} |