/*
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 java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import intervalstore.api.IntervalI;

/**
 * A collection class to store interval-associated data, with O(log N)
 * performance for overlap queries, insertion and deletion (where N is the size
 * of the store). Accepts duplicate entries but not null values.
 * 
 * @author gmcarstairs
 *
 * @param <T>
 *          any type providing <code>getBegin()</code> and <code>getEnd()</code>
 */
public class IntervalStore<T extends IntervalI>
        extends AbstractCollection<T>
        implements intervalstore.api.IntervalStoreI<T>
{
  private List<T> intervals;

  private boolean isTainted;

  private IntervalI[] orderedIntervalStarts;

  /**
   * Constructor
   */
  public IntervalStore()
  {
    intervals = new ArrayList<>();
  }

  class IntervalComparator implements Comparator<T>
  {

    @Override
    public int compare(IntervalI o1, IntervalI o2)
    {
 
          int order = Integer.compare(o1.getBegin(), o2.getBegin());
          if (order == 0)
          {
            /*
             * if tied on start position, longer length sorts to left
             * i.e. the negation of normal ordering by length
             */
            order = Integer.compare(o2.getEnd(), o1.getEnd());
          }
          return order;

    }

  };
  
  /**
   * Constructor given a list of intervals. Note that the list may get sorted as
   * a side-effect of calling this constructor.
   */
  public IntervalStore(List<T> intervals)
  {
    Collections.sort(this.intervals = intervals,
              new IntervalComparator());
      isTainted = true;
    findOverlaps(0, -1); // ensure this is ordered
  }

  /**
   * Adds one interval to the store.
   * 
   * @param interval
   */
  @Override
  public boolean add(T interval)
  {
    if (interval == null)
    {
      return false;
    }

    synchronized (intervals)
    {
      int insertPosition = findFirstBegin(intervals, interval.getBegin());
      intervals.add(insertPosition, interval);
      isTainted = true;
      return true;
    }
  }

  @Override
  public void clear()
  {
    intervals.clear();
    orderedIntervalStarts = null;
    isTainted = true;
  }

  @Override
  public boolean contains(Object entry)
  {
    return listContains(intervals, entry);
  }

  protected int findFirstBegin(List<T> list, long pos)
  {
    int start = 0;
    int end = list.size() - 1;
    int matched = list.size();

    while (start <= end)
    {
      int mid = (start + end) / 2;
      if (list.get(mid).getBegin() >= pos)
      {
        matched = mid;
        end = mid - 1;
      }
      else
      {
        start = mid + 1;
      }
    }
    return matched;
  }

  protected int findFirstEnd(List<T> list, long pos)
  {
    int start = 0;
    int end = list.size() - 1;
    int matched = list.size();

    while (start <= end)
    {
      int mid = (start + end) / 2;
      if (list.get(mid).getEnd() >= pos)
      {
        matched = mid;
        end = mid - 1;
      }
      else
      {
        start = mid + 1;
      }
    }
    return matched;
  }

  /**
   * Adds non-nested intervals to the result list that lie within the target
   * range
   * 
   * @param from
   * @param to
   * @param result
   */
  protected void findIntervalOverlaps(long from, long to,
          List<T> result)
  {

    int startIndex = findFirstEnd(intervals, from);
    final int startIndex1 = startIndex;
    int i = startIndex1;
    while (i < intervals.size())
    {
      T sf = intervals.get(i);
      if (sf.getBegin() > to)
      {
        break;
      }
      if (sf.getBegin() <= to && sf.getEnd() >= from)
      {
        result.add(sf);
      }
      i++;
    }
  }

  @Override
  public List<T> findOverlaps(long start, long end)
  {

    List<T> result = new ArrayList<>();

    int n = intervals.size();
    switch (n)
    {
    case 0:
      return result;
    case 1:
      justCheckOne(intervals.get(0), start, end, result);
      return result;
    default:

      if (isTainted)
      {
        orderedIntervalStarts = intervals.toArray(new IntervalI[0]);
        linkFeatures(orderedIntervalStarts);
        isTainted = false;
      }
      break;
    }

    if (end < start)
    {
      // just ensuring not tainted -- fully loaded
      return result;
    }

    // (1) Find the closest feature to this position.

    int index = getClosestFeature(orderedIntervalStarts, start);
    IntervalI sf = (index < 0 ? null : orderedIntervalStarts[index]);

    // (2) Traverse the containedBy field, checking for overlap.

    while (sf != null)
    {
      if (sf.getEnd() >= start)
      {
        result.add((T) sf);
      }
      sf = sf.getContainedBy();
    }

    // (3) For an interval, find the last feature that starts in this interval,
    // and add all features up through that feature.

    if (end >= start)
    {
      // fill in with all features that start within this interval, fully
      // inclusive
      int index2 = getClosestFeature(orderedIntervalStarts, end);
      while (++index <= index2)
      {
        result.add((T) orderedIntervalStarts[index]);
      }

    }
    return result;
  }

  private int getClosestFeature(IntervalI[] l, long pos)
  {
    int low = 0;
    int high = l.length - 1;
    while (low <= high)
    {
      int mid = (low + high) >>> 1;
      IntervalI f = l[mid];
      switch (Long.signum(f.getBegin() - pos))
      {
      case -1:
        low = mid + 1;
        continue;
      case 1:
        high = mid - 1;
        continue;
      case 0:

        while (++mid <= high && l[mid].getBegin() == pos)
        {
          ;
        }
        return --mid;
      }
    }
    return (high < 0 ? -1 : high);
  }

  @SuppressWarnings("unchecked")
  public T getContainedBy(T sf, T sf0)
  {
    int begin = sf0.getBegin();
    while (sf != null)
    {
      if (begin <= sf.getEnd())
      {
        // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
        // + "\nFS in " + sf.getIndex1() + ":" + sf);
        return sf;
      }
      sf = (T) sf.getContainedBy();
    }
    return null;
  }

  @Override
  public int getDepth()
  {
    if (size() == 0)
    {
      return 0;
    }
    int maxDepth = 0;
    for (int i = intervals.size(); --i >= 0;)
    {
      T element = intervals.get(i);
      T container = element;
      int depth = 0;
      while ((container = (T) container.getContainedBy()) != null)
      {
        if (++depth > maxDepth && container == this)
        {
          maxDepth = depth;
          break;
        }
      }
    }
    return maxDepth;
  }

  @Override
  public boolean isValid()
  {
    for (int i = 0; i < intervals.size() - 1; i++)
    {
      T i1 = intervals.get(i);
      T i2 = intervals.get(i + 1);

      if (i2.getBegin() < i1.getBegin())
      {
        System.err.println("nonNested wrong start order : " + i1.toString()
                + ", " + i2.toString());
        return false;
      }
    }
    return true;
  }

  /**
   * Answers an iterator over the intervals in the store, with no particular
   * ordering guaranteed. The iterator does not support the optional
   * <code>remove</code> operation (throws
   * <code>UnsupportedOperationException</code> if attempted).
   */
  @Override
  public Iterator<T> iterator()
  {
    return intervals.iterator();

  }

  private void justCheckOne(T sf, long start, long end, List<T> result)
  {
    if (sf.getBegin() <= end && sf.getEnd() >= start)
    {
      result.add(sf);
    }
    return;
  }

  private void linkFeatures(IntervalI[] features)
  {
    int n = features.length;
    switch (n)
    {
    case 0:
      return;
    case 1:
      features[0].setIndex1(1);
      return;
    }
    int maxEnd = features[0].getEnd();
    for (int i = 1; i < n;)
    {
      T sf = (T) features[i];
      sf.setIndex1(++i);
      if (sf.getBegin() <= maxEnd)
      {
        sf.setContainedBy(getContainedBy((T) features[i - 2], sf));
      }
      if (sf.getEnd() > maxEnd)
      {
        maxEnd = sf.getEnd();
      }
    }

  }

  /**
   * Answers true if the list contains the interval, else false. This method is
   * optimised for the condition that the list is sorted on interval start
   * position ascending, and will give unreliable results if this does not hold.
   * 
   * @param intervals
   * @param entry
   * @return
   */
  protected boolean listContains(List<T> intervals, Object entry)
  {
    if (intervals == null || entry == null)
    {
      return false;
    }

    T interval = (T) entry;

    /*
     * locate the first entry in the list which does not precede the interval
     */
    int pos = findFirstBegin(intervals, interval.getBegin());
    int len = intervals.size();
    while (pos < len)
    {
      T sf = intervals.get(pos);
      if (sf.getBegin() > interval.getBegin())
      {
        return false; // no match found
      }
      if (sf.getEnd() == interval.getEnd() && sf.equals(interval))
      {
        return true;
      }
      pos++;
    }
    return false;
  }

  @Override
  public String prettyPrint()
  {
    return toString();
  }

  @Override
  public synchronized boolean remove(Object o)
  {
    if (o == null || !(o instanceof IntervalI))
    {
      return false;
    }

    T entry = (T) o;

    /*
     * try the non-nested positional intervals first
     */
    boolean removed = removeInterval(entry);
    if (removed)
    {
      isTainted = true;
    }

    return removed;

  }

  /**
   * Removes the given entry from the list of non-nested entries, returning true
   * if found and removed, or false if not found. Specifically, removes the
   * first item in the list for which <code>item.equals(entry)</code>.
   * 
   * @param entry
   * @return
   */
  protected boolean removeInterval(T entry)
  {
    /*
     * find the first interval that might match, i.e. whose 
     * start position is not less than the target range start
     * (NB inequality test ensures the first match if any is found)
     */
    int startIndex = findFirstBegin(intervals, entry.getBegin());

    /*
     * traverse intervals to look for a match
     */
    int from = entry.getBegin();
    int i = startIndex;
    int size = intervals.size();
    while (i < size)
    {
      T sf = intervals.get(i);
      if (sf.getBegin() > from)
      {
        break;
      }
      if (sf.equals(entry))
      {
        intervals.remove(i);
        return true;
      }
      i++;
    }
    return false;
  }

  @Override
  public int size()
  {
    return intervals.size();
  }

  @Override
  public String toString()
  {
    ensureFinalized();
    StringBuffer sb = new StringBuffer();

    return sb.toString();
  }

}