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