/*
 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
 * Copyright (C) $$Year-Rel$$ The Jalview Authors
 * 
 * This file is part of Jalview.
 * 
 * Jalview is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License 
 * as published by the Free Software Foundation, either version 3
 * of the License, or (at your option) any later version.
 *  
 * Jalview is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty 
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
 * PURPOSE.  See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
 * The Jalview Authors are detailed in the 'AUTHORS' file.
 */
package jalview.datamodel.features;

import jalview.datamodel.SequenceFeature;

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

import intervalstore.nonc.IntervalStore;

/**
 * An adaption of FeatureStore that is efficient and lightweight, accelerating
 * processing speed in JavaScript.
 * 
 * It could be used in Java as well, with significant acceleration, but all this
 * is so fast anyway that it probably will not be noticed in Java to speed it up
 * by a factor of two or three. So for now, at least, this implementation is
 * just in JavaScript. The flag for this is in SequenceFeatures.
 * 
 * This implementation uses the IntervalStore developed by Bob Hanson, found at
 * https://github.com/BobHanson/IntervalStoreJ, forked from the one developed by
 * Mungo Carstairs at https://github.com/bartongroup/IntervalStoreJ.
 * 
 * See the discussion folder at https://github.com/BobHanson/IntervalStoreJ for
 * details.
 * 
 * @author gmcarstairs
 * @author Bob Hanson 2019.08.03-2019.08.16
 *
 */
public class FeatureStoreJS extends FeatureStore
{
  private IntervalStore<SequenceFeature> featureStore;

  public FeatureStoreJS()
  {
    // the only reference to features field in this class -- for the superclass

    // linked-list no-NCList IntervalStore with presort

    features = featureStore = new IntervalStore<>(true);
  }

