ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/tck/TreeMapTest.java

Comparing jsr166/src/test/tck/TreeMapTest.java (file contents):
Revision 1.1 by dl, Tue Dec 28 16:15:59 2004 UTC vs.
Revision 1.30 by jsr166, Sat Feb 28 18:33:42 2015 UTC

#	Line 1 | Line 1
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
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7	<	import junit.framework.*;
8	<	import java.util.*;
9	<	import java.util.concurrent.*;
10	<	import java.io.*;
7	>	import java.util.Arrays;
8	>	import java.util.BitSet;
9	>	import java.util.Collection;
10	>	import java.util.Iterator;
11	>	import java.util.Map;
12	>	import java.util.NavigableMap;
13	>	import java.util.NavigableSet;
14	>	import java.util.NoSuchElementException;
15	>	import java.util.Random;
16	>	import java.util.Set;
17	>	import java.util.TreeMap;
18	>
19	>	import junit.framework.Test;
20	>	import junit.framework.TestSuite;
21
22		public class TreeMapTest extends JSR166TestCase {
23		public static void main(String[] args) {
24	<	junit.textui.TestRunner.run (suite());
24	>	junit.textui.TestRunner.run(suite());
25		}
26		public static Test suite() {
27	<	return new TestSuite(TreeMapTest.class);
27	>	return new TestSuite(TreeMapTest.class);
28		}
29
30		/**
31	<	* Create a map from Integers 1-5 to Strings "A"-"E".
31	>	* Returns a new map from Integers 1-5 to Strings "A"-"E".
32		*/
33	<	private static TreeMap map5() {
34	<	TreeMap map = new TreeMap();
33	>	private static TreeMap map5() {
34	>	TreeMap map = new TreeMap();
35		assertTrue(map.isEmpty());
36	<	map.put(one, "A");
37	<	map.put(five, "E");
38	<	map.put(three, "C");
39	<	map.put(two, "B");
40	<	map.put(four, "D");
36	>	map.put(one, "A");
37	>	map.put(five, "E");
38	>	map.put(three, "C");
39	>	map.put(two, "B");
40	>	map.put(four, "D");
41		assertFalse(map.isEmpty());
42		assertEquals(5, map.size());
43	<	return map;
43	>	return map;
44		}
45
46		/**
47	<	*  clear removes all pairs
47	>	* clear removes all pairs
48		*/
49		public void testClear() {
50		TreeMap map = map5();
51	<	map.clear();
52	<	assertEquals(map.size(), 0);
51	>	map.clear();
52	>	assertEquals(0, map.size());
53		}
54
55		/**
56	<	*
56	>	* copy constructor creates map equal to source map
57		*/
58		public void testConstructFromSorted() {
59		TreeMap map = map5();
#	Line 52 | Line 62 | public class TreeMapTest extends JSR166T
62		}
63
64		/**
65	<	*  Maps with same contents are equal
65	>	* Maps with same contents are equal
66		*/
67		public void testEquals() {
68		TreeMap map1 = map5();
69		TreeMap map2 = map5();
70		assertEquals(map1, map2);
71		assertEquals(map2, map1);
72	<	map1.clear();
72	>	map1.clear();
73		assertFalse(map1.equals(map2));
74		assertFalse(map2.equals(map1));
75		}
76
77		/**
78	<	*  containsKey returns true for contained key
78	>	* containsKey returns true for contained key
79		*/
80		public void testContainsKey() {
81		TreeMap map = map5();
82	<	assertTrue(map.containsKey(one));
82	>	assertTrue(map.containsKey(one));
83		assertFalse(map.containsKey(zero));
84		}
85
86		/**
87	<	*  containsValue returns true for held values
87	>	* containsValue returns true for held values
88		*/
89		public void testContainsValue() {
90		TreeMap map = map5();
91	<	assertTrue(map.containsValue("A"));
91	>	assertTrue(map.containsValue("A"));
92		assertFalse(map.containsValue("Z"));
93		}
94
95		/**
96	<	*  get returns the correct element at the given key,
97	<	*  or null if not present
96	>	* get returns the correct element at the given key,
97	>	* or null if not present
98		*/
99		public void testGet() {
100		TreeMap map = map5();
101	<	assertEquals("A", (String)map.get(one));
101	>	assertEquals("A", (String)map.get(one));
102		TreeMap empty = new TreeMap();
103		assertNull(empty.get(one));
104		}
105
106		/**
107	<	*  isEmpty is true of empty map and false for non-empty
107	>	* isEmpty is true of empty map and false for non-empty
108		*/
109		public void testIsEmpty() {
110		TreeMap empty = new TreeMap();
111		TreeMap map = map5();
112	<	assertTrue(empty.isEmpty());
112	>	assertTrue(empty.isEmpty());
113		assertFalse(map.isEmpty());
114		}
115
116		/**
117	<	*   firstKey returns first key
117	>	* firstKey returns first key
118		*/
119		public void testFirstKey() {
120		TreeMap map = map5();
121	<	assertEquals(one, map.firstKey());
121	>	assertEquals(one, map.firstKey());
122		}
123
124		/**
125	<	*   lastKey returns last key
125	>	* lastKey returns last key
126		*/
127		public void testLastKey() {
128		TreeMap map = map5();
129	<	assertEquals(five, map.lastKey());
129	>	assertEquals(five, map.lastKey());
130		}
131
122	–
132		/**
133	<	*  keySet.toArray returns contains all keys
133	>	* keySet.toArray returns contains all keys
134		*/
135		public void testKeySetToArray() {
136		TreeMap map = map5();
137	<	Set s = map.keySet();
137	>	Set s = map.keySet();
138		Object[] ar = s.toArray();
139		assertTrue(s.containsAll(Arrays.asList(ar)));
140	<	assertEquals(5, ar.length);
140	>	assertEquals(5, ar.length);
141		ar[0] = m10;
142		assertFalse(s.containsAll(Arrays.asList(ar)));
143		}
144
145		/**
146	<	*  descendingkeySet.toArray returns contains all keys
146	>	* descendingkeySet.toArray returns contains all keys
147		*/
148		public void testDescendingKeySetToArray() {
149		TreeMap map = map5();
150	<	Set s = map.descendingKeySet();
150	>	Set s = map.descendingKeySet();
151		Object[] ar = s.toArray();
152	<	assertEquals(5, ar.length);
152	>	assertEquals(5, ar.length);
153		assertTrue(s.containsAll(Arrays.asList(ar)));
154		ar[0] = m10;
155		assertFalse(s.containsAll(Arrays.asList(ar)));
156		}
157
158		/**
159	<	*   keySet returns a Set containing all the keys
159	>	* keySet returns a Set containing all the keys
160		*/
161		public void testKeySet() {
162		TreeMap map = map5();
163	<	Set s = map.keySet();
164	<	assertEquals(5, s.size());
165	<	assertTrue(s.contains(one));
166	<	assertTrue(s.contains(two));
167	<	assertTrue(s.contains(three));
168	<	assertTrue(s.contains(four));
169	<	assertTrue(s.contains(five));
163	>	Set s = map.keySet();
164	>	assertEquals(5, s.size());
165	>	assertTrue(s.contains(one));
166	>	assertTrue(s.contains(two));
167	>	assertTrue(s.contains(three));
168	>	assertTrue(s.contains(four));
169	>	assertTrue(s.contains(five));
170		}
171
172		/**
173	<	*   keySet is ordered
173	>	* keySet is ordered
174		*/
175		public void testKeySetOrder() {
176		TreeMap map = map5();
177	<	Set s = map.keySet();
177	>	Set s = map.keySet();
178		Iterator i = s.iterator();
179		Integer last = (Integer)i.next();
180		assertEquals(last, one);
181	+	int count = 1;
182		while (i.hasNext()) {
183		Integer k = (Integer)i.next();
184		assertTrue(last.compareTo(k) < 0);
185		last = k;
186	+	++count;
187	+	}
188	+	assertEquals(5, count);
189	+	}
190	+
191	+	/**
192	+	* descending iterator of key set is inverse ordered
193	+	*/
194	+	public void testKeySetDescendingIteratorOrder() {
195	+	TreeMap map = map5();
196	+	NavigableSet s = map.navigableKeySet();
197	+	Iterator i = s.descendingIterator();
198	+	Integer last = (Integer)i.next();
199	+	assertEquals(last, five);
200	+	int count = 1;
201	+	while (i.hasNext()) {
202	+	Integer k = (Integer)i.next();
203	+	assertTrue(last.compareTo(k) > 0);
204	+	last = k;
205	+	++count;
206		}
207	+	assertEquals(5, count);
208		}
209
210		/**
211	<	*   descendingKeySet is ordered
211	>	* descendingKeySet is ordered
212		*/
213		public void testDescendingKeySetOrder() {
214		TreeMap map = map5();
215	<	Set s = map.descendingKeySet();
215	>	Set s = map.descendingKeySet();
216		Iterator i = s.iterator();
217		Integer last = (Integer)i.next();
218		assertEquals(last, five);
219	+	int count = 1;
220		while (i.hasNext()) {
221		Integer k = (Integer)i.next();
222		assertTrue(last.compareTo(k) > 0);
223		last = k;
224	+	++count;
225		}
226	+	assertEquals(5, count);
227	+	}
228	+
229	+	/**
230	+	* descending iterator of descendingKeySet is ordered
231	+	*/
232	+	public void testDescendingKeySetDescendingIteratorOrder() {
233	+	TreeMap map = map5();
234	+	NavigableSet s = map.descendingKeySet();
235	+	Iterator i = s.descendingIterator();
236	+	Integer last = (Integer)i.next();
237	+	assertEquals(last, one);
238	+	int count = 1;
239	+	while (i.hasNext()) {
240	+	Integer k = (Integer)i.next();
241	+	assertTrue(last.compareTo(k) < 0);
242	+	last = k;
243	+	++count;
244	+	}
245	+	assertEquals(5, count);
246		}
247
248		/**
#	Line 197 | Line 250 | public class TreeMapTest extends JSR166T
250		*/
251		public void testValues() {
252		TreeMap map = map5();
253	<	Collection s = map.values();
254	<	assertEquals(5, s.size());
255	<	assertTrue(s.contains("A"));
256	<	assertTrue(s.contains("B"));
257	<	assertTrue(s.contains("C"));
258	<	assertTrue(s.contains("D"));
259	<	assertTrue(s.contains("E"));
253	>	Collection s = map.values();
254	>	assertEquals(5, s.size());
255	>	assertTrue(s.contains("A"));
256	>	assertTrue(s.contains("B"));
257	>	assertTrue(s.contains("C"));
258	>	assertTrue(s.contains("D"));
259	>	assertTrue(s.contains("E"));
260		}
261
262		/**
#	Line 211 | Line 264 | public class TreeMapTest extends JSR166T
264		*/
265		public void testEntrySet() {
266		TreeMap map = map5();
267	<	Set s = map.entrySet();
268	<	assertEquals(5, s.size());
267	>	Set s = map.entrySet();
268	>	assertEquals(5, s.size());
269		Iterator it = s.iterator();
270		while (it.hasNext()) {
271		Map.Entry e = (Map.Entry) it.next();
272	<	assertTrue(
272	>	assertTrue(
273		(e.getKey().equals(one) && e.getValue().equals("A")) ||
274		(e.getKey().equals(two) && e.getValue().equals("B")) ||
275		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 230 | Line 283 | public class TreeMapTest extends JSR166T
283		*/
284		public void testDescendingEntrySet() {
285		TreeMap map = map5();
286	<	Set s = map.descendingEntrySet();
287	<	assertEquals(5, s.size());
286	>	Set s = map.descendingMap().entrySet();
287	>	assertEquals(5, s.size());
288		Iterator it = s.iterator();
289		while (it.hasNext()) {
290		Map.Entry e = (Map.Entry) it.next();
291	<	assertTrue(
291	>	assertTrue(
292		(e.getKey().equals(one) && e.getValue().equals("A")) ||
293		(e.getKey().equals(two) && e.getValue().equals("B")) ||
294		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 245 | Line 298 | public class TreeMapTest extends JSR166T
298		}
299
300		/**
301	<	*  entrySet.toArray contains all entries
301	>	* entrySet.toArray contains all entries
302		*/
303		public void testEntrySetToArray() {
304		TreeMap map = map5();
305	<	Set s = map.entrySet();
305	>	Set s = map.entrySet();
306		Object[] ar = s.toArray();
307		assertEquals(5, ar.length);
308		for (int i = 0; i < 5; ++i) {
#	Line 259 | Line 312 | public class TreeMapTest extends JSR166T
312		}
313
314		/**
315	<	*  descendingEntrySet.toArray contains all entries
315	>	* descendingEntrySet.toArray contains all entries
316		*/
317		public void testDescendingEntrySetToArray() {
318		TreeMap map = map5();
319	<	Set s = map.descendingEntrySet();
319	>	Set s = map.descendingMap().entrySet();
320		Object[] ar = s.toArray();
321		assertEquals(5, ar.length);
322		for (int i = 0; i < 5; ++i) {
#	Line 273 | Line 326 | public class TreeMapTest extends JSR166T
326		}
327
328		/**
329	<	*   putAll  adds all key-value pairs from the given map
329	>	* putAll adds all key-value pairs from the given map
330		*/
331		public void testPutAll() {
332		TreeMap empty = new TreeMap();
333		TreeMap map = map5();
334	<	empty.putAll(map);
335	<	assertEquals(5, empty.size());
336	<	assertTrue(empty.containsKey(one));
337	<	assertTrue(empty.containsKey(two));
338	<	assertTrue(empty.containsKey(three));
339	<	assertTrue(empty.containsKey(four));
340	<	assertTrue(empty.containsKey(five));
334	>	empty.putAll(map);
335	>	assertEquals(5, empty.size());
336	>	assertTrue(empty.containsKey(one));
337	>	assertTrue(empty.containsKey(two));
338	>	assertTrue(empty.containsKey(three));
339	>	assertTrue(empty.containsKey(four));
340	>	assertTrue(empty.containsKey(five));
341		}
342
343		/**
344	<	*   remove removes the correct key-value pair from the map
344	>	* remove removes the correct key-value pair from the map
345		*/
346		public void testRemove() {
347		TreeMap map = map5();
348	<	map.remove(five);
349	<	assertEquals(4, map.size());
350	<	assertFalse(map.containsKey(five));
348	>	map.remove(five);
349	>	assertEquals(4, map.size());
350	>	assertFalse(map.containsKey(five));
351		}
352
353		/**
#	Line 313 | Line 366 | public class TreeMapTest extends JSR166T
366
367		Map.Entry e4 = map.lowerEntry(zero);
368		assertNull(e4);
316	–
369		}
370
371		/**
#	Line 332 | Line 384 | public class TreeMapTest extends JSR166T
384
385		Map.Entry e4 = map.higherEntry(six);
386		assertNull(e4);
335	–
387		}
388
389		/**
#	Line 351 | Line 402 | public class TreeMapTest extends JSR166T
402
403		Map.Entry e4 = map.floorEntry(zero);
404		assertNull(e4);
354	–
405		}
406
407		/**
#	Line 370 | Line 420 | public class TreeMapTest extends JSR166T
420
421		Map.Entry e4 = map.ceilingEntry(six);
422		assertNull(e4);
373	–
423		}
424
376	–
425		/**
426		* lowerKey returns preceding element
427		*/
#	Line 390 | Line 438 | public class TreeMapTest extends JSR166T
438
439		Object e4 = q.lowerKey(zero);
440		assertNull(e4);
393	–
441		}
442
443		/**
#	Line 409 | Line 456 | public class TreeMapTest extends JSR166T
456
457		Object e4 = q.higherKey(six);
458		assertNull(e4);
412	–
459		}
460
461		/**
#	Line 428 | Line 474 | public class TreeMapTest extends JSR166T
474
475		Object e4 = q.floorKey(zero);
476		assertNull(e4);
431	–
477		}
478
479		/**
#	Line 447 | Line 492 | public class TreeMapTest extends JSR166T
492
493		Object e4 = q.ceilingKey(six);
494		assertNull(e4);
450	–
495		}
496
497		/**
#	Line 472 | Line 516 | public class TreeMapTest extends JSR166T
516		try {
517		e.setValue("A");
518		shouldThrow();
519	<	} catch (Exception ok) {
476	<	}
519	>	} catch (UnsupportedOperationException success) {}
520		e = map.pollFirstEntry();
521		assertNull(e);
522		}
#	Line 500 | Line 543 | public class TreeMapTest extends JSR166T
543		try {
544		e.setValue("E");
545		shouldThrow();
546	<	} catch (Exception ok) {
504	<	}
546	>	} catch (UnsupportedOperationException success) {}
547		e = map.pollLastEntry();
548		assertNull(e);
549		}
550
551		/**
552	<	*   size returns the correct values
552	>	* size returns the correct values
553		*/
554		public void testSize() {
555		TreeMap map = map5();
556		TreeMap empty = new TreeMap();
557	<	assertEquals(0, empty.size());
558	<	assertEquals(5, map.size());
557	>	assertEquals(0, empty.size());
558	>	assertEquals(5, map.size());
559		}
560
561		/**
#	Line 523 | Line 565 | public class TreeMapTest extends JSR166T
565		TreeMap map = map5();
566		String s = map.toString();
567		for (int i = 1; i <= 5; ++i) {
568	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
568	>	assertTrue(s.contains(String.valueOf(i)));
569		}
570	<	}
570	>	}
571
572		// Exception tests
573
#	Line 533 | Line 575 | public class TreeMapTest extends JSR166T
575		* get(null) of nonempty map throws NPE
576		*/
577		public void testGet_NullPointerException() {
578	+	TreeMap c = map5();
579		try {
537	–	TreeMap c = map5();
580		c.get(null);
581		shouldThrow();
582	<	} catch(NullPointerException e){}
582	>	} catch (NullPointerException success) {}
583		}
584
585		/**
586		* containsKey(null) of nonempty map throws NPE
587		*/
588		public void testContainsKey_NullPointerException() {
589	+	TreeMap c = map5();
590		try {
548	–	TreeMap c = map5();
591		c.containsKey(null);
592		shouldThrow();
593	<	} catch(NullPointerException e){}
593	>	} catch (NullPointerException success) {}
594		}
595
596		/**
597		* remove(null) throws NPE for nonempty map
598		*/
599		public void testRemove1_NullPointerException() {
600	+	TreeMap c = new TreeMap();
601	+	c.put("sadsdf", "asdads");
602		try {
559	–	TreeMap c = new TreeMap();
560	–	c.put("sadsdf", "asdads");
603		c.remove(null);
604		shouldThrow();
605	<	} catch(NullPointerException e){}
605	>	} catch (NullPointerException success) {}
606		}
607
608		/**
609		* A deserialized map equals original
610		*/
611	<	public void testSerialization() {
612	<	TreeMap q = map5();
613	<
614	<	try {
615	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
616	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
617	<	out.writeObject(q);
618	<	out.close();
619	<
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	<	}
611	>	public void testSerialization() throws Exception {
612	>	NavigableMap x = map5();
613	>	NavigableMap y = serialClone(x);
614	>
615	>	assertNotSame(x, y);
616	>	assertEquals(x.size(), y.size());
617	>	assertEquals(x.toString(), y.toString());
618	>	assertEquals(x, y);
619	>	assertEquals(y, x);
620		}
621
622		/**
#	Line 592 | Line 624 | public class TreeMapTest extends JSR166T
624		*/
625		public void testSubMapContents() {
626		TreeMap map = map5();
627	<	NavigableMap sm = map.subMap(two, four);
627	>	NavigableMap sm = map.subMap(two, true, four, false);
628		assertEquals(two, sm.firstKey());
629		assertEquals(three, sm.lastKey());
630		assertEquals(2, sm.size());
#	Line 614 | Line 646 | public class TreeMapTest extends JSR166T
646		k = (Integer)(r.next());
647		assertEquals(two, k);
648		assertFalse(r.hasNext());
649	<
649	>
650		Iterator j = sm.keySet().iterator();
651		j.next();
652		j.remove();
#	Line 623 | Line 655 | public class TreeMapTest extends JSR166T
655		assertEquals(1, sm.size());
656		assertEquals(three, sm.firstKey());
657		assertEquals(three, sm.lastKey());
658	<	assertTrue(sm.remove(three) != null);
658	>	assertEquals("C", sm.remove(three));
659		assertTrue(sm.isEmpty());
660		assertEquals(3, map.size());
661		}
662
663		public void testSubMapContents2() {
664		TreeMap map = map5();
665	<	NavigableMap sm = map.subMap(two, three);
665	>	NavigableMap sm = map.subMap(two, true, three, false);
666		assertEquals(1, sm.size());
667		assertEquals(two, sm.firstKey());
668		assertEquals(two, sm.lastKey());
#	Line 648 | Line 680 | public class TreeMapTest extends JSR166T
680		k = (Integer)(r.next());
681		assertEquals(two, k);
682		assertFalse(r.hasNext());
683	<
683	>
684		Iterator j = sm.keySet().iterator();
685		j.next();
686		j.remove();
#	Line 656 | Line 688 | public class TreeMapTest extends JSR166T
688		assertEquals(4, map.size());
689		assertEquals(0, sm.size());
690		assertTrue(sm.isEmpty());
691	<	assertTrue(sm.remove(three) == null);
691	>	assertSame(sm.remove(three), null);
692		assertEquals(4, map.size());
693		}
694
#	Line 665 | Line 697 | public class TreeMapTest extends JSR166T
697		*/
698		public void testHeadMapContents() {
699		TreeMap map = map5();
700	<	NavigableMap sm = map.headMap(four);
700	>	NavigableMap sm = map.headMap(four, false);
701		assertTrue(sm.containsKey(one));
702		assertTrue(sm.containsKey(two));
703		assertTrue(sm.containsKey(three));
#	Line 691 | Line 723 | public class TreeMapTest extends JSR166T
723		*/
724		public void testTailMapContents() {
725		TreeMap map = map5();
726	<	NavigableMap sm = map.tailMap(two);
726	>	NavigableMap sm = map.tailMap(two, true);
727		assertFalse(sm.containsKey(one));
728		assertTrue(sm.containsKey(two));
729		assertTrue(sm.containsKey(three));
#	Line 735 | Line 767 | public class TreeMapTest extends JSR166T
767		assertEquals("E", e.getValue());
768		assertFalse(i.hasNext());
769
770	<	NavigableMap ssm = sm.tailMap(four);
770	>	NavigableMap ssm = sm.tailMap(four, true);
771		assertEquals(four, ssm.firstKey());
772		assertEquals(five, ssm.lastKey());
773	<	assertTrue(ssm.remove(four) != null);
773	>	assertEquals("D", ssm.remove(four));
774		assertEquals(1, ssm.size());
775		assertEquals(3, sm.size());
776		assertEquals(4, map.size());
777		}
778	<
778	>
779	>	Random rnd = new Random(666);
780	>	BitSet bs;
781	>
782	>	/**
783	>	* Submaps of submaps subdivide correctly
784	>	*/
785	>	public void testRecursiveSubMaps() throws Exception {
786	>	int mapSize = expensiveTests ? 1000 : 100;
787	>	Class cl = TreeMap.class;
788	>	NavigableMap<Integer, Integer> map = newMap(cl);
789	>	bs = new BitSet(mapSize);
790	>
791	>	populate(map, mapSize);
792	>	check(map,                 0, mapSize - 1, true);
793	>	check(map.descendingMap(), 0, mapSize - 1, false);
794	>
795	>	mutateMap(map, 0, mapSize - 1);
796	>	check(map,                 0, mapSize - 1, true);
797	>	check(map.descendingMap(), 0, mapSize - 1, false);
798	>
799	>	bashSubMap(map.subMap(0, true, mapSize, false),
800	>	0, mapSize - 1, true);
801	>	}
802	>
803	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
804	>	NavigableMap<Integer, Integer> result
805	>	= (NavigableMap<Integer, Integer>) cl.newInstance();
806	>	assertEquals(0, result.size());
807	>	assertFalse(result.keySet().iterator().hasNext());
808	>	return result;
809	>	}
810	>
811	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
812	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
813	>	int key = rnd.nextInt(limit);
814	>	put(map, key);
815	>	}
816	>	}
817	>
818	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
819	>	int size = map.size();
820	>	int rangeSize = max - min + 1;
821	>
822	>	// Remove a bunch of entries directly
823	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
824	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
825	>	}
826	>
827	>	// Remove a bunch of entries with iterator
828	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
829	>	if (rnd.nextBoolean()) {
830	>	bs.clear(it.next());
831	>	it.remove();
832	>	}
833	>	}
834	>
835	>	// Add entries till we're back to original size
836	>	while (map.size() < size) {
837	>	int key = min + rnd.nextInt(rangeSize);
838	>	assertTrue(key >= min && key <= max);
839	>	put(map, key);
840	>	}
841	>	}
842	>
843	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
844	>	int size = map.size();
845	>	int rangeSize = max - min + 1;
846	>
847	>	// Remove a bunch of entries directly
848	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
849	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
850	>	}
851	>
852	>	// Remove a bunch of entries with iterator
853	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
854	>	if (rnd.nextBoolean()) {
855	>	bs.clear(it.next());
856	>	it.remove();
857	>	}
858	>	}
859	>
860	>	// Add entries till we're back to original size
861	>	while (map.size() < size) {
862	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
863	>	if (key >= min && key <= max) {
864	>	put(map, key);
865	>	} else {
866	>	try {
867	>	map.put(key, 2 * key);
868	>	shouldThrow();
869	>	} catch (IllegalArgumentException success) {}
870	>	}
871	>	}
872	>	}
873	>
874	>	void put(NavigableMap<Integer, Integer> map, int key) {
875	>	if (map.put(key, 2 * key) == null)
876	>	bs.set(key);
877	>	}
878	>
879	>	void remove(NavigableMap<Integer, Integer> map, int key) {
880	>	if (map.remove(key) != null)
881	>	bs.clear(key);
882	>	}
883	>
884	>	void bashSubMap(NavigableMap<Integer, Integer> map,
885	>	int min, int max, boolean ascending) {
886	>	check(map, min, max, ascending);
887	>	check(map.descendingMap(), min, max, !ascending);
888	>
889	>	mutateSubMap(map, min, max);
890	>	check(map, min, max, ascending);
891	>	check(map.descendingMap(), min, max, !ascending);
892	>
893	>	// Recurse
894	>	if (max - min < 2)
895	>	return;
896	>	int midPoint = (min + max) / 2;
897	>
898	>	// headMap - pick direction and endpoint inclusion randomly
899	>	boolean incl = rnd.nextBoolean();
900	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
901	>	if (ascending) {
902	>	if (rnd.nextBoolean())
903	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
904	>	else
905	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
906	>	false);
907	>	} else {
908	>	if (rnd.nextBoolean())
909	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
910	>	else
911	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
912	>	true);
913	>	}
914	>
915	>	// tailMap - pick direction and endpoint inclusion randomly
916	>	incl = rnd.nextBoolean();
917	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
918	>	if (ascending) {
919	>	if (rnd.nextBoolean())
920	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
921	>	else
922	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
923	>	false);
924	>	} else {
925	>	if (rnd.nextBoolean()) {
926	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
927	>	} else {
928	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
929	>	true);
930	>	}
931	>	}
932	>
933	>	// subMap - pick direction and endpoint inclusion randomly
934	>	int rangeSize = max - min + 1;
935	>	int[] endpoints = new int[2];
936	>	endpoints[0] = min + rnd.nextInt(rangeSize);
937	>	endpoints[1] = min + rnd.nextInt(rangeSize);
938	>	Arrays.sort(endpoints);
939	>	boolean lowIncl = rnd.nextBoolean();
940	>	boolean highIncl = rnd.nextBoolean();
941	>	if (ascending) {
942	>	NavigableMap<Integer,Integer> sm = map.subMap(
943	>	endpoints[0], lowIncl, endpoints[1], highIncl);
944	>	if (rnd.nextBoolean())
945	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
946	>	endpoints[1] - (highIncl ? 0 : 1), true);
947	>	else
948	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
949	>	endpoints[1] - (highIncl ? 0 : 1), false);
950	>	} else {
951	>	NavigableMap<Integer,Integer> sm = map.subMap(
952	>	endpoints[1], highIncl, endpoints[0], lowIncl);
953	>	if (rnd.nextBoolean())
954	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
955	>	endpoints[1] - (highIncl ? 0 : 1), false);
956	>	else
957	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
958	>	endpoints[1] - (highIncl ? 0 : 1), true);
959	>	}
960	>	}
961	>
962	>	/**
963	>	* min and max are both inclusive.  If max < min, interval is empty.
964	>	*/
965	>	void check(NavigableMap<Integer, Integer> map,
966	>	final int min, final int max, final boolean ascending) {
967	>	class ReferenceSet {
968	>	int lower(int key) {
969	>	return ascending ? lowerAscending(key) : higherAscending(key);
970	>	}
971	>	int floor(int key) {
972	>	return ascending ? floorAscending(key) : ceilingAscending(key);
973	>	}
974	>	int ceiling(int key) {
975	>	return ascending ? ceilingAscending(key) : floorAscending(key);
976	>	}
977	>	int higher(int key) {
978	>	return ascending ? higherAscending(key) : lowerAscending(key);
979	>	}
980	>	int first() {
981	>	return ascending ? firstAscending() : lastAscending();
982	>	}
983	>	int last() {
984	>	return ascending ? lastAscending() : firstAscending();
985	>	}
986	>	int lowerAscending(int key) {
987	>	return floorAscending(key - 1);
988	>	}
989	>	int floorAscending(int key) {
990	>	if (key < min)
991	>	return -1;
992	>	else if (key > max)
993	>	key = max;
994	>
995	>	// BitSet should support this! Test would run much faster
996	>	while (key >= min) {
997	>	if (bs.get(key))
998	>	return key;
999	>	key--;
1000	>	}
1001	>	return -1;
1002	>	}
1003	>	int ceilingAscending(int key) {
1004	>	if (key < min)
1005	>	key = min;
1006	>	else if (key > max)
1007	>	return -1;
1008	>	int result = bs.nextSetBit(key);
1009	>	return result > max ? -1 : result;
1010	>	}
1011	>	int higherAscending(int key) {
1012	>	return ceilingAscending(key + 1);
1013	>	}
1014	>	private int firstAscending() {
1015	>	int result = ceilingAscending(min);
1016	>	return result > max ? -1 : result;
1017	>	}
1018	>	private int lastAscending() {
1019	>	int result = floorAscending(max);
1020	>	return result < min ? -1 : result;
1021	>	}
1022	>	}
1023	>	ReferenceSet rs = new ReferenceSet();
1024	>
1025	>	// Test contents using containsKey
1026	>	int size = 0;
1027	>	for (int i = min; i <= max; i++) {
1028	>	boolean bsContainsI = bs.get(i);
1029	>	assertEquals(bsContainsI, map.containsKey(i));
1030	>	if (bsContainsI)
1031	>	size++;
1032	>	}
1033	>	assertEquals(size, map.size());
1034	>
1035	>	// Test contents using contains keySet iterator
1036	>	int size2 = 0;
1037	>	int previousKey = -1;
1038	>	for (int key : map.keySet()) {
1039	>	assertTrue(bs.get(key));
1040	>	size2++;
1041	>	assertTrue(previousKey < 0 ||
1042	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1043	>	previousKey = key;
1044	>	}
1045	>	assertEquals(size2, size);
1046	>
1047	>	// Test navigation ops
1048	>	for (int key = min - 1; key <= max + 1; key++) {
1049	>	assertEq(map.lowerKey(key), rs.lower(key));
1050	>	assertEq(map.floorKey(key), rs.floor(key));
1051	>	assertEq(map.higherKey(key), rs.higher(key));
1052	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1053	>	}
1054	>
1055	>	// Test extrema
1056	>	if (map.size() != 0) {
1057	>	assertEq(map.firstKey(), rs.first());
1058	>	assertEq(map.lastKey(), rs.last());
1059	>	} else {
1060	>	assertEq(rs.first(), -1);
1061	>	assertEq(rs.last(),  -1);
1062	>	try {
1063	>	map.firstKey();
1064	>	shouldThrow();
1065	>	} catch (NoSuchElementException success) {}
1066	>	try {
1067	>	map.lastKey();
1068	>	shouldThrow();
1069	>	} catch (NoSuchElementException success) {}
1070	>	}
1071	>	}
1072	>
1073	>	static void assertEq(Integer i, int j) {
1074	>	if (i == null)
1075	>	assertEquals(j, -1);
1076	>	else
1077	>	assertEquals((int) i, j);
1078	>	}
1079	>
1080	>	static boolean eq(Integer i, int j) {
1081	>	return i == null ? j == -1 : i == j;
1082	>	}
1083	>
1084		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines