1 /*
2 * Copyright (c) 2006, 2014, 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 6420753 6242436 6691185
27 * @summary Compare NavigableMap implementations for identical behavior
28 * @run main LockStep
29 * @run main/othervm -XX:+AggressiveOpts LockStep
30 * @run main/othervm -XX:+AggressiveOpts -Dthorough=true LockStep
31 * @author Martin Buchholz
32 */
33
34 import java.io.*;
35 import java.util.*;
36 import java.util.concurrent.*;
37 import static java.util.Collections.*;
38
39 @SuppressWarnings("unchecked")
40 public class LockStep {
41 static final int DEFAULT_SIZE = 5;
42 static int size; // Running time is O(size**2)
43
44 static int intArg(String[] args, int i, int defaultValue) {
45 return args.length > i ? Integer.parseInt(args[i]) : defaultValue;
46 }
47
48 // Pass -Dthorough=true for more exhaustive testing
49 static final boolean thorough = Boolean.getBoolean("thorough");
50
51 static boolean maybe(int n) { return rnd.nextInt(n) == 0; }
52
53 static void realMain(String[] args) {
54 size = intArg(args, 0, DEFAULT_SIZE);
55
56 lockSteps(new TreeMap(),
57 new ConcurrentSkipListMap());
58 lockSteps(new TreeMap(),
59 Collections.checkedNavigableMap(new TreeMap(), Integer.class, Integer.class));
60 lockSteps(new TreeMap(),
61 Collections.synchronizedNavigableMap(new TreeMap()));
62 lockSteps(new TreeMap(reverseOrder()),
63 new ConcurrentSkipListMap(reverseOrder()));
64
65 lockSteps(new TreeSet(),
66 new ConcurrentSkipListSet());
67 lockSteps(new TreeSet(),
68 Collections.checkedNavigableSet(new TreeSet(), Integer.class));
69 lockSteps(new TreeSet(),
70 Collections.synchronizedNavigableSet(new TreeSet()));
71 lockSteps(new TreeSet(reverseOrder()),
72 new ConcurrentSkipListSet(reverseOrder()));
73 }
74
75 static void lockSteps(NavigableMap m1, NavigableMap m2) {
76 if (maybe(4)) m1 = serialClone(m1);
77 if (maybe(4)) m2 = serialClone(m2);
78 lockStep(m1,
79 m2);
80 lockStep(m1.descendingMap(),
81 m2.descendingMap());
82 lockStep(fullSubMap(m1),
83 fullSubMap(m2));
84 lockStep(fullSubMap(m1.descendingMap()),
85 fullSubMap(m2.descendingMap()));
86 lockStep(fullHeadMap(m1),
87 fullHeadMap(m2));
88 lockStep(fullHeadMap(m1.descendingMap()),
89 fullHeadMap(m2.descendingMap()));
90 lockStep(fullTailMap(m1),
91 fullTailMap(m2));
92 lockStep(fullTailMap(m1.descendingMap()),
93 fullTailMap(m2.descendingMap()));
94 }
95
96 static void lockSteps(NavigableSet s1, NavigableSet s2) {
97 if (maybe(4)) s1 = serialClone(s1);
98 if (maybe(4)) s2 = serialClone(s2);
99 lockStep(s1,
100 s2);
101 lockStep(s1.descendingSet(),
102 s2.descendingSet());
103 lockStep(fullSubSet(s1),
104 fullSubSet(s2));
105 lockStep(fullSubSet(s1.descendingSet()),
106 fullSubSet(s2.descendingSet()));
107 lockStep(fullHeadSet(s1),
108 fullHeadSet(s2));
109 lockStep(fullHeadSet(s1.descendingSet()),
110 fullHeadSet(s2.descendingSet()));
111 lockStep(fullTailSet(s1),
112 fullTailSet(s2));
113 lockStep(fullTailSet(s1.descendingSet()),
114 fullTailSet(s2.descendingSet()));
115 }
116
117 static boolean isAscending(NavigableMap m) {
118 Comparator cmp = m.comparator();
119 return (cmp == null || cmp.compare(1, 2) < 0);
120 }
121
122 static NavigableMap fullSubMap(NavigableMap m) {
123 return isAscending(m)
124 ? m.subMap(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
125 : m.subMap(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
126 }
127
128 static NavigableMap fullHeadMap(NavigableMap m) {
129 return isAscending(m)
130 ? m.headMap(Integer.MAX_VALUE, true)
131 : m.headMap(Integer.MIN_VALUE, true);
132 }
133
134 static NavigableMap fullTailMap(NavigableMap m) {
135 return isAscending(m)
136 ? m.tailMap(Integer.MIN_VALUE, true)
137 : m.tailMap(Integer.MAX_VALUE, true);
138 }
139
140 static boolean isAscending(NavigableSet s) {
141 Comparator cmp = s.comparator();
142 return (cmp == null || cmp.compare(1, 2) < 0);
143 }
144
145 static NavigableSet fullSubSet(NavigableSet s) {
146 return isAscending(s)
147 ? s.subSet(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
148 : s.subSet(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
149 }
150
151 static NavigableSet fullHeadSet(NavigableSet s) {
152 return isAscending(s)
153 ? s.headSet(Integer.MAX_VALUE, true)
154 : s.headSet(Integer.MIN_VALUE, true);
155 }
156
157 static NavigableSet fullTailSet(NavigableSet s) {
158 return isAscending(s)
159 ? s.tailSet(Integer.MIN_VALUE, true)
160 : s.tailSet(Integer.MAX_VALUE, true);
161 }
162
163 static void testEmptyCollection(Collection<?> c) {
164 check(c.isEmpty());
165 equal(c.size(), 0);
166 equal(c.toString(),"[]");
167 equal(c.toArray().length, 0);
168 equal(c.toArray(new Object[0]).length, 0);
169
170 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
171 equal(c.toArray(a), a);
172 equal(a[0], null);
173 check(! c.iterator().hasNext());
174 }
175
176 static void testEmptySet(Set<?> c) {
177 testEmptyCollection(c);
178 equal(c.hashCode(), 0);
179 equal2(c, Collections.<Integer>emptySet());
180 }
181
182 static void testEmptyMap(final Map<?,?> m) {
183 check(m.isEmpty());
184 equal(m.size(), 0);
185 equal(m.toString(),"{}");
186 equal(m.hashCode(), 0);
187 testEmptySet(m.keySet());
188 testEmptySet(m.entrySet());
189 testEmptyCollection(m.values());
190 }
191
192 static final Random rnd;
193
194 static {
195 // sufficiently random for this test
196 long seed = System.nanoTime();
197 System.out.println(LockStep.class.getCanonicalName() + ": Trial random seed: " + seed );
198
199 rnd = new Random(seed);
200 }
201
202 static void equalNext(final Iterator<?> it, Object expected) {
203 if (maybe(2))
204 check(it.hasNext());
205 equal(it.next(), expected);
206 }
207
208 static Comparator comparator(NavigableSet s) {
209 Comparator cmp = s.comparator();
210 return cmp != null ? cmp : new Comparator() {
211 public int compare(Object o1, Object o2) {
212 return ((Comparable) o1).compareTo(o2); }};
213 }
214
215 static Comparator comparator(NavigableMap m) {
216 Comparator cmp = m.comparator();
217 return cmp != null ? cmp : new Comparator() {
218 public int compare(Object o1, Object o2) {
219 return ((Comparable) o1).compareTo(o2); }};
220 }
221
222 static void checkNavigableSet(final NavigableSet s) {
223 if (s.comparator() == null)
224 check(s.descendingSet().descendingSet().comparator() == null);
225 equal(s.isEmpty(), s.size() == 0);
226 equal2(s, s.descendingSet());
227 if (maybe(4) && s instanceof Serializable) {
228 try {
229 equal2(s, serialClone(s));
230 } catch(RuntimeException uhoh) {
231 if(!(uhoh.getCause() instanceof NotSerializableException)) {
232 throw uhoh;
233 }
234 }
235 }
236 Comparator cmp = comparator(s);
237 if (s.isEmpty()) {
238 THROWS(NoSuchElementException.class,
239 () -> s.first(),
240 () -> s.last());
241 equal(null, s.lower(1));
242 equal(null, s.floor(1));
243 equal(null, s.ceiling(1));
244 equal(null, s.higher(1));
245 } else {
246 Object a = s.first();
247 Object z = s.last();
248 equal(s.lower(a), null);
249 equal(s.higher(z), null);
250 equal2(s, s.tailSet(a));
251 equal2(s, s.headSet(z, true));
252 equal2(s, s.subSet(a, true, z, true));
253
254 testEmptySet(s.subSet(a, true, a, false));
255 testEmptySet(s.subSet(z, true, z, false));
256 testEmptySet(s.headSet(a, false));
257 testEmptySet(s.tailSet(z, false));
258
259 equal2(s.headSet(a, true), singleton(a));
260 equal2(s.tailSet(z, true), singleton(z));
261 }
262 Iterator[] its = new Iterator[] {
263 s.iterator(),
264 s.descendingSet().descendingSet().iterator(),
265 };
266 for (final Iterator it : its)
267 if (maybe(4))
268 THROWS(IllegalStateException.class, () -> it.remove());
269 Object prev = null;
270 for (Object e : s) {
271 check(s.contains(e));
272 for (Iterator it : its) equalNext(it, e);
273 equal(e, s.ceiling(e));
274 equal(e, s.floor(e));
275 check(s.higher(e) == null || cmp.compare(e, s.higher(e)) < 0);
276 equal(s.lower(e), prev);
277 if (prev == null) {
278 } else {
279 check(cmp.compare(prev, e) < 0);
280 }
281 prev = e;
282 }
283 for (final Iterator it : its) {
284 if (maybe(2))
285 check(! it.hasNext());
286 Fun fun = () -> it.next();
287 THROWS(NoSuchElementException.class, fun, fun, fun);
288 }
289 }
290
291 static void equalIterators(final Iterator<?> it1,
292 final Iterator<?> it2) {
293 while (it1.hasNext()) {
294 if (maybe(2))
295 check(it2.hasNext());
296 equal(it1.next(), it2.next());
297 }
298 check(! it2.hasNext());
299 }
300
301 static void equalSetsLeaf(final Set s1, final Set s2) {
302 equal2(s1, s2);
303 equal( s1.size(), s2.size());
304 equal( s1.isEmpty(), s2.isEmpty());
305 equal( s1.hashCode(), s2.hashCode());
306 equal( s1.toString(), s2.toString());
307 equal( s1.containsAll(s2), s2.containsAll(s1));
308 }
309
310 static void equalNavigableSetsLeaf(final NavigableSet s1,
311 final NavigableSet s2) {
312 equal2(s1, s2);
313 equal( s1.size(), s2.size());
314 equal( s1.isEmpty(), s2.isEmpty());
315 equal( s1.hashCode(), s2.hashCode());
316 equal( s1.toString(), s2.toString());
317 if (! s1.isEmpty()) {
318 equal(s1.first(), s2.first());
319 equal(s1.last(), s2.last());
320 }
321 equalIterators(s1.iterator(), s2.iterator());
322 equalIterators(s1.descendingIterator(), s2.descendingIterator());
323 checkNavigableSet(s1);
324 checkNavigableSet(s2);
325 }
326
327 static void equalNavigableSets(final NavigableSet s1,
328 final NavigableSet s2) {
329 equalNavigableSetsLeaf(s1, s2);
330 equalNavigableSetsLeaf(s1.descendingSet(), s2.descendingSet());
331 equalNavigableSetsLeaf(s1.descendingSet().descendingSet(), s2);
332 Object min = s1.isEmpty() ? Integer.MIN_VALUE : s1.first();
333 Object max = s2.isEmpty() ? Integer.MAX_VALUE : s2.last();
334 if (s1.comparator() != null &&
335 s1.comparator().compare(min, max) > 0) {
336 Object tmp = min; min = max; max = tmp;
337 }
338
339 equalNavigableSetsLeaf(s1.subSet(min, true, max, true),
340 s2.subSet(min, true, max, true));
341 equalNavigableSetsLeaf(s1.tailSet(min, true),
342 s2.tailSet(min, true));
343 equalNavigableSetsLeaf(s1.headSet(max, true),
344 s2.headSet(max, true));
345 equalNavigableSetsLeaf((NavigableSet) s1.subSet(min, max),
346 (NavigableSet) s2.subSet(min, max));
347 equalNavigableSetsLeaf((NavigableSet) s1.tailSet(min),
348 (NavigableSet) s2.tailSet(min));
349 equalNavigableSetsLeaf((NavigableSet) s1.headSet(max),
350 (NavigableSet) s2.headSet(max));
351 }
352
353 // Destined for a Collections.java near you?
354 static <T> T[] concat(T[]... arrays) {
355 int len = 0;
356 for (int i = 0; i < arrays.length; i++)
357 len += arrays[i].length;
358 T[] a = (T[])java.lang.reflect.Array
359 .newInstance(arrays[0].getClass().getComponentType(), len);
360 int k = 0;
361 for (int i = 0; i < arrays.length; i++) {
362 T[] array = arrays[i];
363 System.arraycopy(array, 0, a, k, array.length);
364 k += array.length;
365 }
366 return a;
367 }
368
369 static void checkNavigableMap(final NavigableMap m) {
370 if (m.comparator() == null) {
371 check(m.descendingMap().descendingMap().comparator() == null);
372 check(m.descendingKeySet().descendingSet().comparator() == null);
373 }
374 equal(m.isEmpty(), m.size() == 0);
375 equal2(m, m.descendingMap());
376 if (maybe(4))
377 equal2(m, serialClone(m));
378 equal2(m.keySet(), m.descendingKeySet());
379 Comparator cmp = comparator(m);
380 if (m.isEmpty()) {
381 THROWS(NoSuchElementException.class,
382 () -> m.firstKey(),
383 () -> m.lastKey());
384 equal(null, m.firstEntry());
385 equal(null, m.lastEntry());
386 equal(null, m.pollFirstEntry());
387 equal(null, m.pollLastEntry());
388 equal(null, m.lowerKey(1));
389 equal(null, m.floorKey(1));
390 equal(null, m.ceilingKey(1));
391 equal(null, m.higherKey(1));
392 equal(null, m.lowerEntry(1));
393 equal(null, m.floorEntry(1));
394 equal(null, m.ceilingEntry(1));
395 equal(null, m.higherEntry(1));
396 } else {
397 Object a = m.firstKey();
398 Object z = m.lastKey();
399 equal(m.lowerKey(a), null);
400 equal(m.higherKey(z), null);
401 equal(a, m.firstEntry().getKey());
402 equal(z, m.lastEntry().getKey());
403 equal2(m, m.tailMap(a));
404 equal2(m, m.headMap(z, true));
405 equal2(m, m.subMap(a, true, z, true));
406
407 testEmptyMap(m.subMap(a, true, a, false));
408 testEmptyMap(m.subMap(z, true, z, false));
409 testEmptyMap(m.headMap(a, false));
410 testEmptyMap(m.tailMap(z, false));
411
412 equal2(m.headMap(a, true), singletonMap(a, m.get(a)));
413 equal2(m.tailMap(z, true), singletonMap(z, m.get(z)));
414 }
415
416 Iterator[] kits = new Iterator[] {
417 m.keySet().iterator(),
418 m.descendingMap().descendingKeySet().iterator(),
419 m.descendingKeySet().descendingSet().iterator(),
420 };
421 Iterator[] vits = new Iterator[] {
422 m.values().iterator(),
423 m.descendingMap().descendingMap().values().iterator(),
424 };
425 Iterator[] eits = new Iterator[] {
426 m.entrySet().iterator(),
427 m.descendingMap().descendingMap().entrySet().iterator(),
428 };
429 Iterator[] its = concat(kits, vits, eits);
430 for (final Iterator it : its)
431 if (maybe(4))
432 THROWS(IllegalStateException.class, () -> it.remove());
433 Map.Entry prev = null;
434 for (Map.Entry e : (Set<Map.Entry>) m.entrySet()) {
435 Object k = e.getKey();
436 Object v = e.getValue();
437 check(m.containsKey(k));
438 check(m.containsValue(v));
439 for (Iterator kit : kits) equalNext(kit, k);
440 for (Iterator vit : vits) equalNext(vit, v);
441 for (Iterator eit : eits) equalNext(eit, e);
442 equal(k, m.ceilingKey(k));
443 equal(k, m.ceilingEntry(k).getKey());
444 equal(k, m.floorKey(k));
445 equal(k, m.floorEntry(k).getKey());
446 check(m.higherKey(k) == null || cmp.compare(k, m.higherKey(k)) < 0);
447 check(m.lowerKey(k) == null || cmp.compare(k, m.lowerKey(k)) > 0);
448 equal(m.lowerEntry(k), prev);
449 if (prev == null) {
450 equal(m.lowerKey(k), null);
451 } else {
452 equal(m.lowerKey(k), prev.getKey());
453 check(cmp.compare(prev.getKey(), e.getKey()) < 0);
454 }
455 prev = e;
456 }
457 for (final Iterator it : its) {
458 if (maybe(2))
459 check(! it.hasNext());
460 Fun fun = () -> it.next();
461 THROWS(NoSuchElementException.class, fun, fun, fun);
462 }
463 }
464
465 static void equalNavigableMapsLeaf(final NavigableMap m1,
466 final NavigableMap m2) {
467 equal2(m1, m2);
468 equal( m1.size(), m2.size());
469 equal( m1.isEmpty(), m2.isEmpty());
470 equal( m1.hashCode(), m2.hashCode());
471 equal( m1.toString(), m2.toString());
472 equal2(m1.firstEntry(), m2.firstEntry());
473 equal2(m1.lastEntry(), m2.lastEntry());
474 checkNavigableMap(m1);
475 checkNavigableMap(m2);
476 }
477
478 static void equalNavigableMaps(NavigableMap m1,
479 NavigableMap m2) {
480 equalNavigableMapsLeaf(m1, m2);
481 equalSetsLeaf(m1.keySet(), m2.keySet());
482 equalNavigableSets(m1.navigableKeySet(),
483 m2.navigableKeySet());
484 equalNavigableSets(m1.descendingKeySet(),
485 m2.descendingKeySet());
486 equal2(m1.entrySet(),
487 m2.entrySet());
488 equalNavigableMapsLeaf(m1.descendingMap(),
489 m2.descendingMap());
490 equalNavigableMapsLeaf(m1.descendingMap().descendingMap(),
491 m2);
492 equalNavigableSetsLeaf((NavigableSet) m1.descendingMap().keySet(),
493 (NavigableSet) m2.descendingMap().keySet());
494 equalNavigableSetsLeaf(m1.descendingMap().descendingKeySet(),
495 m2.descendingMap().descendingKeySet());
496 equal2(m1.descendingMap().entrySet(),
497 m2.descendingMap().entrySet());
498
499 //----------------------------------------------------------------
500 // submaps
501 //----------------------------------------------------------------
502 Object min = Integer.MIN_VALUE;
503 Object max = Integer.MAX_VALUE;
504 if (m1.comparator() != null
505 && m1.comparator().compare(min, max) > 0) {
506 Object tmp = min; min = max; max = tmp;
507 }
508 switch (rnd.nextInt(6)) {
509 case 0:
510 equalNavigableMapsLeaf(m1.subMap(min, true, max, true),
511 m2.subMap(min, true, max, true));
512 break;
513 case 1:
514 equalNavigableMapsLeaf(m1.tailMap(min, true),
515 m2.tailMap(min, true));
516 break;
517 case 2:
518 equalNavigableMapsLeaf(m1.headMap(max, true),
519 m2.headMap(max, true));
520 break;
521 case 3:
522 equalNavigableMapsLeaf((NavigableMap) m1.subMap(min, max),
523 (NavigableMap) m2.subMap(min, max));
524 break;
525 case 4:
526 equalNavigableMapsLeaf((NavigableMap) m1.tailMap(min),
527 (NavigableMap) m2.tailMap(min));
528 break;
529 case 5:
530 equalNavigableMapsLeaf((NavigableMap) m1.headMap(max),
531 (NavigableMap) m2.headMap(max));
532 break;
533 }
534 }
535
536 static abstract class MapFrobber { abstract void frob(NavigableMap m); }
537 static abstract class SetFrobber { abstract void frob(NavigableSet m); }
538
539 static MapFrobber randomAdder(NavigableMap m) {
540 final Integer k = unusedKey(m);
541 final MapFrobber[] randomAdders = {
542 new MapFrobber() {void frob(NavigableMap m) {
543 equal(m.put(k, k+1), null);
544 equal(m.get(k), k+1);
545 if (maybe(4)) {
546 equal(m.put(k, k+1), k+1);
547 equal(m.get(k), k+1);}}},
548 new MapFrobber() {void frob(NavigableMap m) {
549 m.descendingMap().put(k, k+1);
550 equal(m.get(k), k+1);}},
551 new MapFrobber() {void frob(NavigableMap m) {
552 m.tailMap(k,true).headMap(k,true).put(k,k+1);}},
553 new MapFrobber() {void frob(NavigableMap m) {
554 m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}
555 };
556 return new MapFrobber() {void frob(NavigableMap m) {
557 randomAdders[rnd.nextInt(randomAdders.length)].frob(m);
558 if (maybe(2)) equal(m.get(k), k+1);
559 if (maybe(4)) {
560 equal(m.put(k, k+1), k+1);
561 equal(m.get(k), k+1);}}};
562 }
563
564 static SetFrobber randomAdder(NavigableSet s) {
565 final Integer e = unusedElt(s);
566 final SetFrobber[] randomAdders = {
567 new SetFrobber() {void frob(NavigableSet s) {
568 check(s.add(e));}},
569 new SetFrobber() {void frob(NavigableSet s) {
570 s.descendingSet().add(e);}},
571 new SetFrobber() {void frob(NavigableSet s) {
572 s.tailSet(e,true).headSet(e,true).add(e);}},
573 new SetFrobber() {void frob(NavigableSet s) {
574 s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}
575 };
576 return new SetFrobber() {void frob(NavigableSet s) {
577 if (maybe(2)) check(! s.contains(e));
578 randomAdders[rnd.nextInt(randomAdders.length)].frob(s);
579 if (maybe(2)) check(! s.add(e));
580 if (maybe(2)) check(s.contains(e));}};
581 }
582
583 static Integer unusedElt(NavigableSet s) {
584 Integer e;
585 do { e = rnd.nextInt(1024); }
586 while (s.contains(e));
587 return e;
588 }
589
590 static Integer unusedKey(NavigableMap m) {
591 Integer k;
592 do { k = rnd.nextInt(1024); }
593 while (m.containsKey(k));
594 return k;
595 }
596
597 static Integer usedKey(NavigableMap m) {
598 Integer x = rnd.nextInt(1024);
599 Integer floor = (Integer) m.floorKey(x);
600 Integer ceiling = (Integer) m.ceilingKey(x);
601 if (floor != null) return floor;
602 check(ceiling != null);
603 return ceiling;
604 }
605
606 static Integer usedElt(NavigableSet s) {
607 Integer x = rnd.nextInt(1024);
608 Integer floor = (Integer) s.floor(x);
609 Integer ceiling = (Integer) s.ceiling(x);
610 if (floor != null) return floor;
611 check(ceiling != null);
612 return ceiling;
613 }
614
615 static void checkUnusedKey(NavigableMap m, Object k) {
616 check(! m.containsKey(k));
617 equal(m.get(k), null);
618 if (maybe(2))
619 equal(m.remove(k), null);
620 }
621
622 static void checkUnusedElt(NavigableSet s, Object e) {
623 if (maybe(2))
624 check(! s.contains(e));
625 if (maybe(2)) {
626 check(s.ceiling(e) != e);
627 check(s.floor(e) != e);
628 }
629 if (maybe(2))
630 check(! s.remove(e));
631 }
632
633 static Fun remover(final Iterator it) {
634 return () -> it.remove();
635 }
636
637 static MapFrobber randomRemover(NavigableMap m) {
638 final Integer k = usedKey(m);
639 final MapFrobber[] randomRemovers = {
640 new MapFrobber() {void frob(NavigableMap m) {
641 Map.Entry e = m.firstEntry();
642 equal(m.pollFirstEntry(), e);
643 checkUnusedKey(m, e.getKey());}},
644 new MapFrobber() {void frob(NavigableMap m) {
645 Map.Entry e = m.lastEntry();
646 equal(m.pollLastEntry(), e);
647 checkUnusedKey(m, e.getKey());}},
648 new MapFrobber() {void frob(NavigableMap m) {
649 check(m.remove(k) != null);
650 checkUnusedKey(m, k);}},
651 new MapFrobber() {void frob(NavigableMap m) {
652 m.subMap(k, true, k, true).clear();
653 checkUnusedKey(m, k);}},
654 new MapFrobber() {void frob(NavigableMap m) {
655 m.descendingMap().subMap(k, true, k, true).clear();
656 checkUnusedKey(m, k);}},
657 new MapFrobber() {void frob(NavigableMap m) {
658 final Iterator it = m.keySet().iterator();
659 while (it.hasNext())
660 if (it.next().equals(k)) {
661 it.remove();
662 if (maybe(2))
663 THROWS(IllegalStateException.class,
664 () -> it.remove());
665 }
666 checkUnusedKey(m, k);}},
667 new MapFrobber() {void frob(NavigableMap m) {
668 final Iterator it = m.navigableKeySet().descendingIterator();
669 while (it.hasNext())
670 if (it.next().equals(k)) {
671 it.remove();
672 if (maybe(2))
673 THROWS(IllegalStateException.class,
674 () -> it.remove());
675 }
676 checkUnusedKey(m, k);}},
677 new MapFrobber() {void frob(NavigableMap m) {
678 final Iterator<Map.Entry> it = m.entrySet().iterator();
679 while (it.hasNext())
680 if (it.next().getKey().equals(k)) {
681 it.remove();
682 if (maybe(2))
683 THROWS(IllegalStateException.class, remover(it));
684 }
685 checkUnusedKey(m, k);}},
686 };
687
688 return randomRemovers[rnd.nextInt(randomRemovers.length)];
689 }
690
691 static SetFrobber randomRemover(NavigableSet s) {
692 final Integer e = usedElt(s);
693
694 final SetFrobber[] randomRemovers = {
695 new SetFrobber() {void frob(NavigableSet s) {
696 Object e = s.first();
697 equal(s.pollFirst(), e);
698 checkUnusedElt(s, e);}},
699 new SetFrobber() {void frob(NavigableSet s) {
700 Object e = s.last();
701 equal(s.pollLast(), e);
702 checkUnusedElt(s, e);}},
703 new SetFrobber() {void frob(NavigableSet s) {
704 check(s.remove(e));
705 checkUnusedElt(s, e);}},
706 new SetFrobber() {void frob(NavigableSet s) {
707 s.subSet(e, true, e, true).clear();
708 checkUnusedElt(s, e);}},
709 new SetFrobber() {void frob(NavigableSet s) {
710 s.descendingSet().subSet(e, true, e, true).clear();
711 checkUnusedElt(s, e);}},
712 new SetFrobber() {void frob(NavigableSet s) {
713 final Iterator it = s.iterator();
714 while (it.hasNext())
715 if (it.next().equals(e)) {
716 it.remove();
717 if (maybe(2))
718 THROWS(IllegalStateException.class,
719 () -> it.remove());
720 }
721 checkUnusedElt(s, e);}},
722 new SetFrobber() {void frob(NavigableSet s) {
723 final Iterator it = s.descendingSet().iterator();
724 while (it.hasNext())
725 if (it.next().equals(e)) {
726 it.remove();
727 if (maybe(2))
728 THROWS(IllegalStateException.class,
729 () -> it.remove());
730 }
731 checkUnusedElt(s, e);}},
732 new SetFrobber() {void frob(NavigableSet s) {
733 final Iterator it = s.descendingIterator();
734 while (it.hasNext())
735 if (it.next().equals(e)) {
736 it.remove();
737 if (maybe(2))
738 THROWS(IllegalStateException.class,
739 () -> it.remove());
740 }
741 checkUnusedElt(s, e);}}
742 };
743
744 return randomRemovers[rnd.nextInt(randomRemovers.length)];
745 }
746
747 static void lockStep(NavigableMap m1,
748 NavigableMap m2) {
749 if (! (thorough || maybe(3))) return;
750 if (maybe(4)) m1 = serialClone(m1);
751 if (maybe(4)) m2 = serialClone(m2);
752
753 List<NavigableMap> maps = Arrays.asList(m1, m2);
754 for (NavigableMap m : maps) testEmptyMap(m);
755 final Set<Integer> ints = new HashSet<Integer>();
756 while (ints.size() < size)
757 ints.add(rnd.nextInt(1024));
758 final Integer[] elts = ints.toArray(new Integer[size]);
759 for (int i = 0; i < size; i++) {
760 MapFrobber adder = randomAdder(m1);
761 for (final NavigableMap m : maps) {
762 adder.frob(m);
763 equal(m.size(), i+1);
764 }
765 equalNavigableMaps(m1, m2);
766 }
767 for (final NavigableMap m : maps) {
768 final Object e = usedKey(m);
769 THROWS(IllegalArgumentException.class,
770 () -> {m.subMap(e,true,e,false)
771 .subMap(e,true,e,true);},
772 () -> {m.subMap(e,false,e,true)
773 .subMap(e,true,e,true);},
774 () -> m.tailMap(e,false).tailMap(e,true),
775 () -> m.headMap(e,false).headMap(e,true));
776 }
777 //System.out.printf("%s%n", m1);
778 for (int i = size; i > 0; i--) {
779 MapFrobber remover = randomRemover(m1);
780 for (final NavigableMap m : maps) {
781 remover.frob(m);
782 equal(m.size(), i-1);
783 }
784 equalNavigableMaps(m1, m2);
785 }
786 for (NavigableMap m : maps) testEmptyMap(m);
787 }
788
789 static void lockStep(NavigableSet s1,
790 NavigableSet s2) {
791 if (! (thorough || maybe(3))) return;
792 if (maybe(4)) s1 = serialClone(s1);
793 if (maybe(4)) s2 = serialClone(s2);
794
795 List<NavigableSet> sets = Arrays.asList(s1, s2);
796 for (NavigableSet s : sets) testEmptySet(s);
797 final Set<Integer> ints = new HashSet<Integer>();
798 while (ints.size() < size)
799 ints.add(rnd.nextInt(1024));
800 final Integer[] elts = ints.toArray(new Integer[size]);
801 for (int i = 0; i < size; i++) {
802 SetFrobber adder = randomAdder(s1);
803 for (final NavigableSet s : sets) {
804 adder.frob(s);
805 equal(s.size(), i+1);
806 }
807 equalNavigableSets(s1, s2);
808 }
809 for (final NavigableSet s : sets) {
810 final Object e = usedElt(s);
811 THROWS(IllegalArgumentException.class,
812 () -> {s.subSet(e,true,e,false)
813 .subSet(e,true,e,true);},
814 () -> {s.subSet(e,false,e,true)
815 .subSet(e,true,e,true);},
816 () -> s.tailSet(e,false).tailSet(e,true),
817 () -> s.headSet(e,false).headSet(e,true));
818 }
819 //System.out.printf("%s%n", s1);
820 for (int i = size; i > 0; i--) {
821 SetFrobber remover = randomRemover(s1);
822 for (final NavigableSet s : sets) {
823 remover.frob(s);
824 equal(s.size(), i-1);
825 }
826 equalNavigableSets(s1, s2);
827 }
828 for (NavigableSet s : sets) testEmptySet(s);
829 }
830
831 //--------------------- Infrastructure ---------------------------
832 static volatile int passed = 0, failed = 0;
833 static void pass() { passed++; }
834 static void fail() { failed++; Thread.dumpStack(); }
835 static void fail(String msg) { System.out.println(msg); fail(); }
836 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
837 static void check(boolean cond) { if (cond) pass(); else fail(); }
838 static void equal(Object x, Object y) {
839 if (x == null ? y == null : x.equals(y)) pass();
840 else {System.out.println(x + " not equal to " + y); fail();}}
841 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
842 public static void main(String[] args) throws Throwable {
843 try { realMain(args); } catch (Throwable t) { unexpected(t); }
844
845 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
846 if (failed > 0) throw new Exception("Some tests failed");
847 }
848 @FunctionalInterface interface Fun {void f() throws Throwable;}
849 static void THROWS(Class<? extends Throwable> k, Fun... fs) {
850 for (Fun f : fs)
851 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
852 catch (Throwable t) {
853 if (k.isAssignableFrom(t.getClass())) pass();
854 else unexpected(t);}}
855 static byte[] serializedForm(Object obj) {
856 try {
857 ByteArrayOutputStream baos = new ByteArrayOutputStream();
858 new ObjectOutputStream(baos).writeObject(obj);
859 return baos.toByteArray();
860 } catch (IOException e) { throw new RuntimeException(e); }}
861 static Object readObject(byte[] bytes)
862 throws IOException, ClassNotFoundException {
863 InputStream is = new ByteArrayInputStream(bytes);
864 return new ObjectInputStream(is).readObject();}
865 @SuppressWarnings("unchecked")
866 static <T> T serialClone(T obj) {
867 try { return (T) readObject(serializedForm(obj)); }
868 catch (Error|RuntimeException e) { throw e; }
869 catch (Throwable e) { throw new RuntimeException(e); }
870 }
871 }