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   @Test(groups = "Functional")
  50   public void testFindOverlaps_nonNested()
  51   {
  52     IntervalStore<SimpleFeature> store = new IntervalStore<>();
  53     SimpleFeature sf1 = add(store, 10, 20);
  54     // same range different description
  55     SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
  56     store.add(sf2);
  57     SimpleFeature sf3 = add(store, 15, 25);
  58     SimpleFeature sf4 = add(store, 20, 35);
  59
  60     assertEquals(store.size(), 4);
  61     List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
  62     assertTrue(overlaps.isEmpty());
  63
  64     overlaps = store.findOverlaps(8, 10);
  65     assertEquals(overlaps.size(), 2);
  66     assertTrue(overlaps.contains(sf1));
  67     assertTrue(overlaps.contains(sf2));
  68
  69     overlaps = store.findOverlaps(12, 16);
  70     assertEquals(overlaps.size(), 3);
  71     assertTrue(overlaps.contains(sf1));
  72     assertTrue(overlaps.contains(sf2));
  73     assertTrue(overlaps.contains(sf3));
  74
  75     overlaps = store.findOverlaps(33, 33);
  76     assertEquals(overlaps.size(), 1);
  77     assertTrue(overlaps.contains(sf4));
  78
  79     /*
  80      * ensure edge cases are covered
  81      */
  82     overlaps = store.findOverlaps(35, 40);
  83     assertEquals(overlaps.size(), 1);
  84     assertTrue(overlaps.contains(sf4));
  85     assertTrue(store.findOverlaps(36, 100).isEmpty());
  86     assertTrue(store.findOverlaps(1, 9).isEmpty());
  87   }
  88
  89   @Test(groups = "Functional")
  90   public void testFindOverlaps_nested()
  91   {
  92     IntervalStore<SimpleFeature> store = new IntervalStore<>();
  93     SimpleFeature sf1 = add(store, 10, 50);
  94     SimpleFeature sf2 = add(store, 10, 40);
  95     SimpleFeature sf3 = add(store, 20, 30);
  96     // feature at same location but different description
  97     SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
  98     store.add(sf4);
  99     SimpleFeature sf5 = add(store, 35, 36);
 100
 101     List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
 102     assertTrue(overlaps.isEmpty());
 103
 104     overlaps = store.findOverlaps(10, 15);
 105     assertEquals(overlaps.size(), 2);
 106     assertTrue(overlaps.contains(sf1));
 107     assertTrue(overlaps.contains(sf2));
 108
 109     overlaps = store.findOverlaps(45, 60);
 110     assertEquals(overlaps.size(), 1);
 111     assertTrue(overlaps.contains(sf1));
 112
 113     overlaps = store.findOverlaps(32, 38);
 114     assertEquals(overlaps.size(), 3);
 115     assertTrue(overlaps.contains(sf1));
 116     assertTrue(overlaps.contains(sf2));
 117     assertTrue(overlaps.contains(sf5));
 118
 119     overlaps = store.findOverlaps(15, 25);
 120     assertEquals(overlaps.size(), 4);
 121     assertTrue(overlaps.contains(sf1));
 122     assertTrue(overlaps.contains(sf2));
 123     assertTrue(overlaps.contains(sf3));
 124     assertTrue(overlaps.contains(sf4));
 125   }
 126
 127   @Test(groups = "Functional")
 128   public void testFindOverlaps_mixed()
 129   {
 130     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 131     SimpleFeature sf1 = add(store, 10, 50);
 132     SimpleFeature sf2 = add(store, 1, 15);
 133     SimpleFeature sf3 = add(store, 20, 30);
 134     SimpleFeature sf4 = add(store, 40, 100);
 135     SimpleFeature sf5 = add(store, 60, 100);
 136     SimpleFeature sf6 = add(store, 70, 70);
 137
 138     List<SimpleFeature> overlaps = store.findOverlaps(200, 200);
 139     assertTrue(overlaps.isEmpty());
 140
 141     overlaps = store.findOverlaps(1, 9);
 142     assertEquals(overlaps.size(), 1);
 143     assertTrue(overlaps.contains(sf2));
 144
 145     overlaps = store.findOverlaps(5, 18);
 146     assertEquals(overlaps.size(), 2);
 147     assertTrue(overlaps.contains(sf1));
 148     assertTrue(overlaps.contains(sf2));
 149
 150     overlaps = store.findOverlaps(30, 40);
 151     assertEquals(overlaps.size(), 3);
 152     assertTrue(overlaps.contains(sf1));
 153     assertTrue(overlaps.contains(sf3));
 154     assertTrue(overlaps.contains(sf4));
 155
 156     overlaps = store.findOverlaps(80, 90);
 157     assertEquals(overlaps.size(), 2);
 158     assertTrue(overlaps.contains(sf4));
 159     assertTrue(overlaps.contains(sf5));
 160
 161     overlaps = store.findOverlaps(68, 70);
 162     assertEquals(overlaps.size(), 3);
 163     assertTrue(overlaps.contains(sf4));
 164     assertTrue(overlaps.contains(sf5));
 165     assertTrue(overlaps.contains(sf6));
 166   }
 167
 168   /**
 169    * Helper method to add a feature with type "desc"
 170    *
 171    * @param store
 172    * @param from
 173    * @param to
 174    * @return
 175    */
 176   SimpleFeature add(IntervalStore<SimpleFeature> store, int from,
 177           int to)
 178   {
 179     SimpleFeature sf1 = new SimpleFeature(from, to, "desc");
 180     store.add(sf1);
 181     return sf1;
 182   }
 183
 184   @Test(groups = "Functional")
 185   public void testRemove()
 186   {
 187     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 188     SimpleFeature sf1 = add(store, 10, 20);
 189     assertTrue(store.contains(sf1));
 190
 191     try
 192     {
 193       store.remove("what is this?");
 194     } catch (ClassCastException e)
 195     {
 196       // expected;
 197     }
 198     assertFalse(store.remove(null));
 199
 200     /*
 201      * simple deletion
 202      */
 203     assertTrue(store.remove(sf1));
 204     assertTrue(store.isEmpty());
 205
 206     SimpleFeature sf2 = add(store, 0, 0);
 207     SimpleFeature sf2a = add(store, 30, 40);
 208     assertTrue(store.contains(sf2));
 209     assertFalse(store.remove(sf1));
 210     assertTrue(store.remove(sf2));
 211     assertTrue(store.remove(sf2a));
 212     assertTrue(store.isEmpty());
 213
 214     /*
 215      * nested feature deletion
 216      */
 217     SimpleFeature sf4 = add(store, 20, 30);
 218     SimpleFeature sf5 = add(store, 22, 26); // to NCList
 219     SimpleFeature sf6 = add(store, 23, 24); // child of sf5
 220     SimpleFeature sf7 = add(store, 25, 25); // sibling of sf6
 221     SimpleFeature sf8 = add(store, 24, 24); // child of sf6
 222     SimpleFeature sf9 = add(store, 23, 23); // child of sf6
 223     assertEquals(store.size(), 6);
 224
 225     // delete a node with children - they take its place
 226     assertTrue(store.remove(sf6)); // sf8, sf9 should become children of sf5
 227     assertEquals(store.size(), 5);
 228     assertFalse(store.contains(sf6));
 229
 230     // delete a node with no children
 231     assertTrue(store.remove(sf7));
 232     assertEquals(store.size(), 4);
 233     assertFalse(store.contains(sf7));
 234
 235     // delete root of NCList
 236     assertTrue(store.remove(sf5));
 237     assertEquals(store.size(), 3);
 238     assertFalse(store.contains(sf5));
 239
 240     // continue the killing fields
 241     assertTrue(store.remove(sf4));
 242     assertEquals(store.size(), 2);
 243     assertFalse(store.contains(sf4));
 244
 245     assertTrue(store.remove(sf9));
 246     assertEquals(store.size(), 1);
 247     assertFalse(store.contains(sf9));
 248
 249     assertTrue(store.remove(sf8));
 250     assertTrue(store.isEmpty());
 251   }
 252
 253   /**
 254    * A helper method to test whether a list contains a specific object (by
 255    * object identity, not equality test as used by List.contains())
 256    *
 257    * @param list
 258    * @param o
 259    * @return
 260    */
 261   private static boolean containsObject(List<? extends Object> list,
 262           Object o)
 263   {
 264     for (Object i : list)
 265     {
 266       if (i == o)
 267       {
 268         return true;
 269       }
 270     }
 271     return false;
 272   }
 273
 274   @Test(groups = "Functional")
 275   public void testAdd()
 276   {
 277     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 278
 279     assertFalse(store.add(null));
 280
 281     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 282     SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
 283
 284     assertTrue(store.add(sf1));
 285     assertEquals(store.size(), 1);
 286
 287     /*
 288      * contains should return true for the same or an identical feature
 289      */
 290     assertTrue(store.contains(sf1));
 291     assertTrue(store.contains(sf2));
 292
 293     /*
 294      * duplicates are accepted
 295      */
 296     assertTrue(store.add(sf2));
 297     assertEquals(store.size(), 2);
 298
 299     SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath");
 300     assertTrue(store.add(sf3));
 301     assertEquals(store.size(), 3);
 302   }
 303
 304   @Test(groups = "Functional")
 305   public void testAdd_noDuplicates()
 306   {
 307     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 308
 309     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 310     SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
 311     assertTrue(sf1.equals(sf2));
 312     assertTrue(store.add(sf1));
 313     assertEquals(store.size(), 1);
 314     assertFalse(store.add(sf2, false));
 315     assertEquals(store.size(), 1);
 316     assertTrue(store.contains(sf1));
 317     assertTrue(store.contains(sf2)); // because sf1.equals(sf2) !
 318   }
 319
 320   @Test(groups = "Functional")
 321   public void testIsEmpty()
 322   {
 323     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 324     assertTrue(store.isEmpty());
 325     assertEquals(store.size(), 0);
 326
 327     /*
 328      * non-nested feature
 329      */
 330     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 331     store.add(sf1);
 332     assertFalse(store.isEmpty());
 333     assertEquals(store.size(), 1);
 334     store.remove(sf1);
 335     assertTrue(store.isEmpty());
 336     assertEquals(store.size(), 0);
 337
 338     sf1 = new SimpleFeature(0, 0, "Cath");
 339     store.add(sf1);
 340     assertFalse(store.isEmpty());
 341     assertEquals(store.size(), 1);
 342     store.remove(sf1);
 343     assertTrue(store.isEmpty());
 344     assertEquals(store.size(), 0);
 345
 346     /*
 347      * sf2, sf3 added as nested features
 348      */
 349     sf1 = new SimpleFeature(19, 49, "Cath");
 350     SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath");
 351     SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath");
 352     store.add(sf1);
 353     assertEquals(store.size(), 1);
 354     store.add(sf2);
 355     assertEquals(store.size(), 2);
 356     store.add(sf3);
 357     assertEquals(store.size(), 3);
 358     assertTrue(store.remove(sf1));
 359     assertEquals(store.size(), 2);
 360
 361     assertFalse(store.isEmpty());
 362     assertTrue(store.remove(sf2));
 363     assertEquals(store.size(), 1);
 364     assertFalse(store.isEmpty());
 365     assertTrue(store.remove(sf3));
 366     assertEquals(store.size(), 0);
 367     assertTrue(store.isEmpty()); // all gone
 368   }
 369
 370   @Test(groups = "Functional")
 371   public void testRemove_readd()
 372   {
 373     /*
 374      * add a feature and a nested feature
 375      */
 376     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 377     SimpleFeature sf1 = add(store, 10, 20);
 378     // sf2 is nested in sf1 so will be stored in nestedFeatures
 379     SimpleFeature sf2 = add(store, 12, 14);
 380     assertEquals(store.size(), 2);
 381     assertTrue(store.contains(sf1));
 382     assertTrue(store.contains(sf2));
 383
 384     /*
 385      * delete the first feature
 386      */
 387     assertTrue(store.remove(sf1));
 388     assertFalse(store.contains(sf1));
 389     assertTrue(store.contains(sf2));
 390
 391     /*
 392      * re-add the 'nested' feature; it is now duplicated
 393      */
 394     store.add(sf2);
 395     assertEquals(store.size(), 2);
 396     assertTrue(store.contains(sf2));
 397   }
 398
 399   @Test(groups = "Functional")
 400   public void testContains()
 401   {
 402     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 403     SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
 404     SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam");
 405
 406     store.add(sf1);
 407     assertTrue(store.contains(sf1));
 408     assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature
 409     assertFalse(store.contains(sf2)); // different description
 410
 411     /*
 412      * add a nested feature
 413      */
 414     SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath");
 415     store.add(sf3);
 416     assertTrue(store.contains(sf3));
 417     assertTrue(store.contains(new SimpleFeature(sf3)));
 418
 419     /*
 420      * delete the outer (enclosing, non-nested) feature
 421      */
 422     store.remove(sf1);
 423     assertFalse(store.contains(sf1));
 424     assertTrue(store.contains(sf3));
 425
 426     assertFalse(store.contains(null));
 427     try
 428     {
 429       assertFalse(store.contains("junk"));
 430     } catch (ClassCastException e)
 431     {
 432       // expected;
 433     }
 434   }
 435
 436   @Test(groups = "Functional")
 437   public void testFindOverlaps_resultsArg_mixed()
 438   {
 439     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 440     SimpleFeature sf1 = add(store, 10, 50);
 441     SimpleFeature sf2 = add(store, 1, 15);
 442     SimpleFeature sf3 = add(store, 20, 30);
 443     SimpleFeature sf4 = add(store, 40, 100);
 444     SimpleFeature sf5 = add(store, 60, 100);
 445     SimpleFeature sf6 = add(store, 70, 70);
 446
 447     List<SimpleFeature> overlaps = new ArrayList<>();
 448     List<SimpleFeature> overlaps2 = store.findOverlaps(200, 200, overlaps);
 449     assertSame(overlaps, overlaps2);
 450     assertTrue(overlaps.isEmpty());
 451
 452     overlaps.clear();
 453     store.findOverlaps(1, 9, overlaps);
 454     assertEquals(overlaps.size(), 1);
 455     assertTrue(overlaps.contains(sf2));
 456
 457     overlaps.clear();
 458     store.findOverlaps(5, 18, overlaps);
 459     assertEquals(overlaps.size(), 2);
 460     assertTrue(overlaps.contains(sf1));
 461     assertTrue(overlaps.contains(sf2));
 462
 463     overlaps.clear();
 464     store.findOverlaps(30, 40, overlaps);
 465     assertEquals(overlaps.size(), 3);
 466     assertTrue(overlaps.contains(sf1));
 467     assertTrue(overlaps.contains(sf3));
 468     assertTrue(overlaps.contains(sf4));
 469
 470     overlaps.clear();
 471     store.findOverlaps(80, 90, overlaps);
 472     assertEquals(overlaps.size(), 2);
 473     assertTrue(overlaps.contains(sf4));
 474     assertTrue(overlaps.contains(sf5));
 475
 476     overlaps.clear();
 477     store.findOverlaps(68, 70, overlaps);
 478     assertEquals(overlaps.size(), 3);
 479     assertTrue(overlaps.contains(sf4));
 480     assertTrue(overlaps.contains(sf5));
 481     assertTrue(overlaps.contains(sf6));
 482
 483     /*
 484      * and without clearing the list first
 485      * note that sf4 is included twice, as an
 486      * overlap of 68-70 and also of 30-40
 487      */
 488     store.findOverlaps(30, 40, overlaps);
 489     assertEquals(overlaps.size(), 6);
 490     assertTrue(overlaps.contains(sf1));
 491     assertTrue(overlaps.contains(sf3));
 492     assertTrue(overlaps.contains(sf4));
 493     assertTrue(overlaps.contains(sf5));
 494     assertTrue(overlaps.contains(sf6));
 495     assertSame(sf4, overlaps.get(0));
 496     assertSame(sf4, overlaps.get(4));
 497   }
 498
 499   @Test(groups = "Functional")
 500   public void testFindOverlaps_resultsArg_nested()
 501   {
 502     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 503     SimpleFeature sf1 = add(store, 10, 50);
 504     SimpleFeature sf2 = add(store, 10, 40);
 505     SimpleFeature sf3 = add(store, 20, 30);
 506     // feature at same location but different description
 507     SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
 508     store.add(sf4);
 509     SimpleFeature sf5 = add(store, 35, 36);
 510
 511     List<SimpleFeature> overlaps = new ArrayList<>();
 512     store.findOverlaps(1, 9, overlaps);
 513     assertTrue(overlaps.isEmpty());
 514
 515     store.findOverlaps(10, 15, overlaps);
 516     assertEquals(overlaps.size(), 2);
 517     assertTrue(overlaps.contains(sf1));
 518     assertTrue(overlaps.contains(sf2));
 519
 520     overlaps.clear();
 521     store.findOverlaps(45, 60, overlaps);
 522     assertEquals(overlaps.size(), 1);
 523     assertTrue(overlaps.contains(sf1));
 524
 525     overlaps.clear();
 526     store.findOverlaps(32, 38, overlaps);
 527     assertEquals(overlaps.size(), 3);
 528     assertTrue(overlaps.contains(sf1));
 529     assertTrue(overlaps.contains(sf2));
 530     assertTrue(overlaps.contains(sf5));
 531
 532     overlaps.clear();
 533     store.findOverlaps(15, 25, overlaps);
 534     assertEquals(overlaps.size(), 4);
 535     assertTrue(overlaps.contains(sf1));
 536     assertTrue(overlaps.contains(sf2));
 537     assertTrue(overlaps.contains(sf3));
 538     assertTrue(overlaps.contains(sf4));
 539   }
 540
 541   @Test(groups = "Functional")
 542   public void testFindOverlaps_resultsArg_nonNested()
 543   {
 544     IntervalStore<SimpleFeature> store = new IntervalStore<>();
 545     SimpleFeature sf1 = add(store, 10, 20);
 546     // same range different description
 547     SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
 548     store.add(sf2);
 549     SimpleFeature sf3 = add(store, 15, 25);
 550     SimpleFeature sf4 = add(store, 20, 35);
 551
 552     assertEquals(store.size(), 4);
 553     List<SimpleFeature> overlaps = new ArrayList<>();
 554     store.findOverlaps(1, 9, overlaps);
 555     assertTrue(overlaps.isEmpty());
 556
 557     store.findOverlaps(8, 10, overlaps);
 558     assertEquals(overlaps.size(), 2);
 559     assertTrue(overlaps.contains(sf1));
 560     assertTrue(overlaps.contains(sf2));
 561
 562     overlaps.clear();
 563     store.findOverlaps(12, 16, overlaps);
 564     assertEquals(overlaps.size(), 3);
 565     assertTrue(overlaps.contains(sf1));
 566     assertTrue(overlaps.contains(sf2));
 567     assertTrue(overlaps.contains(sf3));
 568
 569     overlaps.clear();
 570     store.findOverlaps(33, 33, overlaps);
 571     assertEquals(overlaps.size(), 1);
 572     assertTrue(overlaps.contains(sf4));
 573
 574     /*
 575      * ensure edge cases are covered
 576      */
 577     overlaps.clear();
 578     store.findOverlaps(35, 40, overlaps);
 579     assertEquals(overlaps.size(), 1);
 580     assertTrue(overlaps.contains(sf4));
 581
 582     overlaps.clear();
 583     assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty());
 584     assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty());
 585   }
 586
 587   /**
 588    * Compares alternative IntervalStoreI implementations for time to add an
 589    * interval then query, at a range of different scales of N (the number of
 590    * stored features).
 591    */
 592   @Test(groups = "Timing")
 593   public void testAddAndQueryTiming()
 594   {
 595     IntervalStoreI<SimpleFeature> store = new intervalstore.impl.IntervalStore<>();
 596     System.out.println("IntervalStoreJ");
 597     testAddAndQueryTiming(store);
 598
 599     System.out.println("\nnonc.IntervalStore");
 600     store = new intervalstore.nonc.IntervalStore<>();
 601     testAddAndQueryTiming(store);
 602   }
 603
 604   /**
 605    * Populates the store with intervals, then logs the time taken to add an
 606    * interval then query, at a range of different scales of N (the number of
 607    * stored features).
 608    *
 609    * @param store
 610    */
 611   private void testAddAndQueryTiming(IntervalStoreI<SimpleFeature> store)
 612   {
 613     final int seqlen = 100000; // e.g. length of gene sequence
 614     final int repeats = 20;
 615     final int K = 1000;
 616     final int warmups = 5;
 617     final int[] scales = new int[] { 10 * K, 100 * K, K * K };
 618
 619     Random r = new Random(732); // fixed seed = repeatable test
 620     int counter = 0; // to ensure a distinct description for each feature
 621
 622     System.out.println("Scale\titeration\tmicrosecs");
 623
 624     for (int scale : scales)
 625     {
 626       /*
 627        * add 'scale' features to the store
 628        */
 629       for (int i = 0; i < scale; i++)
 630       {
 631         SimpleFeature sf = makeFeature(seqlen, r, counter);
 632         counter++;
 633         store.add(sf);
 634       }
 635
 636       /*
 637        * do "add then query" and log the time taken for the query
 638        * we ignore the first 5 repetitions as 'warmups'
 639        */
 640       long total = 0L;
 641       for (int i = 0; i < repeats + warmups; i++)
 642       {
 643         SimpleFeature sf = makeFeature(seqlen, r, counter);
 644         store.add(sf);
 645         long t1 = System.nanoTime();
 646         store.findOverlaps(10, 20);
 647         long elapsed = System.nanoTime() - t1;
 648         if (i >= warmups)
 649         {
 650           total += elapsed;
 651           System.out.println(
 652                   String.format("%d\t%d\t%d", scale, i - warmups,
 653                           elapsed / K));
 654         }
 655       }
 656       System.out.println("average " + (total / (K * repeats)));
 657     }
 658   }
 659
 660   SimpleFeature makeFeature(final int seqlen, Random r, int counter)
 661   {
 662     int i1 = r.nextInt(seqlen);
 663     int i2 = r.nextInt(seqlen);
 664     int from = Math.min(i1, i2);
 665     int to = Math.max(i1, i2);
 666     SimpleFeature sf = new SimpleFeature(from, to, "desc" + counter);
 667     return sf;
 668   }
 669 }