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