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