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