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