/*
 * 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.impl.BinarySearcher;

/**
 * A data store for a set of sequence features that supports efficient lookup of
 * features overlapping a given range. Intended for (but not limited to) storage
 * of features for one sequence and feature type.
 * 
 * @author gmcarstairs
 *
 */
public class FeatureStoreImpl extends FeatureStore
{

  public FeatureStoreImpl()
  {
    super();
  }

  public FeatureStoreImpl(int option)
  {
    super(option);
  }

  /**
   * 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, and returns true. This method allows duplicate features to be
   * added, so test before calling to avoid this.
   * 
   * @param feature
   * @return
   */
  @Override
  protected synchronized boolean addContactFeature(SequenceFeature feature)
  {
    if (contactFeatureStarts == null)
    {
      contactFeatureStarts = new ArrayList<>();
      contactFeatureEnds = new ArrayList<>();
    }

    /*
     * insert into list sorted by start (first contact position):
     * binary search the sorted list to find the insertion point
     */
    int insertPosition = findFirstBegin(contactFeatureStarts,
            feature.getBegin());
    contactFeatureStarts.add(insertPosition, feature);

    /*
     * insert into list sorted by end (second contact position):
     * binary search the sorted list to find the insertion point
     */
    insertPosition = findFirstEnd(contactFeatureEnds,
            feature.getEnd());
    contactFeatureEnds.add(insertPosition, feature);

    return true;
  }

  /**
   * Adds one feature to the IntervalStore that can manage nested features
   * (creating the IntervalStore if necessary)
   */
  @Override
  protected synchronized boolean addPositionalFeature(
          SequenceFeature feature)
  {
    return features.add(feature);
  }

  /**
   * Adds contact features to the result list where either the second or the
   * first contact position lies within the target range
   * 
   * @param from
   * @param to
   * @param result
   */
  @Override
  protected void findContactFeatures(long from, long to,
          List<SequenceFeature> result)
  {
    if (contactFeatureStarts != null)
    {
      findContactStartOverlaps(from, to, result);
      findContactEndOverlaps(from, to, result);
    }
  }

  @Override
  protected boolean containsFeature(SequenceFeature feature)
  {
    return features.contains(feature);
  }

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

  private void findContactEndOverlaps(long from, long to,
          List<SequenceFeature> result)
  {
    /*
     * find the first contact feature (if any) 
     * whose end point is not before the target range
     */
    int index = findFirstEnd(contactFeatureEnds, from);

    int n = contactFeatureEnds.size();
    while (index < n)
    {
      SequenceFeature sf = contactFeatureEnds.get(index);
      if (!sf.isContactFeature())
      {
        System.err.println("Error! non-contact feature type " + sf.getType()
                + " in contact features list");
        index++;
        continue;
      }

      int begin = sf.getBegin();
      if (begin >= from && begin <= to)
      {
        /*
         * this feature's first contact position lies in the search range
         * so we don't include it in results a second time
         */
        index++;
        continue;
      }

      if (sf.getEnd() > 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);
      index++;
    }
  }

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

  private void findContactStartOverlaps(long from, long to,
          List<SequenceFeature> result)
  {
    int index = findFirstBegin(contactFeatureStarts, from);

    while (index < contactFeatureStarts.size())
    {
      SequenceFeature sf = contactFeatureStarts.get(index);
      if (!sf.isContactFeature())
      {
        System.err.println("Error! non-contact feature " + sf.toString()
                + " in contact features list");
        index++;
        continue;
      }
      if (sf.getBegin() > to)
      {
        /*
         * this feature's start (and all following) follows the target range
         */
        break;
      }

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

  /**
   * Returns a (possibly empty) list of features whose extent overlaps the given
   * range. The returned list is not ordered. Contact features are included if
   * either of the contact points lies within the range.
   * 
   * @param start
   *          start position of overlap range (inclusive)
   * @param end
   *          end position of overlap range (inclusive)
   * @param result
   *          ignored
   * @return
   */

  @Override
  public List<SequenceFeature> findOverlappingFeatures(long start, long end,
          List<SequenceFeature> result)
  {
    result = new ArrayList<>();
    findContactFeatures(start, end, result);
    findOverlaps(start, end, result);
    return result;
  }

  private void findOverlaps(long start, long end,
          List<SequenceFeature> result)
  {
    result.addAll(features
            .findOverlaps(start, end));
  }

  @Override
  protected int findFirstBegin(List<SequenceFeature> list, long pos)
  {
    return BinarySearcher.findFirst(list, (int) pos,
            BinarySearcher.fbegin);
  }

  @Override
  protected int findFirstEnd(List<SequenceFeature> list, long pos)
  {
    return BinarySearcher.findFirst(list, (int) pos, BinarySearcher.fend);
  }

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

}