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 junit.framework.*;
10 import java.util.*;
11 
12 public class TreeSubMapTest extends JSR166TestCase {
13 
14     /**
15      * Returns a new map from Integers 1-5 to Strings "A"-"E".
16      */
map5()17     private static NavigableMap map5() {
18         TreeMap map = new TreeMap();
19         assertTrue(map.isEmpty());
20         map.put(zero, "Z");
21         map.put(one, "A");
22         map.put(five, "E");
23         map.put(three, "C");
24         map.put(two, "B");
25         map.put(four, "D");
26         map.put(seven, "F");
27         assertFalse(map.isEmpty());
28         assertEquals(7, map.size());
29         return map.subMap(one, true, seven, false);
30     }
31 
map0()32     private static NavigableMap map0() {
33         TreeMap map = new TreeMap();
34         assertTrue(map.isEmpty());
35         return map.tailMap(one, true);
36     }
37 
38     /**
39      * Returns a new map from Integers -5 to -1 to Strings "A"-"E".
40      */
dmap5()41     private static NavigableMap dmap5() {
42         TreeMap map = new TreeMap();
43         assertTrue(map.isEmpty());
44         map.put(m1, "A");
45         map.put(m5, "E");
46         map.put(m3, "C");
47         map.put(m2, "B");
48         map.put(m4, "D");
49         assertFalse(map.isEmpty());
50         assertEquals(5, map.size());
51         return map.descendingMap();
52     }
53 
dmap0()54     private static NavigableMap dmap0() {
55         TreeMap map = new TreeMap();
56         assertTrue(map.isEmpty());
57         return map;
58     }
59 
60     /**
61      * clear removes all pairs
62      */
testClear()63     public void testClear() {
64         NavigableMap map = map5();
65         map.clear();
66         assertEquals(0, map.size());
67     }
68 
69     /**
70      * Maps with same contents are equal
71      */
testEquals()72     public void testEquals() {
73         NavigableMap map1 = map5();
74         NavigableMap map2 = map5();
75         assertEquals(map1, map2);
76         assertEquals(map2, map1);
77         map1.clear();
78         assertFalse(map1.equals(map2));
79         assertFalse(map2.equals(map1));
80     }
81 
82     /**
83      * containsKey returns true for contained key
84      */
testContainsKey()85     public void testContainsKey() {
86         NavigableMap map = map5();
87         assertTrue(map.containsKey(one));
88         assertFalse(map.containsKey(zero));
89     }
90 
91     /**
92      * containsValue returns true for held values
93      */
testContainsValue()94     public void testContainsValue() {
95         NavigableMap map = map5();
96         assertTrue(map.containsValue("A"));
97         assertFalse(map.containsValue("Z"));
98     }
99 
100     /**
101      * get returns the correct element at the given key,
102      * or null if not present
103      */
testGet()104     public void testGet() {
105         NavigableMap map = map5();
106         assertEquals("A", (String)map.get(one));
107         NavigableMap empty = map0();
108         assertNull(empty.get(one));
109     }
110 
111     /**
112      * isEmpty is true of empty map and false for non-empty
113      */
testIsEmpty()114     public void testIsEmpty() {
115         NavigableMap empty = map0();
116         NavigableMap map = map5();
117         assertTrue(empty.isEmpty());
118         assertFalse(map.isEmpty());
119     }
120 
121     /**
122      * firstKey returns first key
123      */
testFirstKey()124     public void testFirstKey() {
125         NavigableMap map = map5();
126         assertEquals(one, map.firstKey());
127     }
128 
129     /**
130      * lastKey returns last key
131      */
testLastKey()132     public void testLastKey() {
133         NavigableMap map = map5();
134         assertEquals(five, map.lastKey());
135     }
136 
137     /**
138      * keySet returns a Set containing all the keys
139      */
testKeySet()140     public void testKeySet() {
141         NavigableMap map = map5();
142         Set s = map.keySet();
143         assertEquals(5, s.size());
144         assertTrue(s.contains(one));
145         assertTrue(s.contains(two));
146         assertTrue(s.contains(three));
147         assertTrue(s.contains(four));
148         assertTrue(s.contains(five));
149     }
150 
151     /**
152      * keySet is ordered
153      */
testKeySetOrder()154     public void testKeySetOrder() {
155         NavigableMap map = map5();
156         Set s = map.keySet();
157         Iterator i = s.iterator();
158         Integer last = (Integer)i.next();
159         assertEquals(last, one);
160         while (i.hasNext()) {
161             Integer k = (Integer)i.next();
162             assertTrue(last.compareTo(k) < 0);
163             last = k;
164         }
165     }
166 
167     /**
168      * values collection contains all values
169      */
170     public void testValues() {
171         NavigableMap map = map5();
172         Collection s = map.values();
173         assertEquals(5, s.size());
174         assertTrue(s.contains("A"));
175         assertTrue(s.contains("B"));
176         assertTrue(s.contains("C"));
177         assertTrue(s.contains("D"));
178         assertTrue(s.contains("E"));
179     }
180 
181     /**
182      * entrySet contains all pairs
183      */
184     public void testEntrySet() {
185         NavigableMap map = map5();
186         Set s = map.entrySet();
187         assertEquals(5, s.size());
188         Iterator it = s.iterator();
189         while (it.hasNext()) {
190             Map.Entry e = (Map.Entry) it.next();
191             assertTrue(
192                        (e.getKey().equals(one) && e.getValue().equals("A")) ||
193                        (e.getKey().equals(two) && e.getValue().equals("B")) ||
194                        (e.getKey().equals(three) && e.getValue().equals("C")) ||
195                        (e.getKey().equals(four) && e.getValue().equals("D")) ||
196                        (e.getKey().equals(five) && e.getValue().equals("E")));
197         }
198     }
199 
200     /**
201      * putAll adds all key-value pairs from the given map
202      */
203     public void testPutAll() {
204         NavigableMap empty = map0();
205         NavigableMap map = map5();
206         empty.putAll(map);
207         assertEquals(5, empty.size());
208         assertTrue(empty.containsKey(one));
209         assertTrue(empty.containsKey(two));
210         assertTrue(empty.containsKey(three));
211         assertTrue(empty.containsKey(four));
212         assertTrue(empty.containsKey(five));
213     }
214 
215     /**
216      * remove removes the correct key-value pair from the map
217      */
218     public void testRemove() {
219         NavigableMap map = map5();
220         map.remove(five);
221         assertEquals(4, map.size());
222         assertFalse(map.containsKey(five));
223     }
224 
225     /**
226      * lowerEntry returns preceding entry.
227      */
228     public void testLowerEntry() {
229         NavigableMap map = map5();
230         Map.Entry e1 = map.lowerEntry(three);
231         assertEquals(two, e1.getKey());
232 
233         Map.Entry e2 = map.lowerEntry(six);
234         assertEquals(five, e2.getKey());
235 
236         Map.Entry e3 = map.lowerEntry(one);
237         assertNull(e3);
238 
239         Map.Entry e4 = map.lowerEntry(zero);
240         assertNull(e4);
241     }
242 
243     /**
244      * higherEntry returns next entry.
245      */
246     public void testHigherEntry() {
247         NavigableMap map = map5();
248         Map.Entry e1 = map.higherEntry(three);
249         assertEquals(four, e1.getKey());
250 
251         Map.Entry e2 = map.higherEntry(zero);
252         assertEquals(one, e2.getKey());
253 
254         Map.Entry e3 = map.higherEntry(five);
255         assertNull(e3);
256 
257         Map.Entry e4 = map.higherEntry(six);
258         assertNull(e4);
259     }
260 
261     /**
262      * floorEntry returns preceding entry.
263      */
264     public void testFloorEntry() {
265         NavigableMap map = map5();
266         Map.Entry e1 = map.floorEntry(three);
267         assertEquals(three, e1.getKey());
268 
269         Map.Entry e2 = map.floorEntry(six);
270         assertEquals(five, e2.getKey());
271 
272         Map.Entry e3 = map.floorEntry(one);
273         assertEquals(one, e3.getKey());
274 
275         Map.Entry e4 = map.floorEntry(zero);
276         assertNull(e4);
277     }
278 
279     /**
280      * ceilingEntry returns next entry.
281      */
282     public void testCeilingEntry() {
283         NavigableMap map = map5();
284         Map.Entry e1 = map.ceilingEntry(three);
285         assertEquals(three, e1.getKey());
286 
287         Map.Entry e2 = map.ceilingEntry(zero);
288         assertEquals(one, e2.getKey());
289 
290         Map.Entry e3 = map.ceilingEntry(five);
291         assertEquals(five, e3.getKey());
292 
293         Map.Entry e4 = map.ceilingEntry(six);
294         assertNull(e4);
295     }
296 
297     /**
298      * pollFirstEntry returns entries in order
299      */
300     public void testPollFirstEntry() {
301         NavigableMap map = map5();
302         Map.Entry e = map.pollFirstEntry();
303         assertEquals(one, e.getKey());
304         assertEquals("A", e.getValue());
305         e = map.pollFirstEntry();
306         assertEquals(two, e.getKey());
307         map.put(one, "A");
308         e = map.pollFirstEntry();
309         assertEquals(one, e.getKey());
310         assertEquals("A", e.getValue());
311         e = map.pollFirstEntry();
312         assertEquals(three, e.getKey());
313         map.remove(four);
314         e = map.pollFirstEntry();
315         assertEquals(five, e.getKey());
316         try {
317             e.setValue("A");
318             shouldThrow();
319         } catch (UnsupportedOperationException success) {}
320         assertTrue(map.isEmpty());
321         Map.Entry f = map.firstEntry();
322         assertNull(f);
323         e = map.pollFirstEntry();
324         assertNull(e);
325     }
326 
327     /**
328      * pollLastEntry returns entries in order
329      */
330     public void testPollLastEntry() {
331         NavigableMap map = map5();
332         Map.Entry e = map.pollLastEntry();
333         assertEquals(five, e.getKey());
334         assertEquals("E", e.getValue());
335         e = map.pollLastEntry();
336         assertEquals(four, e.getKey());
337         map.put(five, "E");
338         e = map.pollLastEntry();
339         assertEquals(five, e.getKey());
340         assertEquals("E", e.getValue());
341         e = map.pollLastEntry();
342         assertEquals(three, e.getKey());
343         map.remove(two);
344         e = map.pollLastEntry();
345         assertEquals(one, e.getKey());
346         try {
347             e.setValue("E");
348             shouldThrow();
349         } catch (UnsupportedOperationException success) {}
350         e = map.pollLastEntry();
351         assertNull(e);
352     }
353 
354     /**
355      * size returns the correct values
356      */
357     public void testSize() {
358         NavigableMap map = map5();
359         NavigableMap empty = map0();
360         assertEquals(0, empty.size());
361         assertEquals(5, map.size());
362     }
363 
364     /**
365      * toString contains toString of elements
366      */
367     public void testToString() {
368         NavigableMap map = map5();
369         String s = map.toString();
370         for (int i = 1; i <= 5; ++i) {
371             assertTrue(s.contains(String.valueOf(i)));
372         }
373     }
374 
375     // Exception tests
376 
377     /**
378      * get(null) of nonempty map throws NPE
379      */
380     public void testGet_NullPointerException() {
381         try {
382             NavigableMap c = map5();
383             c.get(null);
384             shouldThrow();
385         } catch (NullPointerException success) {}
386     }
387 
388     /**
389      * containsKey(null) of nonempty map throws NPE
390      */
391     public void testContainsKey_NullPointerException() {
392         try {
393             NavigableMap c = map5();
394             c.containsKey(null);
395             shouldThrow();
396         } catch (NullPointerException success) {}
397     }
398 
399     /**
400      * put(null,x) throws NPE
401      */
402     public void testPut1_NullPointerException() {
403         try {
404             NavigableMap c = map5();
405             c.put(null, "whatever");
406             shouldThrow();
407         } catch (NullPointerException success) {}
408     }
409 
410     /**
411      * remove(null) throws NPE
412      */
413     public void testRemove1_NullPointerException() {
414         try {
415             NavigableMap c = map5();
416             c.remove(null);
417             shouldThrow();
418         } catch (NullPointerException success) {}
419     }
420 
421     /**
422      * A deserialized map equals original
423      */
424     public void testSerialization() throws Exception {
425         NavigableMap x = map5();
426         NavigableMap y = serialClone(x);
427 
428         assertNotSame(x, y);
429         assertEquals(x.size(), y.size());
430         assertEquals(x.toString(), y.toString());
431         assertEquals(x, y);
432         assertEquals(y, x);
433     }
434 
435     /**
436      * subMap returns map with keys in requested range
437      */
438     public void testSubMapContents() {
439         NavigableMap map = map5();
440         SortedMap sm = map.subMap(two, four);
441         assertEquals(two, sm.firstKey());
442         assertEquals(three, sm.lastKey());
443         assertEquals(2, sm.size());
444         assertFalse(sm.containsKey(one));
445         assertTrue(sm.containsKey(two));
446         assertTrue(sm.containsKey(three));
447         assertFalse(sm.containsKey(four));
448         assertFalse(sm.containsKey(five));
449         Iterator i = sm.keySet().iterator();
450         Object k;
451         k = (Integer)(i.next());
452         assertEquals(two, k);
453         k = (Integer)(i.next());
454         assertEquals(three, k);
455         assertFalse(i.hasNext());
456         Iterator j = sm.keySet().iterator();
457         j.next();
458         j.remove();
459         assertFalse(map.containsKey(two));
460         assertEquals(4, map.size());
461         assertEquals(1, sm.size());
462         assertEquals(three, sm.firstKey());
463         assertEquals(three, sm.lastKey());
464         assertEquals("C", sm.remove(three));
465         assertTrue(sm.isEmpty());
466         assertEquals(3, map.size());
467     }
468 
469     public void testSubMapContents2() {
470         NavigableMap map = map5();
471         SortedMap sm = map.subMap(two, three);
472         assertEquals(1, sm.size());
473         assertEquals(two, sm.firstKey());
474         assertEquals(two, sm.lastKey());
475         assertFalse(sm.containsKey(one));
476         assertTrue(sm.containsKey(two));
477         assertFalse(sm.containsKey(three));
478         assertFalse(sm.containsKey(four));
479         assertFalse(sm.containsKey(five));
480         Iterator i = sm.keySet().iterator();
481         Object k;
482         k = (Integer)(i.next());
483         assertEquals(two, k);
484         assertFalse(i.hasNext());
485         Iterator j = sm.keySet().iterator();
486         j.next();
487         j.remove();
488         assertFalse(map.containsKey(two));
489         assertEquals(4, map.size());
490         assertEquals(0, sm.size());
491         assertTrue(sm.isEmpty());
492         assertSame(sm.remove(three), null);
493         assertEquals(4, map.size());
494     }
495 
496     /**
497      * headMap returns map with keys in requested range
498      */
499     public void testHeadMapContents() {
500         NavigableMap map = map5();
501         SortedMap sm = map.headMap(four);
502         assertTrue(sm.containsKey(one));
503         assertTrue(sm.containsKey(two));
504         assertTrue(sm.containsKey(three));
505         assertFalse(sm.containsKey(four));
506         assertFalse(sm.containsKey(five));
507         Iterator i = sm.keySet().iterator();
508         Object k;
509         k = (Integer)(i.next());
510         assertEquals(one, k);
511         k = (Integer)(i.next());
512         assertEquals(two, k);
513         k = (Integer)(i.next());
514         assertEquals(three, k);
515         assertFalse(i.hasNext());
516         sm.clear();
517         assertTrue(sm.isEmpty());
518         assertEquals(2, map.size());
519         assertEquals(four, map.firstKey());
520     }
521 
522     /**
523      * headMap returns map with keys in requested range
524      */
525     public void testTailMapContents() {
526         NavigableMap map = map5();
527         SortedMap sm = map.tailMap(two);
528         assertFalse(sm.containsKey(one));
529         assertTrue(sm.containsKey(two));
530         assertTrue(sm.containsKey(three));
531         assertTrue(sm.containsKey(four));
532         assertTrue(sm.containsKey(five));
533         Iterator i = sm.keySet().iterator();
534         Object k;
535         k = (Integer)(i.next());
536         assertEquals(two, k);
537         k = (Integer)(i.next());
538         assertEquals(three, k);
539         k = (Integer)(i.next());
540         assertEquals(four, k);
541         k = (Integer)(i.next());
542         assertEquals(five, k);
543         assertFalse(i.hasNext());
544 
545         Iterator ei = sm.entrySet().iterator();
546         Map.Entry e;
547         e = (Map.Entry)(ei.next());
548         assertEquals(two, e.getKey());
549         assertEquals("B", e.getValue());
550         e = (Map.Entry)(ei.next());
551         assertEquals(three, e.getKey());
552         assertEquals("C", e.getValue());
553         e = (Map.Entry)(ei.next());
554         assertEquals(four, e.getKey());
555         assertEquals("D", e.getValue());
556         e = (Map.Entry)(ei.next());
557         assertEquals(five, e.getKey());
558         assertEquals("E", e.getValue());
559         assertFalse(i.hasNext());
560 
561         SortedMap ssm = sm.tailMap(four);
562         assertEquals(four, ssm.firstKey());
563         assertEquals(five, ssm.lastKey());
564         assertEquals("D", ssm.remove(four));
565         assertEquals(1, ssm.size());
566         assertEquals(3, sm.size());
567         assertEquals(4, map.size());
568     }
569 
570     /**
571      * clear removes all pairs
572      */
573     public void testDescendingClear() {
574         NavigableMap map = dmap5();
575         map.clear();
576         assertEquals(0, map.size());
577     }
578 
579     /**
580      * Maps with same contents are equal
581      */
582     public void testDescendingEquals() {
583         NavigableMap map1 = dmap5();
584         NavigableMap map2 = dmap5();
585         assertEquals(map1, map2);
586         assertEquals(map2, map1);
587         map1.clear();
588         assertFalse(map1.equals(map2));
589         assertFalse(map2.equals(map1));
590     }
591 
592     /**
593      * containsKey returns true for contained key
594      */
595     public void testDescendingContainsKey() {
596         NavigableMap map = dmap5();
597         assertTrue(map.containsKey(m1));
598         assertFalse(map.containsKey(zero));
599     }
600 
601     /**
602      * containsValue returns true for held values
603      */
604     public void testDescendingContainsValue() {
605         NavigableMap map = dmap5();
606         assertTrue(map.containsValue("A"));
607         assertFalse(map.containsValue("Z"));
608     }
609 
610     /**
611      * get returns the correct element at the given key,
612      * or null if not present
613      */
614     public void testDescendingGet() {
615         NavigableMap map = dmap5();
616         assertEquals("A", (String)map.get(m1));
617         NavigableMap empty = dmap0();
618         assertNull(empty.get(m1));
619     }
620 
621     /**
622      * isEmpty is true of empty map and false for non-empty
623      */
624     public void testDescendingIsEmpty() {
625         NavigableMap empty = dmap0();
626         NavigableMap map = dmap5();
627         assertTrue(empty.isEmpty());
628         assertFalse(map.isEmpty());
629     }
630 
631     /**
632      * firstKey returns first key
633      */
634     public void testDescendingFirstKey() {
635         NavigableMap map = dmap5();
636         assertEquals(m1, map.firstKey());
637     }
638 
639     /**
640      * lastKey returns last key
641      */
642     public void testDescendingLastKey() {
643         NavigableMap map = dmap5();
644         assertEquals(m5, map.lastKey());
645     }
646 
647     /**
648      * keySet returns a Set containing all the keys
649      */
650     public void testDescendingKeySet() {
651         NavigableMap map = dmap5();
652         Set s = map.keySet();
653         assertEquals(5, s.size());
654         assertTrue(s.contains(m1));
655         assertTrue(s.contains(m2));
656         assertTrue(s.contains(m3));
657         assertTrue(s.contains(m4));
658         assertTrue(s.contains(m5));
659     }
660 
661     /**
662      * keySet is ordered
663      */
664     public void testDescendingKeySetOrder() {
665         NavigableMap map = dmap5();
666         Set s = map.keySet();
667         Iterator i = s.iterator();
668         Integer last = (Integer)i.next();
669         assertEquals(last, m1);
670         while (i.hasNext()) {
671             Integer k = (Integer)i.next();
672             assertTrue(last.compareTo(k) > 0);
673             last = k;
674         }
675     }
676 
677     /**
678      * values collection contains all values
679      */
680     public void testDescendingValues() {
681         NavigableMap map = dmap5();
682         Collection s = map.values();
683         assertEquals(5, s.size());
684         assertTrue(s.contains("A"));
685         assertTrue(s.contains("B"));
686         assertTrue(s.contains("C"));
687         assertTrue(s.contains("D"));
688         assertTrue(s.contains("E"));
689     }
690 
691     /**
692      * keySet.toArray returns contains all keys
693      */
694     public void testDescendingAscendingKeySetToArray() {
695         NavigableMap map = dmap5();
696         Set s = map.keySet();
697         Object[] ar = s.toArray();
698         assertTrue(s.containsAll(Arrays.asList(ar)));
699         assertEquals(5, ar.length);
700         ar[0] = m10;
701         assertFalse(s.containsAll(Arrays.asList(ar)));
702     }
703 
704     /**
705      * descendingkeySet.toArray returns contains all keys
706      */
707     public void testDescendingDescendingKeySetToArray() {
708         NavigableMap map = dmap5();
709         Set s = map.descendingKeySet();
710         Object[] ar = s.toArray();
711         assertEquals(5, ar.length);
712         assertTrue(s.containsAll(Arrays.asList(ar)));
713         ar[0] = m10;
714         assertFalse(s.containsAll(Arrays.asList(ar)));
715     }
716 
717     /**
718      * Values.toArray contains all values
719      */
720     public void testDescendingValuesToArray() {
721         NavigableMap map = dmap5();
722         Collection v = map.values();
723         Object[] ar = v.toArray();
724         ArrayList s = new ArrayList(Arrays.asList(ar));
725         assertEquals(5, ar.length);
726         assertTrue(s.contains("A"));
727         assertTrue(s.contains("B"));
728         assertTrue(s.contains("C"));
729         assertTrue(s.contains("D"));
730         assertTrue(s.contains("E"));
731     }
732 
733     /**
734      * entrySet contains all pairs
735      */
736     public void testDescendingEntrySet() {
737         NavigableMap map = dmap5();
738         Set s = map.entrySet();
739         assertEquals(5, s.size());
740         Iterator it = s.iterator();
741         while (it.hasNext()) {
742             Map.Entry e = (Map.Entry) it.next();
743             assertTrue(
744                        (e.getKey().equals(m1) && e.getValue().equals("A")) ||
745                        (e.getKey().equals(m2) && e.getValue().equals("B")) ||
746                        (e.getKey().equals(m3) && e.getValue().equals("C")) ||
747                        (e.getKey().equals(m4) && e.getValue().equals("D")) ||
748                        (e.getKey().equals(m5) && e.getValue().equals("E")));
749         }
750     }
751 
752     /**
753      * putAll adds all key-value pairs from the given map
754      */
755     public void testDescendingPutAll() {
756         NavigableMap empty = dmap0();
757         NavigableMap map = dmap5();
758         empty.putAll(map);
759         assertEquals(5, empty.size());
760         assertTrue(empty.containsKey(m1));
761         assertTrue(empty.containsKey(m2));
762         assertTrue(empty.containsKey(m3));
763         assertTrue(empty.containsKey(m4));
764         assertTrue(empty.containsKey(m5));
765     }
766 
767     /**
768      * remove removes the correct key-value pair from the map
769      */
770     public void testDescendingRemove() {
771         NavigableMap map = dmap5();
772         map.remove(m5);
773         assertEquals(4, map.size());
774         assertFalse(map.containsKey(m5));
775     }
776 
777     /**
778      * lowerEntry returns preceding entry.
779      */
780     public void testDescendingLowerEntry() {
781         NavigableMap map = dmap5();
782         Map.Entry e1 = map.lowerEntry(m3);
783         assertEquals(m2, e1.getKey());
784 
785         Map.Entry e2 = map.lowerEntry(m6);
786         assertEquals(m5, e2.getKey());
787 
788         Map.Entry e3 = map.lowerEntry(m1);
789         assertNull(e3);
790 
791         Map.Entry e4 = map.lowerEntry(zero);
792         assertNull(e4);
793     }
794 
795     /**
796      * higherEntry returns next entry.
797      */
798     public void testDescendingHigherEntry() {
799         NavigableMap map = dmap5();
800         Map.Entry e1 = map.higherEntry(m3);
801         assertEquals(m4, e1.getKey());
802 
803         Map.Entry e2 = map.higherEntry(zero);
804         assertEquals(m1, e2.getKey());
805 
806         Map.Entry e3 = map.higherEntry(m5);
807         assertNull(e3);
808 
809         Map.Entry e4 = map.higherEntry(m6);
810         assertNull(e4);
811     }
812 
813     /**
814      * floorEntry returns preceding entry.
815      */
816     public void testDescendingFloorEntry() {
817         NavigableMap map = dmap5();
818         Map.Entry e1 = map.floorEntry(m3);
819         assertEquals(m3, e1.getKey());
820 
821         Map.Entry e2 = map.floorEntry(m6);
822         assertEquals(m5, e2.getKey());
823 
824         Map.Entry e3 = map.floorEntry(m1);
825         assertEquals(m1, e3.getKey());
826 
827         Map.Entry e4 = map.floorEntry(zero);
828         assertNull(e4);
829     }
830 
831     /**
832      * ceilingEntry returns next entry.
833      */
834     public void testDescendingCeilingEntry() {
835         NavigableMap map = dmap5();
836         Map.Entry e1 = map.ceilingEntry(m3);
837         assertEquals(m3, e1.getKey());
838 
839         Map.Entry e2 = map.ceilingEntry(zero);
840         assertEquals(m1, e2.getKey());
841 
842         Map.Entry e3 = map.ceilingEntry(m5);
843         assertEquals(m5, e3.getKey());
844 
845         Map.Entry e4 = map.ceilingEntry(m6);
846         assertNull(e4);
847     }
848 
849     /**
850      * pollFirstEntry returns entries in order
851      */
852     public void testDescendingPollFirstEntry() {
853         NavigableMap map = dmap5();
854         Map.Entry e = map.pollFirstEntry();
855         assertEquals(m1, e.getKey());
856         assertEquals("A", e.getValue());
857         e = map.pollFirstEntry();
858         assertEquals(m2, e.getKey());
859         map.put(m1, "A");
860         e = map.pollFirstEntry();
861         assertEquals(m1, e.getKey());
862         assertEquals("A", e.getValue());
863         e = map.pollFirstEntry();
864         assertEquals(m3, e.getKey());
865         map.remove(m4);
866         e = map.pollFirstEntry();
867         assertEquals(m5, e.getKey());
868         try {
869             e.setValue("A");
870             shouldThrow();
871         } catch (UnsupportedOperationException success) {}
872         e = map.pollFirstEntry();
873         assertNull(e);
874     }
875 
876     /**
877      * pollLastEntry returns entries in order
878      */
879     public void testDescendingPollLastEntry() {
880         NavigableMap map = dmap5();
881         Map.Entry e = map.pollLastEntry();
882         assertEquals(m5, e.getKey());
883         assertEquals("E", e.getValue());
884         e = map.pollLastEntry();
885         assertEquals(m4, e.getKey());
886         map.put(m5, "E");
887         e = map.pollLastEntry();
888         assertEquals(m5, e.getKey());
889         assertEquals("E", e.getValue());
890         e = map.pollLastEntry();
891         assertEquals(m3, e.getKey());
892         map.remove(m2);
893         e = map.pollLastEntry();
894         assertEquals(m1, e.getKey());
895         try {
896             e.setValue("E");
897             shouldThrow();
898         } catch (UnsupportedOperationException success) {}
899         e = map.pollLastEntry();
900         assertNull(e);
901     }
902 
903     /**
904      * size returns the correct values
905      */
906     public void testDescendingSize() {
907         NavigableMap map = dmap5();
908         NavigableMap empty = dmap0();
909         assertEquals(0, empty.size());
910         assertEquals(5, map.size());
911     }
912 
913     /**
914      * toString contains toString of elements
915      */
916     public void testDescendingToString() {
917         NavigableMap map = dmap5();
918         String s = map.toString();
919         for (int i = 1; i <= 5; ++i) {
920             assertTrue(s.contains(String.valueOf(i)));
921         }
922     }
923 
924     // Exception testDescendings
925 
926     /**
927      * get(null) of nonempty map throws NPE
928      */
929     public void testDescendingGet_NullPointerException() {
930         try {
931             NavigableMap c = dmap5();
932             c.get(null);
933             shouldThrow();
934         } catch (NullPointerException success) {}
935     }
936 
937     /**
938      * put(null,x) throws NPE
939      */
940     public void testDescendingPut1_NullPointerException() {
941         try {
942             NavigableMap c = dmap5();
943             c.put(null, "whatever");
944             shouldThrow();
945         } catch (NullPointerException success) {}
946     }
947 
948     /**
949      * A deserialized map equals original
950      */
951     public void testDescendingSerialization() throws Exception {
952         NavigableMap x = dmap5();
953         NavigableMap y = serialClone(x);
954 
955         assertNotSame(x, y);
956         assertEquals(x.size(), y.size());
957         assertEquals(x.toString(), y.toString());
958         assertEquals(x, y);
959         assertEquals(y, x);
960     }
961 
962     /**
963      * subMap returns map with keys in requested range
964      */
965     public void testDescendingSubMapContents() {
966         NavigableMap map = dmap5();
967         SortedMap sm = map.subMap(m2, m4);
968         assertEquals(m2, sm.firstKey());
969         assertEquals(m3, sm.lastKey());
970         assertEquals(2, sm.size());
971         assertFalse(sm.containsKey(m1));
972         assertTrue(sm.containsKey(m2));
973         assertTrue(sm.containsKey(m3));
974         assertFalse(sm.containsKey(m4));
975         assertFalse(sm.containsKey(m5));
976         Iterator i = sm.keySet().iterator();
977         Object k;
978         k = (Integer)(i.next());
979         assertEquals(m2, k);
980         k = (Integer)(i.next());
981         assertEquals(m3, k);
982         assertFalse(i.hasNext());
983         Iterator j = sm.keySet().iterator();
984         j.next();
985         j.remove();
986         assertFalse(map.containsKey(m2));
987         assertEquals(4, map.size());
988         assertEquals(1, sm.size());
989         assertEquals(m3, sm.firstKey());
990         assertEquals(m3, sm.lastKey());
991         assertEquals("C", sm.remove(m3));
992         assertTrue(sm.isEmpty());
993         assertEquals(3, map.size());
994     }
995 
996     public void testDescendingSubMapContents2() {
997         NavigableMap map = dmap5();
998         SortedMap sm = map.subMap(m2, m3);
999         assertEquals(1, sm.size());
1000         assertEquals(m2, sm.firstKey());
1001         assertEquals(m2, sm.lastKey());
1002         assertFalse(sm.containsKey(m1));
1003         assertTrue(sm.containsKey(m2));
1004         assertFalse(sm.containsKey(m3));
1005         assertFalse(sm.containsKey(m4));
1006         assertFalse(sm.containsKey(m5));
1007         Iterator i = sm.keySet().iterator();
1008         Object k;
1009         k = (Integer)(i.next());
1010         assertEquals(m2, k);
1011         assertFalse(i.hasNext());
1012         Iterator j = sm.keySet().iterator();
1013         j.next();
1014         j.remove();
1015         assertFalse(map.containsKey(m2));
1016         assertEquals(4, map.size());
1017         assertEquals(0, sm.size());
1018         assertTrue(sm.isEmpty());
1019         assertSame(sm.remove(m3), null);
1020         assertEquals(4, map.size());
1021     }
1022 
1023     /**
1024      * headMap returns map with keys in requested range
1025      */
1026     public void testDescendingHeadMapContents() {
1027         NavigableMap map = dmap5();
1028         SortedMap sm = map.headMap(m4);
1029         assertTrue(sm.containsKey(m1));
1030         assertTrue(sm.containsKey(m2));
1031         assertTrue(sm.containsKey(m3));
1032         assertFalse(sm.containsKey(m4));
1033         assertFalse(sm.containsKey(m5));
1034         Iterator i = sm.keySet().iterator();
1035         Object k;
1036         k = (Integer)(i.next());
1037         assertEquals(m1, k);
1038         k = (Integer)(i.next());
1039         assertEquals(m2, k);
1040         k = (Integer)(i.next());
1041         assertEquals(m3, k);
1042         assertFalse(i.hasNext());
1043         sm.clear();
1044         assertTrue(sm.isEmpty());
1045         assertEquals(2, map.size());
1046         assertEquals(m4, map.firstKey());
1047     }
1048 
1049     /**
1050      * headMap returns map with keys in requested range
1051      */
1052     public void testDescendingTailMapContents() {
1053         NavigableMap map = dmap5();
1054         SortedMap sm = map.tailMap(m2);
1055         assertFalse(sm.containsKey(m1));
1056         assertTrue(sm.containsKey(m2));
1057         assertTrue(sm.containsKey(m3));
1058         assertTrue(sm.containsKey(m4));
1059         assertTrue(sm.containsKey(m5));
1060         Iterator i = sm.keySet().iterator();
1061         Object k;
1062         k = (Integer)(i.next());
1063         assertEquals(m2, k);
1064         k = (Integer)(i.next());
1065         assertEquals(m3, k);
1066         k = (Integer)(i.next());
1067         assertEquals(m4, k);
1068         k = (Integer)(i.next());
1069         assertEquals(m5, k);
1070         assertFalse(i.hasNext());
1071 
1072         Iterator ei = sm.entrySet().iterator();
1073         Map.Entry e;
1074         e = (Map.Entry)(ei.next());
1075         assertEquals(m2, e.getKey());
1076         assertEquals("B", e.getValue());
1077         e = (Map.Entry)(ei.next());
1078         assertEquals(m3, e.getKey());
1079         assertEquals("C", e.getValue());
1080         e = (Map.Entry)(ei.next());
1081         assertEquals(m4, e.getKey());
1082         assertEquals("D", e.getValue());
1083         e = (Map.Entry)(ei.next());
1084         assertEquals(m5, e.getKey());
1085         assertEquals("E", e.getValue());
1086         assertFalse(i.hasNext());
1087 
1088         SortedMap ssm = sm.tailMap(m4);
1089         assertEquals(m4, ssm.firstKey());
1090         assertEquals(m5, ssm.lastKey());
1091         assertEquals("D", ssm.remove(m4));
1092         assertEquals(1, ssm.size());
1093         assertEquals(3, sm.size());
1094         assertEquals(4, map.size());
1095     }
1096 
1097 }
1098