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.21 by jsr166, Tue May 31 16:16:24 2011 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.*;
9
10		public class TreeMapTest extends JSR166TestCase {
11		public static void main(String[] args) {
12	<	junit.textui.TestRunner.run (suite());
12	>	junit.textui.TestRunner.run(suite());
13		}
14		public static Test suite() {
15	<	return new TestSuite(TreeMapTest.class);
15	>	return new TestSuite(TreeMapTest.class);
16		}
17
18		/**
19		* Create a map from Integers 1-5 to Strings "A"-"E".
20		*/
21	<	private static TreeMap map5() {
22	<	TreeMap map = new TreeMap();
21	>	private static TreeMap map5() {
22	>	TreeMap map = new TreeMap();
23		assertTrue(map.isEmpty());
24	<	map.put(one, "A");
25	<	map.put(five, "E");
26	<	map.put(three, "C");
27	<	map.put(two, "B");
28	<	map.put(four, "D");
24	>	map.put(one, "A");
25	>	map.put(five, "E");
26	>	map.put(three, "C");
27	>	map.put(two, "B");
28	>	map.put(four, "D");
29		assertFalse(map.isEmpty());
30		assertEquals(5, map.size());
31	<	return map;
31	>	return map;
32		}
33
34		/**
35	<	*  clear removes all pairs
35	>	* clear removes all pairs
36		*/
37		public void testClear() {
38		TreeMap map = map5();
39	<	map.clear();
40	<	assertEquals(map.size(), 0);
39	>	map.clear();
40	>	assertEquals(map.size(), 0);
41		}
42
43		/**
44	<	*
44	>	*
45		*/
46		public void testConstructFromSorted() {
47		TreeMap map = map5();
#	Line 52 | Line 50 | public class TreeMapTest extends JSR166T
50		}
51
52		/**
53	<	*  Maps with same contents are equal
53	>	* Maps with same contents are equal
54		*/
55		public void testEquals() {
56		TreeMap map1 = map5();
57		TreeMap map2 = map5();
58		assertEquals(map1, map2);
59		assertEquals(map2, map1);
60	<	map1.clear();
60	>	map1.clear();
61		assertFalse(map1.equals(map2));
62		assertFalse(map2.equals(map1));
63		}
64
65		/**
66	<	*  containsKey returns true for contained key
66	>	* containsKey returns true for contained key
67		*/
68		public void testContainsKey() {
69		TreeMap map = map5();
70	<	assertTrue(map.containsKey(one));
70	>	assertTrue(map.containsKey(one));
71		assertFalse(map.containsKey(zero));
72		}
73
74		/**
75	<	*  containsValue returns true for held values
75	>	* containsValue returns true for held values
76		*/
77		public void testContainsValue() {
78		TreeMap map = map5();
79	<	assertTrue(map.containsValue("A"));
79	>	assertTrue(map.containsValue("A"));
80		assertFalse(map.containsValue("Z"));
81		}
82
83		/**
84	<	*  get returns the correct element at the given key,
85	<	*  or null if not present
84	>	* get returns the correct element at the given key,
85	>	* or null if not present
86		*/
87		public void testGet() {
88		TreeMap map = map5();
89	<	assertEquals("A", (String)map.get(one));
89	>	assertEquals("A", (String)map.get(one));
90		TreeMap empty = new TreeMap();
91		assertNull(empty.get(one));
92		}
93
94		/**
95	<	*  isEmpty is true of empty map and false for non-empty
95	>	* isEmpty is true of empty map and false for non-empty
96		*/
97		public void testIsEmpty() {
98		TreeMap empty = new TreeMap();
99		TreeMap map = map5();
100	<	assertTrue(empty.isEmpty());
100	>	assertTrue(empty.isEmpty());
101		assertFalse(map.isEmpty());
102		}
103
104		/**
105	<	*   firstKey returns first key
105	>	* firstKey returns first key
106		*/
107		public void testFirstKey() {
108		TreeMap map = map5();
109	<	assertEquals(one, map.firstKey());
109	>	assertEquals(one, map.firstKey());
110		}
111
112		/**
113	<	*   lastKey returns last key
113	>	* lastKey returns last key
114		*/
115		public void testLastKey() {
116		TreeMap map = map5();
117	<	assertEquals(five, map.lastKey());
117	>	assertEquals(five, map.lastKey());
118		}
119
122	–
120		/**
121	<	*  keySet.toArray returns contains all keys
121	>	* keySet.toArray returns contains all keys
122		*/
123		public void testKeySetToArray() {
124		TreeMap map = map5();
125	<	Set s = map.keySet();
125	>	Set s = map.keySet();
126		Object[] ar = s.toArray();
127		assertTrue(s.containsAll(Arrays.asList(ar)));
128	<	assertEquals(5, ar.length);
128	>	assertEquals(5, ar.length);
129		ar[0] = m10;
130		assertFalse(s.containsAll(Arrays.asList(ar)));
131		}
132
133		/**
134	<	*  descendingkeySet.toArray returns contains all keys
134	>	* descendingkeySet.toArray returns contains all keys
135		*/
136		public void testDescendingKeySetToArray() {
137		TreeMap map = map5();
138	<	Set s = map.descendingKeySet();
138	>	Set s = map.descendingKeySet();
139		Object[] ar = s.toArray();
140	<	assertEquals(5, ar.length);
140	>	assertEquals(5, ar.length);
141		assertTrue(s.containsAll(Arrays.asList(ar)));
142		ar[0] = m10;
143		assertFalse(s.containsAll(Arrays.asList(ar)));
144		}
145
146		/**
147	<	*   keySet returns a Set containing all the keys
147	>	* keySet returns a Set containing all the keys
148		*/
149		public void testKeySet() {
150		TreeMap map = map5();
151	<	Set s = map.keySet();
152	<	assertEquals(5, s.size());
153	<	assertTrue(s.contains(one));
154	<	assertTrue(s.contains(two));
155	<	assertTrue(s.contains(three));
156	<	assertTrue(s.contains(four));
157	<	assertTrue(s.contains(five));
151	>	Set s = map.keySet();
152	>	assertEquals(5, s.size());
153	>	assertTrue(s.contains(one));
154	>	assertTrue(s.contains(two));
155	>	assertTrue(s.contains(three));
156	>	assertTrue(s.contains(four));
157	>	assertTrue(s.contains(five));
158		}
159
160		/**
161	<	*   keySet is ordered
161	>	* keySet is ordered
162		*/
163		public void testKeySetOrder() {
164		TreeMap map = map5();
165	<	Set s = map.keySet();
165	>	Set s = map.keySet();
166		Iterator i = s.iterator();
167		Integer last = (Integer)i.next();
168		assertEquals(last, one);
169	+	int count = 1;
170		while (i.hasNext()) {
171		Integer k = (Integer)i.next();
172		assertTrue(last.compareTo(k) < 0);
173		last = k;
174	+	++count;
175	+	}
176	+	assertEquals(count ,5);
177	+	}
178	+
179	+	/**
180	+	* descending iterator of key set is inverse ordered
181	+	*/
182	+	public void testKeySetDescendingIteratorOrder() {
183	+	TreeMap map = map5();
184	+	NavigableSet s = map.navigableKeySet();
185	+	Iterator i = s.descendingIterator();
186	+	Integer last = (Integer)i.next();
187	+	assertEquals(last, five);
188	+	int count = 1;
189	+	while (i.hasNext()) {
190	+	Integer k = (Integer)i.next();
191	+	assertTrue(last.compareTo(k) > 0);
192	+	last = k;
193	+	++count;
194		}
195	+	assertEquals(count ,5);
196		}
197
198		/**
199	<	*   descendingKeySet is ordered
199	>	* descendingKeySet is ordered
200		*/
201		public void testDescendingKeySetOrder() {
202		TreeMap map = map5();
203	<	Set s = map.descendingKeySet();
203	>	Set s = map.descendingKeySet();
204		Iterator i = s.iterator();
205		Integer last = (Integer)i.next();
206		assertEquals(last, five);
207	+	int count = 1;
208		while (i.hasNext()) {
209		Integer k = (Integer)i.next();
210		assertTrue(last.compareTo(k) > 0);
211		last = k;
212	+	++count;
213		}
214	+	assertEquals(count, 5);
215	+	}
216	+
217	+	/**
218	+	* descending iterator of descendingKeySet is ordered
219	+	*/
220	+	public void testDescendingKeySetDescendingIteratorOrder() {
221	+	TreeMap map = map5();
222	+	NavigableSet s = map.descendingKeySet();
223	+	Iterator i = s.descendingIterator();
224	+	Integer last = (Integer)i.next();
225	+	assertEquals(last, one);
226	+	int count = 1;
227	+	while (i.hasNext()) {
228	+	Integer k = (Integer)i.next();
229	+	assertTrue(last.compareTo(k) < 0);
230	+	last = k;
231	+	++count;
232	+	}
233	+	assertEquals(count, 5);
234		}
235
236		/**
#	Line 197 | Line 238 | public class TreeMapTest extends JSR166T
238		*/
239		public void testValues() {
240		TreeMap map = map5();
241	<	Collection s = map.values();
242	<	assertEquals(5, s.size());
243	<	assertTrue(s.contains("A"));
244	<	assertTrue(s.contains("B"));
245	<	assertTrue(s.contains("C"));
246	<	assertTrue(s.contains("D"));
247	<	assertTrue(s.contains("E"));
241	>	Collection s = map.values();
242	>	assertEquals(5, s.size());
243	>	assertTrue(s.contains("A"));
244	>	assertTrue(s.contains("B"));
245	>	assertTrue(s.contains("C"));
246	>	assertTrue(s.contains("D"));
247	>	assertTrue(s.contains("E"));
248		}
249
250		/**
#	Line 211 | Line 252 | public class TreeMapTest extends JSR166T
252		*/
253		public void testEntrySet() {
254		TreeMap map = map5();
255	<	Set s = map.entrySet();
256	<	assertEquals(5, s.size());
255	>	Set s = map.entrySet();
256	>	assertEquals(5, s.size());
257		Iterator it = s.iterator();
258		while (it.hasNext()) {
259		Map.Entry e = (Map.Entry) it.next();
260	<	assertTrue(
260	>	assertTrue(
261		(e.getKey().equals(one) && e.getValue().equals("A")) ||
262		(e.getKey().equals(two) && e.getValue().equals("B")) ||
263		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 230 | Line 271 | public class TreeMapTest extends JSR166T
271		*/
272		public void testDescendingEntrySet() {
273		TreeMap map = map5();
274	<	Set s = map.descendingEntrySet();
275	<	assertEquals(5, s.size());
274	>	Set s = map.descendingMap().entrySet();
275	>	assertEquals(5, s.size());
276		Iterator it = s.iterator();
277		while (it.hasNext()) {
278		Map.Entry e = (Map.Entry) it.next();
279	<	assertTrue(
279	>	assertTrue(
280		(e.getKey().equals(one) && e.getValue().equals("A")) ||
281		(e.getKey().equals(two) && e.getValue().equals("B")) ||
282		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 245 | Line 286 | public class TreeMapTest extends JSR166T
286		}
287
288		/**
289	<	*  entrySet.toArray contains all entries
289	>	* entrySet.toArray contains all entries
290		*/
291		public void testEntrySetToArray() {
292		TreeMap map = map5();
293	<	Set s = map.entrySet();
293	>	Set s = map.entrySet();
294		Object[] ar = s.toArray();
295		assertEquals(5, ar.length);
296		for (int i = 0; i < 5; ++i) {
#	Line 259 | Line 300 | public class TreeMapTest extends JSR166T
300		}
301
302		/**
303	<	*  descendingEntrySet.toArray contains all entries
303	>	* descendingEntrySet.toArray contains all entries
304		*/
305		public void testDescendingEntrySetToArray() {
306		TreeMap map = map5();
307	<	Set s = map.descendingEntrySet();
307	>	Set s = map.descendingMap().entrySet();
308		Object[] ar = s.toArray();
309		assertEquals(5, ar.length);
310		for (int i = 0; i < 5; ++i) {
#	Line 273 | Line 314 | public class TreeMapTest extends JSR166T
314		}
315
316		/**
317	<	*   putAll  adds all key-value pairs from the given map
317	>	* putAll adds all key-value pairs from the given map
318		*/
319		public void testPutAll() {
320		TreeMap empty = new TreeMap();
321		TreeMap map = map5();
322	<	empty.putAll(map);
323	<	assertEquals(5, empty.size());
324	<	assertTrue(empty.containsKey(one));
325	<	assertTrue(empty.containsKey(two));
326	<	assertTrue(empty.containsKey(three));
327	<	assertTrue(empty.containsKey(four));
328	<	assertTrue(empty.containsKey(five));
322	>	empty.putAll(map);
323	>	assertEquals(5, empty.size());
324	>	assertTrue(empty.containsKey(one));
325	>	assertTrue(empty.containsKey(two));
326	>	assertTrue(empty.containsKey(three));
327	>	assertTrue(empty.containsKey(four));
328	>	assertTrue(empty.containsKey(five));
329		}
330
331		/**
332	<	*   remove removes the correct key-value pair from the map
332	>	* remove removes the correct key-value pair from the map
333		*/
334		public void testRemove() {
335		TreeMap map = map5();
336	<	map.remove(five);
337	<	assertEquals(4, map.size());
338	<	assertFalse(map.containsKey(five));
336	>	map.remove(five);
337	>	assertEquals(4, map.size());
338	>	assertFalse(map.containsKey(five));
339		}
340
341		/**
#	Line 313 | Line 354 | public class TreeMapTest extends JSR166T
354
355		Map.Entry e4 = map.lowerEntry(zero);
356		assertNull(e4);
316	–
357		}
358
359		/**
#	Line 332 | Line 372 | public class TreeMapTest extends JSR166T
372
373		Map.Entry e4 = map.higherEntry(six);
374		assertNull(e4);
335	–
375		}
376
377		/**
#	Line 351 | Line 390 | public class TreeMapTest extends JSR166T
390
391		Map.Entry e4 = map.floorEntry(zero);
392		assertNull(e4);
354	–
393		}
394
395		/**
#	Line 370 | Line 408 | public class TreeMapTest extends JSR166T
408
409		Map.Entry e4 = map.ceilingEntry(six);
410		assertNull(e4);
373	–
411		}
412
376	–
413		/**
414		* lowerKey returns preceding element
415		*/
#	Line 390 | Line 426 | public class TreeMapTest extends JSR166T
426
427		Object e4 = q.lowerKey(zero);
428		assertNull(e4);
393	–
429		}
430
431		/**
#	Line 409 | Line 444 | public class TreeMapTest extends JSR166T
444
445		Object e4 = q.higherKey(six);
446		assertNull(e4);
412	–
447		}
448
449		/**
#	Line 428 | Line 462 | public class TreeMapTest extends JSR166T
462
463		Object e4 = q.floorKey(zero);
464		assertNull(e4);
431	–
465		}
466
467		/**
#	Line 447 | Line 480 | public class TreeMapTest extends JSR166T
480
481		Object e4 = q.ceilingKey(six);
482		assertNull(e4);
450	–
483		}
484
485		/**
#	Line 472 | Line 504 | public class TreeMapTest extends JSR166T
504		try {
505		e.setValue("A");
506		shouldThrow();
507	<	} catch (Exception ok) {
476	<	}
507	>	} catch (UnsupportedOperationException success) {}
508		e = map.pollFirstEntry();
509		assertNull(e);
510		}
#	Line 500 | Line 531 | public class TreeMapTest extends JSR166T
531		try {
532		e.setValue("E");
533		shouldThrow();
534	<	} catch (Exception ok) {
504	<	}
534	>	} catch (UnsupportedOperationException success) {}
535		e = map.pollLastEntry();
536		assertNull(e);
537		}
538
539		/**
540	<	*   size returns the correct values
540	>	* size returns the correct values
541		*/
542		public void testSize() {
543		TreeMap map = map5();
544		TreeMap empty = new TreeMap();
545	<	assertEquals(0, empty.size());
546	<	assertEquals(5, map.size());
545	>	assertEquals(0, empty.size());
546	>	assertEquals(5, map.size());
547		}
548
549		/**
#	Line 523 | Line 553 | public class TreeMapTest extends JSR166T
553		TreeMap map = map5();
554		String s = map.toString();
555		for (int i = 1; i <= 5; ++i) {
556	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
556	>	assertTrue(s.contains(String.valueOf(i)));
557		}
558	<	}
558	>	}
559
560		// Exception tests
561
#	Line 537 | Line 567 | public class TreeMapTest extends JSR166T
567		TreeMap c = map5();
568		c.get(null);
569		shouldThrow();
570	<	} catch(NullPointerException e){}
570	>	} catch (NullPointerException success) {}
571		}
572
573		/**
#	Line 548 | Line 578 | public class TreeMapTest extends JSR166T
578		TreeMap c = map5();
579		c.containsKey(null);
580		shouldThrow();
581	<	} catch(NullPointerException e){}
581	>	} catch (NullPointerException success) {}
582		}
583
584		/**
#	Line 560 | Line 590 | public class TreeMapTest extends JSR166T
590		c.put("sadsdf", "asdads");
591		c.remove(null);
592		shouldThrow();
593	<	} catch(NullPointerException e){}
593	>	} catch (NullPointerException success) {}
594		}
595
596		/**
597		* A deserialized map equals original
598		*/
599	<	public void testSerialization() {
600	<	TreeMap q = map5();
601	<
602	<	try {
603	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
604	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
605	<	out.writeObject(q);
606	<	out.close();
607	<
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	<	}
599	>	public void testSerialization() throws Exception {
600	>	NavigableMap x = map5();
601	>	NavigableMap y = serialClone(x);
602	>
603	>	assertTrue(x != y);
604	>	assertEquals(x.size(), y.size());
605	>	assertEquals(x.toString(), y.toString());
606	>	assertEquals(x, y);
607	>	assertEquals(y, x);
608		}
609
610		/**
#	Line 592 | Line 612 | public class TreeMapTest extends JSR166T
612		*/
613		public void testSubMapContents() {
614		TreeMap map = map5();
615	<	NavigableMap sm = map.navigableSubMap(two, four);
615	>	NavigableMap sm = map.subMap(two, true, four, false);
616		assertEquals(two, sm.firstKey());
617		assertEquals(three, sm.lastKey());
618		assertEquals(2, sm.size());
#	Line 614 | Line 634 | public class TreeMapTest extends JSR166T
634		k = (Integer)(r.next());
635		assertEquals(two, k);
636		assertFalse(r.hasNext());
637	<
637	>
638		Iterator j = sm.keySet().iterator();
639		j.next();
640		j.remove();
#	Line 623 | Line 643 | public class TreeMapTest extends JSR166T
643		assertEquals(1, sm.size());
644		assertEquals(three, sm.firstKey());
645		assertEquals(three, sm.lastKey());
646	<	assertTrue(sm.remove(three) != null);
646	>	assertEquals("C", sm.remove(three));
647		assertTrue(sm.isEmpty());
648		assertEquals(3, map.size());
649		}
650
651		public void testSubMapContents2() {
652		TreeMap map = map5();
653	<	NavigableMap sm = map.navigableSubMap(two, three);
653	>	NavigableMap sm = map.subMap(two, true, three, false);
654		assertEquals(1, sm.size());
655		assertEquals(two, sm.firstKey());
656		assertEquals(two, sm.lastKey());
#	Line 648 | Line 668 | public class TreeMapTest extends JSR166T
668		k = (Integer)(r.next());
669		assertEquals(two, k);
670		assertFalse(r.hasNext());
671	<
671	>
672		Iterator j = sm.keySet().iterator();
673		j.next();
674		j.remove();
#	Line 656 | Line 676 | public class TreeMapTest extends JSR166T
676		assertEquals(4, map.size());
677		assertEquals(0, sm.size());
678		assertTrue(sm.isEmpty());
679	<	assertTrue(sm.remove(three) == null);
679	>	assertSame(sm.remove(three), null);
680		assertEquals(4, map.size());
681		}
682
#	Line 665 | Line 685 | public class TreeMapTest extends JSR166T
685		*/
686		public void testHeadMapContents() {
687		TreeMap map = map5();
688	<	NavigableMap sm = map.navigableHeadMap(four);
688	>	NavigableMap sm = map.headMap(four, false);
689		assertTrue(sm.containsKey(one));
690		assertTrue(sm.containsKey(two));
691		assertTrue(sm.containsKey(three));
#	Line 691 | Line 711 | public class TreeMapTest extends JSR166T
711		*/
712		public void testTailMapContents() {
713		TreeMap map = map5();
714	<	NavigableMap sm = map.navigableTailMap(two);
714	>	NavigableMap sm = map.tailMap(two, true);
715		assertFalse(sm.containsKey(one));
716		assertTrue(sm.containsKey(two));
717		assertTrue(sm.containsKey(three));
#	Line 735 | Line 755 | public class TreeMapTest extends JSR166T
755		assertEquals("E", e.getValue());
756		assertFalse(i.hasNext());
757
758	<	NavigableMap ssm = sm.navigableTailMap(four);
758	>	NavigableMap ssm = sm.tailMap(four, true);
759		assertEquals(four, ssm.firstKey());
760		assertEquals(five, ssm.lastKey());
761	<	assertTrue(ssm.remove(four) != null);
761	>	assertEquals("D", ssm.remove(four));
762		assertEquals(1, ssm.size());
763		assertEquals(3, sm.size());
764		assertEquals(4, map.size());
765		}
766	<
766	>
767	>	Random rnd = new Random(666);
768	>	BitSet bs;
769	>
770	>	/**
771	>	* Submaps of submaps subdivide correctly
772	>	*/
773	>	public void testRecursiveSubMaps() throws Exception {
774	>	int mapSize = expensiveTests ? 1000 : 100;
775	>	Class cl = TreeMap.class;
776	>	NavigableMap<Integer, Integer> map = newMap(cl);
777	>	bs = new BitSet(mapSize);
778	>
779	>	populate(map, mapSize);
780	>	check(map,                 0, mapSize - 1, true);
781	>	check(map.descendingMap(), 0, mapSize - 1, false);
782	>
783	>	mutateMap(map, 0, mapSize - 1);
784	>	check(map,                 0, mapSize - 1, true);
785	>	check(map.descendingMap(), 0, mapSize - 1, false);
786	>
787	>	bashSubMap(map.subMap(0, true, mapSize, false),
788	>	0, mapSize - 1, true);
789	>	}
790	>
791	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
792	>	NavigableMap<Integer, Integer> result
793	>	= (NavigableMap<Integer, Integer>) cl.newInstance();
794	>	assertEquals(result.size(), 0);
795	>	assertFalse(result.keySet().iterator().hasNext());
796	>	return result;
797	>	}
798	>
799	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
800	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
801	>	int key = rnd.nextInt(limit);
802	>	put(map, key);
803	>	}
804	>	}
805	>
806	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
807	>	int size = map.size();
808	>	int rangeSize = max - min + 1;
809	>
810	>	// Remove a bunch of entries directly
811	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
812	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
813	>	}
814	>
815	>	// Remove a bunch of entries with iterator
816	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
817	>	if (rnd.nextBoolean()) {
818	>	bs.clear(it.next());
819	>	it.remove();
820	>	}
821	>	}
822	>
823	>	// Add entries till we're back to original size
824	>	while (map.size() < size) {
825	>	int key = min + rnd.nextInt(rangeSize);
826	>	assertTrue(key >= min && key<= max);
827	>	put(map, key);
828	>	}
829	>	}
830	>
831	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
832	>	int size = map.size();
833	>	int rangeSize = max - min + 1;
834	>
835	>	// Remove a bunch of entries directly
836	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
837	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
838	>	}
839	>
840	>	// Remove a bunch of entries with iterator
841	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
842	>	if (rnd.nextBoolean()) {
843	>	bs.clear(it.next());
844	>	it.remove();
845	>	}
846	>	}
847	>
848	>	// Add entries till we're back to original size
849	>	while (map.size() < size) {
850	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
851	>	if (key >= min && key<= max) {
852	>	put(map, key);
853	>	} else {
854	>	try {
855	>	map.put(key, 2 * key);
856	>	shouldThrow();
857	>	} catch (IllegalArgumentException success) {}
858	>	}
859	>	}
860	>	}
861	>
862	>	void put(NavigableMap<Integer, Integer> map, int key) {
863	>	if (map.put(key, 2 * key) == null)
864	>	bs.set(key);
865	>	}
866	>
867	>	void remove(NavigableMap<Integer, Integer> map, int key) {
868	>	if (map.remove(key) != null)
869	>	bs.clear(key);
870	>	}
871	>
872	>	void bashSubMap(NavigableMap<Integer, Integer> map,
873	>	int min, int max, boolean ascending) {
874	>	check(map, min, max, ascending);
875	>	check(map.descendingMap(), min, max, !ascending);
876	>
877	>	mutateSubMap(map, min, max);
878	>	check(map, min, max, ascending);
879	>	check(map.descendingMap(), min, max, !ascending);
880	>
881	>	// Recurse
882	>	if (max - min < 2)
883	>	return;
884	>	int midPoint = (min + max) / 2;
885	>
886	>	// headMap - pick direction and endpoint inclusion randomly
887	>	boolean incl = rnd.nextBoolean();
888	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
889	>	if (ascending) {
890	>	if (rnd.nextBoolean())
891	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
892	>	else
893	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
894	>	false);
895	>	} else {
896	>	if (rnd.nextBoolean())
897	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
898	>	else
899	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
900	>	true);
901	>	}
902	>
903	>	// tailMap - pick direction and endpoint inclusion randomly
904	>	incl = rnd.nextBoolean();
905	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
906	>	if (ascending) {
907	>	if (rnd.nextBoolean())
908	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
909	>	else
910	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
911	>	false);
912	>	} else {
913	>	if (rnd.nextBoolean()) {
914	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
915	>	} else {
916	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
917	>	true);
918	>	}
919	>	}
920	>
921	>	// subMap - pick direction and endpoint inclusion randomly
922	>	int rangeSize = max - min + 1;
923	>	int[] endpoints = new int[2];
924	>	endpoints[0] = min + rnd.nextInt(rangeSize);
925	>	endpoints[1] = min + rnd.nextInt(rangeSize);
926	>	Arrays.sort(endpoints);
927	>	boolean lowIncl = rnd.nextBoolean();
928	>	boolean highIncl = rnd.nextBoolean();
929	>	if (ascending) {
930	>	NavigableMap<Integer,Integer> sm = map.subMap(
931	>	endpoints[0], lowIncl, endpoints[1], highIncl);
932	>	if (rnd.nextBoolean())
933	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
934	>	endpoints[1] - (highIncl ? 0 : 1), true);
935	>	else
936	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
937	>	endpoints[1] - (highIncl ? 0 : 1), false);
938	>	} else {
939	>	NavigableMap<Integer,Integer> sm = map.subMap(
940	>	endpoints[1], highIncl, endpoints[0], lowIncl);
941	>	if (rnd.nextBoolean())
942	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
943	>	endpoints[1] - (highIncl ? 0 : 1), false);
944	>	else
945	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
946	>	endpoints[1] - (highIncl ? 0 : 1), true);
947	>	}
948	>	}
949	>
950	>	/**
951	>	* min and max are both inclusive.  If max < min, interval is empty.
952	>	*/
953	>	void check(NavigableMap<Integer, Integer> map,
954	>	final int min, final int max, final boolean ascending) {
955	>	class ReferenceSet {
956	>	int lower(int key) {
957	>	return ascending ? lowerAscending(key) : higherAscending(key);
958	>	}
959	>	int floor(int key) {
960	>	return ascending ? floorAscending(key) : ceilingAscending(key);
961	>	}
962	>	int ceiling(int key) {
963	>	return ascending ? ceilingAscending(key) : floorAscending(key);
964	>	}
965	>	int higher(int key) {
966	>	return ascending ? higherAscending(key) : lowerAscending(key);
967	>	}
968	>	int first() {
969	>	return ascending ? firstAscending() : lastAscending();
970	>	}
971	>	int last() {
972	>	return ascending ? lastAscending() : firstAscending();
973	>	}
974	>	int lowerAscending(int key) {
975	>	return floorAscending(key - 1);
976	>	}
977	>	int floorAscending(int key) {
978	>	if (key < min)
979	>	return -1;
980	>	else if (key > max)
981	>	key = max;
982	>
983	>	// BitSet should support this! Test would run much faster
984	>	while (key >= min) {
985	>	if (bs.get(key))
986	>	return key;
987	>	key--;
988	>	}
989	>	return -1;
990	>	}
991	>	int ceilingAscending(int key) {
992	>	if (key < min)
993	>	key = min;
994	>	else if (key > max)
995	>	return -1;
996	>	int result = bs.nextSetBit(key);
997	>	return result > max ? -1 : result;
998	>	}
999	>	int higherAscending(int key) {
1000	>	return ceilingAscending(key + 1);
1001	>	}
1002	>	private int firstAscending() {
1003	>	int result = ceilingAscending(min);
1004	>	return result > max ? -1 : result;
1005	>	}
1006	>	private int lastAscending() {
1007	>	int result = floorAscending(max);
1008	>	return result < min ? -1 : result;
1009	>	}
1010	>	}
1011	>	ReferenceSet rs = new ReferenceSet();
1012	>
1013	>	// Test contents using containsKey
1014	>	int size = 0;
1015	>	for (int i = min; i <= max; i++) {
1016	>	boolean bsContainsI = bs.get(i);
1017	>	assertEquals(bsContainsI, map.containsKey(i));
1018	>	if (bsContainsI)
1019	>	size++;
1020	>	}
1021	>	assertEquals(map.size(), size);
1022	>
1023	>	// Test contents using contains keySet iterator
1024	>	int size2 = 0;
1025	>	int previousKey = -1;
1026	>	for (int key : map.keySet()) {
1027	>	assertTrue(bs.get(key));
1028	>	size2++;
1029	>	assertTrue(previousKey < 0 ||
1030	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1031	>	previousKey = key;
1032	>	}
1033	>	assertEquals(size2, size);
1034	>
1035	>	// Test navigation ops
1036	>	for (int key = min - 1; key <= max + 1; key++) {
1037	>	assertEq(map.lowerKey(key), rs.lower(key));
1038	>	assertEq(map.floorKey(key), rs.floor(key));
1039	>	assertEq(map.higherKey(key), rs.higher(key));
1040	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1041	>	}
1042	>
1043	>	// Test extrema
1044	>	if (map.size() != 0) {
1045	>	assertEq(map.firstKey(), rs.first());
1046	>	assertEq(map.lastKey(), rs.last());
1047	>	} else {
1048	>	assertEq(rs.first(), -1);
1049	>	assertEq(rs.last(),  -1);
1050	>	try {
1051	>	map.firstKey();
1052	>	shouldThrow();
1053	>	} catch (NoSuchElementException success) {}
1054	>	try {
1055	>	map.lastKey();
1056	>	shouldThrow();
1057	>	} catch (NoSuchElementException success) {}
1058	>	}
1059	>	}
1060	>
1061	>	static void assertEq(Integer i, int j) {
1062	>	if (i == null)
1063	>	assertEquals(j, -1);
1064	>	else
1065	>	assertEquals((int) i, j);
1066	>	}
1067	>
1068	>	static boolean eq(Integer i, int j) {
1069	>	return i == null ? j == -1 : i == j;
1070	>	}
1071	>
1072		}

Diff Legend

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