1 /*
2 * Copyright (c) 2005, 2025, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464
27 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753
28 * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215
29 * 4802647 7123424 8024709 8193128 8327858
30 * @summary Run many tests on many Collection and Map implementations
31 * @author Martin Buchholz
32 * @modules java.base/java.util:open
33 * @enablePreview
34 * @run main MOAT
35 * @key randomness
36 */
37
38 /* Mother Of All (Collection) Tests
39 *
40 * Testing of collection classes is often spotty, because many tests
41 * need to be performed on many implementations, but the onus on
42 * writing the tests falls on the engineer introducing the new
43 * implementation.
44 *
45 * The idea of this mega-test is that:
46 *
47 * An engineer adding a new collection implementation could simply add
48 * their new implementation to a list of implementations in this
49 * test's main method. Any general purpose Collection<Integer> or
50 * Map<Integer,Integer> class is appropriate.
51 *
52 * An engineer fixing a regression could add their regression test here and
53 * simultaneously test all other implementations.
54 */
55
56 import java.io.*;
57 import java.util.*;
58 import java.util.concurrent.*;
59 import static java.util.Collections.*;
60 import java.lang.reflect.*;
61 import java.util.stream.Collectors;
62 import java.util.stream.Stream;
63
64 public class MOAT {
65 // Collections under test must not be initialized to contain this value,
66 // and maps under test must not contain this value as a key.
67 // It's used as a sentinel for absent-element testing.
68 static final int ABSENT_VALUE = 778347983;
69
70 static final Integer[] integerArray;
71 static {
72 Integer[] ia = new Integer[20];
73 // fill with 1..20 inclusive
74 for (int i = 0; i < ia.length; i++) {
75 ia[i] = i + 1;
76 }
77 integerArray = ia;
78 }
79
80 public static void realMain(String[] args) {
81
82 testCollection(new NewAbstractCollection<Integer>());
83 testCollection(new NewAbstractSet<Integer>());
84 testCollection(new LinkedHashSet<Integer>());
85 testCollection(new HashSet<Integer>());
86 testCollection(new Vector<Integer>());
87 testCollection(new Vector<Integer>().subList(0,0));
88 testCollection(new ArrayDeque<Integer>());
89 testCollection(new ArrayList<Integer>());
90 testCollection(new ArrayList<Integer>().subList(0,0));
91 testCollection(new LinkedList<Integer>());
92 testCollection(new LinkedList<Integer>().subList(0,0));
93 testCollection(new TreeSet<Integer>());
94 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
95 testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
96 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
97 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
98 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
99 testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
100 testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));
101 testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>()));
102
103 testCollection(new CopyOnWriteArrayList<Integer>());
104 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
105 testCollection(new CopyOnWriteArraySet<Integer>());
106 testCollection(new PriorityQueue<Integer>());
107 testCollection(new PriorityBlockingQueue<Integer>());
108 testCollection(new ArrayBlockingQueue<Integer>(20));
109 testCollection(new LinkedBlockingQueue<Integer>(20));
110 testCollection(new LinkedBlockingDeque<Integer>(20));
111 testCollection(new ConcurrentLinkedDeque<Integer>());
112 testCollection(new ConcurrentLinkedQueue<Integer>());
113 testCollection(new LinkedTransferQueue<Integer>());
114 testCollection(new ConcurrentSkipListSet<Integer>());
115 testCollection(Arrays.asList(new Integer(42)));
116 testCollection(Arrays.asList(1,2,3));
117 testCollection(nCopies(25,1));
118 testImmutableList(nCopies(25,1));
119
120 testMap(new HashMap<Integer,Integer>());
121 testMap(new LinkedHashMap<Integer,Integer>());
122
123 // TODO: Add reliable support for WeakHashMap.
124 // This test is subject to very rare failures because the GC
125 // may remove unreferenced-keys from the map at any time.
126 // testMap(new WeakHashMap<Integer,Integer>());
127
128 testMap(new IdentityHashMap<Integer,Integer>());
129 testMap(new TreeMap<Integer,Integer>());
130 testMap(new Hashtable<Integer,Integer>());
131 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
132 testMap(new ConcurrentSkipListMap<Integer,Integer>());
133 testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));
134 testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
135 testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
136 testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));
137 testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));
138 testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));
139
140 // Unmodifiable wrappers
141 testImmutableSet(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))), 99);
142 testImmutableSet(AccessFlag.maskToAccessFlags(0, AccessFlag.Location.CLASS), AccessFlag.ABSTRACT);
143 testImmutableSet(AccessFlag.maskToAccessFlags(Modifier.PUBLIC | Modifier.STATIC | Modifier.SYNCHRONIZED, AccessFlag.Location.METHOD), AccessFlag.ABSTRACT);
144 testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
145 testImmutableMap(unmodifiableMap(Collections.singletonMap(1,2)));
146 testImmutableSeqColl(unmodifiableSequencedCollection(Arrays.asList(1,2,3)), 99);
147 testImmutableSeqColl(unmodifiableSequencedSet(new LinkedHashSet<>(Arrays.asList(1,2,3))), 99);
148 var lhm = new LinkedHashMap<Integer,Integer>(); lhm.put(1,2); lhm.put(3, 4);
149 testImmutableSeqMap(unmodifiableSequencedMap(lhm));
150 testCollMutatorsAlwaysThrow(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))));
151 testCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));
152 testEmptyCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));
153 testListMutatorsAlwaysThrow(unmodifiableList(Arrays.asList(1,2,3)));
154 testListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));
155 testEmptyListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));
156 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.singletonMap(1,2)));
157 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));
158 testEmptyMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));
159
160 // Empty collections
161 final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
162 testCollection(emptyArray);
163 testEmptyList(emptyArray);
164 THROWS(IndexOutOfBoundsException.class, () -> emptyArray.set(0,1));
165 THROWS(UnsupportedOperationException.class, () -> emptyArray.add(0,1));
166
167 List<Integer> noOne = nCopies(0,1);
168 testCollection(noOne);
169 testEmptyList(noOne);
170 testImmutableList(noOne);
171
172 Set<Integer> emptySet = emptySet();
173 testCollection(emptySet);
174 testEmptySet(emptySet);
175 testEmptySet(EMPTY_SET);
176 testEmptySet(Collections.emptySet());
177 testEmptySet(Collections.emptySortedSet());
178 testEmptySet(Collections.emptyNavigableSet());
179 testImmutableSet(emptySet, 99);
180
181 List<Integer> emptyList = emptyList();
182 testCollection(emptyList);
183 testEmptyList(emptyList);
184 testEmptyList(EMPTY_LIST);
185 testEmptyList(Collections.emptyList());
186 testImmutableList(emptyList);
187
188 Map<Integer,Integer> emptyMap = emptyMap();
189 testMap(emptyMap);
190 testEmptyMap(emptyMap);
191 testEmptyMap(EMPTY_MAP);
192 testEmptyMap(Collections.emptyMap());
193 testEmptyMap(Collections.emptySortedMap());
194 testEmptyMap(Collections.emptyNavigableMap());
195 testImmutableMap(emptyMap);
196 testImmutableMap(Collections.emptyMap());
197 testImmutableMap(Collections.emptySortedMap());
198 testImmutableMap(Collections.emptyNavigableMap());
199
200 // Singleton collections
201 Set<Integer> singletonSet = singleton(1);
202 equal(singletonSet.size(), 1);
203 testCollection(singletonSet);
204 testImmutableSet(singletonSet, 99);
205
206 List<Integer> singletonList = singletonList(1);
207 equal(singletonList.size(), 1);
208 testCollection(singletonList);
209 testImmutableList(singletonList);
210 testImmutableList(singletonList.subList(0,1));
211 testImmutableList(singletonList.subList(0,1).subList(0,1));
212 testEmptyList(singletonList.subList(0,0));
213 testEmptyList(singletonList.subList(0,0).subList(0,0));
214
215 Map<Integer,Integer> singletonMap = singletonMap(1,2);
216 equal(singletonMap.size(), 1);
217 testMap(singletonMap);
218 testImmutableMap(singletonMap);
219
220 // Immutable List
221 testEmptyList(List.of());
222 testEmptyList(List.of().subList(0,0));
223 testEmptyList(StableValue.list(0, i -> i));
224 testEmptyList(StableValue.list(3, i -> i).subList(0, 0));
225 testListMutatorsAlwaysThrow(List.of());
226 testListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
227 testListMutatorsAlwaysThrow(StableValue.list(0, i -> i));
228 testEmptyListMutatorsAlwaysThrow(List.of());
229 testEmptyListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
230 testEmptyListMutatorsAlwaysThrow(StableValue.list(0, i -> i));
231 testEmptyListMutatorsAlwaysThrow(StableValue.list(3, i -> i).subList(0, 0));
232 for (List<Integer> list : Arrays.asList(
233 List.<Integer>of(),
234 List.of(1),
235 List.of(1, 2),
236 List.of(1, 2, 3),
237 List.of(1, 2, 3, 4),
238 List.of(1, 2, 3, 4, 5),
239 List.of(1, 2, 3, 4, 5, 6),
240 List.of(1, 2, 3, 4, 5, 6, 7),
241 List.of(1, 2, 3, 4, 5, 6, 7, 8),
242 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
243 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
244 List.of(integerArray),
245 Stream.<Integer>empty().toList(),
246 Stream.of(1).toList(),
247 Stream.of(1, 2).toList(),
248 Stream.of(1, 2, 3).toList(),
249 Stream.of(1, 2, 3, 4).toList(),
250 Stream.of((Integer)null).toList(),
251 Stream.of(1, null).toList(),
252 Stream.of(1, null, 3).toList(),
253 Stream.of(1, null, 3, 4).toList(),
254 StableValue.list(0, i -> i),
255 StableValue.list(3, i -> i),
256 StableValue.list(10, i -> i))) {
257 testCollection(list);
258 testImmutableList(list);
259 testListMutatorsAlwaysThrow(list);
260 testImmutableListMutatorsAlwaysThrow(list);
261 if (list.size() >= 1) {
262 // test subLists
263 List<Integer> headList = list.subList(0, list.size() - 1);
264 List<Integer> tailList = list.subList(1, list.size());
265 testCollection(headList);
266 testCollection(tailList);
267 testImmutableList(headList);
268 testImmutableList(tailList);
269 testListMutatorsAlwaysThrow(headList);
270 testListMutatorsAlwaysThrow(tailList);
271 }
272 }
273
274 List<Integer> listCopy = List.copyOf(Arrays.asList(1, 2, 3));
275 testCollection(listCopy);
276 testImmutableList(listCopy);
277 testListMutatorsAlwaysThrow(listCopy);
278
279 List<Integer> listCollected = Stream.of(1, 2, 3).collect(Collectors.toUnmodifiableList());
280 equal(listCollected, List.of(1, 2, 3));
281 testCollection(listCollected);
282 testImmutableList(listCollected);
283 testListMutatorsAlwaysThrow(listCollected);
284
285 // List indexOf / lastIndexOf
286
287 // 0 element
288 System.out.println("testListIndexOf size 0");
289 testListIndexOf(-1, -1);
290
291 System.out.println("testListIndexOf size 1");
292 testListIndexOf(-1, -1, 0);
293 testListIndexOf(0, 0, 1);
294
295 System.out.println("testListIndexOf size 2");
296 testListIndexOf(-1, -1, 0, 0);
297 testListIndexOf(0, 0, 1, 0);
298 testListIndexOf(0, 1, 1, 1);
299 testListIndexOf(1, 1, 0, 1);
300
301
302 System.out.println("testListIndexOf size 3");
303 testListIndexOf(-1, -1, 0, 0, 0);
304 testListIndexOf(0, 0, 1, 0, 0);
305 testListIndexOf(0, 1, 1, 1, 0);
306 testListIndexOf(1, 2, 0, 1, 1);
307 testListIndexOf(2, 2, 0, 0, 1);
308
309 System.out.println("testListIndexOf size N");
310 testListIndexOf(-1, -1, 0, 0, 0, 0, 0, 0, 0);
311 testListIndexOf(2, 6, 0, 0, 1, 0, 1, 0, 1);
312 testListIndexOf(4, 4, 0, 0, 0, 0, 1, 0, 0);
313 testListIndexOf(0, 6, 1, 1, 1, 1, 1, 1, 1);
314 testListIndexOf(0, 7, 1, 1, 1, 1, 1, 1, 1, 1);
315 testListIndexOf(0, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1);
316 testListIndexOf(0, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
317 testListIndexOf(0, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
318 testListIndexOf(0, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
319 testListIndexOf(0, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
320 testListIndexOf(12, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1);
321 testListIndexOf(-1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
322
323 // Immutable Set
324 testEmptySet(Set.of());
325 testCollMutatorsAlwaysThrow(Set.of());
326 testEmptyCollMutatorsAlwaysThrow(Set.of());
327 for (Set<Integer> set : Arrays.asList(
328 Set.<Integer>of(),
329 Set.of(1),
330 Set.of(1, 2),
331 Set.of(1, 2, 3),
332 Set.of(1, 2, 3, 4),
333 Set.of(1, 2, 3, 4, 5),
334 Set.of(1, 2, 3, 4, 5, 6),
335 Set.of(1, 2, 3, 4, 5, 6, 7),
336 Set.of(1, 2, 3, 4, 5, 6, 7, 8),
337 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
338 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
339 Set.of(integerArray))) {
340 testCollection(set);
341 testImmutableSet(set, 99);
342 testCollMutatorsAlwaysThrow(set);
343 }
344
345 Set<Integer> setCopy = Set.copyOf(Arrays.asList(1, 2, 3));
346 testCollection(setCopy);
347 testImmutableSet(setCopy, 99);
348 testCollMutatorsAlwaysThrow(setCopy);
349
350 Set<Integer> setCollected = Stream.of(1, 1, 2, 3, 2, 3)
351 .collect(Collectors.toUnmodifiableSet());
352 equal(setCollected, Set.of(1, 2, 3));
353 testCollection(setCollected);
354 testImmutableSet(setCollected, 99);
355 testCollMutatorsAlwaysThrow(setCollected);
356
357 // Immutable Map
358
359 @SuppressWarnings("unchecked")
360 Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20];
361 for (int i = 0; i < ea.length; i++) {
362 ea[i] = Map.entry(i+1, i+101);
363 }
364
365 testEmptyMap(Map.of());
366 testMapMutatorsAlwaysThrow(Map.of());
367 testEmptyMapMutatorsAlwaysThrow(Map.of());
368 testEmptyMap(StableValue.map(Set.of(), k -> k));
369 testMapMutatorsAlwaysThrow(StableValue.map(Set.of(), k -> k));
370 testEmptyMapMutatorsAlwaysThrow(StableValue.map(Set.of(), k -> k));
371 for (Map<Integer,Integer> map : Arrays.asList(
372 Map.<Integer,Integer>of(),
373 Map.of(1, 101),
374 Map.of(1, 101, 2, 202),
375 Map.of(1, 101, 2, 202, 3, 303),
376 Map.of(1, 101, 2, 202, 3, 303, 4, 404),
377 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505),
378 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606),
379 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707),
380 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808),
381 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909),
382 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010),
383 Map.ofEntries(ea),
384 StableValue.map(Set.<Integer>of(), k -> k),
385 StableValue.map(Set.of(1), k -> k),
386 StableValue.map(Set.of(1, 2, 3), k -> k))) {
387 testMap(map);
388 testImmutableMap(map);
389 testMapMutatorsAlwaysThrow(map);
390 }
391
392 Map<Integer,Integer> mapCopy = Map.copyOf(new HashMap<>(Map.of(1, 101, 2, 202, 3, 303)));
393 testMap(mapCopy);
394 testImmutableMap(mapCopy);
395 testMapMutatorsAlwaysThrow(mapCopy);
396
397 Map<Integer,Integer> mapCollected1 =
398 Stream.of(1, 2, 3)
399 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i));
400 equal(mapCollected1, Map.of(1, 101, 2, 202, 3, 303));
401 testMap(mapCollected1);
402 testImmutableMap(mapCollected1);
403 testMapMutatorsAlwaysThrow(mapCollected1);
404
405 try {
406 Stream.of(1, 1, 2, 3, 2, 3)
407 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i));
408 fail("duplicates should have thrown an exception");
409 } catch (IllegalStateException ise) {
410 pass();
411 }
412
413 Map<Integer,Integer> mapCollected2 =
414 Stream.of(1, 1, 2, 3, 2, 3)
415 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i, Integer::sum));
416 equal(mapCollected2, Map.of(1, 202, 2, 404, 3, 606));
417 testMap(mapCollected2);
418 testImmutableMap(mapCollected2);
419 testMapMutatorsAlwaysThrow(mapCollected2);
420 }
421
422 private static void checkContainsSelf(Collection<Integer> c) {
423 check(c.containsAll(c));
424 check(c.containsAll(Arrays.asList(c.toArray())));
425 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
426 }
427
428 private static void checkContainsEmpty(Collection<Integer> c) {
429 check(c.containsAll(new ArrayList<Integer>()));
430 }
431
432 private static void checkUnique(Set<Integer> s) {
433 for (Integer i : s) {
434 int count = 0;
435 for (Integer j : s) {
436 if (Objects.equals(i,j))
437 ++count;
438 }
439 check(count == 1);
440 }
441 }
442
443 private static <T> void testEmptyCollection(Collection<T> c) {
444 check(c.isEmpty());
445 equal(c.size(), 0);
446 equal(c.toString(),"[]");
447 equal(c.toArray().length, 0);
448 equal(c.toArray(new Object[0]).length, 0);
449 equal(c.toArray(Object[]::new).length, 0);
450 check(c.toArray(new Object[]{42})[0] == null);
451
452 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
453 equal(c.toArray(a), a);
454 equal(a[0], null);
455 testEmptyIterator(c.iterator());
456 }
457
458 static <T> void testEmptyIterator(final Iterator<T> it) {
459 if (rnd.nextBoolean())
460 check(! it.hasNext());
461
462 THROWS(NoSuchElementException.class, () -> it.next());
463
464 try { it.remove(); }
465 catch (IllegalStateException ignored) { pass(); }
466 catch (UnsupportedOperationException ignored) { pass(); }
467 catch (Throwable t) { unexpected(t); }
468
469 if (rnd.nextBoolean())
470 check(! it.hasNext());
471 }
472
473 private static void testEmptyList(List<?> c) {
474 testEmptyCollection(c);
475 equal(c.hashCode(), 1);
476 equal2(c, Collections.<Integer>emptyList());
477 }
478
479 private static <T> void testEmptySet(Set<T> c) {
480 testEmptyCollection(c);
481 equal(c.hashCode(), 0);
482 equal2(c, Collections.<Integer>emptySet());
483 if (c instanceof NavigableSet<?>)
484 testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
485 }
486
487 private static <T> void testImmutableCollection(final Collection<T> c, T t) {
488 THROWS(UnsupportedOperationException.class,
489 () -> c.add(t),
490 () -> c.addAll(singleton(t)));
491 if (! c.isEmpty()) {
492 final T first = c.iterator().next();
493 THROWS(UnsupportedOperationException.class,
494 () -> c.clear(),
495 () -> c.remove(first),
496 () -> c.removeAll(singleton(first)),
497 () -> c.retainAll(emptyList()));
498 } else {
499 testEmptyIterator(c.iterator());
500 }
501 testForEachMatch(c);
502 testSpliteratorMatch(c);
503 }
504
505 private static <T> void testImmutableSeqColl(final SequencedCollection<T> c, T t) {
506 SequencedCollection<T> r = c.reversed();
507 testImmutableCollection(c, t);
508 testImmutableCollection(r, t);
509 THROWS(UnsupportedOperationException.class,
510 () -> c.addFirst(t),
511 () -> c.addLast(t),
512 () -> r.addFirst(t),
513 () -> r.addLast(t));
514 if (! c.isEmpty()) {
515 THROWS(UnsupportedOperationException.class,
516 () -> c.removeFirst(),
517 () -> c.removeLast(),
518 () -> r.removeFirst(),
519 () -> r.removeLast());
520 }
521 }
522
523 private static <T> void testImmutableSet(final Set<T> c, T t) {
524 testImmutableCollection(c, t);
525 }
526
527 private static <T> void testImmutableSeqSet(final SequencedSet<T> c, T t) {
528 testImmutableSeqColl(c, t);
529 }
530
531 private static void testImmutableList(final List<Integer> c) {
532 testList(c);
533 testImmutableCollection(c, 42);
534 testImmutableSeqColl(c, 42);
535 THROWS(UnsupportedOperationException.class,
536 () -> c.set(0,42),
537 () -> c.add(0,42),
538 () -> c.addAll(0,singleton(86)));
539 if (! c.isEmpty())
540 THROWS(UnsupportedOperationException.class,
541 () -> { Iterator<Integer> it = c.iterator();
542 it.next();
543 it.remove(); },
544 () -> { ListIterator<Integer> it = c.listIterator();
545 it.next();
546 it.remove(); });
547 }
548
549 /**
550 * Test that calling a mutator always throws UOE, even if the mutator
551 * wouldn't actually do anything, given its arguments.
552 *
553 * @param c the collection instance to test
554 */
555 private static void testCollMutatorsAlwaysThrow(Collection<Integer> c) {
556 THROWS(UnsupportedOperationException.class,
557 () -> c.addAll(Collections.emptyList()),
558 () -> c.remove(ABSENT_VALUE),
559 () -> c.removeAll(Collections.emptyList()),
560 () -> c.removeIf(x -> false),
561 () -> c.retainAll(c));
562 }
563
564 // Ensures forEach supplies in the same order as the iterator
565 private static <T> void testForEachMatch(Collection<T> c) {
566 var itr = c.iterator();
567 int[] index = {0};
568 c.forEach(item -> {
569 T itrNext = null;
570 if (!itr.hasNext() || !Objects.equals(itrNext = itr.next(), item)) {
571 fail("forEach and iterator mismatch at " + index[0] + " forEach: " + item + ", itr: " + itrNext);
572 }
573 index[0]++;
574 });
575 if (itr.hasNext()) {
576 fail("forEach and iterator mismatch at tail, extras in itr");
577 }
578 }
579
580 // Ensures spliterator returns in the same order as the iterator
581 private static <T> void testSpliteratorMatch(Collection<T> c) {
582 var itr = c.iterator();
583 var split = c.spliterator();
584 int[] index = {0};
585 split.forEachRemaining(item -> {
586 T itrNext = null;
587 if (!itr.hasNext() || !Objects.equals(itrNext = itr.next(), item)) {
588 fail("iterator and spliterator mismatch at " + index[0] + " spliterator: " + item + ", itr: " + itrNext);
589 }
590 index[0]++;
591 });
592 if (itr.hasNext()) {
593 fail("iterator and spliterator mismatch at tail, extra item in itr");
594 }
595 }
596
597 /**
598 * Test that calling a mutator always throws UOE, even if the mutator
599 * wouldn't actually do anything on an empty collection.
600 *
601 * @param c the collection instance to test, must be empty
602 */
603 private static void testEmptyCollMutatorsAlwaysThrow(Collection<Integer> c) {
604 if (! c.isEmpty()) {
605 fail("collection is not empty");
606 }
607 THROWS(UnsupportedOperationException.class,
608 () -> c.clear());
609 }
610
611 /**
612 * As above, for a list.
613 *
614 * @param c the list instance to test
615 */
616 private static void testListMutatorsAlwaysThrow(List<Integer> c) {
617 testCollMutatorsAlwaysThrow(c);
618 THROWS(UnsupportedOperationException.class,
619 () -> c.addAll(0, Collections.emptyList()));
620 }
621
622 private static void testImmutableListMutatorsAlwaysThrow(List<Integer> c) {
623 THROWS(UnsupportedOperationException.class,
624 c::removeFirst,
625 c::removeLast);
626 }
627
628 /**
629 * As above, for an empty list.
630 *
631 * @param c the list instance to test, must be empty
632 */
633 private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) {
634 if (! c.isEmpty()) {
635 fail("list is not empty");
636 }
637 testEmptyCollMutatorsAlwaysThrow(c);
638 THROWS(UnsupportedOperationException.class,
639 () -> c.replaceAll(x -> x),
640 () -> c.sort(null));
641 }
642
643 /**
644 * As above, for a map.
645 *
646 * @param m the map instance to test
647 */
648 private static void testMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
649 THROWS(UnsupportedOperationException.class,
650 () -> m.compute(ABSENT_VALUE, (k, v) -> null),
651 () -> m.computeIfAbsent(ABSENT_VALUE, k -> null),
652 () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null),
653 () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null),
654 () -> m.putAll(Collections.emptyMap()),
655 () -> m.remove(ABSENT_VALUE),
656 () -> m.remove(ABSENT_VALUE, 0),
657 () -> m.replace(ABSENT_VALUE, 0),
658 () -> m.replace(ABSENT_VALUE, 0, 1));
659 }
660
661 /**
662 * As above, for an empty map.
663 *
664 * @param map the map instance to test, must be empty
665 */
666 private static void testEmptyMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
667 if (! m.isEmpty()) {
668 fail("map is not empty");
669 }
670 THROWS(UnsupportedOperationException.class,
671 () -> m.clear(),
672 () -> m.replaceAll((k, v) -> v));
673 }
674
675 private static void clear(Collection<Integer> c) {
676 try { c.clear(); }
677 catch (Throwable t) { unexpected(t); }
678 testEmptyCollection(c);
679 }
680
681 private static <K,V> void testEmptyMap(final Map<K,V> m) {
682 check(m.isEmpty());
683 equal(m.size(), 0);
684 equal(m.toString(),"{}");
685 testEmptySet(m.keySet());
686 testEmptySet(m.entrySet());
687 testEmptyCollection(m.values());
688
689 try { check(! m.containsValue(null)); }
690 catch (NullPointerException ignored) { /* OK */ }
691 try { check(! m.containsKey(null)); }
692 catch (NullPointerException ignored) { /* OK */ }
693 check(! m.containsValue(1));
694 check(! m.containsKey(1));
695 }
696
697 private static void testImmutableMapEntry(final Map.Entry<Integer,Integer> me) {
698 Integer key = me.getKey();
699 Integer val = me.getValue();
700 THROWS(UnsupportedOperationException.class,
701 () -> me.setValue(3));
702 equal(key, me.getKey());
703 equal(val, me.getValue());
704 }
705
706 private static void testImmutableMap(final Map<Integer,Integer> m) {
707 THROWS(UnsupportedOperationException.class,
708 () -> m.put(1,1),
709 () -> m.putAll(singletonMap(1,1)));
710 if (! m.isEmpty()) {
711 final Integer first = m.keySet().iterator().next();
712 THROWS(UnsupportedOperationException.class,
713 () -> m.remove(first),
714 () -> m.clear());
715 testImmutableMapEntry(m.entrySet().iterator().next());
716 }
717 testImmutableSet(m.keySet(), 99);
718 testImmutableCollection(m.values(), 99);
719 testImmutableSet(m.entrySet(), Map.entry(42, 43));
720 }
721
722 private static void testImmutableSeqMap(final SequencedMap<Integer,Integer> m) {
723 SequencedMap<Integer,Integer> r = m.reversed();
724 testImmutableMap(m);
725 testImmutableMap(r);
726 THROWS(UnsupportedOperationException.class,
727 () -> m.putFirst(0, 0),
728 () -> m.putLast(0, 0),
729 () -> r.putFirst(0, 0),
730 () -> r.putLast(0, 0));
731 if (! m.isEmpty()) {
732 THROWS(UnsupportedOperationException.class,
733 () -> m.pollFirstEntry(),
734 () -> m.pollLastEntry(),
735 () -> r.pollFirstEntry(),
736 () -> r.pollLastEntry());
737 testImmutableMapEntry(m.sequencedEntrySet().getFirst());
738 testImmutableMapEntry(r.sequencedEntrySet().getFirst());
739 testImmutableMapEntry(m.sequencedEntrySet().reversed().getFirst());
740 testImmutableMapEntry(r.sequencedEntrySet().reversed().getFirst());
741 }
742 testImmutableSeqSet(m.sequencedKeySet(), 99);
743 testImmutableSeqColl(m.sequencedValues(), 99);
744 testImmutableSeqSet(m.sequencedEntrySet(), Map.entry(42, 43));
745 testImmutableSeqSet(r.sequencedKeySet(), 99);
746 testImmutableSeqColl(r.sequencedValues(), 99);
747 testImmutableSeqSet(r.sequencedEntrySet(), Map.entry(42, 43));
748 }
749
750 private static void clear(Map<?,?> m) {
751 try { m.clear(); }
752 catch (Throwable t) { unexpected(t); }
753 testEmptyMap(m);
754 }
755
756 private static void oneElement(Collection<Integer> c) {
757 clear(c);
758 try {
759 check(c.add(-42));
760 equal(c.toString(), "[-42]");
761 if (c instanceof Set) check(! c.add(-42));
762 } catch (Throwable t) { unexpected(t); }
763 check(! c.isEmpty()); check(c.size() == 1);
764 }
765
766 private static boolean supportsAdd(Collection<Integer> c) {
767 try { check(c.add(ABSENT_VALUE)); }
768 catch (UnsupportedOperationException t) { return false; }
769 catch (Throwable t) { unexpected(t); }
770
771 try {
772 check(c.contains(ABSENT_VALUE));
773 check(c.remove(ABSENT_VALUE));
774 } catch (Throwable t) { unexpected(t); }
775 return true;
776 }
777
778 private static boolean supportsRemove(Collection<Integer> c) {
779 try { check(! c.remove(ABSENT_VALUE)); }
780 catch (UnsupportedOperationException t) { return false; }
781 catch (Throwable t) { unexpected(t); }
782 return true;
783 }
784
785 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
786 // should be Object[].class
787 // Fixed in jdk9, but not jdk8 ...
788 static final boolean needToWorkAround6260652 =
789 Arrays.asList("").toArray().getClass() != Object[].class;
790
791 private static void checkFunctionalInvariants(Collection<Integer> c) {
792 try {
793 checkContainsSelf(c);
794 checkContainsEmpty(c);
795 check(c.size() != 0 ^ c.isEmpty());
796 check(! c.contains(ABSENT_VALUE));
797
798 {
799 int size = 0;
800 for (Integer i : c) size++;
801 check(c.size() == size);
802 }
803
804 if (c instanceof Set) {
805 checkUnique((Set<Integer>)c);
806 }
807
808 check(c.toArray().length == c.size());
809 check(c.toArray().getClass() == Object[].class
810 ||
811 (needToWorkAround6260652 &&
812 c.getClass().getName().equals("java.util.Arrays$ArrayList")));
813 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
814 Integer[] a = c.toArray(new Integer[size]);
815 check((size > c.size()) || a.length == c.size());
816 int i = 0; for (Integer j : c) check(a[i++] == j);
817 check((size <= c.size()) || (a[c.size()] == null));
818 check(a.getClass() == Integer[].class);
819 }
820
821 {
822 Integer[] a = c.toArray(Integer[]::new);
823 equal(c.size(), a.length);
824 check(a.getClass() == Integer[].class);
825 check(Arrays.equals(c.toArray(new Integer[0]), a));
826 }
827
828 check(c.equals(c));
829 if (c instanceof Serializable) {
830 //System.out.printf("Serializing %s%n", c.getClass().getName());
831 try {
832 Object clone = serialClone(c);
833 equal(c instanceof Serializable,
834 clone instanceof Serializable);
835 equal(c instanceof RandomAccess,
836 clone instanceof RandomAccess);
837 if ((c instanceof List) || (c instanceof Set))
838 equal(c, clone);
839 else
840 equal(new HashSet<Integer>(c),
841 new HashSet<Integer>(serialClone(c)));
842 } catch (Error xxx) {
843 if (! (xxx.getCause() instanceof NotSerializableException))
844 throw xxx;
845 }
846 }
847 }
848 catch (Throwable t) { unexpected(t); }
849 }
850
851 //----------------------------------------------------------------
852 // If add(null) succeeds, contains(null) & remove(null) should succeed
853 //----------------------------------------------------------------
854 private static void testNullElement(Collection<Integer> c) {
855
856 try {
857 check(c.add(null));
858 if (c.size() == 1)
859 equal(c.toString(), "[null]");
860 try {
861 checkFunctionalInvariants(c);
862 check(c.contains(null));
863 check(c.remove(null));
864 }
865 catch (Throwable t) { unexpected(t); }
866 }
867 catch (NullPointerException e) { /* OK */ }
868 catch (Throwable t) { unexpected(t); }
869 }
870
871 //----------------------------------------------------------------
872 // If add("x") succeeds, contains("x") & remove("x") should succeed
873 //----------------------------------------------------------------
874 @SuppressWarnings("unchecked")
875 private static void testStringElement(Collection<Integer> c) {
876 Collection x = (Collection)c; // Make type-unsafe
877 try {
878 check(x.add("x"));
879 try {
880 check(x.contains("x"));
881 check(x.remove("x"));
882 } catch (Throwable t) { unexpected(t); }
883 }
884 catch (ClassCastException e) { /* OK */ }
885 catch (Throwable t) { unexpected(t); }
886 }
887
888 private static void testConcurrentCollection(Collection<Integer> c) {
889 try {
890 c.add(1);
891 Iterator<Integer> it = c.iterator();
892 check(it.hasNext());
893 clear(c);
894 check(it.next() instanceof Integer); // No CME
895 check(c.isEmpty());
896 }
897 catch (Throwable t) { unexpected(t); }
898 }
899
900 private static void testQueue(Queue<Integer> q) {
901 q.clear();
902 for (int i = 0; i < 5; i++) {
903 testQueueAddRemove(q, null);
904 testQueueAddRemove(q, 537);
905 q.add(i);
906 }
907 equal(q.size(), 5);
908 checkFunctionalInvariants(q);
909 q.poll();
910 equal(q.size(), 4);
911 checkFunctionalInvariants(q);
912 if ((q instanceof LinkedBlockingQueue) ||
913 (q instanceof LinkedBlockingDeque) ||
914 (q instanceof ConcurrentLinkedDeque) ||
915 (q instanceof ConcurrentLinkedQueue)) {
916 testQueueIteratorRemove(q);
917 }
918 }
919
920 private static void testQueueAddRemove(final Queue<Integer> q,
921 final Integer e) {
922 final List<Integer> originalContents = new ArrayList<>(q);
923 final boolean isEmpty = q.isEmpty();
924 final boolean isList = (q instanceof List);
925 final List asList = isList ? (List) q : null;
926 check(!q.contains(e));
927 try {
928 q.add(e);
929 } catch (NullPointerException npe) {
930 check(e == null);
931 return; // Null elements not supported
932 }
933 check(q.contains(e));
934 check(q.remove(e));
935 check(!q.contains(e));
936 equal(new ArrayList<Integer>(q), originalContents);
937
938 if (q instanceof Deque<?>) {
939 final Deque<Integer> deq = (Deque<Integer>) q;
940 final List<Integer> singleton = Collections.singletonList(e);
941
942 // insert, query, remove element at head
943 if (isEmpty) {
944 THROWS(NoSuchElementException.class,
945 () -> deq.getFirst(),
946 () -> deq.element(),
947 () -> deq.iterator().next());
948 check(deq.peekFirst() == null);
949 check(deq.peek() == null);
950 } else {
951 check(deq.getFirst() != e);
952 check(deq.element() != e);
953 check(deq.iterator().next() != e);
954 check(deq.peekFirst() != e);
955 check(deq.peek() != e);
956 }
957 check(!deq.contains(e));
958 check(!deq.removeFirstOccurrence(e));
959 check(!deq.removeLastOccurrence(e));
960 if (isList) {
961 check(asList.indexOf(e) == -1);
962 check(asList.lastIndexOf(e) == -1);
963 }
964 switch (rnd.nextInt(isList ? 4 : 3)) {
965 case 0: deq.addFirst(e); break;
966 case 1: check(deq.offerFirst(e)); break;
967 case 2: deq.push(e); break;
968 case 3: asList.add(0, e); break;
969 default: throw new AssertionError();
970 }
971 check(deq.peekFirst() == e);
972 check(deq.getFirst() == e);
973 check(deq.element() == e);
974 check(deq.peek() == e);
975 check(deq.iterator().next() == e);
976 check(deq.contains(e));
977 if (isList) {
978 check(asList.get(0) == e);
979 check(asList.indexOf(e) == 0);
980 check(asList.lastIndexOf(e) == 0);
981 check(asList.subList(0, 1).equals(singleton));
982 }
983 switch (rnd.nextInt(isList ? 11 : 9)) {
984 case 0: check(deq.pollFirst() == e); break;
985 case 1: check(deq.removeFirst() == e); break;
986 case 2: check(deq.remove() == e); break;
987 case 3: check(deq.pop() == e); break;
988 case 4: check(deq.removeFirstOccurrence(e)); break;
989 case 5: check(deq.removeLastOccurrence(e)); break;
990 case 6: check(deq.remove(e)); break;
991 case 7: check(deq.removeAll(singleton)); break;
992 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
993 case 9: asList.remove(0); break;
994 case 10: asList.subList(0, 1).clear(); break;
995 default: throw new AssertionError();
996 }
997 if (isEmpty) {
998 THROWS(NoSuchElementException.class,
999 () -> deq.getFirst(),
1000 () -> deq.element(),
1001 () -> deq.iterator().next());
1002 check(deq.peekFirst() == null);
1003 check(deq.peek() == null);
1004 } else {
1005 check(deq.getFirst() != e);
1006 check(deq.element() != e);
1007 check(deq.iterator().next() != e);
1008 check(deq.peekFirst() != e);
1009 check(deq.peek() != e);
1010 }
1011 check(!deq.contains(e));
1012 check(!deq.removeFirstOccurrence(e));
1013 check(!deq.removeLastOccurrence(e));
1014 if (isList) {
1015 check(isEmpty || asList.get(0) != e);
1016 check(asList.indexOf(e) == -1);
1017 check(asList.lastIndexOf(e) == -1);
1018 }
1019 equal(new ArrayList<Integer>(deq), originalContents);
1020
1021 // insert, query, remove element at tail
1022 if (isEmpty) {
1023 check(deq.peekLast() == null);
1024 THROWS(NoSuchElementException.class, () -> deq.getLast());
1025 } else {
1026 check(deq.peekLast() != e);
1027 check(deq.getLast() != e);
1028 }
1029 switch (rnd.nextInt(isList ? 6 : 4)) {
1030 case 0: deq.addLast(e); break;
1031 case 1: check(deq.offerLast(e)); break;
1032 case 2: check(deq.add(e)); break;
1033 case 3: deq.addAll(singleton); break;
1034 case 4: asList.addAll(deq.size(), singleton); break;
1035 case 5: asList.add(deq.size(), e); break;
1036 default: throw new AssertionError();
1037 }
1038 check(deq.peekLast() == e);
1039 check(deq.getLast() == e);
1040 check(deq.contains(e));
1041 if (isList) {
1042 ListIterator it = asList.listIterator(asList.size());
1043 check(it.previous() == e);
1044 check(asList.get(asList.size() - 1) == e);
1045 check(asList.indexOf(e) == asList.size() - 1);
1046 check(asList.lastIndexOf(e) == asList.size() - 1);
1047 int size = asList.size();
1048 check(asList.subList(size - 1, size).equals(singleton));
1049 }
1050 switch (rnd.nextInt(isList ? 8 : 6)) {
1051 case 0: check(deq.pollLast() == e); break;
1052 case 1: check(deq.removeLast() == e); break;
1053 case 2: check(deq.removeFirstOccurrence(e)); break;
1054 case 3: check(deq.removeLastOccurrence(e)); break;
1055 case 4: check(deq.remove(e)); break;
1056 case 5: check(deq.removeAll(singleton)); break;
1057 case 6: asList.remove(asList.size() - 1); break;
1058 case 7:
1059 ListIterator it = asList.listIterator(asList.size());
1060 it.previous();
1061 it.remove();
1062 break;
1063 default: throw new AssertionError();
1064 }
1065 if (isEmpty) {
1066 check(deq.peekLast() == null);
1067 THROWS(NoSuchElementException.class, () -> deq.getLast());
1068 } else {
1069 check(deq.peekLast() != e);
1070 check(deq.getLast() != e);
1071 }
1072 check(!deq.contains(e));
1073 equal(new ArrayList<Integer>(deq), originalContents);
1074
1075 // Test operations on empty deque
1076 switch (rnd.nextInt(isList ? 4 : 2)) {
1077 case 0: deq.clear(); break;
1078 case 1:
1079 Iterator it = deq.iterator();
1080 while (it.hasNext()) {
1081 it.next();
1082 it.remove();
1083 }
1084 break;
1085 case 2: asList.subList(0, asList.size()).clear(); break;
1086 case 3:
1087 ListIterator lit = asList.listIterator(asList.size());
1088 while (lit.hasPrevious()) {
1089 lit.previous();
1090 lit.remove();
1091 }
1092 break;
1093 default: throw new AssertionError();
1094 }
1095 testEmptyCollection(deq);
1096 check(!deq.iterator().hasNext());
1097 if (isList) {
1098 check(!asList.listIterator().hasPrevious());
1099 THROWS(NoSuchElementException.class,
1100 () -> asList.listIterator().previous());
1101 }
1102 THROWS(NoSuchElementException.class,
1103 () -> deq.iterator().next(),
1104 () -> deq.element(),
1105 () -> deq.getFirst(),
1106 () -> deq.getLast(),
1107 () -> deq.pop(),
1108 () -> deq.remove(),
1109 () -> deq.removeFirst(),
1110 () -> deq.removeLast());
1111
1112 check(deq.poll() == null);
1113 check(deq.pollFirst() == null);
1114 check(deq.pollLast() == null);
1115 check(deq.peek() == null);
1116 check(deq.peekFirst() == null);
1117 check(deq.peekLast() == null);
1118 check(!deq.removeFirstOccurrence(e));
1119 check(!deq.removeLastOccurrence(e));
1120
1121 check(deq.addAll(originalContents) == !isEmpty);
1122 equal(new ArrayList<Integer>(deq), originalContents);
1123 check(!deq.addAll(Collections.<Integer>emptyList()));
1124 equal(new ArrayList<Integer>(deq), originalContents);
1125 }
1126 }
1127
1128 private static void testQueueIteratorRemove(Queue<Integer> q) {
1129 System.err.printf("testQueueIteratorRemove %s%n",
1130 q.getClass().getSimpleName());
1131 q.clear();
1132 for (int i = 0; i < 5; i++)
1133 q.add(i);
1134 Iterator<Integer> it = q.iterator();
1135 check(it.hasNext());
1136 for (int i = 3; i >= 0; i--)
1137 q.remove(i);
1138 equal(it.next(), 0);
1139 equal(it.next(), 4);
1140
1141 q.clear();
1142 for (int i = 0; i < 5; i++)
1143 q.add(i);
1144 it = q.iterator();
1145 equal(it.next(), 0);
1146 check(it.hasNext());
1147 for (int i = 1; i < 4; i++)
1148 q.remove(i);
1149 equal(it.next(), 1);
1150 equal(it.next(), 4);
1151 }
1152
1153 // for any array of integer values, check that the result of lastIndexOf(1)
1154 // and indexOf(1) match assumptions for all types of List<Integer> we can
1155 // construct
1156 private static void testListIndexOf(final int index,
1157 final int lastIndex,
1158 final Integer ... values) {
1159 if (values.length == 0) {
1160 checkListIndexOf(emptyList(), index, lastIndex);
1161 } else if (values.length == 1) {
1162 checkListIndexOf(singletonList(values[0]), index, lastIndex);
1163 checkListIndexOf(nCopies(25, values[0]), index, lastIndex == 0 ? 24 : -1);
1164 }
1165 List<Integer> l = List.of(values);
1166 checkListIndexOf(l, index, lastIndex);
1167 checkListIndexOf(Arrays.asList(values), index, lastIndex);
1168 checkListIndexOf(new ArrayList(l), index, lastIndex);
1169 checkListIndexOf(new LinkedList(l), index, lastIndex);
1170 checkListIndexOf(new Vector(l), index, lastIndex);
1171 checkListIndexOf(new CopyOnWriteArrayList(l), index, lastIndex);
1172 }
1173
1174 private static void checkListIndexOf(final List<Integer> list,
1175 final int index,
1176 final int lastIndex) {
1177 String msg = list.getClass().toString();
1178 equal(list.indexOf(1), index, msg);
1179 equal(list.lastIndexOf(1), lastIndex, msg);
1180 equal(list.subList(0, list.size()).indexOf(1), index, msg);
1181 equal(list.subList(0, list.size()).lastIndexOf(1), lastIndex, msg);
1182 }
1183
1184 private static void testList(final List<Integer> l) {
1185 //----------------------------------------------------------------
1186 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
1187 // doesn't throw IndexOutOfBoundsException
1188 //----------------------------------------------------------------
1189 try {
1190 l.addAll(-1, Collections.<Integer>emptyList());
1191 fail("Expected IndexOutOfBoundsException not thrown");
1192 }
1193 catch (UnsupportedOperationException ignored) {/* OK */}
1194 catch (IndexOutOfBoundsException ignored) {/* OK */}
1195 catch (Throwable t) { unexpected(t); }
1196
1197 // equal(l instanceof Serializable,
1198 // l.subList(0,0) instanceof Serializable);
1199 if (l.subList(0,0) instanceof Serializable)
1200 check(l instanceof Serializable);
1201
1202 equal(l instanceof RandomAccess,
1203 l.subList(0,0) instanceof RandomAccess);
1204
1205 l.iterator();
1206 l.listIterator();
1207 l.listIterator(0);
1208 l.listIterator(l.size());
1209 THROWS(IndexOutOfBoundsException.class,
1210 () -> l.listIterator(-1),
1211 () -> l.listIterator(l.size() + 1));
1212
1213 if (l instanceof AbstractList) {
1214 try {
1215 int size = l.size();
1216 AbstractList<Integer> abList = (AbstractList<Integer>) l;
1217 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class });
1218 m.setAccessible(true);
1219 m.invoke(abList, new Object[] { 0, 0 });
1220 m.invoke(abList, new Object[] { size, size });
1221 equal(size, l.size());
1222 }
1223 catch (UnsupportedOperationException ignored) {/* OK */}
1224 catch (Throwable t) { unexpected(t); }
1225 }
1226
1227 int hashCode = 1;
1228 for (Integer i : l)
1229 hashCode = 31 * hashCode + (i == null ? 0 : i.hashCode());
1230 check(l.hashCode() == hashCode);
1231
1232 var t = new ArrayList<>(l);
1233 check(t.equals(l));
1234 check(l.equals(t));
1235 }
1236
1237 private static void testCollection(Collection<Integer> c) {
1238 try { testCollection1(c); }
1239 catch (Throwable t) { unexpected(t); }
1240 }
1241
1242 private static void testCollection1(Collection<Integer> c) {
1243
1244 System.out.println("\n==> " + c.getClass().getName());
1245
1246 checkFunctionalInvariants(c);
1247
1248 if (! supportsAdd(c)) return;
1249 //System.out.println("add() supported");
1250
1251 if (c instanceof NavigableSet) {
1252 System.out.println("NavigableSet tests...");
1253
1254 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
1255 testNavigableSet(ns);
1256 testNavigableSet(ns.headSet(6, false));
1257 testNavigableSet(ns.headSet(5, true));
1258 testNavigableSet(ns.tailSet(0, false));
1259 testNavigableSet(ns.tailSet(1, true));
1260 testNavigableSet(ns.subSet(0, false, 5, true));
1261 testNavigableSet(ns.subSet(1, true, 6, false));
1262 }
1263
1264 if (c instanceof Queue)
1265 testQueue((Queue<Integer>)c);
1266
1267 if (c instanceof List)
1268 testList((List<Integer>)c);
1269
1270 if (c instanceof Set) {
1271 int hashCode = 0;
1272 for (Integer i : c)
1273 hashCode = hashCode + (i == null ? 0 : i.hashCode());
1274 check(c.hashCode() == hashCode);
1275 }
1276
1277 check(supportsRemove(c));
1278
1279 try {
1280 oneElement(c);
1281 checkFunctionalInvariants(c);
1282 }
1283 catch (Throwable t) { unexpected(t); }
1284
1285 clear(c); testNullElement(c);
1286 oneElement(c); testNullElement(c);
1287
1288 clear(c); testStringElement(c);
1289 oneElement(c); testStringElement(c);
1290
1291 if (c.getClass().getName().matches(".*concurrent.*"))
1292 testConcurrentCollection(c);
1293
1294 //----------------------------------------------------------------
1295 // The "all" operations should throw NPE when passed null
1296 //----------------------------------------------------------------
1297 {
1298 clear(c);
1299 try {
1300 c.removeAll(null);
1301 fail("Expected NullPointerException");
1302 }
1303 catch (NullPointerException e) { pass(); }
1304 catch (Throwable t) { unexpected(t); }
1305
1306 oneElement(c);
1307 try {
1308 c.removeAll(null);
1309 fail("Expected NullPointerException");
1310 }
1311 catch (NullPointerException e) { pass(); }
1312 catch (Throwable t) { unexpected(t); }
1313
1314 clear(c);
1315 try {
1316 c.retainAll(null);
1317 fail("Expected NullPointerException");
1318 }
1319 catch (NullPointerException e) { pass(); }
1320 catch (Throwable t) { unexpected(t); }
1321
1322 oneElement(c);
1323 try {
1324 c.retainAll(null);
1325 fail("Expected NullPointerException");
1326 }
1327 catch (NullPointerException e) { pass(); }
1328 catch (Throwable t) { unexpected(t); }
1329
1330 oneElement(c);
1331 try {
1332 c.addAll(null);
1333 fail("Expected NullPointerException");
1334 }
1335 catch (NullPointerException e) { pass(); }
1336 catch (Throwable t) { unexpected(t); }
1337
1338 oneElement(c);
1339 try {
1340 c.containsAll(null);
1341 fail("Expected NullPointerException");
1342 }
1343 catch (NullPointerException e) { pass(); }
1344 catch (Throwable t) { unexpected(t); }
1345 }
1346 }
1347
1348 //----------------------------------------------------------------
1349 // Map
1350 //----------------------------------------------------------------
1351 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
1352 check(m.keySet().size() == m.entrySet().size());
1353 check(m.keySet().size() == m.size());
1354 checkFunctionalInvariants(m.keySet());
1355 checkFunctionalInvariants(m.values());
1356 check(m.size() != 0 ^ m.isEmpty());
1357 check(! m.containsKey(ABSENT_VALUE));
1358
1359 if (m instanceof Serializable) {
1360 //System.out.printf("Serializing %s%n", m.getClass().getName());
1361 try {
1362 Object clone = serialClone(m);
1363 equal(m instanceof Serializable,
1364 clone instanceof Serializable);
1365 equal(m, clone);
1366 } catch (Error xxx) {
1367 if (! (xxx.getCause() instanceof NotSerializableException))
1368 throw xxx;
1369 }
1370 }
1371 }
1372
1373 private static void testMap(Map<Integer,Integer> m) {
1374 System.out.println("\n==> " + m.getClass().getName());
1375
1376 int hashCode = 0;
1377 for (var e : m.entrySet()) {
1378 int entryHash = (e.getKey() == null ? 0 : e.getKey().hashCode()) ^
1379 (e.getValue() == null ? 0 : e.getValue().hashCode());
1380 check(e.hashCode() == entryHash);
1381 hashCode += entryHash;
1382 }
1383 check(m.hashCode() == hashCode);
1384
1385 if (m instanceof ConcurrentMap)
1386 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
1387
1388 if (m instanceof NavigableMap) {
1389 System.out.println("NavigableMap tests...");
1390
1391 NavigableMap<Integer,Integer> nm =
1392 (NavigableMap<Integer,Integer>) m;
1393 testNavigableMapRemovers(nm);
1394 testNavigableMap(nm);
1395 testNavigableMap(nm.headMap(6, false));
1396 testNavigableMap(nm.headMap(5, true));
1397 testNavigableMap(nm.tailMap(0, false));
1398 testNavigableMap(nm.tailMap(1, true));
1399 testNavigableMap(nm.subMap(1, true, 6, false));
1400 testNavigableMap(nm.subMap(0, false, 5, true));
1401 }
1402
1403 checkFunctionalInvariants(m);
1404
1405 if (supportsClear(m)) {
1406 try { clear(m); }
1407 catch (Throwable t) { unexpected(t); }
1408 }
1409
1410 if (supportsPut(m)) {
1411 try {
1412 check(m.put(3333, 77777) == null);
1413 check(m.put(9134, 74982) == null);
1414 check(m.get(9134) == 74982);
1415 check(m.put(9134, 1382) == 74982);
1416 check(m.get(9134) == 1382);
1417 check(m.size() == 2);
1418 checkFunctionalInvariants(m);
1419 checkNPEConsistency(m);
1420 }
1421 catch (Throwable t) { unexpected(t); }
1422 }
1423 }
1424
1425 private static boolean supportsPut(Map<Integer,Integer> m) {
1426 // We're asking for .equals(...) semantics
1427 if (m instanceof IdentityHashMap) return false;
1428
1429 try { check(m.put(ABSENT_VALUE,12735) == null); }
1430 catch (UnsupportedOperationException t) { return false; }
1431 catch (Throwable t) { unexpected(t); }
1432
1433 try {
1434 check(m.containsKey(ABSENT_VALUE));
1435 check(m.remove(ABSENT_VALUE) != null);
1436 } catch (Throwable t) { unexpected(t); }
1437 return true;
1438 }
1439
1440 private static boolean supportsClear(Map<?,?> m) {
1441 try { m.clear(); }
1442 catch (UnsupportedOperationException t) { return false; }
1443 catch (Throwable t) { unexpected(t); }
1444 return true;
1445 }
1446
1447 //----------------------------------------------------------------
1448 // ConcurrentMap
1449 //----------------------------------------------------------------
1450 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
1451 System.out.println("ConcurrentMap tests...");
1452
1453 try {
1454 clear(m);
1455
1456 check(m.putIfAbsent(18357,7346) == null);
1457 check(m.containsKey(18357));
1458 check(m.putIfAbsent(18357,8263) == 7346);
1459 try { m.putIfAbsent(18357,null); fail("NPE"); }
1460 catch (NullPointerException t) { }
1461 check(m.containsKey(18357));
1462
1463 check(! m.replace(18357,8888,7777));
1464 check(m.containsKey(18357));
1465 try { m.replace(18357,null,7777); fail("NPE"); }
1466 catch (NullPointerException t) { }
1467 check(m.containsKey(18357));
1468 check(m.get(18357) == 7346);
1469 check(m.replace(18357,7346,5555));
1470 check(m.replace(18357,5555,7346));
1471 check(m.get(18357) == 7346);
1472
1473 check(m.replace(92347,7834) == null);
1474 try { m.replace(18357,null); fail("NPE"); }
1475 catch (NullPointerException t) { }
1476 check(m.replace(18357,7346) == 7346);
1477 check(m.replace(18357,5555) == 7346);
1478 check(m.get(18357) == 5555);
1479 check(m.replace(18357,7346) == 5555);
1480 check(m.get(18357) == 7346);
1481
1482 check(! m.remove(18357,9999));
1483 check(m.get(18357) == 7346);
1484 check(m.containsKey(18357));
1485 check(! m.remove(18357,null)); // 6272521
1486 check(m.get(18357) == 7346);
1487 check(m.remove(18357,7346));
1488 check(m.get(18357) == null);
1489 check(! m.containsKey(18357));
1490 check(m.isEmpty());
1491
1492 m.putIfAbsent(1,2);
1493 check(m.size() == 1);
1494 check(! m.remove(1,null));
1495 check(! m.remove(1,null));
1496 check(! m.remove(1,1));
1497 check(m.remove(1,2));
1498 check(m.isEmpty());
1499
1500 testEmptyMap(m);
1501 }
1502 catch (Throwable t) { unexpected(t); }
1503 }
1504
1505 private static void throwsConsistently(Class<? extends Throwable> k,
1506 Iterable<Fun> fs) {
1507 List<Class<? extends Throwable>> threw = new ArrayList<>();
1508 for (Fun f : fs)
1509 try { f.f(); threw.add(null); }
1510 catch (Throwable t) {
1511 check(k.isAssignableFrom(t.getClass()));
1512 threw.add(t.getClass());
1513 }
1514 if (new HashSet<Object>(threw).size() != 1)
1515 fail(threw.toString());
1516 }
1517
1518 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
1519 m.clear();
1520 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
1521 ? (ConcurrentMap<T,Integer>) m
1522 : null;
1523 List<Fun> fs = new ArrayList<>();
1524 fs.add(() -> check(! m.containsKey(null)));
1525 fs.add(() -> equal(m.remove(null), null));
1526 fs.add(() -> equal(m.get(null), null));
1527 if (cm != null)
1528 fs.add(() -> check(! cm.remove(null,null)));
1529 throwsConsistently(NullPointerException.class, fs);
1530
1531 fs.clear();
1532 final Map<T,Integer> sm = singletonMap(null,1);
1533 fs.add(() -> { equal(m.put(null,1), null); m.clear();});
1534 fs.add(() -> { m.putAll(sm); m.clear();});
1535 if (cm != null) {
1536 fs.add(() -> check(! cm.remove(null,null)));
1537 fs.add(() -> equal(cm.putIfAbsent(null,1), 1));
1538 fs.add(() -> equal(cm.replace(null,1), null));
1539 fs.add(() -> equal(cm.replace(null,1, 1), 1));
1540 }
1541 throwsConsistently(NullPointerException.class, fs);
1542 }
1543
1544 //----------------------------------------------------------------
1545 // NavigableMap
1546 //----------------------------------------------------------------
1547 private static void
1548 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1549 Integer i,
1550 Integer lower,
1551 Integer floor,
1552 Integer ceiling,
1553 Integer higher) {
1554 equal(m.lowerKey(i), lower);
1555 equal(m.floorKey(i), floor);
1556 equal(m.ceilingKey(i), ceiling);
1557 equal(m.higherKey(i), higher);
1558 }
1559
1560 private static void
1561 checkNavigableSetKeys(NavigableSet<Integer> m,
1562 Integer i,
1563 Integer lower,
1564 Integer floor,
1565 Integer ceiling,
1566 Integer higher) {
1567 equal(m.lower(i), lower);
1568 equal(m.floor(i), floor);
1569 equal(m.ceiling(i), ceiling);
1570 equal(m.higher(i), higher);
1571 }
1572
1573 static final Random rnd = new Random();
1574 static void equalNext(final Iterator<?> it, Object expected) {
1575 if (rnd.nextBoolean())
1576 check(it.hasNext());
1577 equal(it.next(), expected);
1578 }
1579
1580 static void equalMaps(Map m1, Map m2) {
1581 equal(m1, m2);
1582 equal(m2, m1);
1583 equal(m1.size(), m2.size());
1584 equal(m1.isEmpty(), m2.isEmpty());
1585 equal(m1.toString(), m2.toString());
1586 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1587 }
1588
1589 @SuppressWarnings({"unchecked", "rawtypes"})
1590 static void testNavigableMapRemovers(NavigableMap m)
1591 {
1592 final Map emptyMap = new HashMap();
1593
1594 final Map singletonMap = new HashMap();
1595 singletonMap.put(1, 2);
1596
1597 abstract class NavigableMapView {
1598 abstract NavigableMap view(NavigableMap m);
1599 }
1600
1601 NavigableMapView[] views = {
1602 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1603 return m; }},
1604 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1605 return m.headMap(99, true); }},
1606 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1607 return m.tailMap(-99, false); }},
1608 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1609 return m.subMap(-99, true, 99, false); }},
1610 };
1611
1612 abstract class Remover {
1613 abstract void remove(NavigableMap m, Object k, Object v);
1614 }
1615
1616 Remover[] removers = {
1617 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1618 equal(m.remove(k), v); }},
1619
1620 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1621 equal(m.descendingMap().remove(k), v); }},
1622 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1623 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1624 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1625 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1626
1627 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1628 equal(m.headMap(86, true).remove(k), v); }},
1629 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1630 equal(m.tailMap(-86, true).remove(k), v); }},
1631 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1632 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1633
1634 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1635 check(m.keySet().remove(k)); }},
1636 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1637 check(m.navigableKeySet().remove(k)); }},
1638
1639 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1640 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1641 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1642 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1643 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1644 check(m.navigableKeySet().subSet(-86, true, 86, false)
1645 .remove(k)); }},
1646
1647 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1648 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1649 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1650 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1651 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1652 check(m.descendingKeySet().subSet(86, true, -86, false)
1653 .remove(k)); }},
1654 };
1655
1656 for (NavigableMapView view : views) {
1657 for (Remover remover : removers) {
1658 try {
1659 m.clear();
1660 equalMaps(m, emptyMap);
1661 equal(m.put(1, 2), null);
1662 equalMaps(m, singletonMap);
1663 NavigableMap v = view.view(m);
1664 remover.remove(v, 1, 2);
1665 equalMaps(m, emptyMap);
1666 } catch (Throwable t) { unexpected(t); }
1667 }
1668 }
1669 }
1670
1671 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1672 {
1673 clear(m);
1674 checkNavigableMapKeys(m, 1, null, null, null, null);
1675
1676 equal(m.put(1, 2), null);
1677 equal(m.put(3, 4), null);
1678 equal(m.put(5, 9), null);
1679
1680 equal(m.put(1, 2), 2);
1681 equal(m.put(3, 4), 4);
1682 equal(m.put(5, 6), 9);
1683
1684 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1685 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1686 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1687 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1688 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1689 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1690
1691 for (final Iterator<Integer> it :
1692 (Iterator<Integer>[])
1693 new Iterator<?>[] {
1694 m.descendingKeySet().iterator(),
1695 m.navigableKeySet().descendingIterator()}) {
1696 equalNext(it, 5);
1697 equalNext(it, 3);
1698 equalNext(it, 1);
1699 check(! it.hasNext());
1700 THROWS(NoSuchElementException.class, () -> it.next());
1701 }
1702
1703 {
1704 final Iterator<Map.Entry<Integer,Integer>> it
1705 = m.descendingMap().entrySet().iterator();
1706 check(it.hasNext()); equal(it.next().getKey(), 5);
1707 check(it.hasNext()); equal(it.next().getKey(), 3);
1708 check(it.hasNext()); equal(it.next().getKey(), 1);
1709 check(! it.hasNext());
1710 THROWS(NoSuchElementException.class, () -> it.next());
1711 }
1712
1713 prepMapForDescItrTests(m);
1714 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator());
1715 prepMapForDescItrTests(m);
1716 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());
1717 prepMapForDescItrTests(m);
1718 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator());
1719
1720 prepMapForDescItrTests(m);
1721 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator());
1722 prepMapForDescItrTests(m);
1723 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator());
1724 prepMapForDescItrTests(m);
1725 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator());
1726
1727 prepMapForDescItrTests(m);
1728 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator());
1729 prepMapForDescItrTests(m);
1730 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator());
1731 prepMapForDescItrTests(m);
1732 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator());
1733
1734 prepMapForDescItrTests(m);
1735 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator());
1736 prepMapForDescItrTests(m);
1737 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator());
1738 prepMapForDescItrTests(m);
1739 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator());
1740
1741 prepMapForDescItrTests(m);
1742 checkDescItrRmFirst((Collection)m.entrySet(),
1743 m.descendingMap().entrySet().iterator());
1744 prepMapForDescItrTests(m);
1745 checkDescItrRmMid((Collection)m.entrySet(),
1746 m.descendingMap().entrySet().iterator());
1747 prepMapForDescItrTests(m);
1748 checkDescItrRmLast((Collection)m.entrySet(),
1749 m.descendingMap().entrySet().iterator());
1750 }
1751
1752 private static void testNavigableSet(NavigableSet<Integer> s) {
1753 clear(s);
1754 checkNavigableSetKeys(s, 1, null, null, null, null);
1755
1756 check(s.add(1));
1757 check(s.add(3));
1758 check(s.add(5));
1759
1760 check(! s.add(1));
1761 check(! s.add(3));
1762 check(! s.add(5));
1763
1764 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1765 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1766 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1767 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1768 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1769 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1770
1771 for (final Iterator<Integer> it :
1772 (Iterator<Integer>[])
1773 new Iterator<?>[] {
1774 s.descendingIterator(),
1775 s.descendingSet().iterator()}) {
1776 equalNext(it, 5);
1777 equalNext(it, 3);
1778 equalNext(it, 1);
1779 check(! it.hasNext());
1780 THROWS(NoSuchElementException.class, () -> it.next());
1781 }
1782
1783 prepSetForDescItrTests(s);
1784 checkDescItrRmFirst(s, s.descendingIterator());
1785 prepSetForDescItrTests(s);
1786 checkDescItrRmMid(s, s.descendingIterator());
1787 prepSetForDescItrTests(s);
1788 checkDescItrRmLast(s, s.descendingIterator());
1789
1790 prepSetForDescItrTests(s);
1791 checkDescItrRmFirst(s, s.descendingSet().iterator());
1792 prepSetForDescItrTests(s);
1793 checkDescItrRmMid(s, s.descendingSet().iterator());
1794 prepSetForDescItrTests(s);
1795 checkDescItrRmLast(s, s.descendingSet().iterator());
1796 }
1797
1798 private static void prepSetForDescItrTests(Set s) {
1799 clear(s);
1800 check(s.add(1));
1801 check(s.add(3));
1802 check(s.add(5));
1803 }
1804
1805 private static void prepMapForDescItrTests(Map m) {
1806 clear(m);
1807 equal(m.put(1, 2), null);
1808 equal(m.put(3, 4), null);
1809 equal(m.put(5, 9), null);
1810 }
1811
1812 //--------------------------------------------------------------------
1813 // Check behavior of descending iterator when first element is removed
1814 //--------------------------------------------------------------------
1815 private static <T> void checkDescItrRmFirst(Collection<T> ascColl,
1816 Iterator<T> descItr) {
1817 T[] expected = (T[]) ascColl.toArray();
1818 int idx = expected.length -1;
1819
1820 equalNext(descItr, expected[idx--]);
1821 descItr.remove();
1822 while (idx >= 0 && descItr.hasNext()) {
1823 equalNext(descItr, expected[idx--]);
1824 }
1825 equal(descItr.hasNext(), false);
1826 equal(idx, -1);
1827 }
1828
1829 //-----------------------------------------------------------------------
1830 // Check behavior of descending iterator when a middle element is removed
1831 //-----------------------------------------------------------------------
1832 private static <T> void checkDescItrRmMid(Collection<T> ascColl,
1833 Iterator<T> descItr) {
1834 T[] expected = (T[]) ascColl.toArray();
1835 int idx = expected.length -1;
1836
1837 while (idx >= expected.length / 2) {
1838 equalNext(descItr, expected[idx--]);
1839 }
1840 descItr.remove();
1841 while (idx >= 0 && descItr.hasNext()) {
1842 equalNext(descItr, expected[idx--]);
1843 }
1844 equal(descItr.hasNext(), false);
1845 equal(idx, -1);
1846 }
1847
1848 //-----------------------------------------------------------------------
1849 // Check behavior of descending iterator when the last element is removed
1850 //-----------------------------------------------------------------------
1851 private static <T> void checkDescItrRmLast(Collection<T> ascColl,
1852 Iterator<T> descItr) {
1853 T[] expected = (T[]) ascColl.toArray();
1854 int idx = expected.length -1;
1855
1856 while (idx >= 0 && descItr.hasNext()) {
1857 equalNext(descItr, expected[idx--]);
1858 }
1859 equal(idx, -1);
1860 equal(descItr.hasNext(), false);
1861 descItr.remove();
1862 equal(ascColl.contains(expected[0]), false);
1863 }
1864
1865 //--------------------- Infrastructure ---------------------------
1866 static volatile int passed = 0, failed = 0;
1867 static void pass() { passed++; }
1868 static void fail() { failed++; Thread.dumpStack(); }
1869 static void fail(String msg) { System.out.println(msg); fail(); }
1870 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1871 static void check(boolean cond) { if (cond) pass(); else fail(); }
1872 static void equal(Object x, Object y) {
1873 if (x == null ? y == null : x.equals(y)) pass();
1874 else {System.out.println(x + " not equal to " + y); fail();}}
1875 static void equal(Object x, Object y, String msg) {
1876 if (x == null ? y == null : x.equals(y)) pass();
1877 else {System.out.println(x + " not equal to " + y + " : " + msg); fail();}}
1878 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1879 public static void main(String[] args) throws Throwable {
1880 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1881
1882 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1883 if (failed > 0) throw new Exception("Some tests failed");
1884 }
1885 interface Fun {void f() throws Throwable;}
1886 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1887 for (Fun f : fs)
1888 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1889 catch (Throwable t) {
1890 if (k.isAssignableFrom(t.getClass())) pass();
1891 else unexpected(t);}}
1892 static byte[] serializedForm(Object obj) {
1893 try {
1894 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1895 new ObjectOutputStream(baos).writeObject(obj);
1896 return baos.toByteArray();
1897 } catch (IOException e) { throw new Error(e); }}
1898 static Object readObject(byte[] bytes)
1899 throws IOException, ClassNotFoundException {
1900 InputStream is = new ByteArrayInputStream(bytes);
1901 return new ObjectInputStream(is).readObject();}
1902 @SuppressWarnings("unchecked")
1903 static <T> T serialClone(T obj) {
1904 try { return (T) readObject(serializedForm(obj)); }
1905 catch (Exception e) { throw new Error(e); }}
1906 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1907 ArrayList<E> list = new ArrayList<>();
1908 public boolean remove(Object obj) {
1909 return list.remove(obj);
1910 }
1911 public boolean add(E e) {
1912 return list.add(e);
1913 }
1914 public Iterator<E> iterator() {
1915 return list.iterator();
1916 }
1917 public int size() {
1918 return list.size();
1919 }
1920 }
1921 private static class NewAbstractSet<E> extends AbstractSet<E> {
1922 HashSet<E> set = new HashSet<>();
1923 public boolean remove(Object obj) {
1924 return set.remove(obj);
1925 }
1926 public boolean add(E e) {
1927 return set.add(e);
1928 }
1929 public Iterator<E> iterator() {
1930 return set.iterator();
1931 }
1932 public int size() {
1933 return set.size();
1934 }
1935 }
1936
1937 }