1 /*
   2  * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @bug     6420753 6242436 6691185
  27  * @summary Compare NavigableMap implementations for identical behavior
  28  * @run main LockStep
  29  * @run main/othervm -XX:+AggressiveOpts LockStep
  30  * @run main/othervm -XX:+AggressiveOpts -Dthorough=true LockStep
  31  * @author  Martin Buchholz
  32  */
  33 
  34 import java.io.*;
  35 import java.util.*;
  36 import java.util.concurrent.*;
  37 import static java.util.Collections.*;
  38 
  39 @SuppressWarnings("unchecked")
  40 public class LockStep {
  41     static final int DEFAULT_SIZE = 5;
  42     static int size;            // Running time is O(size**2)
  43 
  44     static int intArg(String[] args, int i, int defaultValue) {
  45         return args.length > i ? Integer.parseInt(args[i]) : defaultValue;
  46     }
  47 
  48     // Pass -Dthorough=true for more exhaustive testing
  49     static final boolean thorough = Boolean.getBoolean("thorough");
  50 
  51     static boolean maybe(int n) { return rnd.nextInt(n) == 0; }
  52 
  53     static void realMain(String[] args) {
  54         size = intArg(args, 0, DEFAULT_SIZE);
  55 
  56         lockSteps(new TreeMap(),
  57                   new ConcurrentSkipListMap());
  58         lockSteps(new TreeMap(),
  59                   Collections.checkedNavigableMap(new TreeMap(), Integer.class, Integer.class));
  60         lockSteps(new TreeMap(),
  61                   Collections.synchronizedNavigableMap(new TreeMap()));
  62         lockSteps(new TreeMap(reverseOrder()),
  63                   new ConcurrentSkipListMap(reverseOrder()));
  64 
  65         lockSteps(new TreeSet(),
  66                   new ConcurrentSkipListSet());
  67         lockSteps(new TreeSet(),
  68                   Collections.checkedNavigableSet(new TreeSet(), Integer.class));
  69         lockSteps(new TreeSet(),
  70                   Collections.synchronizedNavigableSet(new TreeSet()));
  71         lockSteps(new TreeSet(reverseOrder()),
  72                   new ConcurrentSkipListSet(reverseOrder()));
  73     }
  74 
  75     static void lockSteps(NavigableMap m1, NavigableMap m2) {
  76         if (maybe(4)) m1 = serialClone(m1);
  77         if (maybe(4)) m2 = serialClone(m2);
  78         lockStep(m1,
  79                  m2);
  80         lockStep(m1.descendingMap(),
  81                  m2.descendingMap());
  82         lockStep(fullSubMap(m1),
  83                  fullSubMap(m2));
  84         lockStep(fullSubMap(m1.descendingMap()),
  85                  fullSubMap(m2.descendingMap()));
  86         lockStep(fullHeadMap(m1),
  87                  fullHeadMap(m2));
  88         lockStep(fullHeadMap(m1.descendingMap()),
  89                  fullHeadMap(m2.descendingMap()));
  90         lockStep(fullTailMap(m1),
  91                  fullTailMap(m2));
  92         lockStep(fullTailMap(m1.descendingMap()),
  93                  fullTailMap(m2.descendingMap()));
  94     }
  95 
  96     static void lockSteps(NavigableSet s1, NavigableSet s2) {
  97         if (maybe(4)) s1 = serialClone(s1);
  98         if (maybe(4)) s2 = serialClone(s2);
  99         lockStep(s1,
 100                  s2);
 101         lockStep(s1.descendingSet(),
 102                  s2.descendingSet());
 103         lockStep(fullSubSet(s1),
 104                  fullSubSet(s2));
 105         lockStep(fullSubSet(s1.descendingSet()),
 106                  fullSubSet(s2.descendingSet()));
 107         lockStep(fullHeadSet(s1),
 108                  fullHeadSet(s2));
 109         lockStep(fullHeadSet(s1.descendingSet()),
 110                  fullHeadSet(s2.descendingSet()));
 111         lockStep(fullTailSet(s1),
 112                  fullTailSet(s2));
 113         lockStep(fullTailSet(s1.descendingSet()),
 114                  fullTailSet(s2.descendingSet()));
 115     }
 116 
 117     static boolean isAscending(NavigableMap m) {
 118         Comparator cmp = m.comparator();
 119         return (cmp == null || cmp.compare(1, 2) < 0);
 120     }
 121 
 122     static NavigableMap fullSubMap(NavigableMap m) {
 123         return isAscending(m)
 124             ? m.subMap(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
 125             : m.subMap(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
 126     }
 127 
 128     static NavigableMap fullHeadMap(NavigableMap m) {
 129         return isAscending(m)
 130             ? m.headMap(Integer.MAX_VALUE, true)
 131             : m.headMap(Integer.MIN_VALUE, true);
 132     }
 133 
 134     static NavigableMap fullTailMap(NavigableMap m) {
 135         return isAscending(m)
 136             ? m.tailMap(Integer.MIN_VALUE, true)
 137             : m.tailMap(Integer.MAX_VALUE, true);
 138     }
 139 
 140     static boolean isAscending(NavigableSet s) {
 141         Comparator cmp = s.comparator();
 142         return (cmp == null || cmp.compare(1, 2) < 0);
 143     }
 144 
 145     static NavigableSet fullSubSet(NavigableSet s) {
 146         return isAscending(s)
 147             ? s.subSet(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
 148             : s.subSet(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
 149     }
 150 
 151     static NavigableSet fullHeadSet(NavigableSet s) {
 152         return isAscending(s)
 153             ? s.headSet(Integer.MAX_VALUE, true)
 154             : s.headSet(Integer.MIN_VALUE, true);
 155     }
 156 
 157     static NavigableSet fullTailSet(NavigableSet s) {
 158         return isAscending(s)
 159             ? s.tailSet(Integer.MIN_VALUE, true)
 160             : s.tailSet(Integer.MAX_VALUE, true);
 161     }
 162 
 163     static void testEmptyCollection(Collection<?> c) {
 164         check(c.isEmpty());
 165         equal(c.size(), 0);
 166         equal(c.toString(),"[]");
 167         equal(c.toArray().length, 0);
 168         equal(c.toArray(new Object[0]).length, 0);
 169 
 170         Object[] a = new Object[1]; a[0] = Boolean.TRUE;
 171         equal(c.toArray(a), a);
 172         equal(a[0], null);
 173         check(! c.iterator().hasNext());
 174     }
 175 
 176     static void testEmptySet(Set<?> c) {
 177         testEmptyCollection(c);
 178         equal(c.hashCode(), 0);
 179         equal2(c, Collections.<Integer>emptySet());
 180     }
 181 
 182     static void testEmptyMap(final Map<?,?> m) {
 183         check(m.isEmpty());
 184         equal(m.size(), 0);
 185         equal(m.toString(),"{}");
 186         equal(m.hashCode(), 0);
 187         testEmptySet(m.keySet());
 188         testEmptySet(m.entrySet());
 189         testEmptyCollection(m.values());
 190     }
 191 
 192     static final Random rnd;
 193 
 194     static {
 195         // sufficiently random for this test
 196         long seed = System.nanoTime();
 197         System.out.println(LockStep.class.getCanonicalName() + ": Trial random seed: " + seed );
 198 
 199         rnd = new Random(seed);
 200     }
 201 
 202     static void equalNext(final Iterator<?> it, Object expected) {
 203         if (maybe(2))
 204             check(it.hasNext());
 205         equal(it.next(), expected);
 206     }
 207 
 208     static Comparator comparator(NavigableSet s) {
 209         Comparator cmp = s.comparator();
 210         return cmp != null ? cmp : new Comparator() {
 211             public int compare(Object o1, Object o2) {
 212                 return ((Comparable) o1).compareTo(o2); }};
 213     }
 214 
 215     static Comparator comparator(NavigableMap m) {
 216         Comparator cmp = m.comparator();
 217         return cmp != null ? cmp : new Comparator() {
 218             public int compare(Object o1, Object o2) {
 219                 return ((Comparable) o1).compareTo(o2); }};
 220     }
 221 
 222     static void checkNavigableSet(final NavigableSet s) {
 223         if (s.comparator() == null)
 224             check(s.descendingSet().descendingSet().comparator() == null);
 225         equal(s.isEmpty(), s.size() == 0);
 226         equal2(s, s.descendingSet());
 227         if (maybe(4) && s instanceof Serializable) {
 228             try {
 229                 equal2(s, serialClone(s));
 230             } catch(RuntimeException uhoh) {
 231                 if(!(uhoh.getCause() instanceof NotSerializableException)) {
 232                     throw uhoh;
 233                 }
 234             }
 235         }
 236         Comparator cmp = comparator(s);
 237         if (s.isEmpty()) {
 238             THROWS(NoSuchElementException.class,
 239                    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());
 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                    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));
 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,
 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);
 483         equalSetsLeaf(m1.keySet(), m2.keySet());
 484         equalNavigableSets(m1.navigableKeySet(),
 485                            m2.navigableKeySet());
 486         equalNavigableSets(m1.descendingKeySet(),
 487                            m2.descendingKeySet());
 488         equal2(m1.entrySet(),
 489                m2.entrySet());
 490         equalNavigableMapsLeaf(m1.descendingMap(),
 491                                m2.descendingMap());
 492         equalNavigableMapsLeaf(m1.descendingMap().descendingMap(),
 493                                m2);
 494         equalNavigableSetsLeaf((NavigableSet) m1.descendingMap().keySet(),
 495                                (NavigableSet) m2.descendingMap().keySet());
 496         equalNavigableSetsLeaf(m1.descendingMap().descendingKeySet(),
 497                                m2.descendingMap().descendingKeySet());
 498         equal2(m1.descendingMap().entrySet(),
 499                m2.descendingMap().entrySet());
 500 
 501         //----------------------------------------------------------------
 502         // submaps
 503         //----------------------------------------------------------------
 504         Object min = Integer.MIN_VALUE;
 505         Object max = Integer.MAX_VALUE;
 506         if (m1.comparator() != null
 507             && m1.comparator().compare(min, max) > 0) {
 508             Object tmp = min; min = max; max = tmp;
 509         }
 510         switch (rnd.nextInt(6)) {
 511         case 0:
 512             equalNavigableMapsLeaf(m1.subMap(min, true, max, true),
 513                                    m2.subMap(min, true, max, true));
 514             break;
 515         case 1:
 516             equalNavigableMapsLeaf(m1.tailMap(min, true),
 517                                    m2.tailMap(min, true));
 518             break;
 519         case 2:
 520             equalNavigableMapsLeaf(m1.headMap(max, true),
 521                                    m2.headMap(max, true));
 522             break;
 523         case 3:
 524             equalNavigableMapsLeaf((NavigableMap) m1.subMap(min, max),
 525                                    (NavigableMap) m2.subMap(min, max));
 526             break;
 527         case 4:
 528             equalNavigableMapsLeaf((NavigableMap) m1.tailMap(min),
 529                                    (NavigableMap) m2.tailMap(min));
 530             break;
 531         case 5:
 532             equalNavigableMapsLeaf((NavigableMap) m1.headMap(max),
 533                                    (NavigableMap) m2.headMap(max));
 534             break;
 535         }
 536     }
 537 
 538     static abstract class MapFrobber { abstract void frob(NavigableMap m); }
 539     static abstract class SetFrobber { abstract void frob(NavigableSet m); }
 540 
 541     static MapFrobber randomAdder(NavigableMap m) {
 542         final Integer k = unusedKey(m);
 543         final MapFrobber[] randomAdders = {
 544             new MapFrobber() {void frob(NavigableMap m) {
 545                 equal(m.put(k, k+1), null);
 546                 equal(m.get(k), k+1);
 547                 if (maybe(4)) {
 548                     equal(m.put(k, k+1), k+1);
 549                     equal(m.get(k), k+1);}}},
 550             new MapFrobber() {void frob(NavigableMap m) {
 551                 m.descendingMap().put(k, k+1);
 552                 equal(m.get(k), k+1);}},
 553             new MapFrobber() {void frob(NavigableMap m) {
 554                 m.tailMap(k,true).headMap(k,true).put(k,k+1);}},
 555             new MapFrobber() {void frob(NavigableMap m) {
 556                 m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}
 557         };
 558         return new MapFrobber() {void frob(NavigableMap m) {
 559             randomAdders[rnd.nextInt(randomAdders.length)].frob(m);
 560             if (maybe(2)) equal(m.get(k), k+1);
 561             if (maybe(4)) {
 562                 equal(m.put(k, k+1), k+1);
 563                 equal(m.get(k), k+1);}}};
 564     }
 565 
 566     static SetFrobber randomAdder(NavigableSet s) {
 567         final Integer e = unusedElt(s);
 568         final SetFrobber[] randomAdders = {
 569             new SetFrobber() {void frob(NavigableSet s) {
 570                 check(s.add(e));}},
 571             new SetFrobber() {void frob(NavigableSet s) {
 572                 s.descendingSet().add(e);}},
 573             new SetFrobber() {void frob(NavigableSet s) {
 574                 s.tailSet(e,true).headSet(e,true).add(e);}},
 575             new SetFrobber() {void frob(NavigableSet s) {
 576                 s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}
 577         };
 578         return new SetFrobber() {void frob(NavigableSet s) {
 579             if (maybe(2)) check(! s.contains(e));
 580             randomAdders[rnd.nextInt(randomAdders.length)].frob(s);
 581             if (maybe(2)) check(! s.add(e));
 582             if (maybe(2)) check(s.contains(e));}};
 583     }
 584 
 585     static Integer unusedElt(NavigableSet s) {
 586         Integer e;
 587         do { e = rnd.nextInt(1024); }
 588         while (s.contains(e));
 589         return e;
 590     }
 591 
 592     static Integer unusedKey(NavigableMap m) {
 593         Integer k;
 594         do { k = rnd.nextInt(1024); }
 595         while (m.containsKey(k));
 596         return k;
 597     }
 598 
 599     static Integer usedKey(NavigableMap m) {
 600         Integer x = rnd.nextInt(1024);
 601         Integer floor   = (Integer) m.floorKey(x);
 602         Integer ceiling = (Integer) m.ceilingKey(x);
 603         if (floor != null) return floor;
 604         check(ceiling != null);
 605         return ceiling;
 606     }
 607 
 608     static Integer usedElt(NavigableSet s) {
 609         Integer x = rnd.nextInt(1024);
 610         Integer floor   = (Integer) s.floor(x);
 611         Integer ceiling = (Integer) s.ceiling(x);
 612         if (floor != null) return floor;
 613         check(ceiling != null);
 614         return ceiling;
 615     }
 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 = {
 697             new SetFrobber() {void frob(NavigableSet s) {
 698                 Object e = s.first();
 699                 equal(s.pollFirst(), e);
 700                 checkUnusedElt(s, e);}},
 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 (Throwable e) {
 871             if (e instanceof Error) {
 872                 throw (Error) e;
 873             } else if (e instanceof RuntimeException) {
 874                 throw (RuntimeException) e;
 875             } else {
 876                 throw new RuntimeException(e);
 877             }
 878         }}
 879 }