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