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