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    * Adds contact features to the result list where either the second or the
  50    * first contact position lies within the target range
  51    *
  52    * @param from
  53    * @param to
  54    * @param result
  55    */
  56   @Override
  57   protected void findContactFeatures(long from, long to,
  58           List<SequenceFeature> result)
  59   {
  60     if (contactFeatureStarts != null)
  61     {
  62       findContactStartOverlaps(from, to, result);
  63       findContactEndOverlaps(from, to, result);
  64     }
  65   }
  66
  67   /**
  68    * Adds to the result list any contact features whose end (second contact
  69    * point), but not start (first contact point), lies in the query from-to
  70    * range
  71    *
  72    * @param from
  73    * @param to
  74    * @param result
  75    */
  76
  77   private void findContactEndOverlaps(long from, long to,
  78           List<SequenceFeature> result)
  79   {
  80     /*
  81      * find the first contact feature (if any)
  82      * whose end point is not before the target range
  83      */
  84     int index = BinarySearcher.findFirst(contactFeatureEnds,
  85             f -> f.getEnd() >= from);
  86
  87     int n = contactFeatureEnds.size();
  88     while (index < n)
  89     {
  90       SequenceFeature sf = contactFeatureEnds.get(index);
  91       if (!sf.isContactFeature())
  92       {
  93         System.err.println("Error! non-contact feature type " + sf.getType()
  94                 + " in contact features list");
  95         index++;
  96         continue;
  97       }
  98
  99       int begin = sf.getBegin();
 100       if (begin >= from && begin <= to)
 101       {
 102         /*
 103          * this feature's first contact position lies in the search range
 104          * so we don't include it in results a second time
 105          */
 106         index++;
 107         continue;
 108       }
 109
 110       if (sf.getEnd() > to)
 111       {
 112         /*
 113          * this feature (and all following) has end point after the target range
 114          */
 115         break;
 116       }
 117
 118       /*
 119        * feature has end >= from and end <= to
 120        * i.e. contact end point lies within overlap search range
 121        */
 122       result.add(sf);
 123       index++;
 124     }
 125   }
 126
 127   /**
 128    * Adds contact features whose start position lies in the from-to range to the
 129    * result list
 130    *
 131    * @param from
 132    * @param to
 133    * @param result
 134    */
 135
 136   private void findContactStartOverlaps(long from, long to,
 137           List<SequenceFeature> result)
 138   {
 139     int index = BinarySearcher.findFirst(contactFeatureStarts,
 140             f -> f.getBegin() >= from);
 141
 142     while (index < contactFeatureStarts.size())
 143     {
 144       SequenceFeature sf = contactFeatureStarts.get(index);
 145       if (!sf.isContactFeature())
 146       {
 147         System.err.println("Error! non-contact feature " + sf.toString()
 148                 + " in contact features list");
 149         index++;
 150         continue;
 151       }
 152       if (sf.getBegin() > to)
 153       {
 154         /*
 155          * this feature's start (and all following) follows the target range
 156          */
 157         break;
 158       }
 159
 160       /*
 161        * feature has begin >= from and begin <= to
 162        * i.e. contact start point lies within overlap search range
 163        */
 164       result.add(sf);
 165       index++;
 166     }
 167   }
 168
 169   /**
 170    * Returns a (possibly empty) list of features whose extent overlaps the given
 171    * range. The returned list is not ordered. Contact features are included if
 172    * either of the contact points lies within the range.
 173    *
 174    * @param start
 175    *          start position of overlap range (inclusive)
 176    * @param end
 177    *          end position of overlap range (inclusive)
 178    * @param result
 179    *          ignored
 180    * @return
 181    */
 182
 183   @Override
 184   public List<SequenceFeature> findOverlappingFeatures(long start, long end,
 185           List<SequenceFeature> result)
 186   {
 187     result = new ArrayList<>();
 188     findContactFeatures(start, end, result);
 189     findOverlaps(start, end, result);
 190     return result;
 191   }
 192
 193   private void findOverlaps(long start, long end,
 194           List<SequenceFeature> result)
 195   {
 196     result.addAll(((IntervalStoreI<SequenceFeature>) features)
 197             .findOverlaps(start, end));
 198     // TODO Auto-generated method stub
 199
 200   }
 201
 202 }