/*

 * Copyright (c) 2005, 2015, 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     6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464

 *          4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753

 *          6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215

 *          4802647 7123424 8024709

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

 * @author  Martin Buchholz

 * @run main MOAT

 * @key randomness

 */

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

import java.lang.reflect.*;

public class MOAT {

    // Collections under test must not be initialized to contain this value,

    // and maps under test must not contain this value as a key.

    // It's used as a sentinel for absent-element testing.

    static final int ABSENT_VALUE = 778347983;

    static final Integer[] integerArray;

    static {

        Integer[] ia = new Integer[20];

        // fill with 1..20 inclusive

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

            ia[i] = i + 1;

        }

        integerArray = ia;

    }

    public static void realMain(String[] args) {

        testCollection(new NewAbstractCollection<Integer>());

        testCollection(new NewAbstractSet<Integer>());

        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(Collections.checkedList(new ArrayList<Integer>(), Integer.class));

        testCollection(Collections.synchronizedList(new ArrayList<Integer>()));

        testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));

        testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));

        testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));

        testCollection(Collections.synchronizedSet(new HashSet<Integer>()));

        testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));

        testCollection(Collections.synchronizedNavigableSet(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 ConcurrentLinkedDeque<Integer>());

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

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

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

        // TODO: Add reliable support for WeakHashMap.

        // This test is subject to very rare failures because the GC

        // may remove unreferenced-keys from the map at any time.

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

        testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));

        testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));

        testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));

        testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));

        testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));

        testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));

        // Unmodifiable wrappers

        testImmutableSet(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))));

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

        testImmutableMap(unmodifiableMap(Collections.singletonMap(1,2)));

        testCollMutatorsAlwaysThrow(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))));

        testCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));

        testEmptyCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));

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

        testListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));

        testEmptyListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));

        testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.singletonMap(1,2)));

        testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));

        testEmptyMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));

        // Empty collections

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

        testCollection(emptyArray);

        testEmptyList(emptyArray);

        THROWS(IndexOutOfBoundsException.class, () -> emptyArray.set(0,1));

        THROWS(UnsupportedOperationException.class, () -> 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);

        testEmptySet(Collections.emptySet());

        testEmptySet(Collections.emptySortedSet());

        testEmptySet(Collections.emptyNavigableSet());

        testImmutableSet(emptySet);

        List<Integer> emptyList = emptyList();

        testCollection(emptyList);

        testEmptyList(emptyList);

        testEmptyList(EMPTY_LIST);

        testEmptyList(Collections.emptyList());

        testImmutableList(emptyList);

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

        testMap(emptyMap);

        testEmptyMap(emptyMap);

        testEmptyMap(EMPTY_MAP);

        testEmptyMap(Collections.emptyMap());

        testEmptyMap(Collections.emptySortedMap());

        testEmptyMap(Collections.emptyNavigableMap());

        testImmutableMap(emptyMap);

        testImmutableMap(Collections.emptyMap());

        testImmutableMap(Collections.emptySortedMap());

        testImmutableMap(Collections.emptyNavigableMap());

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

        // Immutable List

        testEmptyList(List.of());

        testListMutatorsAlwaysThrow(List.of());

        testEmptyListMutatorsAlwaysThrow(List.of());

        for (List<Integer> list : Arrays.asList(

                List.<Integer>of(),

                List.of(1),

                List.of(1, 2),

                List.of(1, 2, 3),

                List.of(1, 2, 3, 4),

                List.of(1, 2, 3, 4, 5),

                List.of(1, 2, 3, 4, 5, 6),

                List.of(1, 2, 3, 4, 5, 6, 7),

                List.of(1, 2, 3, 4, 5, 6, 7, 8),

                List.of(1, 2, 3, 4, 5, 6, 7, 8, 9),

                List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),

                List.of(integerArray))) {

            testCollection(list);

            testImmutableList(list);

            testListMutatorsAlwaysThrow(list);

        }

        // Immutable Set

        testEmptySet(Set.of());

        testCollMutatorsAlwaysThrow(Set.of());

        testEmptyCollMutatorsAlwaysThrow(Set.of());

        for (Set<Integer> set : Arrays.asList(

                Set.<Integer>of(),

                Set.of(1),

                Set.of(1, 2),

                Set.of(1, 2, 3),

                Set.of(1, 2, 3, 4),

                Set.of(1, 2, 3, 4, 5),

                Set.of(1, 2, 3, 4, 5, 6),

                Set.of(1, 2, 3, 4, 5, 6, 7),

                Set.of(1, 2, 3, 4, 5, 6, 7, 8),

                Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9),

                Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),

                Set.of(integerArray))) {

            testCollection(set);

            testImmutableSet(set);

            testCollMutatorsAlwaysThrow(set);

        }

        // Immutable Map

        @SuppressWarnings("unchecked")

        Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20];

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

            ea[i] = Map.entry(i+1, i+101);

        }

        testEmptyMap(Map.of());

        testMapMutatorsAlwaysThrow(Map.of());

        testEmptyMapMutatorsAlwaysThrow(Map.of());

        for (Map<Integer,Integer> map : Arrays.asList(

                Map.<Integer,Integer>of(),

                Map.of(1, 101),

                Map.of(1, 101, 2, 202),

                Map.of(1, 101, 2, 202, 3, 303),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909),

                Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010),

                Map.ofEntries(ea))) {

            testMap(map);

            testImmutableMap(map);

            testMapMutatorsAlwaysThrow(map);

        }

    }

    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 void checkUnique(Set<Integer> s) {

        for (Integer i : s) {

            int count = 0;

            for (Integer j : s) {

                if (Objects.equals(i,j))

                    ++count;

            }

            check(count == 1);

        }

    }

    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, () -> it.next());

        try { it.remove(); }

        catch (IllegalStateException ignored) { pass(); }

        catch (UnsupportedOperationException ignored) { 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,

               () -> c.add(99),

               () -> c.addAll(singleton(99)));

        if (! c.isEmpty()) {

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

            THROWS(UnsupportedOperationException.class,

                   () -> c.clear(),

                   () -> c.remove(first),

                   () -> c.removeAll(singleton(first)),

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

               () -> c.set(0,42),

               () -> c.add(0,42),

               () -> c.addAll(0,singleton(86)));

        if (! c.isEmpty())

            THROWS(UnsupportedOperationException.class,

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

                           it.next();

                           it.remove(); },

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

                           it.next();

                           it.remove(); });

    }

    /**

     * Test that calling a mutator always throws UOE, even if the mutator

     * wouldn't actually do anything, given its arguments.

     *

     * @param c the collection instance to test

     */

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

        THROWS(UnsupportedOperationException.class,

                () -> c.addAll(Collections.emptyList()),

                () -> c.remove(ABSENT_VALUE),

                () -> c.removeAll(Collections.emptyList()),

                () -> c.removeIf(x -> false),

                () -> c.retainAll(c));

    }

    /**

     * Test that calling a mutator always throws UOE, even if the mutator

     * wouldn't actually do anything on an empty collection.

     *

     * @param c the collection instance to test, must be empty

     */

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

        if (! c.isEmpty()) {

            fail("collection is not empty");

        }

        THROWS(UnsupportedOperationException.class,

                () -> c.clear());

    }

    /**

     * As above, for a list.

     *

     * @param c the list instance to test

     */

    private static void testListMutatorsAlwaysThrow(List<Integer> c) {

        testCollMutatorsAlwaysThrow(c);

        THROWS(UnsupportedOperationException.class,

                () -> c.addAll(0, Collections.emptyList()));

    }

    /**

     * As above, for an empty list.

     *

     * @param c the list instance to test, must be empty

     */

    private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) {

        if (! c.isEmpty()) {

            fail("list is not empty");

        }

        testEmptyCollMutatorsAlwaysThrow(c);

        THROWS(UnsupportedOperationException.class,

                () -> c.replaceAll(x -> x),

                () -> c.sort(null));

    }

    /**

     * As above, for a map.

     *

     * @param m the map instance to test

     */

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

        THROWS(UnsupportedOperationException.class,

                () -> m.compute(ABSENT_VALUE, (k, v) -> null),

                () -> m.computeIfAbsent(ABSENT_VALUE, k -> null),

                () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null),

                () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null),

                () -> m.putAll(Collections.emptyMap()),

                () -> m.remove(ABSENT_VALUE),

                () -> m.remove(ABSENT_VALUE, 0),

                () -> m.replace(ABSENT_VALUE, 0),

                () -> m.replace(ABSENT_VALUE, 0, 1));

    }

    /**

     * As above, for an empty map.

     *

     * @param map the map instance to test, must be empty

     */

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

        if (! m.isEmpty()) {

            fail("map is not empty");

        }

        THROWS(UnsupportedOperationException.class,

                () -> m.clear(),

                () -> m.replaceAll((k, v) -> v));

    }

    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 ignored) { /* OK */ }

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

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

        check(! m.containsValue(1));

        check(! m.containsKey(1));

    }

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

        THROWS(UnsupportedOperationException.class,

               () -> m.put(1,1),

               () -> m.putAll(singletonMap(1,1)));

        if (! m.isEmpty()) {

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

            THROWS(UnsupportedOperationException.class,

                   () -> m.remove(first),

                   () -> m.clear());

            final Map.Entry<Integer,Integer> me

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