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, with
 168    * checks for validity of the data structure, and searches for (pseudo-random)
 169    * overlap ranges, for greater (but not perfect!) confidence that corner cases
 170    * are being handled correctly.
 171    */
 172   @Test(groups = "Functional", dataProvider = "scalesOfLife")
 173   public void testAdd_FindOverlaps_pseudoRandom(Integer scale)
 174   {
 175     NCList<Range> ncl = new NCList<Range>();
 176     int count = 0;
 177     List<Range> ranges = new ArrayList<Range>(scale);
 178
 179     for (int i = 0; i < scale; i++)
 180     {
 181       int r1 = random.nextInt(scale + 1);
 182       int r2 = random.nextInt(scale + 1);
 183       int from = Math.min(r1, r2);
 184       int to = Math.max(r1, r2);
 185       Range range = new Range(from, to);
 186       ncl.add(range);
 187       ranges.add(range);
 188
 189       /*
 190        * check list format is valid at each stage of its construction
 191        */
 192       assertTrue(ncl.isValid(),
 193               String.format("Failed for scale = %d, i=%d", scale, i));
 194       count++;
 195       assertEquals(ncl.getSize(), count);
 196     }
 197     // System.out.println(ncl.prettyPrint());
 198
 199     /*
 200      * sort the list of added ranges - this doesn't affect the test,
 201      * just makes it easier to inspect the data in the debugger
 202      */
 203     Collections.sort(ranges, sorter);
 204
 205     testFindOverlaps(ncl, scale, ranges);
 206   }
 207
 208   /**
 209    * A helper method that generates pseudo-random range queries and veries that
 210    * findOverlaps returns the correct matches
 211    *
 212    * @param ncl
 213    *          the NCList to query
 214    * @param scale
 215    *          ncl maximal range is [0, scale]
 216    * @param ranges
 217    *          a list of the ranges stored in ncl
 218    */
 219   protected void testFindOverlaps(NCList<Range> ncl, int scale,
 220           List<Range> ranges)
 221   {
 222     int halfScale = scale / 2;
 223     int minIterations = 20;
 224
 225     /*
 226      * generates ranges in [-halfScale, scale+halfScale]
 227      * - some should be internal to [0, scale] P = 1/4
 228      * - some should lie before 0 P = 1/16
 229      * - some should lie after scale P = 1/16
 230      * - some should overlap left P = 1/4
 231      * - some should overlap right P = 1/4
 232      * - some should enclose P = 1/8
 233      *
 234      * 50 iterations give a 96% probability of including the
 235      * unlikeliest case; keep going until we have done all!
 236      */
 237     boolean inside = false;
 238     boolean enclosing = false;
 239     boolean before = false;
 240     boolean after = false;
 241     boolean overlapLeft = false;
 242     boolean overlapRight = false;
 243     boolean allCasesCovered = false;
 244
 245     int i = 0;
 246     while (i < minIterations || !allCasesCovered)
 247     {
 248       i++;
 249       int r1 = random.nextInt((scale + 1) * 2);
 250       int r2 = random.nextInt((scale + 1) * 2);
 251       int from = Math.min(r1, r2) - halfScale;
 252       int to = Math.max(r1, r2) - halfScale;
 253
 254       /*
 255        * ensure all cases of interest get covered
 256        */
 257       inside |= from >= 0 && to <= scale;
 258       enclosing |= from <= 0 && to >= scale;
 259       before |= to < 0;
 260       after |= from > scale;
 261       overlapLeft |= from < 0 && to >= 0 && to <= scale;
 262       overlapRight |= from >= 0 && from <= scale && to > scale;
 263       if (!allCasesCovered)
 264       {
 265         allCasesCovered |= inside && enclosing && before && after
 266               && overlapLeft && overlapRight;
 267         if (allCasesCovered)
 268         {
 269           System.out
 270                   .println(String
 271                           .format("Covered all findOverlaps cases after %d iterations for scale %d",
 272                                   i, scale));
 273         }
 274       }
 275
 276       verifyFindOverlaps(ncl, from, to, ranges);
 277     }
 278   }
 279
 280   /**
 281    * A helper method that verifies that overlaps found by interrogating an
 282    * NCList correctly match those found by brute force search
 283    *
 284    * @param ncl
 285    * @param from
 286    * @param to
 287    * @param ranges
 288    */
 289   protected void verifyFindOverlaps(NCList<Range> ncl, int from, int to,
 290           List<Range> ranges)
 291   {
 292     List<Range> overlaps = ncl.findOverlaps(from, to);
 293
 294     /*
 295      * check returned entries do indeed overlap from-to range
 296      */
 297     for (Range r : overlaps)
 298     {
 299       int begin = r.getBegin();
 300       int end = r.getEnd();
 301       assertTrue(begin <= to && end >= from, String.format(
 302               "[%d, %d] does not overlap query range [%d, %d]", begin, end,
 303               from, to));
 304     }
 305
 306     /*
 307      * check overlapping ranges are included in the results
 308      * (the test above already shows non-overlapping ranges are not)
 309      */
 310     for (Range r : ranges)
 311     {
 312       int begin = r.getBegin();
 313       int end = r.getEnd();
 314       if (begin <= to && end >= from)
 315       {
 316         boolean found = overlaps.contains(r);
 317         assertTrue(found, String.format(
 318                 "[%d, %d] missing in query range [%d, %d]", begin, end,
 319                 from, to));
 320       }
 321     }
 322   }
 323
 324   @Test(groups = "Functional")
 325   public void testGetEntries()
 326   {
 327     List<Range> ranges = new ArrayList<Range>();
 328     Range r1 = new Range(20, 20);
 329     Range r2 = new Range(10, 20);
 330     Range r3 = new Range(15, 30);
 331     Range r4 = new Range(10, 30);
 332     Range r5 = new Range(11, 19);
 333     Range r6 = new Range(10, 20);
 334     ranges.add(r1);
 335     ranges.add(r2);
 336     ranges.add(r3);
 337     ranges.add(r4);
 338     ranges.add(r5);
 339     ranges.add(r6);
 340
 341     NCList<Range> ncl = new NCList<Range>(ranges);
 342     Range r7 = new Range(1, 100);
 343     ncl.add(r7);
 344
 345     List<Range> contents = ncl.getEntries();
 346     assertEquals(contents.size(), 7);
 347     assertTrue(contents.contains(r1));
 348     assertTrue(contents.contains(r2));
 349     assertTrue(contents.contains(r3));
 350     assertTrue(contents.contains(r4));
 351     assertTrue(contents.contains(r5));
 352     assertTrue(contents.contains(r6));
 353     assertTrue(contents.contains(r7));
 354
 355     ncl = new NCList<Range>();
 356     assertTrue(ncl.getEntries().isEmpty());
 357   }
 358
 359   @Test(groups = "Functional")
 360   public void testDelete()
 361   {
 362     List<Range> ranges = new ArrayList<Range>();
 363     Range r1 = new Range(20, 30);
 364     ranges.add(r1);
 365     NCList<Range> ncl = new NCList<Range>(ranges);
 366     assertTrue(ncl.getEntries().contains(r1));
 367
 368     Range r2 = new Range(20, 30);
 369     assertFalse(ncl.delete(null)); // null argument
 370     assertFalse(ncl.delete(r2)); // never added
 371     assertTrue(ncl.delete(r1)); // success
 372     assertTrue(ncl.getEntries().isEmpty());
 373
 374     /*
 375      * tests where object.equals() == true
 376      */
 377     NCList<SequenceFeature> features = new NCList<SequenceFeature>();
 378     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
 379             "group");
 380     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
 381             "group");
 382     features.add(sf1);
 383     assertEquals(sf1, sf2); // sf1.equals(sf2)
 384     assertFalse(features.delete(sf2)); // equality is not enough for deletion
 385     assertTrue(features.getEntries().contains(sf1)); // still there!
 386     assertTrue(features.delete(sf1));
 387     assertTrue(features.getEntries().isEmpty()); // gone now
 388
 389     /*
 390      * test with duplicate objects in NCList
 391      */
 392     features.add(sf1);
 393     features.add(sf1);
 394     assertEquals(features.getEntries().size(), 2);
 395     assertSame(features.getEntries().get(0), sf1);
 396     assertSame(features.getEntries().get(1), sf1);
 397     assertTrue(features.delete(sf1)); // first match only is deleted
 398     assertTrue(features.contains(sf1));
 399     assertEquals(features.getSize(), 1);
 400     assertTrue(features.delete(sf1));
 401     assertTrue(features.getEntries().isEmpty());
 402   }
 403
 404   @Test(groups = "Functional")
 405   public void testAdd_overlapping()
 406   {
 407     List<Range> ranges = new ArrayList<Range>();
 408     ranges.add(new Range(40, 50));
 409     ranges.add(new Range(20, 30));
 410     NCList<Range> ncl = new NCList<Range>(ranges);
 411     assertEquals(ncl.toString(), "[20-30, 40-50]");
 412     assertTrue(ncl.isValid());
 413
 414     /*
 415      * add range overlapping internally
 416      */
 417     ncl.add(new Range(25, 35));
 418     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
 419     assertTrue(ncl.isValid());
 420
 421     /*
 422      * add range overlapping last range
 423      */
 424     ncl.add(new Range(45, 55));
 425     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
 426     assertTrue(ncl.isValid());
 427
 428     /*
 429      * add range overlapping first range
 430      */
 431     ncl.add(new Range(15, 25));
 432     assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
 433     assertTrue(ncl.isValid());
 434   }
 435
 436   /**
 437    * Test the contains method (which uses object equals test)
 438    */
 439   @Test(groups = "Functional")
 440   public void testContains()
 441   {
 442     NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
 443     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
 444             "group");
 445     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
 446             "group");
 447     SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
 448             "anothergroup");
 449     ncl.add(sf1);
 450
 451     assertTrue(ncl.contains(sf1));
 452     assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
 453     assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
 454
 455     /*
 456      * make some deeper structure in the NCList
 457      */
 458     SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
 459             "group");
 460     ncl.add(sf4);
 461     assertTrue(ncl.contains(sf4));
 462     SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
 463             "group");
 464     SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
 465             "group");
 466     ncl.add(sf5);
 467     ncl.add(sf6);
 468     assertTrue(ncl.contains(sf5));
 469     assertTrue(ncl.contains(sf6));
 470   }
 471 }