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