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