test/intervalstore/nonc/IntervalStoreTest.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 IntervalStoreTest
  48 {
  49
  50   public static void main(String[] args)
  51   {
  52     new IntervalStoreTest().defaultTests();
  53   }
  54
  55   private void defaultTests()
  56   {
  57     testAddAndQueryTiming();
  58   }
  59
  60   @Test(groups = "Functional")
  61   public void testFindOverlaps_nonNested()
  62   {
  63     IntervalStore<SimpleFeature> store = new IntervalStore<>();
  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     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 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     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 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(IntervalStore<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     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 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   /**
 265    * A helper method to test whether a list contains a specific object (by
 266    * object identity, not equality test as used by List.contains())
 267    *
 268    * @param list
 269    * @param o
 270    * @return
 271    */
 272   private static boolean containsObject(List<? extends Object> list,
 273           Object o)
 274   {
 275     for (Object i : list)
 276     {
 277       if (i == o)
 278       {
 279         return true;
 280       }
 281     }
 282     return false;
 283   }
 284
 285   @Test(groups = "Functional")
 286   public void testAdd()
 287   {
 288     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 289
 290     assertFalse(store.add(null));
 291
 292     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 293     SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
 294
 295     assertTrue(store.add(sf1));
 296     assertEquals(store.size(), 1);
 297
 298     /*
 299      * contains should return true for the same or an identical feature
 300      */
 301     assertTrue(store.contains(sf1));
 302     assertTrue(store.contains(sf2));
 303
 304     /*
 305      * duplicates are accepted
 306      */
 307     assertTrue(store.add(sf2));
 308     assertEquals(store.size(), 2);
 309
 310     SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath");
 311     assertTrue(store.add(sf3));
 312     assertEquals(store.size(), 3);
 313   }
 314
 315   @Test(groups = "Functional")
 316   public void testAdd_noDuplicates()
 317   {
 318     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 319
 320     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 321     SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
 322     assertTrue(sf1.equals(sf2));
 323     assertTrue(store.add(sf1));
 324     assertEquals(store.size(), 1);
 325     assertFalse(store.add(sf2, false));
 326     assertEquals(store.size(), 1);
 327     assertTrue(store.contains(sf1));
 328     assertTrue(store.contains(sf2)); // because sf1.equals(sf2) !
 329   }
 330
 331   @Test(groups = "Functional")
 332   public void testIsEmpty()
 333   {
 334     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 335     assertTrue(store.isEmpty());
 336     assertEquals(store.size(), 0);
 337
 338     /*
 339      * non-nested feature
 340      */
 341     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 342     store.add(sf1);
 343     assertFalse(store.isEmpty());
 344     assertEquals(store.size(), 1);
 345     store.remove(sf1);
 346     assertTrue(store.isEmpty());
 347     assertEquals(store.size(), 0);
 348
 349     sf1 = new SimpleFeature(0, 0, "Cath");
 350     store.add(sf1);
 351     assertFalse(store.isEmpty());
 352     assertEquals(store.size(), 1);
 353     store.remove(sf1);
 354     assertTrue(store.isEmpty());
 355     assertEquals(store.size(), 0);
 356
 357     /*
 358      * sf2, sf3 added as nested features
 359      */
 360     sf1 = new SimpleFeature(19, 49, "Cath");
 361     SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath");
 362     SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath");
 363     store.add(sf1);
 364     assertEquals(store.size(), 1);
 365     store.add(sf2);
 366     assertEquals(store.size(), 2);
 367     store.add(sf3);
 368     assertEquals(store.size(), 3);
 369     assertTrue(store.remove(sf1));
 370     assertEquals(store.size(), 2);
 371
 372     assertFalse(store.isEmpty());
 373     assertTrue(store.remove(sf2));
 374     assertEquals(store.size(), 1);
 375     assertFalse(store.isEmpty());
 376     assertTrue(store.remove(sf3));
 377     assertEquals(store.size(), 0);
 378     assertTrue(store.isEmpty()); // all gone
 379   }
 380
 381   @Test(groups = "Functional")
 382   public void testRemove_readd()
 383   {
 384     /*
 385      * add a feature and a nested feature
 386      */
 387     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 388     SimpleFeature sf1 = add(store, 10, 20);
 389     // sf2 is nested in sf1 so will be stored in nestedFeatures
 390     SimpleFeature sf2 = add(store, 12, 14);
 391     assertEquals(store.size(), 2);
 392     assertTrue(store.contains(sf1));
 393     assertTrue(store.contains(sf2));
 394
 395     /*
 396      * delete the first feature
 397      */
 398     assertTrue(store.remove(sf1));
 399     assertFalse(store.contains(sf1));
 400     assertTrue(store.contains(sf2));
 401
 402     /*
 403      * re-add the 'nested' feature; it is now duplicated
 404      */
 405     store.add(sf2);
 406     assertEquals(store.size(), 2);
 407     assertTrue(store.contains(sf2));
 408   }
 409
 410   @Test(groups = "Functional")
 411   public void testContains()
 412   {
 413     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 414     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 415     SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam");
 416
 417     store.add(sf1);
 418     assertTrue(store.contains(sf1));
 419     assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature
 420     assertFalse(store.contains(sf2)); // different description
 421
 422     /*
 423      * add a nested feature
 424      */
 425     SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath");
 426     store.add(sf3);
 427     assertTrue(store.contains(sf3));
 428     assertTrue(store.contains(new SimpleFeature(sf3)));
 429
 430     /*
 431      * delete the outer (enclosing, non-nested) feature
 432      */
 433     store.remove(sf1);
 434     assertFalse(store.contains(sf1));
 435     assertTrue(store.contains(sf3));
 436
 437     assertFalse(store.contains(null));
 438     try
 439     {
 440       assertFalse(store.contains("junk"));
 441     } catch (ClassCastException e)
 442     {
 443       // expected;
 444     }
 445   }
 446
 447   @Test(groups = "Functional")
 448   public void testFindOverlaps_resultsArg_mixed()
 449   {
 450     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 451     SimpleFeature sf1 = add(store, 10, 50);
 452     SimpleFeature sf2 = add(store, 1, 15);
 453     SimpleFeature sf3 = add(store, 20, 30);
 454     SimpleFeature sf4 = add(store, 40, 100);
 455     SimpleFeature sf5 = add(store, 60, 100);
 456     SimpleFeature sf6 = add(store, 70, 70);
 457
 458     List<SimpleFeature> overlaps = new ArrayList<>();
 459     List<SimpleFeature> overlaps2 = store.findOverlaps(200, 200, overlaps);
 460     assertSame(overlaps, overlaps2);
 461     assertTrue(overlaps.isEmpty());
 462
 463     overlaps.clear();
 464     store.findOverlaps(1, 9, overlaps);
 465     assertEquals(overlaps.size(), 1);
 466     assertTrue(overlaps.contains(sf2));
 467
 468     overlaps.clear();
 469     store.findOverlaps(5, 18, overlaps);
 470     assertEquals(overlaps.size(), 2);
 471     assertTrue(overlaps.contains(sf1));
 472     assertTrue(overlaps.contains(sf2));
 473
 474     overlaps.clear();
 475     store.findOverlaps(30, 40, overlaps);
 476     assertEquals(overlaps.size(), 3);
 477     assertTrue(overlaps.contains(sf1));
 478     assertTrue(overlaps.contains(sf3));
 479     assertTrue(overlaps.contains(sf4));
 480
 481     overlaps.clear();
 482     store.findOverlaps(80, 90, overlaps);
 483     assertEquals(overlaps.size(), 2);
 484     assertTrue(overlaps.contains(sf4));
 485     assertTrue(overlaps.contains(sf5));
 486
 487     overlaps.clear();
 488     store.findOverlaps(68, 70, overlaps);
 489     assertEquals(overlaps.size(), 3);
 490     assertTrue(overlaps.contains(sf4));
 491     assertTrue(overlaps.contains(sf5));
 492     assertTrue(overlaps.contains(sf6));
 493
 494     /*
 495      * and without clearing the list first
 496      * note that sf4 is included twice, as an
 497      * overlap of 68-70 and also of 30-40
 498      */
 499     store.findOverlaps(30, 40, overlaps);
 500     assertEquals(overlaps.size(), 6);
 501     assertTrue(overlaps.contains(sf1));
 502     assertTrue(overlaps.contains(sf3));
 503     assertTrue(overlaps.contains(sf4));
 504     assertTrue(overlaps.contains(sf5));
 505     assertTrue(overlaps.contains(sf6));
 506     assertSame(sf4, overlaps.get(0));
 507     assertSame(sf4, overlaps.get(4));
 508   }
 509
 510   @Test(groups = "Functional")
 511   public void testFindOverlaps_resultsArg_nested()
 512   {
 513     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 514     SimpleFeature sf1 = add(store, 10, 50);
 515     SimpleFeature sf2 = add(store, 10, 40);
 516     SimpleFeature sf3 = add(store, 20, 30);
 517     // feature at same location but different description
 518     SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
 519     store.add(sf4);
 520     SimpleFeature sf5 = add(store, 35, 36);
 521
 522     List<SimpleFeature> overlaps = new ArrayList<>();
 523     store.findOverlaps(1, 9, overlaps);
 524     assertTrue(overlaps.isEmpty());
 525
 526     store.findOverlaps(10, 15, overlaps);
 527     assertEquals(overlaps.size(), 2);
 528     assertTrue(overlaps.contains(sf1));
 529     assertTrue(overlaps.contains(sf2));
 530
 531     overlaps.clear();
 532     store.findOverlaps(45, 60, overlaps);
 533     assertEquals(overlaps.size(), 1);
 534     assertTrue(overlaps.contains(sf1));
 535
 536     overlaps.clear();
 537     store.findOverlaps(32, 38, overlaps);
 538     assertEquals(overlaps.size(), 3);
 539     assertTrue(overlaps.contains(sf1));
 540     assertTrue(overlaps.contains(sf2));
 541     assertTrue(overlaps.contains(sf5));
 542
 543     overlaps.clear();
 544     store.findOverlaps(15, 25, overlaps);
 545     assertEquals(overlaps.size(), 4);
 546     assertTrue(overlaps.contains(sf1));
 547     assertTrue(overlaps.contains(sf2));
 548     assertTrue(overlaps.contains(sf3));
 549     assertTrue(overlaps.contains(sf4));
 550   }
 551
 552   @Test(groups = "Functional")
 553   public void testFindOverlaps_resultsArg_nonNested()
 554   {
 555     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 556     SimpleFeature sf1 = add(store, 10, 20);
 557     // same range different description
 558     SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
 559     store.add(sf2);
 560     SimpleFeature sf3 = add(store, 15, 25);
 561     SimpleFeature sf4 = add(store, 20, 35);
 562
 563     assertEquals(store.size(), 4);
 564     List<SimpleFeature> overlaps = new ArrayList<>();
 565     store.findOverlaps(1, 9, overlaps);
 566     assertTrue(overlaps.isEmpty());
 567
 568     store.findOverlaps(8, 10, overlaps);
 569     assertEquals(overlaps.size(), 2);
 570     assertTrue(overlaps.contains(sf1));
 571     assertTrue(overlaps.contains(sf2));
 572
 573     overlaps.clear();
 574     store.findOverlaps(12, 16, overlaps);
 575     assertEquals(overlaps.size(), 3);
 576     assertTrue(overlaps.contains(sf1));
 577     assertTrue(overlaps.contains(sf2));
 578     assertTrue(overlaps.contains(sf3));
 579
 580     overlaps.clear();
 581     store.findOverlaps(33, 33, overlaps);
 582     assertEquals(overlaps.size(), 1);
 583     assertTrue(overlaps.contains(sf4));
 584
 585     /*
 586      * ensure edge cases are covered
 587      */
 588     overlaps.clear();
 589     store.findOverlaps(35, 40, overlaps);
 590     assertEquals(overlaps.size(), 1);
 591     assertTrue(overlaps.contains(sf4));
 592
 593     overlaps.clear();
 594     assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty());
 595     assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty());
 596   }
 597
 598   /**
 599    * Compares alternative IntervalStoreI implementations for time to add an
 600    * interval then query, at a range of different scales of N (the number of
 601    * stored features).
 602    */
 603   @Test(groups = "Timing")
 604   public void testAddAndQueryTiming()
 605   {
 606     testAddAndQuery(1, 20000000, 10, 20);
 607     testAddAndQuery(0, 0, 10, 20);
 608
 609     testAddAndQuery(1, 20000000, 10, 200);
 610     testAddAndQuery(0, 0, 10, 200);
 611
 612     testAddAndQuery(1, 20000000, 10, 2000);
 613     testAddAndQuery(0, 0, 10, 2000);
 614
 615     testAddAndQuery(1, 20000000, -2000000, 2000000);
 616     testAddAndQuery(0, 0, -2000000, 2000000);
 617   }
 618
 619   private void testAddAndQuery(int addstart, int addend, int start, int end)
 620   {
 621     System.out.println("\nadd: " + addstart + " " + addend + " query: "
 622             + start + "  " + end);
 623     StringBuffer sb = new StringBuffer();
 624     IntervalStoreI<SimpleFeature> store;
 625     store = new intervalstore.nonc.IntervalStore<>();
 626     testAddAndQueryTiming(store, false, sb, addstart, addend, start, end);
 627
 628     store = new intervalstore.impl.IntervalStore<>();
 629     testAddAndQueryTiming(store, true, sb, addstart, addend, start, end);
 630
 631     System.out.println(sb);
 632   }
 633
 634   /**
 635    * Populates the store with intervals, then logs the time taken to add an
 636    * interval then query, at a range of different scales of N (the number of
 637    * stored features).
 638    *
 639    * @param store
 640    */
 641   private void testAddAndQueryTiming(IntervalStoreI<SimpleFeature> store,
 642           boolean isNCList, StringBuffer sb, int addstart, int addend,
 643           int start, int end)
 644   {
 645     final int seqlen = 100000; // e.g. length of gene sequence
 646     final int repeats = 20;
 647     final int K = 1000;
 648     final int warmups = 5;
 649     final int[] scales = new int[] { 10 * K, 100 * K, 1000 * K };// , 10000 * K
 650                                                        // };
 651
 652     Random r = new Random(732); // fixed seed = repeatable test
 653     int counter = 0; // to ensure a distinct description for each feature
 654
 655     // System.out.println("Scale\titeration\tmicrosecs");
 656
 657     for (int scale : scales)
 658     {
 659       /*
 660        * add 'scale' features to the store
 661        */
 662       long ntimeLoad = System.nanoTime();
 663       for (int i = 0; i < scale; i++)
 664       {
 665         SimpleFeature sf;
 666         sf = makeFeature(seqlen, r, counter);
 667         counter++;
 668         store.add(sf);
 669       }
 670       if (!isNCList)
 671       {
 672         ((intervalstore.nonc.IntervalStore) store).revalidate();
 673       }
 674       String line = "time to load " + (isNCList ? "NClist " : "NCArray ")
 675               + (System.nanoTime() - ntimeLoad) / K / K + " ms scale "
 676               + scale;
 677       // System.out.println(line);
 678       sb.append(line);
 679
 680       /*
 681        * do "add then query" and log the time taken for the query
 682        * we ignore the first 5 repetitions as 'warmups'
 683        */
 684       long total = 0L;
 685       for (int i = 0; i < repeats + warmups; i++)
 686       {
 687         SimpleFeature sf;
 688         if (addstart == 0)
 689         {
 690           sf = makeFeature(seqlen, r, counter++);
 691         }
 692         else
 693         {
 694           sf = new SimpleFeature(addstart, addend, "desc" + counter++);
 695         }
 696         System.gc();
 697         long t1 = System.nanoTime();
 698         store.add(sf);
 699         store.findOverlaps(start, end);
 700         long elapsed = System.nanoTime() - t1;
 701         if (i >= warmups)
 702         {
 703           total += elapsed;
 704           // System.out.println(
 705           // String.format("%d\t%d\t%d", scale, i - warmups,
 706           // elapsed / K));
 707         }
 708       }
 709       sb.append(
 710               " add+query "
 711                       + (isNCList ? "NCList " : "NCArray ")
 712                       + (total / (K * repeats)) + " microseconds\n");
 713     }
 714   }
 715
 716   SimpleFeature makeFeature(final int seqlen, Random r, int counter)
 717   {
 718     int i1 = r.nextInt(seqlen);
 719     int i2 = r.nextInt(seqlen);
 720     int from = Math.min(i1, i2);
 721     int to = Math.max(i1, i2);
 722     SimpleFeature sf = new SimpleFeature(from, to, "desc" + counter);
 723     return sf;
 724   }
 725 }