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.34 by jsr166, Wed Aug 23 05:33:00 2017 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
21		public class TreeMapTest extends JSR166TestCase {
22		public static void main(String[] args) {
23	<	junit.textui.TestRunner.run (suite());
23	>	main(suite(), args);
24		}
25		public static Test suite() {
26	<	return new TestSuite(TreeMapTest.class);
26	>	class Implementation implements MapImplementation {
27	>	public Class<?> klazz() { return TreeMap.class; }
28	>	public Map emptyMap() { return new TreeMap(); }
29	>	public Object makeKey(int i) { return i; }
30	>	public Object makeValue(int i) { return i; }
31	>	public boolean isConcurrent() { return false; }
32	>	public boolean permitsNullKeys() { return false; }
33	>	public boolean permitsNullValues() { return true; }
34	>	public boolean supportsSetValue() { return true; }
35	>	}
36	>	return newTestSuite(
37	>	TreeMapTest.class,
38	>	MapTest.testSuite(new Implementation()));
39		}
40
41		/**
42	<	* Create a map from Integers 1-5 to Strings "A"-"E".
42	>	* Returns a new map from Integers 1-5 to Strings "A"-"E".
43		*/
44	<	private static TreeMap map5() {
45	<	TreeMap map = new TreeMap();
44	>	private static TreeMap map5() {
45	>	TreeMap map = new TreeMap();
46		assertTrue(map.isEmpty());
47	<	map.put(one, "A");
48	<	map.put(five, "E");
49	<	map.put(three, "C");
50	<	map.put(two, "B");
51	<	map.put(four, "D");
47	>	map.put(one, "A");
48	>	map.put(five, "E");
49	>	map.put(three, "C");
50	>	map.put(two, "B");
51	>	map.put(four, "D");
52		assertFalse(map.isEmpty());
53		assertEquals(5, map.size());
54	<	return map;
54	>	return map;
55		}
56
57		/**
58	<	*  clear removes all pairs
58	>	* clear removes all pairs
59		*/
60		public void testClear() {
61		TreeMap map = map5();
62	<	map.clear();
63	<	assertEquals(map.size(), 0);
62	>	map.clear();
63	>	assertEquals(0, map.size());
64		}
65
66		/**
67	<	*
67	>	* copy constructor creates map equal to source map
68		*/
69		public void testConstructFromSorted() {
70		TreeMap map = map5();
#	Line 52 | Line 73 | public class TreeMapTest extends JSR166T
73		}
74
75		/**
76	<	*  Maps with same contents are equal
76	>	* Maps with same contents are equal
77		*/
78		public void testEquals() {
79		TreeMap map1 = map5();
80		TreeMap map2 = map5();
81		assertEquals(map1, map2);
82		assertEquals(map2, map1);
83	<	map1.clear();
83	>	map1.clear();
84		assertFalse(map1.equals(map2));
85		assertFalse(map2.equals(map1));
86		}
87
88		/**
89	<	*  containsKey returns true for contained key
89	>	* containsKey returns true for contained key
90		*/
91		public void testContainsKey() {
92		TreeMap map = map5();
93	<	assertTrue(map.containsKey(one));
93	>	assertTrue(map.containsKey(one));
94		assertFalse(map.containsKey(zero));
95		}
96
97		/**
98	<	*  containsValue returns true for held values
98	>	* containsValue returns true for held values
99		*/
100		public void testContainsValue() {
101		TreeMap map = map5();
102	<	assertTrue(map.containsValue("A"));
102	>	assertTrue(map.containsValue("A"));
103		assertFalse(map.containsValue("Z"));
104		}
105
106		/**
107	<	*  get returns the correct element at the given key,
108	<	*  or null if not present
107	>	* get returns the correct element at the given key,
108	>	* or null if not present
109		*/
110		public void testGet() {
111		TreeMap map = map5();
112	<	assertEquals("A", (String)map.get(one));
112	>	assertEquals("A", (String)map.get(one));
113		TreeMap empty = new TreeMap();
114		assertNull(empty.get(one));
115		}
116
117		/**
118	<	*  isEmpty is true of empty map and false for non-empty
118	>	* isEmpty is true of empty map and false for non-empty
119		*/
120		public void testIsEmpty() {
121		TreeMap empty = new TreeMap();
122		TreeMap map = map5();
123	<	assertTrue(empty.isEmpty());
123	>	assertTrue(empty.isEmpty());
124		assertFalse(map.isEmpty());
125		}
126
127		/**
128	<	*   firstKey returns first key
128	>	* firstKey returns first key
129		*/
130		public void testFirstKey() {
131		TreeMap map = map5();
132	<	assertEquals(one, map.firstKey());
132	>	assertEquals(one, map.firstKey());
133		}
134
135		/**
136	<	*   lastKey returns last key
136	>	* lastKey returns last key
137		*/
138		public void testLastKey() {
139		TreeMap map = map5();
140	<	assertEquals(five, map.lastKey());
140	>	assertEquals(five, map.lastKey());
141		}
142
122	–
143		/**
144	<	*  keySet.toArray returns contains all keys
144	>	* keySet.toArray returns contains all keys
145		*/
146		public void testKeySetToArray() {
147		TreeMap map = map5();
148	<	Set s = map.keySet();
148	>	Set s = map.keySet();
149		Object[] ar = s.toArray();
150		assertTrue(s.containsAll(Arrays.asList(ar)));
151	<	assertEquals(5, ar.length);
151	>	assertEquals(5, ar.length);
152		ar[0] = m10;
153		assertFalse(s.containsAll(Arrays.asList(ar)));
154		}
155
156		/**
157	<	*  descendingkeySet.toArray returns contains all keys
157	>	* descendingkeySet.toArray returns contains all keys
158		*/
159		public void testDescendingKeySetToArray() {
160		TreeMap map = map5();
161	<	Set s = map.descendingKeySet();
161	>	Set s = map.descendingKeySet();
162		Object[] ar = s.toArray();
163	<	assertEquals(5, ar.length);
163	>	assertEquals(5, ar.length);
164		assertTrue(s.containsAll(Arrays.asList(ar)));
165		ar[0] = m10;
166		assertFalse(s.containsAll(Arrays.asList(ar)));
167		}
168
169		/**
170	<	*   keySet returns a Set containing all the keys
170	>	* keySet returns a Set containing all the keys
171		*/
172		public void testKeySet() {
173		TreeMap map = map5();
174	<	Set s = map.keySet();
175	<	assertEquals(5, s.size());
176	<	assertTrue(s.contains(one));
177	<	assertTrue(s.contains(two));
178	<	assertTrue(s.contains(three));
179	<	assertTrue(s.contains(four));
180	<	assertTrue(s.contains(five));
174	>	Set s = map.keySet();
175	>	assertEquals(5, s.size());
176	>	assertTrue(s.contains(one));
177	>	assertTrue(s.contains(two));
178	>	assertTrue(s.contains(three));
179	>	assertTrue(s.contains(four));
180	>	assertTrue(s.contains(five));
181		}
182
183		/**
184	<	*   keySet is ordered
184	>	* keySet is ordered
185		*/
186		public void testKeySetOrder() {
187		TreeMap map = map5();
188	<	Set s = map.keySet();
188	>	Set s = map.keySet();
189		Iterator i = s.iterator();
190		Integer last = (Integer)i.next();
191		assertEquals(last, one);
192	+	int count = 1;
193		while (i.hasNext()) {
194		Integer k = (Integer)i.next();
195		assertTrue(last.compareTo(k) < 0);
196		last = k;
197	+	++count;
198	+	}
199	+	assertEquals(5, count);
200	+	}
201	+
202	+	/**
203	+	* descending iterator of key set is inverse ordered
204	+	*/
205	+	public void testKeySetDescendingIteratorOrder() {
206	+	TreeMap map = map5();
207	+	NavigableSet s = map.navigableKeySet();
208	+	Iterator i = s.descendingIterator();
209	+	Integer last = (Integer)i.next();
210	+	assertEquals(last, five);
211	+	int count = 1;
212	+	while (i.hasNext()) {
213	+	Integer k = (Integer)i.next();
214	+	assertTrue(last.compareTo(k) > 0);
215	+	last = k;
216	+	++count;
217		}
218	+	assertEquals(5, count);
219		}
220
221		/**
222	<	*   descendingKeySet is ordered
222	>	* descendingKeySet is ordered
223		*/
224		public void testDescendingKeySetOrder() {
225		TreeMap map = map5();
226	<	Set s = map.descendingKeySet();
226	>	Set s = map.descendingKeySet();
227		Iterator i = s.iterator();
228		Integer last = (Integer)i.next();
229		assertEquals(last, five);
230	+	int count = 1;
231		while (i.hasNext()) {
232		Integer k = (Integer)i.next();
233		assertTrue(last.compareTo(k) > 0);
234		last = k;
235	+	++count;
236		}
237	+	assertEquals(5, count);
238	+	}
239	+
240	+	/**
241	+	* descending iterator of descendingKeySet is ordered
242	+	*/
243	+	public void testDescendingKeySetDescendingIteratorOrder() {
244	+	TreeMap map = map5();
245	+	NavigableSet s = map.descendingKeySet();
246	+	Iterator i = s.descendingIterator();
247	+	Integer last = (Integer)i.next();
248	+	assertEquals(last, one);
249	+	int count = 1;
250	+	while (i.hasNext()) {
251	+	Integer k = (Integer)i.next();
252	+	assertTrue(last.compareTo(k) < 0);
253	+	last = k;
254	+	++count;
255	+	}
256	+	assertEquals(5, count);
257		}
258
259		/**
#	Line 197 | Line 261 | public class TreeMapTest extends JSR166T
261		*/
262		public void testValues() {
263		TreeMap map = map5();
264	<	Collection s = map.values();
265	<	assertEquals(5, s.size());
266	<	assertTrue(s.contains("A"));
267	<	assertTrue(s.contains("B"));
268	<	assertTrue(s.contains("C"));
269	<	assertTrue(s.contains("D"));
270	<	assertTrue(s.contains("E"));
264	>	Collection s = map.values();
265	>	assertEquals(5, s.size());
266	>	assertTrue(s.contains("A"));
267	>	assertTrue(s.contains("B"));
268	>	assertTrue(s.contains("C"));
269	>	assertTrue(s.contains("D"));
270	>	assertTrue(s.contains("E"));
271		}
272
273		/**
#	Line 211 | Line 275 | public class TreeMapTest extends JSR166T
275		*/
276		public void testEntrySet() {
277		TreeMap map = map5();
278	<	Set s = map.entrySet();
279	<	assertEquals(5, s.size());
278	>	Set s = map.entrySet();
279	>	assertEquals(5, s.size());
280		Iterator it = s.iterator();
281		while (it.hasNext()) {
282		Map.Entry e = (Map.Entry) it.next();
283	<	assertTrue(
283	>	assertTrue(
284		(e.getKey().equals(one) && e.getValue().equals("A")) ||
285		(e.getKey().equals(two) && e.getValue().equals("B")) ||
286		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 230 | Line 294 | public class TreeMapTest extends JSR166T
294		*/
295		public void testDescendingEntrySet() {
296		TreeMap map = map5();
297	<	Set s = map.descendingEntrySet();
298	<	assertEquals(5, s.size());
297	>	Set s = map.descendingMap().entrySet();
298	>	assertEquals(5, s.size());
299		Iterator it = s.iterator();
300		while (it.hasNext()) {
301		Map.Entry e = (Map.Entry) it.next();
302	<	assertTrue(
302	>	assertTrue(
303		(e.getKey().equals(one) && e.getValue().equals("A")) ||
304		(e.getKey().equals(two) && e.getValue().equals("B")) ||
305		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 245 | Line 309 | public class TreeMapTest extends JSR166T
309		}
310
311		/**
312	<	*  entrySet.toArray contains all entries
312	>	* entrySet.toArray contains all entries
313		*/
314		public void testEntrySetToArray() {
315		TreeMap map = map5();
316	<	Set s = map.entrySet();
316	>	Set s = map.entrySet();
317		Object[] ar = s.toArray();
318		assertEquals(5, ar.length);
319		for (int i = 0; i < 5; ++i) {
#	Line 259 | Line 323 | public class TreeMapTest extends JSR166T
323		}
324
325		/**
326	<	*  descendingEntrySet.toArray contains all entries
326	>	* descendingEntrySet.toArray contains all entries
327		*/
328		public void testDescendingEntrySetToArray() {
329		TreeMap map = map5();
330	<	Set s = map.descendingEntrySet();
330	>	Set s = map.descendingMap().entrySet();
331		Object[] ar = s.toArray();
332		assertEquals(5, ar.length);
333		for (int i = 0; i < 5; ++i) {
#	Line 273 | Line 337 | public class TreeMapTest extends JSR166T
337		}
338
339		/**
340	<	*   putAll  adds all key-value pairs from the given map
340	>	* putAll adds all key-value pairs from the given map
341		*/
342		public void testPutAll() {
343		TreeMap empty = new TreeMap();
344		TreeMap map = map5();
345	<	empty.putAll(map);
346	<	assertEquals(5, empty.size());
347	<	assertTrue(empty.containsKey(one));
348	<	assertTrue(empty.containsKey(two));
349	<	assertTrue(empty.containsKey(three));
350	<	assertTrue(empty.containsKey(four));
351	<	assertTrue(empty.containsKey(five));
345	>	empty.putAll(map);
346	>	assertEquals(5, empty.size());
347	>	assertTrue(empty.containsKey(one));
348	>	assertTrue(empty.containsKey(two));
349	>	assertTrue(empty.containsKey(three));
350	>	assertTrue(empty.containsKey(four));
351	>	assertTrue(empty.containsKey(five));
352		}
353
354		/**
355	<	*   remove removes the correct key-value pair from the map
355	>	* remove removes the correct key-value pair from the map
356		*/
357		public void testRemove() {
358		TreeMap map = map5();
359	<	map.remove(five);
360	<	assertEquals(4, map.size());
361	<	assertFalse(map.containsKey(five));
359	>	map.remove(five);
360	>	assertEquals(4, map.size());
361	>	assertFalse(map.containsKey(five));
362		}
363
364		/**
#	Line 313 | Line 377 | public class TreeMapTest extends JSR166T
377
378		Map.Entry e4 = map.lowerEntry(zero);
379		assertNull(e4);
316	–
380		}
381
382		/**
#	Line 332 | Line 395 | public class TreeMapTest extends JSR166T
395
396		Map.Entry e4 = map.higherEntry(six);
397		assertNull(e4);
335	–
398		}
399
400		/**
#	Line 351 | Line 413 | public class TreeMapTest extends JSR166T
413
414		Map.Entry e4 = map.floorEntry(zero);
415		assertNull(e4);
354	–
416		}
417
418		/**
#	Line 370 | Line 431 | public class TreeMapTest extends JSR166T
431
432		Map.Entry e4 = map.ceilingEntry(six);
433		assertNull(e4);
373	–
434		}
435
376	–
436		/**
437		* lowerKey returns preceding element
438		*/
#	Line 390 | Line 449 | public class TreeMapTest extends JSR166T
449
450		Object e4 = q.lowerKey(zero);
451		assertNull(e4);
393	–
452		}
453
454		/**
#	Line 409 | Line 467 | public class TreeMapTest extends JSR166T
467
468		Object e4 = q.higherKey(six);
469		assertNull(e4);
412	–
470		}
471
472		/**
#	Line 428 | Line 485 | public class TreeMapTest extends JSR166T
485
486		Object e4 = q.floorKey(zero);
487		assertNull(e4);
431	–
488		}
489
490		/**
#	Line 447 | Line 503 | public class TreeMapTest extends JSR166T
503
504		Object e4 = q.ceilingKey(six);
505		assertNull(e4);
450	–
506		}
507
508		/**
#	Line 472 | Line 527 | public class TreeMapTest extends JSR166T
527		try {
528		e.setValue("A");
529		shouldThrow();
530	<	} catch (Exception ok) {
476	<	}
530	>	} catch (UnsupportedOperationException success) {}
531		e = map.pollFirstEntry();
532		assertNull(e);
533		}
#	Line 500 | Line 554 | public class TreeMapTest extends JSR166T
554		try {
555		e.setValue("E");
556		shouldThrow();
557	<	} catch (Exception ok) {
504	<	}
557	>	} catch (UnsupportedOperationException success) {}
558		e = map.pollLastEntry();
559		assertNull(e);
560		}
561
562		/**
563	<	*   size returns the correct values
563	>	* size returns the correct values
564		*/
565		public void testSize() {
566		TreeMap map = map5();
567		TreeMap empty = new TreeMap();
568	<	assertEquals(0, empty.size());
569	<	assertEquals(5, map.size());
568	>	assertEquals(0, empty.size());
569	>	assertEquals(5, map.size());
570		}
571
572		/**
#	Line 523 | Line 576 | public class TreeMapTest extends JSR166T
576		TreeMap map = map5();
577		String s = map.toString();
578		for (int i = 1; i <= 5; ++i) {
579	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
579	>	assertTrue(s.contains(String.valueOf(i)));
580		}
581	<	}
581	>	}
582
583		// Exception tests
584
#	Line 533 | Line 586 | public class TreeMapTest extends JSR166T
586		* get(null) of nonempty map throws NPE
587		*/
588		public void testGet_NullPointerException() {
589	+	TreeMap c = map5();
590		try {
537	–	TreeMap c = map5();
591		c.get(null);
592		shouldThrow();
593	<	} catch(NullPointerException e){}
593	>	} catch (NullPointerException success) {}
594		}
595
596		/**
597		* containsKey(null) of nonempty map throws NPE
598		*/
599		public void testContainsKey_NullPointerException() {
600	+	TreeMap c = map5();
601		try {
548	–	TreeMap c = map5();
602		c.containsKey(null);
603		shouldThrow();
604	<	} catch(NullPointerException e){}
604	>	} catch (NullPointerException success) {}
605		}
606
607		/**
608		* remove(null) throws NPE for nonempty map
609		*/
610		public void testRemove1_NullPointerException() {
611	+	TreeMap c = new TreeMap();
612	+	c.put("sadsdf", "asdads");
613		try {
559	–	TreeMap c = new TreeMap();
560	–	c.put("sadsdf", "asdads");
614		c.remove(null);
615		shouldThrow();
616	<	} catch(NullPointerException e){}
616	>	} catch (NullPointerException success) {}
617		}
618
619		/**
620	<	* A deserialized map equals original
620	>	* A deserialized/reserialized map equals original
621		*/
622	<	public void testSerialization() {
623	<	TreeMap q = map5();
622	>	public void testSerialization() throws Exception {
623	>	NavigableMap x = map5();
624	>	NavigableMap y = serialClone(x);
625
626	<	try {
627	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
628	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
629	<	out.writeObject(q);
630	<	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	<	}
626	>	assertNotSame(x, y);
627	>	assertEquals(x.size(), y.size());
628	>	assertEquals(x.toString(), y.toString());
629	>	assertEquals(x, y);
630	>	assertEquals(y, x);
631		}
632
633		/**
#	Line 592 | Line 635 | public class TreeMapTest extends JSR166T
635		*/
636		public void testSubMapContents() {
637		TreeMap map = map5();
638	<	NavigableMap sm = map.subMap(two, four);
638	>	NavigableMap sm = map.subMap(two, true, four, false);
639		assertEquals(two, sm.firstKey());
640		assertEquals(three, sm.lastKey());
641		assertEquals(2, sm.size());
#	Line 614 | Line 657 | public class TreeMapTest extends JSR166T
657		k = (Integer)(r.next());
658		assertEquals(two, k);
659		assertFalse(r.hasNext());
660	<
660	>
661		Iterator j = sm.keySet().iterator();
662		j.next();
663		j.remove();
#	Line 623 | Line 666 | public class TreeMapTest extends JSR166T
666		assertEquals(1, sm.size());
667		assertEquals(three, sm.firstKey());
668		assertEquals(three, sm.lastKey());
669	<	assertTrue(sm.remove(three) != null);
669	>	assertEquals("C", sm.remove(three));
670		assertTrue(sm.isEmpty());
671		assertEquals(3, map.size());
672		}
673
674		public void testSubMapContents2() {
675		TreeMap map = map5();
676	<	NavigableMap sm = map.subMap(two, three);
676	>	NavigableMap sm = map.subMap(two, true, three, false);
677		assertEquals(1, sm.size());
678		assertEquals(two, sm.firstKey());
679		assertEquals(two, sm.lastKey());
#	Line 648 | Line 691 | public class TreeMapTest extends JSR166T
691		k = (Integer)(r.next());
692		assertEquals(two, k);
693		assertFalse(r.hasNext());
694	<
694	>
695		Iterator j = sm.keySet().iterator();
696		j.next();
697		j.remove();
#	Line 656 | Line 699 | public class TreeMapTest extends JSR166T
699		assertEquals(4, map.size());
700		assertEquals(0, sm.size());
701		assertTrue(sm.isEmpty());
702	<	assertTrue(sm.remove(three) == null);
702	>	assertSame(sm.remove(three), null);
703		assertEquals(4, map.size());
704		}
705
#	Line 665 | Line 708 | public class TreeMapTest extends JSR166T
708		*/
709		public void testHeadMapContents() {
710		TreeMap map = map5();
711	<	NavigableMap sm = map.headMap(four);
711	>	NavigableMap sm = map.headMap(four, false);
712		assertTrue(sm.containsKey(one));
713		assertTrue(sm.containsKey(two));
714		assertTrue(sm.containsKey(three));
#	Line 691 | Line 734 | public class TreeMapTest extends JSR166T
734		*/
735		public void testTailMapContents() {
736		TreeMap map = map5();
737	<	NavigableMap sm = map.tailMap(two);
737	>	NavigableMap sm = map.tailMap(two, true);
738		assertFalse(sm.containsKey(one));
739		assertTrue(sm.containsKey(two));
740		assertTrue(sm.containsKey(three));
#	Line 735 | Line 778 | public class TreeMapTest extends JSR166T
778		assertEquals("E", e.getValue());
779		assertFalse(i.hasNext());
780
781	<	NavigableMap ssm = sm.tailMap(four);
781	>	NavigableMap ssm = sm.tailMap(four, true);
782		assertEquals(four, ssm.firstKey());
783		assertEquals(five, ssm.lastKey());
784	<	assertTrue(ssm.remove(four) != null);
784	>	assertEquals("D", ssm.remove(four));
785		assertEquals(1, ssm.size());
786		assertEquals(3, sm.size());
787		assertEquals(4, map.size());
788		}
789	<
789	>
790	>	Random rnd = new Random(666);
791	>	BitSet bs;
792	>
793	>	/**
794	>	* Submaps of submaps subdivide correctly
795	>	*/
796	>	public void testRecursiveSubMaps() throws Exception {
797	>	int mapSize = expensiveTests ? 1000 : 100;
798	>	Class cl = TreeMap.class;
799	>	NavigableMap<Integer, Integer> map = newMap(cl);
800	>	bs = new BitSet(mapSize);
801	>
802	>	populate(map, mapSize);
803	>	check(map,                 0, mapSize - 1, true);
804	>	check(map.descendingMap(), 0, mapSize - 1, false);
805	>
806	>	mutateMap(map, 0, mapSize - 1);
807	>	check(map,                 0, mapSize - 1, true);
808	>	check(map.descendingMap(), 0, mapSize - 1, false);
809	>
810	>	bashSubMap(map.subMap(0, true, mapSize, false),
811	>	0, mapSize - 1, true);
812	>	}
813	>
814	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
815	>	NavigableMap<Integer, Integer> result
816	>	= (NavigableMap<Integer, Integer>) cl.getConstructor().newInstance();
817	>	assertEquals(0, result.size());
818	>	assertFalse(result.keySet().iterator().hasNext());
819	>	return result;
820	>	}
821	>
822	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
823	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
824	>	int key = rnd.nextInt(limit);
825	>	put(map, key);
826	>	}
827	>	}
828	>
829	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
830	>	int size = map.size();
831	>	int rangeSize = max - min + 1;
832	>
833	>	// Remove a bunch of entries directly
834	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
835	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
836	>	}
837	>
838	>	// Remove a bunch of entries with iterator
839	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
840	>	if (rnd.nextBoolean()) {
841	>	bs.clear(it.next());
842	>	it.remove();
843	>	}
844	>	}
845	>
846	>	// Add entries till we're back to original size
847	>	while (map.size() < size) {
848	>	int key = min + rnd.nextInt(rangeSize);
849	>	assertTrue(key >= min && key <= max);
850	>	put(map, key);
851	>	}
852	>	}
853	>
854	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
855	>	int size = map.size();
856	>	int rangeSize = max - min + 1;
857	>
858	>	// Remove a bunch of entries directly
859	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
860	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
861	>	}
862	>
863	>	// Remove a bunch of entries with iterator
864	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
865	>	if (rnd.nextBoolean()) {
866	>	bs.clear(it.next());
867	>	it.remove();
868	>	}
869	>	}
870	>
871	>	// Add entries till we're back to original size
872	>	while (map.size() < size) {
873	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
874	>	if (key >= min && key <= max) {
875	>	put(map, key);
876	>	} else {
877	>	try {
878	>	map.put(key, 2 * key);
879	>	shouldThrow();
880	>	} catch (IllegalArgumentException success) {}
881	>	}
882	>	}
883	>	}
884	>
885	>	void put(NavigableMap<Integer, Integer> map, int key) {
886	>	if (map.put(key, 2 * key) == null)
887	>	bs.set(key);
888	>	}
889	>
890	>	void remove(NavigableMap<Integer, Integer> map, int key) {
891	>	if (map.remove(key) != null)
892	>	bs.clear(key);
893	>	}
894	>
895	>	void bashSubMap(NavigableMap<Integer, Integer> map,
896	>	int min, int max, boolean ascending) {
897	>	check(map, min, max, ascending);
898	>	check(map.descendingMap(), min, max, !ascending);
899	>
900	>	mutateSubMap(map, min, max);
901	>	check(map, min, max, ascending);
902	>	check(map.descendingMap(), min, max, !ascending);
903	>
904	>	// Recurse
905	>	if (max - min < 2)
906	>	return;
907	>	int midPoint = (min + max) / 2;
908	>
909	>	// headMap - pick direction and endpoint inclusion randomly
910	>	boolean incl = rnd.nextBoolean();
911	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
912	>	if (ascending) {
913	>	if (rnd.nextBoolean())
914	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
915	>	else
916	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
917	>	false);
918	>	} else {
919	>	if (rnd.nextBoolean())
920	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
921	>	else
922	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
923	>	true);
924	>	}
925	>
926	>	// tailMap - pick direction and endpoint inclusion randomly
927	>	incl = rnd.nextBoolean();
928	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
929	>	if (ascending) {
930	>	if (rnd.nextBoolean())
931	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
932	>	else
933	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
934	>	false);
935	>	} else {
936	>	if (rnd.nextBoolean()) {
937	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
938	>	} else {
939	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
940	>	true);
941	>	}
942	>	}
943	>
944	>	// subMap - pick direction and endpoint inclusion randomly
945	>	int rangeSize = max - min + 1;
946	>	int[] endpoints = new int[2];
947	>	endpoints[0] = min + rnd.nextInt(rangeSize);
948	>	endpoints[1] = min + rnd.nextInt(rangeSize);
949	>	Arrays.sort(endpoints);
950	>	boolean lowIncl = rnd.nextBoolean();
951	>	boolean highIncl = rnd.nextBoolean();
952	>	if (ascending) {
953	>	NavigableMap<Integer,Integer> sm = map.subMap(
954	>	endpoints[0], lowIncl, endpoints[1], highIncl);
955	>	if (rnd.nextBoolean())
956	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
957	>	endpoints[1] - (highIncl ? 0 : 1), true);
958	>	else
959	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
960	>	endpoints[1] - (highIncl ? 0 : 1), false);
961	>	} else {
962	>	NavigableMap<Integer,Integer> sm = map.subMap(
963	>	endpoints[1], highIncl, endpoints[0], lowIncl);
964	>	if (rnd.nextBoolean())
965	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
966	>	endpoints[1] - (highIncl ? 0 : 1), false);
967	>	else
968	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
969	>	endpoints[1] - (highIncl ? 0 : 1), true);
970	>	}
971	>	}
972	>
973	>	/**
974	>	* min and max are both inclusive.  If max < min, interval is empty.
975	>	*/
976	>	void check(NavigableMap<Integer, Integer> map,
977	>	final int min, final int max, final boolean ascending) {
978	>	class ReferenceSet {
979	>	int lower(int key) {
980	>	return ascending ? lowerAscending(key) : higherAscending(key);
981	>	}
982	>	int floor(int key) {
983	>	return ascending ? floorAscending(key) : ceilingAscending(key);
984	>	}
985	>	int ceiling(int key) {
986	>	return ascending ? ceilingAscending(key) : floorAscending(key);
987	>	}
988	>	int higher(int key) {
989	>	return ascending ? higherAscending(key) : lowerAscending(key);
990	>	}
991	>	int first() {
992	>	return ascending ? firstAscending() : lastAscending();
993	>	}
994	>	int last() {
995	>	return ascending ? lastAscending() : firstAscending();
996	>	}
997	>	int lowerAscending(int key) {
998	>	return floorAscending(key - 1);
999	>	}
1000	>	int floorAscending(int key) {
1001	>	if (key < min)
1002	>	return -1;
1003	>	else if (key > max)
1004	>	key = max;
1005	>
1006	>	// BitSet should support this! Test would run much faster
1007	>	while (key >= min) {
1008	>	if (bs.get(key))
1009	>	return key;
1010	>	key--;
1011	>	}
1012	>	return -1;
1013	>	}
1014	>	int ceilingAscending(int key) {
1015	>	if (key < min)
1016	>	key = min;
1017	>	else if (key > max)
1018	>	return -1;
1019	>	int result = bs.nextSetBit(key);
1020	>	return result > max ? -1 : result;
1021	>	}
1022	>	int higherAscending(int key) {
1023	>	return ceilingAscending(key + 1);
1024	>	}
1025	>	private int firstAscending() {
1026	>	int result = ceilingAscending(min);
1027	>	return result > max ? -1 : result;
1028	>	}
1029	>	private int lastAscending() {
1030	>	int result = floorAscending(max);
1031	>	return result < min ? -1 : result;
1032	>	}
1033	>	}
1034	>	ReferenceSet rs = new ReferenceSet();
1035	>
1036	>	// Test contents using containsKey
1037	>	int size = 0;
1038	>	for (int i = min; i <= max; i++) {
1039	>	boolean bsContainsI = bs.get(i);
1040	>	assertEquals(bsContainsI, map.containsKey(i));
1041	>	if (bsContainsI)
1042	>	size++;
1043	>	}
1044	>	assertEquals(size, map.size());
1045	>
1046	>	// Test contents using contains keySet iterator
1047	>	int size2 = 0;
1048	>	int previousKey = -1;
1049	>	for (int key : map.keySet()) {
1050	>	assertTrue(bs.get(key));
1051	>	size2++;
1052	>	assertTrue(previousKey < 0 ||
1053	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1054	>	previousKey = key;
1055	>	}
1056	>	assertEquals(size2, size);
1057	>
1058	>	// Test navigation ops
1059	>	for (int key = min - 1; key <= max + 1; key++) {
1060	>	assertEq(map.lowerKey(key), rs.lower(key));
1061	>	assertEq(map.floorKey(key), rs.floor(key));
1062	>	assertEq(map.higherKey(key), rs.higher(key));
1063	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1064	>	}
1065	>
1066	>	// Test extrema
1067	>	if (map.size() != 0) {
1068	>	assertEq(map.firstKey(), rs.first());
1069	>	assertEq(map.lastKey(), rs.last());
1070	>	} else {
1071	>	assertEq(rs.first(), -1);
1072	>	assertEq(rs.last(),  -1);
1073	>	try {
1074	>	map.firstKey();
1075	>	shouldThrow();
1076	>	} catch (NoSuchElementException success) {}
1077	>	try {
1078	>	map.lastKey();
1079	>	shouldThrow();
1080	>	} catch (NoSuchElementException success) {}
1081	>	}
1082	>	}
1083	>
1084	>	static void assertEq(Integer i, int j) {
1085	>	if (i == null)
1086	>	assertEquals(j, -1);
1087	>	else
1088	>	assertEquals((int) i, j);
1089	>	}
1090	>
1091	>	static boolean eq(Integer i, int j) {
1092	>	return i == null ? j == -1 : i == j;
1093	>	}
1094	>
1095		}

Diff Legend

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