src/jalview/datamodel/features/FeatureStoreImpl.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.datamodel.features;
  22
  23 import jalview.datamodel.SequenceFeature;
  24
  25 import java.util.ArrayList;
  26 import java.util.List;
  27
  28 import intervalstore.api.IntervalStoreI;
  29 import intervalstore.impl.BinarySearcher;
  30
  31 /**
  32  * A data store for a set of sequence features that supports efficient lookup of
  33  * features overlapping a given range. Intended for (but not limited to) storage
  34  * of features for one sequence and feature type.
  35  *
  36  * @author gmcarstairs
  37  *
  38  */
  39 public class FeatureStoreImpl extends FeatureStore
  40 {
  41
  42   /**
  43    * Default constructor uses NCList
  44    */
  45   public FeatureStoreImpl()
  46   {
  47     this(true);
  48   }
  49
  50   public FeatureStoreImpl(boolean useNCList)
  51   {
  52     features = (useNCList ? new intervalstore.impl.IntervalStore<>()
  53             : new intervalstore.nonc.IntervalStore<>(false));
  54   }
  55
  56   /**
  57    * Add a contact feature to the lists that hold them ordered by start (first
  58    * contact) and by end (second contact) position, ensuring the lists remain
  59    * ordered, and returns true. This method allows duplicate features to be
  60    * added, so test before calling to avoid this.
  61    *
  62    * @param feature
  63    * @return
  64    */
  65   @Override
  66   protected synchronized boolean addContactFeature(SequenceFeature feature)
  67   {
  68     if (contactFeatureStarts == null)
  69     {
  70       contactFeatureStarts = new ArrayList<>();
  71       contactFeatureEnds = new ArrayList<>();
  72     }
  73
  74     /*
  75      * insert into list sorted by start (first contact position):
  76      * binary search the sorted list to find the insertion point
  77      */
  78     int insertPosition = findFirstBeginStatic(contactFeatureStarts,
  79             feature.getBegin());
  80     contactFeatureStarts.add(insertPosition, feature);
  81
  82     /*
  83      * insert into list sorted by end (second contact position):
  84      * binary search the sorted list to find the insertion point
  85      */
  86     insertPosition = findFirstEndStatic(contactFeatureEnds,
  87             feature.getEnd());
  88     contactFeatureEnds.add(insertPosition, feature);
  89
  90     return true;
  91   }
  92
  93   /**
  94    * Adds one feature to the IntervalStore that can manage nested features
  95    * (creating the IntervalStore if necessary)
  96    */
  97   @Override
  98   protected synchronized void addPositionalFeature(SequenceFeature feature)
  99   {
 100     features.add(feature);
 101   }
 102
 103   /**
 104    * Adds contact features to the result list where either the second or the
 105    * first contact position lies within the target range
 106    *
 107    * @param from
 108    * @param to
 109    * @param result
 110    */
 111   @Override
 112   protected void findContactFeatures(long from, long to,
 113           List<SequenceFeature> result)
 114   {
 115     if (contactFeatureStarts != null)
 116     {
 117       findContactStartOverlaps(from, to, result);
 118       findContactEndOverlaps(from, to, result);
 119     }
 120   }
 121
 122   @Override
 123   protected boolean containsFeature(SequenceFeature feature)
 124   {
 125     return features.contains(feature);
 126   }
 127
 128   /**
 129    * Adds to the result list any contact features whose end (second contact
 130    * point), but not start (first contact point), lies in the query from-to
 131    * range
 132    *
 133    * @param from
 134    * @param to
 135    * @param result
 136    */
 137
 138   private void findContactEndOverlaps(long from, long to,
 139           List<SequenceFeature> result)
 140   {
 141     /*
 142      * find the first contact feature (if any)
 143      * whose end point is not before the target range
 144      */
 145     int index = findFirstEndStatic(contactFeatureEnds, from);
 146
 147     int n = contactFeatureEnds.size();
 148     while (index < n)
 149     {
 150       SequenceFeature sf = contactFeatureEnds.get(index);
 151       if (!sf.isContactFeature())
 152       {
 153         System.err.println("Error! non-contact feature type " + sf.getType()
 154                 + " in contact features list");
 155         index++;
 156         continue;
 157       }
 158
 159       int begin = sf.getBegin();
 160       if (begin >= from && begin <= to)
 161       {
 162         /*
 163          * this feature's first contact position lies in the search range
 164          * so we don't include it in results a second time
 165          */
 166         index++;
 167         continue;
 168       }
 169
 170       if (sf.getEnd() > to)
 171       {
 172         /*
 173          * this feature (and all following) has end point after the target range
 174          */
 175         break;
 176       }
 177
 178       /*
 179        * feature has end >= from and end <= to
 180        * i.e. contact end point lies within overlap search range
 181        */
 182       result.add(sf);
 183       index++;
 184     }
 185   }
 186
 187   /**
 188    * Adds contact features whose start position lies in the from-to range to the
 189    * result list
 190    *
 191    * @param from
 192    * @param to
 193    * @param result
 194    */
 195
 196   private void findContactStartOverlaps(long from, long to,
 197           List<SequenceFeature> result)
 198   {
 199     int index = findFirstBegin(contactFeatureStarts, from);
 200
 201     while (index < contactFeatureStarts.size())
 202     {
 203       SequenceFeature sf = contactFeatureStarts.get(index);
 204       if (!sf.isContactFeature())
 205       {
 206         System.err.println("Error! non-contact feature " + sf.toString()
 207                 + " in contact features list");
 208         index++;
 209         continue;
 210       }
 211       if (sf.getBegin() > to)
 212       {
 213         /*
 214          * this feature's start (and all following) follows the target range
 215          */
 216         break;
 217       }
 218
 219       /*
 220        * feature has begin >= from and begin <= to
 221        * i.e. contact start point lies within overlap search range
 222        */
 223       result.add(sf);
 224       index++;
 225     }
 226   }
 227
 228   /**
 229    * Returns a (possibly empty) list of features whose extent overlaps the given
 230    * range. The returned list is not ordered. Contact features are included if
 231    * either of the contact points lies within the range.
 232    *
 233    * @param start
 234    *          start position of overlap range (inclusive)
 235    * @param end
 236    *          end position of overlap range (inclusive)
 237    * @param result
 238    *          ignored
 239    * @return
 240    */
 241
 242   @Override
 243   public List<SequenceFeature> findOverlappingFeatures(long start, long end,
 244           List<SequenceFeature> result)
 245   {
 246     result = new ArrayList<>();
 247     findContactFeatures(start, end, result);
 248     findOverlaps(start, end, result);
 249     return result;
 250   }
 251
 252   private void findOverlaps(long start, long end,
 253           List<SequenceFeature> result)
 254   {
 255     result.addAll(((IntervalStoreI<SequenceFeature>) features)
 256             .findOverlaps(start, end));
 257   }
 258
 259   @Override
 260   protected int findFirstBegin(List<SequenceFeature> list, long pos)
 261   {
 262     return findFirstBeginStatic(list, pos);
 263   }
 264
 265   /**
 266    * Possibly a bit faster using a static method.
 267    *
 268    * @param list
 269    * @param pos
 270    * @return
 271    */
 272   private static int findFirstBeginStatic(List<SequenceFeature> list,
 273           long pos)
 274   {
 275     return BinarySearcher.findFirst(list, f -> f.getBegin() >= pos);
 276   }
 277
 278   @Override
 279   protected int findFirstEnd(List<SequenceFeature> list, long pos)
 280   {
 281     return findFirstEndStatic(list, pos);
 282   }
 283
 284   /**
 285    * Possibly a bit faster using a static method.
 286    *
 287    * @param list
 288    * @param pos
 289    * @return
 290    */
 291   private static int findFirstEndStatic(List<SequenceFeature> list,
 292           long pos)
 293   {
 294     return BinarySearcher.findFirst(list, f -> f.getEnd() >= pos);
 295   }
 296
 297   @Override
 298   protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
 299   {
 300     return features.remove(sf);
 301   }
 302
 303 }