/*
 * Copyright (c) 2006, 2008, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * @test
 * @bug     6420753 6242436 6691185
 * @summary Compare NavigableMap implementations for identical behavior
 * @author  Martin Buchholz
 */

import java.io.*;
import java.util.*;
import java.util.concurrent.*;
import static java.util.Collections.*;

@SuppressWarnings("unchecked")
public class LockStep {
    static final int DEFAULT_SIZE = 5;
    static int size;            // Running time is O(size**2)

    static int intArg(String[] args, int i, int defaultValue) {
        return args.length > i ? Integer.parseInt(args[i]) : defaultValue;
    }

    // Pass -Dthorough=true for more exhaustive testing
    static final boolean thorough = Boolean.getBoolean("thorough");

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

    static void realMain(String[] args) {
        size = intArg(args, 0, DEFAULT_SIZE);

        lockSteps(new TreeMap(),
                  new ConcurrentSkipListMap());
        lockSteps(new TreeMap(reverseOrder()),
                  new ConcurrentSkipListMap(reverseOrder()));

        lockSteps(new TreeSet(),
                  new ConcurrentSkipListSet());
        lockSteps(new TreeSet(reverseOrder()),
                  new ConcurrentSkipListSet(reverseOrder()));
    }

    static void lockSteps(NavigableMap m1, NavigableMap m2) {
        if (maybe(4)) m1 = serialClone(m1);
        if (maybe(4)) m2 = serialClone(m2);
        lockStep(m1,
                 m2);
        lockStep(m1.descendingMap(),
                 m2.descendingMap());
        lockStep(fullSubMap(m1),
                 fullSubMap(m2));
        lockStep(fullSubMap(m1.descendingMap()),
                 fullSubMap(m2.descendingMap()));
        lockStep(fullHeadMap(m1),
                 fullHeadMap(m2));
        lockStep(fullHeadMap(m1.descendingMap()),
                 fullHeadMap(m2.descendingMap()));
        lockStep(fullTailMap(m1),
                 fullTailMap(m2));
        lockStep(fullTailMap(m1.descendingMap()),
                 fullTailMap(m2.descendingMap()));
    }

    static void lockSteps(NavigableSet s1, NavigableSet s2) {
        if (maybe(4)) s1 = serialClone(s1);
        if (maybe(4)) s2 = serialClone(s2);
        lockStep(s1,
                 s2);
        lockStep(s1.descendingSet(),
                 s2.descendingSet());
        lockStep(fullSubSet(s1),
                 fullSubSet(s2));
        lockStep(fullSubSet(s1.descendingSet()),
                 fullSubSet(s2.descendingSet()));
        lockStep(fullHeadSet(s1),
                 fullHeadSet(s2));
        lockStep(fullHeadSet(s1.descendingSet()),
                 fullHeadSet(s2.descendingSet()));
        lockStep(fullTailSet(s1),
                 fullTailSet(s2));
        lockStep(fullTailSet(s1.descendingSet()),
                 fullTailSet(s2.descendingSet()));
    }

    static boolean isAscending(NavigableMap m) {
        Comparator cmp = m.comparator();
        return (cmp == null || cmp.compare(1, 2) < 0);
    }