  /**
   * Add a contact feature to the lists that hold them ordered by start (first
   * contact) and by end (second contact) position, ensuring the lists remain
   * ordered. This method allows duplicate features to be added, so test before
   * calling to avoid this.
   * 
   * @param feature
   * @return true
   */
  @Override
  protected synchronized boolean addContactFeature(SequenceFeature feature)
  {
    if (contactFeatureStarts == null)
    {
      contactFeatureStarts = new ArrayList<>();
      contactFeatureEnds = new ArrayList<>();
    }
    contactFeatureStarts.add(
            findFirstBegin(contactFeatureStarts, feature.begin), feature);
    contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
            feature);
    return true;
  }


  /**
   * Add a feature to the IntervalStore, not allowing for duplicates.
   *
   *
   * @return false if could not add it (late check for duplicate)
   */
  @Override
  protected synchronized boolean addPositionalFeature(
          SequenceFeature feature)
  {
    return featureStore.add(feature, false);
  }

  /**
   * Initial check in FeatureStore.add(feature) that in other implementations
   * does a containment check, but in this implementation just returns false to
   * indicate that we should continue. This implementation will do this check as
   * part of the add() method for greater efficiency (one binary search instead
   * of two).
   * 
   * @return false -- meaning "maybe not contained; continue adding"
   */
  @Override
  protected boolean checkContainsPositionalFeatureForAdd(
          SequenceFeature feature)
  {
    return false;
  }

  /**
   * Check to see if a feature (or its equivalent based on
   * IntervalI.equalsInterval) is already in this store. This method should be
   * avoided except when necessary, as it involves a binary search with identity
   * check.
   * 
   * @return true if this feature or its equivalent (based on equalsInterval) is
   *         present already in the collection.
   */
  @Override
  protected boolean containsFeature(SequenceFeature feature)
  {
    return featureStore.contains(feature);
  }

  @Override
  protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
  {
    return featureStore.remove(sf);
  }

  /**
   * Add contact features to the result list where either the second or the
   * first contact position lies within the target range, inclusively.
   * 
   * @param from
   * @param to
   * @param result
   */
  @Override
  protected void findContactFeatures(long from, long to,
          List<SequenceFeature> result)
  {
    getContactStartOverlaps(from, to, result);
    getContactEndOverlaps(from, to, result);
  }

  /**
   * Locate the first feature start in a standard ArrayList that is at or after
   * this position.
   * 
   */

  @Override
  protected int findFirstBegin(List<SequenceFeature> list, long pos)
  {
    int matched = list.size();
    int end = matched - 1;
    int start = (end < 0 || list.get(end).begin < pos ? matched : 0);
    while (start <= end)
    {
      int mid = (start + end) / 2;
      if (list.get(mid).begin >= pos)
      {
        matched = mid;
        end = mid - 1;
      }
      else
      {
        start = mid + 1;
      }
    }
    return matched;
  }

  /**
   * Locate the feature end in a standard ArrayList that is after or at this
   * position.
   * 
   */

  @Override
  protected int findFirstEnd(List<SequenceFeature> list, long pos)
  {
    int matched = list.size();
    int end = matched - 1;
    int start = 0;
    while (start <= end)
    {
      int mid = (start + end) / 2;
      if (list.get(mid).end >= pos)
      {
        matched = mid;
        end = mid - 1;
      }
      else
      {
        start = mid + 1;
      }
    }
    return matched;
  }

  /**
   * Returns a (possibly empty) list of features whose extent overlaps the given
   * range. The returned list is ordered as follows:
   * 
   * (1) ContactFeature starts
   * 
   * (2) ContactFeature ends (that are not also starts)
   * 
   * (3) noncontact SequenceFeatures, in reverse start order
   * 
   * (This last reverse order is for efficiency in processing only.)
   * 
   * 
   * 
   * @param start
   *          start position of overlap range (inclusive)
   * @param end
   *          end position of overlap range (inclusive)
   * 
   * @param result
   *          optional result list; for highest efficiency, provide this
   *          parameter
   * @return result same as result parameter, or a new ArrayList if that is null
   */

  @Override
  public List<SequenceFeature> findOverlappingFeatures(long start, long end,
          List<SequenceFeature> result)
  {
    if (result == null)
    {
      result = new ArrayList<>();
    }
    if (contactFeatureStarts != null)
    {
      if (start == end)
      {
        getContactPoints(contactFeatureStarts, start, result, true);
        getContactPoints(contactFeatureEnds, start, result, false);
      }
      else
      {
        findContactFeatures(start, end, result);
      }
    }
    if (featureStore.size() > 0)
    {
      featureStore.findOverlaps(start, end, result);
    }
    return result;
  }

  /**
   * Adds to the result list any contact features having end (second contact
   * point), but not start (first contact point), in the query from-to range
   * 
   * @param from
   * @param to
   * @param result
   */

  private void getContactEndOverlaps(long from, long to,
          List<SequenceFeature> result)
  {
    // find the first contact feature (if any)
    // with end point not before the target range

    for (int i = findFirstEnd(contactFeatureEnds,
            from), n = contactFeatureEnds.size(); i < n; i++)
    {
      SequenceFeature sf = contactFeatureEnds.get(i);
      if (sf.begin >= from && sf.begin <= to)
      {
        // this feature's first contact position lies in the search range
        // so we don't include it in results a second time
        continue;
      }

      if (sf.end > to)
      {
        // this feature (and all following) has end point after the target range
        break;
      }

      // feature has end >= from and end <= to
      // i.e. contact end point lies within overlap search range
      result.add(sf);
    }
  }

  /**
   * Binary search for contact start or end matching a specific position. This
   * efficient search was designed specifically for rapid return for the
   * OverviewPanel. It's implementation sped processing of that panel by 2300%.
   * 
   * @param l
   * @param pos
   * @param result
   * @param isStart
   * 
   * @author Bob Hanson 2019.07.30
   */
  private void getContactPoints(List<SequenceFeature> l, long pos,
          List<SequenceFeature> result, boolean isStart)
  {
    int low = 0;
    int high = l.size() - 1;
    while (low <= high)
    {
      int mid = (low + high) >>> 1;
      SequenceFeature f = l.get(mid);
      switch (Long.signum((isStart ? f.begin : f.end) - pos))
      {
      case -1:
        low = mid + 1;
        continue;
      case 1:
        high = mid - 1;
        continue;
      case 0:
        int m = mid;
        result.add(f);
        // could be "5" in 12345556788 ?
        while (++mid <= high && (f = l.get(mid)) != null
                && (isStart ? f.begin : f.end) == pos)
        {
          result.add(f);
        }
        while (--m >= low && (f = l.get(m)) != null
                && (isStart ? f.begin : f.end) == pos)
        {
          result.add(f);
        }
        return;
      }
    }
  }

  /**
   * Adds contact features whose start position lies in the from-to range to the
   * result list
   * 
   * @param from
   * @param to
   * @param result
   */

  private void getContactStartOverlaps(long from, long to,
          List<SequenceFeature> result)
  {
    for (int i = findFirstBegin(contactFeatureStarts,
            from), n = contactFeatureStarts.size(); i < n; i++)
    {
      SequenceFeature sf = contactFeatureStarts.get(i);
      if (sf.begin > to)
      {
        break;
      }
      result.add(sf);
    }
  }
}