1 /*
2 * Copyright (c) 2006, 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 */
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 new Fun(){void f(){ s.first(); }},
240 new Fun(){void f(){ 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,
269 new Fun(){void f(){ it.remove(); }});
270 Object prev = null;
271 for (Object e : s) {
272 check(s.contains(e));
273 for (Iterator it : its) equalNext(it, e);
274 equal(e, s.ceiling(e));
275 equal(e, s.floor(e));
276 check(s.higher(e) == null || cmp.compare(e, s.higher(e)) < 0);
277 equal(s.lower(e), prev);
278 if (prev == null) {
279 } else {
280 check(cmp.compare(prev, e) < 0);
281 }
282 prev = e;
283 }
284 for (final Iterator it : its) {
285 if (maybe(2))
286 check(! it.hasNext());
287 Fun fun = new Fun(){void f(){ it.next(); }};
288 THROWS(NoSuchElementException.class, fun, fun, fun);
289 }
290 }
291
292 static void equalIterators(final Iterator<?> it1,
293 final Iterator<?> it2) {
294 while (it1.hasNext()) {
295 if (maybe(2))
296 check(it2.hasNext());
297 equal(it1.next(), it2.next());
298 }
299 check(! it2.hasNext());
300 }
301
302 static void equalSetsLeaf(final Set s1, final Set s2) {
303 equal2(s1, s2);
304 equal( s1.size(), s2.size());
305 equal( s1.isEmpty(), s2.isEmpty());
306 equal( s1.hashCode(), s2.hashCode());
307 equal( s1.toString(), s2.toString());
363 T[] array = arrays[i];
364 System.arraycopy(array, 0, a, k, array.length);
365 k += array.length;
366 }
367 return a;
368 }
369
370 static void checkNavigableMap(final NavigableMap m) {
371 if (m.comparator() == null) {
372 check(m.descendingMap().descendingMap().comparator() == null);
373 check(m.descendingKeySet().descendingSet().comparator() == null);
374 }
375 equal(m.isEmpty(), m.size() == 0);
376 equal2(m, m.descendingMap());
377 if (maybe(4))
378 equal2(m, serialClone(m));
379 equal2(m.keySet(), m.descendingKeySet());
380 Comparator cmp = comparator(m);
381 if (m.isEmpty()) {
382 THROWS(NoSuchElementException.class,
383 new Fun(){void f(){ m.firstKey(); }},
384 new Fun(){void f(){ m.lastKey(); }});
385 equal(null, m.firstEntry());
386 equal(null, m.lastEntry());
387 equal(null, m.pollFirstEntry());
388 equal(null, m.pollLastEntry());
389 equal(null, m.lowerKey(1));
390 equal(null, m.floorKey(1));
391 equal(null, m.ceilingKey(1));
392 equal(null, m.higherKey(1));
393 equal(null, m.lowerEntry(1));
394 equal(null, m.floorEntry(1));
395 equal(null, m.ceilingEntry(1));
396 equal(null, m.higherEntry(1));
397 } else {
398 Object a = m.firstKey();
399 Object z = m.lastKey();
400 equal(m.lowerKey(a), null);
401 equal(m.higherKey(z), null);
402 equal(a, m.firstEntry().getKey());
403 equal(z, m.lastEntry().getKey());
404 equal2(m, m.tailMap(a));
413 equal2(m.headMap(a, true), singletonMap(a, m.get(a)));
414 equal2(m.tailMap(z, true), singletonMap(z, m.get(z)));
415 }
416
417 Iterator[] kits = new Iterator[] {
418 m.keySet().iterator(),
419 m.descendingMap().descendingKeySet().iterator(),
420 m.descendingKeySet().descendingSet().iterator(),
421 };
422 Iterator[] vits = new Iterator[] {
423 m.values().iterator(),
424 m.descendingMap().descendingMap().values().iterator(),
425 };
426 Iterator[] eits = new Iterator[] {
427 m.entrySet().iterator(),
428 m.descendingMap().descendingMap().entrySet().iterator(),
429 };
430 Iterator[] its = concat(kits, vits, eits);
431 for (final Iterator it : its)
432 if (maybe(4))
433 THROWS(IllegalStateException.class,
434 new Fun(){void f(){ it.remove(); }});
435 Map.Entry prev = null;
436 for (Map.Entry e : (Set<Map.Entry>) m.entrySet()) {
437 Object k = e.getKey();
438 Object v = e.getValue();
439 check(m.containsKey(k));
440 check(m.containsValue(v));
441 for (Iterator kit : kits) equalNext(kit, k);
442 for (Iterator vit : vits) equalNext(vit, v);
443 for (Iterator eit : eits) equalNext(eit, e);
444 equal(k, m.ceilingKey(k));
445 equal(k, m.ceilingEntry(k).getKey());
446 equal(k, m.floorKey(k));
447 equal(k, m.floorEntry(k).getKey());
448 check(m.higherKey(k) == null || cmp.compare(k, m.higherKey(k)) < 0);
449 check(m.lowerKey(k) == null || cmp.compare(k, m.lowerKey(k)) > 0);
450 equal(m.lowerEntry(k), prev);
451 if (prev == null) {
452 equal(m.lowerKey(k), null);
453 } else {
454 equal(m.lowerKey(k), prev.getKey());
455 check(cmp.compare(prev.getKey(), e.getKey()) < 0);
456 }
457 prev = e;
458 }
459 for (final Iterator it : its) {
460 if (maybe(2))
461 check(! it.hasNext());
462 Fun fun = new Fun(){void f(){ it.next(); }};
463 THROWS(NoSuchElementException.class, fun, fun, fun);
464 }
465 }
466
467 static void equalNavigableMapsLeaf(final NavigableMap m1,
468 final NavigableMap m2) {
469 equal2(m1, m2);
470 equal( m1.size(), m2.size());
471 equal( m1.isEmpty(), m2.isEmpty());
472 equal( m1.hashCode(), m2.hashCode());
473 equal( m1.toString(), m2.toString());
474 equal2(m1.firstEntry(), m2.firstEntry());
475 equal2(m1.lastEntry(), m2.lastEntry());
476 checkNavigableMap(m1);
477 checkNavigableMap(m2);
478 }
479
480 static void equalNavigableMaps(NavigableMap m1,
481 NavigableMap m2) {
482 equalNavigableMapsLeaf(m1, m2);
616
617 static void checkUnusedKey(NavigableMap m, Object k) {
618 check(! m.containsKey(k));
619 equal(m.get(k), null);
620 if (maybe(2))
621 equal(m.remove(k), null);
622 }
623
624 static void checkUnusedElt(NavigableSet s, Object e) {
625 if (maybe(2))
626 check(! s.contains(e));
627 if (maybe(2)) {
628 check(s.ceiling(e) != e);
629 check(s.floor(e) != e);
630 }
631 if (maybe(2))
632 check(! s.remove(e));
633 }
634
635 static Fun remover(final Iterator it) {
636 return new Fun(){void f(){ it.remove(); }};
637 }
638
639 static MapFrobber randomRemover(NavigableMap m) {
640 final Integer k = usedKey(m);
641 final MapFrobber[] randomRemovers = {
642 new MapFrobber() {void frob(NavigableMap m) {
643 Map.Entry e = m.firstEntry();
644 equal(m.pollFirstEntry(), e);
645 checkUnusedKey(m, e.getKey());}},
646 new MapFrobber() {void frob(NavigableMap m) {
647 Map.Entry e = m.lastEntry();
648 equal(m.pollLastEntry(), e);
649 checkUnusedKey(m, e.getKey());}},
650 new MapFrobber() {void frob(NavigableMap m) {
651 check(m.remove(k) != null);
652 checkUnusedKey(m, k);}},
653 new MapFrobber() {void frob(NavigableMap m) {
654 m.subMap(k, true, k, true).clear();
655 checkUnusedKey(m, k);}},
656 new MapFrobber() {void frob(NavigableMap m) {
657 m.descendingMap().subMap(k, true, k, true).clear();
658 checkUnusedKey(m, k);}},
659 new MapFrobber() {void frob(NavigableMap m) {
660 final Iterator it = m.keySet().iterator();
661 while (it.hasNext())
662 if (it.next().equals(k)) {
663 it.remove();
664 if (maybe(2))
665 THROWS(IllegalStateException.class,
666 new Fun(){void f(){ it.remove(); }});
667 }
668 checkUnusedKey(m, k);}},
669 new MapFrobber() {void frob(NavigableMap m) {
670 final Iterator it = m.navigableKeySet().descendingIterator();
671 while (it.hasNext())
672 if (it.next().equals(k)) {
673 it.remove();
674 if (maybe(2))
675 THROWS(IllegalStateException.class,
676 new Fun(){void f(){ it.remove(); }});
677 }
678 checkUnusedKey(m, k);}},
679 new MapFrobber() {void frob(NavigableMap m) {
680 final Iterator<Map.Entry> it = m.entrySet().iterator();
681 while (it.hasNext())
682 if (it.next().getKey().equals(k)) {
683 it.remove();
684 if (maybe(2))
685 THROWS(IllegalStateException.class, remover(it));
686 }
687 checkUnusedKey(m, k);}},
688 };
689
690 return randomRemovers[rnd.nextInt(randomRemovers.length)];
691 }
692
693 static SetFrobber randomRemover(NavigableSet s) {
694 final Integer e = usedElt(s);
695
696 final SetFrobber[] randomRemovers = {
701 new SetFrobber() {void frob(NavigableSet s) {
702 Object e = s.last();
703 equal(s.pollLast(), e);
704 checkUnusedElt(s, e);}},
705 new SetFrobber() {void frob(NavigableSet s) {
706 check(s.remove(e));
707 checkUnusedElt(s, e);}},
708 new SetFrobber() {void frob(NavigableSet s) {
709 s.subSet(e, true, e, true).clear();
710 checkUnusedElt(s, e);}},
711 new SetFrobber() {void frob(NavigableSet s) {
712 s.descendingSet().subSet(e, true, e, true).clear();
713 checkUnusedElt(s, e);}},
714 new SetFrobber() {void frob(NavigableSet s) {
715 final Iterator it = s.iterator();
716 while (it.hasNext())
717 if (it.next().equals(e)) {
718 it.remove();
719 if (maybe(2))
720 THROWS(IllegalStateException.class,
721 new Fun(){void f(){ it.remove(); }});
722 }
723 checkUnusedElt(s, e);}},
724 new SetFrobber() {void frob(NavigableSet s) {
725 final Iterator it = s.descendingSet().iterator();
726 while (it.hasNext())
727 if (it.next().equals(e)) {
728 it.remove();
729 if (maybe(2))
730 THROWS(IllegalStateException.class,
731 new Fun(){void f(){ it.remove(); }});
732 }
733 checkUnusedElt(s, e);}},
734 new SetFrobber() {void frob(NavigableSet s) {
735 final Iterator it = s.descendingIterator();
736 while (it.hasNext())
737 if (it.next().equals(e)) {
738 it.remove();
739 if (maybe(2))
740 THROWS(IllegalStateException.class,
741 new Fun(){void f(){ it.remove(); }});
742 }
743 checkUnusedElt(s, e);}}
744 };
745
746 return randomRemovers[rnd.nextInt(randomRemovers.length)];
747 }
748
749 static void lockStep(NavigableMap m1,
750 NavigableMap m2) {
751 if (! (thorough || maybe(3))) return;
752 if (maybe(4)) m1 = serialClone(m1);
753 if (maybe(4)) m2 = serialClone(m2);
754
755 List<NavigableMap> maps = Arrays.asList(m1, m2);
756 for (NavigableMap m : maps) testEmptyMap(m);
757 final Set<Integer> ints = new HashSet<Integer>();
758 while (ints.size() < size)
759 ints.add(rnd.nextInt(1024));
760 final Integer[] elts = ints.toArray(new Integer[size]);
761 for (int i = 0; i < size; i++) {
762 MapFrobber adder = randomAdder(m1);
763 for (final NavigableMap m : maps) {
764 adder.frob(m);
765 equal(m.size(), i+1);
766 }
767 equalNavigableMaps(m1, m2);
768 }
769 for (final NavigableMap m : maps) {
770 final Object e = usedKey(m);
771 THROWS(IllegalArgumentException.class,
772 new Fun(){void f(){m.subMap(e,true,e,false)
773 .subMap(e,true,e,true);}},
774 new Fun(){void f(){m.subMap(e,false,e,true)
775 .subMap(e,true,e,true);}},
776 new Fun(){void f(){m.tailMap(e,false).tailMap(e,true);}},
777 new Fun(){void f(){m.headMap(e,false).headMap(e,true);}});
778 }
779 //System.out.printf("%s%n", m1);
780 for (int i = size; i > 0; i--) {
781 MapFrobber remover = randomRemover(m1);
782 for (final NavigableMap m : maps) {
783 remover.frob(m);
784 equal(m.size(), i-1);
785 }
786 equalNavigableMaps(m1, m2);
787 }
788 for (NavigableMap m : maps) testEmptyMap(m);
789 }
790
791 static void lockStep(NavigableSet s1,
792 NavigableSet s2) {
793 if (! (thorough || maybe(3))) return;
794 if (maybe(4)) s1 = serialClone(s1);
795 if (maybe(4)) s2 = serialClone(s2);
796
797 List<NavigableSet> sets = Arrays.asList(s1, s2);
798 for (NavigableSet s : sets) testEmptySet(s);
799 final Set<Integer> ints = new HashSet<Integer>();
800 while (ints.size() < size)
801 ints.add(rnd.nextInt(1024));
802 final Integer[] elts = ints.toArray(new Integer[size]);
803 for (int i = 0; i < size; i++) {
804 SetFrobber adder = randomAdder(s1);
805 for (final NavigableSet s : sets) {
806 adder.frob(s);
807 equal(s.size(), i+1);
808 }
809 equalNavigableSets(s1, s2);
810 }
811 for (final NavigableSet s : sets) {
812 final Object e = usedElt(s);
813 THROWS(IllegalArgumentException.class,
814 new Fun(){void f(){s.subSet(e,true,e,false)
815 .subSet(e,true,e,true);}},
816 new Fun(){void f(){s.subSet(e,false,e,true)
817 .subSet(e,true,e,true);}},
818 new Fun(){void f(){s.tailSet(e,false).tailSet(e,true);}},
819 new Fun(){void f(){s.headSet(e,false).headSet(e,true);}});
820 }
821 //System.out.printf("%s%n", s1);
822 for (int i = size; i > 0; i--) {
823 SetFrobber remover = randomRemover(s1);
824 for (final NavigableSet s : sets) {
825 remover.frob(s);
826 equal(s.size(), i-1);
827 }
828 equalNavigableSets(s1, s2);
829 }
830 for (NavigableSet s : sets) testEmptySet(s);
831 }
832
833 //--------------------- Infrastructure ---------------------------
834 static volatile int passed = 0, failed = 0;
835 static void pass() { passed++; }
836 static void fail() { failed++; Thread.dumpStack(); }
837 static void fail(String msg) { System.out.println(msg); fail(); }
838 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
839 static void check(boolean cond) { if (cond) pass(); else fail(); }
840 static void equal(Object x, Object y) {
841 if (x == null ? y == null : x.equals(y)) pass();
842 else {System.out.println(x + " not equal to " + y); fail();}}
843 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
844 public static void main(String[] args) throws Throwable {
845 try { realMain(args); } catch (Throwable t) { unexpected(t); }
846
847 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
848 if (failed > 0) throw new Exception("Some tests failed");
849 }
850 static abstract class Fun {abstract void f() throws Throwable;}
851 static void THROWS(Class<? extends Throwable> k, Fun... fs) {
852 for (Fun f : fs)
853 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
854 catch (Throwable t) {
855 if (k.isAssignableFrom(t.getClass())) pass();
856 else unexpected(t);}}
857 static byte[] serializedForm(Object obj) {
858 try {
859 ByteArrayOutputStream baos = new ByteArrayOutputStream();
860 new ObjectOutputStream(baos).writeObject(obj);
861 return baos.toByteArray();
862 } catch (IOException e) { throw new RuntimeException(e); }}
863 static Object readObject(byte[] bytes)
864 throws IOException, ClassNotFoundException {
865 InputStream is = new ByteArrayInputStream(bytes);
866 return new ObjectInputStream(is).readObject();}
867 @SuppressWarnings("unchecked")
868 static <T> T serialClone(T obj) {
869 try { return (T) readObject(serializedForm(obj)); }
870 catch (Error|RuntimeException e) { throw e; }
|
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 */
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());
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));
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);
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 = {
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; }
|