ViewVC Help

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

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

Comparing jsr166/src/test/tck/ConcurrentSkipListMapTest.java (file contents):
Revision 1.5 by dl, Sat Oct 1 17:05:38 2005 UTC vs.
Revision 1.19 by jsr166, Wed Sep 1 20:12:39 2010 UTC

#	Line 11 | Line 11 | import java.io.*;
11
12		public class ConcurrentSkipListMapTest 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(ConcurrentSkipListMapTest.class);
17	>	return new TestSuite(ConcurrentSkipListMapTest.class);
18		}
19
20		/**
21		* Create a map from Integers 1-5 to Strings "A"-"E".
22		*/
23	<	private static ConcurrentSkipListMap map5() {
24	<	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
23	>	private static ConcurrentSkipListMap map5() {
24	>	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
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		/**
#	Line 38 | Line 38 | public class ConcurrentSkipListMapTest e
38		*/
39		public void testClear() {
40		ConcurrentSkipListMap 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		ConcurrentSkipListMap map = map5();
#	Line 59 | Line 59 | public class ConcurrentSkipListMapTest e
59		ConcurrentSkipListMap 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		}
#	Line 69 | Line 69 | public class ConcurrentSkipListMapTest e
69		*/
70		public void testContainsKey() {
71		ConcurrentSkipListMap map = map5();
72	<	assertTrue(map.containsKey(one));
72	>	assertTrue(map.containsKey(one));
73		assertFalse(map.containsKey(zero));
74		}
75
#	Line 78 | Line 78 | public class ConcurrentSkipListMapTest e
78		*/
79		public void testContainsValue() {
80		ConcurrentSkipListMap map = map5();
81	<	assertTrue(map.containsValue("A"));
81	>	assertTrue(map.containsValue("A"));
82		assertFalse(map.containsValue("Z"));
83		}
84
#	Line 88 | Line 88 | public class ConcurrentSkipListMapTest e
88		*/
89		public void testGet() {
90		ConcurrentSkipListMap map = map5();
91	<	assertEquals("A", (String)map.get(one));
91	>	assertEquals("A", (String)map.get(one));
92		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
93		assertNull(empty.get(one));
94		}
#	Line 99 | Line 99 | public class ConcurrentSkipListMapTest e
99		public void testIsEmpty() {
100		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
101		ConcurrentSkipListMap map = map5();
102	<	assertTrue(empty.isEmpty());
102	>	assertTrue(empty.isEmpty());
103		assertFalse(map.isEmpty());
104		}
105
#	Line 108 | Line 108 | public class ConcurrentSkipListMapTest e
108		*/
109		public void testFirstKey() {
110		ConcurrentSkipListMap map = map5();
111	<	assertEquals(one, map.firstKey());
111	>	assertEquals(one, map.firstKey());
112		}
113
114		/**
#	Line 116 | Line 116 | public class ConcurrentSkipListMapTest e
116		*/
117		public void testLastKey() {
118		ConcurrentSkipListMap map = map5();
119	<	assertEquals(five, map.lastKey());
119	>	assertEquals(five, map.lastKey());
120		}
121
122
#	Line 125 | Line 125 | public class ConcurrentSkipListMapTest e
125		*/
126		public void testKeySetToArray() {
127		ConcurrentSkipListMap 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		}
#	Line 138 | Line 138 | public class ConcurrentSkipListMapTest e
138		*/
139		public void testDescendingKeySetToArray() {
140		ConcurrentSkipListMap 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)));
#	Line 151 | Line 151 | public class ConcurrentSkipListMapTest e
151		*/
152		public void testKeySet() {
153		ConcurrentSkipListMap 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		/**
#	Line 165 | Line 165 | public class ConcurrentSkipListMapTest e
165		*/
166		public void testKeySetOrder() {
167		ConcurrentSkipListMap 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	+	* descending iterator of key set is inverse ordered
184	+	*/
185	+	public void testKeySetDescendingIteratorOrder() {
186	+	ConcurrentSkipListMap 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		/**
#	Line 181 | Line 203 | public class ConcurrentSkipListMapTest e
203		*/
204		public void testDescendingKeySetOrder() {
205		ConcurrentSkipListMap 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	+	ConcurrentSkipListMap 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		/**
240		*  Values.toArray contains all values
241		*/
242		public void testValuesToArray() {
243		ConcurrentSkipListMap map = map5();
244	<	Collection v = map.values();
244	>	Collection v = map.values();
245		Object[] ar = v.toArray();
246		ArrayList s = new ArrayList(Arrays.asList(ar));
247	<	assertEquals(5, ar.length);
248	<	assertTrue(s.contains("A"));
249	<	assertTrue(s.contains("B"));
250	<	assertTrue(s.contains("C"));
251	<	assertTrue(s.contains("D"));
252	<	assertTrue(s.contains("E"));
247	>	assertEquals(5, ar.length);
248	>	assertTrue(s.contains("A"));
249	>	assertTrue(s.contains("B"));
250	>	assertTrue(s.contains("C"));
251	>	assertTrue(s.contains("D"));
252	>	assertTrue(s.contains("E"));
253		}
254
255		/**
#	Line 214 | Line 257 | public class ConcurrentSkipListMapTest e
257		*/
258		public void testValues() {
259		ConcurrentSkipListMap map = map5();
260	<	Collection s = map.values();
261	<	assertEquals(5, s.size());
262	<	assertTrue(s.contains("A"));
263	<	assertTrue(s.contains("B"));
264	<	assertTrue(s.contains("C"));
265	<	assertTrue(s.contains("D"));
266	<	assertTrue(s.contains("E"));
260	>	Collection s = map.values();
261	>	assertEquals(5, s.size());
262	>	assertTrue(s.contains("A"));
263	>	assertTrue(s.contains("B"));
264	>	assertTrue(s.contains("C"));
265	>	assertTrue(s.contains("D"));
266	>	assertTrue(s.contains("E"));
267		}
268
269		/**
#	Line 228 | Line 271 | public class ConcurrentSkipListMapTest e
271		*/
272		public void testEntrySet() {
273		ConcurrentSkipListMap map = map5();
274	<	Set s = map.entrySet();
275	<	assertEquals(5, s.size());
274	>	Set s = map.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 247 | Line 290 | public class ConcurrentSkipListMapTest e
290		*/
291		public void testDescendingEntrySet() {
292		ConcurrentSkipListMap map = map5();
293	<	Set s = map.descendingEntrySet();
294	<	assertEquals(5, s.size());
293	>	Set s = map.descendingMap().entrySet();
294	>	assertEquals(5, s.size());
295		Iterator it = s.iterator();
296		while (it.hasNext()) {
297		Map.Entry e = (Map.Entry) it.next();
298	<	assertTrue(
298	>	assertTrue(
299		(e.getKey().equals(one) && e.getValue().equals("A")) ||
300		(e.getKey().equals(two) && e.getValue().equals("B")) ||
301		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 266 | Line 309 | public class ConcurrentSkipListMapTest e
309		*/
310		public void testEntrySetToArray() {
311		ConcurrentSkipListMap map = map5();
312	<	Set s = map.entrySet();
312	>	Set s = map.entrySet();
313		Object[] ar = s.toArray();
314		assertEquals(5, ar.length);
315		for (int i = 0; i < 5; ++i) {
#	Line 280 | Line 323 | public class ConcurrentSkipListMapTest e
323		*/
324		public void testDescendingEntrySetToArray() {
325		ConcurrentSkipListMap map = map5();
326	<	Set s = map.descendingEntrySet();
326	>	Set s = map.descendingMap().entrySet();
327		Object[] ar = s.toArray();
328		assertEquals(5, ar.length);
329		for (int i = 0; i < 5; ++i) {
#	Line 295 | Line 338 | public class ConcurrentSkipListMapTest e
338		public void testPutAll() {
339		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
340		ConcurrentSkipListMap map = map5();
341	<	empty.putAll(map);
342	<	assertEquals(5, empty.size());
343	<	assertTrue(empty.containsKey(one));
344	<	assertTrue(empty.containsKey(two));
345	<	assertTrue(empty.containsKey(three));
346	<	assertTrue(empty.containsKey(four));
347	<	assertTrue(empty.containsKey(five));
341	>	empty.putAll(map);
342	>	assertEquals(5, empty.size());
343	>	assertTrue(empty.containsKey(one));
344	>	assertTrue(empty.containsKey(two));
345	>	assertTrue(empty.containsKey(three));
346	>	assertTrue(empty.containsKey(four));
347	>	assertTrue(empty.containsKey(five));
348		}
349
350		/**
#	Line 309 | Line 352 | public class ConcurrentSkipListMapTest e
352		*/
353		public void testPutIfAbsent() {
354		ConcurrentSkipListMap map = map5();
355	<	map.putIfAbsent(six, "Z");
355	>	map.putIfAbsent(six, "Z");
356		assertTrue(map.containsKey(six));
357		}
358
#	Line 326 | Line 369 | public class ConcurrentSkipListMapTest e
369		*/
370		public void testReplace() {
371		ConcurrentSkipListMap map = map5();
372	<	assertNull(map.replace(six, "Z"));
372	>	assertNull(map.replace(six, "Z"));
373		assertFalse(map.containsKey(six));
374		}
375
#	Line 346 | Line 389 | public class ConcurrentSkipListMapTest e
389		public void testReplaceValue() {
390		ConcurrentSkipListMap map = map5();
391		assertEquals("A", map.get(one));
392	<	assertFalse(map.replace(one, "Z", "Z"));
392	>	assertFalse(map.replace(one, "Z", "Z"));
393		assertEquals("A", map.get(one));
394		}
395
#	Line 356 | Line 399 | public class ConcurrentSkipListMapTest e
399		public void testReplaceValue2() {
400		ConcurrentSkipListMap map = map5();
401		assertEquals("A", map.get(one));
402	<	assertTrue(map.replace(one, "A", "Z"));
402	>	assertTrue(map.replace(one, "A", "Z"));
403		assertEquals("Z", map.get(one));
404		}
405
#	Line 366 | Line 409 | public class ConcurrentSkipListMapTest e
409		*/
410		public void testRemove() {
411		ConcurrentSkipListMap map = map5();
412	<	map.remove(five);
413	<	assertEquals(4, map.size());
414	<	assertFalse(map.containsKey(five));
412	>	map.remove(five);
413	>	assertEquals(4, map.size());
414	>	assertFalse(map.containsKey(five));
415		}
416
417		/**
#	Line 376 | Line 419 | public class ConcurrentSkipListMapTest e
419		*/
420		public void testRemove2() {
421		ConcurrentSkipListMap map = map5();
422	<	assertTrue(map.containsKey(five));
422	>	assertTrue(map.containsKey(five));
423		assertEquals("E", map.get(five));
424	<	map.remove(five, "E");
425	<	assertEquals(4, map.size());
426	<	assertFalse(map.containsKey(five));
427	<	map.remove(four, "A");
428	<	assertEquals(4, map.size());
429	<	assertTrue(map.containsKey(four));
387	<
424	>	map.remove(five, "E");
425	>	assertEquals(4, map.size());
426	>	assertFalse(map.containsKey(five));
427	>	map.remove(four, "A");
428	>	assertEquals(4, map.size());
429	>	assertTrue(map.containsKey(four));
430		}
431
432		/**
#	Line 403 | Line 445 | public class ConcurrentSkipListMapTest e
445
446		Map.Entry e4 = map.lowerEntry(zero);
447		assertNull(e4);
406	–
448		}
449
450		/**
#	Line 422 | Line 463 | public class ConcurrentSkipListMapTest e
463
464		Map.Entry e4 = map.higherEntry(six);
465		assertNull(e4);
425	–
466		}
467
468		/**
#	Line 441 | Line 481 | public class ConcurrentSkipListMapTest e
481
482		Map.Entry e4 = map.floorEntry(zero);
483		assertNull(e4);
444	–
484		}
485
486		/**
#	Line 460 | Line 499 | public class ConcurrentSkipListMapTest e
499
500		Map.Entry e4 = map.ceilingEntry(six);
501		assertNull(e4);
463	–
502		}
503
504		/**
505		* lowerEntry, higherEntry, ceilingEntry, and floorEntry return
506	<	* imutable entries
506	>	* immutable entries
507		*/
508		public void testEntryImmutablity() {
509		ConcurrentSkipListMap map = map5();
#	Line 473 | Line 511 | public class ConcurrentSkipListMapTest e
511		assertEquals(two, e.getKey());
512		try {
513		e.setValue("X");
514	<	fail();
515	<	} catch(UnsupportedOperationException success) {}
514	>	shouldThrow();
515	>	} catch (UnsupportedOperationException success) {}
516		e = map.higherEntry(zero);
517		assertEquals(one, e.getKey());
518		try {
519		e.setValue("X");
520	<	fail();
521	<	} catch(UnsupportedOperationException success) {}
520	>	shouldThrow();
521	>	} catch (UnsupportedOperationException success) {}
522		e = map.floorEntry(one);
523		assertEquals(one, e.getKey());
524		try {
525		e.setValue("X");
526	<	fail();
527	<	} catch(UnsupportedOperationException success) {}
526	>	shouldThrow();
527	>	} catch (UnsupportedOperationException success) {}
528		e = map.ceilingEntry(five);
529		assertEquals(five, e.getKey());
530		try {
531		e.setValue("X");
532	<	fail();
533	<	} catch(UnsupportedOperationException success) {}
532	>	shouldThrow();
533	>	} catch (UnsupportedOperationException success) {}
534		}
535
536
#	Line 513 | Line 551 | public class ConcurrentSkipListMapTest e
551
552		Object e4 = q.lowerKey(zero);
553		assertNull(e4);
516	–
554		}
555
556		/**
#	Line 532 | Line 569 | public class ConcurrentSkipListMapTest e
569
570		Object e4 = q.higherKey(six);
571		assertNull(e4);
535	–
572		}
573
574		/**
#	Line 551 | Line 587 | public class ConcurrentSkipListMapTest e
587
588		Object e4 = q.floorKey(zero);
589		assertNull(e4);
554	–
590		}
591
592		/**
#	Line 570 | Line 605 | public class ConcurrentSkipListMapTest e
605
606		Object e4 = q.ceilingKey(six);
607		assertNull(e4);
573	–
608		}
609
610		/**
#	Line 595 | Line 629 | public class ConcurrentSkipListMapTest e
629		try {
630		e.setValue("A");
631		shouldThrow();
632	<	} catch (Exception ok) {
599	<	}
632	>	} catch (UnsupportedOperationException success) {}
633		e = map.pollFirstEntry();
634		assertNull(e);
635		}
#	Line 623 | Line 656 | public class ConcurrentSkipListMapTest e
656		try {
657		e.setValue("E");
658		shouldThrow();
659	<	} catch (Exception ok) {
627	<	}
659	>	} catch (UnsupportedOperationException success) {}
660		e = map.pollLastEntry();
661		assertNull(e);
662		}
#	Line 635 | Line 667 | public class ConcurrentSkipListMapTest e
667		public void testSize() {
668		ConcurrentSkipListMap map = map5();
669		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
670	<	assertEquals(0, empty.size());
671	<	assertEquals(5, map.size());
670	>	assertEquals(0, empty.size());
671	>	assertEquals(5, map.size());
672		}
673
674		/**
#	Line 648 | Line 680 | public class ConcurrentSkipListMapTest e
680		for (int i = 1; i <= 5; ++i) {
681		assertTrue(s.indexOf(String.valueOf(i)) >= 0);
682		}
683	<	}
683	>	}
684
685		// Exception tests
686
#	Line 660 | Line 692 | public class ConcurrentSkipListMapTest e
692		ConcurrentSkipListMap c = map5();
693		c.get(null);
694		shouldThrow();
695	<	} catch(NullPointerException e){}
695	>	} catch (NullPointerException success) {}
696		}
697
698		/**
#	Line 671 | Line 703 | public class ConcurrentSkipListMapTest e
703		ConcurrentSkipListMap c = map5();
704		c.containsKey(null);
705		shouldThrow();
706	<	} catch(NullPointerException e){}
706	>	} catch (NullPointerException success) {}
707		}
708
709		/**
#	Line 682 | Line 714 | public class ConcurrentSkipListMapTest e
714		ConcurrentSkipListMap c = new ConcurrentSkipListMap();
715		c.containsValue(null);
716		shouldThrow();
717	<	} catch(NullPointerException e){}
717	>	} catch (NullPointerException success) {}
718		}
719
720
#	Line 694 | Line 726 | public class ConcurrentSkipListMapTest e
726		ConcurrentSkipListMap c = map5();
727		c.put(null, "whatever");
728		shouldThrow();
729	<	} catch(NullPointerException e){}
729	>	} catch (NullPointerException success) {}
730		}
731
732		/**
#	Line 705 | Line 737 | public class ConcurrentSkipListMapTest e
737		ConcurrentSkipListMap c = map5();
738		c.putIfAbsent(null, "whatever");
739		shouldThrow();
740	<	} catch(NullPointerException e){}
740	>	} catch (NullPointerException success) {}
741		}
742
743		/**
#	Line 716 | Line 748 | public class ConcurrentSkipListMapTest e
748		ConcurrentSkipListMap c = map5();
749		c.replace(null, "whatever");
750		shouldThrow();
751	<	} catch(NullPointerException e){}
751	>	} catch (NullPointerException success) {}
752		}
753
754		/**
#	Line 727 | Line 759 | public class ConcurrentSkipListMapTest e
759		ConcurrentSkipListMap c = map5();
760		c.replace(null, one, "whatever");
761		shouldThrow();
762	<	} catch(NullPointerException e){}
762	>	} catch (NullPointerException success) {}
763		}
764
765		/**
#	Line 739 | Line 771 | public class ConcurrentSkipListMapTest e
771		c.put("sadsdf", "asdads");
772		c.remove(null);
773		shouldThrow();
774	<	} catch(NullPointerException e){}
774	>	} catch (NullPointerException success) {}
775		}
776
777		/**
#	Line 751 | Line 783 | public class ConcurrentSkipListMapTest e
783		c.put("sadsdf", "asdads");
784		c.remove(null, "whatever");
785		shouldThrow();
786	<	} catch(NullPointerException e){}
786	>	} catch (NullPointerException success) {}
787		}
788
789		/**
790		* remove(x, null) returns false
791		*/
792		public void testRemove3() {
793	<	try {
794	<	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
795	<	c.put("sadsdf", "asdads");
764	<	assertFalse(c.remove("sadsdf", null));
765	<	} catch(NullPointerException e){
766	<	fail();
767	<	}
793	>	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
794	>	c.put("sadsdf", "asdads");
795	>	assertFalse(c.remove("sadsdf", null));
796		}
797
798		/**
799		* A deserialized map equals original
800		*/
801	<	public void testSerialization() {
801	>	public void testSerialization() throws Exception {
802		ConcurrentSkipListMap q = map5();
803
804	<	try {
805	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
806	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
807	<	out.writeObject(q);
808	<	out.close();
809	<
810	<	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
811	<	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
812	<	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
813	<	assertEquals(q.size(), r.size());
814	<	assertTrue(q.equals(r));
787	<	assertTrue(r.equals(q));
788	<	} catch(Exception e){
789	<	e.printStackTrace();
790	<	unexpectedException();
791	<	}
804	>	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
805	>	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
806	>	out.writeObject(q);
807	>	out.close();
808	>
809	>	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
810	>	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
811	>	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
812	>	assertEquals(q.size(), r.size());
813	>	assertTrue(q.equals(r));
814	>	assertTrue(r.equals(q));
815		}
816
817
#	Line 798 | Line 821 | public class ConcurrentSkipListMapTest e
821		*/
822		public void testSubMapContents() {
823		ConcurrentSkipListMap map = map5();
824	<	NavigableMap sm = map.navigableSubMap(two, four);
824	>	NavigableMap sm = map.subMap(two, true, four, false);
825		assertEquals(two, sm.firstKey());
826		assertEquals(three, sm.lastKey());
827		assertEquals(2, sm.size());
#	Line 820 | Line 843 | public class ConcurrentSkipListMapTest e
843		k = (Integer)(r.next());
844		assertEquals(two, k);
845		assertFalse(r.hasNext());
846	<
846	>
847		Iterator j = sm.keySet().iterator();
848		j.next();
849		j.remove();
#	Line 829 | Line 852 | public class ConcurrentSkipListMapTest e
852		assertEquals(1, sm.size());
853		assertEquals(three, sm.firstKey());
854		assertEquals(three, sm.lastKey());
855	<	assertTrue(sm.remove(three) != null);
855	>	assertEquals("C", sm.remove(three));
856		assertTrue(sm.isEmpty());
857		assertEquals(3, map.size());
858		}
859
860		public void testSubMapContents2() {
861		ConcurrentSkipListMap map = map5();
862	<	NavigableMap sm = map.navigableSubMap(two, three);
862	>	NavigableMap sm = map.subMap(two, true, three, false);
863		assertEquals(1, sm.size());
864		assertEquals(two, sm.firstKey());
865		assertEquals(two, sm.lastKey());
#	Line 854 | Line 877 | public class ConcurrentSkipListMapTest e
877		k = (Integer)(r.next());
878		assertEquals(two, k);
879		assertFalse(r.hasNext());
880	<
880	>
881		Iterator j = sm.keySet().iterator();
882		j.next();
883		j.remove();
#	Line 862 | Line 885 | public class ConcurrentSkipListMapTest e
885		assertEquals(4, map.size());
886		assertEquals(0, sm.size());
887		assertTrue(sm.isEmpty());
888	<	assertTrue(sm.remove(three) == null);
888	>	assertSame(sm.remove(three), null);
889		assertEquals(4, map.size());
890		}
891
#	Line 871 | Line 894 | public class ConcurrentSkipListMapTest e
894		*/
895		public void testHeadMapContents() {
896		ConcurrentSkipListMap map = map5();
897	<	NavigableMap sm = map.navigableHeadMap(four);
897	>	NavigableMap sm = map.headMap(four, false);
898		assertTrue(sm.containsKey(one));
899		assertTrue(sm.containsKey(two));
900		assertTrue(sm.containsKey(three));
#	Line 893 | Line 916 | public class ConcurrentSkipListMapTest e
916		}
917
918		/**
919	<	* headMap returns map with keys in requested range
919	>	* tailMap returns map with keys in requested range
920		*/
921		public void testTailMapContents() {
922		ConcurrentSkipListMap map = map5();
923	<	NavigableMap sm = map.navigableTailMap(two);
923	>	NavigableMap sm = map.tailMap(two, true);
924		assertFalse(sm.containsKey(one));
925		assertTrue(sm.containsKey(two));
926		assertTrue(sm.containsKey(three));
#	Line 941 | Line 964 | public class ConcurrentSkipListMapTest e
964		assertEquals("E", e.getValue());
965		assertFalse(i.hasNext());
966
967	<	NavigableMap ssm = sm.navigableTailMap(four);
967	>	NavigableMap ssm = sm.tailMap(four, true);
968		assertEquals(four, ssm.firstKey());
969		assertEquals(five, ssm.lastKey());
970	<	assertTrue(ssm.remove(four) != null);
970	>	assertEquals("D", ssm.remove(four));
971		assertEquals(1, ssm.size());
972		assertEquals(3, sm.size());
973		assertEquals(4, map.size());
974		}
975	<
975	>
976	>	Random rnd = new Random(666);
977	>	BitSet bs;
978	>
979	>	/**
980	>	* Submaps of submaps subdivide correctly
981	>	*/
982	>	public void testRecursiveSubMaps() throws Exception {
983	>	int mapSize = 1000;
984	>	Class cl = ConcurrentSkipListMap.class;
985	>	NavigableMap<Integer, Integer> map = newMap(cl);
986	>	bs = new BitSet(mapSize);
987	>
988	>	populate(map, mapSize);
989	>	check(map,                 0, mapSize - 1, true);
990	>	check(map.descendingMap(), 0, mapSize - 1, false);
991	>
992	>	mutateMap(map, 0, mapSize - 1);
993	>	check(map,                 0, mapSize - 1, true);
994	>	check(map.descendingMap(), 0, mapSize - 1, false);
995	>
996	>	bashSubMap(map.subMap(0, true, mapSize, false),
997	>	0, mapSize - 1, true);
998	>	}
999	>
1000	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
1001	>	NavigableMap<Integer, Integer> result =
1002	>	(NavigableMap<Integer, Integer>) cl.newInstance();
1003	>	assertEquals(result.size(), 0);
1004	>	assertFalse(result.keySet().iterator().hasNext());
1005	>	return result;
1006	>	}
1007	>
1008	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
1009	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
1010	>	int key = rnd.nextInt(limit);
1011	>	put(map, key);
1012	>	}
1013	>	}
1014	>
1015	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1016	>	int size = map.size();
1017	>	int rangeSize = max - min + 1;
1018	>
1019	>	// Remove a bunch of entries directly
1020	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1021	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1022	>	}
1023	>
1024	>	// Remove a bunch of entries with iterator
1025	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1026	>	if (rnd.nextBoolean()) {
1027	>	bs.clear(it.next());
1028	>	it.remove();
1029	>	}
1030	>	}
1031	>
1032	>	// Add entries till we're back to original size
1033	>	while (map.size() < size) {
1034	>	int key = min + rnd.nextInt(rangeSize);
1035	>	assertTrue(key >= min && key<= max);
1036	>	put(map, key);
1037	>	}
1038	>	}
1039	>
1040	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1041	>	int size = map.size();
1042	>	int rangeSize = max - min + 1;
1043	>
1044	>	// Remove a bunch of entries directly
1045	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1046	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1047	>	}
1048	>
1049	>	// Remove a bunch of entries with iterator
1050	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1051	>	if (rnd.nextBoolean()) {
1052	>	bs.clear(it.next());
1053	>	it.remove();
1054	>	}
1055	>	}
1056	>
1057	>	// Add entries till we're back to original size
1058	>	while (map.size() < size) {
1059	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
1060	>	if (key >= min && key<= max) {
1061	>	put(map, key);
1062	>	} else {
1063	>	try {
1064	>	map.put(key, 2 * key);
1065	>	shouldThrow();
1066	>	} catch (IllegalArgumentException success) {}
1067	>	}
1068	>	}
1069	>	}
1070	>
1071	>	void put(NavigableMap<Integer, Integer> map, int key) {
1072	>	if (map.put(key, 2 * key) == null)
1073	>	bs.set(key);
1074	>	}
1075	>
1076	>	void remove(NavigableMap<Integer, Integer> map, int key) {
1077	>	if (map.remove(key) != null)
1078	>	bs.clear(key);
1079	>	}
1080	>
1081	>	void bashSubMap(NavigableMap<Integer, Integer> map,
1082	>	int min, int max, boolean ascending) {
1083	>	check(map, min, max, ascending);
1084	>	check(map.descendingMap(), min, max, !ascending);
1085	>
1086	>	mutateSubMap(map, min, max);
1087	>	check(map, min, max, ascending);
1088	>	check(map.descendingMap(), min, max, !ascending);
1089	>
1090	>	// Recurse
1091	>	if (max - min < 2)
1092	>	return;
1093	>	int midPoint = (min + max) / 2;
1094	>
1095	>	// headMap - pick direction and endpoint inclusion randomly
1096	>	boolean incl = rnd.nextBoolean();
1097	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1098	>	if (ascending) {
1099	>	if (rnd.nextBoolean())
1100	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1101	>	else
1102	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1103	>	false);
1104	>	} else {
1105	>	if (rnd.nextBoolean())
1106	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1107	>	else
1108	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1109	>	true);
1110	>	}
1111	>
1112	>	// tailMap - pick direction and endpoint inclusion randomly
1113	>	incl = rnd.nextBoolean();
1114	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1115	>	if (ascending) {
1116	>	if (rnd.nextBoolean())
1117	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1118	>	else
1119	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1120	>	false);
1121	>	} else {
1122	>	if (rnd.nextBoolean()) {
1123	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1124	>	} else {
1125	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1126	>	true);
1127	>	}
1128	>	}
1129	>
1130	>	// subMap - pick direction and endpoint inclusion randomly
1131	>	int rangeSize = max - min + 1;
1132	>	int[] endpoints = new int[2];
1133	>	endpoints[0] = min + rnd.nextInt(rangeSize);
1134	>	endpoints[1] = min + rnd.nextInt(rangeSize);
1135	>	Arrays.sort(endpoints);
1136	>	boolean lowIncl = rnd.nextBoolean();
1137	>	boolean highIncl = rnd.nextBoolean();
1138	>	if (ascending) {
1139	>	NavigableMap<Integer,Integer> sm = map.subMap(
1140	>	endpoints[0], lowIncl, endpoints[1], highIncl);
1141	>	if (rnd.nextBoolean())
1142	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1143	>	endpoints[1] - (highIncl ? 0 : 1), true);
1144	>	else
1145	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1146	>	endpoints[1] - (highIncl ? 0 : 1), false);
1147	>	} else {
1148	>	NavigableMap<Integer,Integer> sm = map.subMap(
1149	>	endpoints[1], highIncl, endpoints[0], lowIncl);
1150	>	if (rnd.nextBoolean())
1151	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1152	>	endpoints[1] - (highIncl ? 0 : 1), false);
1153	>	else
1154	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1155	>	endpoints[1] - (highIncl ? 0 : 1), true);
1156	>	}
1157	>	}
1158	>
1159	>	/**
1160	>	* min and max are both inclusive.  If max < min, interval is empty.
1161	>	*/
1162	>	void check(NavigableMap<Integer, Integer> map,
1163	>	final int min, final int max, final boolean ascending) {
1164	>	class ReferenceSet {
1165	>	int lower(int key) {
1166	>	return ascending ? lowerAscending(key) : higherAscending(key);
1167	>	}
1168	>	int floor(int key) {
1169	>	return ascending ? floorAscending(key) : ceilingAscending(key);
1170	>	}
1171	>	int ceiling(int key) {
1172	>	return ascending ? ceilingAscending(key) : floorAscending(key);
1173	>	}
1174	>	int higher(int key) {
1175	>	return ascending ? higherAscending(key) : lowerAscending(key);
1176	>	}
1177	>	int first() {
1178	>	return ascending ? firstAscending() : lastAscending();
1179	>	}
1180	>	int last() {
1181	>	return ascending ? lastAscending() : firstAscending();
1182	>	}
1183	>	int lowerAscending(int key) {
1184	>	return floorAscending(key - 1);
1185	>	}
1186	>	int floorAscending(int key) {
1187	>	if (key < min)
1188	>	return -1;
1189	>	else if (key > max)
1190	>	key = max;
1191	>
1192	>	// BitSet should support this! Test would run much faster
1193	>	while (key >= min) {
1194	>	if (bs.get(key))
1195	>	return key;
1196	>	key--;
1197	>	}
1198	>	return -1;
1199	>	}
1200	>	int ceilingAscending(int key) {
1201	>	if (key < min)
1202	>	key = min;
1203	>	else if (key > max)
1204	>	return -1;
1205	>	int result = bs.nextSetBit(key);
1206	>	return result > max ? -1 : result;
1207	>	}
1208	>	int higherAscending(int key) {
1209	>	return ceilingAscending(key + 1);
1210	>	}
1211	>	private int firstAscending() {
1212	>	int result = ceilingAscending(min);
1213	>	return result > max ? -1 : result;
1214	>	}
1215	>	private int lastAscending() {
1216	>	int result = floorAscending(max);
1217	>	return result < min ? -1 : result;
1218	>	}
1219	>	}
1220	>	ReferenceSet rs = new ReferenceSet();
1221	>
1222	>	// Test contents using containsKey
1223	>	int size = 0;
1224	>	for (int i = min; i <= max; i++) {
1225	>	boolean bsContainsI = bs.get(i);
1226	>	assertEquals(bsContainsI, map.containsKey(i));
1227	>	if (bsContainsI)
1228	>	size++;
1229	>	}
1230	>	assertEquals(map.size(), size);
1231	>
1232	>	// Test contents using contains keySet iterator
1233	>	int size2 = 0;
1234	>	int previousKey = -1;
1235	>	for (int key : map.keySet()) {
1236	>	assertTrue(bs.get(key));
1237	>	size2++;
1238	>	assertTrue(previousKey < 0 ||
1239	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1240	>	previousKey = key;
1241	>	}
1242	>	assertEquals(size2, size);
1243	>
1244	>	// Test navigation ops
1245	>	for (int key = min - 1; key <= max + 1; key++) {
1246	>	assertEq(map.lowerKey(key), rs.lower(key));
1247	>	assertEq(map.floorKey(key), rs.floor(key));
1248	>	assertEq(map.higherKey(key), rs.higher(key));
1249	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1250	>	}
1251	>
1252	>	// Test extrema
1253	>	if (map.size() != 0) {
1254	>	assertEq(map.firstKey(), rs.first());
1255	>	assertEq(map.lastKey(), rs.last());
1256	>	} else {
1257	>	assertEq(rs.first(), -1);
1258	>	assertEq(rs.last(),  -1);
1259	>	try {
1260	>	map.firstKey();
1261	>	shouldThrow();
1262	>	} catch (NoSuchElementException success) {}
1263	>	try {
1264	>	map.lastKey();
1265	>	shouldThrow();
1266	>	} catch (NoSuchElementException success) {}
1267	>	}
1268	>	}
1269	>
1270	>	static void assertEq(Integer i, int j) {
1271	>	if (i == null)
1272	>	assertEquals(j, -1);
1273	>	else
1274	>	assertEquals((int) i, j);
1275	>	}
1276	>
1277	>	static boolean eq(Integer i, int j) {
1278	>	return i == null ? j == -1 : i == j;
1279	>	}
1280	>
1281		}

Diff Legend

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