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 import intervalstore.impl.IntervalStore;
  31
  32 /**
  33  * A data store for a set of sequence features that supports efficient lookup of
  34  * features overlapping a given range. Intended for (but not limited to) storage
  35  * of features for one sequence and feature type.
  36  *
  37  * @author gmcarstairs
  38  *
  39  */
  40 public class FeatureStoreImpl extends FeatureStore
  41 {
  42
  43   public FeatureStoreImpl()
  44   {
  45     features = new IntervalStore<>();
  46   }
  47
  48   /**
  49    * Add a contact feature to the lists that hold them ordered by start (first
  50    * contact) and by end (second contact) position, ensuring the lists remain
  51    * ordered, and returns true. This method allows duplicate features to be
  52    * added, so test before calling to avoid this.
  53    *
  54    * @param feature
  55    * @return
  56    */
  57   @Override
  58   protected synchronized boolean addContactFeature(SequenceFeature feature)
  59   {
  60     if (contactFeatureStarts == null)
  61     {
  62       contactFeatureStarts = new ArrayList<>();
  63       contactFeatureEnds = new ArrayList<>();
  64     }
  65
  66     /*
  67      * insert into list sorted by start (first contact position):
  68      * binary search the sorted list to find the insertion point
  69      */
  70     int insertPosition = findFirstBeginStatic(contactFeatureStarts,
  71             feature.getBegin());
  72     contactFeatureStarts.add(insertPosition, feature);
  73
  74     /*
  75      * insert into list sorted by end (second contact position):
  76      * binary search the sorted list to find the insertion point
  77      */
  78     insertPosition = findFirstEndStatic(contactFeatureEnds,
  79             feature.getEnd());
  80     contactFeatureEnds.add(insertPosition, feature);
  81
  82     return true;
  83   }
  84
  85   /**
  86    * Adds one feature to the IntervalStore that can manage nested features
  87    * (creating the IntervalStore if necessary)
  88    */
  89   @Override
  90   protected synchronized void addNestedFeature(SequenceFeature feature)
  91   {
  92     features.add(feature);
  93   }
  94
  95   /**
  96    * Adds contact features to the result list where either the second or the
  97    * first contact position lies within the target range
  98    *
  99    * @param from
 100    * @param to
 101    * @param result
 102    */
 103   @Override
 104   protected void findContactFeatures(long from, long to,
 105           List<SequenceFeature> result)
 106   {
 107     if (contactFeatureStarts != null)
 108     {
 109       findContactStartOverlaps(from, to, result);
 110       findContactEndOverlaps(from, to, result);
 111     }
 112   }
 113
 114   @Override
 115   protected boolean containsFeature(SequenceFeature feature)
 116   {
 117     return features.contains(feature);
 118   }
 119
 120   /**
 121    * Adds to the result list any contact features whose end (second contact
 122    * point), but not start (first contact point), lies in the query from-to
 123    * range
 124    *
 125    * @param from
 126    * @param to
 127    * @param result
 128    */
 129
 130   private void findContactEndOverlaps(long from, long to,
 131           List<SequenceFeature> result)
 132   {
 133     /*
 134      * find the first contact feature (if any)
 135      * whose end point is not before the target range
 136      */
 137     int index = findFirstEndStatic(contactFeatureEnds, from);
 138
 139     int n = contactFeatureEnds.size();
 140     while (index < n)
 141     {
 142       SequenceFeature sf = contactFeatureEnds.get(index);
 143       if (!sf.isContactFeature())
 144       {
 145         System.err.println("Error! non-contact feature type " + sf.getType()
 146                 + " in contact features list");
 147         index++;
 148         continue;
 149       }
 150
 151       int begin = sf.getBegin();
 152       if (begin >= from && begin <= to)
 153       {
 154         /*
 155          * this feature's first contact position lies in the search range
 156          * so we don't include it in results a second time
 157          */
 158         index++;
 159         continue;
 160       }
 161
 162       if (sf.getEnd() > to)
 163       {
 164         /*
 165          * this feature (and all following) has end point after the target range
 166          */
 167         break;
 168       }
 169
 170       /*
 171        * feature has end >= from and end <= to
 172        * i.e. contact end point lies within overlap search range
 173        */
 174       result.add(sf);
 175       index++;
 176     }
 177   }
 178
 179   /**
 180    * Adds contact features whose start position lies in the from-to range to the
 181    * result list
 182    *
 183    * @param from
 184    * @param to
 185    * @param result
 186    */
 187
 188   private void findContactStartOverlaps(long from, long to,
 189           List<SequenceFeature> result)
 190   {
 191     int index = findFirstBegin(contactFeatureStarts, from);
 192
 193     while (index < contactFeatureStarts.size())
 194     {
 195       SequenceFeature sf = contactFeatureStarts.get(index);
 196       if (!sf.isContactFeature())
 197       {
 198         System.err.println("Error! non-contact feature " + sf.toString()
 199                 + " in contact features list");
 200         index++;
 201         continue;
 202       }
 203       if (sf.getBegin() > to)
 204       {
 205         /*
 206          * this feature's start (and all following) follows the target range
 207          */
 208         break;
 209       }
 210
 211       /*
 212        * feature has begin >= from and begin <= to
 213        * i.e. contact start point lies within overlap search range
 214        */
 215       result.add(sf);
 216       index++;
 217     }
 218   }
 219
 220   /**
 221    * Returns a (possibly empty) list of features whose extent overlaps the given
 222    * range. The returned list is not ordered. Contact features are included if
 223    * either of the contact points lies within the range.
 224    *
 225    * @param start
 226    *          start position of overlap range (inclusive)
 227    * @param end
 228    *          end position of overlap range (inclusive)
 229    * @param result
 230    *          ignored
 231    * @return
 232    */
 233
 234   @Override
 235   public List<SequenceFeature> findOverlappingFeatures(long start, long end,
 236           List<SequenceFeature> result)
 237   {
 238     result = new ArrayList<>();
 239     findContactFeatures(start, end, result);
 240     findOverlaps(start, end, result);
 241     return result;
 242   }
 243
 244   private void findOverlaps(long start, long end,
 245           List<SequenceFeature> result)
 246   {
 247     result.addAll(((IntervalStoreI<SequenceFeature>) features)
 248             .findOverlaps(start, end));
 249   }
 250
 251   @Override
 252   protected int findFirstBegin(List<SequenceFeature> list, long pos)
 253   {
 254     return findFirstBeginStatic(list, pos);
 255   }
 256
 257   /**
 258    * Possibly a bit faster using a static method.
 259    *
 260    * @param list
 261    * @param pos
 262    * @return
 263    */
 264   private static int findFirstBeginStatic(List<SequenceFeature> list,
 265           long pos)
 266   {
 267     return BinarySearcher.findFirst(list, f -> f.getBegin() >= pos);
 268   }
 269
 270   @Override
 271   protected int findFirstEnd(List<SequenceFeature> list, long pos)
 272   {
 273     return findFirstEndStatic(list, pos);
 274   }
 275
 276   /**
 277    * Possibly a bit faster using a static method.
 278    *
 279    * @param list
 280    * @param pos
 281    * @return
 282    */
 283   private static int findFirstEndStatic(List<SequenceFeature> list,
 284           long pos)
 285   {
 286     return BinarySearcher.findFirst(list, f -> f.getEnd() >= pos);
 287   }
 288
 289 }