package jalview.datamodel.features;
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 jalview.datamodel.SequenceFeature;

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

import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

public class NCListTest
{

  private Random random = new Random(107);

  private Comparator<ContiguousI> sorter = new RangeComparator(true);

  /**
   * A basic sanity test of the constructor
   */
  @Test(groups = "Functional")
  public void testConstructor()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 20));
    ranges.add(new Range(10, 20));
    ranges.add(new Range(15, 30));
    ranges.add(new Range(10, 30));
    ranges.add(new Range(11, 19));
    ranges.add(new Range(10, 20));
    ranges.add(new Range(1, 100));

    NCList<Range> ncl = new NCList<Range>(ranges);
    String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
    assertEquals(ncl.toString(), expected);
    assertTrue(ncl.isValid());

    Collections.reverse(ranges);
    ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), expected);
    assertTrue(ncl.isValid());
  }

  @Test(groups = "Functional")
  public void testFindOverlaps()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 50));
    ranges.add(new Range(30, 70));
    ranges.add(new Range(1, 100));
    ranges.add(new Range(70, 120));
  
    NCList<Range> ncl = new NCList<Range>(ranges);

    List<Range> overlaps = ncl.findOverlaps(121, 122);
    assertEquals(overlaps.size(), 0);

    overlaps = ncl.findOverlaps(21, 22);
    assertEquals(overlaps.size(), 2);
    assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
    assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
    assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
    assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);

    overlaps = ncl.findOverlaps(110, 110);
    assertEquals(overlaps.size(), 1);
    assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
    assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
  }

  @Test(groups = "Functional")
  public void testAdd_onTheEnd()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 50));
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), "[20-50]");
    assertTrue(ncl.isValid());

    ncl.add(new Range(60, 70));
    assertEquals(ncl.toString(), "[20-50, 60-70]");
    assertTrue(ncl.isValid());
  }

  @Test(groups = "Functional")
  public void testAdd_inside()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 50));
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), "[20-50]");
    assertTrue(ncl.isValid());

    ncl.add(new Range(30, 40));
    assertEquals(ncl.toString(), "[20-50 [30-40]]");
  }

  @Test(groups = "Functional")
  public void testAdd_onTheFront()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 50));
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), "[20-50]");
    assertTrue(ncl.isValid());

    ncl.add(new Range(5, 15));
    assertEquals(ncl.toString(), "[5-15, 20-50]");
    assertTrue(ncl.isValid());
  }

  @Test(groups = "Functional")
  public void testAdd_enclosing()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 50));
    ranges.add(new Range(30, 60));
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), "[20-50, 30-60]");
    assertTrue(ncl.isValid());
    assertEquals(ncl.getStart(), 20);

    ncl.add(new Range(10, 70));
    assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
    assertTrue(ncl.isValid());
  }

  @Test(groups = "Functional")
  public void testAdd_spanning()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(20, 40));
    ranges.add(new Range(60, 70));
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), "[20-40, 60-70]");
    assertTrue(ncl.isValid());

    ncl.add(new Range(30, 50));
    assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
    assertTrue(ncl.isValid());

    ncl.add(new Range(40, 65));
    assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
    assertTrue(ncl.isValid());
  }

  /**
   * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
   * [0-scale] interval to be stored
   * 
   * @return
   */
  @DataProvider(name = "scalesOfLife")
  public Object[][] getScales()
  {
    return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
  }

  /**
   * Do a number of pseudo-random (reproducible) builds of an NCList, with
   * checks for validity of the data structure, and searches for (pseudo-random)
   * overlap ranges, for greater (but not perfect!) confidence that corner cases
   * are being handled correctly.
   */
  @Test(groups = "Functional", dataProvider = "scalesOfLife")
  public void testAdd_FindOverlaps_pseudoRandom(Integer scale)
  {
    NCList<Range> ncl = new NCList<Range>();
    int count = 0;
    List<Range> ranges = new ArrayList<Range>(scale);
    
    for (int i = 0; i < scale; i++)
    {
      int r1 = random.nextInt(scale + 1);
      int r2 = random.nextInt(scale + 1);
      int from = Math.min(r1, r2);
      int to = Math.max(r1, r2);
      Range range = new Range(from, to);
      ncl.add(range);
      ranges.add(range);
    
      /*
       * check list format is valid at each stage of its construction
       */
      assertTrue(ncl.isValid(),
              String.format("Failed for scale = %d, i=%d", scale, i));
      count++;
      assertEquals(ncl.getSize(), count);
    }
    // System.out.println(ncl.prettyPrint());
    
    /*
     * sort the list of added ranges - this doesn't affect the test,
     * just makes it easier to inspect the data in the debugger
     */
    Collections.sort(ranges, sorter);
    
    testFindOverlaps(ncl, scale, ranges);
  }

  /**
   * A helper method that generates pseudo-random range queries and veries that
   * findOverlaps returns the correct matches
   * 
   * @param ncl
   *          the NCList to query
   * @param scale
   *          ncl maximal range is [0, scale]
   * @param ranges
   *          a list of the ranges stored in ncl
   */
  protected void testFindOverlaps(NCList<Range> ncl, int scale,
          List<Range> ranges)
  {
    int halfScale = scale / 2;
    int minIterations = 20;

    /*
     * generates ranges in [-halfScale, scale+halfScale]
     * - some should be internal to [0, scale] P = 1/4
     * - some should lie before 0 P = 1/16
     * - some should lie after scale P = 1/16
     * - some should overlap left P = 1/4
     * - some should overlap right P = 1/4
     * - some should enclose P = 1/8
     * 
     * 50 iterations give a 96% probability of including the
     * unlikeliest case; keep going until we have done all!
     */
    boolean inside = false;
    boolean enclosing = false;
    boolean before = false;
    boolean after = false;
    boolean overlapLeft = false;
    boolean overlapRight = false;
    boolean allCasesCovered = false;

    int i = 0;
    while (i < minIterations || !allCasesCovered)
    {
      i++;
      int r1 = random.nextInt((scale + 1) * 2);
      int r2 = random.nextInt((scale + 1) * 2);
      int from = Math.min(r1, r2) - halfScale;
      int to = Math.max(r1, r2) - halfScale;

      /*
       * ensure all cases of interest get covered
       */
      inside |= from >= 0 && to <= scale;
      enclosing |= from <= 0 && to >= scale;
      before |= to < 0;
      after |= from > scale;
      overlapLeft |= from < 0 && to >= 0 && to <= scale;
      overlapRight |= from >= 0 && from <= scale && to > scale;
      if (!allCasesCovered)
      {
        allCasesCovered |= inside && enclosing && before && after
              && overlapLeft && overlapRight;
        if (allCasesCovered)
        {
          System.out
                  .println(String
                          .format("Covered all findOverlaps cases after %d iterations for scale %d",
                                  i, scale));
        }
      }

      verifyFindOverlaps(ncl, from, to, ranges);
    }
  }

  /**
   * A helper method that verifies that overlaps found by interrogating an
   * NCList correctly match those found by brute force search
   * 
   * @param ncl
   * @param from
   * @param to
   * @param ranges
   */
  protected void verifyFindOverlaps(NCList<Range> ncl, int from, int to,
          List<Range> ranges)
  {
    List<Range> overlaps = ncl.findOverlaps(from, to);

    /*
     * check returned entries do indeed overlap from-to range
     */
    for (Range r : overlaps)
    {
      int begin = r.getBegin();
      int end = r.getEnd();
      assertTrue(begin <= to && end >= from, String.format(
              "[%d, %d] does not overlap query range [%d, %d]", begin, end,
              from, to));
    }

    /*
     * check overlapping ranges are included in the results
     * (the test above already shows non-overlapping ranges are not)
     */
    for (Range r : ranges)
    {
      int begin = r.getBegin();
      int end = r.getEnd();
      if (begin <= to && end >= from)
      {
        boolean found = overlaps.contains(r);
        assertTrue(found, String.format(
                "[%d, %d] missing in query range [%d, %d]", begin, end,
                from, to));
      }
    }
  }

  @Test(groups = "Functional")
  public void testGetEntries()
  {
    List<Range> ranges = new ArrayList<Range>();
    Range r1 = new Range(20, 20);
    Range r2 = new Range(10, 20);
    Range r3 = new Range(15, 30);
    Range r4 = new Range(10, 30);
    Range r5 = new Range(11, 19);
    Range r6 = new Range(10, 20);
    ranges.add(r1);
    ranges.add(r2);
    ranges.add(r3);
    ranges.add(r4);
    ranges.add(r5);
    ranges.add(r6);
  
    NCList<Range> ncl = new NCList<Range>(ranges);
    Range r7 = new Range(1, 100);
    ncl.add(r7);

    List<Range> contents = ncl.getEntries();
    assertEquals(contents.size(), 7);
    assertTrue(contents.contains(r1));
    assertTrue(contents.contains(r2));
    assertTrue(contents.contains(r3));
    assertTrue(contents.contains(r4));
    assertTrue(contents.contains(r5));
    assertTrue(contents.contains(r6));
    assertTrue(contents.contains(r7));

    ncl = new NCList<Range>();
    assertTrue(ncl.getEntries().isEmpty());
  }

  @Test(groups = "Functional")
  public void testDelete()
  {
    List<Range> ranges = new ArrayList<Range>();
    Range r1 = new Range(20, 30);
    ranges.add(r1);
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertTrue(ncl.getEntries().contains(r1));

    Range r2 = new Range(20, 30);
    assertFalse(ncl.delete(null)); // null argument
    assertFalse(ncl.delete(r2)); // never added
    assertTrue(ncl.delete(r1)); // success
    assertTrue(ncl.getEntries().isEmpty());

    /*
     * tests where object.equals() == true
     */
    NCList<SequenceFeature> features = new NCList<SequenceFeature>();
    SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
            "group");
    SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
            "group");
    features.add(sf1);
    assertEquals(sf1, sf2); // sf1.equals(sf2)
    assertFalse(features.delete(sf2)); // equality is not enough for deletion
    assertTrue(features.getEntries().contains(sf1)); // still there!
    assertTrue(features.delete(sf1));
    assertTrue(features.getEntries().isEmpty()); // gone now

    /*
     * test with duplicate objects in NCList
     */
    features.add(sf1);
    features.add(sf1);
    assertEquals(features.getEntries().size(), 2);
    assertSame(features.getEntries().get(0), sf1);
    assertSame(features.getEntries().get(1), sf1);
    assertTrue(features.delete(sf1)); // first match only is deleted
    assertTrue(features.contains(sf1));
    assertEquals(features.getSize(), 1);
    assertTrue(features.delete(sf1));
    assertTrue(features.getEntries().isEmpty());
  }

  @Test(groups = "Functional")
  public void testAdd_overlapping()
  {
    List<Range> ranges = new ArrayList<Range>();
    ranges.add(new Range(40, 50));
    ranges.add(new Range(20, 30));
    NCList<Range> ncl = new NCList<Range>(ranges);
    assertEquals(ncl.toString(), "[20-30, 40-50]");
    assertTrue(ncl.isValid());
  
    /*
     * add range overlapping internally
     */
    ncl.add(new Range(25, 35));
    assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
    assertTrue(ncl.isValid());

    /*
     * add range overlapping last range
     */
    ncl.add(new Range(45, 55));
    assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
    assertTrue(ncl.isValid());

    /*
     * add range overlapping first range
     */
    ncl.add(new Range(15, 25));
    assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
    assertTrue(ncl.isValid());
  }

  /**
   * Test the contains method (which uses object equals test)
   */
  @Test(groups = "Functional")
  public void testContains()
  {
    NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
    SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
            "group");
    SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
            "group");
    SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
            "anothergroup");
    ncl.add(sf1);

    assertTrue(ncl.contains(sf1));
    assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
    assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)

    /*
     * make some deeper structure in the NCList
     */
    SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
            "group");
    ncl.add(sf4);
    assertTrue(ncl.contains(sf4));
    SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
            "group");
    SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
            "group");
    ncl.add(sf5);
    ncl.add(sf6);
    assertTrue(ncl.contains(sf5));
    assertTrue(ncl.contains(sf6));
  }
}