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 junit.framework.*;
10import java.util.*;
11
12public class TreeSubMapTest extends JSR166TestCase {
13
14    /**
15     * Returns a new map from Integers 1-5 to Strings "A"-"E".
16     */
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
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     */
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
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     */
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     */
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     */
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     */
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     */
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     */
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     */
124    public void testFirstKey() {
125        NavigableMap map = map5();
126        assertEquals(one, map.firstKey());
127    }
128
129    /**
130     * lastKey returns last key
131     */
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     */
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     */
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