/*

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

import junit.framework.Test;

import junit.framework.TestSuite;

public class TreeMapTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(TreeMapTest.class);

    }

    /**

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

     */

    private static TreeMap map5() {

        TreeMap map = new TreeMap();

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

        TreeMap map = map5();

        map.clear();

        assertEquals(0, map.size());

    }

    /**

     * copy constructor creates map equal to source map

     */

    public void testConstructFromSorted() {

        TreeMap map = map5();

        TreeMap map2 = new TreeMap(map);

        assertEquals(map, map2);

    }

    /**

     * Maps with same contents are equal

     */

    public void testEquals() {

        TreeMap map1 = map5();

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

        TreeMap map = map5();

        assertTrue(map.containsKey(one));

        assertFalse(map.containsKey(zero));

    }

    /**

     * containsValue returns true for held values

     */

    public void testContainsValue() {

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

        TreeMap map = map5();

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

        TreeMap empty = new TreeMap();

        assertNull(empty.get(one));

    }

    /**

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

     */

    public void testIsEmpty() {

        TreeMap empty = new TreeMap();

        TreeMap map = map5();

        assertTrue(empty.isEmpty());

        assertFalse(map.isEmpty());

    }

    /**

     * firstKey returns first key

     */

    public void testFirstKey() {

        TreeMap map = map5();

        assertEquals(one, map.firstKey());

    }

    /**

     * lastKey returns last key

     */

    public void testLastKey() {

        TreeMap map = map5();

        assertEquals(five, map.lastKey());

    }

    /**

     * keySet.toArray returns contains all keys

     */

    public void testKeySetToArray() {

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

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

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

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

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

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

        TreeMap 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 collection contains all values

     */

    public void testValues() {

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

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

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

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

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

        TreeMap empty = new TreeMap();

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

        TreeMap map = map5();

        map.remove(five);

        assertEquals(4, map.size());

        assertFalse(map.containsKey(five));

    }

    /**

     * lowerEntry returns preceding entry.

     */

    public void testLowerEntry() {

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

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

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

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

    }

    /**

     * lowerKey returns preceding element

     */

    public void testLowerKey() {

        TreeMap q = map5();

        Object e1 = q.lowerKey(three);

        assertEquals(two, e1);

        Object e2 = q.lowerKey(six);

        assertEquals(five, e2);

        Object e3 = q.lowerKey(one);

        assertNull(e3);

        Object e4 = q.lowerKey(zero);

        assertNull(e4);

    }

    /**

     * higherKey returns next element

     */

    public void testHigherKey() {

        TreeMap q = map5();

        Object e1 = q.higherKey(three);

        assertEquals(four, e1);

        Object e2 = q.higherKey(zero);

        assertEquals(one, e2);

        Object e3 = q.higherKey(five);

        assertNull(e3);

        Object e4 = q.higherKey(six);

        assertNull(e4);

    }

    /**

     * floorKey returns preceding element

     */

    public void testFloorKey() {

        TreeMap q = map5();

        Object e1 = q.floorKey(three);

        assertEquals(three, e1);

        Object e2 = q.floorKey(six);

        assertEquals(five, e2);

        Object e3 = q.floorKey(one);

        assertEquals(one, e3);

        Object e4 = q.floorKey(zero);

        assertNull(e4);

    }

    /**

     * ceilingKey returns next element

     */

    public void testCeilingKey() {

        TreeMap q = map5();

        Object e1 = q.ceilingKey(three);

        assertEquals(three, e1);

        Object e2 = q.ceilingKey(zero);

        assertEquals(one, e2);

        Object e3 = q.ceilingKey(five);

        assertEquals(five, e3);

        Object e4 = q.ceilingKey(six);

        assertNull(e4);

    }

    /**

     * pollFirstEntry returns entries in order

     */

    public void testPollFirstEntry() {

        TreeMap map = map5();