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