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

Diff Legend

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