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