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 
7 package jsr166;
8 
9 import java.util.ArrayList;
10 import java.util.Arrays;
11 import java.util.Collection;
12 import java.util.Iterator;
13 import java.util.Map;
14 import java.util.NavigableMap;
15 import java.util.Set;
16 import java.util.SortedMap;
17 import java.util.concurrent.ConcurrentNavigableMap;
18 import java.util.concurrent.ConcurrentSkipListMap;
19 
20 import junit.framework.Test;
21 import junit.framework.TestSuite;
22 
23 public 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      */
map5()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      */
dmap5()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 
map0()68     private static ConcurrentNavigableMap map0() {
69         ConcurrentSkipListMap map = new ConcurrentSkipListMap();
70         assertTrue(map.isEmpty());
71         return map.tailMap(one, true);
72     }
73 
dmap0()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      */
testClear()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      */
testEquals()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      */
testContainsKey()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      */
testContainsValue()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      */
testGet()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      */
testIsEmpty()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      */
testFirstKey()144     public void testFirstKey() {
145         ConcurrentNavigableMap map = map5();
146         assertEquals(one, map.firstKey());
147     }
148 
149     /**
150      * lastKey returns last key
151      */
testLastKey()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      */
testKeySet()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      */
testKeySetOrder()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