libcore/luni/src/test/java/tests/api/java/util/concurrent/ConcurrentSkipListSubMapTest.java

   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/licenses/publicdomain
   5  */
   6
   7 package tests.api.java.util.concurrent; // android-added
   8
   9 import junit.framework.*;
  10 import java.util.*;
  11 import java.util.concurrent.*;
  12 import java.io.*;
  13
  14 public class ConcurrentSkipListSubMapTest extends JSR166TestCase {
  15     public static Test suite() {
  16         return new TestSuite(ConcurrentSkipListSubMapTest.class);
  17     }
  18
  19     /**
  20      * Create a map from Integers 1-5 to Strings "A"-"E".
  21      */
  22     private static ConcurrentNavigableMap map5() {
  23         ConcurrentSkipListMap map = new ConcurrentSkipListMap();
  24         assertTrue(map.isEmpty());
  25         map.put(zero, "Z");
  26         map.put(one, "A");
  27         map.put(five, "E");
  28         map.put(three, "C");
  29         map.put(two, "B");
  30         map.put(four, "D");
  31         map.put(seven, "F");
  32         assertFalse(map.isEmpty());
  33         assertEquals(7, map.size());
  34         return map.subMap(one, true, seven, false);
  35     }
  36
  37     /**
  38      * Create a map from Integers -5 to -1 to Strings "A"-"E".
  39      */
  40     private static ConcurrentNavigableMap dmap5() {
  41         ConcurrentSkipListMap map = new ConcurrentSkipListMap();
  42         assertTrue(map.isEmpty());
  43         map.put(m1, "A");
  44         map.put(m5, "E");
  45         map.put(m3, "C");
  46         map.put(m2, "B");
  47         map.put(m4, "D");
  48         assertFalse(map.isEmpty());
  49         assertEquals(5, map.size());
  50         return map.descendingMap();
  51     }
  52
  53     private static ConcurrentNavigableMap map0() {
  54         ConcurrentSkipListMap map = new ConcurrentSkipListMap();
  55         assertTrue(map.isEmpty());
  56         return map.tailMap(one, true);
  57     }
  58
  59     private static ConcurrentNavigableMap dmap0() {
  60         ConcurrentSkipListMap map = new ConcurrentSkipListMap();
  61         assertTrue(map.isEmpty());
  62         return map;
  63     }
  64
  65     /**
  66      *  clear removes all pairs
  67      */
  68     public void testClear() {
  69         ConcurrentNavigableMap map = map5();
  70         map.clear();
  71         assertEquals(map.size(), 0);
  72     }
  73
  74
  75     /**
  76      *  Maps with same contents are equal
  77      */
  78     public void testEquals() {
  79         ConcurrentNavigableMap map1 = map5();
  80         ConcurrentNavigableMap map2 = map5();
  81         assertEquals(map1, map2);
  82         assertEquals(map2, map1);
  83         map1.clear();
  84         assertFalse(map1.equals(map2));
  85         assertFalse(map2.equals(map1));
  86     }
  87
  88     /**
  89      *  containsKey returns true for contained key
  90      */
  91     public void testContainsKey() {
  92         ConcurrentNavigableMap map = map5();
  93         assertTrue(map.containsKey(one));
  94         assertFalse(map.containsKey(zero));
  95     }
  96
  97     /**
  98      *  containsValue returns true for held values
  99      */
 100     public void testContainsValue() {
 101         ConcurrentNavigableMap map = map5();
 102         assertTrue(map.containsValue("A"));
 103         assertFalse(map.containsValue("Z"));
 104     }
 105
 106     /**
 107      *  get returns the correct element at the given key,
 108      *  or null if not present
 109      */
 110     public void testGet() {
 111         ConcurrentNavigableMap map = map5();
 112         assertEquals("A", (String)map.get(one));
 113         ConcurrentNavigableMap empty = map0();
 114         assertNull(empty.get(one));
 115     }
 116
 117     /**
 118      *  isEmpty is true of empty map and false for non-empty
 119      */
 120     public void testIsEmpty() {
 121         ConcurrentNavigableMap empty = map0();
 122         ConcurrentNavigableMap map = map5();
 123         assertTrue(empty.isEmpty());
 124         assertFalse(map.isEmpty());
 125     }
 126
 127     /**
 128      *   firstKey returns first key
 129      */
 130     public void testFirstKey() {
 131         ConcurrentNavigableMap map = map5();
 132         assertEquals(one, map.firstKey());
 133     }
 134
 135     /**
 136      *   lastKey returns last key
 137      */
 138     public void testLastKey() {
 139         ConcurrentNavigableMap map = map5();
 140         assertEquals(five, map.lastKey());
 141     }
 142
 143
 144     /**
 145      *   keySet returns a Set containing all the keys
 146      */
 147     public void testKeySet() {
 148         ConcurrentNavigableMap map = map5();
 149         Set s = map.keySet();
 150         assertEquals(5, s.size());
 151         assertTrue(s.contains(one));
 152         assertTrue(s.contains(two));
 153         assertTrue(s.contains(three));
 154         assertTrue(s.contains(four));
 155         assertTrue(s.contains(five));
 156     }
 157
 158     /**
 159      *   keySet is ordered
 160      */
 161     public void testKeySetOrder() {
 162         ConcurrentNavigableMap map = map5();
 163         Set s = map.keySet();
 164         Iterator i = s.iterator();
 165         Integer last = (Integer)i.next();
 166         assertEquals(last, one);
 167         while (i.hasNext()) {
 168             Integer k = (Integer)i.next();
 169             assertTrue(last.compareTo(k) < 0);
 170             last = k;
 171         }
 172     }
 173
 174     /**
 175      * values collection contains all values
 176      */
 177     public void testValues() {
 178         ConcurrentNavigableMap map = map5();
 179         Collection s = map.values();
 180         assertEquals(5, s.size());
 181         assertTrue(s.contains("A"));
 182         assertTrue(s.contains("B"));
 183         assertTrue(s.contains("C"));
 184         assertTrue(s.contains("D"));
 185         assertTrue(s.contains("E"));
 186     }
 187
 188     /**
 189      *  keySet.toArray returns contains all keys
 190      */
 191     public void testKeySetToArray() {
 192         ConcurrentNavigableMap map = map5();
 193         Set s = map.keySet();
 194         Object[] ar = s.toArray();
 195         assertTrue(s.containsAll(Arrays.asList(ar)));
 196         assertEquals(5, ar.length);
 197         ar[0] = m10;
 198         assertFalse(s.containsAll(Arrays.asList(ar)));
 199     }
 200
 201     /**
 202      *  descendingkeySet.toArray returns contains all keys
 203      */
 204     public void testDescendingKeySetToArray() {
 205         ConcurrentNavigableMap map = map5();
 206         Set s = map.descendingKeySet();
 207         Object[] ar = s.toArray();
 208         assertEquals(5, ar.length);
 209         assertTrue(s.containsAll(Arrays.asList(ar)));
 210         ar[0] = m10;
 211         assertFalse(s.containsAll(Arrays.asList(ar)));
 212     }
 213
 214     /**
 215      *  Values.toArray contains all values
 216      */
 217     public void testValuesToArray() {
 218         ConcurrentNavigableMap map = map5();
 219         Collection v = map.values();
 220         Object[] ar = v.toArray();
 221         ArrayList s = new ArrayList(Arrays.asList(ar));
 222         assertEquals(5, ar.length);
 223         assertTrue(s.contains("A"));
 224         assertTrue(s.contains("B"));
 225         assertTrue(s.contains("C"));
 226         assertTrue(s.contains("D"));
 227         assertTrue(s.contains("E"));
 228     }
 229
 230
 231     /**
 232      * entrySet contains all pairs
 233      */
 234     public void testEntrySet() {
 235         ConcurrentNavigableMap map = map5();
 236         Set s = map.entrySet();
 237         assertEquals(5, s.size());
 238         Iterator it = s.iterator();
 239         while (it.hasNext()) {
 240             Map.Entry e = (Map.Entry) it.next();
 241             assertTrue(
 242                        (e.getKey().equals(one) && e.getValue().equals("A")) ||
 243                        (e.getKey().equals(two) && e.getValue().equals("B")) ||
 244                        (e.getKey().equals(three) && e.getValue().equals("C")) ||
 245                        (e.getKey().equals(four) && e.getValue().equals("D")) ||
 246                        (e.getKey().equals(five) && e.getValue().equals("E")));
 247         }
 248     }
 249
 250     /**
 251      *   putAll  adds all key-value pairs from the given map
 252      */
 253     public void testPutAll() {
 254         ConcurrentNavigableMap empty = map0();
 255         ConcurrentNavigableMap map = map5();
 256         empty.putAll(map);
 257         assertEquals(5, empty.size());
 258         assertTrue(empty.containsKey(one));
 259         assertTrue(empty.containsKey(two));
 260         assertTrue(empty.containsKey(three));
 261         assertTrue(empty.containsKey(four));
 262         assertTrue(empty.containsKey(five));
 263     }
 264
 265     /**
 266      *   putIfAbsent works when the given key is not present
 267      */
 268     public void testPutIfAbsent() {
 269         ConcurrentNavigableMap map = map5();
 270         map.putIfAbsent(six, "Z");
 271         assertTrue(map.containsKey(six));
 272     }
 273
 274     /**
 275      *   putIfAbsent does not add the pair if the key is already present
 276      */
 277     public void testPutIfAbsent2() {
 278         ConcurrentNavigableMap map = map5();
 279         assertEquals("A", map.putIfAbsent(one, "Z"));
 280     }
 281
 282     /**
 283      *   replace fails when the given key is not present
 284      */
 285     public void testReplace() {
 286         ConcurrentNavigableMap map = map5();
 287         assertNull(map.replace(six, "Z"));
 288         assertFalse(map.containsKey(six));
 289     }
 290
 291     /**
 292      *   replace succeeds if the key is already present
 293      */
 294     public void testReplace2() {
 295         ConcurrentNavigableMap map = map5();
 296         assertNotNull(map.replace(one, "Z"));
 297         assertEquals("Z", map.get(one));
 298     }
 299
 300
 301     /**
 302      * replace value fails when the given key not mapped to expected value
 303      */
 304     public void testReplaceValue() {
 305         ConcurrentNavigableMap map = map5();
 306         assertEquals("A", map.get(one));
 307         assertFalse(map.replace(one, "Z", "Z"));
 308         assertEquals("A", map.get(one));
 309     }
 310
 311     /**
 312      * replace value succeeds when the given key mapped to expected value
 313      */
 314     public void testReplaceValue2() {
 315         ConcurrentNavigableMap map = map5();
 316         assertEquals("A", map.get(one));
 317         assertTrue(map.replace(one, "A", "Z"));
 318         assertEquals("Z", map.get(one));
 319     }
 320
 321
 322     /**
 323      *   remove removes the correct key-value pair from the map
 324      */
 325     public void testRemove() {
 326         ConcurrentNavigableMap map = map5();
 327         map.remove(five);
 328         assertEquals(4, map.size());
 329         assertFalse(map.containsKey(five));
 330     }
 331
 332     /**
 333      * remove(key,value) removes only if pair present
 334      */
 335     public void testRemove2() {
 336         ConcurrentNavigableMap map = map5();
 337         assertTrue(map.containsKey(five));
 338         assertEquals("E", map.get(five));
 339         map.remove(five, "E");
 340         assertEquals(4, map.size());
 341         assertFalse(map.containsKey(five));
 342         map.remove(four, "A");
 343         assertEquals(4, map.size());
 344         assertTrue(map.containsKey(four));
 345     }
 346
 347     /**
 348      * lowerEntry returns preceding entry.
 349      */
 350     public void testLowerEntry() {
 351         ConcurrentNavigableMap map = map5();
 352         Map.Entry e1 = map.lowerEntry(three);
 353         assertEquals(two, e1.getKey());
 354
 355         Map.Entry e2 = map.lowerEntry(six);
 356         assertEquals(five, e2.getKey());
 357
 358         Map.Entry e3 = map.lowerEntry(one);
 359         assertNull(e3);
 360
 361         Map.Entry e4 = map.lowerEntry(zero);
 362         assertNull(e4);
 363     }
 364
 365     /**
 366      * higherEntry returns next entry.
 367      */
 368     public void testHigherEntry() {
 369         ConcurrentNavigableMap map = map5();
 370         Map.Entry e1 = map.higherEntry(three);
 371         assertEquals(four, e1.getKey());
 372
 373         Map.Entry e2 = map.higherEntry(zero);
 374         assertEquals(one, e2.getKey());
 375
 376         Map.Entry e3 = map.higherEntry(five);
 377         assertNull(e3);
 378
 379         Map.Entry e4 = map.higherEntry(six);
 380         assertNull(e4);
 381     }
 382
 383     /**
 384      * floorEntry returns preceding entry.
 385      */
 386     public void testFloorEntry() {
 387         ConcurrentNavigableMap map = map5();
 388         Map.Entry e1 = map.floorEntry(three);
 389         assertEquals(three, e1.getKey());
 390
 391         Map.Entry e2 = map.floorEntry(six);
 392         assertEquals(five, e2.getKey());
 393
 394         Map.Entry e3 = map.floorEntry(one);
 395         assertEquals(one, e3.getKey());
 396
 397         Map.Entry e4 = map.floorEntry(zero);
 398         assertNull(e4);
 399     }
 400
 401     /**
 402      * ceilingEntry returns next entry.
 403      */
 404     public void testCeilingEntry() {
 405         ConcurrentNavigableMap map = map5();
 406         Map.Entry e1 = map.ceilingEntry(three);
 407         assertEquals(three, e1.getKey());
 408
 409         Map.Entry e2 = map.ceilingEntry(zero);
 410         assertEquals(one, e2.getKey());
 411
 412         Map.Entry e3 = map.ceilingEntry(five);
 413         assertEquals(five, e3.getKey());
 414
 415         Map.Entry e4 = map.ceilingEntry(six);
 416         assertNull(e4);
 417     }
 418
 419     /**
 420      * pollFirstEntry returns entries in order
 421      */
 422     public void testPollFirstEntry() {
 423         ConcurrentNavigableMap map = map5();
 424         Map.Entry e = map.pollFirstEntry();
 425         assertEquals(one, e.getKey());
 426         assertEquals("A", e.getValue());
 427         e = map.pollFirstEntry();
 428         assertEquals(two, e.getKey());
 429         map.put(one, "A");
 430         e = map.pollFirstEntry();
 431         assertEquals(one, e.getKey());
 432         assertEquals("A", e.getValue());
 433         e = map.pollFirstEntry();
 434         assertEquals(three, e.getKey());
 435         map.remove(four);
 436         e = map.pollFirstEntry();
 437         assertEquals(five, e.getKey());
 438         try {
 439             e.setValue("A");
 440             shouldThrow();
 441         } catch (UnsupportedOperationException success) {}
 442         e = map.pollFirstEntry();
 443         assertNull(e);
 444     }
 445
 446     /**
 447      * pollLastEntry returns entries in order
 448      */
 449     public void testPollLastEntry() {
 450         ConcurrentNavigableMap map = map5();
 451         Map.Entry e = map.pollLastEntry();
 452         assertEquals(five, e.getKey());
 453         assertEquals("E", e.getValue());
 454         e = map.pollLastEntry();
 455         assertEquals(four, e.getKey());
 456         map.put(five, "E");
 457         e = map.pollLastEntry();
 458         assertEquals(five, e.getKey());
 459         assertEquals("E", e.getValue());
 460         e = map.pollLastEntry();
 461         assertEquals(three, e.getKey());
 462         map.remove(two);
 463         e = map.pollLastEntry();
 464         assertEquals(one, e.getKey());
 465         try {
 466             e.setValue("E");
 467             shouldThrow();
 468         } catch (UnsupportedOperationException success) {}
 469         e = map.pollLastEntry();
 470         assertNull(e);
 471     }
 472
 473     /**
 474      *   size returns the correct values
 475      */
 476     public void testSize() {
 477         ConcurrentNavigableMap map = map5();
 478         ConcurrentNavigableMap empty = map0();
 479         assertEquals(0, empty.size());
 480         assertEquals(5, map.size());
 481     }
 482
 483     /**
 484      * toString contains toString of elements
 485      */
 486     public void testToString() {
 487         ConcurrentNavigableMap map = map5();
 488         String s = map.toString();
 489         for (int i = 1; i <= 5; ++i) {
 490             assertTrue(s.indexOf(String.valueOf(i)) >= 0);
 491         }
 492     }
 493
 494     // Exception tests
 495
 496     /**
 497      * get(null) of nonempty map throws NPE
 498      */
 499     public void testGet_NullPointerException() {
 500         try {
 501             ConcurrentNavigableMap c = map5();
 502             c.get(null);
 503             shouldThrow();
 504         } catch (NullPointerException success) {}
 505     }
 506
 507     /**
 508      * containsKey(null) of nonempty map throws NPE
 509      */
 510     public void testContainsKey_NullPointerException() {
 511         try {
 512             ConcurrentNavigableMap c = map5();
 513             c.containsKey(null);
 514             shouldThrow();
 515         } catch (NullPointerException success) {}
 516     }
 517
 518     /**
 519      * containsValue(null) throws NPE
 520      */
 521     public void testContainsValue_NullPointerException() {
 522         try {
 523             ConcurrentNavigableMap c = map0();
 524             c.containsValue(null);
 525             shouldThrow();
 526         } catch (NullPointerException success) {}
 527     }
 528
 529
 530     /**
 531      * put(null,x) throws NPE
 532      */
 533     public void testPut1_NullPointerException() {
 534         try {
 535             ConcurrentNavigableMap c = map5();
 536             c.put(null, "whatever");
 537             shouldThrow();
 538         } catch (NullPointerException success) {}
 539     }
 540
 541     /**
 542      * putIfAbsent(null, x) throws NPE
 543      */
 544     public void testPutIfAbsent1_NullPointerException() {
 545         try {
 546             ConcurrentNavigableMap c = map5();
 547             c.putIfAbsent(null, "whatever");
 548             shouldThrow();
 549         } catch (NullPointerException success) {}
 550     }
 551
 552     /**
 553      * replace(null, x) throws NPE
 554      */
 555     public void testReplace_NullPointerException() {
 556         try {
 557             ConcurrentNavigableMap c = map5();
 558             c.replace(null, "whatever");
 559             shouldThrow();
 560         } catch (NullPointerException success) {}
 561     }
 562
 563     /**
 564      * replace(null, x, y) throws NPE
 565      */
 566     public void testReplaceValue_NullPointerException() {
 567         try {
 568             ConcurrentNavigableMap c = map5();
 569             c.replace(null, one, "whatever");
 570             shouldThrow();
 571         } catch (NullPointerException success) {}
 572     }
 573
 574     /**
 575      * remove(null) throws NPE
 576      */
 577     public void testRemove1_NullPointerException() {
 578         try {
 579             ConcurrentNavigableMap c = map5();
 580             c.remove(null);
 581             shouldThrow();
 582         } catch (NullPointerException success) {}
 583     }
 584
 585     /**
 586      * remove(null, x) throws NPE
 587      */
 588     public void testRemove2_NullPointerException() {
 589         try {
 590             ConcurrentNavigableMap c = map5();
 591             c.remove(null, "whatever");
 592             shouldThrow();
 593         } catch (NullPointerException success) {}
 594     }
 595
 596     /**
 597      * A deserialized map equals original
 598      */
 599     public void testSerialization() throws Exception {
 600         ConcurrentNavigableMap q = map5();
 601
 602         ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
 603         ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
 604         out.writeObject(q);
 605         out.close();
 606
 607         ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
 608         ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
 609         ConcurrentNavigableMap r = (ConcurrentNavigableMap)in.readObject();
 610         assertEquals(q.size(), r.size());
 611         assertTrue(q.equals(r));
 612         assertTrue(r.equals(q));
 613     }
 614
 615
 616
 617     /**
 618      * subMap returns map with keys in requested range
 619      */
 620     public void testSubMapContents() {
 621         ConcurrentNavigableMap map = map5();
 622         SortedMap sm = map.subMap(two, four);
 623         assertEquals(two, sm.firstKey());
 624         assertEquals(three, sm.lastKey());
 625         assertEquals(2, sm.size());
 626         assertFalse(sm.containsKey(one));
 627         assertTrue(sm.containsKey(two));
 628         assertTrue(sm.containsKey(three));
 629         assertFalse(sm.containsKey(four));
 630         assertFalse(sm.containsKey(five));
 631         Iterator i = sm.keySet().iterator();
 632         Object k;
 633         k = (Integer)(i.next());
 634         assertEquals(two, k);
 635         k = (Integer)(i.next());
 636         assertEquals(three, k);
 637         assertFalse(i.hasNext());
 638         Iterator j = sm.keySet().iterator();
 639         j.next();
 640         j.remove();
 641         assertFalse(map.containsKey(two));
 642         assertEquals(4, map.size());
 643         assertEquals(1, sm.size());
 644         assertEquals(three, sm.firstKey());
 645         assertEquals(three, sm.lastKey());
 646         assertEquals("C", sm.remove(three));
 647         assertTrue(sm.isEmpty());
 648         assertEquals(3, map.size());
 649     }
 650
 651     public void testSubMapContents2() {
 652         ConcurrentNavigableMap map = map5();
 653         SortedMap sm = map.subMap(two, three);
 654         assertEquals(1, sm.size());
 655         assertEquals(two, sm.firstKey());
 656         assertEquals(two, sm.lastKey());
 657         assertFalse(sm.containsKey(one));
 658         assertTrue(sm.containsKey(two));
 659         assertFalse(sm.containsKey(three));
 660         assertFalse(sm.containsKey(four));
 661         assertFalse(sm.containsKey(five));
 662         Iterator i = sm.keySet().iterator();
 663         Object k;
 664         k = (Integer)(i.next());
 665         assertEquals(two, k);
 666         assertFalse(i.hasNext());
 667         Iterator j = sm.keySet().iterator();
 668         j.next();
 669         j.remove();
 670         assertFalse(map.containsKey(two));
 671         assertEquals(4, map.size());
 672         assertEquals(0, sm.size());
 673         assertTrue(sm.isEmpty());
 674         assertSame(sm.remove(three), null);
 675         assertEquals(4, map.size());
 676     }
 677
 678     /**
 679      * headMap returns map with keys in requested range
 680      */
 681     public void testHeadMapContents() {
 682         ConcurrentNavigableMap map = map5();
 683         SortedMap sm = map.headMap(four);
 684         assertTrue(sm.containsKey(one));
 685         assertTrue(sm.containsKey(two));
 686         assertTrue(sm.containsKey(three));
 687         assertFalse(sm.containsKey(four));
 688         assertFalse(sm.containsKey(five));
 689         Iterator i = sm.keySet().iterator();
 690         Object k;
 691         k = (Integer)(i.next());
 692         assertEquals(one, k);
 693         k = (Integer)(i.next());
 694         assertEquals(two, k);
 695         k = (Integer)(i.next());
 696         assertEquals(three, k);
 697         assertFalse(i.hasNext());
 698         sm.clear();
 699         assertTrue(sm.isEmpty());
 700         assertEquals(2, map.size());
 701         assertEquals(four, map.firstKey());
 702     }
 703
 704     /**
 705      * headMap returns map with keys in requested range
 706      */
 707     public void testTailMapContents() {
 708         ConcurrentNavigableMap map = map5();
 709         SortedMap sm = map.tailMap(two);
 710         assertFalse(sm.containsKey(one));
 711         assertTrue(sm.containsKey(two));
 712         assertTrue(sm.containsKey(three));
 713         assertTrue(sm.containsKey(four));
 714         assertTrue(sm.containsKey(five));
 715         Iterator i = sm.keySet().iterator();
 716         Object k;
 717         k = (Integer)(i.next());
 718         assertEquals(two, k);
 719         k = (Integer)(i.next());
 720         assertEquals(three, k);
 721         k = (Integer)(i.next());
 722         assertEquals(four, k);
 723         k = (Integer)(i.next());
 724         assertEquals(five, k);
 725         assertFalse(i.hasNext());
 726
 727         Iterator ei = sm.entrySet().iterator();
 728         Map.Entry e;
 729         e = (Map.Entry)(ei.next());
 730         assertEquals(two, e.getKey());
 731         assertEquals("B", e.getValue());
 732         e = (Map.Entry)(ei.next());
 733         assertEquals(three, e.getKey());
 734         assertEquals("C", e.getValue());
 735         e = (Map.Entry)(ei.next());
 736         assertEquals(four, e.getKey());
 737         assertEquals("D", e.getValue());
 738         e = (Map.Entry)(ei.next());
 739         assertEquals(five, e.getKey());
 740         assertEquals("E", e.getValue());
 741         assertFalse(i.hasNext());
 742
 743         SortedMap ssm = sm.tailMap(four);
 744         assertEquals(four, ssm.firstKey());
 745         assertEquals(five, ssm.lastKey());
 746         assertEquals("D", ssm.remove(four));
 747         assertEquals(1, ssm.size());
 748         assertEquals(3, sm.size());
 749         assertEquals(4, map.size());
 750     }
 751
 752     /**
 753      *  clear removes all pairs
 754      */
 755     public void testDescendingClear() {
 756         ConcurrentNavigableMap map = dmap5();
 757         map.clear();
 758         assertEquals(map.size(), 0);
 759     }
 760
 761
 762     /**
 763      *  Maps with same contents are equal
 764      */
 765     public void testDescendingEquals() {
 766         ConcurrentNavigableMap map1 = dmap5();
 767         ConcurrentNavigableMap map2 = dmap5();
 768         assertEquals(map1, map2);
 769         assertEquals(map2, map1);
 770         map1.clear();
 771         assertFalse(map1.equals(map2));
 772         assertFalse(map2.equals(map1));
 773     }
 774
 775     /**
 776      *  containsKey returns true for contained key
 777      */
 778     public void testDescendingContainsKey() {
 779         ConcurrentNavigableMap map = dmap5();
 780         assertTrue(map.containsKey(m1));
 781         assertFalse(map.containsKey(zero));
 782     }
 783
 784     /**
 785      *  containsValue returns true for held values
 786      */
 787     public void testDescendingContainsValue() {
 788         ConcurrentNavigableMap map = dmap5();
 789         assertTrue(map.containsValue("A"));
 790         assertFalse(map.containsValue("Z"));
 791     }
 792
 793     /**
 794      *  get returns the correct element at the given key,
 795      *  or null if not present
 796      */
 797     public void testDescendingGet() {
 798         ConcurrentNavigableMap map = dmap5();
 799         assertEquals("A", (String)map.get(m1));
 800         ConcurrentNavigableMap empty = dmap0();
 801         assertNull(empty.get(m1));
 802     }
 803
 804     /**
 805      *  isEmpty is true of empty map and false for non-empty
 806      */
 807     public void testDescendingIsEmpty() {
 808         ConcurrentNavigableMap empty = dmap0();
 809         ConcurrentNavigableMap map = dmap5();
 810         assertTrue(empty.isEmpty());
 811         assertFalse(map.isEmpty());
 812     }
 813
 814     /**
 815      *   firstKey returns first key
 816      */
 817     public void testDescendingFirstKey() {
 818         ConcurrentNavigableMap map = dmap5();
 819         assertEquals(m1, map.firstKey());
 820     }
 821
 822     /**
 823      *   lastKey returns last key
 824      */
 825     public void testDescendingLastKey() {
 826         ConcurrentNavigableMap map = dmap5();
 827         assertEquals(m5, map.lastKey());
 828     }
 829
 830
 831     /**
 832      *   keySet returns a Set containing all the keys
 833      */
 834     public void testDescendingKeySet() {
 835         ConcurrentNavigableMap map = dmap5();
 836         Set s = map.keySet();
 837         assertEquals(5, s.size());
 838         assertTrue(s.contains(m1));
 839         assertTrue(s.contains(m2));
 840         assertTrue(s.contains(m3));
 841         assertTrue(s.contains(m4));
 842         assertTrue(s.contains(m5));
 843     }
 844
 845     /**
 846      *   keySet is ordered
 847      */
 848     public void testDescendingKeySetOrder() {
 849         ConcurrentNavigableMap map = dmap5();
 850         Set s = map.keySet();
 851         Iterator i = s.iterator();
 852         Integer last = (Integer)i.next();
 853         assertEquals(last, m1);
 854         while (i.hasNext()) {
 855             Integer k = (Integer)i.next();
 856             assertTrue(last.compareTo(k) > 0);
 857             last = k;
 858         }
 859     }
 860
 861     /**
 862      * values collection contains all values
 863      */
 864     public void testDescendingValues() {
 865         ConcurrentNavigableMap map = dmap5();
 866         Collection s = map.values();
 867         assertEquals(5, s.size());
 868         assertTrue(s.contains("A"));
 869         assertTrue(s.contains("B"));
 870         assertTrue(s.contains("C"));
 871         assertTrue(s.contains("D"));
 872         assertTrue(s.contains("E"));
 873     }
 874
 875     /**
 876      *  keySet.toArray returns contains all keys
 877      */
 878     public void testDescendingAscendingKeySetToArray() {
 879         ConcurrentNavigableMap map = dmap5();
 880         Set s = map.keySet();
 881         Object[] ar = s.toArray();
 882         assertTrue(s.containsAll(Arrays.asList(ar)));
 883         assertEquals(5, ar.length);
 884         ar[0] = m10;
 885         assertFalse(s.containsAll(Arrays.asList(ar)));
 886     }
 887
 888     /**
 889      *  descendingkeySet.toArray returns contains all keys
 890      */
 891     public void testDescendingDescendingKeySetToArray() {
 892         ConcurrentNavigableMap map = dmap5();
 893         Set s = map.descendingKeySet();
 894         Object[] ar = s.toArray();
 895         assertEquals(5, ar.length);
 896         assertTrue(s.containsAll(Arrays.asList(ar)));
 897         ar[0] = m10;
 898         assertFalse(s.containsAll(Arrays.asList(ar)));
 899     }
 900
 901     /**
 902      *  Values.toArray contains all values
 903      */
 904     public void testDescendingValuesToArray() {
 905         ConcurrentNavigableMap map = dmap5();
 906         Collection v = map.values();
 907         Object[] ar = v.toArray();
 908         ArrayList s = new ArrayList(Arrays.asList(ar));
 909         assertEquals(5, ar.length);
 910         assertTrue(s.contains("A"));
 911         assertTrue(s.contains("B"));
 912         assertTrue(s.contains("C"));
 913         assertTrue(s.contains("D"));
 914         assertTrue(s.contains("E"));
 915     }
 916
 917
 918     /**
 919      * entrySet contains all pairs
 920      */
 921     public void testDescendingEntrySet() {
 922         ConcurrentNavigableMap map = dmap5();
 923         Set s = map.entrySet();
 924         assertEquals(5, s.size());
 925         Iterator it = s.iterator();
 926         while (it.hasNext()) {
 927             Map.Entry e = (Map.Entry) it.next();
 928             assertTrue(
 929                        (e.getKey().equals(m1) && e.getValue().equals("A")) ||
 930                        (e.getKey().equals(m2) && e.getValue().equals("B")) ||
 931                        (e.getKey().equals(m3) && e.getValue().equals("C")) ||
 932                        (e.getKey().equals(m4) && e.getValue().equals("D")) ||
 933                        (e.getKey().equals(m5) && e.getValue().equals("E")));
 934         }
 935     }
 936
 937     /**
 938      *   putAll  adds all key-value pairs from the given map
 939      */
 940     public void testDescendingPutAll() {
 941         ConcurrentNavigableMap empty = dmap0();
 942         ConcurrentNavigableMap map = dmap5();
 943         empty.putAll(map);
 944         assertEquals(5, empty.size());
 945         assertTrue(empty.containsKey(m1));
 946         assertTrue(empty.containsKey(m2));
 947         assertTrue(empty.containsKey(m3));
 948         assertTrue(empty.containsKey(m4));
 949         assertTrue(empty.containsKey(m5));
 950     }
 951
 952     /**
 953      *   putIfAbsent works when the given key is not present
 954      */
 955     public void testDescendingPutIfAbsent() {
 956         ConcurrentNavigableMap map = dmap5();
 957         map.putIfAbsent(six, "Z");
 958         assertTrue(map.containsKey(six));
 959     }
 960
 961     /**
 962      *   putIfAbsent does not add the pair if the key is already present
 963      */
 964     public void testDescendingPutIfAbsent2() {
 965         ConcurrentNavigableMap map = dmap5();
 966         assertEquals("A", map.putIfAbsent(m1, "Z"));
 967     }
 968
 969     /**
 970      *   replace fails when the given key is not present
 971      */
 972     public void testDescendingReplace() {
 973         ConcurrentNavigableMap map = dmap5();
 974         assertNull(map.replace(six, "Z"));
 975         assertFalse(map.containsKey(six));
 976     }
 977
 978     /**
 979      *   replace succeeds if the key is already present
 980      */
 981     public void testDescendingReplace2() {
 982         ConcurrentNavigableMap map = dmap5();
 983         assertNotNull(map.replace(m1, "Z"));
 984         assertEquals("Z", map.get(m1));
 985     }
 986
 987
 988     /**
 989      * replace value fails when the given key not mapped to expected value
 990      */
 991     public void testDescendingReplaceValue() {
 992         ConcurrentNavigableMap map = dmap5();
 993         assertEquals("A", map.get(m1));
 994         assertFalse(map.replace(m1, "Z", "Z"));
 995         assertEquals("A", map.get(m1));
 996     }
 997
 998     /**
 999      * replace value succeeds when the given key mapped to expected value
1000      */
1001     public void testDescendingReplaceValue2() {
1002         ConcurrentNavigableMap map = dmap5();
1003         assertEquals("A", map.get(m1));
1004         assertTrue(map.replace(m1, "A", "Z"));
1005         assertEquals("Z", map.get(m1));
1006     }
1007
1008
1009     /**
1010      *   remove removes the correct key-value pair from the map
1011      */
1012     public void testDescendingRemove() {
1013         ConcurrentNavigableMap map = dmap5();
1014         map.remove(m5);
1015         assertEquals(4, map.size());
1016         assertFalse(map.containsKey(m5));
1017     }
1018
1019     /**
1020      * remove(key,value) removes only if pair present
1021      */
1022     public void testDescendingRemove2() {
1023         ConcurrentNavigableMap map = dmap5();
1024         assertTrue(map.containsKey(m5));
1025         assertEquals("E", map.get(m5));
1026         map.remove(m5, "E");
1027         assertEquals(4, map.size());
1028         assertFalse(map.containsKey(m5));
1029         map.remove(m4, "A");
1030         assertEquals(4, map.size());
1031         assertTrue(map.containsKey(m4));
1032     }
1033
1034     /**
1035      * lowerEntry returns preceding entry.
1036      */
1037     public void testDescendingLowerEntry() {
1038         ConcurrentNavigableMap map = dmap5();
1039         Map.Entry e1 = map.lowerEntry(m3);
1040         assertEquals(m2, e1.getKey());
1041
1042         Map.Entry e2 = map.lowerEntry(m6);
1043         assertEquals(m5, e2.getKey());
1044
1045         Map.Entry e3 = map.lowerEntry(m1);
1046         assertNull(e3);
1047
1048         Map.Entry e4 = map.lowerEntry(zero);
1049         assertNull(e4);
1050     }
1051
1052     /**
1053      * higherEntry returns next entry.
1054      */
1055     public void testDescendingHigherEntry() {
1056         ConcurrentNavigableMap map = dmap5();
1057         Map.Entry e1 = map.higherEntry(m3);
1058         assertEquals(m4, e1.getKey());
1059
1060         Map.Entry e2 = map.higherEntry(zero);
1061         assertEquals(m1, e2.getKey());
1062
1063         Map.Entry e3 = map.higherEntry(m5);
1064         assertNull(e3);
1065
1066         Map.Entry e4 = map.higherEntry(m6);
1067         assertNull(e4);
1068     }
1069
1070     /**
1071      * floorEntry returns preceding entry.
1072      */
1073     public void testDescendingFloorEntry() {
1074         ConcurrentNavigableMap map = dmap5();
1075         Map.Entry e1 = map.floorEntry(m3);
1076         assertEquals(m3, e1.getKey());
1077
1078         Map.Entry e2 = map.floorEntry(m6);
1079         assertEquals(m5, e2.getKey());
1080
1081         Map.Entry e3 = map.floorEntry(m1);
1082         assertEquals(m1, e3.getKey());
1083
1084         Map.Entry e4 = map.floorEntry(zero);
1085         assertNull(e4);
1086     }
1087
1088     /**
1089      * ceilingEntry returns next entry.
1090      */
1091     public void testDescendingCeilingEntry() {
1092         ConcurrentNavigableMap map = dmap5();
1093         Map.Entry e1 = map.ceilingEntry(m3);
1094         assertEquals(m3, e1.getKey());
1095
1096         Map.Entry e2 = map.ceilingEntry(zero);
1097         assertEquals(m1, e2.getKey());
1098
1099         Map.Entry e3 = map.ceilingEntry(m5);
1100         assertEquals(m5, e3.getKey());
1101
1102         Map.Entry e4 = map.ceilingEntry(m6);
1103         assertNull(e4);
1104     }
1105
1106     /**
1107      * pollFirstEntry returns entries in order
1108      */
1109     public void testDescendingPollFirstEntry() {
1110         ConcurrentNavigableMap map = dmap5();
1111         Map.Entry e = map.pollFirstEntry();
1112         assertEquals(m1, e.getKey());
1113         assertEquals("A", e.getValue());
1114         e = map.pollFirstEntry();
1115         assertEquals(m2, e.getKey());
1116         map.put(m1, "A");
1117         e = map.pollFirstEntry();
1118         assertEquals(m1, e.getKey());
1119         assertEquals("A", e.getValue());
1120         e = map.pollFirstEntry();
1121         assertEquals(m3, e.getKey());
1122         map.remove(m4);
1123         e = map.pollFirstEntry();
1124         assertEquals(m5, e.getKey());
1125         try {
1126             e.setValue("A");
1127             shouldThrow();
1128         } catch (UnsupportedOperationException success) {}
1129         e = map.pollFirstEntry();
1130         assertNull(e);
1131     }
1132
1133     /**
1134      * pollLastEntry returns entries in order
1135      */
1136     public void testDescendingPollLastEntry() {
1137         ConcurrentNavigableMap map = dmap5();
1138         Map.Entry e = map.pollLastEntry();
1139         assertEquals(m5, e.getKey());
1140         assertEquals("E", e.getValue());
1141         e = map.pollLastEntry();
1142         assertEquals(m4, e.getKey());
1143         map.put(m5, "E");
1144         e = map.pollLastEntry();
1145         assertEquals(m5, e.getKey());
1146         assertEquals("E", e.getValue());
1147         e = map.pollLastEntry();
1148         assertEquals(m3, e.getKey());
1149         map.remove(m2);
1150         e = map.pollLastEntry();
1151         assertEquals(m1, e.getKey());
1152         try {
1153             e.setValue("E");
1154             shouldThrow();
1155         } catch (UnsupportedOperationException success) {}
1156         e = map.pollLastEntry();
1157         assertNull(e);
1158     }
1159
1160     /**
1161      *   size returns the correct values
1162      */
1163     public void testDescendingSize() {
1164         ConcurrentNavigableMap map = dmap5();
1165         ConcurrentNavigableMap empty = dmap0();
1166         assertEquals(0, empty.size());
1167         assertEquals(5, map.size());
1168     }
1169
1170     /**
1171      * toString contains toString of elements
1172      */
1173     public void testDescendingToString() {
1174         ConcurrentNavigableMap map = dmap5();
1175         String s = map.toString();
1176         for (int i = 1; i <= 5; ++i) {
1177             assertTrue(s.indexOf(String.valueOf(i)) >= 0);
1178         }
1179     }
1180
1181     // Exception testDescendings
1182
1183     /**
1184      * get(null) of empty map throws NPE
1185      */
1186     public void testDescendingGet_NullPointerException() {
1187         try {
1188             ConcurrentNavigableMap c = dmap5();
1189             c.get(null);
1190             shouldThrow();
1191         } catch (NullPointerException success) {}
1192     }
1193
1194     /**
1195      * containsKey(null) of empty map throws NPE
1196      */
1197     public void testDescendingContainsKey_NullPointerException() {
1198         try {
1199             ConcurrentNavigableMap c = dmap5();
1200             c.containsKey(null);
1201             shouldThrow();
1202         } catch (NullPointerException success) {}
1203     }
1204
1205     /**
1206      * containsValue(null) throws NPE
1207      */
1208     public void testDescendingContainsValue_NullPointerException() {
1209         try {
1210             ConcurrentNavigableMap c = dmap0();
1211             c.containsValue(null);
1212             shouldThrow();
1213         } catch (NullPointerException success) {}
1214     }
1215
1216
1217     /**
1218      * put(null,x) throws NPE
1219      */
1220     public void testDescendingPut1_NullPointerException() {
1221         try {
1222             ConcurrentNavigableMap c = dmap5();
1223             c.put(null, "whatever");
1224             shouldThrow();
1225         } catch (NullPointerException success) {}
1226     }
1227
1228     /**
1229      * putIfAbsent(null, x) throws NPE
1230      */
1231     public void testDescendingPutIfAbsent1_NullPointerException() {
1232         try {
1233             ConcurrentNavigableMap c = dmap5();
1234             c.putIfAbsent(null, "whatever");
1235             shouldThrow();
1236         } catch (NullPointerException success) {}
1237     }
1238
1239     /**
1240      * replace(null, x) throws NPE
1241      */
1242     public void testDescendingReplace_NullPointerException() {
1243         try {
1244             ConcurrentNavigableMap c = dmap5();
1245             c.replace(null, "whatever");
1246             shouldThrow();
1247         } catch (NullPointerException success) {}
1248     }
1249
1250     /**
1251      * replace(null, x, y) throws NPE
1252      */
1253     public void testDescendingReplaceValue_NullPointerException() {
1254         try {
1255             ConcurrentNavigableMap c = dmap5();
1256             c.replace(null, m1, "whatever");
1257             shouldThrow();
1258         } catch (NullPointerException success) {}
1259     }
1260
1261     /**
1262      * remove(null) throws NPE
1263      */
1264     public void testDescendingRemove1_NullPointerException() {
1265         try {
1266             ConcurrentNavigableMap c = dmap5();
1267             c.remove(null);
1268             shouldThrow();
1269         } catch (NullPointerException success) {}
1270     }
1271
1272     /**
1273      * remove(null, x) throws NPE
1274      */
1275     public void testDescendingRemove2_NullPointerException() {
1276         try {
1277             ConcurrentNavigableMap c = dmap5();
1278             c.remove(null, "whatever");
1279             shouldThrow();
1280         } catch (NullPointerException success) {}
1281     }
1282
1283     /**
1284      * A deserialized map equals original
1285      */
1286     public void testDescendingSerialization() throws Exception {
1287         ConcurrentNavigableMap q = dmap5();
1288
1289         ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
1290         ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
1291         out.writeObject(q);
1292         out.close();
1293
1294         ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
1295         ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
1296         ConcurrentNavigableMap r = (ConcurrentNavigableMap)in.readObject();
1297         assertEquals(q.size(), r.size());
1298         assertTrue(q.equals(r));
1299         assertTrue(r.equals(q));
1300     }
1301
1302
1303     /**
1304      * subMap returns map with keys in requested range
1305      */
1306     public void testDescendingSubMapContents() {
1307         ConcurrentNavigableMap map = dmap5();
1308         SortedMap sm = map.subMap(m2, m4);
1309         assertEquals(m2, sm.firstKey());
1310         assertEquals(m3, sm.lastKey());
1311         assertEquals(2, sm.size());
1312         assertFalse(sm.containsKey(m1));
1313         assertTrue(sm.containsKey(m2));
1314         assertTrue(sm.containsKey(m3));
1315         assertFalse(sm.containsKey(m4));
1316         assertFalse(sm.containsKey(m5));
1317         Iterator i = sm.keySet().iterator();
1318         Object k;
1319         k = (Integer)(i.next());
1320         assertEquals(m2, k);
1321         k = (Integer)(i.next());
1322         assertEquals(m3, k);
1323         assertFalse(i.hasNext());
1324         Iterator j = sm.keySet().iterator();
1325         j.next();
1326         j.remove();
1327         assertFalse(map.containsKey(m2));
1328         assertEquals(4, map.size());
1329         assertEquals(1, sm.size());
1330         assertEquals(m3, sm.firstKey());
1331         assertEquals(m3, sm.lastKey());
1332         assertEquals("C", sm.remove(m3));
1333         assertTrue(sm.isEmpty());
1334         assertEquals(3, map.size());
1335     }
1336
1337     public void testDescendingSubMapContents2() {
1338         ConcurrentNavigableMap map = dmap5();
1339         SortedMap sm = map.subMap(m2, m3);
1340         assertEquals(1, sm.size());
1341         assertEquals(m2, sm.firstKey());
1342         assertEquals(m2, sm.lastKey());
1343         assertFalse(sm.containsKey(m1));
1344         assertTrue(sm.containsKey(m2));
1345         assertFalse(sm.containsKey(m3));
1346         assertFalse(sm.containsKey(m4));
1347         assertFalse(sm.containsKey(m5));
1348         Iterator i = sm.keySet().iterator();
1349         Object k;
1350         k = (Integer)(i.next());
1351         assertEquals(m2, k);
1352         assertFalse(i.hasNext());
1353         Iterator j = sm.keySet().iterator();
1354         j.next();
1355         j.remove();
1356         assertFalse(map.containsKey(m2));
1357         assertEquals(4, map.size());
1358         assertEquals(0, sm.size());
1359         assertTrue(sm.isEmpty());
1360         assertSame(sm.remove(m3), null);
1361         assertEquals(4, map.size());
1362     }
1363
1364     /**
1365      * headMap returns map with keys in requested range
1366      */
1367     public void testDescendingHeadMapContents() {
1368         ConcurrentNavigableMap map = dmap5();
1369         SortedMap sm = map.headMap(m4);
1370         assertTrue(sm.containsKey(m1));
1371         assertTrue(sm.containsKey(m2));
1372         assertTrue(sm.containsKey(m3));
1373         assertFalse(sm.containsKey(m4));
1374         assertFalse(sm.containsKey(m5));
1375         Iterator i = sm.keySet().iterator();
1376         Object k;
1377         k = (Integer)(i.next());
1378         assertEquals(m1, k);
1379         k = (Integer)(i.next());
1380         assertEquals(m2, k);
1381         k = (Integer)(i.next());
1382         assertEquals(m3, k);
1383         assertFalse(i.hasNext());
1384         sm.clear();
1385         assertTrue(sm.isEmpty());
1386         assertEquals(2, map.size());
1387         assertEquals(m4, map.firstKey());
1388     }
1389
1390     /**
1391      * headMap returns map with keys in requested range
1392      */
1393     public void testDescendingTailMapContents() {
1394         ConcurrentNavigableMap map = dmap5();
1395         SortedMap sm = map.tailMap(m2);
1396         assertFalse(sm.containsKey(m1));
1397         assertTrue(sm.containsKey(m2));
1398         assertTrue(sm.containsKey(m3));
1399         assertTrue(sm.containsKey(m4));
1400         assertTrue(sm.containsKey(m5));
1401         Iterator i = sm.keySet().iterator();
1402         Object k;
1403         k = (Integer)(i.next());
1404         assertEquals(m2, k);
1405         k = (Integer)(i.next());
1406         assertEquals(m3, k);
1407         k = (Integer)(i.next());
1408         assertEquals(m4, k);
1409         k = (Integer)(i.next());
1410         assertEquals(m5, k);
1411         assertFalse(i.hasNext());
1412
1413         Iterator ei = sm.entrySet().iterator();
1414         Map.Entry e;
1415         e = (Map.Entry)(ei.next());
1416         assertEquals(m2, e.getKey());
1417         assertEquals("B", e.getValue());
1418         e = (Map.Entry)(ei.next());
1419         assertEquals(m3, e.getKey());
1420         assertEquals("C", e.getValue());
1421         e = (Map.Entry)(ei.next());
1422         assertEquals(m4, e.getKey());
1423         assertEquals("D", e.getValue());
1424         e = (Map.Entry)(ei.next());
1425         assertEquals(m5, e.getKey());
1426         assertEquals("E", e.getValue());
1427         assertFalse(i.hasNext());
1428
1429         SortedMap ssm = sm.tailMap(m4);
1430         assertEquals(m4, ssm.firstKey());
1431         assertEquals(m5, ssm.lastKey());
1432         assertEquals("D", ssm.remove(m4));
1433         assertEquals(1, ssm.size());
1434         assertEquals(3, sm.size());
1435         assertEquals(4, map.size());
1436     }
1437
1438 }