package jalview.datamodel.features;

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

/**
 * An adapted implementation of NCList as described in the paper
 * 
 * <pre>
 * todo
 * </pre>
 */
public class NCList<T extends ContiguousI>
{

  /*
   * a list, in start position order, of sublists of ranges ordered so 
   * that each contains (or is the same as) the one that follows it
   */
  private List<NCNode<T>> subranges;

  /*
   * a comparator to sort intervals by start position ascending, with
   * longer (enclosing) intervals preceding those they enclose 
   */
  Comparator<ContiguousI> intervalSorter = new RangeComparator(true);

  /**
   * Constructor given a list of things that are each located on a contiguous
   * interval. Note that the constructor may reorder the list.
   * <p>
   * We assume here that for each range, start &lt;= end. Behaviour for reverse
   * ordered ranges is undefined.
   * 
   * @param ranges
   */
  public NCList(List<T> ranges)
  {
    build(ranges);
  }

  /**
   * @param ranges
   */
  protected void build(List<T> ranges)
  {
    /*
     * sort by start ascending so that contained intervals 
     * follow their containing interval
     */
    Collections.sort(ranges, intervalSorter);

    List<SubList> sublists = findSubranges(ranges);

    subranges = new ArrayList<NCNode<T>>();

    /*
     * convert each subrange to an NCNode consisting of a range and
     * (possibly) its contained NCList
     */
    for (SubList sublist : sublists)
    {
      subranges.add(new NCNode<T>(ranges.subList(sublist.startIndex,
              sublist.endIndex + 1)));
    }
    sublists.clear();
  }

  public NCList(T entry)
  {
    List<T> ranges = new ArrayList<T>();
    ranges.add(entry);
    build(ranges);
  }

  /**
   * Traverses the sorted ranges to identify sublists, within which each
   * interval contains the one that follows it
   * 
   * @param ranges
   * @return
   */
  protected List<SubList> findSubranges(List<T> ranges)
  {
    List<SubList> sublists = new ArrayList<SubList>();
    
    int listStartIndex = 0;
    long lastEndPos = Long.MAX_VALUE;

    for (int i = 0; i < ranges.size(); i++)
    {
      ContiguousI nextInterval = ranges.get(i);
      long nextStart = nextInterval.getBegin();
      long nextEnd = nextInterval.getEnd();
      if (nextStart > lastEndPos || nextEnd > lastEndPos)
      {
        /*
         * this interval is not contained in the preceding one 
         * close off the last sublist
         */
        sublists.add(new SubList(listStartIndex, i - 1));
        listStartIndex = i;
      }
      lastEndPos = nextEnd;
    }

    sublists.add(new SubList(listStartIndex, ranges.size() - 1));
    return sublists;
  }

  /**
   * Adds one entry to the stored set
   * 
   * @param entry
   */
  public synchronized void add(T entry)
  {
    long start = entry.getBegin();
    long end = entry.getEnd();

    /*
     * cases:
     * - precedes all subranges: add as NCNode on front of list
     * - follows all subranges: add as NCNode on end of list
     * - enclosed by a subrange - add recursively to subrange
     * - encloses one or more subranges - push them inside it
     * - none of the above - add as a new node and resort nodes list (?)
     */

    /*
     * find the first subrange whose end does not precede entry's start
     */
    int candidateIndex = findFirstOverlap(start);
    if (candidateIndex == -1)
    {
      /*
       * all subranges precede this one - add it on the end
       */
      subranges.add(new NCNode<T>(entry));
      return;
    }

    /*
     * search for maximal span of subranges i-k that the new entry
     * encloses; or a subrange that encloses the new entry
     */
    int i = candidateIndex;
    boolean enclosing = false;
    boolean overlapping = false;

    for (int j = candidateIndex; j < subranges.size(); j++)
    {
      NCNode<T> subrange = subranges.get(j);

      if (end < subrange.getStart() && !overlapping)
      {
        /*
         * new entry lies between subranges j-1 j
         */
        subranges.add(j, new NCNode<T>(entry));
        return;
      }

      if (subrange.getStart() <= start && subrange.getEnd() >= end)
      {
        /*
         * push new entry inside this subrange as it encloses it
         */
        subrange.add(entry);
        return;
      }
      
      if (start <= subrange.getStart())
      {
        if (end >= subrange.getEnd())
        {
          /*
           * new entry encloses this subrange (and possibly preceding ones);
           * continue to find the maximal list it encloses
           */
          enclosing = true;
          continue;
        }
        else
        {
          /*
           * entry spans from before this subrange to inside it
           */
          if (enclosing)
          {
            /*
             * entry encloses one or more preceding subranges
             */
            addEnclosingRange(entry, i, j - 1);
            return;
          }
          else
          {
            /*
             * entry spans two subranges but doesn't enclose any
             * so just add it 
             */
            subranges.add(j, new NCNode<T>(entry));
            return;
          }
        }
      }
    }
  }
  
  /**
   * Update the tree so that the range of the new entry encloses subranges i to
   * j (inclusive). That is, replace subranges i-j with a new subrange that
   * contains them.
   * 
   * @param entry
   * @param i
   * @param j
   */
  protected synchronized void addEnclosingRange(T entry, int i, int j)
  {
    // TODO how to rebuild the subranges as an NCList?

  }

  /**
   * Returns a (possibly empty) list of items whose extent overlaps the given
   * range
   * 
   * @param from
   *          start of overlap range (inclusive)
   * @param to
   *          end of overlap range (inclusive)
   * @return
   */
  public List<T> findOverlaps(long from, long to)
  {
    List<T> result = new ArrayList<T>();

    findOverlaps(from, to, result);
    
    return result;
  }

  /**
   * Recursively searches the NCList adding any items that overlap the from-to
   * range to the result list
   * 
   * @param from
   * @param to
   * @param result
   */
  protected void findOverlaps(long from, long to,
 List<T> result)
  {
    /*
     * find the first sublist that might overlap, i.e. 
     * the first whose end position is >= from
     */
    int candidateIndex = findFirstOverlap(from);

    if (candidateIndex == -1)
    {
      return;
    }

    for (int i = candidateIndex; i < subranges.size(); i++)
    {
      NCNode<T> candidate = subranges.get(i);
      if (candidate.getStart() > to)
      {
        /*
         * we are past the end of our target range
         */
        break;
      }
      candidate.addOverlaps(from, to, result);
    }

  }

  /**
   * Search subranges for the first one whose end position is not before the
   * target range's start position, i.e. the first one that may overlap the
   * target range. Returns the index in the list of the first such range found,
   * or -1 if none found.
   * 
   * @param from
   * @return
   */
  protected int findFirstOverlap(long from)
  {
    // TODO binary search
    // for now quick cheat linear search
    int i = 0;
    if (subranges != null)
    {
      for (NCNode<T> subrange : subranges)
      {
        if (subrange.getEnd() >= from)
        {
          return i;
        }
        i++;
      }
    }
    return -1;
  }

  /**
   * Formats the tree as a bracketed list e.g.
   * 
   * <pre>
   * [1-100 [10-30 [10-20]], 15-30 [20-20]]
   * </pre>
   */
  @Override
  public String toString()
  {
    return subranges.toString();
  }
}