/*

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

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/publicdomain/zero/1.0/

 */

import java.util.ArrayList;

import java.util.Arrays;

import java.util.BitSet;

import java.util.Collection;

import java.util.Iterator;

import java.util.Map;

import java.util.NavigableMap;

import java.util.NavigableSet;

import java.util.NoSuchElementException;

import java.util.Random;

import java.util.Set;

import java.util.concurrent.ConcurrentSkipListMap;

import junit.framework.Test;

public class ConcurrentSkipListMapTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        class Implementation implements MapImplementation {

            public Class<?> klazz() { return ConcurrentSkipListMap.class; }

            public Map emptyMap() { return new ConcurrentSkipListMap(); }

            public boolean isConcurrent() { return true; }

            public boolean permitsNullKeys() { return false; }

            public boolean permitsNullValues() { return false; }

            public boolean supportsSetValue() { return false; }

        }

        return newTestSuite(

            ConcurrentSkipListMapTest.class,

            MapTest.testSuite(new Implementation()));

    }

    /**

     * Returns a new map from Integers 1-5 to Strings "A"-"E".

     */

    private static ConcurrentSkipListMap map5() {

        ConcurrentSkipListMap map = new ConcurrentSkipListMap();

        assertTrue(map.isEmpty());

        map.put(one, "A");

        map.put(five, "E");

        map.put(three, "C");

        map.put(two, "B");

        map.put(four, "D");

        assertFalse(map.isEmpty());

        assertEquals(5, map.size());

        return map;

    }

    /**

     * clear removes all pairs

     */

    public void testClear() {

        ConcurrentSkipListMap map = map5();

        map.clear();

        assertEquals(0, map.size());

    }

    /**

     * copy constructor creates map equal to source map

     */

    public void testConstructFromSorted() {

        ConcurrentSkipListMap map = map5();

        ConcurrentSkipListMap map2 = new ConcurrentSkipListMap(map);

        assertEquals(map, map2);

    }

    /**

     * Maps with same contents are equal

     */

    public void testEquals() {

        ConcurrentSkipListMap map1 = map5();

        ConcurrentSkipListMap map2 = map5();

        assertEquals(map1, map2);

        assertEquals(map2, map1);

        map1.clear();

        assertFalse(map1.equals(map2));

        assertFalse(map2.equals(map1));

    }

    /**

     * containsKey returns true for contained key

     */

    public void testContainsKey() {

        ConcurrentSkipListMap map = map5();

        assertTrue(map.containsKey(one));

        assertFalse(map.containsKey(zero));

    }

    /**

     * containsValue returns true for held values

     */

    public void testContainsValue() {

        ConcurrentSkipListMap map = map5();

        assertTrue(map.containsValue("A"));

        assertFalse(map.containsValue("Z"));

    }

    /**

     * get returns the correct element at the given key,

     * or null if not present

     */

    public void testGet() {

        ConcurrentSkipListMap map = map5();

        assertEquals("A", (String)map.get(one));

        ConcurrentSkipListMap empty = new ConcurrentSkipListMap();

        assertNull(empty.get(one));

    }

    /**

     * isEmpty is true of empty map and false for non-empty

     */

    public void testIsEmpty() {

        ConcurrentSkipListMap empty = new ConcurrentSkipListMap();

        ConcurrentSkipListMap map = map5();

        assertTrue(empty.isEmpty());

        assertFalse(map.isEmpty());

    }

    /**

     * firstKey returns first key

     */

    public void testFirstKey() {

        ConcurrentSkipListMap map = map5();

        assertEquals(one, map.firstKey());

    }

    /**

     * lastKey returns last key

     */

    public void testLastKey() {

        ConcurrentSkipListMap map = map5();

        assertEquals(five, map.lastKey());

    }

    /**

     * keySet.toArray returns contains all keys

     */

    public void testKeySetToArray() {

        ConcurrentSkipListMap map = map5();

        Set s = map.keySet();

        Object[] ar = s.toArray();

        assertTrue(s.containsAll(Arrays.asList(ar)));

        assertEquals(5, ar.length);

        ar[0] = m10;

        assertFalse(s.containsAll(Arrays.asList(ar)));

    }

    /**

     * descendingkeySet.toArray returns contains all keys

     */

    public void testDescendingKeySetToArray() {

        ConcurrentSkipListMap map = map5();

        Set s = map.descendingKeySet();

        Object[] ar = s.toArray();

        assertEquals(5, ar.length);

        assertTrue(s.containsAll(Arrays.asList(ar)));

        ar[0] = m10;

        assertFalse(s.containsAll(Arrays.asList(ar)));

    }

    /**

     * keySet returns a Set containing all the keys

     */

    public void testKeySet() {

        ConcurrentSkipListMap map = map5();

        Set s = map.keySet();

        assertEquals(5, s.size());

        assertTrue(s.contains(one));

        assertTrue(s.contains(two));

        assertTrue(s.contains(three));

        assertTrue(s.contains(four));

        assertTrue(s.contains(five));

    }

    /**

     * keySet is ordered

     */

    public void testKeySetOrder() {

        ConcurrentSkipListMap map = map5();

        Set s = map.keySet();

        Iterator i = s.iterator();

        Integer last = (Integer)i.next();

        assertEquals(last, one);

        int count = 1;

        while (i.hasNext()) {

            Integer k = (Integer)i.next();

            assertTrue(last.compareTo(k) < 0);

            last = k;

            ++count;

        }

        assertEquals(5, count);

    }

    /**

     * descending iterator of key set is inverse ordered

     */

    public void testKeySetDescendingIteratorOrder() {

        ConcurrentSkipListMap map = map5();

        NavigableSet s = map.navigableKeySet();

        Iterator i = s.descendingIterator();

        Integer last = (Integer)i.next();

        assertEquals(last, five);

        int count = 1;

        while (i.hasNext()) {

            Integer k = (Integer)i.next();

            assertTrue(last.compareTo(k) > 0);

            last = k;

            ++count;

        }

        assertEquals(5, count);

    }

    /**

     * descendingKeySet is ordered

     */

    public void testDescendingKeySetOrder() {

        ConcurrentSkipListMap map = map5();

        Set s = map.descendingKeySet();

        Iterator i = s.iterator();

        Integer last = (Integer)i.next();

        assertEquals(last, five);

        int count = 1;

        while (i.hasNext()) {

            Integer k = (Integer)i.next();

            assertTrue(last.compareTo(k) > 0);

            last = k;

            ++count;

        }

        assertEquals(5, count);

    }

    /**

     * descending iterator of descendingKeySet is ordered

     */

    public void testDescendingKeySetDescendingIteratorOrder() {

        ConcurrentSkipListMap map = map5();

        NavigableSet s = map.descendingKeySet();

        Iterator i = s.descendingIterator();

        Integer last = (Integer)i.next();

        assertEquals(last, one);

        int count = 1;

        while (i.hasNext()) {

            Integer k = (Integer)i.next();

            assertTrue(last.compareTo(k) < 0);

            last = k;

            ++count;

        }

        assertEquals(5, count);

    }

    /**

     * Values.toArray contains all values

     */

    public void testValuesToArray() {

        ConcurrentSkipListMap map = map5();

        Collection v = map.values();

        Object[] ar = v.toArray();

        ArrayList s = new ArrayList(Arrays.asList(ar));

        assertEquals(5, ar.length);

        assertTrue(s.contains("A"));

        assertTrue(s.contains("B"));

        assertTrue(s.contains("C"));

        assertTrue(s.contains("D"));

        assertTrue(s.contains("E"));

    }

    /**

     * values collection contains all values

     */

    public void testValues() {

        ConcurrentSkipListMap map = map5();

        Collection s = map.values();

        assertEquals(5, s.size());

        assertTrue(s.contains("A"));

        assertTrue(s.contains("B"));

        assertTrue(s.contains("C"));

        assertTrue(s.contains("D"));

        assertTrue(s.contains("E"));

    }

    /**

     * entrySet contains all pairs

     */

    public void testEntrySet() {

        ConcurrentSkipListMap map = map5();

        Set s = map.entrySet();

        assertEquals(5, s.size());

        Iterator it = s.iterator();

        while (it.hasNext()) {

            Map.Entry e = (Map.Entry) it.next();

            assertTrue(

                       (e.getKey().equals(one) && e.getValue().equals("A")) ||

                       (e.getKey().equals(two) && e.getValue().equals("B")) ||

                       (e.getKey().equals(three) && e.getValue().equals("C")) ||

                       (e.getKey().equals(four) && e.getValue().equals("D")) ||

                       (e.getKey().equals(five) && e.getValue().equals("E")));

        }

    }

    /**

     * descendingEntrySet contains all pairs

     */

    public void testDescendingEntrySet() {

        ConcurrentSkipListMap map = map5();

        Set s = map.descendingMap().entrySet();

        assertEquals(5, s.size());

        Iterator it = s.iterator();

        while (it.hasNext()) {

            Map.Entry e = (Map.Entry) it.next();

            assertTrue(

                       (e.getKey().equals(one) && e.getValue().equals("A")) ||

                       (e.getKey().equals(two) && e.getValue().equals("B")) ||

                       (e.getKey().equals(three) && e.getValue().equals("C")) ||

                       (e.getKey().equals(four) && e.getValue().equals("D")) ||

                       (e.getKey().equals(five) && e.getValue().equals("E")));

        }

    }

    /**

     * entrySet.toArray contains all entries

     */

    public void testEntrySetToArray() {

        ConcurrentSkipListMap map = map5();

        Set s = map.entrySet();

        Object[] ar = s.toArray();

        assertEquals(5, ar.length);

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

            assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));

            assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));

        }

    }

    /**

     * descendingEntrySet.toArray contains all entries

     */

    public void testDescendingEntrySetToArray() {

        ConcurrentSkipListMap map = map5();

        Set s = map.descendingMap().entrySet();

        Object[] ar = s.toArray();

        assertEquals(5, ar.length);

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

            assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));

            assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));

        }

    }

    /**

     * putAll adds all key-value pairs from the given map

     */

    public void testPutAll() {

        ConcurrentSkipListMap empty = new ConcurrentSkipListMap();

        ConcurrentSkipListMap map = map5();

        empty.putAll(map);

        assertEquals(5, empty.size());

        assertTrue(empty.containsKey(one));

        assertTrue(empty.containsKey(two));

        assertTrue(empty.containsKey(three));

        assertTrue(empty.containsKey(four));

        assertTrue(empty.containsKey(five));

    }

    /**

     * putIfAbsent works when the given key is not present

     */

    public void testPutIfAbsent() {

        ConcurrentSkipListMap map = map5();

        map.putIfAbsent(six, "Z");

        assertTrue(map.containsKey(six));

    }

    /**

     * putIfAbsent does not add the pair if the key is already present

     */

    public void testPutIfAbsent2() {

        ConcurrentSkipListMap map = map5();

        assertEquals("A", map.putIfAbsent(one, "Z"));

    }

    /**

     * replace fails when the given key is not present

     */

    public void testReplace() {

        ConcurrentSkipListMap map = map5();

        assertNull(map.replace(six, "Z"));

        assertFalse(map.containsKey(six));

    }

    /**

     * replace succeeds if the key is already present

     */

    public void testReplace2() {

        ConcurrentSkipListMap map = map5();

        assertNotNull(map.replace(one, "Z"));

        assertEquals("Z", map.get(one));

    }

    /**

     * replace value fails when the given key not mapped to expected value

     */

    public void testReplaceValue() {

        ConcurrentSkipListMap map = map5();

        assertEquals("A", map.get(one));

        assertFalse(map.replace(one, "Z", "Z"));

        assertEquals("A", map.get(one));

    }

    /**

     * replace value succeeds when the given key mapped to expected value

     */

    public void testReplaceValue2() {

        ConcurrentSkipListMap map = map5();

        assertEquals("A", map.get(one));

        assertTrue(map.replace(one, "A", "Z"));

        assertEquals("Z", map.get(one));

    }

    /**

     * remove removes the correct key-value pair from the map

     */

    public void testRemove() {

        ConcurrentSkipListMap map = map5();

        map.remove(five);

        assertEquals(4, map.size());

        assertFalse(map.containsKey(five));

    }

    /**

     * remove(key,value) removes only if pair present

     */

    public void testRemove2() {

        ConcurrentSkipListMap map = map5();

        assertTrue(map.containsKey(five));

        assertEquals("E", map.get(five));

        map.remove(five, "E");

        assertEquals(4, map.size());

        assertFalse(map.containsKey(five));

        map.remove(four, "A");

        assertEquals(4, map.size());

        assertTrue(map.containsKey(four));

    }

    /**

     * lowerEntry returns preceding entry.

     */

    public void testLowerEntry() {

        ConcurrentSkipListMap map = map5();

        Map.Entry e1 = map.lowerEntry(three);

        assertEquals(two, e1.getKey());

        Map.Entry e2 = map.lowerEntry(six);

        assertEquals(five, e2.getKey());

        Map.Entry e3 = map.lowerEntry(one);

        assertNull(e3);

        Map.Entry e4 = map.lowerEntry(zero);

        assertNull(e4);

    }

    /**

     * higherEntry returns next entry.

     */

    public void testHigherEntry() {

        ConcurrentSkipListMap map = map5();

        Map.Entry e1 = map.higherEntry(three);

        assertEquals(four, e1.getKey());

        Map.Entry e2 = map.higherEntry(zero);

        assertEquals(one, e2.getKey());

        Map.Entry e3 = map.higherEntry(five);

        assertNull(e3);

        Map.Entry e4 = map.higherEntry(six);

        assertNull(e4);

    }

    /**

     * floorEntry returns preceding entry.

     */

    public void testFloorEntry() {

        ConcurrentSkipListMap map = map5();

        Map.Entry e1 = map.floorEntry(three);

        assertEquals(three, e1.getKey());

        Map.Entry e2 = map.floorEntry(six);

        assertEquals(five, e2.getKey());

        Map.Entry e3 = map.floorEntry(one);

        assertEquals(one, e3.getKey());

        Map.Entry e4 = map.floorEntry(zero);

        assertNull(e4);