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 boolean addPositionalFeature(
  99           SequenceFeature feature)
 100   {
 101     return features.add(feature);
 102   }
 103
 104   /**
 105    * Adds contact features to the result list where either the second or the
 106    * first contact position lies within the target range
 107    *
 108    * @param from
 109    * @param to
 110    * @param result
 111    */
 112   @Override
 113   protected void findContactFeatures(long from, long to,
 114           List<SequenceFeature> result)
 115   {
 116     if (contactFeatureStarts != null)
 117     {
 118       findContactStartOverlaps(from, to, result);
 119       findContactEndOverlaps(from, to, result);
 120     }
 121   }
 122
 123   @Override
 124   protected boolean containsFeature(SequenceFeature feature)
 125   {
 126     return features.contains(feature);
 127   }
 128
 129   /**
 130    * Adds to the result list any contact features whose end (second contact
 131    * point), but not start (first contact point), lies in the query from-to
 132    * range
 133    *
 134    * @param from
 135    * @param to
 136    * @param result
 137    */
 138
 139   private void findContactEndOverlaps(long from, long to,
 140           List<SequenceFeature> result)
 141   {
 142     /*
 143      * find the first contact feature (if any)
 144      * whose end point is not before the target range
 145      */
 146     int index = findFirstEndStatic(contactFeatureEnds, from);
 147
 148     int n = contactFeatureEnds.size();
 149     while (index < n)
 150     {
 151       SequenceFeature sf = contactFeatureEnds.get(index);
 152       if (!sf.isContactFeature())
 153       {
 154         System.err.println("Error! non-contact feature type " + sf.getType()
 155                 + " in contact features list");
 156         index++;
 157         continue;
 158       }
 159
 160       int begin = sf.getBegin();
 161       if (begin >= from && begin <= to)
 162       {
 163         /*
 164          * this feature's first contact position lies in the search range
 165          * so we don't include it in results a second time
 166          */
 167         index++;
 168         continue;
 169       }
 170
 171       if (sf.getEnd() > to)
 172       {
 173         /*
 174          * this feature (and all following) has end point after the target range
 175          */
 176         break;
 177       }
 178
 179       /*
 180        * feature has end >= from and end <= to
 181        * i.e. contact end point lies within overlap search range
 182        */
 183       result.add(sf);
 184       index++;
 185     }
 186   }
 187
 188   /**
 189    * Adds contact features whose start position lies in the from-to range to the
 190    * result list
 191    *
 192    * @param from
 193    * @param to
 194    * @param result
 195    */
 196
 197   private void findContactStartOverlaps(long from, long to,
 198           List<SequenceFeature> result)
 199   {
 200     int index = findFirstBegin(contactFeatureStarts, from);
 201
 202     while (index < contactFeatureStarts.size())
 203     {
 204       SequenceFeature sf = contactFeatureStarts.get(index);
 205       if (!sf.isContactFeature())
 206       {
 207         System.err.println("Error! non-contact feature " + sf.toString()
 208                 + " in contact features list");
 209         index++;
 210         continue;
 211       }
 212       if (sf.getBegin() > to)
 213       {
 214         /*
 215          * this feature's start (and all following) follows the target range
 216          */
 217         break;
 218       }
 219
 220       /*
 221        * feature has begin >= from and begin <= to
 222        * i.e. contact start point lies within overlap search range
 223        */
 224       result.add(sf);
 225       index++;
 226     }
 227   }
 228
 229   /**
 230    * Returns a (possibly empty) list of features whose extent overlaps the given
 231    * range. The returned list is not ordered. Contact features are included if
 232    * either of the contact points lies within the range.
 233    *
 234    * @param start
 235    *          start position of overlap range (inclusive)
 236    * @param end
 237    *          end position of overlap range (inclusive)
 238    * @param result
 239    *          ignored
 240    * @return
 241    */
 242
 243   @Override
 244   public List<SequenceFeature> findOverlappingFeatures(long start, long end,
 245           List<SequenceFeature> result)
 246   {
 247     result = new ArrayList<>();
 248     findContactFeatures(start, end, result);
 249     findOverlaps(start, end, result);
 250     return result;
 251   }
 252
 253   private void findOverlaps(long start, long end,
 254           List<SequenceFeature> result)
 255   {
 256     result.addAll(((IntervalStoreI<SequenceFeature>) features)
 257             .findOverlaps(start, end));
 258   }
 259
 260   @Override
 261   protected int findFirstBegin(List<SequenceFeature> list, long pos)
 262   {
 263     return findFirstBeginStatic(list, pos);
 264   }
 265
 266   /**
 267    * Possibly a bit faster using a static method.
 268    *
 269    * @param list
 270    * @param pos
 271    * @return
 272    */
 273   private static int findFirstBeginStatic(List<SequenceFeature> list,
 274           long pos)
 275   {
 276     return BinarySearcher.findFirst(list, f -> f.getBegin() >= pos);
 277   }
 278
 279   @Override
 280   protected int findFirstEnd(List<SequenceFeature> list, long pos)
 281   {
 282     return findFirstEndStatic(list, pos);
 283   }
 284
 285   /**
 286    * Possibly a bit faster using a static method.
 287    *
 288    * @param list
 289    * @param pos
 290    * @return
 291    */
 292   private static int findFirstEndStatic(List<SequenceFeature> list,
 293           long pos)
 294   {
 295     return BinarySearcher.findFirst(list, f -> f.getEnd() >= pos);
 296   }
 297
 298   @Override
 299   protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
 300   {
 301     return features.remove(sf);
 302   }
 303
 304 }