1/*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7package jsr166;
8
9import java.util.ArrayList;
10import java.util.Arrays;
11import java.util.Collection;
12import java.util.Iterator;
13import java.util.Map;
14import java.util.NavigableMap;
15import java.util.Set;
16import java.util.SortedMap;
17import java.util.TreeMap;
18
19import junit.framework.Test;
20import junit.framework.TestSuite;
21
22public 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     */
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
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     */
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
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     */
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     */
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     */
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     */
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     */
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     */
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     */
143    public void testFirstKey() {
144        NavigableMap map = map5();
145        assertEquals(one, map.firstKey());
146    }
147
148    /**
149     * lastKey returns last key
150     */
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     */
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     */
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