1 /*
2 * Copyright (c) 2005, 2013, 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
30 * @summary Run many tests on many Collection and Map implementations
31 * @author Martin Buchholz
32 * @run main MOAT
33 */
34
35 /* Mother Of All (Collection) Tests
36 *
37 * Testing of collection classes is often spotty, because many tests
38 * need to be performed on many implementations, but the onus on
39 * writing the tests falls on the engineer introducing the new
40 * implementation.
41 *
42 * The idea of this mega-test is that:
43 *
44 * An engineer adding a new collection implementation could simply add
45 * their new implementation to a list of implementations in this
46 * test's main method. Any general purpose Collection<Integer> or
47 * Map<Integer,Integer> class is appropriate.
48 *
49 * An engineer fixing a regression could add their regression test here and
50 * simultaneously test all other implementations.
51 */
52
53 import java.io.*;
54 import java.util.*;
55 import java.util.concurrent.*;
56 import static java.util.Collections.*;
57 import java.lang.reflect.*;
58
59 public class MOAT {
60 public static void realMain(String[] args) {
61
62 testCollection(new NewAbstractCollection<Integer>());
63 testCollection(new NewAbstractSet<Integer>());
64 testCollection(new LinkedHashSet<Integer>());
65 testCollection(new HashSet<Integer>());
66 testCollection(new Vector<Integer>());
67 testCollection(new Vector<Integer>().subList(0,0));
68 testCollection(new ArrayDeque<Integer>());
69 testCollection(new ArrayList<Integer>());
70 testCollection(new ArrayList<Integer>().subList(0,0));
71 testCollection(new LinkedList<Integer>());
72 testCollection(new LinkedList<Integer>().subList(0,0));
73 testCollection(new TreeSet<Integer>());
74 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
75 testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
76 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
77 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
78 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
79 testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
80 testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));
81 testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>()));
82
83 testCollection(new CopyOnWriteArrayList<Integer>());
84 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
85 testCollection(new CopyOnWriteArraySet<Integer>());
86 testCollection(new PriorityQueue<Integer>());
87 testCollection(new PriorityBlockingQueue<Integer>());
88 testCollection(new ArrayBlockingQueue<Integer>(20));
89 testCollection(new LinkedBlockingQueue<Integer>(20));
90 testCollection(new LinkedBlockingDeque<Integer>(20));
91 testCollection(new ConcurrentLinkedDeque<Integer>());
92 testCollection(new ConcurrentLinkedQueue<Integer>());
93 testCollection(new LinkedTransferQueue<Integer>());
94 testCollection(new ConcurrentSkipListSet<Integer>());
95 testCollection(Arrays.asList(new Integer(42)));
96 testCollection(Arrays.asList(1,2,3));
97 testCollection(nCopies(25,1));
98 testImmutableList(nCopies(25,1));
99 testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
100
101 testMap(new HashMap<Integer,Integer>());
102 testMap(new LinkedHashMap<Integer,Integer>());
103 testMap(new WeakHashMap<Integer,Integer>());
104 testMap(new IdentityHashMap<Integer,Integer>());
105 testMap(new TreeMap<Integer,Integer>());
106 testMap(new Hashtable<Integer,Integer>());
107 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
108 testMap(new ConcurrentSkipListMap<Integer,Integer>());
109 testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));
110 testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
111 testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
112 testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));
113 testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));
114 testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));
115
116 // Empty collections
117 final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
118 testCollection(emptyArray);
119 testEmptyList(emptyArray);
120 THROWS(IndexOutOfBoundsException.class,
121 new Fun(){void f(){ emptyArray.set(0,1); }});
122 THROWS(UnsupportedOperationException.class,
123 new Fun(){void f(){ emptyArray.add(0,1); }});
124
125 List<Integer> noOne = nCopies(0,1);
126 testCollection(noOne);
127 testEmptyList(noOne);
128 testImmutableList(noOne);
129
130 Set<Integer> emptySet = emptySet();
131 testCollection(emptySet);
132 testEmptySet(emptySet);
133 testEmptySet(EMPTY_SET);
134 testEmptySet(Collections.emptySet());
135 testEmptySet(Collections.emptySortedSet());
136 testEmptySet(Collections.emptyNavigableSet());
137 testImmutableSet(emptySet);
138
139 List<Integer> emptyList = emptyList();
140 testCollection(emptyList);
141 testEmptyList(emptyList);
142 testEmptyList(EMPTY_LIST);
143 testEmptyList(Collections.emptyList());
144 testImmutableList(emptyList);
145
146 Map<Integer,Integer> emptyMap = emptyMap();
147 testMap(emptyMap);
148 testEmptyMap(emptyMap);
149 testEmptyMap(EMPTY_MAP);
150 testEmptyMap(Collections.emptyMap());
151 testEmptyMap(Collections.emptySortedMap());
152 testEmptyMap(Collections.emptyNavigableMap());
153 testImmutableMap(emptyMap);
154 testImmutableMap(Collections.emptyMap());
155 testImmutableMap(Collections.emptySortedMap());
156 testImmutableMap(Collections.emptyNavigableMap());
157
158 // Singleton collections
159 Set<Integer> singletonSet = singleton(1);
160 equal(singletonSet.size(), 1);
161 testCollection(singletonSet);
162 testImmutableSet(singletonSet);
163
164 List<Integer> singletonList = singletonList(1);
165 equal(singletonList.size(), 1);
166 testCollection(singletonList);
167 testImmutableList(singletonList);
168 testImmutableList(singletonList.subList(0,1));
169 testImmutableList(singletonList.subList(0,1).subList(0,1));
170 testEmptyList(singletonList.subList(0,0));
171 testEmptyList(singletonList.subList(0,0).subList(0,0));
172
173 Map<Integer,Integer> singletonMap = singletonMap(1,2);
174 equal(singletonMap.size(), 1);
175 testMap(singletonMap);
176 testImmutableMap(singletonMap);
177 }
178
179 private static void checkContainsSelf(Collection<Integer> c) {
180 check(c.containsAll(c));
181 check(c.containsAll(Arrays.asList(c.toArray())));
182 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
183 }
184
185 private static void checkContainsEmpty(Collection<Integer> c) {
186 check(c.containsAll(new ArrayList<Integer>()));
187 }
188
189 private static <T> void testEmptyCollection(Collection<T> c) {
190 check(c.isEmpty());
191 equal(c.size(), 0);
192 equal(c.toString(),"[]");
193 equal(c.toArray().length, 0);
194 equal(c.toArray(new Object[0]).length, 0);
195 check(c.toArray(new Object[]{42})[0] == null);
196
197 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
198 equal(c.toArray(a), a);
199 equal(a[0], null);
200 testEmptyIterator(c.iterator());
201 }
202
203 static <T> void testEmptyIterator(final Iterator<T> it) {
204 if (rnd.nextBoolean())
205 check(! it.hasNext());
206
207 THROWS(NoSuchElementException.class,
208 new Fun(){void f(){ it.next(); }});
209
210 try { it.remove(); }
211 catch (IllegalStateException ignored) { pass(); }
212 catch (UnsupportedOperationException ignored) { pass(); }
213 catch (Throwable t) { unexpected(t); }
214
215 if (rnd.nextBoolean())
216 check(! it.hasNext());
217 }
218
219 private static void testEmptyList(List<?> c) {
220 testEmptyCollection(c);
221 equal(c.hashCode(), 1);
222 equal2(c, Collections.<Integer>emptyList());
223 }
224
225 private static <T> void testEmptySet(Set<T> c) {
226 testEmptyCollection(c);
227 equal(c.hashCode(), 0);
228 equal2(c, Collections.<Integer>emptySet());
229 if (c instanceof NavigableSet<?>)
230 testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
231 }
232
233 private static void testImmutableCollection(final Collection<Integer> c) {
234 THROWS(UnsupportedOperationException.class,
235 new Fun(){void f(){ c.add(99); }},
236 new Fun(){void f(){ c.addAll(singleton(99)); }});
237 if (! c.isEmpty()) {
238 final Integer first = c.iterator().next();
239 THROWS(UnsupportedOperationException.class,
240 new Fun(){void f(){ c.clear(); }},
241 new Fun(){void f(){ c.remove(first); }},
242 new Fun(){void f(){ c.removeAll(singleton(first)); }},
243 new Fun(){void f(){ c.retainAll(emptyList()); }}
244 );
245 }
246 }
247
248 private static void testImmutableSet(final Set<Integer> c) {
249 testImmutableCollection(c);
250 }
251
252 private static void testImmutableList(final List<Integer> c) {
253 testList(c);
254 testImmutableCollection(c);
255 THROWS(UnsupportedOperationException.class,
256 new Fun(){void f(){ c.set(0,42); }},
257 new Fun(){void f(){ c.add(0,42); }},
258 new Fun(){void f(){ c.addAll(0,singleton(86)); }});
259 if (! c.isEmpty())
260 THROWS(UnsupportedOperationException.class,
261 new Fun(){void f(){
262 Iterator<Integer> it = c.iterator();
263 it.next(); it.remove();}},
264 new Fun(){void f(){
265 ListIterator<Integer> it = c.listIterator();
266 it.next(); it.remove();}});
267 }
268
269 private static void clear(Collection<Integer> c) {
270 try { c.clear(); }
271 catch (Throwable t) { unexpected(t); }
272 testEmptyCollection(c);
273 }
274
275 private static <K,V> void testEmptyMap(final Map<K,V> m) {
276 check(m.isEmpty());
277 equal(m.size(), 0);
278 equal(m.toString(),"{}");
279 testEmptySet(m.keySet());
280 testEmptySet(m.entrySet());
281 testEmptyCollection(m.values());
282
283 try { check(! m.containsValue(null)); }
284 catch (NullPointerException ignored) { /* OK */ }
285 try { check(! m.containsKey(null)); }
286 catch (NullPointerException ignored) { /* OK */ }
287 check(! m.containsValue(1));
288 check(! m.containsKey(1));
289 }
290
291 private static void testImmutableMap(final Map<Integer,Integer> m) {
292 THROWS(UnsupportedOperationException.class,
293 new Fun(){void f(){ m.put(1,1); }},
294 new Fun(){void f(){ m.putAll(singletonMap(1,1)); }});
295 if (! m.isEmpty()) {
296 final Integer first = m.keySet().iterator().next();
297 THROWS(UnsupportedOperationException.class,
298 new Fun(){void f(){ m.remove(first); }},
299 new Fun(){void f(){ m.clear(); }});
300 final Map.Entry<Integer,Integer> me
301 = m.entrySet().iterator().next();
302 Integer key = me.getKey();
303 Integer val = me.getValue();
304 THROWS(UnsupportedOperationException.class,
305 new Fun(){void f(){ me.setValue(3); }});
306 equal(key, me.getKey());
307 equal(val, me.getValue());
308 }
309 testImmutableSet(m.keySet());
310 testImmutableCollection(m.values());
311 //testImmutableSet(m.entrySet());
312 }
313
314 private static void clear(Map<?,?> m) {
315 try { m.clear(); }
316 catch (Throwable t) { unexpected(t); }
317 testEmptyMap(m);
318 }
319
320 private static void oneElement(Collection<Integer> c) {
321 clear(c);
322 try {
323 check(c.add(-42));
324 equal(c.toString(), "[-42]");
325 if (c instanceof Set) check(! c.add(-42));
326 } catch (Throwable t) { unexpected(t); }
327 check(! c.isEmpty()); check(c.size() == 1);
328 }
329
330 private static boolean supportsAdd(Collection<Integer> c) {
331 try { check(c.add(778347983)); }
332 catch (UnsupportedOperationException t) { return false; }
333 catch (Throwable t) { unexpected(t); }
334
335 try {
336 check(c.contains(778347983));
337 check(c.remove(778347983));
338 } catch (Throwable t) { unexpected(t); }
339 return true;
340 }
341
342 private static boolean supportsRemove(Collection<Integer> c) {
343 try { check(! c.remove(19134032)); }
344 catch (UnsupportedOperationException t) { return false; }
345 catch (Throwable t) { unexpected(t); }
346 return true;
347 }
348
349 private static void checkFunctionalInvariants(Collection<Integer> c) {
350 try {
351 checkContainsSelf(c);
352 checkContainsEmpty(c);
353 check(c.size() != 0 ^ c.isEmpty());
354
355 {
356 int size = 0;
357 for (Integer i : c) size++;
358 check(c.size() == size);
359 }
360
361 check(c.toArray().length == c.size());
362 check(c.toArray().getClass() == Object[].class
363 ||
364 // !!!!
365 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
366 // should be Object[].class
367 (c.getClass().getName().equals("java.util.Arrays$ArrayList"))
368 );
369 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
370 Integer[] a = c.toArray(new Integer[size]);
371 check((size > c.size()) || a.length == c.size());
372 int i = 0; for (Integer j : c) check(a[i++] == j);
373 check((size <= c.size()) || (a[c.size()] == null));
374 check(a.getClass() == Integer[].class);
375 }
376
377 check(c.equals(c));
378 if (c instanceof Serializable) {
379 //System.out.printf("Serializing %s%n", c.getClass().getName());
380 try {
381 Object clone = serialClone(c);
382 equal(c instanceof Serializable,
383 clone instanceof Serializable);
384 equal(c instanceof RandomAccess,
385 clone instanceof RandomAccess);
386 if ((c instanceof List) || (c instanceof Set))
387 equal(c, clone);
388 else
389 equal(new HashSet<Integer>(c),
390 new HashSet<Integer>(serialClone(c)));
391 } catch (Error xxx) {
392 if (! (xxx.getCause() instanceof NotSerializableException))
393 throw xxx;
394 }
395 }
396 }
397 catch (Throwable t) { unexpected(t); }
398 }
399
400 //----------------------------------------------------------------
401 // If add(null) succeeds, contains(null) & remove(null) should succeed
402 //----------------------------------------------------------------
403 private static void testNullElement(Collection<Integer> c) {
404
405 try {
406 check(c.add(null));
407 if (c.size() == 1)
408 equal(c.toString(), "[null]");
409 try {
410 checkFunctionalInvariants(c);
411 check(c.contains(null));
412 check(c.remove(null));
413 }
414 catch (Throwable t) { unexpected(t); }
415 }
416 catch (NullPointerException e) { /* OK */ }
417 catch (Throwable t) { unexpected(t); }
418 }
419
420
421 //----------------------------------------------------------------
422 // If add("x") succeeds, contains("x") & remove("x") should succeed
423 //----------------------------------------------------------------
424 @SuppressWarnings("unchecked")
425 private static void testStringElement(Collection<Integer> c) {
426 Collection x = (Collection)c; // Make type-unsafe
427 try {
428 check(x.add("x"));
429 try {
430 check(x.contains("x"));
431 check(x.remove("x"));
432 } catch (Throwable t) { unexpected(t); }
433 }
434 catch (ClassCastException e) { /* OK */ }
435 catch (Throwable t) { unexpected(t); }
436 }
437
438 private static void testConcurrentCollection(Collection<Integer> c) {
439 try {
440 c.add(1);
441 Iterator<Integer> it = c.iterator();
442 check(it.hasNext());
443 clear(c);
444 check(it.next() instanceof Integer); // No CME
445 check(c.isEmpty());
446 }
447 catch (Throwable t) { unexpected(t); }
448 }
449
450 private static void testQueue(Queue<Integer> q) {
451 q.clear();
452 for (int i = 0; i < 5; i++) {
453 testQueueAddRemove(q, null);
454 testQueueAddRemove(q, 537);
455 q.add(i);
456 }
457 equal(q.size(), 5);
458 checkFunctionalInvariants(q);
459 q.poll();
460 equal(q.size(), 4);
461 checkFunctionalInvariants(q);
462 if ((q instanceof LinkedBlockingQueue) ||
463 (q instanceof LinkedBlockingDeque) ||
464 (q instanceof ConcurrentLinkedDeque) ||
465 (q instanceof ConcurrentLinkedQueue)) {
466 testQueueIteratorRemove(q);
467 }
468 }
469
470 private static void testQueueAddRemove(final Queue<Integer> q,
471 final Integer e) {
472 final List<Integer> originalContents = new ArrayList<Integer>(q);
473 final boolean isEmpty = q.isEmpty();
474 final boolean isList = (q instanceof List);
475 final List asList = isList ? (List) q : null;
476 check(!q.contains(e));
477 try {
478 q.add(e);
479 } catch (NullPointerException npe) {
480 check(e == null);
481 return; // Null elements not supported
482 }
483 check(q.contains(e));
484 check(q.remove(e));
485 check(!q.contains(e));
486 equal(new ArrayList<Integer>(q), originalContents);
487
488 if (q instanceof Deque<?>) {
489 final Deque<Integer> deq = (Deque<Integer>) q;
490 final List<Integer> singleton = Collections.singletonList(e);
491
492 // insert, query, remove element at head
493 if (isEmpty) {
494 THROWS(NoSuchElementException.class,
495 new Fun(){void f(){ deq.getFirst(); }},
496 new Fun(){void f(){ deq.element(); }},
497 new Fun(){void f(){ deq.iterator().next(); }});
498 check(deq.peekFirst() == null);
499 check(deq.peek() == null);
500 } else {
501 check(deq.getFirst() != e);
502 check(deq.element() != e);
503 check(deq.iterator().next() != e);
504 check(deq.peekFirst() != e);
505 check(deq.peek() != e);
506 }
507 check(!deq.contains(e));
508 check(!deq.removeFirstOccurrence(e));
509 check(!deq.removeLastOccurrence(e));
510 if (isList) {
511 check(asList.indexOf(e) == -1);
512 check(asList.lastIndexOf(e) == -1);
513 }
514 switch (rnd.nextInt(isList ? 4 : 3)) {
515 case 0: deq.addFirst(e); break;
516 case 1: check(deq.offerFirst(e)); break;
517 case 2: deq.push(e); break;
518 case 3: asList.add(0, e); break;
519 default: throw new AssertionError();
520 }
521 check(deq.peekFirst() == e);
522 check(deq.getFirst() == e);
523 check(deq.element() == e);
524 check(deq.peek() == e);
525 check(deq.iterator().next() == e);
526 check(deq.contains(e));
527 if (isList) {
528 check(asList.get(0) == e);
529 check(asList.indexOf(e) == 0);
530 check(asList.lastIndexOf(e) == 0);
531 check(asList.subList(0, 1).equals(singleton));
532 }
533 switch (rnd.nextInt(isList ? 11 : 9)) {
534 case 0: check(deq.pollFirst() == e); break;
535 case 1: check(deq.removeFirst() == e); break;
536 case 2: check(deq.remove() == e); break;
537 case 3: check(deq.pop() == e); break;
538 case 4: check(deq.removeFirstOccurrence(e)); break;
539 case 5: check(deq.removeLastOccurrence(e)); break;
540 case 6: check(deq.remove(e)); break;
541 case 7: check(deq.removeAll(singleton)); break;
542 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
543 case 9: asList.remove(0); break;
544 case 10: asList.subList(0, 1).clear(); break;
545 default: throw new AssertionError();
546 }
547 if (isEmpty) {
548 THROWS(NoSuchElementException.class,
549 new Fun(){void f(){ deq.getFirst(); }},
550 new Fun(){void f(){ deq.element(); }},
551 new Fun(){void f(){ deq.iterator().next(); }});
552 check(deq.peekFirst() == null);
553 check(deq.peek() == null);
554 } else {
555 check(deq.getFirst() != e);
556 check(deq.element() != e);
557 check(deq.iterator().next() != e);
558 check(deq.peekFirst() != e);
559 check(deq.peek() != e);
560 }
561 check(!deq.contains(e));
562 check(!deq.removeFirstOccurrence(e));
563 check(!deq.removeLastOccurrence(e));
564 if (isList) {
565 check(isEmpty || asList.get(0) != e);
566 check(asList.indexOf(e) == -1);
567 check(asList.lastIndexOf(e) == -1);
568 }
569 equal(new ArrayList<Integer>(deq), originalContents);
570
571 // insert, query, remove element at tail
572 if (isEmpty) {
573 check(deq.peekLast() == null);
574 THROWS(NoSuchElementException.class,
575 new Fun(){void f(){ deq.getLast(); }});
576 } else {
577 check(deq.peekLast() != e);
578 check(deq.getLast() != e);
579 }
580 switch (rnd.nextInt(isList ? 6 : 4)) {
581 case 0: deq.addLast(e); break;
582 case 1: check(deq.offerLast(e)); break;
583 case 2: check(deq.add(e)); break;
584 case 3: deq.addAll(singleton); break;
585 case 4: asList.addAll(deq.size(), singleton); break;
586 case 5: asList.add(deq.size(), e); break;
587 default: throw new AssertionError();
588 }
589 check(deq.peekLast() == e);
590 check(deq.getLast() == e);
591 check(deq.contains(e));
592 if (isList) {
593 ListIterator it = asList.listIterator(asList.size());
594 check(it.previous() == e);
595 check(asList.get(asList.size() - 1) == e);
596 check(asList.indexOf(e) == asList.size() - 1);
597 check(asList.lastIndexOf(e) == asList.size() - 1);
598 int size = asList.size();
599 check(asList.subList(size - 1, size).equals(singleton));
600 }
601 switch (rnd.nextInt(isList ? 8 : 6)) {
602 case 0: check(deq.pollLast() == e); break;
603 case 1: check(deq.removeLast() == e); break;
604 case 2: check(deq.removeFirstOccurrence(e)); break;
605 case 3: check(deq.removeLastOccurrence(e)); break;
606 case 4: check(deq.remove(e)); break;
607 case 5: check(deq.removeAll(singleton)); break;
608 case 6: asList.remove(asList.size() - 1); break;
609 case 7:
610 ListIterator it = asList.listIterator(asList.size());
611 it.previous();
612 it.remove();
613 break;
614 default: throw new AssertionError();
615 }
616 if (isEmpty) {
617 check(deq.peekLast() == null);
618 THROWS(NoSuchElementException.class,
619 new Fun(){void f(){ deq.getLast(); }});
620 } else {
621 check(deq.peekLast() != e);
622 check(deq.getLast() != e);
623 }
624 check(!deq.contains(e));
625 equal(new ArrayList<Integer>(deq), originalContents);
626
627 // Test operations on empty deque
628 switch (rnd.nextInt(isList ? 4 : 2)) {
629 case 0: deq.clear(); break;
630 case 1:
631 Iterator it = deq.iterator();
632 while (it.hasNext()) {
633 it.next();
634 it.remove();
635 }
636 break;
637 case 2: asList.subList(0, asList.size()).clear(); break;
638 case 3:
639 ListIterator lit = asList.listIterator(asList.size());
640 while (lit.hasPrevious()) {
641 lit.previous();
642 lit.remove();
643 }
644 break;
645 default: throw new AssertionError();
646 }
647 testEmptyCollection(deq);
648 check(!deq.iterator().hasNext());
649 if (isList) {
650 check(!asList.listIterator().hasPrevious());
651 THROWS(NoSuchElementException.class,
652 new Fun(){void f(){ asList.listIterator().previous(); }});
653 }
654 THROWS(NoSuchElementException.class,
655 new Fun(){void f(){ deq.iterator().next(); }},
656 new Fun(){void f(){ deq.element(); }},
657 new Fun(){void f(){ deq.getFirst(); }},
658 new Fun(){void f(){ deq.getLast(); }},
659 new Fun(){void f(){ deq.pop(); }},
660 new Fun(){void f(){ deq.remove(); }},
661 new Fun(){void f(){ deq.removeFirst(); }},
662 new Fun(){void f(){ deq.removeLast(); }});
663
664 check(deq.poll() == null);
665 check(deq.pollFirst() == null);
666 check(deq.pollLast() == null);
667 check(deq.peek() == null);
668 check(deq.peekFirst() == null);
669 check(deq.peekLast() == null);
670 check(!deq.removeFirstOccurrence(e));
671 check(!deq.removeLastOccurrence(e));
672
673 check(deq.addAll(originalContents) == !isEmpty);
674 equal(new ArrayList<Integer>(deq), originalContents);
675 check(!deq.addAll(Collections.<Integer>emptyList()));
676 equal(new ArrayList<Integer>(deq), originalContents);
677 }
678 }
679
680 private static void testQueueIteratorRemove(Queue<Integer> q) {
681 System.err.printf("testQueueIteratorRemove %s%n",
682 q.getClass().getSimpleName());
683 q.clear();
684 for (int i = 0; i < 5; i++)
685 q.add(i);
686 Iterator<Integer> it = q.iterator();
687 check(it.hasNext());
688 for (int i = 3; i >= 0; i--)
689 q.remove(i);
690 equal(it.next(), 0);
691 equal(it.next(), 4);
692
693 q.clear();
694 for (int i = 0; i < 5; i++)
695 q.add(i);
696 it = q.iterator();
697 equal(it.next(), 0);
698 check(it.hasNext());
699 for (int i = 1; i < 4; i++)
700 q.remove(i);
701 equal(it.next(), 1);
702 equal(it.next(), 4);
703 }
704
705 private static void testList(final List<Integer> l) {
706 //----------------------------------------------------------------
707 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
708 // doesn't throw IndexOutOfBoundsException
709 //----------------------------------------------------------------
710 try {
711 l.addAll(-1, Collections.<Integer>emptyList());
712 fail("Expected IndexOutOfBoundsException not thrown");
713 }
714 catch (UnsupportedOperationException ignored) {/* OK */}
715 catch (IndexOutOfBoundsException ignored) {/* OK */}
716 catch (Throwable t) { unexpected(t); }
717
718 // equal(l instanceof Serializable,
719 // l.subList(0,0) instanceof Serializable);
720 if (l.subList(0,0) instanceof Serializable)
721 check(l instanceof Serializable);
722
723 equal(l instanceof RandomAccess,
724 l.subList(0,0) instanceof RandomAccess);
725
726 l.iterator();
727 l.listIterator();
728 l.listIterator(0);
729 l.listIterator(l.size());
730 THROWS(IndexOutOfBoundsException.class,
731 new Fun(){void f(){l.listIterator(-1);}},
732 new Fun(){void f(){l.listIterator(l.size() + 1);}});
733
734 if (l instanceof AbstractList) {
735 try {
736 int size = l.size();
737 AbstractList<Integer> abList = (AbstractList<Integer>) l;
738 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class });
739 m.setAccessible(true);
740 m.invoke(abList, new Object[] { 0, 0 });
741 m.invoke(abList, new Object[] { size, size });
742 equal(size, l.size());
743 }
744 catch (UnsupportedOperationException ignored) {/* OK */}
745 catch (Throwable t) { unexpected(t); }
746 }
747 }
748
749 private static void testCollection(Collection<Integer> c) {
750 try { testCollection1(c); }
751 catch (Throwable t) { unexpected(t); }
752 }
753
754 private static void testCollection1(Collection<Integer> c) {
755
756 System.out.println("\n==> " + c.getClass().getName());
757
758 checkFunctionalInvariants(c);
759
760 if (! supportsAdd(c)) return;
761 //System.out.println("add() supported");
762
763 if (c instanceof NavigableSet) {
764 System.out.println("NavigableSet tests...");
765
766 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
767 testNavigableSet(ns);
768 testNavigableSet(ns.headSet(6, false));
769 testNavigableSet(ns.headSet(5, true));
770 testNavigableSet(ns.tailSet(0, false));
771 testNavigableSet(ns.tailSet(1, true));
772 testNavigableSet(ns.subSet(0, false, 5, true));
773 testNavigableSet(ns.subSet(1, true, 6, false));
774 }
775
776 if (c instanceof Queue)
777 testQueue((Queue<Integer>)c);
778
779 if (c instanceof List)
780 testList((List<Integer>)c);
781
782 check(supportsRemove(c));
783
784 try {
785 oneElement(c);
786 checkFunctionalInvariants(c);
787 }
788 catch (Throwable t) { unexpected(t); }
789
790 clear(c); testNullElement(c);
791 oneElement(c); testNullElement(c);
792
793 clear(c); testStringElement(c);
794 oneElement(c); testStringElement(c);
795
796 if (c.getClass().getName().matches(".*concurrent.*"))
797 testConcurrentCollection(c);
798
799 //----------------------------------------------------------------
800 // The "all" operations should throw NPE when passed null
801 //----------------------------------------------------------------
802 {
803 clear(c);
804 try {
805 c.removeAll(null);
806 fail("Expected NullPointerException");
807 }
808 catch (NullPointerException e) { pass(); }
809 catch (Throwable t) { unexpected(t); }
810
811 oneElement(c);
812 try {
813 c.removeAll(null);
814 fail("Expected NullPointerException");
815 }
816 catch (NullPointerException e) { pass(); }
817 catch (Throwable t) { unexpected(t); }
818
819 clear(c);
820 try {
821 c.retainAll(null);
822 fail("Expected NullPointerException");
823 }
824 catch (NullPointerException e) { pass(); }
825 catch (Throwable t) { unexpected(t); }
826
827 oneElement(c);
828 try {
829 c.retainAll(null);
830 fail("Expected NullPointerException");
831 }
832 catch (NullPointerException e) { pass(); }
833 catch (Throwable t) { unexpected(t); }
834
835 oneElement(c);
836 try {
837 c.addAll(null);
838 fail("Expected NullPointerException");
839 }
840 catch (NullPointerException e) { pass(); }
841 catch (Throwable t) { unexpected(t); }
842
843 oneElement(c);
844 try {
845 c.containsAll(null);
846 fail("Expected NullPointerException");
847 }
848 catch (NullPointerException e) { pass(); }
849 catch (Throwable t) { unexpected(t); }
850 }
851 }
852
853 //----------------------------------------------------------------
854 // Map
855 //----------------------------------------------------------------
856 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
857 check(m.keySet().size() == m.entrySet().size());
858 check(m.keySet().size() == m.size());
859 checkFunctionalInvariants(m.keySet());
860 checkFunctionalInvariants(m.values());
861 check(m.size() != 0 ^ m.isEmpty());
862 }
863
864 private static void testMap(Map<Integer,Integer> m) {
865 System.out.println("\n==> " + m.getClass().getName());
866
867 if (m instanceof ConcurrentMap)
868 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
869
870 if (m instanceof NavigableMap) {
871 System.out.println("NavigableMap tests...");
872
873 NavigableMap<Integer,Integer> nm =
874 (NavigableMap<Integer,Integer>) m;
875 testNavigableMapRemovers(nm);
876 testNavigableMap(nm);
877 testNavigableMap(nm.headMap(6, false));
878 testNavigableMap(nm.headMap(5, true));
879 testNavigableMap(nm.tailMap(0, false));
880 testNavigableMap(nm.tailMap(1, true));
881 testNavigableMap(nm.subMap(1, true, 6, false));
882 testNavigableMap(nm.subMap(0, false, 5, true));
883 }
884
885 checkFunctionalInvariants(m);
886
887 if (supportsClear(m)) {
888 try { clear(m); }
889 catch (Throwable t) { unexpected(t); }
890 }
891
892 if (supportsPut(m)) {
893 try {
894 check(m.put(3333, 77777) == null);
895 check(m.put(9134, 74982) == null);
896 check(m.get(9134) == 74982);
897 check(m.put(9134, 1382) == 74982);
898 check(m.get(9134) == 1382);
899 check(m.size() == 2);
900 checkFunctionalInvariants(m);
901 checkNPEConsistency(m);
902 }
903 catch (Throwable t) { unexpected(t); }
904 }
905 }
906
907 private static boolean supportsPut(Map<Integer,Integer> m) {
908 // We're asking for .equals(...) semantics
909 if (m instanceof IdentityHashMap) return false;
910
911 try { check(m.put(778347983,12735) == null); }
912 catch (UnsupportedOperationException t) { return false; }
913 catch (Throwable t) { unexpected(t); }
914
915 try {
916 check(m.containsKey(778347983));
917 check(m.remove(778347983) != null);
918 } catch (Throwable t) { unexpected(t); }
919 return true;
920 }
921
922 private static boolean supportsClear(Map<?,?> m) {
923 try { m.clear(); }
924 catch (UnsupportedOperationException t) { return false; }
925 catch (Throwable t) { unexpected(t); }
926 return true;
927 }
928
929 //----------------------------------------------------------------
930 // ConcurrentMap
931 //----------------------------------------------------------------
932 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
933 System.out.println("ConcurrentMap tests...");
934
935 try {
936 clear(m);
937
938 check(m.putIfAbsent(18357,7346) == null);
939 check(m.containsKey(18357));
940 check(m.putIfAbsent(18357,8263) == 7346);
941 try { m.putIfAbsent(18357,null); fail("NPE"); }
942 catch (NullPointerException t) { }
943 check(m.containsKey(18357));
944
945 check(! m.replace(18357,8888,7777));
946 check(m.containsKey(18357));
947 try { m.replace(18357,null,7777); fail("NPE"); }
948 catch (NullPointerException t) { }
949 check(m.containsKey(18357));
950 check(m.get(18357) == 7346);
951 check(m.replace(18357,7346,5555));
952 check(m.replace(18357,5555,7346));
953 check(m.get(18357) == 7346);
954
955 check(m.replace(92347,7834) == null);
956 try { m.replace(18357,null); fail("NPE"); }
957 catch (NullPointerException t) { }
958 check(m.replace(18357,7346) == 7346);
959 check(m.replace(18357,5555) == 7346);
960 check(m.get(18357) == 5555);
961 check(m.replace(18357,7346) == 5555);
962 check(m.get(18357) == 7346);
963
964 check(! m.remove(18357,9999));
965 check(m.get(18357) == 7346);
966 check(m.containsKey(18357));
967 check(! m.remove(18357,null)); // 6272521
968 check(m.get(18357) == 7346);
969 check(m.remove(18357,7346));
970 check(m.get(18357) == null);
971 check(! m.containsKey(18357));
972 check(m.isEmpty());
973
974 m.putIfAbsent(1,2);
975 check(m.size() == 1);
976 check(! m.remove(1,null));
977 check(! m.remove(1,null));
978 check(! m.remove(1,1));
979 check(m.remove(1,2));
980 check(m.isEmpty());
981
982 testEmptyMap(m);
983 }
984 catch (Throwable t) { unexpected(t); }
985 }
986
987 private static void throwsConsistently(Class<? extends Throwable> k,
988 Iterable<Fun> fs) {
989 List<Class<? extends Throwable>> threw
990 = new ArrayList<Class<? extends Throwable>>();
991 for (Fun f : fs)
992 try { f.f(); threw.add(null); }
993 catch (Throwable t) {
994 check(k.isAssignableFrom(t.getClass()));
995 threw.add(t.getClass());
996 }
997 if (new HashSet<Object>(threw).size() != 1)
998 fail(threw.toString());
999 }
1000
1001 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
1002 m.clear();
1003 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
1004 ? (ConcurrentMap<T,Integer>) m
1005 : null;
1006 List<Fun> fs = new ArrayList<Fun>();
1007 fs.add(new Fun(){void f(){ check(! m.containsKey(null));}});
1008 fs.add(new Fun(){void f(){ equal(m.remove(null), null);}});
1009 fs.add(new Fun(){void f(){ equal(m.get(null), null);}});
1010 if (cm != null) {
1011 fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});}
1012 throwsConsistently(NullPointerException.class, fs);
1013
1014 fs.clear();
1015 final Map<T,Integer> sm = singletonMap(null,1);
1016 fs.add(new Fun(){void f(){ equal(m.put(null,1), null); m.clear();}});
1017 fs.add(new Fun(){void f(){ m.putAll(sm); m.clear();}});
1018 if (cm != null) {
1019 fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});
1020 fs.add(new Fun(){void f(){ equal(cm.putIfAbsent(null,1), 1);}});
1021 fs.add(new Fun(){void f(){ equal(cm.replace(null,1), null);}});
1022 fs.add(new Fun(){void f(){ equal(cm.replace(null,1, 1), 1);}});
1023 }
1024 throwsConsistently(NullPointerException.class, fs);
1025 }
1026
1027 //----------------------------------------------------------------
1028 // NavigableMap
1029 //----------------------------------------------------------------
1030 private static void
1031 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1032 Integer i,
1033 Integer lower,
1034 Integer floor,
1035 Integer ceiling,
1036 Integer higher) {
1037 equal(m.lowerKey(i), lower);
1038 equal(m.floorKey(i), floor);
1039 equal(m.ceilingKey(i), ceiling);
1040 equal(m.higherKey(i), higher);
1041 }
1042
1043 private static void
1044 checkNavigableSetKeys(NavigableSet<Integer> m,
1045 Integer i,
1046 Integer lower,
1047 Integer floor,
1048 Integer ceiling,
1049 Integer higher) {
1050 equal(m.lower(i), lower);
1051 equal(m.floor(i), floor);
1052 equal(m.ceiling(i), ceiling);
1053 equal(m.higher(i), higher);
1054 }
1055
1056 static final Random rnd = new Random();
1057 static void equalNext(final Iterator<?> it, Object expected) {
1058 if (rnd.nextBoolean())
1059 check(it.hasNext());
1060 equal(it.next(), expected);
1061 }
1062
1063 static void equalMaps(Map m1, Map m2) {
1064 equal(m1, m2);
1065 equal(m2, m1);
1066 equal(m1.size(), m2.size());
1067 equal(m1.isEmpty(), m2.isEmpty());
1068 equal(m1.toString(), m2.toString());
1069 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1070 }
1071
1072 @SuppressWarnings({"unchecked", "rawtypes"})
1073 static void testNavigableMapRemovers(NavigableMap m)
1074 {
1075 final Map emptyMap = new HashMap();
1076
1077 final Map singletonMap = new HashMap();
1078 singletonMap.put(1, 2);
1079
1080 abstract class NavigableMapView {
1081 abstract NavigableMap view(NavigableMap m);
1082 }
1083
1084 NavigableMapView[] views = {
1085 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1086 return m; }},
1087 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1088 return m.headMap(99, true); }},
1089 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1090 return m.tailMap(-99, false); }},
1091 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1092 return m.subMap(-99, true, 99, false); }},
1093 };
1094
1095 abstract class Remover {
1096 abstract void remove(NavigableMap m, Object k, Object v);
1097 }
1098
1099 Remover[] removers = {
1100 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1101 equal(m.remove(k), v); }},
1102
1103 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1104 equal(m.descendingMap().remove(k), v); }},
1105 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1106 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1107 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1108 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1109
1110 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1111 equal(m.headMap(86, true).remove(k), v); }},
1112 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1113 equal(m.tailMap(-86, true).remove(k), v); }},
1114 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1115 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1116
1117 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1118 check(m.keySet().remove(k)); }},
1119 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1120 check(m.navigableKeySet().remove(k)); }},
1121
1122 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1123 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1124 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1125 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1126 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1127 check(m.navigableKeySet().subSet(-86, true, 86, false)
1128 .remove(k)); }},
1129
1130 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1131 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1132 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1133 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1134 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1135 check(m.descendingKeySet().subSet(86, true, -86, false)
1136 .remove(k)); }},
1137 };
1138
1139 for (NavigableMapView view : views) {
1140 for (Remover remover : removers) {
1141 try {
1142 m.clear();
1143 equalMaps(m, emptyMap);
1144 equal(m.put(1, 2), null);
1145 equalMaps(m, singletonMap);
1146 NavigableMap v = view.view(m);
1147 remover.remove(v, 1, 2);
1148 equalMaps(m, emptyMap);
1149 } catch (Throwable t) { unexpected(t); }
1150 }
1151 }
1152 }
1153
1154 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1155 {
1156 clear(m);
1157 checkNavigableMapKeys(m, 1, null, null, null, null);
1158
1159 equal(m.put(1, 2), null);
1160 equal(m.put(3, 4), null);
1161 equal(m.put(5, 9), null);
1162
1163 equal(m.put(1, 2), 2);
1164 equal(m.put(3, 4), 4);
1165 equal(m.put(5, 6), 9);
1166
1167 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1168 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1169 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1170 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1171 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1172 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1173
1174 for (final Iterator<Integer> it :
1175 (Iterator<Integer>[])
1176 new Iterator<?>[] {
1177 m.descendingKeySet().iterator(),
1178 m.navigableKeySet().descendingIterator()}) {
1179 equalNext(it, 5);
1180 equalNext(it, 3);
1181 equalNext(it, 1);
1182 check(! it.hasNext());
1183 THROWS(NoSuchElementException.class,
1184 new Fun(){void f(){it.next();}});
1185 }
1186
1187 {
1188 final Iterator<Map.Entry<Integer,Integer>> it
1189 = m.descendingMap().entrySet().iterator();
1190 check(it.hasNext()); equal(it.next().getKey(), 5);
1191 check(it.hasNext()); equal(it.next().getKey(), 3);
1192 check(it.hasNext()); equal(it.next().getKey(), 1);
1193 check(! it.hasNext());
1194 THROWS(NoSuchElementException.class,
1195 new Fun(){void f(){it.next();}});
1196 }
1197
1198 prepMapForDescItrTests(m);
1199 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator());
1200 prepMapForDescItrTests(m);
1201 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());
1202 prepMapForDescItrTests(m);
1203 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator());
1204
1205 prepMapForDescItrTests(m);
1206 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator());
1207 prepMapForDescItrTests(m);
1208 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator());
1209 prepMapForDescItrTests(m);
1210 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator());
1211
1212 prepMapForDescItrTests(m);
1213 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator());
1214 prepMapForDescItrTests(m);
1215 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator());
1216 prepMapForDescItrTests(m);
1217 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator());
1218
1219 prepMapForDescItrTests(m);
1220 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator());
1221 prepMapForDescItrTests(m);
1222 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator());
1223 prepMapForDescItrTests(m);
1224 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator());
1225
1226 prepMapForDescItrTests(m);
1227 checkDescItrRmFirst((Collection)m.entrySet(),
1228 m.descendingMap().entrySet().iterator());
1229 prepMapForDescItrTests(m);
1230 checkDescItrRmMid((Collection)m.entrySet(),
1231 m.descendingMap().entrySet().iterator());
1232 prepMapForDescItrTests(m);
1233 checkDescItrRmLast((Collection)m.entrySet(),
1234 m.descendingMap().entrySet().iterator());
1235 }
1236
1237 private static void testNavigableSet(NavigableSet<Integer> s) {
1238 clear(s);
1239 checkNavigableSetKeys(s, 1, null, null, null, null);
1240
1241 check(s.add(1));
1242 check(s.add(3));
1243 check(s.add(5));
1244
1245 check(! s.add(1));
1246 check(! s.add(3));
1247 check(! s.add(5));
1248
1249 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1250 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1251 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1252 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1253 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1254 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1255
1256 for (final Iterator<Integer> it :
1257 (Iterator<Integer>[])
1258 new Iterator<?>[] {
1259 s.descendingIterator(),
1260 s.descendingSet().iterator()}) {
1261 equalNext(it, 5);
1262 equalNext(it, 3);
1263 equalNext(it, 1);
1264 check(! it.hasNext());
1265 THROWS(NoSuchElementException.class,
1266 new Fun(){void f(){it.next();}});
1267 }
1268
1269 prepSetForDescItrTests(s);
1270 checkDescItrRmFirst(s, s.descendingIterator());
1271 prepSetForDescItrTests(s);
1272 checkDescItrRmMid(s, s.descendingIterator());
1273 prepSetForDescItrTests(s);
1274 checkDescItrRmLast(s, s.descendingIterator());
1275
1276 prepSetForDescItrTests(s);
1277 checkDescItrRmFirst(s, s.descendingSet().iterator());
1278 prepSetForDescItrTests(s);
1279 checkDescItrRmMid(s, s.descendingSet().iterator());
1280 prepSetForDescItrTests(s);
1281 checkDescItrRmLast(s, s.descendingSet().iterator());
1282 }
1283
1284 private static void prepSetForDescItrTests(Set s) {
1285 clear(s);
1286 check(s.add(1));
1287 check(s.add(3));
1288 check(s.add(5));
1289 }
1290
1291 private static void prepMapForDescItrTests(Map m) {
1292 clear(m);
1293 equal(m.put(1, 2), null);
1294 equal(m.put(3, 4), null);
1295 equal(m.put(5, 9), null);
1296 }
1297
1298 //--------------------------------------------------------------------
1299 // Check behavior of descending iterator when first element is removed
1300 //--------------------------------------------------------------------
1301 private static <T> void checkDescItrRmFirst(Collection<T> ascColl,
1302 Iterator<T> descItr) {
1303 T[] expected = (T[]) ascColl.toArray();
1304 int idx = expected.length -1;
1305
1306 equalNext(descItr, expected[idx--]);
1307 descItr.remove();
1308 while(idx >= 0 && descItr.hasNext()) {
1309 equalNext(descItr, expected[idx--]);
1310 }
1311 equal(descItr.hasNext(), false);
1312 equal(idx, -1);
1313 }
1314
1315 //-----------------------------------------------------------------------
1316 // Check behavior of descending iterator when a middle element is removed
1317 //-----------------------------------------------------------------------
1318 private static <T> void checkDescItrRmMid(Collection<T> ascColl,
1319 Iterator<T> descItr) {
1320 T[] expected = (T[]) ascColl.toArray();
1321 int idx = expected.length -1;
1322
1323 while (idx >= expected.length / 2) {
1324 equalNext(descItr, expected[idx--]);
1325 }
1326 descItr.remove();
1327 while (idx >= 0 && descItr.hasNext()) {
1328 equalNext(descItr, expected[idx--]);
1329 }
1330 equal(descItr.hasNext(), false);
1331 equal(idx, -1);
1332 }
1333
1334 //-----------------------------------------------------------------------
1335 // Check behavior of descending iterator when the last element is removed
1336 //-----------------------------------------------------------------------
1337 private static <T> void checkDescItrRmLast(Collection<T> ascColl,
1338 Iterator<T> descItr) {
1339 T[] expected = (T[]) ascColl.toArray();
1340 int idx = expected.length -1;
1341
1342 while (idx >= 0 && descItr.hasNext()) {
1343 equalNext(descItr, expected[idx--]);
1344 }
1345 equal(idx, -1);
1346 equal(descItr.hasNext(), false);
1347 descItr.remove();
1348 equal(ascColl.contains(expected[0]), false);
1349 }
1350
1351 //--------------------- Infrastructure ---------------------------
1352 static volatile int passed = 0, failed = 0;
1353 static void pass() { passed++; }
1354 static void fail() { failed++; Thread.dumpStack(); }
1355 static void fail(String msg) { System.out.println(msg); fail(); }
1356 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1357 static void check(boolean cond) { if (cond) pass(); else fail(); }
1358 static void equal(Object x, Object y) {
1359 if (x == null ? y == null : x.equals(y)) pass();
1360 else {System.out.println(x + " not equal to " + y); fail();}}
1361 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1362 public static void main(String[] args) throws Throwable {
1363 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1364
1365 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1366 if (failed > 0) throw new Exception("Some tests failed");
1367 }
1368 private static abstract class Fun {abstract void f() throws Throwable;}
1369 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1370 for (Fun f : fs)
1371 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1372 catch (Throwable t) {
1373 if (k.isAssignableFrom(t.getClass())) pass();
1374 else unexpected(t);}}
1375 static byte[] serializedForm(Object obj) {
1376 try {
1377 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1378 new ObjectOutputStream(baos).writeObject(obj);
1379 return baos.toByteArray();
1380 } catch (IOException e) { throw new Error(e); }}
1381 static Object readObject(byte[] bytes)
1382 throws IOException, ClassNotFoundException {
1383 InputStream is = new ByteArrayInputStream(bytes);
1384 return new ObjectInputStream(is).readObject();}
1385 @SuppressWarnings("unchecked")
1386 static <T> T serialClone(T obj) {
1387 try { return (T) readObject(serializedForm(obj)); }
1388 catch (Exception e) { throw new Error(e); }}
1389 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1390 ArrayList<E> list = new ArrayList<>();
1391 public boolean remove(Object obj) {
1392 return list.remove(obj);
1393 }
1394 public boolean add(E e) {
1395 return list.add(e);
1396 }
1397 public Iterator<E> iterator() {
1398 return list.iterator();
1399 }
1400 public int size() {
1401 return list.size();
1402 }
1403 }
1404 private static class NewAbstractSet<E> extends AbstractSet<E> {
1405 HashSet<E> set = new HashSet<>();
1406 public boolean remove(Object obj) {
1407 return set.remove(obj);
1408 }
1409 public boolean add(E e) {
1410 return set.add(e);
1411 }
1412 public Iterator<E> iterator() {
1413 return set.iterator();
1414 }
1415 public int size() {
1416 return set.size();
1417 }
1418 }
1419
1420 }