/*

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

import java.util.Iterator;

import java.util.Map;

import java.util.NavigableMap;

import java.util.Set;

import java.util.SortedMap;

import java.util.TreeMap;

import junit.framework.Test;

import junit.framework.TestSuite;

public class TreeSubMapTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(TreeSubMapTest.class);

    }

    /**

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

     */

    private static NavigableMap map5() {

        TreeMap map = new TreeMap();

        assertTrue(map.isEmpty());

        map.put(zero, "Z");

        map.put(one, "A");

        map.put(five, "E");

        map.put(three, "C");

        map.put(two, "B");

        map.put(four, "D");

        map.put(seven, "F");

        assertFalse(map.isEmpty());

        assertEquals(7, map.size());

        return map.subMap(one, true, seven, false);

    }

    private static NavigableMap map0() {

        TreeMap map = new TreeMap();

        assertTrue(map.isEmpty());

        return map.tailMap(one, true);

    }

    /**

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

     */

    private static NavigableMap dmap5() {

        TreeMap map = new TreeMap();

        assertTrue(map.isEmpty());

        map.put(m1, "A");

        map.put(m5, "E");

        map.put(m3, "C");

        map.put(m2, "B");

        map.put(m4, "D");

        assertFalse(map.isEmpty());

        assertEquals(5, map.size());

        return map.descendingMap();

    }

    private static NavigableMap dmap0() {

        TreeMap map = new TreeMap();

        assertTrue(map.isEmpty());

        return map;

    }

    /**

     * clear removes all pairs

     */

    public void testClear() {

        NavigableMap map = map5();

        map.clear();

        assertEquals(0, map.size());

    }

    /**

     * Maps with same contents are equal

     */

    public void testEquals() {

        NavigableMap map1 = map5();

        NavigableMap 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() {

        NavigableMap map = map5();

        assertTrue(map.containsKey(one));

        assertFalse(map.containsKey(zero));

    }

    /**

     * containsValue returns true for held values

     */

    public void testContainsValue() {

        NavigableMap 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() {

        NavigableMap map = map5();

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

        NavigableMap empty = map0();

        assertNull(empty.get(one));

    }

    /**

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

     */

    public void testIsEmpty() {

        NavigableMap empty = map0();

        NavigableMap map = map5();

        assertTrue(empty.isEmpty());

        assertFalse(map.isEmpty());

    }

    /**

     * firstKey returns first key

     */

    public void testFirstKey() {

        NavigableMap map = map5();

        assertEquals(one, map.firstKey());

    }

    /**

     * lastKey returns last key

     */

    public void testLastKey() {

        NavigableMap map = map5();

        assertEquals(five, map.lastKey());

    }

    /**

     * keySet returns a Set containing all the keys

     */

    public void testKeySet() {

        NavigableMap 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() {

        NavigableMap map = map5();

        Set s = map.keySet();

        Iterator i = s.iterator();

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

        assertEquals(last, one);

        while (i.hasNext()) {

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

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

            last = k;

        }

    }

    /**

     * values collection contains all values

     */

    public void testValues() {

        NavigableMap 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() {

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

        }

    }

    /**

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

     */

    public void testPutAll() {

        NavigableMap empty = map0();

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

    }

    /**

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

     */

    public void testRemove() {

        NavigableMap map = map5();

        map.remove(five);

        assertEquals(4, map.size());

        assertFalse(map.containsKey(five));

    }

    /**

     * lowerEntry returns preceding entry.

     */

    public void testLowerEntry() {

        NavigableMap 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() {

        NavigableMap 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() {

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

    }

    /**

     * ceilingEntry returns next entry.

     */

    public void testCeilingEntry() {

        NavigableMap map = map5();

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

        assertEquals(three, e1.getKey());

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

        assertEquals(one, e2.getKey());

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

        assertEquals(five, e3.getKey());

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

        assertNull(e4);

    }

    /**

     * pollFirstEntry returns entries in order

     */

    public void testPollFirstEntry() {

        NavigableMap map = map5();

        Map.Entry e = map.pollFirstEntry();

        assertEquals(one, e.getKey());

        assertEquals("A", e.getValue());

        e = map.pollFirstEntry();

        assertEquals(two, e.getKey());

        map.put(one, "A");

        e = map.pollFirstEntry();

        assertEquals(one, e.getKey());

        assertEquals("A", e.getValue());

        e = map.pollFirstEntry();

        assertEquals(three, e.getKey());

        map.remove(four);

        e = map.pollFirstEntry();

        assertEquals(five, e.getKey());

        try {

            e.setValue("A");

            shouldThrow();

        } catch (UnsupportedOperationException success) {}

        assertTrue(map.isEmpty());

        Map.Entry f = map.firstEntry();

        assertNull(f);

        e = map.pollFirstEntry();

        assertNull(e);

    }

    /**

     * pollLastEntry returns entries in order

     */

    public void testPollLastEntry() {

        NavigableMap map = map5();

        Map.Entry e = map.pollLastEntry();

        assertEquals(five, e.getKey());

        assertEquals("E", e.getValue());

        e = map.pollLastEntry();

        assertEquals(four, e.getKey());

        map.put(five, "E");

        e = map.pollLastEntry();

        assertEquals(five, e.getKey());

        assertEquals("E", e.getValue());

        e = map.pollLastEntry();

        assertEquals(three, e.getKey());

        map.remove(two);

        e = map.pollLastEntry();

        assertEquals(one, e.getKey());

        try {

            e.setValue("E");

            shouldThrow();

        } catch (UnsupportedOperationException success) {}

        e = map.pollLastEntry();

        assertNull(e);

    }

    /**

     * size returns the correct values

     */

    public void testSize() {

        NavigableMap map = map5();

        NavigableMap empty = map0();

        assertEquals(0, empty.size());

        assertEquals(5, map.size());

    }

    /**

     * toString contains toString of elements

     */

    public void testToString() {

        NavigableMap map = map5();

        String s = map.toString();

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

            assertTrue(s.contains(String.valueOf(i)));

        }

    }

    // Exception tests

    /**

     * get(null) of nonempty map throws NPE

     */

    public void testGet_NullPointerException() {

        NavigableMap c = map5();

        try {

            c.get(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * containsKey(null) of nonempty map throws NPE

     */

    public void testContainsKey_NullPointerException() {

        NavigableMap c = map5();

        try {

            c.containsKey(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * put(null,x) throws NPE

     */

    public void testPut1_NullPointerException() {

        NavigableMap c = map5();

        try {

            c.put(null, "whatever");

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * remove(null) throws NPE

     */

    public void testRemove1_NullPointerException() {

        NavigableMap c = map5();

        try {

            c.remove(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * A deserialized map equals original

     */

    public void testSerialization() throws Exception {

        NavigableMap x = map5();

        NavigableMap y = serialClone(x);

        assertNotSame(x, y);

        assertEquals(x.size(), y.size());

        assertEquals(x.toString(), y.toString());

        assertEquals(x, y);

        assertEquals(y, x);

    }

    /**

     * subMap returns map with keys in requested range

     */

    public void testSubMapContents() {

        NavigableMap map = map5();

        SortedMap sm = map.subMap(two, four);

        assertEquals(two, sm.firstKey());

        assertEquals(three, sm.lastKey());

        assertEquals(2, sm.size());

        assertFalse(sm.containsKey(one));

        assertTrue(sm.containsKey(two));

        assertTrue(sm.containsKey(three));

        assertFalse(sm.containsKey(four));

        assertFalse(sm.containsKey(five));

        Iterator i = sm.keySet().iterator();

        Object k;

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

        assertEquals(two, k);

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

        assertEquals(three, k);

        assertFalse(i.hasNext());

        Iterator j = sm.keySet().iterator();

        j.next();

        j.remove();

        assertFalse(map.containsKey(two));

        assertEquals(4, map.size());

        assertEquals(1, sm.size());

        assertEquals(three, sm.firstKey());

        assertEquals(three, sm.lastKey());

        assertEquals("C", sm.remove(three));

        assertTrue(sm.isEmpty());

        assertEquals(3, map.size());

    }

    public void testSubMapContents2() {

        NavigableMap map = map5();

        SortedMap sm = map.subMap(two, three);

        assertEquals(1, sm.size());

        assertEquals(two, sm.firstKey());

        assertEquals(two, sm.lastKey());

        assertFalse(sm.containsKey(one));

        assertTrue(sm.containsKey(two));

        assertFalse(sm.containsKey(three));

        assertFalse(sm.containsKey(four));

        assertFalse(sm.containsKey(five));

        Iterator i = sm.keySet().iterator();

        Object k;

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

        assertEquals(two, k);

        assertFalse(i.hasNext());

        Iterator j = sm.keySet().iterator();

        j.next();

        j.remove();