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