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