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   protected void testDelete_pseudoRandom(NCList<SequenceFeature> ncl,
 206           List<SequenceFeature> features)
 207   {
 208     int deleted = 0;
 209
 210     while (!features.isEmpty())
 211     {
 212       assertEquals(ncl.size(), 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.size(), 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   protected void testAdd_pseudoRandom(Integer scale,
 254           NCList<SequenceFeature> ncl,
 255           List<SequenceFeature> features)
 256   {
 257     int count = 0;
 258     final int size = 50;
 259
 260     for (int i = 0; i < size; i++)
 261     {
 262       int r1 = random.nextInt(scale + 1);
 263       int r2 = random.nextInt(scale + 1);
 264       int from = Math.min(r1, r2);
 265       int to = Math.max(r1, r2);
 266
 267       /*
 268        * choice of two feature values means that occasionally an identical
 269        * feature may be generated, in which case it should not be added
 270        */
 271       float value = (float) i % 2;
 272       SequenceFeature feature = new SequenceFeature("Pfam", "", from, to,
 273               value, "group");
 274
 275       /*
 276        * add to NCList - with duplicate entries (by equals) disallowed
 277        */
 278       ncl.add(feature, false);
 279       if (features.contains(feature))
 280       {
 281         System.out.println("Duplicate feature generated "
 282                 + feature.toString());
 283       }
 284       else
 285       {
 286         features.add(feature);
 287         count++;
 288       }
 289
 290       /*
 291        * check list format is valid at each stage of its construction
 292        */
 293       assertTrue(ncl.isValid(),
 294               String.format("Failed for scale = %d, i=%d", scale, i));
 295       assertEquals(ncl.size(), count);
 296     }
 297     // System.out.println(ncl.prettyPrint());
 298   }
 299
 300   /**
 301    * A helper method that generates pseudo-random range queries and veries that
 302    * findOverlaps returns the correct matches
 303    *
 304    * @param ncl
 305    *          the NCList to query
 306    * @param scale
 307    *          ncl maximal range is [0, scale]
 308    * @param features
 309    *          a list of the ranges stored in ncl
 310    */
 311   protected void testFindOverlaps_pseudoRandom(NCList<SequenceFeature> ncl,
 312           int scale,
 313           List<SequenceFeature> features)
 314   {
 315     int halfScale = scale / 2;
 316     int minIterations = 20;
 317
 318     /*
 319      * generates ranges in [-halfScale, scale+halfScale]
 320      * - some should be internal to [0, scale] P = 1/4
 321      * - some should lie before 0 P = 1/16
 322      * - some should lie after scale P = 1/16
 323      * - some should overlap left P = 1/4
 324      * - some should overlap right P = 1/4
 325      * - some should enclose P = 1/8
 326      *
 327      * 50 iterations give a 96% probability of including the
 328      * unlikeliest case; keep going until we have done all!
 329      */
 330     boolean inside = false;
 331     boolean enclosing = false;
 332     boolean before = false;
 333     boolean after = false;
 334     boolean overlapLeft = false;
 335     boolean overlapRight = false;
 336     boolean allCasesCovered = false;
 337
 338     int i = 0;
 339     while (i < minIterations || !allCasesCovered)
 340     {
 341       i++;
 342       int r1 = random.nextInt((scale + 1) * 2);
 343       int r2 = random.nextInt((scale + 1) * 2);
 344       int from = Math.min(r1, r2) - halfScale;
 345       int to = Math.max(r1, r2) - halfScale;
 346
 347       /*
 348        * ensure all cases of interest get covered
 349        */
 350       inside |= from >= 0 && to <= scale;
 351       enclosing |= from <= 0 && to >= scale;
 352       before |= to < 0;
 353       after |= from > scale;
 354       overlapLeft |= from < 0 && to >= 0 && to <= scale;
 355       overlapRight |= from >= 0 && from <= scale && to > scale;
 356       if (!allCasesCovered)
 357       {
 358         allCasesCovered |= inside && enclosing && before && after
 359               && overlapLeft && overlapRight;
 360         if (allCasesCovered)
 361         {
 362           System.out
 363                   .println(String
 364                           .format("Covered all findOverlaps cases after %d iterations for scale %d",
 365                                   i, scale));
 366         }
 367       }
 368
 369       verifyFindOverlaps(ncl, from, to, features);
 370     }
 371   }
 372
 373   /**
 374    * A helper method that verifies that overlaps found by interrogating an
 375    * NCList correctly match those found by brute force search
 376    *
 377    * @param ncl
 378    * @param from
 379    * @param to
 380    * @param features
 381    */
 382   protected void verifyFindOverlaps(NCList<SequenceFeature> ncl, int from,
 383           int to, List<SequenceFeature> features)
 384   {
 385     List<SequenceFeature> overlaps = ncl.findOverlaps(from, to);
 386
 387     /*
 388      * check returned entries do indeed overlap from-to range
 389      */
 390     for (ContiguousI sf : overlaps)
 391     {
 392       int begin = sf.getBegin();
 393       int end = sf.getEnd();
 394       assertTrue(begin <= to && end >= from, String.format(
 395               "[%d, %d] does not overlap query range [%d, %d]", begin, end,
 396               from, to));
 397     }
 398
 399     /*
 400      * check overlapping ranges are included in the results
 401      * (the test above already shows non-overlapping ranges are not)
 402      */
 403     for (ContiguousI sf : features)
 404     {
 405       int begin = sf.getBegin();
 406       int end = sf.getEnd();
 407       if (begin <= to && end >= from)
 408       {
 409         boolean found = overlaps.contains(sf);
 410         assertTrue(found, String.format(
 411                 "[%d, %d] missing in query range [%d, %d]", begin, end,
 412                 from, to));
 413       }
 414     }
 415   }
 416
 417   @Test(groups = "Functional")
 418   public void testGetEntries()
 419   {
 420     List<Range> ranges = new ArrayList<Range>();
 421     Range r1 = new Range(20, 20);
 422     Range r2 = new Range(10, 20);
 423     Range r3 = new Range(15, 30);
 424     Range r4 = new Range(10, 30);
 425     Range r5 = new Range(11, 19);
 426     Range r6 = new Range(10, 20);
 427     ranges.add(r1);
 428     ranges.add(r2);
 429     ranges.add(r3);
 430     ranges.add(r4);
 431     ranges.add(r5);
 432     ranges.add(r6);
 433
 434     NCList<Range> ncl = new NCList<Range>(ranges);
 435     Range r7 = new Range(1, 100);
 436     ncl.add(r7);
 437
 438     List<Range> contents = ncl.getEntries();
 439     assertEquals(contents.size(), 7);
 440     assertTrue(contents.contains(r1));
 441     assertTrue(contents.contains(r2));
 442     assertTrue(contents.contains(r3));
 443     assertTrue(contents.contains(r4));
 444     assertTrue(contents.contains(r5));
 445     assertTrue(contents.contains(r6));
 446     assertTrue(contents.contains(r7));
 447
 448     ncl = new NCList<Range>();
 449     assertTrue(ncl.getEntries().isEmpty());
 450   }
 451
 452   @Test(groups = "Functional")
 453   public void testDelete()
 454   {
 455     List<Range> ranges = new ArrayList<Range>();
 456     Range r1 = new Range(20, 30);
 457     ranges.add(r1);
 458     NCList<Range> ncl = new NCList<Range>(ranges);
 459     assertTrue(ncl.getEntries().contains(r1));
 460
 461     Range r2 = new Range(20, 30);
 462     assertFalse(ncl.delete(null)); // null argument
 463     assertFalse(ncl.delete(r2)); // never added
 464     assertTrue(ncl.delete(r1)); // success
 465     assertTrue(ncl.getEntries().isEmpty());
 466
 467     /*
 468      * tests where object.equals() == true
 469      */
 470     NCList<SequenceFeature> features = new NCList<SequenceFeature>();
 471     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
 472             "group");
 473     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
 474             "group");
 475     features.add(sf1);
 476     assertEquals(sf1, sf2); // sf1.equals(sf2)
 477     assertFalse(features.delete(sf2)); // equality is not enough for deletion
 478     assertTrue(features.getEntries().contains(sf1)); // still there!
 479     assertTrue(features.delete(sf1));
 480     assertTrue(features.getEntries().isEmpty()); // gone now
 481
 482     /*
 483      * test with duplicate objects in NCList
 484      */
 485     features.add(sf1);
 486     features.add(sf1);
 487     assertEquals(features.getEntries().size(), 2);
 488     assertSame(features.getEntries().get(0), sf1);
 489     assertSame(features.getEntries().get(1), sf1);
 490     assertTrue(features.delete(sf1)); // first match only is deleted
 491     assertTrue(features.contains(sf1));
 492     assertEquals(features.size(), 1);
 493     assertTrue(features.delete(sf1));
 494     assertTrue(features.getEntries().isEmpty());
 495   }
 496
 497   @Test(groups = "Functional")
 498   public void testAdd_overlapping()
 499   {
 500     List<Range> ranges = new ArrayList<Range>();
 501     ranges.add(new Range(40, 50));
 502     ranges.add(new Range(20, 30));
 503     NCList<Range> ncl = new NCList<Range>(ranges);
 504     assertEquals(ncl.toString(), "[20-30, 40-50]");
 505     assertTrue(ncl.isValid());
 506
 507     /*
 508      * add range overlapping internally
 509      */
 510     ncl.add(new Range(25, 35));
 511     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
 512     assertTrue(ncl.isValid());
 513
 514     /*
 515      * add range overlapping last range
 516      */
 517     ncl.add(new Range(45, 55));
 518     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
 519     assertTrue(ncl.isValid());
 520
 521     /*
 522      * add range overlapping first range
 523      */
 524     ncl.add(new Range(15, 25));
 525     assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
 526     assertTrue(ncl.isValid());
 527   }
 528
 529   /**
 530    * Test the contains method (which uses object equals test)
 531    */
 532   @Test(groups = "Functional")
 533   public void testContains()
 534   {
 535     NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
 536     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
 537             "group");
 538     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
 539             "group");
 540     SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
 541             "anothergroup");
 542     ncl.add(sf1);
 543
 544     assertTrue(ncl.contains(sf1));
 545     assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
 546     assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
 547
 548     /*
 549      * make some deeper structure in the NCList
 550      */
 551     SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
 552             "group");
 553     ncl.add(sf4);
 554     assertTrue(ncl.contains(sf4));
 555     SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
 556             "group");
 557     SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
 558             "group");
 559     ncl.add(sf5);
 560     ncl.add(sf6);
 561     assertTrue(ncl.contains(sf5));
 562     assertTrue(ncl.contains(sf6));
 563   }
 564
 565   @Test(groups = "Functional")
 566   public void testIsValid()
 567   {
 568     List<Range> ranges = new ArrayList<Range>();
 569     Range r1 = new Range(40, 50);
 570     ranges.add(r1);
 571     NCList<Range> ncl = new NCList<Range>(ranges);
 572     assertTrue(ncl.isValid());
 573
 574     Range r2 = new Range(42, 44);
 575     ncl.add(r2);
 576     assertTrue(ncl.isValid());
 577     Range r3 = new Range(46, 48);
 578     ncl.add(r3);
 579     assertTrue(ncl.isValid());
 580     Range r4 = new Range(43, 43);
 581     ncl.add(r4);
 582     assertTrue(ncl.isValid());
 583
 584     assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]");
 585     assertTrue(ncl.isValid());
 586
 587     r1.start = 43;
 588     assertFalse(ncl.isValid()); // r2 not inside r1
 589     r1.start = 40;
 590     assertTrue(ncl.isValid());
 591
 592     r3.start = 41;
 593     assertFalse(ncl.isValid()); // r3 should precede r2
 594     r3.start = 46;
 595     assertTrue(ncl.isValid());
 596
 597     r4.start = 41;
 598     assertFalse(ncl.isValid()); // r4 not inside r2
 599     r4.start = 43;
 600     assertTrue(ncl.isValid());
 601
 602     r4.start = 44;
 603     assertFalse(ncl.isValid()); // r4 has reverse range
 604   }
 605
 606   @Test(groups = "Functional")
 607   public void testPrettyPrint()
 608   {
 609     /*
 610      * construct NCList from a list of ranges
 611      * they are sorted then assembled into NCList subregions
 612      * notice that 42-42 end up inside 41-46
 613      */
 614     List<Range> ranges = new ArrayList<Range>();
 615     ranges.add(new Range(40, 50));
 616     ranges.add(new Range(45, 55));
 617     ranges.add(new Range(40, 45));
 618     ranges.add(new Range(41, 46));
 619     ranges.add(new Range(42, 42));
 620     ranges.add(new Range(42, 42));
 621     NCList<Range> ncl = new NCList<Range>(ranges);
 622     assertTrue(ncl.isValid());
 623     assertEquals(ncl.toString(),
 624             "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]");
 625     String expected = "40-50\n  40-45\n41-46\n  42-42\n    42-42\n45-55\n";
 626     assertEquals(ncl.prettyPrint(), expected);
 627
 628     /*
 629      * repeat but now add ranges one at a time
 630      * notice that 42-42 end up inside 40-50 so we get
 631      * a different but equal valid NCList structure
 632      */
 633     ranges.clear();
 634     ncl = new NCList<Range>(ranges);
 635     ncl.add(new Range(40, 50));
 636     ncl.add(new Range(45, 55));
 637     ncl.add(new Range(40, 45));
 638     ncl.add(new Range(41, 46));
 639     ncl.add(new Range(42, 42));
 640     ncl.add(new Range(42, 42));
 641     assertTrue(ncl.isValid());
 642     assertEquals(ncl.toString(),
 643             "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]");
 644     expected = "40-50\n  40-45\n    42-42\n      42-42\n  41-46\n45-55\n";
 645     assertEquals(ncl.prettyPrint(), expected);
 646   }
 647
 648   /**
 649    * A test that shows different valid trees can be constructed from the same
 650    * set of ranges, depending on the order of construction
 651    */
 652   @Test(groups = "Functional")
 653   public void testConstructor_alternativeTrees()
 654   {
 655     List<Range> ranges = new ArrayList<Range>();
 656     ranges.add(new Range(10, 60));
 657     ranges.add(new Range(20, 30));
 658     ranges.add(new Range(40, 50));
 659
 660     /*
 661      * constructor with greedy traversal of sorted ranges to build nested
 662      * containment lists results in 20-30 inside 10-60, 40-50 a sibling
 663      */
 664     NCList<Range> ncl = new NCList<Range>(ranges);
 665     assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]");
 666     assertTrue(ncl.isValid());
 667
 668     /*
 669      * adding ranges one at a time results in 40-50
 670      * a sibling of 20-30 inside 10-60
 671      */
 672     ncl = new NCList<Range>(new Range(10, 60));
 673     ncl.add(new Range(20, 30));
 674     ncl.add(new Range(40, 50));
 675     assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]");
 676     assertTrue(ncl.isValid());
 677   }
 678 }