/*

 * 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.

 *

 */

/*

 * @test

 * @bug     6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464

 *          4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753

 *          6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215

 * @summary Run many tests on many Collection and Map implementations

 * @author  Martin Buchholz

 */

/* Mother Of All (Collection) Tests

 *

 * Testing of collection classes is often spotty, because many tests

 * need to be performed on many implementations, but the onus on

 * writing the tests falls on the engineer introducing the new

 * implementation.

 *

 * The idea of this mega-test is that:

 *

 * An engineer adding a new collection implementation could simply add

 * their new implementation to a list of implementations in this

 * test's main method.  Any general purpose Collection<Integer> or

 * Map<Integer,Integer> class is appropriate.

 *

 * An engineer fixing a regression could add their regression test here and

 * simultaneously test all other implementations.

 */

import java.io.*;

import java.util.*;

import java.util.concurrent.*;

import static java.util.Collections.*;

public class MOAT {

    public static void realMain(String[] args) {

        testCollection(new LinkedHashSet<Integer>());

        testCollection(new HashSet<Integer>());

        testCollection(new Vector<Integer>());

        testCollection(new Vector<Integer>().subList(0,0));

        testCollection(new ArrayDeque<Integer>());

        testCollection(new ArrayList<Integer>());

        testCollection(new ArrayList<Integer>().subList(0,0));

        testCollection(new LinkedList<Integer>());

        testCollection(new LinkedList<Integer>().subList(0,0));

        testCollection(new TreeSet<Integer>());

        testCollection(new CopyOnWriteArrayList<Integer>());

        testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));

        testCollection(new CopyOnWriteArraySet<Integer>());

        testCollection(new PriorityQueue<Integer>());

        testCollection(new PriorityBlockingQueue<Integer>());

        testCollection(new ArrayBlockingQueue<Integer>(20));

        testCollection(new LinkedBlockingQueue<Integer>(20));

        testCollection(new LinkedBlockingDeque<Integer>(20));

        testCollection(new ConcurrentLinkedQueue<Integer>());

        testCollection(new LinkedTransferQueue<Integer>());

        testCollection(new ConcurrentSkipListSet<Integer>());

        testCollection(Arrays.asList(new Integer(42)));

        testCollection(Arrays.asList(1,2,3));

        testCollection(nCopies(25,1));

        testImmutableList(nCopies(25,1));

        testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));

        testMap(new HashMap<Integer,Integer>());

        testMap(new LinkedHashMap<Integer,Integer>());

        testMap(new WeakHashMap<Integer,Integer>());

        testMap(new IdentityHashMap<Integer,Integer>());

        testMap(new TreeMap<Integer,Integer>());

        testMap(new Hashtable<Integer,Integer>());

        testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));

        testMap(new ConcurrentSkipListMap<Integer,Integer>());

        // Empty collections

        final List<Integer> emptyArray = Arrays.asList(new Integer[]{});

        testCollection(emptyArray);

        testEmptyList(emptyArray);

        THROWS(IndexOutOfBoundsException.class,

               new Fun(){void f(){ emptyArray.set(0,1); }});

        THROWS(UnsupportedOperationException.class,

               new Fun(){void f(){ emptyArray.add(0,1); }});

        List<Integer> noOne = nCopies(0,1);

        testCollection(noOne);

        testEmptyList(noOne);

        testImmutableList(noOne);

        Set<Integer> emptySet = emptySet();

        testCollection(emptySet);

        testEmptySet(emptySet);

        testEmptySet(EMPTY_SET);

        testImmutableSet(emptySet);

        List<Integer> emptyList = emptyList();

        testCollection(emptyList);

        testEmptyList(emptyList);

        testEmptyList(EMPTY_LIST);

        testImmutableList(emptyList);

        Map<Integer,Integer> emptyMap = emptyMap();

        testMap(emptyMap);

        testEmptyMap(emptyMap);

        testEmptyMap(EMPTY_MAP);

        testImmutableMap(emptyMap);

        // Singleton collections

        Set<Integer> singletonSet = singleton(1);

        equal(singletonSet.size(), 1);

        testCollection(singletonSet);

        testImmutableSet(singletonSet);

        List<Integer> singletonList = singletonList(1);

        equal(singletonList.size(), 1);

        testCollection(singletonList);

        testImmutableList(singletonList);

        testImmutableList(singletonList.subList(0,1));

        testImmutableList(singletonList.subList(0,1).subList(0,1));

        testEmptyList(singletonList.subList(0,0));

        testEmptyList(singletonList.subList(0,0).subList(0,0));

        Map<Integer,Integer> singletonMap = singletonMap(1,2);

        equal(singletonMap.size(), 1);

        testMap(singletonMap);

        testImmutableMap(singletonMap);

    }

    private static void checkContainsSelf(Collection<Integer> c) {

        check(c.containsAll(c));

        check(c.containsAll(Arrays.asList(c.toArray())));

        check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));

    }

    private static void checkContainsEmpty(Collection<Integer> c) {

        check(c.containsAll(new ArrayList<Integer>()));

    }

    private static <T> void testEmptyCollection(Collection<T> c) {

        check(c.isEmpty());

        equal(c.size(), 0);

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

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

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

        check(c.toArray(new Object[]{42})[0] == null);

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

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

        equal(a[0], null);

        testEmptyIterator(c.iterator());

    }

    static <T> void testEmptyIterator(final Iterator<T> it) {

        if (rnd.nextBoolean())

            check(! it.hasNext());

        THROWS(NoSuchElementException.class,

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

        try { it.remove(); }

        catch (IllegalStateException _) { pass(); }

        catch (UnsupportedOperationException _) { pass(); }

        catch (Throwable t) { unexpected(t); }

        if (rnd.nextBoolean())

            check(! it.hasNext());

    }

    private static void testEmptyList(List<?> c) {

        testEmptyCollection(c);

        equal(c.hashCode(), 1);

        equal2(c, Collections.<Integer>emptyList());

    }

    private static <T> void testEmptySet(Set<T> c) {

        testEmptyCollection(c);

        equal(c.hashCode(), 0);

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

        if (c instanceof NavigableSet<?>)

            testEmptyIterator(((NavigableSet<T>)c).descendingIterator());

    }

    private static void testImmutableCollection(final Collection<Integer> c) {

        THROWS(UnsupportedOperationException.class,

               new Fun(){void f(){ c.add(99); }},

               new Fun(){void f(){ c.addAll(singleton(99)); }});

        if (! c.isEmpty()) {

            final Integer first = c.iterator().next();

            THROWS(UnsupportedOperationException.class,

                   new Fun(){void f(){ c.clear(); }},

                   new Fun(){void f(){ c.remove(first); }},

                   new Fun(){void f(){ c.removeAll(singleton(first)); }},

                   new Fun(){void f(){ c.retainAll(emptyList()); }}

                   );

        }

    }

    private static void testImmutableSet(final Set<Integer> c) {

        testImmutableCollection(c);

    }

    private static void testImmutableList(final List<Integer> c) {

        testList(c);

        testImmutableCollection(c);

        THROWS(UnsupportedOperationException.class,

               new Fun(){void f(){ c.set(0,42); }},

               new Fun(){void f(){ c.add(0,42); }},

               new Fun(){void f(){ c.addAll(0,singleton(86)); }});

        if (! c.isEmpty())

            THROWS(UnsupportedOperationException.class,

                   new Fun(){void f(){

                           Iterator<Integer> it = c.iterator();

                           it.next(); it.remove();}},

                   new Fun(){void f(){

                           ListIterator<Integer> it = c.listIterator();

                           it.next(); it.remove();}});

    }

    private static void clear(Collection<Integer> c) {

        try { c.clear(); }

        catch (Throwable t) { unexpected(t); }

        testEmptyCollection(c);

    }

    private static <K,V> void testEmptyMap(final Map<K,V> m) {

        check(m.isEmpty());

        equal(m.size(), 0);

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

        testEmptySet(m.keySet());

        testEmptySet(m.entrySet());

        testEmptyCollection(m.values());

        try { check(! m.containsValue(null)); }

        catch (NullPointerException _) { /* OK */ }

        try { check(! m.containsKey(null)); }

        catch (NullPointerException _) { /* OK */ }

        check(! m.containsValue(1));

        check(! m.containsKey(1));

    }

    private static void testImmutableMap(final Map<Integer,Integer> m) {

        THROWS(UnsupportedOperationException.class,

               new Fun(){void f(){ m.put(1,1); }},

               new Fun(){void f(){ m.putAll(singletonMap(1,1)); }});

        if (! m.isEmpty()) {

            final Integer first = m.keySet().iterator().next();

            THROWS(UnsupportedOperationException.class,

                   new Fun(){void f(){ m.remove(first); }},

                   new Fun(){void f(){ m.clear(); }});

            final Map.Entry<Integer,Integer> me

                = m.entrySet().iterator().next();

            Integer key = me.getKey();

            Integer val = me.getValue();

            THROWS(UnsupportedOperationException.class,

                   new Fun(){void f(){ me.setValue(3); }});

            equal(key, me.getKey());

            equal(val, me.getValue());

        }

        testImmutableSet(m.keySet());

        testImmutableCollection(m.values());

        //testImmutableSet(m.entrySet());

    }

    private static void clear(Map<?,?> m) {

        try { m.clear(); }

        catch (Throwable t) { unexpected(t); }

        testEmptyMap(m);

    }

    private static void oneElement(Collection<Integer> c) {

        clear(c);

        try {

            check(c.add(-42));

            equal(c.toString(), "[-42]");

            if (c instanceof Set) check(! c.add(-42));

        } catch (Throwable t) { unexpected(t); }

        check(! c.isEmpty()); check(c.size() == 1);

    }

    private static boolean supportsAdd(Collection<Integer> c) {

        try { check(c.add(778347983)); }

        catch (UnsupportedOperationException t) { return false; }

        catch (Throwable t) { unexpected(t); }

        try {

            check(c.contains(778347983));

            check(c.remove(778347983));

        } catch (Throwable t) { unexpected(t); }

        return true;

    }

    private static boolean supportsRemove(Collection<Integer> c) {

        try { check(! c.remove(19134032)); }

        catch (UnsupportedOperationException t) { return false; }

        catch (Throwable t) { unexpected(t); }

        return true;

    }

    private static void checkFunctionalInvariants(Collection<Integer> c) {

        try {

            checkContainsSelf(c);

            checkContainsEmpty(c);

            check(c.size() != 0 ^ c.isEmpty());

            {

                int size = 0;

                for (Integer i : c) size++;

                check(c.size() == size);

            }

            check(c.toArray().length == c.size());

            check(c.toArray().getClass() == Object[].class

                  ||

                  // !!!!

                  // 6260652: (coll) Arrays.asList(x).toArray().getClass()

                  // should be Object[].class

                  (c.getClass().getName().equals("java.util.Arrays$ArrayList"))

                  );

            for (int size : new int[]{0,1,c.size(), c.size()+1}) {

                Integer[] a = c.toArray(new Integer[size]);

                check((size > c.size()) || a.length == c.size());

                int i = 0; for (Integer j : c) check(a[i++] == j);

                check((size <= c.size()) || (a[c.size()] == null));

                check(a.getClass() == Integer[].class);

            }

            check(c.equals(c));

            if (c instanceof Serializable) {

                //System.out.printf("Serializing %s%n", c.getClass().getName());

                try {

                    Object clone = serialClone(c);

                    equal(c instanceof Serializable,

                          clone instanceof Serializable);

                    equal(c instanceof RandomAccess,

                          clone instanceof RandomAccess);

                    if ((c instanceof List) || (c instanceof Set))

                        equal(c, clone);

                    else

                        equal(new HashSet<Integer>(c),

                              new HashSet<Integer>(serialClone(c)));

                } catch (Error xxx) {

                    if (! (xxx.getCause() instanceof NotSerializableException))

                        throw xxx;

                }

            }

        }

        catch (Throwable t) { unexpected(t); }

    }

    //----------------------------------------------------------------

    // If add(null) succeeds, contains(null) & remove(null) should succeed

    //----------------------------------------------------------------

    private static void testNullElement(Collection<Integer> c) {

        // !!!! 5018849: (coll) TreeSet.contains(null) does not agree with Javadoc

        if (c instanceof TreeSet) return;

        try {

            check(c.add(null));

            if (c.size() == 1)

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

            try {

                checkFunctionalInvariants(c);

                check(c.contains(null));

                check(c.remove(null));

            }

            catch (Throwable t) { unexpected(t); }

        }

        catch (NullPointerException e) { /* OK */ }

        catch (Throwable t) { unexpected(t); }

    }

    //----------------------------------------------------------------

    // If add("x") succeeds, contains("x") & remove("x") should succeed

    //----------------------------------------------------------------

    @SuppressWarnings("unchecked")

    private static void testStringElement(Collection<Integer> c) {

        Collection x = (Collection)c; // Make type-unsafe

        try {

            check(x.add("x"));

            try {

                check(x.contains("x"));

                check(x.remove("x"));

            } catch (Throwable t) { unexpected(t); }

        }

        catch (ClassCastException e) { /* OK */ }

        catch (Throwable t) { unexpected(t); }

    }

    private static void testConcurrentCollection(Collection<Integer> c) {

        try {

            c.add(1);

            Iterator<Integer> it = c.iterator();

            check(it.hasNext());

            clear(c);

            check(it.next() instanceof Integer); // No CME

            check(c.isEmpty());

        }

        catch (Throwable t) { unexpected(t); }

    }

    private static void testQueue(Queue<Integer> q) {

        q.clear();

        for (int i = 0; i < 5; i++) {

            testQueueAddRemove(q, null);

            testQueueAddRemove(q, 537);

            q.add(i);

        }

        equal(q.size(), 5);

        checkFunctionalInvariants(q);

        q.poll();

        equal(q.size(), 4);

        checkFunctionalInvariants(q);

        if ((q instanceof LinkedBlockingQueue) ||

            (q instanceof LinkedBlockingDeque) ||

            (q instanceof ConcurrentLinkedQueue)) {

            testQueueIteratorRemove(q);

        }

    }

    private static void testQueueAddRemove(final Queue<Integer> q,

                                           final Integer e) {

        final List<Integer> originalContents = new ArrayList<Integer>(q);

        final boolean isEmpty = q.isEmpty();

        final boolean isList = (q instanceof List);

        final List asList = isList ? (List) q : null;

        check(!q.contains(e));

        try {

            q.add(e);

        } catch (NullPointerException npe) {

            check(e == null);

            return;                     // Null elements not supported

        }

        check(q.contains(e));

        check(q.remove(e));

        check(!q.contains(e));

        equal(new ArrayList<Integer>(q), originalContents);

        if (q instanceof Deque<?>) {

            final Deque<Integer> deq = (Deque<Integer>) q;

            final List<Integer> singleton = Collections.singletonList(e);

            // insert, query, remove element at head

            if (isEmpty) {

                THROWS(NoSuchElementException.class,

                       new Fun(){void f(){ deq.getFirst(); }},

                       new Fun(){void f(){ deq.element(); }},

                       new Fun(){void f(){ deq.iterator().next(); }});

                check(deq.peekFirst() == null);

                check(deq.peek() == null);

            } else {

                check(deq.getFirst() != e);

                check(deq.element() != e);

                check(deq.iterator().next() != e);

                check(deq.peekFirst() != e);

                check(deq.peek() != e);

            }

            check(!deq.contains(e));

            check(!deq.removeFirstOccurrence(e));

            check(!deq.removeLastOccurrence(e));

            if (isList) {

                check(asList.indexOf(e) == -1);

                check(asList.lastIndexOf(e) == -1);

            }

            switch (rnd.nextInt(isList ? 4 : 3)) {

            case 0: deq.addFirst(e); break;

            case 1: check(deq.offerFirst(e)); break;

            case 2: deq.push(e); break;

            case 3: asList.add(0, e); break;

            default: throw new AssertionError();

            }

            check(deq.peekFirst() == e);

            check(deq.getFirst() == e);

            check(deq.element() == e);

            check(deq.peek() == e);

            check(deq.iterator().next() == e);

            check(deq.contains(e));

            if (isList) {

                check(asList.get(0) == e);

                check(asList.indexOf(e) == 0);

                check(asList.lastIndexOf(e) == 0);

                check(asList.subList(0, 1).equals(singleton));

            }

            switch (rnd.nextInt(isList ? 11 : 9)) {

            case 0: check(deq.pollFirst() == e); break;

            case 1: check(deq.removeFirst() == e); break;

            case 2: check(deq.remove() == e); break;

            case 3: check(deq.pop() == e); break;

            case 4: check(deq.removeFirstOccurrence(e)); break;

            case 5: check(deq.removeLastOccurrence(e)); break;

            case 6: check(deq.remove(e)); break;

            case 7: check(deq.removeAll(singleton)); break;

            case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;

            case 9: asList.remove(0); break;

            case 10: asList.subList(0, 1).clear(); break;

            default: throw new AssertionError();

            }

            if (isEmpty) {