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.2 by dl, Tue Mar 22 01:30:22 2005 UTC vs.
Revision 1.29 by jsr166, Tue Feb 21 01:54:03 2012 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	>	import java.util.concurrent.ConcurrentSkipListMap;
10
11		public class ConcurrentSkipListMapTest extends JSR166TestCase {
12		public static void main(String[] args) {
13	<	junit.textui.TestRunner.run (suite());
13	>	junit.textui.TestRunner.run(suite());
14		}
15		public static Test suite() {
16	<	return new TestSuite(ConcurrentSkipListMapTest.class);
16	>	return new TestSuite(ConcurrentSkipListMapTest.class);
17		}
18
19		/**
20	<	* Create a map from Integers 1-5 to Strings "A"-"E".
20	>	* Creates a map from Integers 1-5 to Strings "A"-"E".
21		*/
22	<	private static ConcurrentSkipListMap map5() {
23	<	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
22	>	private static ConcurrentSkipListMap map5() {
23	>	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
24		assertTrue(map.isEmpty());
25	<	map.put(one, "A");
26	<	map.put(five, "E");
27	<	map.put(three, "C");
28	<	map.put(two, "B");
29	<	map.put(four, "D");
25	>	map.put(one, "A");
26	>	map.put(five, "E");
27	>	map.put(three, "C");
28	>	map.put(two, "B");
29	>	map.put(four, "D");
30		assertFalse(map.isEmpty());
31		assertEquals(5, map.size());
32	<	return map;
32	>	return map;
33		}
34
35		/**
36	<	*  clear removes all pairs
36	>	* clear removes all pairs
37		*/
38		public void testClear() {
39		ConcurrentSkipListMap map = map5();
40	<	map.clear();
41	<	assertEquals(map.size(), 0);
40	>	map.clear();
41	>	assertEquals(0, map.size());
42		}
43
44		/**
45	<	*
45	>	*
46		*/
47		public void testConstructFromSorted() {
48		ConcurrentSkipListMap map = map5();
#	Line 52 | Line 51 | public class ConcurrentSkipListMapTest e
51		}
52
53		/**
54	<	*  Maps with same contents are equal
54	>	* Maps with same contents are equal
55		*/
56		public void testEquals() {
57		ConcurrentSkipListMap map1 = map5();
58		ConcurrentSkipListMap map2 = map5();
59		assertEquals(map1, map2);
60		assertEquals(map2, map1);
61	<	map1.clear();
61	>	map1.clear();
62		assertFalse(map1.equals(map2));
63		assertFalse(map2.equals(map1));
64		}
65
66		/**
67	<	*  containsKey returns true for contained key
67	>	* containsKey returns true for contained key
68		*/
69		public void testContainsKey() {
70		ConcurrentSkipListMap map = map5();
71	<	assertTrue(map.containsKey(one));
71	>	assertTrue(map.containsKey(one));
72		assertFalse(map.containsKey(zero));
73		}
74
75		/**
76	<	*  containsValue returns true for held values
76	>	* containsValue returns true for held values
77		*/
78		public void testContainsValue() {
79		ConcurrentSkipListMap map = map5();
80	<	assertTrue(map.containsValue("A"));
80	>	assertTrue(map.containsValue("A"));
81		assertFalse(map.containsValue("Z"));
82		}
83
84		/**
85	<	*  get returns the correct element at the given key,
86	<	*  or null if not present
85	>	* get returns the correct element at the given key,
86	>	* or null if not present
87		*/
88		public void testGet() {
89		ConcurrentSkipListMap map = map5();
90	<	assertEquals("A", (String)map.get(one));
90	>	assertEquals("A", (String)map.get(one));
91		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
92		assertNull(empty.get(one));
93		}
94
95		/**
96	<	*  isEmpty is true of empty map and false for non-empty
96	>	* isEmpty is true of empty map and false for non-empty
97		*/
98		public void testIsEmpty() {
99		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
100		ConcurrentSkipListMap map = map5();
101	<	assertTrue(empty.isEmpty());
101	>	assertTrue(empty.isEmpty());
102		assertFalse(map.isEmpty());
103		}
104
105		/**
106	<	*   firstKey returns first key
106	>	* firstKey returns first key
107		*/
108		public void testFirstKey() {
109		ConcurrentSkipListMap map = map5();
110	<	assertEquals(one, map.firstKey());
110	>	assertEquals(one, map.firstKey());
111		}
112
113		/**
114	<	*   lastKey returns last key
114	>	* lastKey returns last key
115		*/
116		public void testLastKey() {
117		ConcurrentSkipListMap map = map5();
118	<	assertEquals(five, map.lastKey());
118	>	assertEquals(five, map.lastKey());
119		}
120
122	–
121		/**
122	<	*  keySet.toArray returns contains all keys
122	>	* keySet.toArray returns contains all keys
123		*/
124		public void testKeySetToArray() {
125		ConcurrentSkipListMap map = map5();
126	<	Set s = map.keySet();
126	>	Set s = map.keySet();
127		Object[] ar = s.toArray();
128		assertTrue(s.containsAll(Arrays.asList(ar)));
129	<	assertEquals(5, ar.length);
129	>	assertEquals(5, ar.length);
130		ar[0] = m10;
131		assertFalse(s.containsAll(Arrays.asList(ar)));
132		}
133
134		/**
135	<	*  descendingkeySet.toArray returns contains all keys
135	>	* descendingkeySet.toArray returns contains all keys
136		*/
137		public void testDescendingKeySetToArray() {
138		ConcurrentSkipListMap map = map5();
139	<	Set s = map.descendingKeySet();
139	>	Set s = map.descendingKeySet();
140		Object[] ar = s.toArray();
141	<	assertEquals(5, ar.length);
141	>	assertEquals(5, ar.length);
142		assertTrue(s.containsAll(Arrays.asList(ar)));
143		ar[0] = m10;
144		assertFalse(s.containsAll(Arrays.asList(ar)));
145		}
146
147		/**
148	<	*   keySet returns a Set containing all the keys
148	>	* keySet returns a Set containing all the keys
149		*/
150		public void testKeySet() {
151		ConcurrentSkipListMap map = map5();
152	<	Set s = map.keySet();
153	<	assertEquals(5, s.size());
154	<	assertTrue(s.contains(one));
155	<	assertTrue(s.contains(two));
156	<	assertTrue(s.contains(three));
157	<	assertTrue(s.contains(four));
158	<	assertTrue(s.contains(five));
152	>	Set s = map.keySet();
153	>	assertEquals(5, s.size());
154	>	assertTrue(s.contains(one));
155	>	assertTrue(s.contains(two));
156	>	assertTrue(s.contains(three));
157	>	assertTrue(s.contains(four));
158	>	assertTrue(s.contains(five));
159		}
160
161		/**
162	<	*   keySet is ordered
162	>	* keySet is ordered
163		*/
164		public void testKeySetOrder() {
165		ConcurrentSkipListMap map = map5();
166	<	Set s = map.keySet();
166	>	Set s = map.keySet();
167		Iterator i = s.iterator();
168		Integer last = (Integer)i.next();
169		assertEquals(last, one);
170	+	int count = 1;
171		while (i.hasNext()) {
172		Integer k = (Integer)i.next();
173		assertTrue(last.compareTo(k) < 0);
174		last = k;
175	+	++count;
176	+	}
177	+	assertEquals(5, count);
178	+	}
179	+
180	+	/**
181	+	* descending iterator of key set is inverse ordered
182	+	*/
183	+	public void testKeySetDescendingIteratorOrder() {
184	+	ConcurrentSkipListMap map = map5();
185	+	NavigableSet s = map.navigableKeySet();
186	+	Iterator i = s.descendingIterator();
187	+	Integer last = (Integer)i.next();
188	+	assertEquals(last, five);
189	+	int count = 1;
190	+	while (i.hasNext()) {
191	+	Integer k = (Integer)i.next();
192	+	assertTrue(last.compareTo(k) > 0);
193	+	last = k;
194	+	++count;
195		}
196	+	assertEquals(5, count);
197		}
198
199		/**
200	<	*   descendingKeySet is ordered
200	>	* descendingKeySet is ordered
201		*/
202		public void testDescendingKeySetOrder() {
203		ConcurrentSkipListMap map = map5();
204	<	Set s = map.descendingKeySet();
204	>	Set s = map.descendingKeySet();
205		Iterator i = s.iterator();
206		Integer last = (Integer)i.next();
207		assertEquals(last, five);
208	+	int count = 1;
209		while (i.hasNext()) {
210		Integer k = (Integer)i.next();
211		assertTrue(last.compareTo(k) > 0);
212		last = k;
213	+	++count;
214		}
215	+	assertEquals(5, count);
216	+	}
217	+
218	+	/**
219	+	* descending iterator of descendingKeySet is ordered
220	+	*/
221	+	public void testDescendingKeySetDescendingIteratorOrder() {
222	+	ConcurrentSkipListMap map = map5();
223	+	NavigableSet s = map.descendingKeySet();
224	+	Iterator i = s.descendingIterator();
225	+	Integer last = (Integer)i.next();
226	+	assertEquals(last, one);
227	+	int count = 1;
228	+	while (i.hasNext()) {
229	+	Integer k = (Integer)i.next();
230	+	assertTrue(last.compareTo(k) < 0);
231	+	last = k;
232	+	++count;
233	+	}
234	+	assertEquals(5, count);
235	+	}
236	+
237	+	/**
238	+	* Values.toArray contains all values
239	+	*/
240	+	public void testValuesToArray() {
241	+	ConcurrentSkipListMap map = map5();
242	+	Collection v = map.values();
243	+	Object[] ar = v.toArray();
244	+	ArrayList s = new ArrayList(Arrays.asList(ar));
245	+	assertEquals(5, ar.length);
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 197 | Line 255 | public class ConcurrentSkipListMapTest e
255		*/
256		public void testValues() {
257		ConcurrentSkipListMap map = map5();
258	<	Collection s = map.values();
259	<	assertEquals(5, s.size());
260	<	assertTrue(s.contains("A"));
261	<	assertTrue(s.contains("B"));
262	<	assertTrue(s.contains("C"));
263	<	assertTrue(s.contains("D"));
264	<	assertTrue(s.contains("E"));
258	>	Collection s = map.values();
259	>	assertEquals(5, s.size());
260	>	assertTrue(s.contains("A"));
261	>	assertTrue(s.contains("B"));
262	>	assertTrue(s.contains("C"));
263	>	assertTrue(s.contains("D"));
264	>	assertTrue(s.contains("E"));
265		}
266
267		/**
#	Line 211 | Line 269 | public class ConcurrentSkipListMapTest e
269		*/
270		public void testEntrySet() {
271		ConcurrentSkipListMap map = map5();
272	<	Set s = map.entrySet();
273	<	assertEquals(5, s.size());
272	>	Set s = map.entrySet();
273	>	assertEquals(5, s.size());
274		Iterator it = s.iterator();
275		while (it.hasNext()) {
276		Map.Entry e = (Map.Entry) it.next();
277	<	assertTrue(
277	>	assertTrue(
278		(e.getKey().equals(one) && e.getValue().equals("A")) ||
279		(e.getKey().equals(two) && e.getValue().equals("B")) ||
280		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 230 | Line 288 | public class ConcurrentSkipListMapTest e
288		*/
289		public void testDescendingEntrySet() {
290		ConcurrentSkipListMap map = map5();
291	<	Set s = map.descendingEntrySet();
292	<	assertEquals(5, s.size());
291	>	Set s = map.descendingMap().entrySet();
292	>	assertEquals(5, s.size());
293		Iterator it = s.iterator();
294		while (it.hasNext()) {
295		Map.Entry e = (Map.Entry) it.next();
296	<	assertTrue(
296	>	assertTrue(
297		(e.getKey().equals(one) && e.getValue().equals("A")) ||
298		(e.getKey().equals(two) && e.getValue().equals("B")) ||
299		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 245 | Line 303 | public class ConcurrentSkipListMapTest e
303		}
304
305		/**
306	<	*  entrySet.toArray contains all entries
306	>	* entrySet.toArray contains all entries
307		*/
308		public void testEntrySetToArray() {
309		ConcurrentSkipListMap map = map5();
310	<	Set s = map.entrySet();
310	>	Set s = map.entrySet();
311		Object[] ar = s.toArray();
312		assertEquals(5, ar.length);
313		for (int i = 0; i < 5; ++i) {
#	Line 259 | Line 317 | public class ConcurrentSkipListMapTest e
317		}
318
319		/**
320	<	*  descendingEntrySet.toArray contains all entries
320	>	* descendingEntrySet.toArray contains all entries
321		*/
322		public void testDescendingEntrySetToArray() {
323		ConcurrentSkipListMap map = map5();
324	<	Set s = map.descendingEntrySet();
324	>	Set s = map.descendingMap().entrySet();
325		Object[] ar = s.toArray();
326		assertEquals(5, ar.length);
327		for (int i = 0; i < 5; ++i) {
#	Line 273 | Line 331 | public class ConcurrentSkipListMapTest e
331		}
332
333		/**
334	<	*   putAll  adds all key-value pairs from the given map
334	>	* putAll adds all key-value pairs from the given map
335		*/
336		public void testPutAll() {
337		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
338		ConcurrentSkipListMap map = map5();
339	<	empty.putAll(map);
340	<	assertEquals(5, empty.size());
341	<	assertTrue(empty.containsKey(one));
342	<	assertTrue(empty.containsKey(two));
343	<	assertTrue(empty.containsKey(three));
344	<	assertTrue(empty.containsKey(four));
345	<	assertTrue(empty.containsKey(five));
339	>	empty.putAll(map);
340	>	assertEquals(5, empty.size());
341	>	assertTrue(empty.containsKey(one));
342	>	assertTrue(empty.containsKey(two));
343	>	assertTrue(empty.containsKey(three));
344	>	assertTrue(empty.containsKey(four));
345	>	assertTrue(empty.containsKey(five));
346		}
347
348		/**
349	<	*   putIfAbsent works when the given key is not present
349	>	* putIfAbsent works when the given key is not present
350		*/
351		public void testPutIfAbsent() {
352		ConcurrentSkipListMap map = map5();
353	<	map.putIfAbsent(six, "Z");
353	>	map.putIfAbsent(six, "Z");
354		assertTrue(map.containsKey(six));
355		}
356
357		/**
358	<	*   putIfAbsent does not add the pair if the key is already present
358	>	* putIfAbsent does not add the pair if the key is already present
359		*/
360		public void testPutIfAbsent2() {
361		ConcurrentSkipListMap map = map5();
#	Line 305 | Line 363 | public class ConcurrentSkipListMapTest e
363		}
364
365		/**
366	<	*   replace fails when the given key is not present
366	>	* replace fails when the given key is not present
367		*/
368		public void testReplace() {
369		ConcurrentSkipListMap map = map5();
370	<	assertNull(map.replace(six, "Z"));
370	>	assertNull(map.replace(six, "Z"));
371		assertFalse(map.containsKey(six));
372		}
373
374		/**
375	<	*   replace succeeds if the key is already present
375	>	* replace succeeds if the key is already present
376		*/
377		public void testReplace2() {
378		ConcurrentSkipListMap map = map5();
#	Line 322 | Line 380 | public class ConcurrentSkipListMapTest e
380		assertEquals("Z", map.get(one));
381		}
382
325	–
383		/**
384		* replace value fails when the given key not mapped to expected value
385		*/
386		public void testReplaceValue() {
387		ConcurrentSkipListMap map = map5();
388		assertEquals("A", map.get(one));
389	<	assertFalse(map.replace(one, "Z", "Z"));
389	>	assertFalse(map.replace(one, "Z", "Z"));
390		assertEquals("A", map.get(one));
391		}
392
#	Line 339 | Line 396 | public class ConcurrentSkipListMapTest e
396		public void testReplaceValue2() {
397		ConcurrentSkipListMap map = map5();
398		assertEquals("A", map.get(one));
399	<	assertTrue(map.replace(one, "A", "Z"));
399	>	assertTrue(map.replace(one, "A", "Z"));
400		assertEquals("Z", map.get(one));
401		}
402
346	–
403		/**
404	<	*   remove removes the correct key-value pair from the map
404	>	* remove removes the correct key-value pair from the map
405		*/
406		public void testRemove() {
407		ConcurrentSkipListMap map = map5();
408	<	map.remove(five);
409	<	assertEquals(4, map.size());
410	<	assertFalse(map.containsKey(five));
408	>	map.remove(five);
409	>	assertEquals(4, map.size());
410	>	assertFalse(map.containsKey(five));
411		}
412
413		/**
#	Line 359 | Line 415 | public class ConcurrentSkipListMapTest e
415		*/
416		public void testRemove2() {
417		ConcurrentSkipListMap map = map5();
418	<	assertTrue(map.containsKey(five));
418	>	assertTrue(map.containsKey(five));
419		assertEquals("E", map.get(five));
420	<	map.remove(five, "E");
421	<	assertEquals(4, map.size());
422	<	assertFalse(map.containsKey(five));
423	<	map.remove(four, "A");
424	<	assertEquals(4, map.size());
425	<	assertTrue(map.containsKey(four));
370	<
420	>	map.remove(five, "E");
421	>	assertEquals(4, map.size());
422	>	assertFalse(map.containsKey(five));
423	>	map.remove(four, "A");
424	>	assertEquals(4, map.size());
425	>	assertTrue(map.containsKey(four));
426		}
427
428		/**
#	Line 386 | Line 441 | public class ConcurrentSkipListMapTest e
441
442		Map.Entry e4 = map.lowerEntry(zero);
443		assertNull(e4);
389	–
444		}
445
446		/**
#	Line 405 | Line 459 | public class ConcurrentSkipListMapTest e
459
460		Map.Entry e4 = map.higherEntry(six);
461		assertNull(e4);
408	–
462		}
463
464		/**
#	Line 424 | Line 477 | public class ConcurrentSkipListMapTest e
477
478		Map.Entry e4 = map.floorEntry(zero);
479		assertNull(e4);
427	–
480		}
481
482		/**
#	Line 443 | Line 495 | public class ConcurrentSkipListMapTest e
495
496		Map.Entry e4 = map.ceilingEntry(six);
497		assertNull(e4);
446	–
498		}
499
500	+	/**
501	+	* lowerEntry, higherEntry, ceilingEntry, and floorEntry return
502	+	* immutable entries
503	+	*/
504	+	public void testEntryImmutability() {
505	+	ConcurrentSkipListMap map = map5();
506	+	Map.Entry e = map.lowerEntry(three);
507	+	assertEquals(two, e.getKey());
508	+	try {
509	+	e.setValue("X");
510	+	shouldThrow();
511	+	} catch (UnsupportedOperationException success) {}
512	+	e = map.higherEntry(zero);
513	+	assertEquals(one, e.getKey());
514	+	try {
515	+	e.setValue("X");
516	+	shouldThrow();
517	+	} catch (UnsupportedOperationException success) {}
518	+	e = map.floorEntry(one);
519	+	assertEquals(one, e.getKey());
520	+	try {
521	+	e.setValue("X");
522	+	shouldThrow();
523	+	} catch (UnsupportedOperationException success) {}
524	+	e = map.ceilingEntry(five);
525	+	assertEquals(five, e.getKey());
526	+	try {
527	+	e.setValue("X");
528	+	shouldThrow();
529	+	} catch (UnsupportedOperationException success) {}
530	+	}
531
532		/**
533		* lowerKey returns preceding element
#	Line 463 | Line 545 | public class ConcurrentSkipListMapTest e
545
546		Object e4 = q.lowerKey(zero);
547		assertNull(e4);
466	–
548		}
549
550		/**
#	Line 482 | Line 563 | public class ConcurrentSkipListMapTest e
563
564		Object e4 = q.higherKey(six);
565		assertNull(e4);
485	–
566		}
567
568		/**
#	Line 501 | Line 581 | public class ConcurrentSkipListMapTest e
581
582		Object e4 = q.floorKey(zero);
583		assertNull(e4);
504	–
584		}
585
586		/**
#	Line 520 | Line 599 | public class ConcurrentSkipListMapTest e
599
600		Object e4 = q.ceilingKey(six);
601		assertNull(e4);
523	–
602		}
603
604		/**
#	Line 545 | Line 623 | public class ConcurrentSkipListMapTest e
623		try {
624		e.setValue("A");
625		shouldThrow();
626	<	} catch (Exception ok) {
549	<	}
626	>	} catch (UnsupportedOperationException success) {}
627		e = map.pollFirstEntry();
628		assertNull(e);
629		}
#	Line 573 | Line 650 | public class ConcurrentSkipListMapTest e
650		try {
651		e.setValue("E");
652		shouldThrow();
653	<	} catch (Exception ok) {
577	<	}
653	>	} catch (UnsupportedOperationException success) {}
654		e = map.pollLastEntry();
655		assertNull(e);
656		}
657
658		/**
659	<	*   size returns the correct values
659	>	* size returns the correct values
660		*/
661		public void testSize() {
662		ConcurrentSkipListMap map = map5();
663		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
664	<	assertEquals(0, empty.size());
665	<	assertEquals(5, map.size());
664	>	assertEquals(0, empty.size());
665	>	assertEquals(5, map.size());
666		}
667
668		/**
#	Line 596 | Line 672 | public class ConcurrentSkipListMapTest e
672		ConcurrentSkipListMap map = map5();
673		String s = map.toString();
674		for (int i = 1; i <= 5; ++i) {
675	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
675	>	assertTrue(s.contains(String.valueOf(i)));
676		}
677	<	}
677	>	}
678
679		// Exception tests
680
#	Line 610 | Line 686 | public class ConcurrentSkipListMapTest e
686		ConcurrentSkipListMap c = map5();
687		c.get(null);
688		shouldThrow();
689	<	} catch(NullPointerException e){}
689	>	} catch (NullPointerException success) {}
690		}
691
692		/**
#	Line 621 | Line 697 | public class ConcurrentSkipListMapTest e
697		ConcurrentSkipListMap c = map5();
698		c.containsKey(null);
699		shouldThrow();
700	<	} catch(NullPointerException e){}
700	>	} catch (NullPointerException success) {}
701		}
702
703		/**
#	Line 632 | Line 708 | public class ConcurrentSkipListMapTest e
708		ConcurrentSkipListMap c = new ConcurrentSkipListMap();
709		c.containsValue(null);
710		shouldThrow();
711	<	} catch(NullPointerException e){}
711	>	} catch (NullPointerException success) {}
712		}
713
638	–
714		/**
715		* put(null,x) throws NPE
716		*/
#	Line 644 | Line 719 | public class ConcurrentSkipListMapTest e
719		ConcurrentSkipListMap c = map5();
720		c.put(null, "whatever");
721		shouldThrow();
722	<	} catch(NullPointerException e){}
722	>	} catch (NullPointerException success) {}
723		}
724
725		/**
#	Line 655 | Line 730 | public class ConcurrentSkipListMapTest e
730		ConcurrentSkipListMap c = map5();
731		c.putIfAbsent(null, "whatever");
732		shouldThrow();
733	<	} catch(NullPointerException e){}
733	>	} catch (NullPointerException success) {}
734		}
735
736		/**
#	Line 666 | Line 741 | public class ConcurrentSkipListMapTest e
741		ConcurrentSkipListMap c = map5();
742		c.replace(null, "whatever");
743		shouldThrow();
744	<	} catch(NullPointerException e){}
744	>	} catch (NullPointerException success) {}
745		}
746
747		/**
#	Line 677 | Line 752 | public class ConcurrentSkipListMapTest e
752		ConcurrentSkipListMap c = map5();
753		c.replace(null, one, "whatever");
754		shouldThrow();
755	<	} catch(NullPointerException e){}
755	>	} catch (NullPointerException success) {}
756		}
757
758		/**
#	Line 689 | Line 764 | public class ConcurrentSkipListMapTest e
764		c.put("sadsdf", "asdads");
765		c.remove(null);
766		shouldThrow();
767	<	} catch(NullPointerException e){}
767	>	} catch (NullPointerException success) {}
768		}
769
770		/**
#	Line 701 | Line 776 | public class ConcurrentSkipListMapTest e
776		c.put("sadsdf", "asdads");
777		c.remove(null, "whatever");
778		shouldThrow();
779	<	} catch(NullPointerException e){}
779	>	} catch (NullPointerException success) {}
780		}
781
782		/**
783	<	* A deserialized map equals original
783	>	* remove(x, null) returns false
784		*/
785	<	public void testSerialization() {
786	<	ConcurrentSkipListMap q = map5();
787	<
788	<	try {
714	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
715	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
716	<	out.writeObject(q);
717	<	out.close();
718	<
719	<	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
720	<	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
721	<	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
722	<	assertEquals(q.size(), r.size());
723	<	assertTrue(q.equals(r));
724	<	assertTrue(r.equals(q));
725	<	} catch(Exception e){
726	<	e.printStackTrace();
727	<	unexpectedException();
728	<	}
785	>	public void testRemove3() {
786	>	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
787	>	c.put("sadsdf", "asdads");
788	>	assertFalse(c.remove("sadsdf", null));
789		}
790
791	<
791	>	/**
792	>	* A deserialized map equals original
793	>	*/
794	>	public void testSerialization() throws Exception {
795	>	NavigableMap x = map5();
796	>	NavigableMap y = serialClone(x);
797	>
798	>	assertTrue(x != y);
799	>	assertEquals(x.size(), y.size());
800	>	assertEquals(x.toString(), y.toString());
801	>	assertEquals(x, y);
802	>	assertEquals(y, x);
803	>	}
804
805		/**
806		* subMap returns map with keys in requested range
807		*/
808		public void testSubMapContents() {
809		ConcurrentSkipListMap map = map5();
810	<	NavigableMap sm = map.navigableSubMap(two, four);
810	>	NavigableMap sm = map.subMap(two, true, four, false);
811		assertEquals(two, sm.firstKey());
812		assertEquals(three, sm.lastKey());
813		assertEquals(2, sm.size());
#	Line 757 | Line 829 | public class ConcurrentSkipListMapTest e
829		k = (Integer)(r.next());
830		assertEquals(two, k);
831		assertFalse(r.hasNext());
832	<
832	>
833		Iterator j = sm.keySet().iterator();
834		j.next();
835		j.remove();
#	Line 766 | Line 838 | public class ConcurrentSkipListMapTest e
838		assertEquals(1, sm.size());
839		assertEquals(three, sm.firstKey());
840		assertEquals(three, sm.lastKey());
841	<	assertTrue(sm.remove(three) != null);
841	>	assertEquals("C", sm.remove(three));
842		assertTrue(sm.isEmpty());
843		assertEquals(3, map.size());
844		}
845
846		public void testSubMapContents2() {
847		ConcurrentSkipListMap map = map5();
848	<	NavigableMap sm = map.navigableSubMap(two, three);
848	>	NavigableMap sm = map.subMap(two, true, three, false);
849		assertEquals(1, sm.size());
850		assertEquals(two, sm.firstKey());
851		assertEquals(two, sm.lastKey());
#	Line 791 | Line 863 | public class ConcurrentSkipListMapTest e
863		k = (Integer)(r.next());
864		assertEquals(two, k);
865		assertFalse(r.hasNext());
866	<
866	>
867		Iterator j = sm.keySet().iterator();
868		j.next();
869		j.remove();
#	Line 799 | Line 871 | public class ConcurrentSkipListMapTest e
871		assertEquals(4, map.size());
872		assertEquals(0, sm.size());
873		assertTrue(sm.isEmpty());
874	<	assertTrue(sm.remove(three) == null);
874	>	assertSame(sm.remove(three), null);
875		assertEquals(4, map.size());
876		}
877
#	Line 808 | Line 880 | public class ConcurrentSkipListMapTest e
880		*/
881		public void testHeadMapContents() {
882		ConcurrentSkipListMap map = map5();
883	<	NavigableMap sm = map.navigableHeadMap(four);
883	>	NavigableMap sm = map.headMap(four, false);
884		assertTrue(sm.containsKey(one));
885		assertTrue(sm.containsKey(two));
886		assertTrue(sm.containsKey(three));
#	Line 830 | Line 902 | public class ConcurrentSkipListMapTest e
902		}
903
904		/**
905	<	* headMap returns map with keys in requested range
905	>	* tailMap returns map with keys in requested range
906		*/
907		public void testTailMapContents() {
908		ConcurrentSkipListMap map = map5();
909	<	NavigableMap sm = map.navigableTailMap(two);
909	>	NavigableMap sm = map.tailMap(two, true);
910		assertFalse(sm.containsKey(one));
911		assertTrue(sm.containsKey(two));
912		assertTrue(sm.containsKey(three));
#	Line 878 | Line 950 | public class ConcurrentSkipListMapTest e
950		assertEquals("E", e.getValue());
951		assertFalse(i.hasNext());
952
953	<	NavigableMap ssm = sm.navigableTailMap(four);
953	>	NavigableMap ssm = sm.tailMap(four, true);
954		assertEquals(four, ssm.firstKey());
955		assertEquals(five, ssm.lastKey());
956	<	assertTrue(ssm.remove(four) != null);
956	>	assertEquals("D", ssm.remove(four));
957		assertEquals(1, ssm.size());
958		assertEquals(3, sm.size());
959		assertEquals(4, map.size());
960		}
961	<
961	>
962	>	Random rnd = new Random(666);
963	>	BitSet bs;
964	>
965	>	/**
966	>	* Submaps of submaps subdivide correctly
967	>	*/
968	>	public void testRecursiveSubMaps() throws Exception {
969	>	int mapSize = expensiveTests ? 1000 : 100;
970	>	Class cl = ConcurrentSkipListMap.class;
971	>	NavigableMap<Integer, Integer> map = newMap(cl);
972	>	bs = new BitSet(mapSize);
973	>
974	>	populate(map, mapSize);
975	>	check(map,                 0, mapSize - 1, true);
976	>	check(map.descendingMap(), 0, mapSize - 1, false);
977	>
978	>	mutateMap(map, 0, mapSize - 1);
979	>	check(map,                 0, mapSize - 1, true);
980	>	check(map.descendingMap(), 0, mapSize - 1, false);
981	>
982	>	bashSubMap(map.subMap(0, true, mapSize, false),
983	>	0, mapSize - 1, true);
984	>	}
985	>
986	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
987	>	NavigableMap<Integer, Integer> result =
988	>	(NavigableMap<Integer, Integer>) cl.newInstance();
989	>	assertEquals(0, result.size());
990	>	assertFalse(result.keySet().iterator().hasNext());
991	>	return result;
992	>	}
993	>
994	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
995	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
996	>	int key = rnd.nextInt(limit);
997	>	put(map, key);
998	>	}
999	>	}
1000	>
1001	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1002	>	int size = map.size();
1003	>	int rangeSize = max - min + 1;
1004	>
1005	>	// Remove a bunch of entries directly
1006	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1007	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1008	>	}
1009	>
1010	>	// Remove a bunch of entries with iterator
1011	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1012	>	if (rnd.nextBoolean()) {
1013	>	bs.clear(it.next());
1014	>	it.remove();
1015	>	}
1016	>	}
1017	>
1018	>	// Add entries till we're back to original size
1019	>	while (map.size() < size) {
1020	>	int key = min + rnd.nextInt(rangeSize);
1021	>	assertTrue(key >= min && key<= max);
1022	>	put(map, key);
1023	>	}
1024	>	}
1025	>
1026	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1027	>	int size = map.size();
1028	>	int rangeSize = max - min + 1;
1029	>
1030	>	// Remove a bunch of entries directly
1031	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1032	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1033	>	}
1034	>
1035	>	// Remove a bunch of entries with iterator
1036	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1037	>	if (rnd.nextBoolean()) {
1038	>	bs.clear(it.next());
1039	>	it.remove();
1040	>	}
1041	>	}
1042	>
1043	>	// Add entries till we're back to original size
1044	>	while (map.size() < size) {
1045	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
1046	>	if (key >= min && key<= max) {
1047	>	put(map, key);
1048	>	} else {
1049	>	try {
1050	>	map.put(key, 2 * key);
1051	>	shouldThrow();
1052	>	} catch (IllegalArgumentException success) {}
1053	>	}
1054	>	}
1055	>	}
1056	>
1057	>	void put(NavigableMap<Integer, Integer> map, int key) {
1058	>	if (map.put(key, 2 * key) == null)
1059	>	bs.set(key);
1060	>	}
1061	>
1062	>	void remove(NavigableMap<Integer, Integer> map, int key) {
1063	>	if (map.remove(key) != null)
1064	>	bs.clear(key);
1065	>	}
1066	>
1067	>	void bashSubMap(NavigableMap<Integer, Integer> map,
1068	>	int min, int max, boolean ascending) {
1069	>	check(map, min, max, ascending);
1070	>	check(map.descendingMap(), min, max, !ascending);
1071	>
1072	>	mutateSubMap(map, min, max);
1073	>	check(map, min, max, ascending);
1074	>	check(map.descendingMap(), min, max, !ascending);
1075	>
1076	>	// Recurse
1077	>	if (max - min < 2)
1078	>	return;
1079	>	int midPoint = (min + max) / 2;
1080	>
1081	>	// headMap - pick direction and endpoint inclusion randomly
1082	>	boolean incl = rnd.nextBoolean();
1083	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1084	>	if (ascending) {
1085	>	if (rnd.nextBoolean())
1086	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1087	>	else
1088	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1089	>	false);
1090	>	} else {
1091	>	if (rnd.nextBoolean())
1092	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1093	>	else
1094	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1095	>	true);
1096	>	}
1097	>
1098	>	// tailMap - pick direction and endpoint inclusion randomly
1099	>	incl = rnd.nextBoolean();
1100	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1101	>	if (ascending) {
1102	>	if (rnd.nextBoolean())
1103	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1104	>	else
1105	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1106	>	false);
1107	>	} else {
1108	>	if (rnd.nextBoolean()) {
1109	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1110	>	} else {
1111	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1112	>	true);
1113	>	}
1114	>	}
1115	>
1116	>	// subMap - pick direction and endpoint inclusion randomly
1117	>	int rangeSize = max - min + 1;
1118	>	int[] endpoints = new int[2];
1119	>	endpoints[0] = min + rnd.nextInt(rangeSize);
1120	>	endpoints[1] = min + rnd.nextInt(rangeSize);
1121	>	Arrays.sort(endpoints);
1122	>	boolean lowIncl = rnd.nextBoolean();
1123	>	boolean highIncl = rnd.nextBoolean();
1124	>	if (ascending) {
1125	>	NavigableMap<Integer,Integer> sm = map.subMap(
1126	>	endpoints[0], lowIncl, endpoints[1], highIncl);
1127	>	if (rnd.nextBoolean())
1128	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1129	>	endpoints[1] - (highIncl ? 0 : 1), true);
1130	>	else
1131	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1132	>	endpoints[1] - (highIncl ? 0 : 1), false);
1133	>	} else {
1134	>	NavigableMap<Integer,Integer> sm = map.subMap(
1135	>	endpoints[1], highIncl, endpoints[0], lowIncl);
1136	>	if (rnd.nextBoolean())
1137	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1138	>	endpoints[1] - (highIncl ? 0 : 1), false);
1139	>	else
1140	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1141	>	endpoints[1] - (highIncl ? 0 : 1), true);
1142	>	}
1143	>	}
1144	>
1145	>	/**
1146	>	* min and max are both inclusive.  If max < min, interval is empty.
1147	>	*/
1148	>	void check(NavigableMap<Integer, Integer> map,
1149	>	final int min, final int max, final boolean ascending) {
1150	>	class ReferenceSet {
1151	>	int lower(int key) {
1152	>	return ascending ? lowerAscending(key) : higherAscending(key);
1153	>	}
1154	>	int floor(int key) {
1155	>	return ascending ? floorAscending(key) : ceilingAscending(key);
1156	>	}
1157	>	int ceiling(int key) {
1158	>	return ascending ? ceilingAscending(key) : floorAscending(key);
1159	>	}
1160	>	int higher(int key) {
1161	>	return ascending ? higherAscending(key) : lowerAscending(key);
1162	>	}
1163	>	int first() {
1164	>	return ascending ? firstAscending() : lastAscending();
1165	>	}
1166	>	int last() {
1167	>	return ascending ? lastAscending() : firstAscending();
1168	>	}
1169	>	int lowerAscending(int key) {
1170	>	return floorAscending(key - 1);
1171	>	}
1172	>	int floorAscending(int key) {
1173	>	if (key < min)
1174	>	return -1;
1175	>	else if (key > max)
1176	>	key = max;
1177	>
1178	>	// BitSet should support this! Test would run much faster
1179	>	while (key >= min) {
1180	>	if (bs.get(key))
1181	>	return key;
1182	>	key--;
1183	>	}
1184	>	return -1;
1185	>	}
1186	>	int ceilingAscending(int key) {
1187	>	if (key < min)
1188	>	key = min;
1189	>	else if (key > max)
1190	>	return -1;
1191	>	int result = bs.nextSetBit(key);
1192	>	return result > max ? -1 : result;
1193	>	}
1194	>	int higherAscending(int key) {
1195	>	return ceilingAscending(key + 1);
1196	>	}
1197	>	private int firstAscending() {
1198	>	int result = ceilingAscending(min);
1199	>	return result > max ? -1 : result;
1200	>	}
1201	>	private int lastAscending() {
1202	>	int result = floorAscending(max);
1203	>	return result < min ? -1 : result;
1204	>	}
1205	>	}
1206	>	ReferenceSet rs = new ReferenceSet();
1207	>
1208	>	// Test contents using containsKey
1209	>	int size = 0;
1210	>	for (int i = min; i <= max; i++) {
1211	>	boolean bsContainsI = bs.get(i);
1212	>	assertEquals(bsContainsI, map.containsKey(i));
1213	>	if (bsContainsI)
1214	>	size++;
1215	>	}
1216	>	assertEquals(size, map.size());
1217	>
1218	>	// Test contents using contains keySet iterator
1219	>	int size2 = 0;
1220	>	int previousKey = -1;
1221	>	for (int key : map.keySet()) {
1222	>	assertTrue(bs.get(key));
1223	>	size2++;
1224	>	assertTrue(previousKey < 0 ||
1225	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1226	>	previousKey = key;
1227	>	}
1228	>	assertEquals(size2, size);
1229	>
1230	>	// Test navigation ops
1231	>	for (int key = min - 1; key <= max + 1; key++) {
1232	>	assertEq(map.lowerKey(key), rs.lower(key));
1233	>	assertEq(map.floorKey(key), rs.floor(key));
1234	>	assertEq(map.higherKey(key), rs.higher(key));
1235	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1236	>	}
1237	>
1238	>	// Test extrema
1239	>	if (map.size() != 0) {
1240	>	assertEq(map.firstKey(), rs.first());
1241	>	assertEq(map.lastKey(), rs.last());
1242	>	} else {
1243	>	assertEq(rs.first(), -1);
1244	>	assertEq(rs.last(),  -1);
1245	>	try {
1246	>	map.firstKey();
1247	>	shouldThrow();
1248	>	} catch (NoSuchElementException success) {}
1249	>	try {
1250	>	map.lastKey();
1251	>	shouldThrow();
1252	>	} catch (NoSuchElementException success) {}
1253	>	}
1254	>	}
1255	>
1256	>	static void assertEq(Integer i, int j) {
1257	>	if (i == null)
1258	>	assertEquals(j, -1);
1259	>	else
1260	>	assertEquals((int) i, j);
1261	>	}
1262	>
1263	>	static boolean eq(Integer i, int j) {
1264	>	return i == null ? j == -1 : i == j;
1265	>	}
1266	>
1267		}

Diff Legend

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