1 /*

     2  * Copyright 2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  */

    23 

    24 /*

    25  * @test

    26  * @bug     6420753 6242436

    27  * @summary Compare NavigableMap implementations for identical behavior

    28  * @author  Martin Buchholz

    29  */

    30 

    31 import java.io.*;

    32 import java.util.*;

    33 import java.util.concurrent.*;

    34 import static java.util.Collections.*;

    35 

    36 @SuppressWarnings("unchecked")

    37 public class LockStep {

    38     static final int DEFAULT_SIZE = 5;

    39     static int size;            // Running time is O(size**2)

    40 

    41     static int intArg(String[] args, int i, int defaultValue) {

    42         return args.length > i ? Integer.parseInt(args[i]) : defaultValue;

    43     }

    44 

    45     // Pass -Dthorough=true for more exhaustive testing

    46     static final boolean thorough = Boolean.getBoolean("thorough");

    47 

    48     static boolean maybe(int n) { return rnd.nextInt(n) == 0; }

    49 

    50     static void realMain(String[] args) {

    51         size = intArg(args, 0, DEFAULT_SIZE);

    52 

    53         lockSteps(new TreeMap(),

    54                   new ConcurrentSkipListMap());

    55         lockSteps(new TreeMap(reverseOrder()),

    56                   new ConcurrentSkipListMap(reverseOrder()));

    57 

    58         lockSteps(new TreeSet(),

    59                   new ConcurrentSkipListSet());

    60         lockSteps(new TreeSet(reverseOrder()),

    61                   new ConcurrentSkipListSet(reverseOrder()));

    62     }

    63 

    64     static void lockSteps(NavigableMap m1, NavigableMap m2) {

    65         if (maybe(4)) m1 = serialClone(m1);

    66         if (maybe(4)) m2 = serialClone(m2);

    67         lockStep(m1,

    68                  m2);

    69         lockStep(m1.descendingMap(),

    70                  m2.descendingMap());

    71         lockStep(fullSubMap(m1),

    72                  fullSubMap(m2));

    73         lockStep(fullSubMap(m1.descendingMap()),

    74                  fullSubMap(m2.descendingMap()));

    75         lockStep(fullHeadMap(m1),

    76                  fullHeadMap(m2));

    77         lockStep(fullHeadMap(m1.descendingMap()),

    78                  fullHeadMap(m2.descendingMap()));

    79         lockStep(fullTailMap(m1),

    80                  fullTailMap(m2));

    81         lockStep(fullTailMap(m1.descendingMap()),

    82                  fullTailMap(m2.descendingMap()));

    83     }

    84 

    85     static void lockSteps(NavigableSet s1, NavigableSet s2) {

    86         if (maybe(4)) s1 = serialClone(s1);

    87         if (maybe(4)) s2 = serialClone(s2);

    88         lockStep(s1,

    89                  s2);

    90         lockStep(s1.descendingSet(),

    91                  s2.descendingSet());

    92         lockStep(fullSubSet(s1),

    93                  fullSubSet(s2));

    94         lockStep(fullSubSet(s1.descendingSet()),

    95                  fullSubSet(s2.descendingSet()));

    96         lockStep(fullHeadSet(s1),

    97                  fullHeadSet(s2));

    98         lockStep(fullHeadSet(s1.descendingSet()),

    99                  fullHeadSet(s2.descendingSet()));

   100         lockStep(fullTailSet(s1),

   101                  fullTailSet(s2));

   102         lockStep(fullTailSet(s1.descendingSet()),

   103                  fullTailSet(s2.descendingSet()));

   104     }

   105 

   106     static boolean isAscending(NavigableMap m) {

   107         Comparator cmp = m.comparator();

   108         return (cmp == null || cmp.compare(1, 2) < 0);

   109     }

   110 

   111     static NavigableMap fullSubMap(NavigableMap m) {

   112         return isAscending(m)

   113             ? m.subMap(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)

   114             : m.subMap(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);

   115     }

   116 

   117     static NavigableMap fullHeadMap(NavigableMap m) {

   118         return isAscending(m)

   119             ? m.headMap(Integer.MAX_VALUE, true)

   120             : m.headMap(Integer.MIN_VALUE, true);

   121     }

   122 

   123     static NavigableMap fullTailMap(NavigableMap m) {

   124         return isAscending(m)

   125             ? m.tailMap(Integer.MIN_VALUE, true)

   126             : m.tailMap(Integer.MAX_VALUE, true);

   127     }

   128 

   129     static boolean isAscending(NavigableSet s) {

   130         Comparator cmp = s.comparator();

   131         return (cmp == null || cmp.compare(1, 2) < 0);

   132     }

   133 

   134     static NavigableSet fullSubSet(NavigableSet s) {

   135         return isAscending(s)

   136             ? s.subSet(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)

   137             : s.subSet(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);

   138     }

   139 

   140     static NavigableSet fullHeadSet(NavigableSet s) {

   141         return isAscending(s)

   142             ? s.headSet(Integer.MAX_VALUE, true)

   143             : s.headSet(Integer.MIN_VALUE, true);

   144     }

   145 

   146     static NavigableSet fullTailSet(NavigableSet s) {

   147         return isAscending(s)

   148             ? s.tailSet(Integer.MIN_VALUE, true)

   149             : s.tailSet(Integer.MAX_VALUE, true);

   150     }

   151 

   152     static void testEmptyCollection(Collection<?> c) {

   153         check(c.isEmpty());

   154         equal(c.size(), 0);

   155         equal(c.toString(),"[]");

   156         equal(c.toArray().length, 0);

   157         equal(c.toArray(new Object[0]).length, 0);

   158 

   159         Object[] a = new Object[1]; a[0] = Boolean.TRUE;

   160         equal(c.toArray(a), a);

   161         equal(a[0], null);

   162     }

   163 

   164     static void testEmptySet(Set<?> c) {

   165         testEmptyCollection(c);

   166         equal(c.hashCode(), 0);

   167         equal2(c, Collections.<Integer>emptySet());

   168     }

   169 

   170     static void testEmptyMap(final Map<?,?> m) {

   171         check(m.isEmpty());

   172         equal(m.size(), 0);

   173         equal(m.toString(),"{}");

   174         equal(m.hashCode(), 0);

   175         testEmptySet(m.keySet());

   176         testEmptySet(m.entrySet());

   177         testEmptyCollection(m.values());

   178     }

   179 

   180     static final Random rnd = new Random();

   181 

   182     static void equalNext(final Iterator<?> it, Object expected) {

   183         if (maybe(2))

   184             check(it.hasNext());

   185         equal(it.next(), expected);

   186     }

   187 

   188     static Comparator comparator(NavigableSet s) {

   189         Comparator cmp = s.comparator();

   190         return cmp != null ? cmp : new Comparator() {

   191             public int compare(Object o1, Object o2) {

   192                 return ((Comparable) o1).compareTo(o2); }};

   193     }

   194 

   195     static Comparator comparator(NavigableMap m) {

   196         Comparator cmp = m.comparator();

   197         return cmp != null ? cmp : new Comparator() {

   198             public int compare(Object o1, Object o2) {

   199                 return ((Comparable) o1).compareTo(o2); }};

   200     }

   201 

   202     static void checkNavigableSet(final NavigableSet s) {

   203         if (s.comparator() == null)

   204             check(s.descendingSet().descendingSet().comparator() == null);

   205         equal(s.isEmpty(), s.size() == 0);

   206         equal2(s, s.descendingSet());

   207         if (maybe(4) && s instanceof Serializable)

   208             equal2(s, serialClone(s));

   209         Comparator cmp = comparator(s);

   210         if (s.isEmpty()) {

   211             THROWS(NoSuchElementException.class,

   212                    new Fun(){void f(){ s.first(); }},

   213                    new Fun(){void f(){ s.last();  }});

   214             equal(null, s.lower(1));

   215             equal(null, s.floor(1));

   216             equal(null, s.ceiling(1));

   217             equal(null, s.higher(1));

   218         } else {

   219             Object a = s.first();

   220             Object z = s.last();

   221             equal(s.lower(a), null);

   222             equal(s.higher(z), null);

   223             equal2(s, s.tailSet(a));

   224             equal2(s, s.headSet(z, true));

   225             equal2(s, s.subSet(a, true, z, true));

   226 

   227             testEmptySet(s.subSet(a, true, a, false));

   228             testEmptySet(s.subSet(z, true, z, false));

   229             testEmptySet(s.headSet(a, false));

   230             testEmptySet(s.tailSet(z, false));

   231 

   232             equal2(s.headSet(a, true), singleton(a));

   233             equal2(s.tailSet(z, true), singleton(z));

   234         }

   235         Iterator[] its = new Iterator[] {

   236             s.iterator(),

   237             s.descendingSet().descendingSet().iterator(),

   238         };

   239         for (final Iterator it : its)

   240             if (maybe(4))

   241                 THROWS(IllegalStateException.class,

   242                        new Fun(){void f(){ it.remove(); }});

   243         Object prev = null;

   244         for (Object e : s) {

   245             check(s.contains(e));

   246             for (Iterator it : its) equalNext(it, e);

   247             equal(e, s.ceiling(e));

   248             equal(e, s.floor(e));

   249             check(s.higher(e) == null || cmp.compare(e, s.higher(e)) < 0);

   250             equal(s.lower(e), prev);

   251             if (prev == null) {

   252             } else {

   253                 check(cmp.compare(prev, e) < 0);

   254             }

   255             prev = e;

   256         }

   257         for (final Iterator it : its) {

   258             if (maybe(2))

   259                 check(! it.hasNext());

   260             Fun fun = new Fun(){void f(){ it.next(); }};

   261             THROWS(NoSuchElementException.class, fun, fun, fun);

   262         }

   263     }

   264 

   265     static void equalNavigableSetsLeaf(final NavigableSet s1,

   266                                        final NavigableSet s2) {

   267         equal2(s1,            s2);

   268         equal( s1.size(),     s2.size());

   269         equal( s1.isEmpty(),  s2.isEmpty());

   270         equal( s1.hashCode(), s2.hashCode());

   271         equal( s1.toString(), s2.toString());

   272         if (! s1.isEmpty()) {

   273             equal(s1.first(), s2.first());

   274             equal(s1.last(),  s2.last());

   275         }

   276         checkNavigableSet(s1);

   277         checkNavigableSet(s2);

   278     }

   279 

   280     static void equalNavigableSets(final NavigableSet s1,

   281                                    final NavigableSet s2) {

   282         equalNavigableSetsLeaf(s1, s2);

   283         equalNavigableSetsLeaf(s1.descendingSet(), s2.descendingSet());

   284         equalNavigableSetsLeaf(s1.descendingSet().descendingSet(), s2);

   285         Object min = s1.isEmpty() ? Integer.MIN_VALUE : s1.first();

   286         Object max = s2.isEmpty() ? Integer.MAX_VALUE : s2.last();

   287         if (s1.comparator() != null &&

   288             s1.comparator().compare(min, max) > 0) {

   289             Object tmp = min; min = max; max = tmp;

   290         }

   291 

   292         equalNavigableSetsLeaf(s1.subSet(min, true, max, true),

   293                                s2.subSet(min, true, max, true));

   294         equalNavigableSetsLeaf(s1.tailSet(min, true),

   295                                s2.tailSet(min, true));

   296         equalNavigableSetsLeaf(s1.headSet(max, true),

   297                                s2.headSet(max, true));

   298         equalNavigableSetsLeaf((NavigableSet) s1.subSet(min, max),

   299                                (NavigableSet) s2.subSet(min, max));

   300         equalNavigableSetsLeaf((NavigableSet) s1.tailSet(min),

   301                                (NavigableSet) s2.tailSet(min));

   302         equalNavigableSetsLeaf((NavigableSet) s1.headSet(max),

   303                                (NavigableSet) s2.headSet(max));

   304     }

   305 

   306     // Destined for a Collections.java near you?

   307     static <T> T[] concat(T[]... arrays) {

   308         int len = 0;

   309         for (int i = 0; i < arrays.length; i++)

   310             len += arrays[i].length;

   311         T[] a = (T[])java.lang.reflect.Array

   312             .newInstance(arrays[0].getClass().getComponentType(), len);

   313         int k = 0;

   314         for (int i = 0; i < arrays.length; i++) {

   315             T[] array = arrays[i];

   316             System.arraycopy(array, 0, a, k, array.length);

   317             k += array.length;

   318         }

   319         return a;

   320     }

   321 

   322     static void checkNavigableMap(final NavigableMap m) {

   323         if (m.comparator() == null) {

   324             check(m.descendingMap().descendingMap().comparator() == null);

   325             check(m.descendingKeySet().descendingSet().comparator() == null);

   326         }

   327         equal(m.isEmpty(), m.size() == 0);

   328         equal2(m, m.descendingMap());

   329         if (maybe(4))

   330             equal2(m, serialClone(m));

   331         equal2(m.keySet(), m.descendingKeySet());

   332         Comparator cmp = comparator(m);

   333         if (m.isEmpty()) {

   334             THROWS(NoSuchElementException.class,

   335                    new Fun(){void f(){ m.firstKey(); }},

   336                    new Fun(){void f(){ m.lastKey();  }});

   337             equal(null, m.firstEntry());

   338             equal(null, m.lastEntry());

   339             equal(null, m.pollFirstEntry());

   340             equal(null, m.pollLastEntry());

   341             equal(null, m.lowerKey(1));

   342             equal(null, m.floorKey(1));

   343             equal(null, m.ceilingKey(1));

   344             equal(null, m.higherKey(1));

   345             equal(null, m.lowerEntry(1));

   346             equal(null, m.floorEntry(1));

   347             equal(null, m.ceilingEntry(1));

   348             equal(null, m.higherEntry(1));

   349         } else {

   350             Object a = m.firstKey();

   351             Object z = m.lastKey();

   352             equal(m.lowerKey(a), null);

   353             equal(m.higherKey(z), null);

   354             equal(a, m.firstEntry().getKey());

   355             equal(z, m.lastEntry().getKey());

   356             equal2(m, m.tailMap(a));

   357             equal2(m, m.headMap(z, true));

   358             equal2(m, m.subMap(a, true, z, true));

   359 

   360             testEmptyMap(m.subMap(a, true, a, false));

   361             testEmptyMap(m.subMap(z, true, z, false));

   362             testEmptyMap(m.headMap(a, false));

   363             testEmptyMap(m.tailMap(z, false));

   364 

   365             equal2(m.headMap(a, true), singletonMap(a, m.get(a)));

   366             equal2(m.tailMap(z, true), singletonMap(z, m.get(z)));

   367         }

   368 

   369         Iterator[] kits = new Iterator[] {

   370             m.keySet().iterator(),

   371             m.descendingMap().descendingKeySet().iterator(),

   372             m.descendingKeySet().descendingSet().iterator(),

   373         };

   374         Iterator[] vits = new Iterator[] {

   375             m.values().iterator(),

   376             m.descendingMap().descendingMap().values().iterator(),

   377         };

   378         Iterator[] eits = new Iterator[] {

   379             m.entrySet().iterator(),

   380             m.descendingMap().descendingMap().entrySet().iterator(),

   381         };

   382         Iterator[] its = concat(kits, vits, eits);

   383         for (final Iterator it : its)

   384             if (maybe(4))

   385                 THROWS(IllegalStateException.class,

   386                        new Fun(){void f(){ it.remove(); }});

   387         Map.Entry prev = null;

   388         for (Map.Entry e : (Set<Map.Entry>) m.entrySet()) {

   389             Object k = e.getKey();

   390             Object v = e.getValue();

   391             check(m.containsKey(k));

   392             check(m.containsValue(v));

   393             for (Iterator kit : kits) equalNext(kit, k);

   394             for (Iterator vit : vits) equalNext(vit, v);

   395             for (Iterator eit : eits) equalNext(eit, e);

   396             equal(k, m.ceilingKey(k));

   397             equal(k, m.ceilingEntry(k).getKey());

   398             equal(k, m.floorKey(k));

   399             equal(k, m.floorEntry(k).getKey());

   400             check(m.higherKey(k) == null || cmp.compare(k, m.higherKey(k)) < 0);

   401             check(m.lowerKey(k)  == null || cmp.compare(k, m.lowerKey(k))  > 0);

   402             equal(m.lowerEntry(k), prev);

   403             if (prev == null) {

   404                 equal(m.lowerKey(k), null);

   405             } else {

   406                 equal(m.lowerKey(k), prev.getKey());

   407                 check(cmp.compare(prev.getKey(), e.getKey()) < 0);

   408             }

   409             prev = e;

   410         }

   411         for (final Iterator it : its) {

   412             if (maybe(2))

   413                 check(! it.hasNext());

   414             Fun fun = new Fun(){void f(){ it.next(); }};

   415             THROWS(NoSuchElementException.class, fun, fun, fun);

   416         }

   417     }

   418 

   419     static void equalNavigableMapsLeaf(final NavigableMap m1,

   420                                        final NavigableMap m2) {

   421         equal2(m1,              m2);

   422         equal( m1.size(),       m2.size());

   423         equal( m1.isEmpty(),    m2.isEmpty());

   424         equal( m1.hashCode(),   m2.hashCode());

   425         equal( m1.toString(),   m2.toString());

   426         equal2(m1.firstEntry(), m2.firstEntry());

   427         equal2(m1.lastEntry(),  m2.lastEntry());

   428         checkNavigableMap(m1);

   429         checkNavigableMap(m2);

   430     }

   431 

   432     static void equalNavigableMaps(NavigableMap m1,

   433                                    NavigableMap m2) {

   434         equalNavigableMapsLeaf(m1, m2);

   435         equalNavigableSetsLeaf((NavigableSet) m1.keySet(),

   436                                (NavigableSet) m2.keySet());

   437         equalNavigableSets(m1.navigableKeySet(),

   438                            m2.navigableKeySet());

   439         equalNavigableSets(m1.descendingKeySet(),

   440                            m2.descendingKeySet());

   441         equal2(m1.entrySet(),

   442                m2.entrySet());

   443         equalNavigableMapsLeaf(m1.descendingMap(),

   444                                m2.descendingMap());

   445         equalNavigableMapsLeaf(m1.descendingMap().descendingMap(),

   446                                m2);

   447         equalNavigableSetsLeaf((NavigableSet) m1.descendingMap().keySet(),

   448                                (NavigableSet) m2.descendingMap().keySet());

   449         equalNavigableSetsLeaf(m1.descendingMap().descendingKeySet(),

   450                                m2.descendingMap().descendingKeySet());

   451         equal2(m1.descendingMap().entrySet(),

   452                m2.descendingMap().entrySet());

   453 

   454         //----------------------------------------------------------------

   455         // submaps

   456         //----------------------------------------------------------------

   457         Object min = Integer.MIN_VALUE;

   458         Object max = Integer.MAX_VALUE;

   459         if (m1.comparator() != null

   460             && m1.comparator().compare(min, max) > 0) {

   461             Object tmp = min; min = max; max = tmp;

   462         }

   463         switch (rnd.nextInt(6)) {

   464         case 0:

   465             equalNavigableMapsLeaf(m1.subMap(min, true, max, true),

   466                                    m2.subMap(min, true, max, true));

   467             break;

   468         case 1:

   469             equalNavigableMapsLeaf(m1.tailMap(min, true),

   470                                    m2.tailMap(min, true));

   471             break;

   472         case 2:

   473             equalNavigableMapsLeaf(m1.headMap(max, true),

   474                                    m2.headMap(max, true));

   475             break;

   476         case 3:

   477             equalNavigableMapsLeaf((NavigableMap) m1.subMap(min, max),

   478                                    (NavigableMap) m2.subMap(min, max));

   479             break;

   480         case 4:

   481             equalNavigableMapsLeaf((NavigableMap) m1.tailMap(min),

   482                                    (NavigableMap) m2.tailMap(min));

   483             break;

   484         case 5:

   485             equalNavigableMapsLeaf((NavigableMap) m1.headMap(max),

   486                                    (NavigableMap) m2.headMap(max));

   487             break;

   488         }

   489     }

   490 

   491     static abstract class MapFrobber { abstract void frob(NavigableMap m); }

   492     static abstract class SetFrobber { abstract void frob(NavigableSet m); }

   493 

   494     static MapFrobber randomAdder(NavigableMap m) {

   495         final Integer k = unusedKey(m);

   496         MapFrobber f;

   497         switch (rnd.nextInt(4)) {

   498         case 0: f = new MapFrobber() {void frob(NavigableMap m) {

   499             equal(m.put(k, k+1), null);

   500             equal(m.get(k), k+1);

   501             if (maybe(4)) {

   502                 equal(m.put(k, k+1), k+1);

   503                 equal(m.get(k), k+1);}}};

   504             break;

   505         case 1: f = new MapFrobber() {void frob(NavigableMap m) {

   506             m.descendingMap().put(k, k+1);

   507             equal(m.get(k), k+1);}};

   508             break;

   509         case 2: f = new MapFrobber() {void frob(NavigableMap m) {

   510             m.tailMap(k,true).headMap(k,true).put(k,k+1);}};

   511             break;

   512         case 3: f = new MapFrobber() {void frob(NavigableMap m) {

   513             m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}};

   514             break;

   515         default: throw new Error();

   516         }

   517         final MapFrobber ff = f;

   518         return new MapFrobber() {void frob(NavigableMap m) {

   519             ff.frob(m);

   520             if (maybe(2)) equal(m.get(k), k+1);

   521             if (maybe(4)) {

   522                 equal(m.put(k, k+1), k+1);

   523                 equal(m.get(k), k+1);}}};

   524     }

   525 

   526     static SetFrobber randomAdder(NavigableSet s) {

   527         final Integer e = unusedElt(s);

   528         SetFrobber f;

   529         switch (rnd.nextInt(4)) {

   530         case 0: f = new SetFrobber() {void frob(NavigableSet s) {

   531             check(s.add(e));}};

   532             break;

   533         case 1: f = new SetFrobber() {void frob(NavigableSet s) {

   534             s.descendingSet().add(e);}};

   535             break;

   536         case 2: f = new SetFrobber() {void frob(NavigableSet s) {

   537             s.tailSet(e,true).headSet(e,true).add(e);}};

   538             break;

   539         case 3: f = new SetFrobber() {void frob(NavigableSet s) {

   540             s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}};

   541             break;

   542         default: throw new Error();

   543         }

   544         final SetFrobber ff = f;

   545         return new SetFrobber() {void frob(NavigableSet s) {

   546             if (maybe(2)) check(! s.contains(e));

   547             ff.frob(s);

   548             if (maybe(2)) check(! s.add(e));

   549             if (maybe(2)) check(s.contains(e));}};

   550     }

   551 

   552     static Integer unusedElt(NavigableSet s) {

   553         Integer e;

   554         do { e = rnd.nextInt(1024); }

   555         while (s.contains(e));

   556         return e;

   557     }

   558 

   559     static Integer unusedKey(NavigableMap m) {

   560         Integer k;

   561         do { k = rnd.nextInt(1024); }

   562         while (m.containsKey(k));

   563         return k;

   564     }

   565 

   566     static Integer usedKey(NavigableMap m) {

   567         Integer x = rnd.nextInt(1024);

   568         Integer floor   = (Integer) m.floorKey(x);

   569         Integer ceiling = (Integer) m.ceilingKey(x);

   570         if (floor != null) return floor;

   571         check(ceiling != null);

   572         return ceiling;

   573     }

   574 

   575     static Integer usedElt(NavigableSet s) {

   576         Integer x = rnd.nextInt(1024);

   577         Integer floor   = (Integer) s.floor(x);

   578         Integer ceiling = (Integer) s.ceiling(x);

   579         if (floor != null) return floor;

   580         check(ceiling != null);

   581         return ceiling;

   582     }

   583 

   584     static void checkUnusedKey(NavigableMap m, Object k) {

   585         check(! m.containsKey(k));

   586         equal(m.get(k), null);

   587         if (maybe(2))

   588             equal(m.remove(k), null);

   589     }

   590 

   591     static void checkUnusedElt(NavigableSet s, Object e) {

   592         if (maybe(2))

   593             check(! s.contains(e));

   594         if (maybe(2)) {

   595             check(s.ceiling(e) != e);

   596             check(s.floor(e)   != e);

   597         }

   598         if (maybe(2))

   599             check(! s.remove(e));

   600     }

   601 

   602     static Fun remover(final Iterator it) {

   603         return new Fun(){void f(){ it.remove(); }};

   604     }

   605 

   606     static MapFrobber randomRemover(NavigableMap m) {

   607         final Integer k = usedKey(m);

   608         switch (rnd.nextInt(7)) {

   609         default: throw new Error();

   610         case 0: return new MapFrobber() {void frob(NavigableMap m) {

   611             Map.Entry e = m.firstEntry();

   612             equal(m.pollFirstEntry(), e);

   613             checkUnusedKey(m, e.getKey());}};

   614         case 1: return new MapFrobber() {void frob(NavigableMap m) {

   615             Map.Entry e = m.lastEntry();

   616             equal(m.pollLastEntry(), e);

   617             checkUnusedKey(m, e.getKey());}};

   618         case 2: return new MapFrobber() {void frob(NavigableMap m) {

   619             check(m.remove(k) != null);

   620             checkUnusedKey(m, k);}};

   621         case 3: return new MapFrobber() {void frob(NavigableMap m) {

   622             m.subMap(k, true, k, true).clear();

   623             checkUnusedKey(m, k);}};

   624         case 4: return new MapFrobber() {void frob(NavigableMap m) {

   625             m.descendingMap().subMap(k, true, k, true).clear();

   626             checkUnusedKey(m, k);}};

   627         case 5: return new MapFrobber() {void frob(NavigableMap m) {

   628             final Iterator it = m.keySet().iterator();

   629             while (it.hasNext())

   630                 if (it.next().equals(k)) {

   631                     it.remove();

   632                     if (maybe(2))

   633                         THROWS(IllegalStateException.class,

   634                                new Fun(){void f(){ it.remove(); }});

   635                 }

   636             checkUnusedKey(m, k);}};

   637         case 6: return new MapFrobber() {void frob(NavigableMap m) {

   638             final Iterator<Map.Entry> it = m.entrySet().iterator();

   639             while (it.hasNext())

   640                 if (it.next().getKey().equals(k)) {

   641                     it.remove();

   642                     if (maybe(2))

   643                         THROWS(IllegalStateException.class, remover(it));

   644                 }

   645             checkUnusedKey(m, k);}};

   646         }

   647     }

   648 

   649     static SetFrobber randomRemover(NavigableSet s) {

   650         final Integer e = usedElt(s);

   651         switch (rnd.nextInt(7)) {

   652         default: throw new Error();

   653         case 0: return new SetFrobber() {void frob(NavigableSet s) {

   654             Object e = s.first();

   655             equal(s.pollFirst(), e);

   656             checkUnusedElt(s, e);}};

   657         case 1: return new SetFrobber() {void frob(NavigableSet s) {

   658             Object e = s.last();

   659             equal(s.pollLast(), e);

   660             checkUnusedElt(s, e);}};

   661         case 2: return new SetFrobber() {void frob(NavigableSet s) {

   662             check(s.remove(e));

   663             checkUnusedElt(s, e);}};

   664         case 3: return new SetFrobber() {void frob(NavigableSet s) {

   665             s.subSet(e, true, e, true).clear();

   666             checkUnusedElt(s, e);}};

   667         case 4: return new SetFrobber() {void frob(NavigableSet s) {

   668             s.descendingSet().subSet(e, true, e, true).clear();

   669             checkUnusedElt(s, e);}};

   670         case 5: return new SetFrobber() {void frob(NavigableSet s) {

   671             final Iterator it = s.iterator();

   672             while (it.hasNext())

   673                 if (it.next().equals(e)) {

   674                     it.remove();

   675                     if (maybe(2))

   676                         THROWS(IllegalStateException.class,

   677                                new Fun(){void f(){ it.remove(); }});

   678                 }

   679             checkUnusedElt(s, e);}};

   680         case 6: return new SetFrobber() {void frob(NavigableSet s) {

   681             final Iterator it = s.descendingSet().iterator();

   682             while (it.hasNext())

   683                 if (it.next().equals(e)) {

   684                     it.remove();

   685                     if (maybe(2))

   686                         THROWS(IllegalStateException.class,

   687                                new Fun(){void f(){ it.remove(); }});

   688                 }

   689             checkUnusedElt(s, e);}};

   690         }

   691     }

   692 

   693     static void lockStep(NavigableMap m1,

   694                          NavigableMap m2) {

   695         if (! (thorough || maybe(3))) return;

   696         if (maybe(4)) m1 = serialClone(m1);

   697         if (maybe(4)) m2 = serialClone(m2);

   698 

   699         List<NavigableMap> maps = Arrays.asList(m1, m2);

   700         for (NavigableMap m : maps) testEmptyMap(m);

   701         final Set<Integer> ints = new HashSet<Integer>();

   702         while (ints.size() < size)

   703             ints.add(rnd.nextInt(1024));

   704         final Integer[] elts = ints.toArray(new Integer[size]);

   705         for (int i = 0; i < size; i++) {

   706             MapFrobber adder = randomAdder(m1);

   707             for (final NavigableMap m : maps) {

   708                 adder.frob(m);

   709                 equal(m.size(), i+1);

   710             }

   711             equalNavigableMaps(m1, m2);

   712         }

   713         for (final NavigableMap m : maps) {

   714             final Object e = usedKey(m);

   715             THROWS(IllegalArgumentException.class,

   716                    new Fun(){void f(){m.subMap(e,true,e,false)

   717                                        .subMap(e,true,e,true);}},

   718                    new Fun(){void f(){m.subMap(e,false,e,true)

   719                                        .subMap(e,true,e,true);}},

   720                    new Fun(){void f(){m.tailMap(e,false).tailMap(e,true);}},

   721                    new Fun(){void f(){m.headMap(e,false).headMap(e,true);}});

   722         }

   723         //System.out.printf("%s%n", m1);

   724         for (int i = size; i > 0; i--) {

   725             MapFrobber remover = randomRemover(m1);

   726             for (final NavigableMap m : maps) {

   727                 remover.frob(m);

   728                 equal(m.size(), i-1);

   729             }

   730             equalNavigableMaps(m1, m2);

   731         }

   732         for (NavigableMap m : maps) testEmptyMap(m);

   733     }

   734 

   735     static void lockStep(NavigableSet s1,

   736                          NavigableSet s2) {

   737         if (! (thorough || maybe(3))) return;

   738         if (maybe(4)) s1 = serialClone(s1);

   739         if (maybe(4)) s2 = serialClone(s2);

   740 

   741         List<NavigableSet> sets = Arrays.asList(s1, s2);

   742         for (NavigableSet s : sets) testEmptySet(s);

   743         final Set<Integer> ints = new HashSet<Integer>();

   744         while (ints.size() < size)

   745             ints.add(rnd.nextInt(1024));

   746         final Integer[] elts = ints.toArray(new Integer[size]);

   747         for (int i = 0; i < size; i++) {

   748             SetFrobber adder = randomAdder(s1);

   749             for (final NavigableSet s : sets) {

   750                 adder.frob(s);

   751                 equal(s.size(), i+1);

   752             }

   753             equalNavigableSets(s1, s2);

   754         }

   755         for (final NavigableSet s : sets) {

   756             final Object e = usedElt(s);

   757             THROWS(IllegalArgumentException.class,

   758                    new Fun(){void f(){s.subSet(e,true,e,false)

   759                                        .subSet(e,true,e,true);}},

   760                    new Fun(){void f(){s.subSet(e,false,e,true)

   761                                        .subSet(e,true,e,true);}},

   762                    new Fun(){void f(){s.tailSet(e,false).tailSet(e,true);}},

   763                    new Fun(){void f(){s.headSet(e,false).headSet(e,true);}});

   764         }

   765         //System.out.printf("%s%n", s1);

   766         for (int i = size; i > 0; i--) {

   767             SetFrobber remover = randomRemover(s1);

   768             for (final NavigableSet s : sets) {

   769                 remover.frob(s);

   770                 equal(s.size(), i-1);

   771             }

   772             equalNavigableSets(s1, s2);

   773         }

   774         for (NavigableSet s : sets) testEmptySet(s);

   775     }

   776 

   777     //--------------------- Infrastructure ---------------------------

   778     static volatile int passed = 0, failed = 0;

   779     static void pass() { passed++; }

   780     static void fail() { failed++; Thread.dumpStack(); }

   781     static void fail(String msg) { System.out.println(msg); fail(); }

   782     static void unexpected(Throwable t) { failed++; t.printStackTrace(); }

   783     static void check(boolean cond) { if (cond) pass(); else fail(); }

   784     static void equal(Object x, Object y) {

   785         if (x == null ? y == null : x.equals(y)) pass();

   786         else {System.out.println(x + " not equal to " + y); fail();}}

   787     static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}

   788     public static void main(String[] args) throws Throwable {

   789         try { realMain(args); } catch (Throwable t) { unexpected(t); }

   790 

   791         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);

   792         if (failed > 0) throw new Exception("Some tests failed");

   793     }

   794     static abstract class Fun {abstract void f() throws Throwable;}

   795     static void THROWS(Class<? extends Throwable> k, Fun... fs) {

   796           for (Fun f : fs)

   797               try { f.f(); fail("Expected " + k.getName() + " not thrown"); }

   798               catch (Throwable t) {

   799                   if (k.isAssignableFrom(t.getClass())) pass();

   800                   else unexpected(t);}}

   801     static byte[] serializedForm(Object obj) {

   802         try {

   803             ByteArrayOutputStream baos = new ByteArrayOutputStream();

   804             new ObjectOutputStream(baos).writeObject(obj);

   805             return baos.toByteArray();

   806         } catch (IOException e) { throw new RuntimeException(e); }}

   807     static Object readObject(byte[] bytes)

   808         throws IOException, ClassNotFoundException {

   809         InputStream is = new ByteArrayInputStream(bytes);

   810         return new ObjectInputStream(is).readObject();}

   811     @SuppressWarnings("unchecked")

   812     static <T> T serialClone(T obj) {

   813         try { return (T) readObject(serializedForm(obj)); }

   814         catch (Exception e) { throw new RuntimeException(e); }}

   815 }