test/jalview/datamodel/features/NCListTest.java

   1 package jalview.datamodel.features;
   2 import static org.testng.Assert.assertEquals;
   3 import static org.testng.Assert.assertFalse;
   4 import static org.testng.Assert.assertSame;
   5 import static org.testng.Assert.assertTrue;
   6
   7 import jalview.datamodel.SequenceFeature;
   8
   9 import java.util.ArrayList;
  10 import java.util.Collections;
  11 import java.util.Comparator;
  12 import java.util.List;
  13 import java.util.Random;
  14
  15 import junit.extensions.PA;
  16
  17 import org.testng.annotations.DataProvider;
  18 import org.testng.annotations.Test;
  19
  20 public class NCListTest
  21 {
  22
  23   private Random random = new Random(107);
  24
  25   private Comparator<ContiguousI> sorter = new RangeComparator(true);
  26
  27   /**
  28    * A basic sanity test of the constructor
  29    */
  30   @Test(groups = "Functional")
  31   public void testConstructor()
  32   {
  33     List<Range> ranges = new ArrayList<Range>();
  34     ranges.add(new Range(20, 20));
  35     ranges.add(new Range(10, 20));
  36     ranges.add(new Range(15, 30));
  37     ranges.add(new Range(10, 30));
  38     ranges.add(new Range(11, 19));
  39     ranges.add(new Range(10, 20));
  40     ranges.add(new Range(1, 100));
  41
  42     NCList<Range> ncl = new NCList<Range>(ranges);
  43     String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
  44     assertEquals(ncl.toString(), expected);
  45     assertTrue(ncl.isValid());
  46
  47     Collections.reverse(ranges);
  48     ncl = new NCList<Range>(ranges);
  49     assertEquals(ncl.toString(), expected);
  50     assertTrue(ncl.isValid());
  51   }
  52
  53   @Test(groups = "Functional")
  54   public void testFindOverlaps()
  55   {
  56     List<Range> ranges = new ArrayList<Range>();
  57     ranges.add(new Range(20, 50));
  58     ranges.add(new Range(30, 70));
  59     ranges.add(new Range(1, 100));
  60     ranges.add(new Range(70, 120));
  61
  62     NCList<Range> ncl = new NCList<Range>(ranges);
  63
  64     List<Range> overlaps = ncl.findOverlaps(121, 122);
  65     assertEquals(overlaps.size(), 0);
  66
  67     overlaps = ncl.findOverlaps(21, 22);
  68     assertEquals(overlaps.size(), 2);
  69     assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
  70     assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
  71     assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
  72     assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
  73
  74     overlaps = ncl.findOverlaps(110, 110);
  75     assertEquals(overlaps.size(), 1);
  76     assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
  77     assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
  78   }
  79
  80   @Test(groups = "Functional")
  81   public void testAdd_onTheEnd()
  82   {
  83     List<Range> ranges = new ArrayList<Range>();
  84     ranges.add(new Range(20, 50));
  85     NCList<Range> ncl = new NCList<Range>(ranges);
  86     assertEquals(ncl.toString(), "[20-50]");
  87     assertTrue(ncl.isValid());
  88
  89     ncl.add(new Range(60, 70));
  90     assertEquals(ncl.toString(), "[20-50, 60-70]");
  91     assertTrue(ncl.isValid());
  92   }
  93
  94   @Test(groups = "Functional")
  95   public void testAdd_inside()
  96   {
  97     List<Range> ranges = new ArrayList<Range>();
  98     ranges.add(new Range(20, 50));
  99     NCList<Range> ncl = new NCList<Range>(ranges);
 100     assertEquals(ncl.toString(), "[20-50]");
 101     assertTrue(ncl.isValid());
 102
 103     ncl.add(new Range(30, 40));
 104     assertEquals(ncl.toString(), "[20-50 [30-40]]");
 105   }
 106
 107   @Test(groups = "Functional")
 108   public void testAdd_onTheFront()
 109   {
 110     List<Range> ranges = new ArrayList<Range>();
 111     ranges.add(new Range(20, 50));
 112     NCList<Range> ncl = new NCList<Range>(ranges);
 113     assertEquals(ncl.toString(), "[20-50]");
 114     assertTrue(ncl.isValid());
 115
 116     ncl.add(new Range(5, 15));
 117     assertEquals(ncl.toString(), "[5-15, 20-50]");
 118     assertTrue(ncl.isValid());
 119   }
 120
 121   @Test(groups = "Functional")
 122   public void testAdd_enclosing()
 123   {
 124     List<Range> ranges = new ArrayList<Range>();
 125     ranges.add(new Range(20, 50));
 126     ranges.add(new Range(30, 60));
 127     NCList<Range> ncl = new NCList<Range>(ranges);
 128     assertEquals(ncl.toString(), "[20-50, 30-60]");
 129     assertTrue(ncl.isValid());
 130     assertEquals(ncl.getStart(), 20);
 131
 132     ncl.add(new Range(10, 70));
 133     assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
 134     assertTrue(ncl.isValid());
 135   }
 136
 137   @Test(groups = "Functional")
 138   public void testAdd_spanning()
 139   {
 140     List<Range> ranges = new ArrayList<Range>();
 141     ranges.add(new Range(20, 40));
 142     ranges.add(new Range(60, 70));
 143     NCList<Range> ncl = new NCList<Range>(ranges);
 144     assertEquals(ncl.toString(), "[20-40, 60-70]");
 145     assertTrue(ncl.isValid());
 146
 147     ncl.add(new Range(30, 50));
 148     assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
 149     assertTrue(ncl.isValid());
 150
 151     ncl.add(new Range(40, 65));
 152     assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
 153     assertTrue(ncl.isValid());
 154   }
 155
 156   /**
 157    * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
 158    * [0-scale] interval to be stored
 159    *
 160    * @return
 161    */
 162   @DataProvider(name = "scalesOfLife")
 163   public Object[][] getScales()
 164   {
 165     return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
 166   }
 167
 168   /**
 169    * Do a number of pseudo-random (reproducible) builds of an NCList, to
 170    * exercise as many methods of the class as possible while generating the
 171    * range of possible structure topologies
 172    * <ul>
 173    * <li>verify that add adds an entry and increments size</li>
 174    * <li>...except where the entry is already contained (by equals test)</li>
 175    * <li>verify that the structure is valid at all stages of construction</li>
 176    * <li>generate, run and verify a range of overlap queries</li>
 177    * <li>tear down the structure by deleting entries, verifying correctness at
 178    * each stage</li>
 179    * </ul>
 180    */
 181   @Test(groups = "Functional", dataProvider = "scalesOfLife")
 182   public void test_pseudoRandom(Integer scale)
 183   {
 184     NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
 185     List<SequenceFeature> features = new ArrayList<SequenceFeature>(scale);
 186
 187     testAdd_pseudoRandom(scale, ncl, features);
 188
 189     /*
 190      * sort the list of added ranges - this doesn't affect the test,
 191      * just makes it easier to inspect the data in the debugger
 192      */
 193     Collections.sort(features, sorter);
 194
 195     testFindOverlaps_pseudoRandom(ncl, scale, features);
 196
 197     testDelete_pseudoRandom(ncl, features);
 198   }
 199
 200   /**
 201    * Pick randomly selected entries to delete in turn, checking the NCList size
 202    * and validity at each stage, until it is empty
 203    *
 204    * @param ncl
 205    * @param features
 206    */
 207   protected void testDelete_pseudoRandom(NCList<SequenceFeature> ncl,
 208           List<SequenceFeature> features)
 209   {
 210     int deleted = 0;
 211
 212     while (!features.isEmpty())
 213     {
 214       assertEquals(ncl.size(), features.size());
 215       int toDelete = random.nextInt(features.size());
 216       SequenceFeature entry = features.get(toDelete);
 217       assertTrue(ncl.contains(entry), String.format(
 218               "NCList doesn't contain entry [%d] '%s'!", deleted,
 219               entry.toString()));
 220
 221       ncl.delete(entry);
 222       assertFalse(ncl.contains(entry), String.format(
 223               "NCList still contains deleted entry [%d] '%s'!", deleted,
 224               entry.toString()));
 225       features.remove(toDelete);
 226       deleted++;
 227
 228       assertTrue(ncl.isValid(), String.format(
 229               "NCList invalid after %d deletions, last deleted was '%s'",
 230               deleted, entry.toString()));
 231
 232       /*
 233        * brute force check that deleting one entry didn't delete any others
 234        */
 235       for (int i = 0; i < features.size(); i++)
 236       {
 237         SequenceFeature sf = features.get(i);
 238         assertTrue(ncl.contains(sf), String.format(
 239                         "NCList doesn't contain entry [%d] %s after deleting '%s'!",
 240                         i, sf.toString(), entry.toString()));
 241       }
 242     }
 243     assertEquals(ncl.size(), 0); // all gone
 244   }
 245
 246   /**
 247    * Randomly generate entries and add them to the NCList, checking its validity
 248    * and size at each stage. A few entries should be duplicates (by equals test)
 249    * so not get added.
 250    *
 251    * @param scale
 252    * @param ncl
 253    * @param features
 254    */
 255   protected void testAdd_pseudoRandom(Integer scale,
 256           NCList<SequenceFeature> ncl,
 257           List<SequenceFeature> features)
 258   {
 259     int count = 0;
 260     final int size = 50;
 261
 262     for (int i = 0; i < size; i++)
 263     {
 264       int r1 = random.nextInt(scale + 1);
 265       int r2 = random.nextInt(scale + 1);
 266       int from = Math.min(r1, r2);
 267       int to = Math.max(r1, r2);
 268
 269       /*
 270        * choice of two feature values means that occasionally an identical
 271        * feature may be generated, in which case it should not be added
 272        */
 273       float value = (float) i % 2;
 274       SequenceFeature feature = new SequenceFeature("Pfam", "", from, to,
 275               value, "group");
 276
 277       /*
 278        * add to NCList - with duplicate entries (by equals) disallowed
 279        */
 280       ncl.add(feature, false);
 281       if (features.contains(feature))
 282       {
 283         System.out.println("Duplicate feature generated "
 284                 + feature.toString());
 285       }
 286       else
 287       {
 288         features.add(feature);
 289         count++;
 290       }
 291
 292       /*
 293        * check list format is valid at each stage of its construction
 294        */
 295       assertTrue(ncl.isValid(),
 296               String.format("Failed for scale = %d, i=%d", scale, i));
 297       assertEquals(ncl.size(), count);
 298     }
 299     // System.out.println(ncl.prettyPrint());
 300   }
 301
 302   /**
 303    * A helper method that generates pseudo-random range queries and veries that
 304    * findOverlaps returns the correct matches
 305    *
 306    * @param ncl
 307    *          the NCList to query
 308    * @param scale
 309    *          ncl maximal range is [0, scale]
 310    * @param features
 311    *          a list of the ranges stored in ncl
 312    */
 313   protected void testFindOverlaps_pseudoRandom(NCList<SequenceFeature> ncl,
 314           int scale,
 315           List<SequenceFeature> features)
 316   {
 317     int halfScale = scale / 2;
 318     int minIterations = 20;
 319
 320     /*
 321      * generates ranges in [-halfScale, scale+halfScale]
 322      * - some should be internal to [0, scale] P = 1/4
 323      * - some should lie before 0 P = 1/16
 324      * - some should lie after scale P = 1/16
 325      * - some should overlap left P = 1/4
 326      * - some should overlap right P = 1/4
 327      * - some should enclose P = 1/8
 328      *
 329      * 50 iterations give a 96% probability of including the
 330      * unlikeliest case; keep going until we have done all!
 331      */
 332     boolean inside = false;
 333     boolean enclosing = false;
 334     boolean before = false;
 335     boolean after = false;
 336     boolean overlapLeft = false;
 337     boolean overlapRight = false;
 338     boolean allCasesCovered = false;
 339
 340     int i = 0;
 341     while (i < minIterations || !allCasesCovered)
 342     {
 343       i++;
 344       int r1 = random.nextInt((scale + 1) * 2);
 345       int r2 = random.nextInt((scale + 1) * 2);
 346       int from = Math.min(r1, r2) - halfScale;
 347       int to = Math.max(r1, r2) - halfScale;
 348
 349       /*
 350        * ensure all cases of interest get covered
 351        */
 352       inside |= from >= 0 && to <= scale;
 353       enclosing |= from <= 0 && to >= scale;
 354       before |= to < 0;
 355       after |= from > scale;
 356       overlapLeft |= from < 0 && to >= 0 && to <= scale;
 357       overlapRight |= from >= 0 && from <= scale && to > scale;
 358       if (!allCasesCovered)
 359       {
 360         allCasesCovered |= inside && enclosing && before && after
 361               && overlapLeft && overlapRight;
 362         if (allCasesCovered)
 363         {
 364           System.out
 365                   .println(String
 366                           .format("Covered all findOverlaps cases after %d iterations for scale %d",
 367                                   i, scale));
 368         }
 369       }
 370
 371       verifyFindOverlaps(ncl, from, to, features);
 372     }
 373   }
 374
 375   /**
 376    * A helper method that verifies that overlaps found by interrogating an
 377    * NCList correctly match those found by brute force search
 378    *
 379    * @param ncl
 380    * @param from
 381    * @param to
 382    * @param features
 383    */
 384   protected void verifyFindOverlaps(NCList<SequenceFeature> ncl, int from,
 385           int to, List<SequenceFeature> features)
 386   {
 387     List<SequenceFeature> overlaps = ncl.findOverlaps(from, to);
 388
 389     /*
 390      * check returned entries do indeed overlap from-to range
 391      */
 392     for (ContiguousI sf : overlaps)
 393     {
 394       int begin = sf.getBegin();
 395       int end = sf.getEnd();
 396       assertTrue(begin <= to && end >= from, String.format(
 397               "[%d, %d] does not overlap query range [%d, %d]", begin, end,
 398               from, to));
 399     }
 400
 401     /*
 402      * check overlapping ranges are included in the results
 403      * (the test above already shows non-overlapping ranges are not)
 404      */
 405     for (ContiguousI sf : features)
 406     {
 407       int begin = sf.getBegin();
 408       int end = sf.getEnd();
 409       if (begin <= to && end >= from)
 410       {
 411         boolean found = overlaps.contains(sf);
 412         assertTrue(found, String.format(
 413                 "[%d, %d] missing in query range [%d, %d]", begin, end,
 414                 from, to));
 415       }
 416     }
 417   }
 418
 419   @Test(groups = "Functional")
 420   public void testGetEntries()
 421   {
 422     List<Range> ranges = new ArrayList<Range>();
 423     Range r1 = new Range(20, 20);
 424     Range r2 = new Range(10, 20);
 425     Range r3 = new Range(15, 30);
 426     Range r4 = new Range(10, 30);
 427     Range r5 = new Range(11, 19);
 428     Range r6 = new Range(10, 20);
 429     ranges.add(r1);
 430     ranges.add(r2);
 431     ranges.add(r3);
 432     ranges.add(r4);
 433     ranges.add(r5);
 434     ranges.add(r6);
 435
 436     NCList<Range> ncl = new NCList<Range>(ranges);
 437     Range r7 = new Range(1, 100);
 438     ncl.add(r7);
 439
 440     List<Range> contents = ncl.getEntries();
 441     assertEquals(contents.size(), 7);
 442     assertTrue(contents.contains(r1));
 443     assertTrue(contents.contains(r2));
 444     assertTrue(contents.contains(r3));
 445     assertTrue(contents.contains(r4));
 446     assertTrue(contents.contains(r5));
 447     assertTrue(contents.contains(r6));
 448     assertTrue(contents.contains(r7));
 449
 450     ncl = new NCList<Range>();
 451     assertTrue(ncl.getEntries().isEmpty());
 452   }
 453
 454   @Test(groups = "Functional")
 455   public void testDelete()
 456   {
 457     List<Range> ranges = new ArrayList<Range>();
 458     Range r1 = new Range(20, 30);
 459     ranges.add(r1);
 460     NCList<Range> ncl = new NCList<Range>(ranges);
 461     assertTrue(ncl.getEntries().contains(r1));
 462
 463     Range r2 = new Range(20, 30);
 464     assertFalse(ncl.delete(null)); // null argument
 465     assertFalse(ncl.delete(r2)); // never added
 466     assertTrue(ncl.delete(r1)); // success
 467     assertTrue(ncl.getEntries().isEmpty());
 468
 469     /*
 470      * tests where object.equals() == true
 471      */
 472     NCList<SequenceFeature> features = new NCList<SequenceFeature>();
 473     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
 474             "group");
 475     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
 476             "group");
 477     features.add(sf1);
 478     assertEquals(sf1, sf2); // sf1.equals(sf2)
 479     assertFalse(features.delete(sf2)); // equality is not enough for deletion
 480     assertTrue(features.getEntries().contains(sf1)); // still there!
 481     assertTrue(features.delete(sf1));
 482     assertTrue(features.getEntries().isEmpty()); // gone now
 483
 484     /*
 485      * test with duplicate objects in NCList
 486      */
 487     features.add(sf1);
 488     features.add(sf1);
 489     assertEquals(features.getEntries().size(), 2);
 490     assertSame(features.getEntries().get(0), sf1);
 491     assertSame(features.getEntries().get(1), sf1);
 492     assertTrue(features.delete(sf1)); // first match only is deleted
 493     assertTrue(features.contains(sf1));
 494     assertEquals(features.size(), 1);
 495     assertTrue(features.delete(sf1));
 496     assertTrue(features.getEntries().isEmpty());
 497   }
 498
 499   @Test(groups = "Functional")
 500   public void testAdd_overlapping()
 501   {
 502     List<Range> ranges = new ArrayList<Range>();
 503     ranges.add(new Range(40, 50));
 504     ranges.add(new Range(20, 30));
 505     NCList<Range> ncl = new NCList<Range>(ranges);
 506     assertEquals(ncl.toString(), "[20-30, 40-50]");
 507     assertTrue(ncl.isValid());
 508
 509     /*
 510      * add range overlapping internally
 511      */
 512     ncl.add(new Range(25, 35));
 513     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
 514     assertTrue(ncl.isValid());
 515
 516     /*
 517      * add range overlapping last range
 518      */
 519     ncl.add(new Range(45, 55));
 520     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
 521     assertTrue(ncl.isValid());
 522
 523     /*
 524      * add range overlapping first range
 525      */
 526     ncl.add(new Range(15, 25));
 527     assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
 528     assertTrue(ncl.isValid());
 529   }
 530
 531   /**
 532    * Test the contains method (which uses object equals test)
 533    */
 534   @Test(groups = "Functional")
 535   public void testContains()
 536   {
 537     NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
 538     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
 539             "group");
 540     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
 541             "group");
 542     SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
 543             "anothergroup");
 544     ncl.add(sf1);
 545
 546     assertTrue(ncl.contains(sf1));
 547     assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
 548     assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
 549
 550     /*
 551      * make some deeper structure in the NCList
 552      */
 553     SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
 554             "group");
 555     ncl.add(sf4);
 556     assertTrue(ncl.contains(sf4));
 557     SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
 558             "group");
 559     SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
 560             "group");
 561     ncl.add(sf5);
 562     ncl.add(sf6);
 563     assertTrue(ncl.contains(sf5));
 564     assertTrue(ncl.contains(sf6));
 565   }
 566
 567   @Test(groups = "Functional")
 568   public void testIsValid()
 569   {
 570     List<Range> ranges = new ArrayList<Range>();
 571     Range r1 = new Range(40, 50);
 572     ranges.add(r1);
 573     NCList<Range> ncl = new NCList<Range>(ranges);
 574     assertTrue(ncl.isValid());
 575
 576     Range r2 = new Range(42, 44);
 577     ncl.add(r2);
 578     assertTrue(ncl.isValid());
 579     Range r3 = new Range(46, 48);
 580     ncl.add(r3);
 581     assertTrue(ncl.isValid());
 582     Range r4 = new Range(43, 43);
 583     ncl.add(r4);
 584     assertTrue(ncl.isValid());
 585
 586     assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]");
 587     assertTrue(ncl.isValid());
 588
 589     PA.setValue(r1, "start", 43);
 590     assertFalse(ncl.isValid()); // r2 not inside r1
 591     PA.setValue(r1, "start", 40);
 592     assertTrue(ncl.isValid());
 593
 594     PA.setValue(r3, "start", 41);
 595     assertFalse(ncl.isValid()); // r3 should precede r2
 596     PA.setValue(r3, "start", 46);
 597     assertTrue(ncl.isValid());
 598
 599     PA.setValue(r4, "start", 41);
 600     assertFalse(ncl.isValid()); // r4 not inside r2
 601     PA.setValue(r4, "start", 43);
 602     assertTrue(ncl.isValid());
 603
 604     PA.setValue(r4, "start", 44);
 605     assertFalse(ncl.isValid()); // r4 has reverse range
 606   }
 607
 608   @Test(groups = "Functional")
 609   public void testPrettyPrint()
 610   {
 611     /*
 612      * construct NCList from a list of ranges
 613      * they are sorted then assembled into NCList subregions
 614      * notice that 42-42 end up inside 41-46
 615      */
 616     List<Range> ranges = new ArrayList<Range>();
 617     ranges.add(new Range(40, 50));
 618     ranges.add(new Range(45, 55));
 619     ranges.add(new Range(40, 45));
 620     ranges.add(new Range(41, 46));
 621     ranges.add(new Range(42, 42));
 622     ranges.add(new Range(42, 42));
 623     NCList<Range> ncl = new NCList<Range>(ranges);
 624     assertTrue(ncl.isValid());
 625     assertEquals(ncl.toString(),
 626             "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]");
 627     String expected = "40-50\n  40-45\n41-46\n  42-42\n    42-42\n45-55\n";
 628     assertEquals(ncl.prettyPrint(), expected);
 629
 630     /*
 631      * repeat but now add ranges one at a time
 632      * notice that 42-42 end up inside 40-50 so we get
 633      * a different but equal valid NCList structure
 634      */
 635     ranges.clear();
 636     ncl = new NCList<Range>(ranges);
 637     ncl.add(new Range(40, 50));
 638     ncl.add(new Range(45, 55));
 639     ncl.add(new Range(40, 45));
 640     ncl.add(new Range(41, 46));
 641     ncl.add(new Range(42, 42));
 642     ncl.add(new Range(42, 42));
 643     assertTrue(ncl.isValid());
 644     assertEquals(ncl.toString(),
 645             "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]");
 646     expected = "40-50\n  40-45\n    42-42\n      42-42\n  41-46\n45-55\n";
 647     assertEquals(ncl.prettyPrint(), expected);
 648   }
 649
 650   /**
 651    * A test that shows different valid trees can be constructed from the same
 652    * set of ranges, depending on the order of construction
 653    */
 654   @Test(groups = "Functional")
 655   public void testConstructor_alternativeTrees()
 656   {
 657     List<Range> ranges = new ArrayList<Range>();
 658     ranges.add(new Range(10, 60));
 659     ranges.add(new Range(20, 30));
 660     ranges.add(new Range(40, 50));
 661
 662     /*
 663      * constructor with greedy traversal of sorted ranges to build nested
 664      * containment lists results in 20-30 inside 10-60, 40-50 a sibling
 665      */
 666     NCList<Range> ncl = new NCList<Range>(ranges);
 667     assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]");
 668     assertTrue(ncl.isValid());
 669
 670     /*
 671      * adding ranges one at a time results in 40-50
 672      * a sibling of 20-30 inside 10-60
 673      */
 674     ncl = new NCList<Range>(new Range(10, 60));
 675     ncl.add(new Range(20, 30));
 676     ncl.add(new Range(40, 50));
 677     assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]");
 678     assertTrue(ncl.isValid());
 679   }
 680 }