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