test/intervalstore/nonc/IntervalStore0Test.java

   1 /*
   2 BSD 3-Clause License
   3
   4 Copyright (c) 2018, Mungo Carstairs
   5 All rights reserved.
   6
   7 Redistribution and use in source and binary forms, with or without
   8 modification, are permitted provided that the following conditions are met:
   9
  10 * Redistributions of source code must retain the above copyright notice, this
  11   list of conditions and the following disclaimer.
  12
  13 * Redistributions in binary form must reproduce the above copyright notice,
  14   this list of conditions and the following disclaimer in the documentation
  15   and/or other materials provided with the distribution.
  16
  17 * Neither the name of the copyright holder nor the names of its
  18   contributors may be used to endorse or promote products derived from
  19   this software without specific prior written permission.
  20
  21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31 */
  32 package intervalstore.nonc;
  33
  34 import static org.testng.Assert.assertEquals;
  35 import static org.testng.Assert.assertFalse;
  36 import static org.testng.Assert.assertSame;
  37 import static org.testng.Assert.assertTrue;
  38
  39 import java.util.ArrayList;
  40 import java.util.List;
  41 import java.util.Random;
  42
  43 import org.testng.annotations.Test;
  44
  45 import intervalstore.api.IntervalStoreI;
  46
  47 public class IntervalStore0Test
  48 {
  49
  50   public static void main(String[] args)
  51   {
  52     new IntervalStore0Test().defaultTests();
  53   }
  54
  55   private void defaultTests()
  56   {
  57     testAddAndQueryTiming();
  58   }
  59
  60   @Test(groups = "Functional")
  61   public void testFindOverlaps_nonNested()
  62   {
  63     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
  64     SimpleFeature sf1 = add(store, 10, 20);
  65     // same range different description
  66     SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
  67     store.add(sf2);
  68     SimpleFeature sf3 = add(store, 15, 25);
  69     SimpleFeature sf4 = add(store, 20, 35);
  70
  71     assertEquals(store.size(), 4);
  72     List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
  73     assertTrue(overlaps.isEmpty());
  74
  75     overlaps = store.findOverlaps(8, 10);
  76     assertEquals(overlaps.size(), 2);
  77     assertTrue(overlaps.contains(sf1));
  78     assertTrue(overlaps.contains(sf2));
  79
  80     overlaps = store.findOverlaps(12, 16);
  81     assertEquals(overlaps.size(), 3);
  82     assertTrue(overlaps.contains(sf1));
  83     assertTrue(overlaps.contains(sf2));
  84     assertTrue(overlaps.contains(sf3));
  85
  86     overlaps = store.findOverlaps(33, 33);
  87     assertEquals(overlaps.size(), 1);
  88     assertTrue(overlaps.contains(sf4));
  89
  90     /*
  91      * ensure edge cases are covered
  92      */
  93     overlaps = store.findOverlaps(35, 40);
  94     assertEquals(overlaps.size(), 1);
  95     assertTrue(overlaps.contains(sf4));
  96     assertTrue(store.findOverlaps(36, 100).isEmpty());
  97     assertTrue(store.findOverlaps(1, 9).isEmpty());
  98   }
  99
 100   @Test(groups = "Functional")
 101   public void testFindOverlaps_nested()
 102   {
 103     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 104     SimpleFeature sf1 = add(store, 10, 50);
 105     SimpleFeature sf2 = add(store, 10, 40);
 106     SimpleFeature sf3 = add(store, 20, 30);
 107     // feature at same location but different description
 108     SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
 109     store.add(sf4);
 110     SimpleFeature sf5 = add(store, 35, 36);
 111
 112     List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
 113     assertTrue(overlaps.isEmpty());
 114
 115     overlaps = store.findOverlaps(10, 15);
 116     assertEquals(overlaps.size(), 2);
 117     assertTrue(overlaps.contains(sf1));
 118     assertTrue(overlaps.contains(sf2));
 119
 120     overlaps = store.findOverlaps(45, 60);
 121     assertEquals(overlaps.size(), 1);
 122     assertTrue(overlaps.contains(sf1));
 123
 124     overlaps = store.findOverlaps(32, 38);
 125     assertEquals(overlaps.size(), 3);
 126     assertTrue(overlaps.contains(sf1));
 127     assertTrue(overlaps.contains(sf2));
 128     assertTrue(overlaps.contains(sf5));
 129
 130     overlaps = store.findOverlaps(15, 25);
 131     assertEquals(overlaps.size(), 4);
 132     assertTrue(overlaps.contains(sf1));
 133     assertTrue(overlaps.contains(sf2));
 134     assertTrue(overlaps.contains(sf3));
 135     assertTrue(overlaps.contains(sf4));
 136   }
 137
 138   @Test(groups = "Functional")
 139   public void testFindOverlaps_mixed()
 140   {
 141     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 142     SimpleFeature sf1 = add(store, 10, 50);
 143     SimpleFeature sf2 = add(store, 1, 15);
 144     SimpleFeature sf3 = add(store, 20, 30);
 145     SimpleFeature sf4 = add(store, 40, 100);
 146     SimpleFeature sf5 = add(store, 60, 100);
 147     SimpleFeature sf6 = add(store, 70, 70);
 148
 149     List<SimpleFeature> overlaps = store.findOverlaps(200, 200);
 150     assertTrue(overlaps.isEmpty());
 151
 152     overlaps = store.findOverlaps(1, 9);
 153     assertEquals(overlaps.size(), 1);
 154     assertTrue(overlaps.contains(sf2));
 155
 156     overlaps = store.findOverlaps(5, 18);
 157     assertEquals(overlaps.size(), 2);
 158     assertTrue(overlaps.contains(sf1));
 159     assertTrue(overlaps.contains(sf2));
 160
 161     overlaps = store.findOverlaps(30, 40);
 162     assertEquals(overlaps.size(), 3);
 163     assertTrue(overlaps.contains(sf1));
 164     assertTrue(overlaps.contains(sf3));
 165     assertTrue(overlaps.contains(sf4));
 166
 167     overlaps = store.findOverlaps(80, 90);
 168     assertEquals(overlaps.size(), 2);
 169     assertTrue(overlaps.contains(sf4));
 170     assertTrue(overlaps.contains(sf5));
 171
 172     overlaps = store.findOverlaps(68, 70);
 173     assertEquals(overlaps.size(), 3);
 174     assertTrue(overlaps.contains(sf4));
 175     assertTrue(overlaps.contains(sf5));
 176     assertTrue(overlaps.contains(sf6));
 177   }
 178
 179   /**
 180    * Helper method to add a feature with type "desc"
 181    *
 182    * @param store
 183    * @param from
 184    * @param to
 185    * @return
 186    */
 187   SimpleFeature add(IntervalStore0<SimpleFeature> store, int from,
 188           int to)
 189   {
 190     SimpleFeature sf1 = new SimpleFeature(from, to, "desc");
 191     store.add(sf1);
 192     return sf1;
 193   }
 194
 195   @Test(groups = "Functional")
 196   public void testRemove()
 197   {
 198     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 199     SimpleFeature sf1 = add(store, 10, 20);
 200     assertTrue(store.contains(sf1));
 201
 202     try
 203     {
 204       store.remove("what is this?");
 205     } catch (ClassCastException e)
 206     {
 207       // expected;
 208     }
 209     assertFalse(store.remove(null));
 210
 211     /*
 212      * simple deletion
 213      */
 214     assertTrue(store.remove(sf1));
 215     assertTrue(store.isEmpty());
 216
 217     SimpleFeature sf2 = add(store, 0, 0);
 218     SimpleFeature sf2a = add(store, 30, 40);
 219     assertTrue(store.contains(sf2));
 220     assertFalse(store.remove(sf1));
 221     assertTrue(store.remove(sf2));
 222     assertTrue(store.remove(sf2a));
 223     assertTrue(store.isEmpty());
 224
 225     /*
 226      * nested feature deletion
 227      */
 228     SimpleFeature sf4 = add(store, 20, 30);
 229     SimpleFeature sf5 = add(store, 22, 26); // to NCList
 230     SimpleFeature sf6 = add(store, 23, 24); // child of sf5
 231     SimpleFeature sf7 = add(store, 25, 25); // sibling of sf6
 232     SimpleFeature sf8 = add(store, 24, 24); // child of sf6
 233     SimpleFeature sf9 = add(store, 23, 23); // child of sf6
 234     assertEquals(store.size(), 6);
 235
 236     // delete a node with children - they take its place
 237     assertTrue(store.remove(sf6)); // sf8, sf9 should become children of sf5
 238     assertEquals(store.size(), 5);
 239     assertFalse(store.contains(sf6));
 240
 241     // delete a node with no children
 242     assertTrue(store.remove(sf7));
 243     assertEquals(store.size(), 4);
 244     assertFalse(store.contains(sf7));
 245
 246     // delete root of NCList
 247     assertTrue(store.remove(sf5));
 248     assertEquals(store.size(), 3);
 249     assertFalse(store.contains(sf5));
 250
 251     // continue the killing fields
 252     assertTrue(store.remove(sf4));
 253     assertEquals(store.size(), 2);
 254     assertFalse(store.contains(sf4));
 255
 256     assertTrue(store.remove(sf9));
 257     assertEquals(store.size(), 1);
 258     assertFalse(store.contains(sf9));
 259
 260     assertTrue(store.remove(sf8));
 261     assertTrue(store.isEmpty());
 262   }
 263
 264   @Test(groups = "Functional")
 265   public void testAdd()
 266   {
 267     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 268
 269     assertFalse(store.add(null));
 270
 271     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 272     SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
 273
 274     assertTrue(store.add(sf1));
 275     assertEquals(store.size(), 1);
 276
 277     /*
 278      * contains should return true for the same or an identical feature
 279      */
 280     assertTrue(store.contains(sf1));
 281     assertTrue(store.contains(sf2));
 282
 283     /*
 284      * duplicates are accepted
 285      */
 286     assertTrue(store.add(sf2));
 287     assertEquals(store.size(), 2);
 288
 289     SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath");
 290     assertTrue(store.add(sf3));
 291     assertEquals(store.size(), 3);
 292   }
 293
 294   @Test(groups = "Functional")
 295   public void testAdd_noDuplicates()
 296   {
 297     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 298
 299     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 300     SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
 301     assertTrue(sf1.equals(sf2));
 302     assertTrue(store.add(sf1));
 303     assertEquals(store.size(), 1);
 304     assertFalse(store.add(sf2, false));
 305     assertEquals(store.size(), 1);
 306     assertTrue(store.contains(sf1));
 307     assertTrue(store.contains(sf2)); // because sf1.equals(sf2) !
 308   }
 309
 310   @Test(groups = "Functional")
 311   public void testIsEmpty()
 312   {
 313     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 314     assertTrue(store.isEmpty());
 315     assertEquals(store.size(), 0);
 316
 317     /*
 318      * non-nested feature
 319      */
 320     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 321     store.add(sf1);
 322     assertFalse(store.isEmpty());
 323     assertEquals(store.size(), 1);
 324     store.remove(sf1);
 325     assertTrue(store.isEmpty());
 326     assertEquals(store.size(), 0);
 327
 328     sf1 = new SimpleFeature(0, 0, "Cath");
 329     store.add(sf1);
 330     assertFalse(store.isEmpty());
 331     assertEquals(store.size(), 1);
 332     store.remove(sf1);
 333     assertTrue(store.isEmpty());
 334     assertEquals(store.size(), 0);
 335
 336     /*
 337      * sf2, sf3 added as nested features
 338      */
 339     sf1 = new SimpleFeature(19, 49, "Cath");
 340     SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath");
 341     SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath");
 342     store.add(sf1);
 343     assertEquals(store.size(), 1);
 344     store.add(sf2);
 345     assertEquals(store.size(), 2);
 346     store.add(sf3);
 347     assertEquals(store.size(), 3);
 348     assertTrue(store.remove(sf1));
 349     assertEquals(store.size(), 2);
 350
 351     assertFalse(store.isEmpty());
 352     assertTrue(store.remove(sf2));
 353     assertEquals(store.size(), 1);
 354     assertFalse(store.isEmpty());
 355     assertTrue(store.remove(sf3));
 356     assertEquals(store.size(), 0);
 357     assertTrue(store.isEmpty()); // all gone
 358   }
 359
 360   @Test(groups = "Functional")
 361   public void testRemove_readd()
 362   {
 363     /*
 364      * add a feature and a nested feature
 365      */
 366     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 367     SimpleFeature sf1 = add(store, 10, 20);
 368     // sf2 is nested in sf1 so will be stored in nestedFeatures
 369     SimpleFeature sf2 = add(store, 12, 14);
 370     assertEquals(store.size(), 2);
 371     assertTrue(store.contains(sf1));
 372     assertTrue(store.contains(sf2));
 373
 374     /*
 375      * delete the first feature
 376      */
 377     assertTrue(store.remove(sf1));
 378     assertFalse(store.contains(sf1));
 379     assertTrue(store.contains(sf2));
 380
 381     /*
 382      * re-add the 'nested' feature; it is now duplicated
 383      */
 384     store.add(sf2);
 385     assertEquals(store.size(), 2);
 386     assertTrue(store.contains(sf2));
 387   }
 388
 389   @Test(groups = "Functional")
 390   public void testContains()
 391   {
 392     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 393     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 394     SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam");
 395
 396     store.add(sf1);
 397     assertTrue(store.contains(sf1));
 398     assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature
 399     assertFalse(store.contains(sf2)); // different description
 400
 401     /*
 402      * add a nested feature
 403      */
 404     SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath");
 405     store.add(sf3);
 406     assertTrue(store.contains(sf3));
 407     assertTrue(store.contains(new SimpleFeature(sf3)));
 408
 409     /*
 410      * delete the outer (enclosing, non-nested) feature
 411      */
 412     store.remove(sf1);
 413     assertFalse(store.contains(sf1));
 414     assertTrue(store.contains(sf3));
 415
 416     assertFalse(store.contains(null));
 417     try
 418     {
 419       assertFalse(store.contains("junk"));
 420     } catch (ClassCastException e)
 421     {
 422       // expected;
 423     }
 424   }
 425
 426   @Test(groups = "Functional")
 427   public void testFindOverlaps_resultsArg_mixed()
 428   {
 429     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 430     SimpleFeature sf1 = add(store, 10, 50);
 431     SimpleFeature sf2 = add(store, 1, 15);
 432     SimpleFeature sf3 = add(store, 20, 30);
 433     SimpleFeature sf4 = add(store, 40, 100);
 434     SimpleFeature sf5 = add(store, 60, 100);
 435     SimpleFeature sf6 = add(store, 70, 70);
 436
 437     List<SimpleFeature> overlaps = new ArrayList<>();
 438     List<SimpleFeature> overlaps2 = store.findOverlaps(200, 200, overlaps);
 439     assertSame(overlaps, overlaps2);
 440     assertTrue(overlaps.isEmpty());
 441
 442     overlaps.clear();
 443     store.findOverlaps(1, 9, overlaps);
 444     assertEquals(overlaps.size(), 1);
 445     assertTrue(overlaps.contains(sf2));
 446
 447     overlaps.clear();
 448     store.findOverlaps(5, 18, overlaps);
 449     assertEquals(overlaps.size(), 2);
 450     assertTrue(overlaps.contains(sf1));
 451     assertTrue(overlaps.contains(sf2));
 452
 453     overlaps.clear();
 454     store.findOverlaps(30, 40, overlaps);
 455     assertEquals(overlaps.size(), 3);
 456     assertTrue(overlaps.contains(sf1));
 457     assertTrue(overlaps.contains(sf3));
 458     assertTrue(overlaps.contains(sf4));
 459
 460     overlaps.clear();
 461     store.findOverlaps(80, 90, overlaps);
 462     assertEquals(overlaps.size(), 2);
 463     assertTrue(overlaps.contains(sf4));
 464     assertTrue(overlaps.contains(sf5));
 465
 466     overlaps.clear();
 467     store.findOverlaps(68, 70, overlaps);
 468     assertEquals(overlaps.size(), 3);
 469     assertTrue(overlaps.contains(sf4));
 470     assertTrue(overlaps.contains(sf5));
 471     assertTrue(overlaps.contains(sf6));
 472
 473     /*
 474      * and without clearing the list first
 475      * note that sf4 is included twice, as an
 476      * overlap of 68-70 and also of 30-40
 477      */
 478     store.findOverlaps(30, 40, overlaps);
 479     assertEquals(overlaps.size(), 6);
 480     assertTrue(overlaps.contains(sf1));
 481     assertTrue(overlaps.contains(sf3));
 482     assertTrue(overlaps.contains(sf4));
 483     assertTrue(overlaps.contains(sf5));
 484     assertTrue(overlaps.contains(sf6));
 485     assertSame(sf4, overlaps.get(2)); // not (0)
 486     assertSame(sf4, overlaps.get(3)); // not (4)
 487   }
 488
 489   @Test(groups = "Functional")
 490   public void testFindOverlaps_resultsArg_nested()
 491   {
 492     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 493     SimpleFeature sf1 = add(store, 10, 50);
 494     SimpleFeature sf2 = add(store, 10, 40);
 495     SimpleFeature sf3 = add(store, 20, 30);
 496     // feature at same location but different description
 497     SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
 498     store.add(sf4);
 499     SimpleFeature sf5 = add(store, 35, 36);
 500
 501     List<SimpleFeature> overlaps = new ArrayList<>();
 502     store.findOverlaps(1, 9, overlaps);
 503     assertTrue(overlaps.isEmpty());
 504
 505     store.findOverlaps(10, 15, overlaps);
 506     assertEquals(overlaps.size(), 2);
 507     assertTrue(overlaps.contains(sf1));
 508     assertTrue(overlaps.contains(sf2));
 509
 510     overlaps.clear();
 511     store.findOverlaps(45, 60, overlaps);
 512     assertEquals(overlaps.size(), 1);
 513     assertTrue(overlaps.contains(sf1));
 514
 515     overlaps.clear();
 516     store.findOverlaps(32, 38, overlaps);
 517     assertEquals(overlaps.size(), 3);
 518     assertTrue(overlaps.contains(sf1));
 519     assertTrue(overlaps.contains(sf2));
 520     assertTrue(overlaps.contains(sf5));
 521
 522     overlaps.clear();
 523     store.findOverlaps(15, 25, overlaps);
 524     assertEquals(overlaps.size(), 4);
 525     assertTrue(overlaps.contains(sf1));
 526     assertTrue(overlaps.contains(sf2));
 527     assertTrue(overlaps.contains(sf3));
 528     assertTrue(overlaps.contains(sf4));
 529   }
 530
 531   @Test(groups = "Functional")
 532   public void testFindOverlaps_resultsArg_nonNested()
 533   {
 534     IntervalStore0<SimpleFeature> store = new IntervalStore0<>();
 535     SimpleFeature sf1 = add(store, 10, 20);
 536     // same range different description
 537     SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
 538     store.add(sf2);
 539     SimpleFeature sf3 = add(store, 15, 25);
 540     SimpleFeature sf4 = add(store, 20, 35);
 541
 542     assertEquals(store.size(), 4);
 543     List<SimpleFeature> overlaps = new ArrayList<>();
 544     store.findOverlaps(1, 9, overlaps);
 545     assertTrue(overlaps.isEmpty());
 546
 547     store.findOverlaps(8, 10, overlaps);
 548     assertEquals(overlaps.size(), 2);
 549     assertTrue(overlaps.contains(sf1));
 550     assertTrue(overlaps.contains(sf2));
 551
 552     overlaps.clear();
 553     store.findOverlaps(12, 16, overlaps);
 554     assertEquals(overlaps.size(), 3);
 555     assertTrue(overlaps.contains(sf1));
 556     assertTrue(overlaps.contains(sf2));
 557     assertTrue(overlaps.contains(sf3));
 558
 559     overlaps.clear();
 560     store.findOverlaps(33, 33, overlaps);
 561     assertEquals(overlaps.size(), 1);
 562     assertTrue(overlaps.contains(sf4));
 563
 564     /*
 565      * ensure edge cases are covered
 566      */
 567     overlaps.clear();
 568     store.findOverlaps(35, 40, overlaps);
 569     assertEquals(overlaps.size(), 1);
 570     assertTrue(overlaps.contains(sf4));
 571
 572     overlaps.clear();
 573     assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty());
 574     assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty());
 575   }
 576
 577   /**
 578    * Compares alternative IntervalStoreI implementations for time to add an
 579    * interval then query, at a range of different scales of N (the number of
 580    * stored features).
 581    */
 582   @Test(groups = "Timing", enabled = false)
 583   public void testAddAndQueryTiming()
 584   {
 585     testAddAndQuery(1, 20000000, 10, 20);
 586     testAddAndQuery(0, 0, 10, 20);
 587
 588     testAddAndQuery(1, 20000000, 10, 200);
 589     testAddAndQuery(0, 0, 10, 200);
 590
 591     testAddAndQuery(1, 20000000, 10, 2000);
 592     testAddAndQuery(0, 0, 10, 2000);
 593
 594     testAddAndQuery(1, 20000000, -2000000, 2000000);
 595     testAddAndQuery(0, 0, -2000000, 2000000);
 596   }
 597
 598   private void testAddAndQuery(int addstart, int addend, int start, int end)
 599   {
 600     System.out.println("\nadd: " + addstart + " " + addend + " query: "
 601             + start + "  " + end);
 602     StringBuffer sb = new StringBuffer();
 603     IntervalStoreI<SimpleFeature> store;
 604     store = new IntervalStore0<>();
 605     testAddAndQueryTiming(store, false, sb, addstart, addend, start, end);
 606
 607     store = new intervalstore.impl.IntervalStore<>();
 608     testAddAndQueryTiming(store, true, sb, addstart, addend, start, end);
 609
 610     System.out.println(sb);
 611   }
 612
 613   /**
 614    * Populates the store with intervals, then logs the time taken to add an
 615    * interval then query, at a range of different scales of N (the number of
 616    * stored features).
 617    *
 618    * @param store
 619    */
 620   private void testAddAndQueryTiming(IntervalStoreI<SimpleFeature> store,
 621           boolean isNCList, StringBuffer sb, int addstart, int addend,
 622           int start, int end)
 623   {
 624     final int seqlen = 100000; // e.g. length of gene sequence
 625     final int repeats = 20;
 626     final int K = 1000;
 627     final int warmups = 5;
 628     final int[] scales = new int[] { 10 * K, 100 * K, 1000 * K };// , 10000 * K
 629                                                        // };
 630
 631     Random r = new Random(732); // fixed seed = repeatable test
 632     int counter = 0; // to ensure a distinct description for each feature
 633
 634     // System.out.println("Scale\titeration\tmicrosecs");
 635
 636     for (int scale : scales)
 637     {
 638       /*
 639        * add 'scale' features to the store
 640        */
 641       long ntimeLoad = System.nanoTime();
 642       for (int i = 0; i < scale; i++)
 643       {
 644         SimpleFeature sf;
 645         sf = makeFeature(seqlen, r, counter);
 646         counter++;
 647         store.add(sf);
 648       }
 649       if (!isNCList)
 650       {
 651         ((intervalstore.nonc.IntervalStore0<SimpleFeature>) store)
 652                 .revalidate();
 653       }
 654       String line = "time to load " + (isNCList ? "NClist " : "NCArray ")
 655               + (System.nanoTime() - ntimeLoad) / K / K + " ms scale "
 656               + scale;
 657       // System.out.println(line);
 658       sb.append(line);
 659
 660       /*
 661        * do "add then query" and log the time taken for the query
 662        * we ignore the first 5 repetitions as 'warmups'
 663        */
 664       long total = 0L;
 665       for (int i = 0; i < repeats + warmups; i++)
 666       {
 667         SimpleFeature sf;
 668         if (addstart == 0)
 669         {
 670           sf = makeFeature(seqlen, r, counter++);
 671         }
 672         else
 673         {
 674           sf = new SimpleFeature(addstart, addend, "desc" + counter++);
 675         }
 676         System.gc();
 677         long t1 = System.nanoTime();
 678         store.add(sf);
 679         store.findOverlaps(start, end);
 680         long elapsed = System.nanoTime() - t1;
 681         if (i >= warmups)
 682         {
 683           total += elapsed;
 684           // System.out.println(
 685           // String.format("%d\t%d\t%d", scale, i - warmups,
 686           // elapsed / K));
 687         }
 688       }
 689       sb.append(
 690               " add+query "
 691                       + (isNCList ? "NCList " : "NCArray ")
 692                       + (total / (K * repeats)) + " microseconds\n");
 693     }
 694   }
 695
 696   SimpleFeature makeFeature(final int seqlen, Random r, int counter)
 697   {
 698     int i1 = r.nextInt(seqlen);
 699     int i2 = r.nextInt(seqlen);
 700     int from = Math.min(i1, i2);
 701     int to = Math.max(i1, i2);
 702     SimpleFeature sf = new SimpleFeature(from, to, "desc" + counter);
 703     return sf;
 704   }
 705 }