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