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.Arrays;

    35 import java.util.BitSet;

    36 import java.util.Collection;

    37 import java.util.Iterator;

    38 import java.util.Map;

    39 import java.util.NavigableMap;

    40 import java.util.NavigableSet;

    41 import java.util.NoSuchElementException;

    42 import java.util.Random;

    43 import java.util.Set;

    44 import java.util.TreeMap;

    45 

    46 import junit.framework.Test;

    47 import junit.framework.TestSuite;

    48 

    49 public class TreeMapTest extends JSR166TestCase {

    50     public static void main(String[] args) {

    51         main(suite(), args);

    52     }

    53     public static Test suite() {

    54         return new TestSuite(TreeMapTest.class);

    55     }

    56 

    57     /**

    58      * Returns a new map from Integers 1-5 to Strings "A"-"E".

    59      */

    60     private static TreeMap map5() {

    61         TreeMap map = new TreeMap();

    62         assertTrue(map.isEmpty());

    63         map.put(one, "A");

    64         map.put(five, "E");

    65         map.put(three, "C");

    66         map.put(two, "B");

    67         map.put(four, "D");

    68         assertFalse(map.isEmpty());

    69         assertEquals(5, map.size());

    70         return map;

    71     }

    72 

    73     /**

    74      * clear removes all pairs

    75      */

    76     public void testClear() {

    77         TreeMap map = map5();

    78         map.clear();

    79         assertEquals(0, map.size());

    80     }

    81 

    82     /**

    83      * copy constructor creates map equal to source map

    84      */

    85     public void testConstructFromSorted() {

    86         TreeMap map = map5();

    87         TreeMap map2 = new TreeMap(map);

    88         assertEquals(map, map2);

    89     }

    90 

    91     /**

    92      * Maps with same contents are equal

    93      */

    94     public void testEquals() {

    95         TreeMap map1 = map5();

    96         TreeMap map2 = map5();

    97         assertEquals(map1, map2);

    98         assertEquals(map2, map1);

    99         map1.clear();

   100         assertFalse(map1.equals(map2));

   101         assertFalse(map2.equals(map1));

   102     }

   103 

   104     /**

   105      * containsKey returns true for contained key

   106      */

   107     public void testContainsKey() {

   108         TreeMap map = map5();

   109         assertTrue(map.containsKey(one));

   110         assertFalse(map.containsKey(zero));

   111     }

   112 

   113     /**

   114      * containsValue returns true for held values

   115      */

   116     public void testContainsValue() {

   117         TreeMap map = map5();

   118         assertTrue(map.containsValue("A"));

   119         assertFalse(map.containsValue("Z"));

   120     }

   121 

   122     /**

   123      * get returns the correct element at the given key,

   124      * or null if not present

   125      */

   126     public void testGet() {

   127         TreeMap map = map5();

   128         assertEquals("A", (String)map.get(one));

   129         TreeMap empty = new TreeMap();

   130         assertNull(empty.get(one));

   131     }

   132 

   133     /**

   134      * isEmpty is true of empty map and false for non-empty

   135      */

   136     public void testIsEmpty() {

   137         TreeMap empty = new TreeMap();

   138         TreeMap map = map5();

   139         assertTrue(empty.isEmpty());

   140         assertFalse(map.isEmpty());

   141     }

   142 

   143     /**

   144      * firstKey returns first key

   145      */

   146     public void testFirstKey() {

   147         TreeMap map = map5();

   148         assertEquals(one, map.firstKey());

   149     }

   150 

   151     /**

   152      * lastKey returns last key

   153      */

   154     public void testLastKey() {

   155         TreeMap map = map5();

   156         assertEquals(five, map.lastKey());

   157     }

   158 

   159     /**

   160      * keySet.toArray returns contains all keys

   161      */

   162     public void testKeySetToArray() {

   163         TreeMap map = map5();

   164         Set s = map.keySet();

   165         Object[] ar = s.toArray();

   166         assertTrue(s.containsAll(Arrays.asList(ar)));

   167         assertEquals(5, ar.length);

   168         ar[0] = m10;

   169         assertFalse(s.containsAll(Arrays.asList(ar)));

   170     }

   171 

   172     /**

   173      * descendingkeySet.toArray returns contains all keys

   174      */

   175     public void testDescendingKeySetToArray() {

   176         TreeMap map = map5();

   177         Set s = map.descendingKeySet();

   178         Object[] ar = s.toArray();

   179         assertEquals(5, ar.length);

   180         assertTrue(s.containsAll(Arrays.asList(ar)));

   181         ar[0] = m10;

   182         assertFalse(s.containsAll(Arrays.asList(ar)));

   183     }

   184 

   185     /**

   186      * keySet returns a Set containing all the keys

   187      */

   188     public void testKeySet() {

   189         TreeMap map = map5();

   190         Set s = map.keySet();

   191         assertEquals(5, s.size());

   192         assertTrue(s.contains(one));

   193         assertTrue(s.contains(two));

   194         assertTrue(s.contains(three));

   195         assertTrue(s.contains(four));

   196         assertTrue(s.contains(five));

   197     }

   198 

   199     /**

   200      * keySet is ordered

   201      */

   202     public void testKeySetOrder() {

   203         TreeMap map = map5();

   204         Set s = map.keySet();

   205         Iterator i = s.iterator();

   206         Integer last = (Integer)i.next();

   207         assertEquals(last, one);

   208         int count = 1;

   209         while (i.hasNext()) {

   210             Integer k = (Integer)i.next();

   211             assertTrue(last.compareTo(k) < 0);

   212             last = k;

   213             ++count;

   214         }

   215         assertEquals(5, count);

   216     }

   217 

   218     /**

   219      * descending iterator of key set is inverse ordered

   220      */

   221     public void testKeySetDescendingIteratorOrder() {

   222         TreeMap map = map5();

   223         NavigableSet s = map.navigableKeySet();

   224         Iterator i = s.descendingIterator();

   225         Integer last = (Integer)i.next();

   226         assertEquals(last, five);

   227         int count = 1;

   228         while (i.hasNext()) {

   229             Integer k = (Integer)i.next();

   230             assertTrue(last.compareTo(k) > 0);

   231             last = k;

   232             ++count;

   233         }

   234         assertEquals(5, count);

   235     }

   236 

   237     /**

   238      * descendingKeySet is ordered

   239      */

   240     public void testDescendingKeySetOrder() {

   241         TreeMap map = map5();

   242         Set s = map.descendingKeySet();

   243         Iterator i = s.iterator();

   244         Integer last = (Integer)i.next();

   245         assertEquals(last, five);

   246         int count = 1;

   247         while (i.hasNext()) {

   248             Integer k = (Integer)i.next();

   249             assertTrue(last.compareTo(k) > 0);

   250             last = k;

   251             ++count;

   252         }

   253         assertEquals(5, count);

   254     }

   255 

   256     /**

   257      * descending iterator of descendingKeySet is ordered

   258      */

   259     public void testDescendingKeySetDescendingIteratorOrder() {

   260         TreeMap map = map5();

   261         NavigableSet s = map.descendingKeySet();

   262         Iterator i = s.descendingIterator();

   263         Integer last = (Integer)i.next();

   264         assertEquals(last, one);

   265         int count = 1;

   266         while (i.hasNext()) {

   267             Integer k = (Integer)i.next();

   268             assertTrue(last.compareTo(k) < 0);

   269             last = k;

   270             ++count;

   271         }

   272         assertEquals(5, count);

   273     }

   274 

   275     /**

   276      * values collection contains all values

   277      */

   278     public void testValues() {

   279         TreeMap map = map5();

   280         Collection s = map.values();

   281         assertEquals(5, s.size());

   282         assertTrue(s.contains("A"));

   283         assertTrue(s.contains("B"));

   284         assertTrue(s.contains("C"));

   285         assertTrue(s.contains("D"));

   286         assertTrue(s.contains("E"));

   287     }

   288 

   289     /**

   290      * entrySet contains all pairs

   291      */

   292     public void testEntrySet() {

   293         TreeMap map = map5();

   294         Set s = map.entrySet();

   295         assertEquals(5, s.size());

   296         Iterator it = s.iterator();

   297         while (it.hasNext()) {

   298             Map.Entry e = (Map.Entry) it.next();

   299             assertTrue(

   300                        (e.getKey().equals(one) && e.getValue().equals("A")) ||

   301                        (e.getKey().equals(two) && e.getValue().equals("B")) ||

   302                        (e.getKey().equals(three) && e.getValue().equals("C")) ||

   303                        (e.getKey().equals(four) && e.getValue().equals("D")) ||

   304                        (e.getKey().equals(five) && e.getValue().equals("E")));

   305         }

   306     }

   307 

   308     /**

   309      * descendingEntrySet contains all pairs

   310      */

   311     public void testDescendingEntrySet() {

   312         TreeMap map = map5();

   313         Set s = map.descendingMap().entrySet();

   314         assertEquals(5, s.size());

   315         Iterator it = s.iterator();

   316         while (it.hasNext()) {

   317             Map.Entry e = (Map.Entry) it.next();

   318             assertTrue(

   319                        (e.getKey().equals(one) && e.getValue().equals("A")) ||

   320                        (e.getKey().equals(two) && e.getValue().equals("B")) ||

   321                        (e.getKey().equals(three) && e.getValue().equals("C")) ||

   322                        (e.getKey().equals(four) && e.getValue().equals("D")) ||

   323                        (e.getKey().equals(five) && e.getValue().equals("E")));

   324         }

   325     }

   326 

   327     /**

   328      * entrySet.toArray contains all entries

   329      */

   330     public void testEntrySetToArray() {

   331         TreeMap map = map5();

   332         Set s = map.entrySet();

   333         Object[] ar = s.toArray();

   334         assertEquals(5, ar.length);

   335         for (int i = 0; i < 5; ++i) {

   336             assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));

   337             assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));

   338         }

   339     }

   340 

   341     /**

   342      * descendingEntrySet.toArray contains all entries

   343      */

   344     public void testDescendingEntrySetToArray() {

   345         TreeMap map = map5();

   346         Set s = map.descendingMap().entrySet();

   347         Object[] ar = s.toArray();

   348         assertEquals(5, ar.length);

   349         for (int i = 0; i < 5; ++i) {

   350             assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));

   351             assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));

   352         }

   353     }

   354 

   355     /**

   356      * putAll adds all key-value pairs from the given map

   357      */

   358     public void testPutAll() {

   359         TreeMap empty = new TreeMap();

   360         TreeMap map = map5();

   361         empty.putAll(map);

   362         assertEquals(5, empty.size());

   363         assertTrue(empty.containsKey(one));

   364         assertTrue(empty.containsKey(two));

   365         assertTrue(empty.containsKey(three));

   366         assertTrue(empty.containsKey(four));

   367         assertTrue(empty.containsKey(five));

   368     }

   369 

   370     /**

   371      * remove removes the correct key-value pair from the map

   372      */

   373     public void testRemove() {

   374         TreeMap map = map5();

   375         map.remove(five);

   376         assertEquals(4, map.size());

   377         assertFalse(map.containsKey(five));

   378     }

   379 

   380     /**

   381      * lowerEntry returns preceding entry.

   382      */

   383     public void testLowerEntry() {

   384         TreeMap map = map5();

   385         Map.Entry e1 = map.lowerEntry(three);

   386         assertEquals(two, e1.getKey());

   387 

   388         Map.Entry e2 = map.lowerEntry(six);

   389         assertEquals(five, e2.getKey());

   390 

   391         Map.Entry e3 = map.lowerEntry(one);

   392         assertNull(e3);

   393 

   394         Map.Entry e4 = map.lowerEntry(zero);

   395         assertNull(e4);

   396     }

   397 

   398     /**

   399      * higherEntry returns next entry.

   400      */

   401     public void testHigherEntry() {

   402         TreeMap map = map5();

   403         Map.Entry e1 = map.higherEntry(three);

   404         assertEquals(four, e1.getKey());

   405 

   406         Map.Entry e2 = map.higherEntry(zero);

   407         assertEquals(one, e2.getKey());

   408 

   409         Map.Entry e3 = map.higherEntry(five);

   410         assertNull(e3);

   411 

   412         Map.Entry e4 = map.higherEntry(six);

   413         assertNull(e4);

   414     }

   415 

   416     /**

   417      * floorEntry returns preceding entry.

   418      */

   419     public void testFloorEntry() {

   420         TreeMap map = map5();

   421         Map.Entry e1 = map.floorEntry(three);

   422         assertEquals(three, e1.getKey());

   423 

   424         Map.Entry e2 = map.floorEntry(six);

   425         assertEquals(five, e2.getKey());

   426 

   427         Map.Entry e3 = map.floorEntry(one);

   428         assertEquals(one, e3.getKey());

   429 

   430         Map.Entry e4 = map.floorEntry(zero);

   431         assertNull(e4);

   432     }

   433 

   434     /**

   435      * ceilingEntry returns next entry.

   436      */

   437     public void testCeilingEntry() {

   438         TreeMap map = map5();

   439         Map.Entry e1 = map.ceilingEntry(three);

   440         assertEquals(three, e1.getKey());

   441 

   442         Map.Entry e2 = map.ceilingEntry(zero);

   443         assertEquals(one, e2.getKey());

   444 

   445         Map.Entry e3 = map.ceilingEntry(five);

   446         assertEquals(five, e3.getKey());

   447 

   448         Map.Entry e4 = map.ceilingEntry(six);

   449         assertNull(e4);

   450     }

   451 

   452     /**

   453      * lowerKey returns preceding element

   454      */

   455     public void testLowerKey() {

   456         TreeMap q = map5();

   457         Object e1 = q.lowerKey(three);

   458         assertEquals(two, e1);

   459 

   460         Object e2 = q.lowerKey(six);

   461         assertEquals(five, e2);

   462 

   463         Object e3 = q.lowerKey(one);

   464         assertNull(e3);

   465 

   466         Object e4 = q.lowerKey(zero);

   467         assertNull(e4);

   468     }

   469 

   470     /**

   471      * higherKey returns next element

   472      */

   473     public void testHigherKey() {

   474         TreeMap q = map5();

   475         Object e1 = q.higherKey(three);

   476         assertEquals(four, e1);

   477 

   478         Object e2 = q.higherKey(zero);

   479         assertEquals(one, e2);

   480 

   481         Object e3 = q.higherKey(five);

   482         assertNull(e3);

   483 

   484         Object e4 = q.higherKey(six);

   485         assertNull(e4);

   486     }

   487 

   488     /**

   489      * floorKey returns preceding element

   490      */

   491     public void testFloorKey() {

   492         TreeMap q = map5();

   493         Object e1 = q.floorKey(three);

   494         assertEquals(three, e1);

   495 

   496         Object e2 = q.floorKey(six);

   497         assertEquals(five, e2);

   498 

   499         Object e3 = q.floorKey(one);

   500         assertEquals(one, e3);

   501 

   502         Object e4 = q.floorKey(zero);

   503         assertNull(e4);

   504     }

   505 

   506     /**

   507      * ceilingKey returns next element

   508      */

   509     public void testCeilingKey() {

   510         TreeMap q = map5();

   511         Object e1 = q.ceilingKey(three);

   512         assertEquals(three, e1);

   513 

   514         Object e2 = q.ceilingKey(zero);

   515         assertEquals(one, e2);

   516 

   517         Object e3 = q.ceilingKey(five);

   518         assertEquals(five, e3);

   519 

   520         Object e4 = q.ceilingKey(six);

   521         assertNull(e4);

   522     }

   523 

   524     /**

   525      * pollFirstEntry returns entries in order

   526      */

   527     public void testPollFirstEntry() {

   528         TreeMap map = map5();

   529         Map.Entry e = map.pollFirstEntry();

   530         assertEquals(one, e.getKey());

   531         assertEquals("A", e.getValue());

   532         e = map.pollFirstEntry();

   533         assertEquals(two, e.getKey());

   534         map.put(one, "A");

   535         e = map.pollFirstEntry();

   536         assertEquals(one, e.getKey());

   537         assertEquals("A", e.getValue());

   538         e = map.pollFirstEntry();

   539         assertEquals(three, e.getKey());

   540         map.remove(four);

   541         e = map.pollFirstEntry();

   542         assertEquals(five, e.getKey());

   543         try {

   544             e.setValue("A");

   545             shouldThrow();

   546         } catch (UnsupportedOperationException success) {}

   547         e = map.pollFirstEntry();

   548         assertNull(e);

   549     }

   550 

   551     /**

   552      * pollLastEntry returns entries in order

   553      */

   554     public void testPollLastEntry() {

   555         TreeMap map = map5();

   556         Map.Entry e = map.pollLastEntry();

   557         assertEquals(five, e.getKey());

   558         assertEquals("E", e.getValue());

   559         e = map.pollLastEntry();

   560         assertEquals(four, e.getKey());

   561         map.put(five, "E");

   562         e = map.pollLastEntry();

   563         assertEquals(five, e.getKey());

   564         assertEquals("E", e.getValue());

   565         e = map.pollLastEntry();

   566         assertEquals(three, e.getKey());

   567         map.remove(two);

   568         e = map.pollLastEntry();

   569         assertEquals(one, e.getKey());

   570         try {

   571             e.setValue("E");

   572             shouldThrow();

   573         } catch (UnsupportedOperationException success) {}

   574         e = map.pollLastEntry();

   575         assertNull(e);

   576     }

   577 

   578     /**

   579      * size returns the correct values

   580      */

   581     public void testSize() {

   582         TreeMap map = map5();

   583         TreeMap empty = new TreeMap();

   584         assertEquals(0, empty.size());

   585         assertEquals(5, map.size());

   586     }

   587 

   588     /**

   589      * toString contains toString of elements

   590      */

   591     public void testToString() {

   592         TreeMap map = map5();

   593         String s = map.toString();

   594         for (int i = 1; i <= 5; ++i) {

   595             assertTrue(s.contains(String.valueOf(i)));

   596         }

   597     }

   598 

   599     // Exception tests

   600 

   601     /**

   602      * get(null) of nonempty map throws NPE

   603      */

   604     public void testGet_NullPointerException() {

   605         TreeMap c = map5();

   606         try {

   607             c.get(null);

   608             shouldThrow();

   609         } catch (NullPointerException success) {}

   610     }

   611 

   612     /**

   613      * containsKey(null) of nonempty map throws NPE

   614      */

   615     public void testContainsKey_NullPointerException() {

   616         TreeMap c = map5();

   617         try {

   618             c.containsKey(null);

   619             shouldThrow();

   620         } catch (NullPointerException success) {}

   621     }

   622 

   623     /**

   624      * remove(null) throws NPE for nonempty map

   625      */

   626     public void testRemove1_NullPointerException() {

   627         TreeMap c = new TreeMap();

   628         c.put("sadsdf", "asdads");

   629         try {

   630             c.remove(null);

   631             shouldThrow();

   632         } catch (NullPointerException success) {}

   633     }

   634 

   635     /**

   636      * A deserialized map equals original

   637      */

   638     public void testSerialization() throws Exception {

   639         NavigableMap x = map5();

   640         NavigableMap y = serialClone(x);

   641 

   642         assertNotSame(x, y);

   643         assertEquals(x.size(), y.size());

   644         assertEquals(x.toString(), y.toString());

   645         assertEquals(x, y);

   646         assertEquals(y, x);

   647     }

   648 

   649     /**

   650      * subMap returns map with keys in requested range

   651      */

   652     public void testSubMapContents() {

   653         TreeMap map = map5();

   654         NavigableMap sm = map.subMap(two, true, four, false);

   655         assertEquals(two, sm.firstKey());

   656         assertEquals(three, sm.lastKey());

   657         assertEquals(2, sm.size());

   658         assertFalse(sm.containsKey(one));

   659         assertTrue(sm.containsKey(two));

   660         assertTrue(sm.containsKey(three));

   661         assertFalse(sm.containsKey(four));

   662         assertFalse(sm.containsKey(five));

   663         Iterator i = sm.keySet().iterator();

   664         Object k;

   665         k = (Integer)(i.next());

   666         assertEquals(two, k);

   667         k = (Integer)(i.next());

   668         assertEquals(three, k);

   669         assertFalse(i.hasNext());

   670         Iterator r = sm.descendingKeySet().iterator();

   671         k = (Integer)(r.next());

   672         assertEquals(three, k);

   673         k = (Integer)(r.next());

   674         assertEquals(two, k);

   675         assertFalse(r.hasNext());

   676 

   677         Iterator j = sm.keySet().iterator();

   678         j.next();

   679         j.remove();

   680         assertFalse(map.containsKey(two));

   681         assertEquals(4, map.size());

   682         assertEquals(1, sm.size());

   683         assertEquals(three, sm.firstKey());

   684         assertEquals(three, sm.lastKey());

   685         assertEquals("C", sm.remove(three));

   686         assertTrue(sm.isEmpty());

   687         assertEquals(3, map.size());

   688     }

   689 

   690     public void testSubMapContents2() {

   691         TreeMap map = map5();

   692         NavigableMap sm = map.subMap(two, true, three, false);

   693         assertEquals(1, sm.size());

   694         assertEquals(two, sm.firstKey());

   695         assertEquals(two, sm.lastKey());

   696         assertFalse(sm.containsKey(one));

   697         assertTrue(sm.containsKey(two));

   698         assertFalse(sm.containsKey(three));

   699         assertFalse(sm.containsKey(four));

   700         assertFalse(sm.containsKey(five));

   701         Iterator i = sm.keySet().iterator();

   702         Object k;

   703         k = (Integer)(i.next());

   704         assertEquals(two, k);

   705         assertFalse(i.hasNext());

   706         Iterator r = sm.descendingKeySet().iterator();

   707         k = (Integer)(r.next());

   708         assertEquals(two, k);

   709         assertFalse(r.hasNext());

   710 

   711         Iterator j = sm.keySet().iterator();

   712         j.next();

   713         j.remove();

   714         assertFalse(map.containsKey(two));

   715         assertEquals(4, map.size());

   716         assertEquals(0, sm.size());

   717         assertTrue(sm.isEmpty());

   718         assertSame(sm.remove(three), null);

   719         assertEquals(4, map.size());

   720     }

   721 

   722     /**

   723      * headMap returns map with keys in requested range

   724      */

   725     public void testHeadMapContents() {

   726         TreeMap map = map5();

   727         NavigableMap sm = map.headMap(four, false);

   728         assertTrue(sm.containsKey(one));

   729         assertTrue(sm.containsKey(two));

   730         assertTrue(sm.containsKey(three));

   731         assertFalse(sm.containsKey(four));

   732         assertFalse(sm.containsKey(five));

   733         Iterator i = sm.keySet().iterator();

   734         Object k;

   735         k = (Integer)(i.next());

   736         assertEquals(one, k);

   737         k = (Integer)(i.next());

   738         assertEquals(two, k);

   739         k = (Integer)(i.next());

   740         assertEquals(three, k);

   741         assertFalse(i.hasNext());

   742         sm.clear();

   743         assertTrue(sm.isEmpty());

   744         assertEquals(2, map.size());

   745         assertEquals(four, map.firstKey());

   746     }

   747 

   748     /**

   749      * headMap returns map with keys in requested range

   750      */

   751     public void testTailMapContents() {

   752         TreeMap map = map5();

   753         NavigableMap sm = map.tailMap(two, true);

   754         assertFalse(sm.containsKey(one));

   755         assertTrue(sm.containsKey(two));

   756         assertTrue(sm.containsKey(three));

   757         assertTrue(sm.containsKey(four));

   758         assertTrue(sm.containsKey(five));

   759         Iterator i = sm.keySet().iterator();

   760         Object k;

   761         k = (Integer)(i.next());

   762         assertEquals(two, k);

   763         k = (Integer)(i.next());

   764         assertEquals(three, k);

   765         k = (Integer)(i.next());

   766         assertEquals(four, k);

   767         k = (Integer)(i.next());

   768         assertEquals(five, k);

   769         assertFalse(i.hasNext());

   770         Iterator r = sm.descendingKeySet().iterator();

   771         k = (Integer)(r.next());

   772         assertEquals(five, k);

   773         k = (Integer)(r.next());

   774         assertEquals(four, k);

   775         k = (Integer)(r.next());

   776         assertEquals(three, k);

   777         k = (Integer)(r.next());

   778         assertEquals(two, k);

   779         assertFalse(r.hasNext());

   780 

   781         Iterator ei = sm.entrySet().iterator();

   782         Map.Entry e;

   783         e = (Map.Entry)(ei.next());

   784         assertEquals(two, e.getKey());

   785         assertEquals("B", e.getValue());

   786         e = (Map.Entry)(ei.next());

   787         assertEquals(three, e.getKey());

   788         assertEquals("C", e.getValue());

   789         e = (Map.Entry)(ei.next());

   790         assertEquals(four, e.getKey());

   791         assertEquals("D", e.getValue());

   792         e = (Map.Entry)(ei.next());

   793         assertEquals(five, e.getKey());

   794         assertEquals("E", e.getValue());

   795         assertFalse(i.hasNext());

   796 

   797         NavigableMap ssm = sm.tailMap(four, true);

   798         assertEquals(four, ssm.firstKey());

   799         assertEquals(five, ssm.lastKey());

   800         assertEquals("D", ssm.remove(four));

   801         assertEquals(1, ssm.size());

   802         assertEquals(3, sm.size());

   803         assertEquals(4, map.size());

   804     }

   805 

   806     Random rnd = new Random(666);

   807     BitSet bs;

   808 

   809     /**

   810      * Submaps of submaps subdivide correctly

   811      */

   812     public void testRecursiveSubMaps() throws Exception {

   813         int mapSize = expensiveTests ? 1000 : 100;

   814         Class cl = TreeMap.class;

   815         NavigableMap<Integer, Integer> map = newMap(cl);

   816         bs = new BitSet(mapSize);

   817 

   818         populate(map, mapSize);

   819         check(map,                 0, mapSize - 1, true);

   820         check(map.descendingMap(), 0, mapSize - 1, false);

   821 

   822         mutateMap(map, 0, mapSize - 1);

   823         check(map,                 0, mapSize - 1, true);

   824         check(map.descendingMap(), 0, mapSize - 1, false);

   825 

   826         bashSubMap(map.subMap(0, true, mapSize, false),

   827                    0, mapSize - 1, true);

   828     }

   829 

   830     static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {

   831         NavigableMap<Integer, Integer> result

   832             = (NavigableMap<Integer, Integer>) cl.newInstance();

   833         assertEquals(0, result.size());

   834         assertFalse(result.keySet().iterator().hasNext());

   835         return result;

   836     }

   837 

   838     void populate(NavigableMap<Integer, Integer> map, int limit) {

   839         for (int i = 0, n = 2 * limit / 3; i < n; i++) {

   840             int key = rnd.nextInt(limit);

   841             put(map, key);

   842         }

   843     }

   844 

   845     void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {

   846         int size = map.size();

   847         int rangeSize = max - min + 1;

   848 

   849         // Remove a bunch of entries directly

   850         for (int i = 0, n = rangeSize / 2; i < n; i++) {

   851             remove(map, min - 5 + rnd.nextInt(rangeSize + 10));

   852         }

   853 

   854         // Remove a bunch of entries with iterator

   855         for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {

   856             if (rnd.nextBoolean()) {

   857                 bs.clear(it.next());

   858                 it.remove();

   859             }

   860         }

   861 

   862         // Add entries till we're back to original size

   863         while (map.size() < size) {

   864             int key = min + rnd.nextInt(rangeSize);

   865             assertTrue(key >= min && key <= max);

   866             put(map, key);

   867         }

   868     }

   869 

   870     void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {

   871         int size = map.size();

   872         int rangeSize = max - min + 1;

   873 

   874         // Remove a bunch of entries directly

   875         for (int i = 0, n = rangeSize / 2; i < n; i++) {

   876             remove(map, min - 5 + rnd.nextInt(rangeSize + 10));

   877         }

   878 

   879         // Remove a bunch of entries with iterator

   880         for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {

   881             if (rnd.nextBoolean()) {

   882                 bs.clear(it.next());

   883                 it.remove();

   884             }

   885         }

   886 

   887         // Add entries till we're back to original size

   888         while (map.size() < size) {

   889             int key = min - 5 + rnd.nextInt(rangeSize + 10);

   890             if (key >= min && key <= max) {

   891                 put(map, key);

   892             } else {

   893                 try {

   894                     map.put(key, 2 * key);

   895                     shouldThrow();

   896                 } catch (IllegalArgumentException success) {}

   897             }

   898         }

   899     }

   900 

   901     void put(NavigableMap<Integer, Integer> map, int key) {

   902         if (map.put(key, 2 * key) == null)

   903             bs.set(key);

   904     }

   905 

   906     void remove(NavigableMap<Integer, Integer> map, int key) {

   907         if (map.remove(key) != null)

   908             bs.clear(key);

   909     }

   910 

   911     void bashSubMap(NavigableMap<Integer, Integer> map,

   912                     int min, int max, boolean ascending) {

   913         check(map, min, max, ascending);

   914         check(map.descendingMap(), min, max, !ascending);

   915 

   916         mutateSubMap(map, min, max);

   917         check(map, min, max, ascending);

   918         check(map.descendingMap(), min, max, !ascending);

   919 

   920         // Recurse

   921         if (max - min < 2)

   922             return;

   923         int midPoint = (min + max) / 2;

   924 

   925         // headMap - pick direction and endpoint inclusion randomly

   926         boolean incl = rnd.nextBoolean();

   927         NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);

   928         if (ascending) {

   929             if (rnd.nextBoolean())

   930                 bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);

   931             else

   932                 bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),

   933                            false);

   934         } else {

   935             if (rnd.nextBoolean())

   936                 bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);

   937             else

   938                 bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,

   939                            true);

   940         }

   941 

   942         // tailMap - pick direction and endpoint inclusion randomly

   943         incl = rnd.nextBoolean();

   944         NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);

   945         if (ascending) {

   946             if (rnd.nextBoolean())

   947                 bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);

   948             else

   949                 bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,

   950                            false);

   951         } else {

   952             if (rnd.nextBoolean()) {

   953                 bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);

   954             } else {

   955                 bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),

   956                            true);

   957             }

   958         }

   959 

   960         // subMap - pick direction and endpoint inclusion randomly

   961         int rangeSize = max - min + 1;

   962         int[] endpoints = new int[2];

   963         endpoints[0] = min + rnd.nextInt(rangeSize);

   964         endpoints[1] = min + rnd.nextInt(rangeSize);

   965         Arrays.sort(endpoints);

   966         boolean lowIncl = rnd.nextBoolean();

   967         boolean highIncl = rnd.nextBoolean();

   968         if (ascending) {

   969             NavigableMap<Integer,Integer> sm = map.subMap(

   970                 endpoints[0], lowIncl, endpoints[1], highIncl);

   971             if (rnd.nextBoolean())

   972                 bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),

   973                            endpoints[1] - (highIncl ? 0 : 1), true);

   974             else

   975                 bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),

   976                            endpoints[1] - (highIncl ? 0 : 1), false);

   977         } else {

   978             NavigableMap<Integer,Integer> sm = map.subMap(

   979                 endpoints[1], highIncl, endpoints[0], lowIncl);

   980             if (rnd.nextBoolean())

   981                 bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),

   982                            endpoints[1] - (highIncl ? 0 : 1), false);

   983             else

   984                 bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),

   985                            endpoints[1] - (highIncl ? 0 : 1), true);

   986         }

   987     }

   988 

   989     /**

   990      * min and max are both inclusive.  If max < min, interval is empty.

   991      */

   992     void check(NavigableMap<Integer, Integer> map,

   993                       final int min, final int max, final boolean ascending) {

   994         class ReferenceSet {

   995             int lower(int key) {

   996                 return ascending ? lowerAscending(key) : higherAscending(key);

   997             }

   998             int floor(int key) {

   999                 return ascending ? floorAscending(key) : ceilingAscending(key);

  1000             }

  1001             int ceiling(int key) {

  1002                 return ascending ? ceilingAscending(key) : floorAscending(key);

  1003             }

  1004             int higher(int key) {

  1005                 return ascending ? higherAscending(key) : lowerAscending(key);

  1006             }

  1007             int first() {

  1008                 return ascending ? firstAscending() : lastAscending();

  1009             }

  1010             int last() {

  1011                 return ascending ? lastAscending() : firstAscending();

  1012             }

  1013             int lowerAscending(int key) {

  1014                 return floorAscending(key - 1);

  1015             }

  1016             int floorAscending(int key) {

  1017                 if (key < min)

  1018                     return -1;

  1019                 else if (key > max)

  1020                     key = max;

  1021 

  1022                 // BitSet should support this! Test would run much faster

  1023                 while (key >= min) {

  1024                     if (bs.get(key))

  1025                         return key;

  1026                     key--;

  1027                 }

  1028                 return -1;

  1029             }

  1030             int ceilingAscending(int key) {

  1031                 if (key < min)

  1032                     key = min;

  1033                 else if (key > max)

  1034                     return -1;

  1035                 int result = bs.nextSetBit(key);

  1036                 return result > max ? -1 : result;

  1037             }

  1038             int higherAscending(int key) {

  1039                 return ceilingAscending(key + 1);

  1040             }

  1041             private int firstAscending() {

  1042                 int result = ceilingAscending(min);

  1043                 return result > max ? -1 : result;

  1044             }

  1045             private int lastAscending() {

  1046                 int result = floorAscending(max);

  1047                 return result < min ? -1 : result;

  1048             }

  1049         }

  1050         ReferenceSet rs = new ReferenceSet();

  1051 

  1052         // Test contents using containsKey

  1053         int size = 0;

  1054         for (int i = min; i <= max; i++) {

  1055             boolean bsContainsI = bs.get(i);

  1056             assertEquals(bsContainsI, map.containsKey(i));

  1057             if (bsContainsI)

  1058                 size++;

  1059         }

  1060         assertEquals(size, map.size());

  1061 

  1062         // Test contents using contains keySet iterator

  1063         int size2 = 0;

  1064         int previousKey = -1;

  1065         for (int key : map.keySet()) {

  1066             assertTrue(bs.get(key));

  1067             size2++;

  1068             assertTrue(previousKey < 0 ||

  1069                 (ascending ? key - previousKey > 0 : key - previousKey < 0));

  1070             previousKey = key;

  1071         }

  1072         assertEquals(size2, size);

  1073 

  1074         // Test navigation ops

  1075         for (int key = min - 1; key <= max + 1; key++) {

  1076             assertEq(map.lowerKey(key), rs.lower(key));

  1077             assertEq(map.floorKey(key), rs.floor(key));

  1078             assertEq(map.higherKey(key), rs.higher(key));

  1079             assertEq(map.ceilingKey(key), rs.ceiling(key));

  1080         }

  1081 

  1082         // Test extrema

  1083         if (map.size() != 0) {

  1084             assertEq(map.firstKey(), rs.first());

  1085             assertEq(map.lastKey(), rs.last());

  1086         } else {

  1087             assertEq(rs.first(), -1);

  1088             assertEq(rs.last(),  -1);

  1089             try {

  1090                 map.firstKey();

  1091                 shouldThrow();

  1092             } catch (NoSuchElementException success) {}

  1093             try {

  1094                 map.lastKey();

  1095                 shouldThrow();

  1096             } catch (NoSuchElementException success) {}

  1097         }

  1098     }

  1099 

  1100     static void assertEq(Integer i, int j) {

  1101         if (i == null)

  1102             assertEquals(j, -1);

  1103         else

  1104             assertEquals((int) i, j);

  1105     }

  1106 

  1107     static boolean eq(Integer i, int j) {

  1108         return i == null ? j == -1 : i == j;

  1109     }

  1110 

  1111 }