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