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

Diff Legend

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