test/tck/TreeMapTest.java

/*
 * 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/licenses/publicdomain
 */

import junit.framework.*;
import java.util.*;
import java.util.concurrent.*;
import java.io.*;

public class TreeMapTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());  
    }
    public static Test suite() {
        return new TestSuite(TreeMapTest.class);
    }

    /**
     * Create a 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(map.size(), 0);
    }

    /**
     *  
     */
    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);
        while (i.hasNext()) {
            Integer k = (Integer)i.next();
            assertTrue(last.compareTo(k) < 0);
            last = k;
        }
    }

    /**
     *   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);
        while (i.hasNext()) {
            Integer k = (Integer)i.next();
            assertTrue(last.compareTo(k) > 0);
            last = k;
        }
    }

    /**
     * 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.descendingEntrySet();
        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.descendingEntrySet();
        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();
        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 (Exception ok) {
        }
        e = map.pollFirstEntry();
        assertNull(e);
    }

    /**
     * pollLastEntry returns entries in order
     */
    public void testPollLastEntry() {
        TreeMap 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 (Exception ok) {
        }
        e = map.pollLastEntry();
        assertNull(e);
    }

    /**
     *   size returns the correct values
     */
    public void testSize() {
        TreeMap map = map5();
        TreeMap empty = new TreeMap();
        assertEquals(0, empty.size());
        assertEquals(5, map.size());
    }

    /**
     * toString contains toString of elements
     */
    public void testToString() {
        TreeMap map = map5();
        String s = map.toString();
        for (int i = 1; i <= 5; ++i) {
            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
        }
    }        

    // Exception tests

    /**
     * get(null) of nonempty map throws NPE
     */
    public void testGet_NullPointerException() {
        try {
            TreeMap c = map5();
            c.get(null);
            shouldThrow();
        } catch(NullPointerException e){}
    }

    /**
     * containsKey(null) of nonempty map throws NPE
     */
    public void testContainsKey_NullPointerException() {
        try {
            TreeMap c = map5();
            c.containsKey(null);
            shouldThrow();
        } catch(NullPointerException e){}
    }

    /**
     * remove(null) throws NPE for nonempty map
     */
    public void testRemove1_NullPointerException() {
        try {
            TreeMap c = new TreeMap();
            c.put("sadsdf", "asdads");
            c.remove(null);
            shouldThrow();
        } catch(NullPointerException e){}
    }

    /**
     * A deserialized map equals original
     */
    public void testSerialization() {
        TreeMap q = map5();

        try {
            ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
            ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
            out.writeObject(q);
            out.close();

            ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
            ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
            TreeMap r = (TreeMap)in.readObject();
            assertEquals(q.size(), r.size());
            assertTrue(q.equals(r));
            assertTrue(r.equals(q));
        } catch(Exception e){
            e.printStackTrace();
            unexpectedException();
        }
    }

    /**
     * subMap returns map with keys in requested range
     */
    public void testSubMapContents() {
        TreeMap map = map5();
        NavigableMap sm = map.navigableSubMap(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 r = sm.descendingKeySet().iterator();
        k = (Integer)(r.next());
        assertEquals(three, k);
        k = (Integer)(r.next());
        assertEquals(two, k);
        assertFalse(r.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());
        assertTrue(sm.remove(three) != null);
        assertTrue(sm.isEmpty());
        assertEquals(3, map.size());
    }

    public void testSubMapContents2() {
        TreeMap map = map5();
        NavigableMap sm = map.navigableSubMap(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 r = sm.descendingKeySet().iterator();
        k = (Integer)(r.next());
        assertEquals(two, k);
        assertFalse(r.hasNext());
        
        Iterator j = sm.keySet().iterator();
        j.next();
        j.remove();
        assertFalse(map.containsKey(two));
        assertEquals(4, map.size());
        assertEquals(0, sm.size());
        assertTrue(sm.isEmpty());
        assertTrue(sm.remove(three) == null);
        assertEquals(4, map.size());
    }

    /**
     * headMap returns map with keys in requested range
     */
    public void testHeadMapContents() {
        TreeMap map = map5();
        NavigableMap sm = map.navigableHeadMap(four);
        assertTrue(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(one, k);
        k = (Integer)(i.next());
        assertEquals(two, k);
        k = (Integer)(i.next());
        assertEquals(three, k);
        assertFalse(i.hasNext());
        sm.clear();
        assertTrue(sm.isEmpty());
        assertEquals(2, map.size());
        assertEquals(four, map.firstKey());
    }

    /**
     * headMap returns map with keys in requested range
     */
    public void testTailMapContents() {
        TreeMap map = map5();
        NavigableMap sm = map.navigableTailMap(two);
        assertFalse(sm.containsKey(one));
        assertTrue(sm.containsKey(two));
        assertTrue(sm.containsKey(three));
        assertTrue(sm.containsKey(four));
        assertTrue(sm.containsKey(five));
        Iterator i = sm.keySet().iterator();
        Object k;
        k = (Integer)(i.next());
        assertEquals(two, k);
        k = (Integer)(i.next());
        assertEquals(three, k);
        k = (Integer)(i.next());
        assertEquals(four, k);
        k = (Integer)(i.next());
        assertEquals(five, k);
        assertFalse(i.hasNext());
        Iterator r = sm.descendingKeySet().iterator();
        k = (Integer)(r.next());
        assertEquals(five, k);
        k = (Integer)(r.next());
        assertEquals(four, k);
        k = (Integer)(r.next());
        assertEquals(three, k);
        k = (Integer)(r.next());
        assertEquals(two, k);
        assertFalse(r.hasNext());

        Iterator ei = sm.entrySet().iterator();
        Map.Entry e;
        e = (Map.Entry)(ei.next());
        assertEquals(two, e.getKey());
        assertEquals("B", e.getValue());
        e = (Map.Entry)(ei.next());
        assertEquals(three, e.getKey());
        assertEquals("C", e.getValue());
        e = (Map.Entry)(ei.next());
        assertEquals(four, e.getKey());
        assertEquals("D", e.getValue());
        e = (Map.Entry)(ei.next());
        assertEquals(five, e.getKey());
        assertEquals("E", e.getValue());
        assertFalse(i.hasNext());

        NavigableMap ssm = sm.navigableTailMap(four);
        assertEquals(four, ssm.firstKey());
        assertEquals(five, ssm.lastKey());
        assertTrue(ssm.remove(four) != null);
        assertEquals(1, ssm.size());
        assertEquals(3, sm.size());
        assertEquals(4, map.size());
    }
    
}
Revision:	1.2
Committed:	Tue Mar 22 01:30:22 2005 UTC (19 years, 1 month ago) by dl
Branch:	MAIN
Changes since 1.1:	+5 -5 lines
Log Message:	NavigableMap.subMap -> NavigableMap.navigableSubMap, and associated changes
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain, as explained at
4	* http://creativecommons.org/licenses/publicdomain
5	*/
6
7	import junit.framework.*;
8	import java.util.*;
9	import java.util.concurrent.*;
10	import java.io.*;
11
12	public class TreeMapTest extends JSR166TestCase {
13	public static void main(String[] args) {
14	junit.textui.TestRunner.run (suite());
15	}
16	public static Test suite() {
17	return new TestSuite(TreeMapTest.class);
18	}
19
20	/**
21	* Create a map from Integers 1-5 to Strings "A"-"E".
22	*/
23	private static TreeMap map5() {
24	TreeMap map = new TreeMap();
25	assertTrue(map.isEmpty());
26	map.put(one, "A");
27	map.put(five, "E");
28	map.put(three, "C");
29	map.put(two, "B");
30	map.put(four, "D");
31	assertFalse(map.isEmpty());
32	assertEquals(5, map.size());
33	return map;
34	}
35
36	/**
37	* clear removes all pairs
38	*/
39	public void testClear() {
40	TreeMap map = map5();
41	map.clear();
42	assertEquals(map.size(), 0);
43	}
44
45	/**
46	*
47	*/
48	public void testConstructFromSorted() {
49	TreeMap map = map5();
50	TreeMap map2 = new TreeMap(map);
51	assertEquals(map, map2);
52	}
53
54	/**
55	* Maps with same contents are equal
56	*/
57	public void testEquals() {
58	TreeMap map1 = map5();
59	TreeMap map2 = map5();
60	assertEquals(map1, map2);
61	assertEquals(map2, map1);
62	map1.clear();
63	assertFalse(map1.equals(map2));
64	assertFalse(map2.equals(map1));
65	}
66
67	/**
68	* containsKey returns true for contained key
69	*/
70	public void testContainsKey() {
71	TreeMap map = map5();
72	assertTrue(map.containsKey(one));
73	assertFalse(map.containsKey(zero));
74	}
75
76	/**
77	* containsValue returns true for held values
78	*/
79	public void testContainsValue() {
80	TreeMap map = map5();
81	assertTrue(map.containsValue("A"));
82	assertFalse(map.containsValue("Z"));
83	}
84
85	/**
86	* get returns the correct element at the given key,
87	* or null if not present
88	*/
89	public void testGet() {
90	TreeMap map = map5();
91	assertEquals("A", (String)map.get(one));
92	TreeMap empty = new TreeMap();
93	assertNull(empty.get(one));
94	}
95
96	/**
97	* isEmpty is true of empty map and false for non-empty
98	*/
99	public void testIsEmpty() {
100	TreeMap empty = new TreeMap();
101	TreeMap map = map5();
102	assertTrue(empty.isEmpty());
103	assertFalse(map.isEmpty());
104	}
105
106	/**
107	* firstKey returns first key
108	*/
109	public void testFirstKey() {
110	TreeMap map = map5();
111	assertEquals(one, map.firstKey());
112	}
113
114	/**
115	* lastKey returns last key
116	*/
117	public void testLastKey() {
118	TreeMap map = map5();
119	assertEquals(five, map.lastKey());
120	}
121
122
123	/**
124	* keySet.toArray returns contains all keys
125	*/
126	public void testKeySetToArray() {
127	TreeMap map = map5();
128	Set s = map.keySet();
129	Object[] ar = s.toArray();
130	assertTrue(s.containsAll(Arrays.asList(ar)));
131	assertEquals(5, ar.length);
132	ar[0] = m10;
133	assertFalse(s.containsAll(Arrays.asList(ar)));
134	}
135
136	/**
137	* descendingkeySet.toArray returns contains all keys
138	*/
139	public void testDescendingKeySetToArray() {
140	TreeMap map = map5();
141	Set s = map.descendingKeySet();
142	Object[] ar = s.toArray();
143	assertEquals(5, ar.length);
144	assertTrue(s.containsAll(Arrays.asList(ar)));
145	ar[0] = m10;
146	assertFalse(s.containsAll(Arrays.asList(ar)));
147	}
148
149	/**
150	* keySet returns a Set containing all the keys
151	*/
152	public void testKeySet() {
153	TreeMap map = map5();
154	Set s = map.keySet();
155	assertEquals(5, s.size());
156	assertTrue(s.contains(one));
157	assertTrue(s.contains(two));
158	assertTrue(s.contains(three));
159	assertTrue(s.contains(four));
160	assertTrue(s.contains(five));
161	}
162
163	/**
164	* keySet is ordered
165	*/
166	public void testKeySetOrder() {
167	TreeMap map = map5();
168	Set s = map.keySet();
169	Iterator i = s.iterator();
170	Integer last = (Integer)i.next();
171	assertEquals(last, one);
172	while (i.hasNext()) {
173	Integer k = (Integer)i.next();
174	assertTrue(last.compareTo(k) < 0);
175	last = k;
176	}
177	}
178
179	/**
180	* descendingKeySet is ordered
181	*/
182	public void testDescendingKeySetOrder() {
183	TreeMap map = map5();
184	Set s = map.descendingKeySet();
185	Iterator i = s.iterator();
186	Integer last = (Integer)i.next();
187	assertEquals(last, five);
188	while (i.hasNext()) {
189	Integer k = (Integer)i.next();
190	assertTrue(last.compareTo(k) > 0);
191	last = k;
192	}
193	}
194
195	/**
196	* values collection contains all values
197	*/
198	public void testValues() {
199	TreeMap map = map5();
200	Collection s = map.values();
201	assertEquals(5, s.size());
202	assertTrue(s.contains("A"));
203	assertTrue(s.contains("B"));
204	assertTrue(s.contains("C"));
205	assertTrue(s.contains("D"));
206	assertTrue(s.contains("E"));
207	}
208
209	/**
210	* entrySet contains all pairs
211	*/
212	public void testEntrySet() {
213	TreeMap map = map5();
214	Set s = map.entrySet();
215	assertEquals(5, s.size());
216	Iterator it = s.iterator();
217	while (it.hasNext()) {
218	Map.Entry e = (Map.Entry) it.next();
219	assertTrue(
220	(e.getKey().equals(one) && e.getValue().equals("A")) \|\|
221	(e.getKey().equals(two) && e.getValue().equals("B")) \|\|
222	(e.getKey().equals(three) && e.getValue().equals("C")) \|\|
223	(e.getKey().equals(four) && e.getValue().equals("D")) \|\|
224	(e.getKey().equals(five) && e.getValue().equals("E")));
225	}
226	}
227
228	/**
229	* descendingEntrySet contains all pairs
230	*/
231	public void testDescendingEntrySet() {
232	TreeMap map = map5();
233	Set s = map.descendingEntrySet();
234	assertEquals(5, s.size());
235	Iterator it = s.iterator();
236	while (it.hasNext()) {
237	Map.Entry e = (Map.Entry) it.next();
238	assertTrue(
239	(e.getKey().equals(one) && e.getValue().equals("A")) \|\|
240	(e.getKey().equals(two) && e.getValue().equals("B")) \|\|
241	(e.getKey().equals(three) && e.getValue().equals("C")) \|\|
242	(e.getKey().equals(four) && e.getValue().equals("D")) \|\|
243	(e.getKey().equals(five) && e.getValue().equals("E")));
244	}
245	}
246
247	/**
248	* entrySet.toArray contains all entries
249	*/
250	public void testEntrySetToArray() {
251	TreeMap map = map5();
252	Set s = map.entrySet();
253	Object[] ar = s.toArray();
254	assertEquals(5, ar.length);
255	for (int i = 0; i < 5; ++i) {
256	assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
257	assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
258	}
259	}
260
261	/**
262	* descendingEntrySet.toArray contains all entries
263	*/
264	public void testDescendingEntrySetToArray() {
265	TreeMap map = map5();
266	Set s = map.descendingEntrySet();
267	Object[] ar = s.toArray();
268	assertEquals(5, ar.length);
269	for (int i = 0; i < 5; ++i) {
270	assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
271	assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
272	}
273	}
274
275	/**
276	* putAll adds all key-value pairs from the given map
277	*/
278	public void testPutAll() {
279	TreeMap empty = new TreeMap();
280	TreeMap map = map5();
281	empty.putAll(map);
282	assertEquals(5, empty.size());
283	assertTrue(empty.containsKey(one));
284	assertTrue(empty.containsKey(two));
285	assertTrue(empty.containsKey(three));
286	assertTrue(empty.containsKey(four));
287	assertTrue(empty.containsKey(five));
288	}
289
290	/**
291	* remove removes the correct key-value pair from the map
292	*/
293	public void testRemove() {
294	TreeMap map = map5();
295	map.remove(five);
296	assertEquals(4, map.size());
297	assertFalse(map.containsKey(five));
298	}
299
300	/**
301	* lowerEntry returns preceding entry.
302	*/
303	public void testLowerEntry() {
304	TreeMap map = map5();
305	Map.Entry e1 = map.lowerEntry(three);
306	assertEquals(two, e1.getKey());
307
308	Map.Entry e2 = map.lowerEntry(six);
309	assertEquals(five, e2.getKey());
310
311	Map.Entry e3 = map.lowerEntry(one);
312	assertNull(e3);
313
314	Map.Entry e4 = map.lowerEntry(zero);
315	assertNull(e4);
316
317	}
318
319	/**
320	* higherEntry returns next entry.
321	*/
322	public void testHigherEntry() {
323	TreeMap map = map5();
324	Map.Entry e1 = map.higherEntry(three);
325	assertEquals(four, e1.getKey());
326
327	Map.Entry e2 = map.higherEntry(zero);
328	assertEquals(one, e2.getKey());
329
330	Map.Entry e3 = map.higherEntry(five);
331	assertNull(e3);
332
333	Map.Entry e4 = map.higherEntry(six);
334	assertNull(e4);
335
336	}
337
338	/**
339	* floorEntry returns preceding entry.
340	*/
341	public void testFloorEntry() {
342	TreeMap map = map5();
343	Map.Entry e1 = map.floorEntry(three);
344	assertEquals(three, e1.getKey());
345
346	Map.Entry e2 = map.floorEntry(six);
347	assertEquals(five, e2.getKey());
348
349	Map.Entry e3 = map.floorEntry(one);
350	assertEquals(one, e3.getKey());
351
352	Map.Entry e4 = map.floorEntry(zero);
353	assertNull(e4);
354
355	}
356
357	/**
358	* ceilingEntry returns next entry.
359	*/
360	public void testCeilingEntry() {
361	TreeMap map = map5();
362	Map.Entry e1 = map.ceilingEntry(three);
363	assertEquals(three, e1.getKey());
364
365	Map.Entry e2 = map.ceilingEntry(zero);
366	assertEquals(one, e2.getKey());
367
368	Map.Entry e3 = map.ceilingEntry(five);
369	assertEquals(five, e3.getKey());
370
371	Map.Entry e4 = map.ceilingEntry(six);
372	assertNull(e4);
373
374	}
375
376
377	/**
378	* lowerKey returns preceding element
379	*/
380	public void testLowerKey() {
381	TreeMap q = map5();
382	Object e1 = q.lowerKey(three);
383	assertEquals(two, e1);
384
385	Object e2 = q.lowerKey(six);
386	assertEquals(five, e2);
387
388	Object e3 = q.lowerKey(one);
389	assertNull(e3);
390
391	Object e4 = q.lowerKey(zero);
392	assertNull(e4);
393
394	}
395
396	/**
397	* higherKey returns next element
398	*/
399	public void testHigherKey() {
400	TreeMap q = map5();
401	Object e1 = q.higherKey(three);
402	assertEquals(four, e1);
403
404	Object e2 = q.higherKey(zero);
405	assertEquals(one, e2);
406
407	Object e3 = q.higherKey(five);
408	assertNull(e3);
409
410	Object e4 = q.higherKey(six);
411	assertNull(e4);
412
413	}
414
415	/**
416	* floorKey returns preceding element
417	*/
418	public void testFloorKey() {
419	TreeMap q = map5();
420	Object e1 = q.floorKey(three);
421	assertEquals(three, e1);
422
423	Object e2 = q.floorKey(six);
424	assertEquals(five, e2);
425
426	Object e3 = q.floorKey(one);
427	assertEquals(one, e3);
428
429	Object e4 = q.floorKey(zero);
430	assertNull(e4);
431
432	}
433
434	/**
435	* ceilingKey returns next element
436	*/
437	public void testCeilingKey() {
438	TreeMap q = map5();
439	Object e1 = q.ceilingKey(three);
440	assertEquals(three, e1);
441
442	Object e2 = q.ceilingKey(zero);
443	assertEquals(one, e2);
444
445	Object e3 = q.ceilingKey(five);
446	assertEquals(five, e3);
447
448	Object e4 = q.ceilingKey(six);
449	assertNull(e4);
450
451	}
452
453	/**
454	* pollFirstEntry returns entries in order
455	*/
456	public void testPollFirstEntry() {
457	TreeMap map = map5();
458	Map.Entry e = map.pollFirstEntry();
459	assertEquals(one, e.getKey());
460	assertEquals("A", e.getValue());
461	e = map.pollFirstEntry();
462	assertEquals(two, e.getKey());
463	map.put(one, "A");
464	e = map.pollFirstEntry();
465	assertEquals(one, e.getKey());
466	assertEquals("A", e.getValue());
467	e = map.pollFirstEntry();
468	assertEquals(three, e.getKey());
469	map.remove(four);
470	e = map.pollFirstEntry();
471	assertEquals(five, e.getKey());
472	try {
473	e.setValue("A");
474	shouldThrow();
475	} catch (Exception ok) {
476	}
477	e = map.pollFirstEntry();
478	assertNull(e);
479	}
480
481	/**
482	* pollLastEntry returns entries in order
483	*/
484	public void testPollLastEntry() {
485	TreeMap map = map5();
486	Map.Entry e = map.pollLastEntry();
487	assertEquals(five, e.getKey());
488	assertEquals("E", e.getValue());
489	e = map.pollLastEntry();
490	assertEquals(four, e.getKey());
491	map.put(five, "E");
492	e = map.pollLastEntry();
493	assertEquals(five, e.getKey());
494	assertEquals("E", e.getValue());
495	e = map.pollLastEntry();
496	assertEquals(three, e.getKey());
497	map.remove(two);
498	e = map.pollLastEntry();
499	assertEquals(one, e.getKey());
500	try {
501	e.setValue("E");
502	shouldThrow();
503	} catch (Exception ok) {
504	}
505	e = map.pollLastEntry();
506	assertNull(e);
507	}
508
509	/**
510	* size returns the correct values
511	*/
512	public void testSize() {
513	TreeMap map = map5();
514	TreeMap empty = new TreeMap();
515	assertEquals(0, empty.size());
516	assertEquals(5, map.size());
517	}
518
519	/**
520	* toString contains toString of elements
521	*/
522	public void testToString() {
523	TreeMap map = map5();
524	String s = map.toString();
525	for (int i = 1; i <= 5; ++i) {
526	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
527	}
528	}
529
530	// Exception tests
531
532	/**
533	* get(null) of nonempty map throws NPE
534	*/
535	public void testGet_NullPointerException() {
536	try {
537	TreeMap c = map5();
538	c.get(null);
539	shouldThrow();
540	} catch(NullPointerException e){}
541	}
542
543	/**
544	* containsKey(null) of nonempty map throws NPE
545	*/
546	public void testContainsKey_NullPointerException() {
547	try {
548	TreeMap c = map5();
549	c.containsKey(null);
550	shouldThrow();
551	} catch(NullPointerException e){}
552	}
553
554	/**
555	* remove(null) throws NPE for nonempty map
556	*/
557	public void testRemove1_NullPointerException() {
558	try {
559	TreeMap c = new TreeMap();
560	c.put("sadsdf", "asdads");
561	c.remove(null);
562	shouldThrow();
563	} catch(NullPointerException e){}
564	}
565
566	/**
567	* A deserialized map equals original
568	*/
569	public void testSerialization() {
570	TreeMap q = map5();
571
572	try {
573	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
574	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
575	out.writeObject(q);
576	out.close();
577
578	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
579	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
580	TreeMap r = (TreeMap)in.readObject();
581	assertEquals(q.size(), r.size());
582	assertTrue(q.equals(r));
583	assertTrue(r.equals(q));
584	} catch(Exception e){
585	e.printStackTrace();
586	unexpectedException();
587	}
588	}
589
590	/**
591	* subMap returns map with keys in requested range
592	*/
593	public void testSubMapContents() {
594	TreeMap map = map5();
595	NavigableMap sm = map.navigableSubMap(two, four);
596	assertEquals(two, sm.firstKey());
597	assertEquals(three, sm.lastKey());
598	assertEquals(2, sm.size());
599	assertFalse(sm.containsKey(one));
600	assertTrue(sm.containsKey(two));
601	assertTrue(sm.containsKey(three));
602	assertFalse(sm.containsKey(four));
603	assertFalse(sm.containsKey(five));
604	Iterator i = sm.keySet().iterator();
605	Object k;
606	k = (Integer)(i.next());
607	assertEquals(two, k);
608	k = (Integer)(i.next());
609	assertEquals(three, k);
610	assertFalse(i.hasNext());
611	Iterator r = sm.descendingKeySet().iterator();
612	k = (Integer)(r.next());
613	assertEquals(three, k);
614	k = (Integer)(r.next());
615	assertEquals(two, k);
616	assertFalse(r.hasNext());
617
618	Iterator j = sm.keySet().iterator();
619	j.next();
620	j.remove();
621	assertFalse(map.containsKey(two));
622	assertEquals(4, map.size());
623	assertEquals(1, sm.size());
624	assertEquals(three, sm.firstKey());
625	assertEquals(three, sm.lastKey());
626	assertTrue(sm.remove(three) != null);
627	assertTrue(sm.isEmpty());
628	assertEquals(3, map.size());
629	}
630
631	public void testSubMapContents2() {
632	TreeMap map = map5();
633	NavigableMap sm = map.navigableSubMap(two, three);
634	assertEquals(1, sm.size());
635	assertEquals(two, sm.firstKey());
636	assertEquals(two, sm.lastKey());
637	assertFalse(sm.containsKey(one));
638	assertTrue(sm.containsKey(two));
639	assertFalse(sm.containsKey(three));
640	assertFalse(sm.containsKey(four));
641	assertFalse(sm.containsKey(five));
642	Iterator i = sm.keySet().iterator();
643	Object k;
644	k = (Integer)(i.next());
645	assertEquals(two, k);
646	assertFalse(i.hasNext());
647	Iterator r = sm.descendingKeySet().iterator();
648	k = (Integer)(r.next());
649	assertEquals(two, k);
650	assertFalse(r.hasNext());
651
652	Iterator j = sm.keySet().iterator();
653	j.next();
654	j.remove();
655	assertFalse(map.containsKey(two));
656	assertEquals(4, map.size());
657	assertEquals(0, sm.size());
658	assertTrue(sm.isEmpty());
659	assertTrue(sm.remove(three) == null);
660	assertEquals(4, map.size());
661	}
662
663	/**
664	* headMap returns map with keys in requested range
665	*/
666	public void testHeadMapContents() {
667	TreeMap map = map5();
668	NavigableMap sm = map.navigableHeadMap(four);
669	assertTrue(sm.containsKey(one));
670	assertTrue(sm.containsKey(two));
671	assertTrue(sm.containsKey(three));
672	assertFalse(sm.containsKey(four));
673	assertFalse(sm.containsKey(five));
674	Iterator i = sm.keySet().iterator();
675	Object k;
676	k = (Integer)(i.next());
677	assertEquals(one, k);
678	k = (Integer)(i.next());
679	assertEquals(two, k);
680	k = (Integer)(i.next());
681	assertEquals(three, k);
682	assertFalse(i.hasNext());
683	sm.clear();
684	assertTrue(sm.isEmpty());
685	assertEquals(2, map.size());
686	assertEquals(four, map.firstKey());
687	}
688
689	/**
690	* headMap returns map with keys in requested range
691	*/
692	public void testTailMapContents() {
693	TreeMap map = map5();
694	NavigableMap sm = map.navigableTailMap(two);
695	assertFalse(sm.containsKey(one));
696	assertTrue(sm.containsKey(two));
697	assertTrue(sm.containsKey(three));
698	assertTrue(sm.containsKey(four));
699	assertTrue(sm.containsKey(five));
700	Iterator i = sm.keySet().iterator();
701	Object k;
702	k = (Integer)(i.next());
703	assertEquals(two, k);
704	k = (Integer)(i.next());
705	assertEquals(three, k);
706	k = (Integer)(i.next());
707	assertEquals(four, k);
708	k = (Integer)(i.next());
709	assertEquals(five, k);
710	assertFalse(i.hasNext());
711	Iterator r = sm.descendingKeySet().iterator();
712	k = (Integer)(r.next());
713	assertEquals(five, k);
714	k = (Integer)(r.next());
715	assertEquals(four, k);
716	k = (Integer)(r.next());
717	assertEquals(three, k);
718	k = (Integer)(r.next());
719	assertEquals(two, k);
720	assertFalse(r.hasNext());
721
722	Iterator ei = sm.entrySet().iterator();
723	Map.Entry e;
724	e = (Map.Entry)(ei.next());
725	assertEquals(two, e.getKey());
726	assertEquals("B", e.getValue());
727	e = (Map.Entry)(ei.next());
728	assertEquals(three, e.getKey());
729	assertEquals("C", e.getValue());
730	e = (Map.Entry)(ei.next());
731	assertEquals(four, e.getKey());
732	assertEquals("D", e.getValue());
733	e = (Map.Entry)(ei.next());
734	assertEquals(five, e.getKey());
735	assertEquals("E", e.getValue());
736	assertFalse(i.hasNext());
737
738	NavigableMap ssm = sm.navigableTailMap(four);
739	assertEquals(four, ssm.firstKey());
740	assertEquals(five, ssm.lastKey());
741	assertTrue(ssm.remove(four) != null);
742	assertEquals(1, ssm.size());
743	assertEquals(3, sm.size());
744	assertEquals(4, map.size());
745	}
746
747	}