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