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.9 by jsr166, Mon Nov 2 20:28:31 2009 UTC vs.
Revision 1.43 by dl, Tue Jan 26 13:33:05 2021 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7	<	import junit.framework.*;
8	<	import java.util.*;
9	<	import java.util.concurrent.*;
10	<	import java.io.*;
7	>	import java.util.ArrayList;
8	>	import java.util.Arrays;
9	>	import java.util.BitSet;
10	>	import java.util.Collection;
11	>	import java.util.Iterator;
12	>	import java.util.Map;
13	>	import java.util.NavigableMap;
14	>	import java.util.NavigableSet;
15	>	import java.util.NoSuchElementException;
16	>	import java.util.Random;
17	>	import java.util.Set;
18	>	import java.util.concurrent.ConcurrentSkipListMap;
19	>
20	>	import junit.framework.Test;
21
22		public class ConcurrentSkipListMapTest extends JSR166TestCase {
23		public static void main(String[] args) {
24	<	junit.textui.TestRunner.run (suite());
24	>	main(suite(), args);
25		}
26		public static Test suite() {
27	<	return new TestSuite(ConcurrentSkipListMapTest.class);
27	>	class Implementation implements MapImplementation {
28	>	public Class<?> klazz() { return ConcurrentSkipListMap.class; }
29	>	public Map emptyMap() { return new ConcurrentSkipListMap(); }
30	>	public boolean isConcurrent() { return true; }
31	>	public boolean remappingFunctionCalledAtMostOnce() { return false; };
32	>	public boolean permitsNullKeys() { return false; }
33	>	public boolean permitsNullValues() { return false; }
34	>	public boolean supportsSetValue() { return false; }
35	>	}
36	>	return newTestSuite(
37	>	ConcurrentSkipListMapTest.class,
38	>	MapTest.testSuite(new Implementation()));
39		}
40
41		/**
42	<	* Create a map from Integers 1-5 to Strings "A"-"E".
42	>	* Returns a new map from Items 1-5 to Strings "A"-"E".
43		*/
44	<	private static ConcurrentSkipListMap map5() {
45	<	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
44	>	private static ConcurrentSkipListMap<Item,String> map5() {
45	>	ConcurrentSkipListMap<Item,String> map = new ConcurrentSkipListMap<Item,String>();
46		assertTrue(map.isEmpty());
47	<	map.put(one, "A");
48	<	map.put(five, "E");
49	<	map.put(three, "C");
50	<	map.put(two, "B");
51	<	map.put(four, "D");
47	>	map.put(one, "A");
48	>	map.put(five, "E");
49	>	map.put(three, "C");
50	>	map.put(two, "B");
51	>	map.put(four, "D");
52		assertFalse(map.isEmpty());
53	<	assertEquals(5, map.size());
54	<	return map;
53	>	mustEqual(5, map.size());
54	>	return map;
55		}
56
57		/**
58	<	*  clear removes all pairs
58	>	* clear removes all pairs
59		*/
60		public void testClear() {
61	<	ConcurrentSkipListMap map = map5();
62	<	map.clear();
63	<	assertEquals(map.size(), 0);
61	>	ConcurrentSkipListMap<Item,String> map = map5();
62	>	map.clear();
63	>	mustEqual(0, map.size());
64		}
65
66		/**
67	<	*
67	>	* copy constructor creates map equal to source map
68		*/
69		public void testConstructFromSorted() {
70	<	ConcurrentSkipListMap map = map5();
71	<	ConcurrentSkipListMap map2 = new ConcurrentSkipListMap(map);
72	<	assertEquals(map, map2);
70	>	ConcurrentSkipListMap<Item,String> map = map5();
71	>	ConcurrentSkipListMap<Item,String> map2 = new ConcurrentSkipListMap<Item,String>(map);
72	>	mustEqual(map, map2);
73		}
74
75		/**
76	<	*  Maps with same contents are equal
76	>	* Maps with same contents are equal
77		*/
78		public void testEquals() {
79	<	ConcurrentSkipListMap map1 = map5();
80	<	ConcurrentSkipListMap map2 = map5();
81	<	assertEquals(map1, map2);
82	<	assertEquals(map2, map1);
83	<	map1.clear();
79	>	ConcurrentSkipListMap<Item,String> map1 = map5();
80	>	ConcurrentSkipListMap<Item,String> map2 = map5();
81	>	mustEqual(map1, map2);
82	>	mustEqual(map2, map1);
83	>	map1.clear();
84		assertFalse(map1.equals(map2));
85		assertFalse(map2.equals(map1));
86		}
87
88		/**
89	<	*  containsKey returns true for contained key
89	>	* containsKey returns true for contained key
90		*/
91		public void testContainsKey() {
92	<	ConcurrentSkipListMap map = map5();
93	<	assertTrue(map.containsKey(one));
92	>	ConcurrentSkipListMap<Item,String> map = map5();
93	>	assertTrue(map.containsKey(one));
94		assertFalse(map.containsKey(zero));
95		}
96
97		/**
98	<	*  containsValue returns true for held values
98	>	* containsValue returns true for held values
99		*/
100		public void testContainsValue() {
101	<	ConcurrentSkipListMap map = map5();
102	<	assertTrue(map.containsValue("A"));
101	>	ConcurrentSkipListMap<Item,String> map = map5();
102	>	assertTrue(map.containsValue("A"));
103		assertFalse(map.containsValue("Z"));
104		}
105
106		/**
107	<	*  get returns the correct element at the given key,
108	<	*  or null if not present
107	>	* get returns the correct element at the given key,
108	>	* or null if not present
109		*/
110		public void testGet() {
111	<	ConcurrentSkipListMap map = map5();
112	<	assertEquals("A", (String)map.get(one));
113	<	ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
111	>	ConcurrentSkipListMap<Item,String> map = map5();
112	>	mustEqual("A", map.get(one));
113	>	ConcurrentSkipListMap<Item,String> empty = new ConcurrentSkipListMap<Item,String>();
114		assertNull(empty.get(one));
115		}
116
117		/**
118	<	*  isEmpty is true of empty map and false for non-empty
118	>	* isEmpty is true of empty map and false for non-empty
119		*/
120		public void testIsEmpty() {
121	<	ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
122	<	ConcurrentSkipListMap map = map5();
123	<	assertTrue(empty.isEmpty());
121	>	ConcurrentSkipListMap<Item,String> empty = new ConcurrentSkipListMap<Item,String>();
122	>	ConcurrentSkipListMap<Item,String> map = map5();
123	>	assertTrue(empty.isEmpty());
124		assertFalse(map.isEmpty());
125		}
126
127		/**
128	<	*   firstKey returns first key
128	>	* firstKey returns first key
129		*/
130		public void testFirstKey() {
131	<	ConcurrentSkipListMap map = map5();
132	<	assertEquals(one, map.firstKey());
131	>	ConcurrentSkipListMap<Item,String> map = map5();
132	>	mustEqual(one, map.firstKey());
133		}
134
135		/**
136	<	*   lastKey returns last key
136	>	* lastKey returns last key
137		*/
138		public void testLastKey() {
139	<	ConcurrentSkipListMap map = map5();
140	<	assertEquals(five, map.lastKey());
139	>	ConcurrentSkipListMap<Item,String> map = map5();
140	>	mustEqual(five, map.lastKey());
141		}
142
122	–
143		/**
144	<	*  keySet.toArray returns contains all keys
144	>	* keySet.toArray returns contains all keys
145		*/
146		public void testKeySetToArray() {
147	<	ConcurrentSkipListMap map = map5();
148	<	Set s = map.keySet();
147	>	ConcurrentSkipListMap<Item,String> map = map5();
148	>	Set<Item> s = map.keySet();
149		Object[] ar = s.toArray();
150		assertTrue(s.containsAll(Arrays.asList(ar)));
151	<	assertEquals(5, ar.length);
152	<	ar[0] = m10;
151	>	mustEqual(5, ar.length);
152	>	ar[0] = minusTen;
153		assertFalse(s.containsAll(Arrays.asList(ar)));
154		}
155
156		/**
157	<	*  descendingkeySet.toArray returns contains all keys
157	>	* descendingkeySet.toArray returns contains all keys
158		*/
159		public void testDescendingKeySetToArray() {
160	<	ConcurrentSkipListMap map = map5();
161	<	Set s = map.descendingKeySet();
160	>	ConcurrentSkipListMap<Item,String> map = map5();
161	>	Set<Item> s = map.descendingKeySet();
162		Object[] ar = s.toArray();
163	<	assertEquals(5, ar.length);
163	>	mustEqual(5, ar.length);
164		assertTrue(s.containsAll(Arrays.asList(ar)));
165	<	ar[0] = m10;
165	>	ar[0] = minusTen;
166		assertFalse(s.containsAll(Arrays.asList(ar)));
167		}
168
169		/**
170	<	*   keySet returns a Set containing all the keys
170	>	* keySet returns a Set containing all the keys
171		*/
172		public void testKeySet() {
173	<	ConcurrentSkipListMap map = map5();
174	<	Set s = map.keySet();
175	<	assertEquals(5, s.size());
176	<	assertTrue(s.contains(one));
177	<	assertTrue(s.contains(two));
178	<	assertTrue(s.contains(three));
179	<	assertTrue(s.contains(four));
180	<	assertTrue(s.contains(five));
173	>	ConcurrentSkipListMap<Item,String> map = map5();
174	>	Set<Item> s = map.keySet();
175	>	mustEqual(5, s.size());
176	>	mustContain(s, one);
177	>	mustContain(s, two);
178	>	mustContain(s, three);
179	>	mustContain(s, four);
180	>	mustContain(s, five);
181		}
182
183		/**
184	<	*   keySet is ordered
184	>	* keySet is ordered
185		*/
186		public void testKeySetOrder() {
187	<	ConcurrentSkipListMap map = map5();
188	<	Set s = map.keySet();
189	<	Iterator i = s.iterator();
190	<	Integer last = (Integer)i.next();
191	<	assertEquals(last, one);
187	>	ConcurrentSkipListMap<Item,String> map = map5();
188	>	Set<Item> s = map.keySet();
189	>	Iterator<? extends Item> i = s.iterator();
190	>	Item last = i.next();
191	>	mustEqual(last, one);
192		int count = 1;
193		while (i.hasNext()) {
194	<	Integer k = (Integer)i.next();
194	>	Item k = i.next();
195		assertTrue(last.compareTo(k) < 0);
196		last = k;
197		++count;
198		}
199	<	assertEquals(count ,5);
199	>	mustEqual(5, count);
200		}
201
202		/**
203		* descending iterator of key set is inverse ordered
204		*/
205		public void testKeySetDescendingIteratorOrder() {
206	<	ConcurrentSkipListMap map = map5();
207	<	NavigableSet s = map.navigableKeySet();
208	<	Iterator i = s.descendingIterator();
209	<	Integer last = (Integer)i.next();
210	<	assertEquals(last, five);
206	>	ConcurrentSkipListMap<Item,String> map = map5();
207	>	NavigableSet<Item> s = map.navigableKeySet();
208	>	Iterator<? extends Item> i = s.descendingIterator();
209	>	Item last = (Item)i.next();
210	>	mustEqual(last, five);
211		int count = 1;
212		while (i.hasNext()) {
213	<	Integer k = (Integer)i.next();
213	>	Item k = (Item)i.next();
214		assertTrue(last.compareTo(k) > 0);
215		last = k;
216		++count;
217		}
218	<	assertEquals(count ,5);
218	>	mustEqual(5, count);
219		}
220
221		/**
222	<	*   descendingKeySet is ordered
222	>	* descendingKeySet is ordered
223		*/
224		public void testDescendingKeySetOrder() {
225	<	ConcurrentSkipListMap map = map5();
226	<	Set s = map.descendingKeySet();
227	<	Iterator i = s.iterator();
228	<	Integer last = (Integer)i.next();
229	<	assertEquals(last, five);
225	>	ConcurrentSkipListMap<Item,String> map = map5();
226	>	Set<Item> s = map.descendingKeySet();
227	>	Iterator<? extends Item> i = s.iterator();
228	>	Item last = (Item)i.next();
229	>	mustEqual(last, five);
230		int count = 1;
231		while (i.hasNext()) {
232	<	Integer k = (Integer)i.next();
232	>	Item k = (Item)i.next();
233		assertTrue(last.compareTo(k) > 0);
234		last = k;
235		++count;
236		}
237	<	assertEquals(count, 5);
237	>	mustEqual(5, count);
238		}
239
240		/**
241	<	*  descending iterator of descendingKeySet is ordered
241	>	* descending iterator of descendingKeySet is ordered
242		*/
243		public void testDescendingKeySetDescendingIteratorOrder() {
244	<	ConcurrentSkipListMap map = map5();
245	<	NavigableSet s = map.descendingKeySet();
246	<	Iterator i = s.descendingIterator();
247	<	Integer last = (Integer)i.next();
248	<	assertEquals(last, one);
244	>	ConcurrentSkipListMap<Item,String> map = map5();
245	>	NavigableSet<Item> s = map.descendingKeySet();
246	>	Iterator<? extends Item> i = s.descendingIterator();
247	>	Item last = (Item)i.next();
248	>	mustEqual(last, one);
249		int count = 1;
250		while (i.hasNext()) {
251	<	Integer k = (Integer)i.next();
251	>	Item k = (Item)i.next();
252		assertTrue(last.compareTo(k) < 0);
253		last = k;
254		++count;
255		}
256	<	assertEquals(count, 5);
256	>	mustEqual(5, count);
257		}
258
259		/**
260	<	*  Values.toArray contains all values
260	>	* Values.toArray contains all values
261		*/
262		public void testValuesToArray() {
263	<	ConcurrentSkipListMap map = map5();
264	<	Collection v = map.values();
265	<	Object[] ar = v.toArray();
266	<	ArrayList s = new ArrayList(Arrays.asList(ar));
267	<	assertEquals(5, ar.length);
268	<	assertTrue(s.contains("A"));
269	<	assertTrue(s.contains("B"));
270	<	assertTrue(s.contains("C"));
271	<	assertTrue(s.contains("D"));
272	<	assertTrue(s.contains("E"));
263	>	ConcurrentSkipListMap<Item,String> map = map5();
264	>	Collection<String> v = map.values();
265	>	String[] ar = v.toArray(new String[0]);
266	>	ArrayList<String> s = new ArrayList<String>(Arrays.asList(ar));
267	>	mustEqual(5, ar.length);
268	>	assertTrue(s.contains("A"));
269	>	assertTrue(s.contains("B"));
270	>	assertTrue(s.contains("C"));
271	>	assertTrue(s.contains("D"));
272	>	assertTrue(s.contains("E"));
273		}
274
275		/**
276		* values collection contains all values
277		*/
278		public void testValues() {
279	<	ConcurrentSkipListMap map = map5();
280	<	Collection s = map.values();
281	<	assertEquals(5, s.size());
282	<	assertTrue(s.contains("A"));
283	<	assertTrue(s.contains("B"));
284	<	assertTrue(s.contains("C"));
285	<	assertTrue(s.contains("D"));
286	<	assertTrue(s.contains("E"));
279	>	ConcurrentSkipListMap<Item,String> map = map5();
280	>	Collection<String> s = map.values();
281	>	mustEqual(5, s.size());
282	>	assertTrue(s.contains("A"));
283	>	assertTrue(s.contains("B"));
284	>	assertTrue(s.contains("C"));
285	>	assertTrue(s.contains("D"));
286	>	assertTrue(s.contains("E"));
287		}
288
289		/**
290		* entrySet contains all pairs
291		*/
292		public void testEntrySet() {
293	<	ConcurrentSkipListMap map = map5();
294	<	Set s = map.entrySet();
295	<	assertEquals(5, s.size());
296	<	Iterator it = s.iterator();
293	>	ConcurrentSkipListMap<Item,String> map = map5();
294	>	Set<Map.Entry<Item,String>> s = map.entrySet();
295	>	mustEqual(5, s.size());
296	>	Iterator<Map.Entry<Item,String>> it = s.iterator();
297		while (it.hasNext()) {
298	<	Map.Entry e = (Map.Entry) it.next();
298	>	Map.Entry<Item,String> e = it.next();
299		assertTrue(
300		(e.getKey().equals(one) && e.getValue().equals("A")) ||
301		(e.getKey().equals(two) && e.getValue().equals("B")) ||
#	Line 289 | Line 309 | public class ConcurrentSkipListMapTest e
309		* descendingEntrySet contains all pairs
310		*/
311		public void testDescendingEntrySet() {
312	<	ConcurrentSkipListMap map = map5();
313	<	Set s = map.descendingMap().entrySet();
314	<	assertEquals(5, s.size());
315	<	Iterator it = s.iterator();
312	>	ConcurrentSkipListMap<Item,String> map = map5();
313	>	Set<Map.Entry<Item,String>> s = map.descendingMap().entrySet();
314	>	mustEqual(5, s.size());
315	>	Iterator<Map.Entry<Item,String>> it = s.iterator();
316		while (it.hasNext()) {
317	<	Map.Entry e = (Map.Entry) it.next();
317	>	Map.Entry<Item,String> e = it.next();
318		assertTrue(
319		(e.getKey().equals(one) && e.getValue().equals("A")) ||
320		(e.getKey().equals(two) && e.getValue().equals("B")) ||
#	Line 305 | Line 325 | public class ConcurrentSkipListMapTest e
325		}
326
327		/**
328	<	*  entrySet.toArray contains all entries
328	>	* entrySet.toArray contains all entries
329		*/
330		public void testEntrySetToArray() {
331	<	ConcurrentSkipListMap map = map5();
332	<	Set s = map.entrySet();
331	>	ConcurrentSkipListMap<Item,String> map = map5();
332	>	Set<Map.Entry<Item,String>> s = map.entrySet();
333		Object[] ar = s.toArray();
334	<	assertEquals(5, ar.length);
334	>	mustEqual(5, ar.length);
335		for (int i = 0; i < 5; ++i) {
336		assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
337		assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
#	Line 319 | Line 339 | public class ConcurrentSkipListMapTest e
339		}
340
341		/**
342	<	*  descendingEntrySet.toArray contains all entries
342	>	* descendingEntrySet.toArray contains all entries
343		*/
344		public void testDescendingEntrySetToArray() {
345	<	ConcurrentSkipListMap map = map5();
346	<	Set s = map.descendingMap().entrySet();
345	>	ConcurrentSkipListMap<Item,String> map = map5();
346	>	Set<Map.Entry<Item,String>> s = map.descendingMap().entrySet();
347		Object[] ar = s.toArray();
348	<	assertEquals(5, ar.length);
348	>	mustEqual(5, ar.length);
349		for (int i = 0; i < 5; ++i) {
350		assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
351		assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
#	Line 333 | Line 353 | public class ConcurrentSkipListMapTest e
353		}
354
355		/**
356	<	*   putAll  adds all key-value pairs from the given map
356	>	* putAll adds all key-value pairs from the given map
357		*/
358		public void testPutAll() {
359	<	ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
360	<	ConcurrentSkipListMap map = map5();
361	<	empty.putAll(map);
362	<	assertEquals(5, empty.size());
363	<	assertTrue(empty.containsKey(one));
364	<	assertTrue(empty.containsKey(two));
365	<	assertTrue(empty.containsKey(three));
366	<	assertTrue(empty.containsKey(four));
367	<	assertTrue(empty.containsKey(five));
359	>	ConcurrentSkipListMap<Item,String> p = new ConcurrentSkipListMap<Item,String>();
360	>	ConcurrentSkipListMap<Item,String> map = map5();
361	>	p.putAll(map);
362	>	mustEqual(5, p.size());
363	>	assertTrue(p.containsKey(one));
364	>	assertTrue(p.containsKey(two));
365	>	assertTrue(p.containsKey(three));
366	>	assertTrue(p.containsKey(four));
367	>	assertTrue(p.containsKey(five));
368		}
369
370		/**
371	<	*   putIfAbsent works when the given key is not present
371	>	* putIfAbsent works when the given key is not present
372		*/
373		public void testPutIfAbsent() {
374	<	ConcurrentSkipListMap map = map5();
375	<	map.putIfAbsent(six, "Z");
374	>	ConcurrentSkipListMap<Item,String> map = map5();
375	>	map.putIfAbsent(six, "Z");
376		assertTrue(map.containsKey(six));
377		}
378
379		/**
380	<	*   putIfAbsent does not add the pair if the key is already present
380	>	* putIfAbsent does not add the pair if the key is already present
381		*/
382		public void testPutIfAbsent2() {
383	<	ConcurrentSkipListMap map = map5();
384	<	assertEquals("A", map.putIfAbsent(one, "Z"));
383	>	ConcurrentSkipListMap<Item,String> map = map5();
384	>	mustEqual("A", map.putIfAbsent(one, "Z"));
385		}
386
387		/**
388	<	*   replace fails when the given key is not present
388	>	* replace fails when the given key is not present
389		*/
390		public void testReplace() {
391	<	ConcurrentSkipListMap map = map5();
392	<	assertNull(map.replace(six, "Z"));
391	>	ConcurrentSkipListMap<Item,String> map = map5();
392	>	assertNull(map.replace(six, "Z"));
393		assertFalse(map.containsKey(six));
394		}
395
396		/**
397	<	*   replace succeeds if the key is already present
397	>	* replace succeeds if the key is already present
398		*/
399		public void testReplace2() {
400	<	ConcurrentSkipListMap map = map5();
400	>	ConcurrentSkipListMap<Item,String> map = map5();
401		assertNotNull(map.replace(one, "Z"));
402	<	assertEquals("Z", map.get(one));
402	>	mustEqual("Z", map.get(one));
403		}
404
385	–
405		/**
406		* replace value fails when the given key not mapped to expected value
407		*/
408		public void testReplaceValue() {
409	<	ConcurrentSkipListMap map = map5();
410	<	assertEquals("A", map.get(one));
411	<	assertFalse(map.replace(one, "Z", "Z"));
412	<	assertEquals("A", map.get(one));
409	>	ConcurrentSkipListMap<Item,String> map = map5();
410	>	mustEqual("A", map.get(one));
411	>	assertFalse(map.replace(one, "Z", "Z"));
412	>	mustEqual("A", map.get(one));
413		}
414
415		/**
416		* replace value succeeds when the given key mapped to expected value
417		*/
418		public void testReplaceValue2() {
419	<	ConcurrentSkipListMap map = map5();
420	<	assertEquals("A", map.get(one));
421	<	assertTrue(map.replace(one, "A", "Z"));
422	<	assertEquals("Z", map.get(one));
419	>	ConcurrentSkipListMap<Item,String> map = map5();
420	>	mustEqual("A", map.get(one));
421	>	assertTrue(map.replace(one, "A", "Z"));
422	>	mustEqual("Z", map.get(one));
423		}
424
406	–
425		/**
426	<	*   remove removes the correct key-value pair from the map
426	>	* remove removes the correct key-value pair from the map
427		*/
428		public void testRemove() {
429	<	ConcurrentSkipListMap map = map5();
430	<	map.remove(five);
431	<	assertEquals(4, map.size());
432	<	assertFalse(map.containsKey(five));
429	>	ConcurrentSkipListMap<Item,String> map = map5();
430	>	map.remove(five);
431	>	mustEqual(4, map.size());
432	>	assertFalse(map.containsKey(five));
433		}
434
435		/**
436		* remove(key,value) removes only if pair present
437		*/
438		public void testRemove2() {
439	<	ConcurrentSkipListMap map = map5();
440	<	assertTrue(map.containsKey(five));
441	<	assertEquals("E", map.get(five));
442	<	map.remove(five, "E");
443	<	assertEquals(4, map.size());
444	<	assertFalse(map.containsKey(five));
445	<	map.remove(four, "A");
446	<	assertEquals(4, map.size());
447	<	assertTrue(map.containsKey(four));
430	<
439	>	ConcurrentSkipListMap<Item,String> map = map5();
440	>	assertTrue(map.containsKey(five));
441	>	mustEqual("E", map.get(five));
442	>	map.remove(five, "E");
443	>	mustEqual(4, map.size());
444	>	assertFalse(map.containsKey(five));
445	>	map.remove(four, "A");
446	>	mustEqual(4, map.size());
447	>	assertTrue(map.containsKey(four));
448		}
449
450		/**
451		* lowerEntry returns preceding entry.
452		*/
453		public void testLowerEntry() {
454	<	ConcurrentSkipListMap map = map5();
455	<	Map.Entry e1 = map.lowerEntry(three);
456	<	assertEquals(two, e1.getKey());
454	>	ConcurrentSkipListMap<Item,String> map = map5();
455	>	Map.Entry<Item,String> e1 = map.lowerEntry(three);
456	>	mustEqual(two, e1.getKey());
457
458	<	Map.Entry e2 = map.lowerEntry(six);
459	<	assertEquals(five, e2.getKey());
458	>	Map.Entry<Item,String> e2 = map.lowerEntry(six);
459	>	mustEqual(five, e2.getKey());
460
461	<	Map.Entry e3 = map.lowerEntry(one);
461	>	Map.Entry<Item,String> e3 = map.lowerEntry(one);
462		assertNull(e3);
463
464	<	Map.Entry e4 = map.lowerEntry(zero);
464	>	Map.Entry<Item,String> e4 = map.lowerEntry(zero);
465		assertNull(e4);
449	–
466		}
467
468		/**
469		* higherEntry returns next entry.
470		*/
471		public void testHigherEntry() {
472	<	ConcurrentSkipListMap map = map5();
473	<	Map.Entry e1 = map.higherEntry(three);
474	<	assertEquals(four, e1.getKey());
472	>	ConcurrentSkipListMap<Item,String> map = map5();
473	>	Map.Entry<Item,String> e1 = map.higherEntry(three);
474	>	mustEqual(four, e1.getKey());
475
476	<	Map.Entry e2 = map.higherEntry(zero);
477	<	assertEquals(one, e2.getKey());
476	>	Map.Entry<Item,String> e2 = map.higherEntry(zero);
477	>	mustEqual(one, e2.getKey());
478
479	<	Map.Entry e3 = map.higherEntry(five);
479	>	Map.Entry<Item,String> e3 = map.higherEntry(five);
480		assertNull(e3);
481
482	<	Map.Entry e4 = map.higherEntry(six);
482	>	Map.Entry<Item,String> e4 = map.higherEntry(six);
483		assertNull(e4);
468	–
484		}
485
486		/**
487		* floorEntry returns preceding entry.
488		*/
489		public void testFloorEntry() {
490	<	ConcurrentSkipListMap map = map5();
491	<	Map.Entry e1 = map.floorEntry(three);
492	<	assertEquals(three, e1.getKey());
490	>	ConcurrentSkipListMap<Item,String> map = map5();
491	>	Map.Entry<Item,String> e1 = map.floorEntry(three);
492	>	mustEqual(three, e1.getKey());
493
494	<	Map.Entry e2 = map.floorEntry(six);
495	<	assertEquals(five, e2.getKey());
494	>	Map.Entry<Item,String> e2 = map.floorEntry(six);
495	>	mustEqual(five, e2.getKey());
496
497	<	Map.Entry e3 = map.floorEntry(one);
498	<	assertEquals(one, e3.getKey());
497	>	Map.Entry<Item,String> e3 = map.floorEntry(one);
498	>	mustEqual(one, e3.getKey());
499
500	<	Map.Entry e4 = map.floorEntry(zero);
500	>	Map.Entry<Item,String> e4 = map.floorEntry(zero);
501		assertNull(e4);
487	–
502		}
503
504		/**
505		* ceilingEntry returns next entry.
506		*/
507		public void testCeilingEntry() {
508	<	ConcurrentSkipListMap map = map5();
509	<	Map.Entry e1 = map.ceilingEntry(three);
510	<	assertEquals(three, e1.getKey());
508	>	ConcurrentSkipListMap<Item,String> map = map5();
509	>	Map.Entry<Item,String> e1 = map.ceilingEntry(three);
510	>	mustEqual(three, e1.getKey());
511
512	<	Map.Entry e2 = map.ceilingEntry(zero);
513	<	assertEquals(one, e2.getKey());
512	>	Map.Entry<Item,String> e2 = map.ceilingEntry(zero);
513	>	mustEqual(one, e2.getKey());
514
515	<	Map.Entry e3 = map.ceilingEntry(five);
516	<	assertEquals(five, e3.getKey());
515	>	Map.Entry<Item,String> e3 = map.ceilingEntry(five);
516	>	mustEqual(five, e3.getKey());
517
518	<	Map.Entry e4 = map.ceilingEntry(six);
518	>	Map.Entry<Item,String> e4 = map.ceilingEntry(six);
519		assertNull(e4);
506	–
520		}
521
522		/**
523		* lowerEntry, higherEntry, ceilingEntry, and floorEntry return
524	<	* imutable entries
524	>	* immutable entries
525		*/
526	<	public void testEntryImmutablity() {
527	<	ConcurrentSkipListMap map = map5();
528	<	Map.Entry e = map.lowerEntry(three);
529	<	assertEquals(two, e.getKey());
526	>	public void testEntryImmutability() {
527	>	ConcurrentSkipListMap<Item,String> map = map5();
528	>	Map.Entry<Item,String> e = map.lowerEntry(three);
529	>	mustEqual(two, e.getKey());
530		try {
531		e.setValue("X");
532	<	fail();
533	<	} catch(UnsupportedOperationException success) {}
532	>	shouldThrow();
533	>	} catch (UnsupportedOperationException success) {}
534		e = map.higherEntry(zero);
535	<	assertEquals(one, e.getKey());
535	>	mustEqual(one, e.getKey());
536		try {
537		e.setValue("X");
538	<	fail();
539	<	} catch(UnsupportedOperationException success) {}
538	>	shouldThrow();
539	>	} catch (UnsupportedOperationException success) {}
540		e = map.floorEntry(one);
541	<	assertEquals(one, e.getKey());
541	>	mustEqual(one, e.getKey());
542		try {
543		e.setValue("X");
544	<	fail();
545	<	} catch(UnsupportedOperationException success) {}
544	>	shouldThrow();
545	>	} catch (UnsupportedOperationException success) {}
546		e = map.ceilingEntry(five);
547	<	assertEquals(five, e.getKey());
547	>	mustEqual(five, e.getKey());
548		try {
549		e.setValue("X");
550	<	fail();
551	<	} catch(UnsupportedOperationException success) {}
550	>	shouldThrow();
551	>	} catch (UnsupportedOperationException success) {}
552		}
553
541	–
542	–
554		/**
555		* lowerKey returns preceding element
556		*/
557		public void testLowerKey() {
558	<	ConcurrentSkipListMap q = map5();
558	>	ConcurrentSkipListMap<Item,String> q = map5();
559		Object e1 = q.lowerKey(three);
560	<	assertEquals(two, e1);
560	>	mustEqual(two, e1);
561
562		Object e2 = q.lowerKey(six);
563	<	assertEquals(five, e2);
563	>	mustEqual(five, e2);
564
565		Object e3 = q.lowerKey(one);
566		assertNull(e3);
567
568		Object e4 = q.lowerKey(zero);
569		assertNull(e4);
559	–
570		}
571
572		/**
573		* higherKey returns next element
574		*/
575		public void testHigherKey() {
576	<	ConcurrentSkipListMap q = map5();
576	>	ConcurrentSkipListMap<Item,String> q = map5();
577		Object e1 = q.higherKey(three);
578	<	assertEquals(four, e1);
578	>	mustEqual(four, e1);
579
580		Object e2 = q.higherKey(zero);
581	<	assertEquals(one, e2);
581	>	mustEqual(one, e2);
582
583		Object e3 = q.higherKey(five);
584		assertNull(e3);
585
586		Object e4 = q.higherKey(six);
587		assertNull(e4);
578	–
588		}
589
590		/**
591		* floorKey returns preceding element
592		*/
593		public void testFloorKey() {
594	<	ConcurrentSkipListMap q = map5();
594	>	ConcurrentSkipListMap<Item,String> q = map5();
595		Object e1 = q.floorKey(three);
596	<	assertEquals(three, e1);
596	>	mustEqual(three, e1);
597
598		Object e2 = q.floorKey(six);
599	<	assertEquals(five, e2);
599	>	mustEqual(five, e2);
600
601		Object e3 = q.floorKey(one);
602	<	assertEquals(one, e3);
602	>	mustEqual(one, e3);
603
604		Object e4 = q.floorKey(zero);
605		assertNull(e4);
597	–
606		}
607
608		/**
609		* ceilingKey returns next element
610		*/
611		public void testCeilingKey() {
612	<	ConcurrentSkipListMap q = map5();
612	>	ConcurrentSkipListMap<Item,String> q = map5();
613		Object e1 = q.ceilingKey(three);
614	<	assertEquals(three, e1);
614	>	mustEqual(three, e1);
615
616		Object e2 = q.ceilingKey(zero);
617	<	assertEquals(one, e2);
617	>	mustEqual(one, e2);
618
619		Object e3 = q.ceilingKey(five);
620	<	assertEquals(five, e3);
620	>	mustEqual(five, e3);
621
622		Object e4 = q.ceilingKey(six);
623		assertNull(e4);
616	–
624		}
625
626		/**
627		* pollFirstEntry returns entries in order
628		*/
629		public void testPollFirstEntry() {
630	<	ConcurrentSkipListMap map = map5();
631	<	Map.Entry e = map.pollFirstEntry();
632	<	assertEquals(one, e.getKey());
633	<	assertEquals("A", e.getValue());
630	>	ConcurrentSkipListMap<Item,String> map = map5();
631	>	Map.Entry<Item,String> e = map.pollFirstEntry();
632	>	mustEqual(one, e.getKey());
633	>	mustEqual("A", e.getValue());
634		e = map.pollFirstEntry();
635	<	assertEquals(two, e.getKey());
635	>	mustEqual(two, e.getKey());
636		map.put(one, "A");
637		e = map.pollFirstEntry();
638	<	assertEquals(one, e.getKey());
639	<	assertEquals("A", e.getValue());
638	>	mustEqual(one, e.getKey());
639	>	mustEqual("A", e.getValue());
640		e = map.pollFirstEntry();
641	<	assertEquals(three, e.getKey());
641	>	mustEqual(three, e.getKey());
642		map.remove(four);
643		e = map.pollFirstEntry();
644	<	assertEquals(five, e.getKey());
644	>	mustEqual(five, e.getKey());
645		try {
646		e.setValue("A");
647		shouldThrow();
648	<	} catch (Exception ok) {
642	<	}
648	>	} catch (UnsupportedOperationException success) {}
649		e = map.pollFirstEntry();
650		assertNull(e);
651		}
#	Line 648 | Line 654 | public class ConcurrentSkipListMapTest e
654		* pollLastEntry returns entries in order
655		*/
656		public void testPollLastEntry() {
657	<	ConcurrentSkipListMap map = map5();
658	<	Map.Entry e = map.pollLastEntry();
659	<	assertEquals(five, e.getKey());
660	<	assertEquals("E", e.getValue());
657	>	ConcurrentSkipListMap<Item,String> map = map5();
658	>	Map.Entry<Item,String> e = map.pollLastEntry();
659	>	mustEqual(five, e.getKey());
660	>	mustEqual("E", e.getValue());
661		e = map.pollLastEntry();
662	<	assertEquals(four, e.getKey());
662	>	mustEqual(four, e.getKey());
663		map.put(five, "E");
664		e = map.pollLastEntry();
665	<	assertEquals(five, e.getKey());
666	<	assertEquals("E", e.getValue());
665	>	mustEqual(five, e.getKey());
666	>	mustEqual("E", e.getValue());
667		e = map.pollLastEntry();
668	<	assertEquals(three, e.getKey());
668	>	mustEqual(three, e.getKey());
669		map.remove(two);
670		e = map.pollLastEntry();
671	<	assertEquals(one, e.getKey());
671	>	mustEqual(one, e.getKey());
672		try {
673		e.setValue("E");
674		shouldThrow();
675	<	} catch (Exception ok) {
670	<	}
675	>	} catch (UnsupportedOperationException success) {}
676		e = map.pollLastEntry();
677		assertNull(e);
678		}
679
680		/**
681	<	*   size returns the correct values
681	>	* size returns the correct values
682		*/
683		public void testSize() {
684	<	ConcurrentSkipListMap map = map5();
685	<	ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
686	<	assertEquals(0, empty.size());
687	<	assertEquals(5, map.size());
684	>	ConcurrentSkipListMap<Item,String> map = map5();
685	>	ConcurrentSkipListMap<Item,String> empty = new ConcurrentSkipListMap<Item,String>();
686	>	mustEqual(0, empty.size());
687	>	mustEqual(5, map.size());
688		}
689
690		/**
691		* toString contains toString of elements
692		*/
693		public void testToString() {
694	<	ConcurrentSkipListMap map = map5();
694	>	ConcurrentSkipListMap<Item,String> map = map5();
695		String s = map.toString();
696		for (int i = 1; i <= 5; ++i) {
697	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
697	>	assertTrue(s.contains(String.valueOf(i)));
698		}
699		}
700
#	Line 699 | Line 704 | public class ConcurrentSkipListMapTest e
704		* get(null) of nonempty map throws NPE
705		*/
706		public void testGet_NullPointerException() {
707	+	ConcurrentSkipListMap<Item,String> c = map5();
708		try {
703	–	ConcurrentSkipListMap c = map5();
709		c.get(null);
710		shouldThrow();
711	<	} catch(NullPointerException e){}
711	>	} catch (NullPointerException success) {}
712		}
713
714		/**
715		* containsKey(null) of nonempty map throws NPE
716		*/
717		public void testContainsKey_NullPointerException() {
718	+	ConcurrentSkipListMap<Item,String> c = map5();
719		try {
714	–	ConcurrentSkipListMap c = map5();
720		c.containsKey(null);
721		shouldThrow();
722	<	} catch(NullPointerException e){}
722	>	} catch (NullPointerException success) {}
723		}
724
725		/**
726		* containsValue(null) throws NPE
727		*/
728		public void testContainsValue_NullPointerException() {
729	+	ConcurrentSkipListMap<Item,String> c = new ConcurrentSkipListMap<Item,String>();
730		try {
725	–	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
731		c.containsValue(null);
732		shouldThrow();
733	<	} catch(NullPointerException e){}
733	>	} catch (NullPointerException success) {}
734		}
735
731	–
736		/**
737		* put(null,x) throws NPE
738		*/
739		public void testPut1_NullPointerException() {
740	+	ConcurrentSkipListMap<Item,String> c = map5();
741		try {
737	–	ConcurrentSkipListMap c = map5();
742		c.put(null, "whatever");
743		shouldThrow();
744	<	} catch(NullPointerException e){}
744	>	} catch (NullPointerException success) {}
745		}
746
747		/**
748		* putIfAbsent(null, x) throws NPE
749		*/
750		public void testPutIfAbsent1_NullPointerException() {
751	+	ConcurrentSkipListMap<Item,String> c = map5();
752		try {
748	–	ConcurrentSkipListMap c = map5();
753		c.putIfAbsent(null, "whatever");
754		shouldThrow();
755	<	} catch(NullPointerException e){}
755	>	} catch (NullPointerException success) {}
756		}
757
758		/**
759		* replace(null, x) throws NPE
760		*/
761		public void testReplace_NullPointerException() {
762	+	ConcurrentSkipListMap<Item,String> c = map5();
763		try {
764	<	ConcurrentSkipListMap c = map5();
760	<	c.replace(null, "whatever");
764	>	c.replace(null, "A");
765		shouldThrow();
766	<	} catch(NullPointerException e){}
766	>	} catch (NullPointerException success) {}
767		}
768
769		/**
770		* replace(null, x, y) throws NPE
771		*/
772		public void testReplaceValue_NullPointerException() {
773	+	ConcurrentSkipListMap<Item,String> c = map5();
774		try {
775	<	ConcurrentSkipListMap c = map5();
771	<	c.replace(null, one, "whatever");
775	>	c.replace(null, "A", "B");
776		shouldThrow();
777	<	} catch(NullPointerException e){}
777	>	} catch (NullPointerException success) {}
778		}
779
780		/**
781		* remove(null) throws NPE
782		*/
783		public void testRemove1_NullPointerException() {
784	+	ConcurrentSkipListMap<Item,String> c = new ConcurrentSkipListMap<Item,String>();
785	+	c.put(zero, "A");
786		try {
781	–	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
782	–	c.put("sadsdf", "asdads");
787		c.remove(null);
788		shouldThrow();
789	<	} catch(NullPointerException e){}
789	>	} catch (NullPointerException success) {}
790		}
791
792		/**
793		* remove(null, x) throws NPE
794		*/
795		public void testRemove2_NullPointerException() {
796	+	ConcurrentSkipListMap<Item,String> c = new ConcurrentSkipListMap<Item,String>();
797	+	c.put(zero, "asdads");
798		try {
793	–	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
794	–	c.put("sadsdf", "asdads");
799		c.remove(null, "whatever");
800		shouldThrow();
801	<	} catch(NullPointerException e){}
801	>	} catch (NullPointerException success) {}
802		}
803
804		/**
805		* remove(x, null) returns false
806		*/
807		public void testRemove3() {
808	<	try {
809	<	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
810	<	c.put("sadsdf", "asdads");
807	<	assertFalse(c.remove("sadsdf", null));
808	<	} catch(NullPointerException e){
809	<	fail();
810	<	}
808	>	ConcurrentSkipListMap<Item,String> c = new ConcurrentSkipListMap<Item,String>();
809	>	c.put(zero, "asdads");
810	>	assertFalse(c.remove("sadsdf", null));
811		}
812
813		/**
814	<	* A deserialized map equals original
814	>	* A cloned map equals original
815		*/
816	<	public void testSerialization() {
817	<	ConcurrentSkipListMap q = map5();
816	>	public void testClone() {
817	>	ConcurrentSkipListMap<Item,String> x = map5();
818	>	ConcurrentSkipListMap<Item,String> y = x.clone();
819
820	<	try {
821	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
822	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
823	<	out.writeObject(q);
824	<	out.close();
825	<
826	<	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
827	<	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
827	<	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
828	<	assertEquals(q.size(), r.size());
829	<	assertTrue(q.equals(r));
830	<	assertTrue(r.equals(q));
831	<	} catch(Exception e){
832	<	e.printStackTrace();
833	<	unexpectedException();
834	<	}
820	>	assertNotSame(x, y);
821	>	mustEqual(x.size(), y.size());
822	>	mustEqual(x.toString(), y.toString());
823	>	mustEqual(x, y);
824	>	mustEqual(y, x);
825	>	y.clear();
826	>	assertTrue(y.isEmpty());
827	>	assertFalse(x.equals(y));
828		}
829
830	+	/**
831	+	* A deserialized/reserialized map equals original
832	+	*/
833	+	public void testSerialization() throws Exception {
834	+	NavigableMap<Item,String> x = map5();
835	+	NavigableMap<Item,String> y = serialClone(x);
836
837	+	assertNotSame(x, y);
838	+	mustEqual(x.size(), y.size());
839	+	mustEqual(x.toString(), y.toString());
840	+	mustEqual(x, y);
841	+	mustEqual(y, x);
842	+	y.clear();
843	+	assertTrue(y.isEmpty());
844	+	assertFalse(x.equals(y));
845	+	}
846
847		/**
848		* subMap returns map with keys in requested range
849		*/
850		public void testSubMapContents() {
851	<	ConcurrentSkipListMap map = map5();
852	<	NavigableMap sm = map.subMap(two, true, four, false);
853	<	assertEquals(two, sm.firstKey());
854	<	assertEquals(three, sm.lastKey());
855	<	assertEquals(2, sm.size());
851	>	ConcurrentSkipListMap<Item,String> map = map5();
852	>	NavigableMap<Item,String> sm = map.subMap(two, true, four, false);
853	>	mustEqual(two, sm.firstKey());
854	>	mustEqual(three, sm.lastKey());
855	>	mustEqual(2, sm.size());
856		assertFalse(sm.containsKey(one));
857		assertTrue(sm.containsKey(two));
858		assertTrue(sm.containsKey(three));
859		assertFalse(sm.containsKey(four));
860		assertFalse(sm.containsKey(five));
861	<	Iterator i = sm.keySet().iterator();
862	<	Object k;
863	<	k = (Integer)(i.next());
864	<	assertEquals(two, k);
865	<	k = (Integer)(i.next());
866	<	assertEquals(three, k);
861	>	Iterator<? extends Item> i = sm.keySet().iterator();
862	>	Item k;
863	>	k = (Item)(i.next());
864	>	mustEqual(two, k);
865	>	k = (Item)(i.next());
866	>	mustEqual(three, k);
867		assertFalse(i.hasNext());
868	<	Iterator r = sm.descendingKeySet().iterator();
869	<	k = (Integer)(r.next());
870	<	assertEquals(three, k);
871	<	k = (Integer)(r.next());
872	<	assertEquals(two, k);
868	>	Iterator<? extends Item> r = sm.descendingKeySet().iterator();
869	>	k = (Item)(r.next());
870	>	mustEqual(three, k);
871	>	k = (Item)(r.next());
872	>	mustEqual(two, k);
873		assertFalse(r.hasNext());
874
875	<	Iterator j = sm.keySet().iterator();
875	>	Iterator<? extends Item> j = sm.keySet().iterator();
876		j.next();
877		j.remove();
878		assertFalse(map.containsKey(two));
879	<	assertEquals(4, map.size());
880	<	assertEquals(1, sm.size());
881	<	assertEquals(three, sm.firstKey());
882	<	assertEquals(three, sm.lastKey());
883	<	assertTrue(sm.remove(three) != null);
879	>	mustEqual(4, map.size());
880	>	mustEqual(1, sm.size());
881	>	mustEqual(three, sm.firstKey());
882	>	mustEqual(three, sm.lastKey());
883	>	mustEqual("C", sm.remove(three));
884		assertTrue(sm.isEmpty());
885	<	assertEquals(3, map.size());
885	>	mustEqual(3, map.size());
886		}
887
888		public void testSubMapContents2() {
889	<	ConcurrentSkipListMap map = map5();
890	<	NavigableMap sm = map.subMap(two, true, three, false);
891	<	assertEquals(1, sm.size());
892	<	assertEquals(two, sm.firstKey());
893	<	assertEquals(two, sm.lastKey());
889	>	ConcurrentSkipListMap<Item,String> map = map5();
890	>	NavigableMap<Item,String> sm = map.subMap(two, true, three, false);
891	>	mustEqual(1, sm.size());
892	>	mustEqual(two, sm.firstKey());
893	>	mustEqual(two, sm.lastKey());
894		assertFalse(sm.containsKey(one));
895		assertTrue(sm.containsKey(two));
896		assertFalse(sm.containsKey(three));
897		assertFalse(sm.containsKey(four));
898		assertFalse(sm.containsKey(five));
899	<	Iterator i = sm.keySet().iterator();
900	<	Object k;
901	<	k = (Integer)(i.next());
902	<	assertEquals(two, k);
899	>	Iterator<? extends Item> i = sm.keySet().iterator();
900	>	Item k;
901	>	k = (Item)(i.next());
902	>	mustEqual(two, k);
903		assertFalse(i.hasNext());
904	<	Iterator r = sm.descendingKeySet().iterator();
905	<	k = (Integer)(r.next());
906	<	assertEquals(two, k);
904	>	Iterator<? extends Item> r = sm.descendingKeySet().iterator();
905	>	k = (Item)(r.next());
906	>	mustEqual(two, k);
907		assertFalse(r.hasNext());
908
909	<	Iterator j = sm.keySet().iterator();
909	>	Iterator<? extends Item> j = sm.keySet().iterator();
910		j.next();
911		j.remove();
912		assertFalse(map.containsKey(two));
913	<	assertEquals(4, map.size());
914	<	assertEquals(0, sm.size());
913	>	mustEqual(4, map.size());
914	>	mustEqual(0, sm.size());
915		assertTrue(sm.isEmpty());
916	<	assertTrue(sm.remove(three) == null);
917	<	assertEquals(4, map.size());
916	>	assertSame(sm.remove(three), null);
917	>	mustEqual(4, map.size());
918		}
919
920		/**
921		* headMap returns map with keys in requested range
922		*/
923		public void testHeadMapContents() {
924	<	ConcurrentSkipListMap map = map5();
925	<	NavigableMap sm = map.headMap(four, false);
924	>	ConcurrentSkipListMap<Item,String> map = map5();
925	>	NavigableMap<Item,String> sm = map.headMap(four, false);
926		assertTrue(sm.containsKey(one));
927		assertTrue(sm.containsKey(two));
928		assertTrue(sm.containsKey(three));
929		assertFalse(sm.containsKey(four));
930		assertFalse(sm.containsKey(five));
931	<	Iterator i = sm.keySet().iterator();
932	<	Object k;
933	<	k = (Integer)(i.next());
934	<	assertEquals(one, k);
935	<	k = (Integer)(i.next());
936	<	assertEquals(two, k);
937	<	k = (Integer)(i.next());
938	<	assertEquals(three, k);
931	>	Iterator<? extends Item> i = sm.keySet().iterator();
932	>	Item k;
933	>	k = (Item)(i.next());
934	>	mustEqual(one, k);
935	>	k = (Item)(i.next());
936	>	mustEqual(two, k);
937	>	k = (Item)(i.next());
938	>	mustEqual(three, k);
939		assertFalse(i.hasNext());
940		sm.clear();
941		assertTrue(sm.isEmpty());
942	<	assertEquals(2, map.size());
943	<	assertEquals(four, map.firstKey());
942	>	mustEqual(2, map.size());
943	>	mustEqual(four, map.firstKey());
944		}
945
946		/**
947		* tailMap returns map with keys in requested range
948		*/
949		public void testTailMapContents() {
950	<	ConcurrentSkipListMap map = map5();
951	<	NavigableMap sm = map.tailMap(two, true);
950	>	ConcurrentSkipListMap<Item,String> map = map5();
951	>	NavigableMap<Item,String> sm = map.tailMap(two, true);
952		assertFalse(sm.containsKey(one));
953		assertTrue(sm.containsKey(two));
954		assertTrue(sm.containsKey(three));
955		assertTrue(sm.containsKey(four));
956		assertTrue(sm.containsKey(five));
957	<	Iterator i = sm.keySet().iterator();
958	<	Object k;
959	<	k = (Integer)(i.next());
960	<	assertEquals(two, k);
961	<	k = (Integer)(i.next());
962	<	assertEquals(three, k);
963	<	k = (Integer)(i.next());
964	<	assertEquals(four, k);
965	<	k = (Integer)(i.next());
958	<	assertEquals(five, k);
957	>	Iterator<? extends Item> i = sm.keySet().iterator();
958	>	Item k = i.next();
959	>	mustEqual(two, k);
960	>	k = i.next();
961	>	mustEqual(three, k);
962	>	k = i.next();
963	>	mustEqual(four, k);
964	>	k = i.next();
965	>	mustEqual(five, k);
966		assertFalse(i.hasNext());
967	<	Iterator r = sm.descendingKeySet().iterator();
968	<	k = (Integer)(r.next());
969	<	assertEquals(five, k);
970	<	k = (Integer)(r.next());
971	<	assertEquals(four, k);
972	<	k = (Integer)(r.next());
973	<	assertEquals(three, k);
974	<	k = (Integer)(r.next());
975	<	assertEquals(two, k);
967	>	Iterator<Item> r = sm.descendingKeySet().iterator();
968	>	k = r.next();
969	>	mustEqual(five, k);
970	>	k = r.next();
971	>	mustEqual(four, k);
972	>	k = r.next();
973	>	mustEqual(three, k);
974	>	k = r.next();
975	>	mustEqual(two, k);
976		assertFalse(r.hasNext());
977
978	<	Iterator ei = sm.entrySet().iterator();
979	<	Map.Entry e;
980	<	e = (Map.Entry)(ei.next());
981	<	assertEquals(two, e.getKey());
982	<	assertEquals("B", e.getValue());
983	<	e = (Map.Entry)(ei.next());
984	<	assertEquals(three, e.getKey());
985	<	assertEquals("C", e.getValue());
986	<	e = (Map.Entry)(ei.next());
987	<	assertEquals(four, e.getKey());
988	<	assertEquals("D", e.getValue());
989	<	e = (Map.Entry)(ei.next());
990	<	assertEquals(five, e.getKey());
991	<	assertEquals("E", e.getValue());
978	>	Iterator<Map.Entry<Item,String>> ei = sm.entrySet().iterator();
979	>	Map.Entry<Item,String> e;
980	>	e = (ei.next());
981	>	mustEqual(two, e.getKey());
982	>	mustEqual("B", e.getValue());
983	>	e = (ei.next());
984	>	mustEqual(three, e.getKey());
985	>	mustEqual("C", e.getValue());
986	>	e = (ei.next());
987	>	mustEqual(four, e.getKey());
988	>	mustEqual("D", e.getValue());
989	>	e = (ei.next());
990	>	mustEqual(five, e.getKey());
991	>	mustEqual("E", e.getValue());
992		assertFalse(i.hasNext());
993
994	<	NavigableMap ssm = sm.tailMap(four, true);
995	<	assertEquals(four, ssm.firstKey());
996	<	assertEquals(five, ssm.lastKey());
997	<	assertTrue(ssm.remove(four) != null);
998	<	assertEquals(1, ssm.size());
999	<	assertEquals(3, sm.size());
1000	<	assertEquals(4, map.size());
994	>	NavigableMap<Item,String> ssm = sm.tailMap(four, true);
995	>	mustEqual(four, ssm.firstKey());
996	>	mustEqual(five, ssm.lastKey());
997	>	mustEqual("D", ssm.remove(four));
998	>	mustEqual(1, ssm.size());
999	>	mustEqual(3, sm.size());
1000	>	mustEqual(4, map.size());
1001		}
1002
1003		Random rnd = new Random(666);
#	Line 999 | Line 1006 | public class ConcurrentSkipListMapTest e
1006		/**
1007		* Submaps of submaps subdivide correctly
1008		*/
1009	<	public void testRecursiveSubMaps() {
1010	<	int mapSize = 1000;
1011	<	Class cl = ConcurrentSkipListMap.class;
1012	<	NavigableMap<Integer, Integer> map = newMap(cl);
1009	>	public void testRecursiveSubMaps() throws Exception {
1010	>	int mapSize = expensiveTests ? 1000 : 100;
1011	>	Class<?> cl = ConcurrentSkipListMap.class;
1012	>	NavigableMap<Item, Item> map = newMap(cl);
1013		bs = new BitSet(mapSize);
1014
1015		populate(map, mapSize);
#	Line 1013 | Line 1020 | public class ConcurrentSkipListMapTest e
1020		check(map,                 0, mapSize - 1, true);
1021		check(map.descendingMap(), 0, mapSize - 1, false);
1022
1023	<	bashSubMap(map.subMap(0, true, mapSize, false),
1023	>	bashSubMap(map.subMap(zero, true, itemFor(mapSize), false),
1024		0, mapSize - 1, true);
1025		}
1026
1027	<	static NavigableMap<Integer, Integer> newMap(Class cl) {
1028	<	NavigableMap<Integer, Integer> result = null;
1029	<	try {
1030	<	result = (NavigableMap<Integer, Integer>) cl.newInstance();
1031	<	} catch(Exception e) {
1025	<	fail();
1026	<	}
1027	<	assertEquals(result.size(), 0);
1027	>	static NavigableMap<Item, Item> newMap(Class<?> cl) throws Exception {
1028	>	@SuppressWarnings("unchecked")
1029	>	NavigableMap<Item, Item> result =
1030	>	(NavigableMap<Item, Item>) cl.getConstructor().newInstance();
1031	>	mustEqual(0, result.size());
1032		assertFalse(result.keySet().iterator().hasNext());
1033		return result;
1034		}
1035
1036	<	void populate(NavigableMap<Integer, Integer> map, int limit) {
1036	>	void populate(NavigableMap<Item, Item> map, int limit) {
1037		for (int i = 0, n = 2 * limit / 3; i < n; i++) {
1038		int key = rnd.nextInt(limit);
1039		put(map, key);
1040		}
1041		}
1042
1043	<	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1043	>	void mutateMap(NavigableMap<Item, Item> map, int min, int max) {
1044		int size = map.size();
1045		int rangeSize = max - min + 1;
1046
#	Line 1046 | Line 1050 | public class ConcurrentSkipListMapTest e
1050		}
1051
1052		// Remove a bunch of entries with iterator
1053	<	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1053	>	for (Iterator<Item> it = map.keySet().iterator(); it.hasNext(); ) {
1054		if (rnd.nextBoolean()) {
1055	<	bs.clear(it.next());
1055	>	bs.clear(it.next().value);
1056		it.remove();
1057		}
1058		}
#	Line 1056 | Line 1060 | public class ConcurrentSkipListMapTest e
1060		// Add entries till we're back to original size
1061		while (map.size() < size) {
1062		int key = min + rnd.nextInt(rangeSize);
1063	<	assertTrue(key >= min && key<= max);
1063	>	assertTrue(key >= min && key <= max);
1064		put(map, key);
1065		}
1066		}
1067
1068	<	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1068	>	void mutateSubMap(NavigableMap<Item, Item> map, int min, int max) {
1069		int size = map.size();
1070		int rangeSize = max - min + 1;
1071
#	Line 1071 | Line 1075 | public class ConcurrentSkipListMapTest e
1075		}
1076
1077		// Remove a bunch of entries with iterator
1078	<	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1078	>	for (Iterator<Item> it = map.keySet().iterator(); it.hasNext(); ) {
1079		if (rnd.nextBoolean()) {
1080	<	bs.clear(it.next());
1080	>	bs.clear(it.next().value);
1081		it.remove();
1082		}
1083		}
#	Line 1081 | Line 1085 | public class ConcurrentSkipListMapTest e
1085		// Add entries till we're back to original size
1086		while (map.size() < size) {
1087		int key = min - 5 + rnd.nextInt(rangeSize + 10);
1088	<	if (key >= min && key<= max) {
1088	>	if (key >= min && key <= max) {
1089		put(map, key);
1090		} else {
1091		try {
1092	<	map.put(key, 2 * key);
1093	<	fail();
1094	<	} catch(IllegalArgumentException e) {
1091	<	// expected
1092	<	}
1092	>	map.put(itemFor(key), itemFor(2 * key));
1093	>	shouldThrow();
1094	>	} catch (IllegalArgumentException success) {}
1095		}
1096		}
1097		}
1098
1099	<	void put(NavigableMap<Integer, Integer> map, int key) {
1100	<	if (map.put(key, 2 * key) == null)
1099	>	void put(NavigableMap<Item, Item> map, int key) {
1100	>	if (map.put(itemFor(key), itemFor(2 * key)) == null)
1101		bs.set(key);
1102		}
1103
1104	<	void remove(NavigableMap<Integer, Integer> map, int key) {
1105	<	if (map.remove(key) != null)
1104	>	void remove(NavigableMap<Item, Item> map, int key) {
1105	>	if (map.remove(itemFor(key)) != null)
1106		bs.clear(key);
1107		}
1108
1109	<	void bashSubMap(NavigableMap<Integer, Integer> map,
1109	>	void bashSubMap(NavigableMap<Item, Item> map,
1110		int min, int max, boolean ascending) {
1111		check(map, min, max, ascending);
1112		check(map.descendingMap(), min, max, !ascending);
#	Line 1120 | Line 1122 | public class ConcurrentSkipListMapTest e
1122
1123		// headMap - pick direction and endpoint inclusion randomly
1124		boolean incl = rnd.nextBoolean();
1125	<	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1125	>	NavigableMap<Item,Item> hm = map.headMap(itemFor(midPoint), incl);
1126		if (ascending) {
1127		if (rnd.nextBoolean())
1128		bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
#	Line 1137 | Line 1139 | public class ConcurrentSkipListMapTest e
1139
1140		// tailMap - pick direction and endpoint inclusion randomly
1141		incl = rnd.nextBoolean();
1142	<	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1142	>	NavigableMap<Item,Item> tm = map.tailMap(itemFor(midPoint),incl);
1143		if (ascending) {
1144		if (rnd.nextBoolean())
1145		bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
#	Line 1162 | Line 1164 | public class ConcurrentSkipListMapTest e
1164		boolean lowIncl = rnd.nextBoolean();
1165		boolean highIncl = rnd.nextBoolean();
1166		if (ascending) {
1167	<	NavigableMap<Integer,Integer> sm = map.subMap(
1168	<	endpoints[0], lowIncl, endpoints[1], highIncl);
1167	>	NavigableMap<Item,Item> sm = map.subMap(
1168	>	itemFor(endpoints[0]), lowIncl, itemFor(endpoints[1]), highIncl);
1169		if (rnd.nextBoolean())
1170		bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1171		endpoints[1] - (highIncl ? 0 : 1), true);
#	Line 1171 | Line 1173 | public class ConcurrentSkipListMapTest e
1173		bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1174		endpoints[1] - (highIncl ? 0 : 1), false);
1175		} else {
1176	<	NavigableMap<Integer,Integer> sm = map.subMap(
1177	<	endpoints[1], highIncl, endpoints[0], lowIncl);
1176	>	NavigableMap<Item,Item> sm = map.subMap(
1177	>	itemFor(endpoints[1]), highIncl, itemFor(endpoints[0]), lowIncl);
1178		if (rnd.nextBoolean())
1179		bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1180		endpoints[1] - (highIncl ? 0 : 1), false);
#	Line 1185 | Line 1187 | public class ConcurrentSkipListMapTest e
1187		/**
1188		* min and max are both inclusive.  If max < min, interval is empty.
1189		*/
1190	<	void check(NavigableMap<Integer, Integer> map,
1190	>	void check(NavigableMap<Item, Item> map,
1191		final int min, final int max, final boolean ascending) {
1192	<	class ReferenceSet {
1192	>	class ReferenceSet {
1193		int lower(int key) {
1194		return ascending ? lowerAscending(key) : higherAscending(key);
1195		}
#	Line 1218 | Line 1220 | public class ConcurrentSkipListMapTest e
1220		// BitSet should support this! Test would run much faster
1221		while (key >= min) {
1222		if (bs.get(key))
1223	<	return(key);
1223	>	return key;
1224		key--;
1225		}
1226		return -1;
#	Line 1249 | Line 1251 | public class ConcurrentSkipListMapTest e
1251		int size = 0;
1252		for (int i = min; i <= max; i++) {
1253		boolean bsContainsI = bs.get(i);
1254	<	assertEquals(bsContainsI, map.containsKey(i));
1254	>	mustEqual(bsContainsI, map.containsKey(itemFor(i)));
1255		if (bsContainsI)
1256		size++;
1257		}
1258	<	assertEquals(map.size(), size);
1258	>	mustEqual(size, map.size());
1259
1260		// Test contents using contains keySet iterator
1261		int size2 = 0;
1262		int previousKey = -1;
1263	<	for (int key : map.keySet()) {
1264	<	assertTrue(bs.get(key));
1263	>	for (Item key : map.keySet()) {
1264	>	assertTrue(bs.get(key.value));
1265		size2++;
1266		assertTrue(previousKey < 0 ||
1267	<	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1268	<	previousKey = key;
1267	>	(ascending ? key.value - previousKey > 0 : key.value - previousKey < 0));
1268	>	previousKey = key.value;
1269		}
1270	<	assertEquals(size2, size);
1270	>	mustEqual(size2, size);
1271
1272		// Test navigation ops
1273		for (int key = min - 1; key <= max + 1; key++) {
1274	<	assertEq(map.lowerKey(key), rs.lower(key));
1275	<	assertEq(map.floorKey(key), rs.floor(key));
1276	<	assertEq(map.higherKey(key), rs.higher(key));
1277	<	assertEq(map.ceilingKey(key), rs.ceiling(key));
1274	>	Item k = itemFor(key);
1275	>	assertEq(map.lowerKey(k), rs.lower(key));
1276	>	assertEq(map.floorKey(k), rs.floor(key));
1277	>	assertEq(map.higherKey(k), rs.higher(key));
1278	>	assertEq(map.ceilingKey(k), rs.ceiling(key));
1279		}
1280
1281		// Test extrema
#	Line 1280 | Line 1283 | public class ConcurrentSkipListMapTest e
1283		assertEq(map.firstKey(), rs.first());
1284		assertEq(map.lastKey(), rs.last());
1285		} else {
1286	<	assertEq(rs.first(), -1);
1287	<	assertEq(rs.last(),  -1);
1286	>	mustEqual(rs.first(), -1);
1287	>	mustEqual(rs.last(),  -1);
1288		try {
1289		map.firstKey();
1290	<	fail();
1291	<	} catch(NoSuchElementException e) {
1289	<	// expected
1290	<	}
1290	>	shouldThrow();
1291	>	} catch (NoSuchElementException success) {}
1292		try {
1293		map.lastKey();
1294	<	fail();
1295	<	} catch(NoSuchElementException e) {
1295	<	// expected
1296	<	}
1294	>	shouldThrow();
1295	>	} catch (NoSuchElementException success) {}
1296		}
1297		}
1298
1299	<	static void assertEq(Integer i, int j) {
1299	>	static void assertEq(Item i, int j) {
1300		if (i == null)
1301	<	assertEquals(j, -1);
1301	>	mustEqual(j, -1);
1302		else
1303	<	assertEquals((int) i, j);
1303	>	mustEqual(i, j);
1304		}
1305
1306	<	static boolean eq(Integer i, int j) {
1307	<	return i == null ? j == -1 : i == j;
1306	>	static boolean eq(Item i, int j) {
1307	>	return (i == null) ? j == -1 : i.value == j;
1308		}
1309
1310		}

Diff Legend

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