    static NavigableMap fullSubMap(NavigableMap m) {
        return isAscending(m)
            ? m.subMap(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
            : m.subMap(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
    }

    static NavigableMap fullHeadMap(NavigableMap m) {
        return isAscending(m)
            ? m.headMap(Integer.MAX_VALUE, true)
            : m.headMap(Integer.MIN_VALUE, true);
    }

    static NavigableMap fullTailMap(NavigableMap m) {
        return isAscending(m)
            ? m.tailMap(Integer.MIN_VALUE, true)
            : m.tailMap(Integer.MAX_VALUE, true);
    }

    static boolean isAscending(NavigableSet s) {
        Comparator cmp = s.comparator();
        return (cmp == null || cmp.compare(1, 2) < 0);
    }

    static NavigableSet fullSubSet(NavigableSet s) {
        return isAscending(s)
            ? s.subSet(Integer.MIN_VALUE, true, Integer.MAX_VALUE, true)
            : s.subSet(Integer.MAX_VALUE, true, Integer.MIN_VALUE, true);
    }

    static NavigableSet fullHeadSet(NavigableSet s) {
        return isAscending(s)
            ? s.headSet(Integer.MAX_VALUE, true)
            : s.headSet(Integer.MIN_VALUE, true);
    }

    static NavigableSet fullTailSet(NavigableSet s) {
        return isAscending(s)
            ? s.tailSet(Integer.MIN_VALUE, true)
            : s.tailSet(Integer.MAX_VALUE, true);
    }

    static void testEmptyCollection(Collection<?> c) {
        check(c.isEmpty());
        equal(c.size(), 0);
        equal(c.toString(),"[]");
        equal(c.toArray().length, 0);
        equal(c.toArray(new Object[0]).length, 0);

        Object[] a = new Object[1]; a[0] = Boolean.TRUE;
        equal(c.toArray(a), a);
        equal(a[0], null);
        check(! c.iterator().hasNext());
    }

    static void testEmptySet(Set<?> c) {
        testEmptyCollection(c);
        equal(c.hashCode(), 0);
        equal2(c, Collections.<Integer>emptySet());
    }

    static void testEmptyMap(final Map<?,?> m) {
        check(m.isEmpty());
        equal(m.size(), 0);
        equal(m.toString(),"{}");
        equal(m.hashCode(), 0);
        testEmptySet(m.keySet());
        testEmptySet(m.entrySet());
        testEmptyCollection(m.values());
    }

    static final Random rnd = new Random();

    static void equalNext(final Iterator<?> it, Object expected) {
        if (maybe(2))
            check(it.hasNext());
        equal(it.next(), expected);
    }

    static Comparator comparator(NavigableSet s) {
        Comparator cmp = s.comparator();
        return cmp != null ? cmp : new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Comparable) o1).compareTo(o2); }};
    }

    static Comparator comparator(NavigableMap m) {
        Comparator cmp = m.comparator();
        return cmp != null ? cmp : new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Comparable) o1).compareTo(o2); }};
    }

    static void checkNavigableSet(final NavigableSet s) {
        if (s.comparator() == null)
            check(s.descendingSet().descendingSet().comparator() == null);
        equal(s.isEmpty(), s.size() == 0);
        equal2(s, s.descendingSet());
        if (maybe(4) && s instanceof Serializable)
            equal2(s, serialClone(s));
        Comparator cmp = comparator(s);
        if (s.isEmpty()) {
            THROWS(NoSuchElementException.class,
                   new Fun(){void f(){ s.first(); }},
                   new Fun(){void f(){ s.last();  }});
            equal(null, s.lower(1));
            equal(null, s.floor(1));
            equal(null, s.ceiling(1));
            equal(null, s.higher(1));
        } else {
            Object a = s.first();
            Object z = s.last();
            equal(s.lower(a), null);
            equal(s.higher(z), null);
            equal2(s, s.tailSet(a));
            equal2(s, s.headSet(z, true));
            equal2(s, s.subSet(a, true, z, true));

            testEmptySet(s.subSet(a, true, a, false));
            testEmptySet(s.subSet(z, true, z, false));
            testEmptySet(s.headSet(a, false));
            testEmptySet(s.tailSet(z, false));

            equal2(s.headSet(a, true), singleton(a));
            equal2(s.tailSet(z, true), singleton(z));
        }
        Iterator[] its = new Iterator[] {
            s.iterator(),
            s.descendingSet().descendingSet().iterator(),
        };
        for (final Iterator it : its)
            if (maybe(4))
                THROWS(IllegalStateException.class,
                       new Fun(){void f(){ it.remove(); }});
        Object prev = null;
        for (Object e : s) {
            check(s.contains(e));
            for (Iterator it : its) equalNext(it, e);
            equal(e, s.ceiling(e));
            equal(e, s.floor(e));
            check(s.higher(e) == null || cmp.compare(e, s.higher(e)) < 0);
            equal(s.lower(e), prev);
            if (prev == null) {
            } else {
                check(cmp.compare(prev, e) < 0);
            }
            prev = e;
        }
        for (final Iterator it : its) {
            if (maybe(2))
                check(! it.hasNext());
            Fun fun = new Fun(){void f(){ it.next(); }};
            THROWS(NoSuchElementException.class, fun, fun, fun);
        }
    }

    static void equalIterators(final Iterator<?> it1,
                               final Iterator<?> it2) {
        while (it1.hasNext()) {
            if (maybe(2))
                check(it2.hasNext());
            equal(it1.next(), it2.next());
        }
        check(! it2.hasNext());
    }

    static void equalNavigableSetsLeaf(final NavigableSet s1,
                                       final NavigableSet s2) {
        equal2(s1,            s2);
        equal( s1.size(),     s2.size());
        equal( s1.isEmpty(),  s2.isEmpty());
        equal( s1.hashCode(), s2.hashCode());
        equal( s1.toString(), s2.toString());
        if (! s1.isEmpty()) {
            equal(s1.first(), s2.first());
            equal(s1.last(),  s2.last());
        }
        equalIterators(s1.iterator(), s2.iterator());
        equalIterators(s1.descendingIterator(), s2.descendingIterator());
        checkNavigableSet(s1);
        checkNavigableSet(s2);
    }

    static void equalNavigableSets(final NavigableSet s1,
                                   final NavigableSet s2) {
        equalNavigableSetsLeaf(s1, s2);
        equalNavigableSetsLeaf(s1.descendingSet(), s2.descendingSet());
        equalNavigableSetsLeaf(s1.descendingSet().descendingSet(), s2);
        Object min = s1.isEmpty() ? Integer.MIN_VALUE : s1.first();
        Object max = s2.isEmpty() ? Integer.MAX_VALUE : s2.last();
        if (s1.comparator() != null &&
            s1.comparator().compare(min, max) > 0) {
            Object tmp = min; min = max; max = tmp;
        }

        equalNavigableSetsLeaf(s1.subSet(min, true, max, true),
                               s2.subSet(min, true, max, true));
        equalNavigableSetsLeaf(s1.tailSet(min, true),
                               s2.tailSet(min, true));
        equalNavigableSetsLeaf(s1.headSet(max, true),
                               s2.headSet(max, true));
        equalNavigableSetsLeaf((NavigableSet) s1.subSet(min, max),
                               (NavigableSet) s2.subSet(min, max));
        equalNavigableSetsLeaf((NavigableSet) s1.tailSet(min),
                               (NavigableSet) s2.tailSet(min));
        equalNavigableSetsLeaf((NavigableSet) s1.headSet(max),
                               (NavigableSet) s2.headSet(max));
    }

    // Destined for a Collections.java near you?
    static <T> T[] concat(T[]... arrays) {
        int len = 0;
        for (int i = 0; i < arrays.length; i++)
            len += arrays[i].length;
        T[] a = (T[])java.lang.reflect.Array
            .newInstance(arrays[0].getClass().getComponentType(), len);
        int k = 0;
        for (int i = 0; i < arrays.length; i++) {
            T[] array = arrays[i];
            System.arraycopy(array, 0, a, k, array.length);
            k += array.length;
        }
        return a;
    }

    static void checkNavigableMap(final NavigableMap m) {
        if (m.comparator() == null) {
            check(m.descendingMap().descendingMap().comparator() == null);
            check(m.descendingKeySet().descendingSet().comparator() == null);
        }
        equal(m.isEmpty(), m.size() == 0);
        equal2(m, m.descendingMap());
        if (maybe(4))
            equal2(m, serialClone(m));
        equal2(m.keySet(), m.descendingKeySet());
        Comparator cmp = comparator(m);
        if (m.isEmpty()) {
            THROWS(NoSuchElementException.class,
                   new Fun(){void f(){ m.firstKey(); }},
                   new Fun(){void f(){ m.lastKey();  }});
            equal(null, m.firstEntry());
            equal(null, m.lastEntry());
            equal(null, m.pollFirstEntry());
            equal(null, m.pollLastEntry());
            equal(null, m.lowerKey(1));
            equal(null, m.floorKey(1));
            equal(null, m.ceilingKey(1));
            equal(null, m.higherKey(1));
            equal(null, m.lowerEntry(1));
            equal(null, m.floorEntry(1));
            equal(null, m.ceilingEntry(1));
            equal(null, m.higherEntry(1));
        } else {
            Object a = m.firstKey();
            Object z = m.lastKey();
            equal(m.lowerKey(a), null);
            equal(m.higherKey(z), null);
            equal(a, m.firstEntry().getKey());
            equal(z, m.lastEntry().getKey());
            equal2(m, m.tailMap(a));
            equal2(m, m.headMap(z, true));
            equal2(m, m.subMap(a, true, z, true));

            testEmptyMap(m.subMap(a, true, a, false));
            testEmptyMap(m.subMap(z, true, z, false));
            testEmptyMap(m.headMap(a, false));
            testEmptyMap(m.tailMap(z, false));

            equal2(m.headMap(a, true), singletonMap(a, m.get(a)));
            equal2(m.tailMap(z, true), singletonMap(z, m.get(z)));
        }

        Iterator[] kits = new Iterator[] {
            m.keySet().iterator(),
            m.descendingMap().descendingKeySet().iterator(),
            m.descendingKeySet().descendingSet().iterator(),
        };
        Iterator[] vits = new Iterator[] {
            m.values().iterator(),
            m.descendingMap().descendingMap().values().iterator(),
        };
        Iterator[] eits = new Iterator[] {
            m.entrySet().iterator(),
            m.descendingMap().descendingMap().entrySet().iterator(),
        };
        Iterator[] its = concat(kits, vits, eits);
        for (final Iterator it : its)
            if (maybe(4))
                THROWS(IllegalStateException.class,
                       new Fun(){void f(){ it.remove(); }});
        Map.Entry prev = null;
        for (Map.Entry e : (Set<Map.Entry>) m.entrySet()) {
            Object k = e.getKey();
            Object v = e.getValue();
            check(m.containsKey(k));
            check(m.containsValue(v));
            for (Iterator kit : kits) equalNext(kit, k);
            for (Iterator vit : vits) equalNext(vit, v);
            for (Iterator eit : eits) equalNext(eit, e);
            equal(k, m.ceilingKey(k));
            equal(k, m.ceilingEntry(k).getKey());
            equal(k, m.floorKey(k));
            equal(k, m.floorEntry(k).getKey());
            check(m.higherKey(k) == null || cmp.compare(k, m.higherKey(k)) < 0);
            check(m.lowerKey(k)  == null || cmp.compare(k, m.lowerKey(k))  > 0);
            equal(m.lowerEntry(k), prev);
            if (prev == null) {
                equal(m.lowerKey(k), null);
            } else {
                equal(m.lowerKey(k), prev.getKey());
                check(cmp.compare(prev.getKey(), e.getKey()) < 0);
            }
            prev = e;
        }
        for (final Iterator it : its) {
            if (maybe(2))
                check(! it.hasNext());
            Fun fun = new Fun(){void f(){ it.next(); }};
            THROWS(NoSuchElementException.class, fun, fun, fun);
        }
    }

    static void equalNavigableMapsLeaf(final NavigableMap m1,
                                       final NavigableMap m2) {
        equal2(m1,              m2);
        equal( m1.size(),       m2.size());
        equal( m1.isEmpty(),    m2.isEmpty());
        equal( m1.hashCode(),   m2.hashCode());
        equal( m1.toString(),   m2.toString());
        equal2(m1.firstEntry(), m2.firstEntry());
        equal2(m1.lastEntry(),  m2.lastEntry());
        checkNavigableMap(m1);
        checkNavigableMap(m2);
    }

    static void equalNavigableMaps(NavigableMap m1,
                                   NavigableMap m2) {
        equalNavigableMapsLeaf(m1, m2);
        equalNavigableSetsLeaf((NavigableSet) m1.keySet(),
                               (NavigableSet) m2.keySet());
        equalNavigableSets(m1.navigableKeySet(),
                           m2.navigableKeySet());
        equalNavigableSets(m1.descendingKeySet(),
                           m2.descendingKeySet());
        equal2(m1.entrySet(),
               m2.entrySet());
        equalNavigableMapsLeaf(m1.descendingMap(),
                               m2.descendingMap());
        equalNavigableMapsLeaf(m1.descendingMap().descendingMap(),
                               m2);
        equalNavigableSetsLeaf((NavigableSet) m1.descendingMap().keySet(),
                               (NavigableSet) m2.descendingMap().keySet());
        equalNavigableSetsLeaf(m1.descendingMap().descendingKeySet(),
                               m2.descendingMap().descendingKeySet());
        equal2(m1.descendingMap().entrySet(),
               m2.descendingMap().entrySet());

        //----------------------------------------------------------------
        // submaps
        //----------------------------------------------------------------
        Object min = Integer.MIN_VALUE;
        Object max = Integer.MAX_VALUE;
        if (m1.comparator() != null
            && m1.comparator().compare(min, max) > 0) {
            Object tmp = min; min = max; max = tmp;
        }
        switch (rnd.nextInt(6)) {
        case 0:
            equalNavigableMapsLeaf(m1.subMap(min, true, max, true),
                                   m2.subMap(min, true, max, true));
            break;
        case 1:
            equalNavigableMapsLeaf(m1.tailMap(min, true),
                                   m2.tailMap(min, true));
            break;
        case 2:
            equalNavigableMapsLeaf(m1.headMap(max, true),
                                   m2.headMap(max, true));
            break;
        case 3:
            equalNavigableMapsLeaf((NavigableMap) m1.subMap(min, max),
                                   (NavigableMap) m2.subMap(min, max));
            break;
        case 4:
            equalNavigableMapsLeaf((NavigableMap) m1.tailMap(min),
                                   (NavigableMap) m2.tailMap(min));
            break;
        case 5:
            equalNavigableMapsLeaf((NavigableMap) m1.headMap(max),
                                   (NavigableMap) m2.headMap(max));
            break;
        }
    }

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

    static MapFrobber randomAdder(NavigableMap m) {
        final Integer k = unusedKey(m);
        final MapFrobber[] randomAdders = {
            new MapFrobber() {void frob(NavigableMap m) {
                equal(m.put(k, k+1), null);
                equal(m.get(k), k+1);
                if (maybe(4)) {
                    equal(m.put(k, k+1), k+1);
                    equal(m.get(k), k+1);}}},
            new MapFrobber() {void frob(NavigableMap m) {
                m.descendingMap().put(k, k+1);
                equal(m.get(k), k+1);}},
            new MapFrobber() {void frob(NavigableMap m) {
                m.tailMap(k,true).headMap(k,true).put(k,k+1);}},
            new MapFrobber() {void frob(NavigableMap m) {
                m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}
        };
        return new MapFrobber() {void frob(NavigableMap m) {
            randomAdders[rnd.nextInt(randomAdders.length)].frob(m);
            if (maybe(2)) equal(m.get(k), k+1);
            if (maybe(4)) {
                equal(m.put(k, k+1), k+1);
                equal(m.get(k), k+1);}}};
    }

    static SetFrobber randomAdder(NavigableSet s) {
        final Integer e = unusedElt(s);
        final SetFrobber[] randomAdders = {
            new SetFrobber() {void frob(NavigableSet s) {
                check(s.add(e));}},
            new SetFrobber() {void frob(NavigableSet s) {
                s.descendingSet().add(e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                s.tailSet(e,true).headSet(e,true).add(e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}
        };
        return new SetFrobber() {void frob(NavigableSet s) {
            if (maybe(2)) check(! s.contains(e));
            randomAdders[rnd.nextInt(randomAdders.length)].frob(s);
            if (maybe(2)) check(! s.add(e));
            if (maybe(2)) check(s.contains(e));}};
    }

    static Integer unusedElt(NavigableSet s) {
        Integer e;
        do { e = rnd.nextInt(1024); }
        while (s.contains(e));
        return e;
    }

    static Integer unusedKey(NavigableMap m) {
        Integer k;
        do { k = rnd.nextInt(1024); }
        while (m.containsKey(k));
        return k;
    }

    static Integer usedKey(NavigableMap m) {
        Integer x = rnd.nextInt(1024);
        Integer floor   = (Integer) m.floorKey(x);
        Integer ceiling = (Integer) m.ceilingKey(x);
        if (floor != null) return floor;
        check(ceiling != null);
        return ceiling;
    }

    static Integer usedElt(NavigableSet s) {
        Integer x = rnd.nextInt(1024);
        Integer floor   = (Integer) s.floor(x);
        Integer ceiling = (Integer) s.ceiling(x);
        if (floor != null) return floor;
        check(ceiling != null);
        return ceiling;
    }

    static void checkUnusedKey(NavigableMap m, Object k) {
        check(! m.containsKey(k));
        equal(m.get(k), null);
        if (maybe(2))
            equal(m.remove(k), null);
    }

    static void checkUnusedElt(NavigableSet s, Object e) {
        if (maybe(2))
            check(! s.contains(e));
        if (maybe(2)) {
            check(s.ceiling(e) != e);
            check(s.floor(e)   != e);
        }
        if (maybe(2))
            check(! s.remove(e));
    }

    static Fun remover(final Iterator it) {
        return new Fun(){void f(){ it.remove(); }};
    }

    static MapFrobber randomRemover(NavigableMap m) {
        final Integer k = usedKey(m);
        final MapFrobber[] randomRemovers = {
            new MapFrobber() {void frob(NavigableMap m) {
                Map.Entry e = m.firstEntry();
                equal(m.pollFirstEntry(), e);
                checkUnusedKey(m, e.getKey());}},
            new MapFrobber() {void frob(NavigableMap m) {
                Map.Entry e = m.lastEntry();
                equal(m.pollLastEntry(), e);
                checkUnusedKey(m, e.getKey());}},
            new MapFrobber() {void frob(NavigableMap m) {
                check(m.remove(k) != null);
                checkUnusedKey(m, k);}},
            new MapFrobber() {void frob(NavigableMap m) {
                m.subMap(k, true, k, true).clear();
                checkUnusedKey(m, k);}},
            new MapFrobber() {void frob(NavigableMap m) {
                m.descendingMap().subMap(k, true, k, true).clear();
                checkUnusedKey(m, k);}},
            new MapFrobber() {void frob(NavigableMap m) {
                final Iterator it = m.keySet().iterator();
                while (it.hasNext())
                    if (it.next().equals(k)) {
                        it.remove();
                        if (maybe(2))
                            THROWS(IllegalStateException.class,
                                   new Fun(){void f(){ it.remove(); }});
                    }
                checkUnusedKey(m, k);}},
            new MapFrobber() {void frob(NavigableMap m) {
                final Iterator it = m.navigableKeySet().descendingIterator();
                while (it.hasNext())
                    if (it.next().equals(k)) {
                        it.remove();
                        if (maybe(2))
                            THROWS(IllegalStateException.class,
                                   new Fun(){void f(){ it.remove(); }});
                    }
                checkUnusedKey(m, k);}},
            new MapFrobber() {void frob(NavigableMap m) {
                final Iterator<Map.Entry> it = m.entrySet().iterator();
                while (it.hasNext())
                    if (it.next().getKey().equals(k)) {
                        it.remove();
                        if (maybe(2))
                            THROWS(IllegalStateException.class, remover(it));
                    }
                checkUnusedKey(m, k);}},
        };

        return randomRemovers[rnd.nextInt(randomRemovers.length)];
    }

    static SetFrobber randomRemover(NavigableSet s) {
        final Integer e = usedElt(s);

        final SetFrobber[] randomRemovers = {
            new SetFrobber() {void frob(NavigableSet s) {
                Object e = s.first();
                equal(s.pollFirst(), e);
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                Object e = s.last();
                equal(s.pollLast(), e);
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                check(s.remove(e));
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                s.subSet(e, true, e, true).clear();
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                s.descendingSet().subSet(e, true, e, true).clear();
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                final Iterator it = s.iterator();
                while (it.hasNext())
                    if (it.next().equals(e)) {
                        it.remove();
                        if (maybe(2))
                            THROWS(IllegalStateException.class,
                                   new Fun(){void f(){ it.remove(); }});
                    }
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                final Iterator it = s.descendingSet().iterator();
                while (it.hasNext())
                    if (it.next().equals(e)) {
                        it.remove();
                        if (maybe(2))
                            THROWS(IllegalStateException.class,
                                   new Fun(){void f(){ it.remove(); }});
                    }
                checkUnusedElt(s, e);}},
            new SetFrobber() {void frob(NavigableSet s) {
                final Iterator it = s.descendingIterator();
                while (it.hasNext())
                    if (it.next().equals(e)) {
                        it.remove();
                        if (maybe(2))
                            THROWS(IllegalStateException.class,
                                   new Fun(){void f(){ it.remove(); }});
                    }
                checkUnusedElt(s, e);}}
        };

        return randomRemovers[rnd.nextInt(randomRemovers.length)];
    }

    static void lockStep(NavigableMap m1,
                         NavigableMap m2) {
        if (! (thorough || maybe(3))) return;
        if (maybe(4)) m1 = serialClone(m1);
        if (maybe(4)) m2 = serialClone(m2);

        List<NavigableMap> maps = Arrays.asList(m1, m2);
        for (NavigableMap m : maps) testEmptyMap(m);
        final Set<Integer> ints = new HashSet<Integer>();
        while (ints.size() < size)
            ints.add(rnd.nextInt(1024));
        final Integer[] elts = ints.toArray(new Integer[size]);
        for (int i = 0; i < size; i++) {
            MapFrobber adder = randomAdder(m1);
            for (final NavigableMap m : maps) {
                adder.frob(m);
                equal(m.size(), i+1);
            }
            equalNavigableMaps(m1, m2);
        }
        for (final NavigableMap m : maps) {
            final Object e = usedKey(m);
            THROWS(IllegalArgumentException.class,
                   new Fun(){void f(){m.subMap(e,true,e,false)
                                       .subMap(e,true,e,true);}},
                   new Fun(){void f(){m.subMap(e,false,e,true)
                                       .subMap(e,true,e,true);}},
                   new Fun(){void f(){m.tailMap(e,false).tailMap(e,true);}},
                   new Fun(){void f(){m.headMap(e,false).headMap(e,true);}});
        }
        //System.out.printf("%s%n", m1);
        for (int i = size; i > 0; i--) {
            MapFrobber remover = randomRemover(m1);
            for (final NavigableMap m : maps) {
                remover.frob(m);
                equal(m.size(), i-1);
            }
            equalNavigableMaps(m1, m2);
        }
        for (NavigableMap m : maps) testEmptyMap(m);
    }

    static void lockStep(NavigableSet s1,
                         NavigableSet s2) {
        if (! (thorough || maybe(3))) return;
        if (maybe(4)) s1 = serialClone(s1);
        if (maybe(4)) s2 = serialClone(s2);

        List<NavigableSet> sets = Arrays.asList(s1, s2);
        for (NavigableSet s : sets) testEmptySet(s);
        final Set<Integer> ints = new HashSet<Integer>();
        while (ints.size() < size)
            ints.add(rnd.nextInt(1024));
        final Integer[] elts = ints.toArray(new Integer[size]);
        for (int i = 0; i < size; i++) {
            SetFrobber adder = randomAdder(s1);
            for (final NavigableSet s : sets) {
                adder.frob(s);
                equal(s.size(), i+1);
            }
            equalNavigableSets(s1, s2);
        }
        for (final NavigableSet s : sets) {
            final Object e = usedElt(s);
            THROWS(IllegalArgumentException.class,
                   new Fun(){void f(){s.subSet(e,true,e,false)
                                       .subSet(e,true,e,true);}},
                   new Fun(){void f(){s.subSet(e,false,e,true)
                                       .subSet(e,true,e,true);}},
                   new Fun(){void f(){s.tailSet(e,false).tailSet(e,true);}},
                   new Fun(){void f(){s.headSet(e,false).headSet(e,true);}});
        }
        //System.out.printf("%s%n", s1);
        for (int i = size; i > 0; i--) {
            SetFrobber remover = randomRemover(s1);
            for (final NavigableSet s : sets) {
                remover.frob(s);
                equal(s.size(), i-1);
            }
            equalNavigableSets(s1, s2);
        }
        for (NavigableSet s : sets) testEmptySet(s);
    }

    //--------------------- Infrastructure ---------------------------
    static volatile int passed = 0, failed = 0;
    static void pass() { passed++; }
    static void fail() { failed++; Thread.dumpStack(); }
    static void fail(String msg) { System.out.println(msg); fail(); }
    static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
    static void check(boolean cond) { if (cond) pass(); else fail(); }
    static void equal(Object x, Object y) {
        if (x == null ? y == null : x.equals(y)) pass();
        else {System.out.println(x + " not equal to " + y); fail();}}
    static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
    public static void main(String[] args) throws Throwable {
        try { realMain(args); } catch (Throwable t) { unexpected(t); }

        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
        if (failed > 0) throw new Exception("Some tests failed");
    }
    static abstract class Fun {abstract void f() throws Throwable;}
    static void THROWS(Class<? extends Throwable> k, Fun... fs) {
          for (Fun f : fs)
              try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
              catch (Throwable t) {
                  if (k.isAssignableFrom(t.getClass())) pass();
                  else unexpected(t);}}
    static byte[] serializedForm(Object obj) {
        try {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            new ObjectOutputStream(baos).writeObject(obj);
            return baos.toByteArray();
        } catch (IOException e) { throw new RuntimeException(e); }}
    static Object readObject(byte[] bytes)
        throws IOException, ClassNotFoundException {
        InputStream is = new ByteArrayInputStream(bytes);
        return new ObjectInputStream(is).readObject();}
    @SuppressWarnings("unchecked")
    static <T> T serialClone(T obj) {
        try { return (T) readObject(serializedForm(obj)); }
        catch (Exception e) { throw new RuntimeException(e); }}
}