test/jalview/datamodel/features/NCListTest.java

   1 package jalview.datamodel.features;
   2 import static org.testng.Assert.assertEquals;
   3 import static org.testng.Assert.assertTrue;
   4
   5 import java.util.ArrayList;
   6 import java.util.Collections;
   7 import java.util.Comparator;
   8 import java.util.List;
   9 import java.util.Random;
  10
  11 import org.testng.annotations.DataProvider;
  12 import org.testng.annotations.Test;
  13
  14 public class NCListTest
  15 {
  16
  17   private Random random = new Random(107);
  18
  19   private Comparator<ContiguousI> sorter = new RangeComparator(true);
  20
  21   /**
  22    * A basic sanity test of the constructor
  23    */
  24   @Test(groups = "Functional")
  25   public void testConstructor()
  26   {
  27     List<Range> ranges = new ArrayList<Range>();
  28     ranges.add(new Range(20, 20));
  29     ranges.add(new Range(10, 20));
  30     ranges.add(new Range(15, 30));
  31     ranges.add(new Range(10, 30));
  32     ranges.add(new Range(11, 19));
  33     ranges.add(new Range(10, 20));
  34     ranges.add(new Range(1, 100));
  35
  36     NCList<Range> ncl = new NCList<Range>(ranges);
  37     String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
  38     assertEquals(ncl.toString(), expected);
  39     assertTrue(ncl.isValid());
  40
  41     Collections.reverse(ranges);
  42     ncl = new NCList<Range>(ranges);
  43     assertEquals(ncl.toString(), expected);
  44     assertTrue(ncl.isValid());
  45   }
  46
  47   @Test(groups = "Functional")
  48   public void testFindOverlaps()
  49   {
  50     List<Range> ranges = new ArrayList<Range>();
  51     ranges.add(new Range(20, 50));
  52     ranges.add(new Range(30, 70));
  53     ranges.add(new Range(1, 100));
  54     ranges.add(new Range(70, 120));
  55
  56     NCList<Range> ncl = new NCList<Range>(ranges);
  57
  58     List<Range> overlaps = ncl.findOverlaps(121, 122);
  59     assertEquals(overlaps.size(), 0);
  60
  61     overlaps = ncl.findOverlaps(21, 22);
  62     assertEquals(overlaps.size(), 2);
  63     assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
  64     assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
  65     assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
  66     assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
  67
  68     overlaps = ncl.findOverlaps(110, 110);
  69     assertEquals(overlaps.size(), 1);
  70     assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
  71     assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
  72   }
  73
  74   @Test(groups = "Functional")
  75   public void testAdd_onTheEnd()
  76   {
  77     List<Range> ranges = new ArrayList<Range>();
  78     ranges.add(new Range(20, 50));
  79     NCList<Range> ncl = new NCList<Range>(ranges);
  80     assertEquals(ncl.toString(), "[20-50]");
  81     assertTrue(ncl.isValid());
  82
  83     ncl.add(new Range(60, 70));
  84     assertEquals(ncl.toString(), "[20-50, 60-70]");
  85     assertTrue(ncl.isValid());
  86   }
  87
  88   @Test(groups = "Functional")
  89   public void testAdd_inside()
  90   {
  91     List<Range> ranges = new ArrayList<Range>();
  92     ranges.add(new Range(20, 50));
  93     NCList<Range> ncl = new NCList<Range>(ranges);
  94     assertEquals(ncl.toString(), "[20-50]");
  95     assertTrue(ncl.isValid());
  96
  97     ncl.add(new Range(30, 40));
  98     assertEquals(ncl.toString(), "[20-50 [30-40]]");
  99   }
 100
 101   @Test(groups = "Functional")
 102   public void testAdd_onTheFront()
 103   {
 104     List<Range> ranges = new ArrayList<Range>();
 105     ranges.add(new Range(20, 50));
 106     NCList<Range> ncl = new NCList<Range>(ranges);
 107     assertEquals(ncl.toString(), "[20-50]");
 108     assertTrue(ncl.isValid());
 109
 110     ncl.add(new Range(5, 15));
 111     assertEquals(ncl.toString(), "[5-15, 20-50]");
 112     assertTrue(ncl.isValid());
 113   }
 114
 115   @Test(groups = "Functional")
 116   public void testAdd_enclosing()
 117   {
 118     List<Range> ranges = new ArrayList<Range>();
 119     ranges.add(new Range(20, 50));
 120     ranges.add(new Range(30, 60));
 121     NCList<Range> ncl = new NCList<Range>(ranges);
 122     assertEquals(ncl.toString(), "[20-50, 30-60]");
 123     assertTrue(ncl.isValid());
 124     assertEquals(ncl.getStart(), 20);
 125
 126     ncl.add(new Range(10, 70));
 127     assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
 128     assertTrue(ncl.isValid());
 129   }
 130
 131   @Test(groups = "Functional")
 132   public void testAdd_spanning()
 133   {
 134     List<Range> ranges = new ArrayList<Range>();
 135     ranges.add(new Range(20, 40));
 136     ranges.add(new Range(60, 70));
 137     NCList<Range> ncl = new NCList<Range>(ranges);
 138     assertEquals(ncl.toString(), "[20-40, 60-70]");
 139     assertTrue(ncl.isValid());
 140
 141     ncl.add(new Range(30, 50));
 142     assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
 143     assertTrue(ncl.isValid());
 144
 145     ncl.add(new Range(40, 65));
 146     assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
 147     assertTrue(ncl.isValid());
 148   }
 149
 150   /**
 151    * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
 152    * [0-scale] interval to be stored
 153    *
 154    * @return
 155    */
 156   @DataProvider(name = "scalesOfLife")
 157   public Object[][] getScales()
 158   {
 159     return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
 160   }
 161
 162   /**
 163    * Do a number of pseudo-random (reproducible) builds of an NCList, with
 164    * checks for validity of the data structure, and searches for (pseudo-random)
 165    * overlap ranges, for greater (but not perfect!) confidence that corner cases
 166    * are being handled correctly.
 167    */
 168   @Test(groups = "Functional", dataProvider = "scalesOfLife")
 169   public void testAdd_FindOverlaps_pseudoRandom(Integer scale)
 170   {
 171     NCList<Range> ncl = new NCList<Range>();
 172     int count = 0;
 173     List<Range> ranges = new ArrayList<Range>(scale);
 174
 175     for (int i = 0; i < scale; i++)
 176     {
 177       int r1 = random.nextInt(scale + 1);
 178       int r2 = random.nextInt(scale + 1);
 179       int from = Math.min(r1, r2);
 180       int to = Math.max(r1, r2);
 181       Range range = new Range(from, to);
 182       ncl.add(range);
 183       ranges.add(range);
 184
 185       /*
 186        * check list format is valid at each stage of its construction
 187        */
 188       assertTrue(ncl.isValid(),
 189               String.format("Failed for scale = %d, i=%d", scale, i));
 190       count++;
 191       assertEquals(ncl.getSize(), count);
 192     }
 193     // System.out.println(ncl.prettyPrint());
 194
 195     /*
 196      * sort the list of added ranges - this doesn't affect the test,
 197      * just makes it easier to inspect the data in the debugger
 198      */
 199     Collections.sort(ranges, sorter);
 200
 201     testFindOverlaps(ncl, scale, ranges);
 202   }
 203
 204   /**
 205    * A helper method that generates pseudo-random range queries and veries that
 206    * findOverlaps returns the correct matches
 207    *
 208    * @param ncl
 209    *          the NCList to query
 210    * @param scale
 211    *          ncl maximal range is [0, scale]
 212    * @param ranges
 213    *          a list of the ranges stored in ncl
 214    */
 215   protected void testFindOverlaps(NCList<Range> ncl, int scale,
 216           List<Range> ranges)
 217   {
 218     int halfScale = scale / 2;
 219     int minIterations = 20;
 220
 221     /*
 222      * generates ranges in [-halfScale, scale+halfScale]
 223      * - some should be internal to [0, scale] P = 1/4
 224      * - some should lie before 0 P = 1/16
 225      * - some should lie after scale P = 1/16
 226      * - some should overlap left P = 1/4
 227      * - some should overlap right P = 1/4
 228      * - some should enclose P = 1/8
 229      *
 230      * 50 iterations give a 96% probability of including the
 231      * unlikeliest case; keep going until we have done all!
 232      */
 233     boolean inside = false;
 234     boolean enclosing = false;
 235     boolean before = false;
 236     boolean after = false;
 237     boolean overlapLeft = false;
 238     boolean overlapRight = false;
 239     boolean allCasesCovered = false;
 240
 241     int i = 0;
 242     while (i < minIterations || !allCasesCovered)
 243     {
 244       i++;
 245       int r1 = random.nextInt((scale + 1) * 2);
 246       int r2 = random.nextInt((scale + 1) * 2);
 247       int from = Math.min(r1, r2) - halfScale;
 248       int to = Math.max(r1, r2) - halfScale;
 249
 250       /*
 251        * ensure all cases of interest get covered
 252        */
 253       inside |= from >= 0 && to <= scale;
 254       enclosing |= from <= 0 && to >= scale;
 255       before |= to < 0;
 256       after |= from > scale;
 257       overlapLeft |= from < 0 && to >= 0 && to <= scale;
 258       overlapRight |= from >= 0 && from <= scale && to > scale;
 259       if (!allCasesCovered)
 260       {
 261         allCasesCovered |= inside && enclosing && before && after
 262               && overlapLeft && overlapRight;
 263         if (allCasesCovered)
 264         {
 265           System.out
 266                   .println(String
 267                           .format("Covered all findOverlaps cases after %d iterations for scale %d",
 268                                   i, scale));
 269         }
 270       }
 271
 272       verifyFindOverlaps(ncl, from, to, ranges);
 273     }
 274   }
 275
 276   /**
 277    * A helper method that verifies that overlaps found by interrogating an
 278    * NCList correctly match those found by brute force search
 279    *
 280    * @param ncl
 281    * @param from
 282    * @param to
 283    * @param ranges
 284    */
 285   protected void verifyFindOverlaps(NCList<Range> ncl, int from, int to,
 286           List<Range> ranges)
 287   {
 288     List<Range> overlaps = ncl.findOverlaps(from, to);
 289
 290     /*
 291      * check returned entries do indeed overlap from-to range
 292      */
 293     for (Range r : overlaps)
 294     {
 295       int begin = r.getBegin();
 296       int end = r.getEnd();
 297       assertTrue(begin <= to && end >= from, String.format(
 298               "[%d, %d] does not overlap query range [%d, %d]", begin, end,
 299               from, to));
 300     }
 301
 302     /*
 303      * check overlapping ranges are included in the results
 304      * (the test above already shows non-overlapping ranges are not)
 305      */
 306     for (Range r : ranges)
 307     {
 308       int begin = r.getBegin();
 309       int end = r.getEnd();
 310       if (begin <= to && end >= from)
 311       {
 312         boolean found = overlaps.contains(r);
 313         assertTrue(found, String.format(
 314                 "[%d, %d] missing in query range [%d, %d]", begin, end,
 315                 from, to));
 316       }
 317     }
 318   }
 319
 320   @Test(groups = "Functional")
 321   public void testGetEntries()
 322   {
 323     List<Range> ranges = new ArrayList<Range>();
 324     Range r1 = new Range(20, 20);
 325     Range r2 = new Range(10, 20);
 326     Range r3 = new Range(15, 30);
 327     Range r4 = new Range(10, 30);
 328     Range r5 = new Range(11, 19);
 329     Range r6 = new Range(10, 20);
 330     ranges.add(r1);
 331     ranges.add(r2);
 332     ranges.add(r3);
 333     ranges.add(r4);
 334     ranges.add(r5);
 335     ranges.add(r6);
 336
 337     NCList<Range> ncl = new NCList<Range>(ranges);
 338     Range r7 = new Range(1, 100);
 339     ncl.add(r7);
 340
 341     List<Range> contents = ncl.getEntries();
 342     assertEquals(contents.size(), 7);
 343     assertTrue(contents.contains(r1));
 344     assertTrue(contents.contains(r2));
 345     assertTrue(contents.contains(r3));
 346     assertTrue(contents.contains(r4));
 347     assertTrue(contents.contains(r5));
 348     assertTrue(contents.contains(r6));
 349     assertTrue(contents.contains(r7));
 350
 351     ncl = new NCList<Range>();
 352     assertTrue(ncl.getEntries().isEmpty());
 353   }
 354
 355   @Test(groups = "Functional")
 356   public void testDelete()
 357   {
 358     assertTrue(false, "todo");
 359   }
 360
 361   @Test(groups = "Functional")
 362   public void testAdd_overlapping()
 363   {
 364     List<Range> ranges = new ArrayList<Range>();
 365     ranges.add(new Range(40, 50));
 366     ranges.add(new Range(20, 30));
 367     NCList<Range> ncl = new NCList<Range>(ranges);
 368     assertEquals(ncl.toString(), "[20-30, 40-50]");
 369     assertTrue(ncl.isValid());
 370
 371     /*
 372      * add range overlapping internally
 373      */
 374     ncl.add(new Range(25, 35));
 375     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
 376     assertTrue(ncl.isValid());
 377
 378     /*
 379      * add range overlapping last range
 380      */
 381     ncl.add(new Range(45, 55));
 382     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
 383     assertTrue(ncl.isValid());
 384
 385     /*
 386      * add range overlapping first range
 387      */
 388     ncl.add(new Range(15, 25));
 389     assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
 390     assertTrue(ncl.isValid());
 391   }
 392 }