/*
BSD 3-Clause License

Copyright (c) 2018, Mungo Carstairs
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.

* Neither the name of the copyright holder nor the names of its
  contributors may be used to endorse or promote products derived from
  this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package intervalstore.nonc;

import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertSame;
import static org.testng.Assert.assertTrue;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.testng.annotations.Test;

import intervalstore.api.IntervalStoreI;

public class IntervalStoreTest
{
  @Test(groups = "Functional")
  public void testFindOverlaps_nonNested()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 20);
    // same range different description
    SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
    store.add(sf2);
    SimpleFeature sf3 = add(store, 15, 25);
    SimpleFeature sf4 = add(store, 20, 35);

    assertEquals(store.size(), 4);
    List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
    assertTrue(overlaps.isEmpty());

    overlaps = store.findOverlaps(8, 10);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));

    overlaps = store.findOverlaps(12, 16);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
    assertTrue(overlaps.contains(sf3));

    overlaps = store.findOverlaps(33, 33);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf4));

    /*
     * ensure edge cases are covered
     */
    overlaps = store.findOverlaps(35, 40);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf4));
    assertTrue(store.findOverlaps(36, 100).isEmpty());
    assertTrue(store.findOverlaps(1, 9).isEmpty());
  }

  @Test(groups = "Functional")
  public void testFindOverlaps_nested()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 50);
    SimpleFeature sf2 = add(store, 10, 40);
    SimpleFeature sf3 = add(store, 20, 30);
    // feature at same location but different description
    SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
    store.add(sf4);
    SimpleFeature sf5 = add(store, 35, 36);

    List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
    assertTrue(overlaps.isEmpty());

    overlaps = store.findOverlaps(10, 15);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));

    overlaps = store.findOverlaps(45, 60);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf1));

    overlaps = store.findOverlaps(32, 38);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
    assertTrue(overlaps.contains(sf5));

    overlaps = store.findOverlaps(15, 25);
    assertEquals(overlaps.size(), 4);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
    assertTrue(overlaps.contains(sf3));
    assertTrue(overlaps.contains(sf4));
  }

  @Test(groups = "Functional")
  public void testFindOverlaps_mixed()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 50);
    SimpleFeature sf2 = add(store, 1, 15);
    SimpleFeature sf3 = add(store, 20, 30);
    SimpleFeature sf4 = add(store, 40, 100);
    SimpleFeature sf5 = add(store, 60, 100);
    SimpleFeature sf6 = add(store, 70, 70);

    List<SimpleFeature> overlaps = store.findOverlaps(200, 200);
    assertTrue(overlaps.isEmpty());

    overlaps = store.findOverlaps(1, 9);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf2));

    overlaps = store.findOverlaps(5, 18);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));

    overlaps = store.findOverlaps(30, 40);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf3));
    assertTrue(overlaps.contains(sf4));

    overlaps = store.findOverlaps(80, 90);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf4));
    assertTrue(overlaps.contains(sf5));

    overlaps = store.findOverlaps(68, 70);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf4));
    assertTrue(overlaps.contains(sf5));
    assertTrue(overlaps.contains(sf6));
  }

  /**
   * Helper method to add a feature with type "desc"
   * 
   * @param store
   * @param from
   * @param to
   * @return
   */
  SimpleFeature add(IntervalStore<SimpleFeature> store, int from,
          int to)
  {
    SimpleFeature sf1 = new SimpleFeature(from, to, "desc");
    store.add(sf1);
    return sf1;
  }

  @Test(groups = "Functional")
  public void testRemove()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 20);
    assertTrue(store.contains(sf1));

    try
    {
      store.remove("what is this?");
    } catch (ClassCastException e)
    {
      // expected;
    }
    assertFalse(store.remove(null));

    /*
     * simple deletion
     */
    assertTrue(store.remove(sf1));
    assertTrue(store.isEmpty());

    SimpleFeature sf2 = add(store, 0, 0);
    SimpleFeature sf2a = add(store, 30, 40);
    assertTrue(store.contains(sf2));
    assertFalse(store.remove(sf1));
    assertTrue(store.remove(sf2));
    assertTrue(store.remove(sf2a));
    assertTrue(store.isEmpty());

    /*
     * nested feature deletion
     */
    SimpleFeature sf4 = add(store, 20, 30);
    SimpleFeature sf5 = add(store, 22, 26); // to NCList
    SimpleFeature sf6 = add(store, 23, 24); // child of sf5
    SimpleFeature sf7 = add(store, 25, 25); // sibling of sf6
    SimpleFeature sf8 = add(store, 24, 24); // child of sf6
    SimpleFeature sf9 = add(store, 23, 23); // child of sf6
    assertEquals(store.size(), 6);

    // delete a node with children - they take its place
    assertTrue(store.remove(sf6)); // sf8, sf9 should become children of sf5
    assertEquals(store.size(), 5);
    assertFalse(store.contains(sf6));

    // delete a node with no children
    assertTrue(store.remove(sf7));
    assertEquals(store.size(), 4);
    assertFalse(store.contains(sf7));

    // delete root of NCList
    assertTrue(store.remove(sf5));
    assertEquals(store.size(), 3);
    assertFalse(store.contains(sf5));

    // continue the killing fields
    assertTrue(store.remove(sf4));
    assertEquals(store.size(), 2);
    assertFalse(store.contains(sf4));

    assertTrue(store.remove(sf9));
    assertEquals(store.size(), 1);
    assertFalse(store.contains(sf9));

    assertTrue(store.remove(sf8));
    assertTrue(store.isEmpty());
  }

  /**
   * A helper method to test whether a list contains a specific object (by
   * object identity, not equality test as used by List.contains())
   * 
   * @param list
   * @param o
   * @return
   */
  private static boolean containsObject(List<? extends Object> list,
          Object o)
  {
    for (Object i : list)
    {
      if (i == o)
      {
        return true;
      }
    }
    return false;
  }

  @Test(groups = "Functional")
  public void testAdd()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();

    assertFalse(store.add(null));

    SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
    SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");

    assertTrue(store.add(sf1));
    assertEquals(store.size(), 1);

    /*
     * contains should return true for the same or an identical feature
     */
    assertTrue(store.contains(sf1));
    assertTrue(store.contains(sf2));

    /*
     * duplicates are accepted
     */
    assertTrue(store.add(sf2));
    assertEquals(store.size(), 2);

    SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath");
    assertTrue(store.add(sf3));
    assertEquals(store.size(), 3);
  }

  @Test(groups = "Functional")
  public void testAdd_noDuplicates()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();

    SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
    SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
    assertTrue(sf1.equals(sf2));
    assertTrue(store.add(sf1));
    assertEquals(store.size(), 1);
    assertFalse(store.add(sf2, false));
    assertEquals(store.size(), 1);
    assertTrue(store.contains(sf1));
    assertTrue(store.contains(sf2)); // because sf1.equals(sf2) !
  }

  @Test(groups = "Functional")
  public void testIsEmpty()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    assertTrue(store.isEmpty());
    assertEquals(store.size(), 0);

    /*
     * non-nested feature
     */
    SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
    store.add(sf1);
    assertFalse(store.isEmpty());
    assertEquals(store.size(), 1);
    store.remove(sf1);
    assertTrue(store.isEmpty());
    assertEquals(store.size(), 0);

    sf1 = new SimpleFeature(0, 0, "Cath");
    store.add(sf1);
    assertFalse(store.isEmpty());
    assertEquals(store.size(), 1);
    store.remove(sf1);
    assertTrue(store.isEmpty());
    assertEquals(store.size(), 0);

    /*
     * sf2, sf3 added as nested features
     */
    sf1 = new SimpleFeature(19, 49, "Cath");
    SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath");
    SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath");
    store.add(sf1);
    assertEquals(store.size(), 1);
    store.add(sf2);
    assertEquals(store.size(), 2);
    store.add(sf3);
    assertEquals(store.size(), 3);
    assertTrue(store.remove(sf1));
    assertEquals(store.size(), 2);

    assertFalse(store.isEmpty());
    assertTrue(store.remove(sf2));
    assertEquals(store.size(), 1);
    assertFalse(store.isEmpty());
    assertTrue(store.remove(sf3));
    assertEquals(store.size(), 0);
    assertTrue(store.isEmpty()); // all gone
  }

  @Test(groups = "Functional")
  public void testRemove_readd()
  {
    /*
     * add a feature and a nested feature
     */
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 20);
    // sf2 is nested in sf1 so will be stored in nestedFeatures
    SimpleFeature sf2 = add(store, 12, 14);
    assertEquals(store.size(), 2);
    assertTrue(store.contains(sf1));
    assertTrue(store.contains(sf2));

    /*
     * delete the first feature
     */
    assertTrue(store.remove(sf1));
    assertFalse(store.contains(sf1));
    assertTrue(store.contains(sf2));

    /*
     * re-add the 'nested' feature; it is now duplicated
     */
    store.add(sf2);
    assertEquals(store.size(), 2);
    assertTrue(store.contains(sf2));
  }

  @Test(groups = "Functional")
  public void testContains()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
    SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam");

    store.add(sf1);
    assertTrue(store.contains(sf1));
    assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature
    assertFalse(store.contains(sf2)); // different description

    /*
     * add a nested feature
     */
    SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath");
    store.add(sf3);
    assertTrue(store.contains(sf3));
    assertTrue(store.contains(new SimpleFeature(sf3)));

    /*
     * delete the outer (enclosing, non-nested) feature
     */
    store.remove(sf1);
    assertFalse(store.contains(sf1));
    assertTrue(store.contains(sf3));

    assertFalse(store.contains(null));
    try
    {
      assertFalse(store.contains("junk"));
    } catch (ClassCastException e)
    {
      // expected;
    }
  }

  @Test(groups = "Functional")
  public void testFindOverlaps_resultsArg_mixed()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 50);
    SimpleFeature sf2 = add(store, 1, 15);
    SimpleFeature sf3 = add(store, 20, 30);
    SimpleFeature sf4 = add(store, 40, 100);
    SimpleFeature sf5 = add(store, 60, 100);
    SimpleFeature sf6 = add(store, 70, 70);
  
    List<SimpleFeature> overlaps = new ArrayList<>();
    List<SimpleFeature> overlaps2 = store.findOverlaps(200, 200, overlaps);
    assertSame(overlaps, overlaps2);
    assertTrue(overlaps.isEmpty());
  
    overlaps.clear();
    store.findOverlaps(1, 9, overlaps);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf2));
  
    overlaps.clear();
    store.findOverlaps(5, 18, overlaps);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
  
    overlaps.clear();
    store.findOverlaps(30, 40, overlaps);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf3));
    assertTrue(overlaps.contains(sf4));
  
    overlaps.clear();
    store.findOverlaps(80, 90, overlaps);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf4));
    assertTrue(overlaps.contains(sf5));
  
    overlaps.clear();
    store.findOverlaps(68, 70, overlaps);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf4));
    assertTrue(overlaps.contains(sf5));
    assertTrue(overlaps.contains(sf6));

    /*
     * and without clearing the list first
     * note that sf4 is included twice, as an
     * overlap of 68-70 and also of 30-40
     */
    store.findOverlaps(30, 40, overlaps);
    assertEquals(overlaps.size(), 6);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf3));
    assertTrue(overlaps.contains(sf4));
    assertTrue(overlaps.contains(sf5));
    assertTrue(overlaps.contains(sf6));
    assertSame(sf4, overlaps.get(0));
    assertSame(sf4, overlaps.get(4));
  }

  @Test(groups = "Functional")
  public void testFindOverlaps_resultsArg_nested()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 50);
    SimpleFeature sf2 = add(store, 10, 40);
    SimpleFeature sf3 = add(store, 20, 30);
    // feature at same location but different description
    SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
    store.add(sf4);
    SimpleFeature sf5 = add(store, 35, 36);
  
    List<SimpleFeature> overlaps = new ArrayList<>();
    store.findOverlaps(1, 9, overlaps);
    assertTrue(overlaps.isEmpty());
  
    store.findOverlaps(10, 15, overlaps);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
  
    overlaps.clear();
    store.findOverlaps(45, 60, overlaps);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf1));
  
    overlaps.clear();
    store.findOverlaps(32, 38, overlaps);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
    assertTrue(overlaps.contains(sf5));
  
    overlaps.clear();
    store.findOverlaps(15, 25, overlaps);
    assertEquals(overlaps.size(), 4);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
    assertTrue(overlaps.contains(sf3));
    assertTrue(overlaps.contains(sf4));
  }

  @Test(groups = "Functional")
  public void testFindOverlaps_resultsArg_nonNested()
  {
    IntervalStore<SimpleFeature> store = new IntervalStore<>();
    SimpleFeature sf1 = add(store, 10, 20);
    // same range different description
    SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
    store.add(sf2);
    SimpleFeature sf3 = add(store, 15, 25);
    SimpleFeature sf4 = add(store, 20, 35);
  
    assertEquals(store.size(), 4);
    List<SimpleFeature> overlaps = new ArrayList<>();
    store.findOverlaps(1, 9, overlaps);
    assertTrue(overlaps.isEmpty());
  
    store.findOverlaps(8, 10, overlaps);
    assertEquals(overlaps.size(), 2);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
  
    overlaps.clear();
    store.findOverlaps(12, 16, overlaps);
    assertEquals(overlaps.size(), 3);
    assertTrue(overlaps.contains(sf1));
    assertTrue(overlaps.contains(sf2));
    assertTrue(overlaps.contains(sf3));
  
    overlaps.clear();
    store.findOverlaps(33, 33, overlaps);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf4));
  
    /*
     * ensure edge cases are covered
     */
    overlaps.clear();
    store.findOverlaps(35, 40, overlaps);
    assertEquals(overlaps.size(), 1);
    assertTrue(overlaps.contains(sf4));

    overlaps.clear();
    assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty());
    assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty());
  }

  /**
   * Compares alternative IntervalStoreI implementations for time to add an
   * interval then query, at a range of different scales of N (the number of
   * stored features).
   */
  @Test(groups = "Timing")
  public void testAddAndQueryTiming()
  {
    IntervalStoreI<SimpleFeature> store = new intervalstore.impl.IntervalStore<>();
    System.out.println("IntervalStoreJ");
    testAddAndQueryTiming(store);

    System.out.println("\nnonc.IntervalStore");
    store = new intervalstore.nonc.IntervalStore<>();
    testAddAndQueryTiming(store);
  }

  /**
   * Populates the store with intervals, then logs the time taken to add an
   * interval then query, at a range of different scales of N (the number of
   * stored features).
   * 
   * @param store
   */
  private void testAddAndQueryTiming(IntervalStoreI<SimpleFeature> store)
  {
    final int seqlen = 100000; // e.g. length of gene sequence
    final int repeats = 20;
    final int K = 1000;
    final int warmups = 5;
    final int[] scales = new int[] { 10 * K, 100 * K, K * K };

    Random r = new Random(732); // fixed seed = repeatable test
    int counter = 0; // to ensure a distinct description for each feature

    System.out.println("Scale\titeration\tmicrosecs");
    
    for (int scale : scales)
    {
      /*
       * add 'scale' features to the store
       */
      for (int i = 0; i < scale; i++)
      {
        SimpleFeature sf = makeFeature(seqlen, r, counter);
        counter++;
        store.add(sf);
      }

      /*
       * do "add then query" and log the time taken for the query
       * we ignore the first 5 repetitions as 'warmups'
       */
      long total = 0L;
      for (int i = 0; i < repeats + warmups; i++)
      {
        SimpleFeature sf = makeFeature(seqlen, r, counter);
        store.add(sf);
        long t1 = System.nanoTime();
        store.findOverlaps(10, 20);
        long elapsed = System.nanoTime() - t1;
        if (i >= warmups)
        {
          total += elapsed;
          System.out.println(
                  String.format("%d\t%d\t%d", scale, i - warmups,
                          elapsed / K));
        }
      }
      System.out.println("average " + (total / (K * repeats)));
    }
  }

  SimpleFeature makeFeature(final int seqlen, Random r, int counter)
  {
    int i1 = r.nextInt(seqlen);
    int i2 = r.nextInt(seqlen);
    int from = Math.min(i1, i2);
    int to = Math.max(i1, i2);
    SimpleFeature sf = new SimpleFeature(from, to, "desc" + counter);
    return sf;
  }
}