/*

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

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

 * have any questions.

 */

/*

 * @test

 * @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);

    }

    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 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());

        }

        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);

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