src/jalview/datamodel/features/FeatureStoreJS.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 /**
  29  * An adaption of FeatureStore that is efficient and lightweight, accelerating
  30  * processing speed in JavaScript.
  31  *
  32  * @author gmcarstairs
  33  * @author Bob Hanson 2019.08.03
  34  *
  35  */
  36 public class FeatureStoreJS extends FeatureStore
  37 {
  38   boolean contactsTainted = true;
  39
  40   /**
  41    * internal reference to features as an ArrayList
  42    */
  43   private ArrayList<SequenceFeature> featureList;
  44
  45   /**
  46    * contact features ordered by first contact position
  47    */
  48   private SequenceFeature[] orderedFeatureStarts;
  49
  50   /**
  51    * indicates that we need to rebuild orderedFeatureStarts and reset index
  52    * fields
  53    */
  54   private boolean isTainted = true;
  55
  56   /**
  57    * Constructor
  58    */
  59   public FeatureStoreJS()
  60   {
  61     features = featureList = new ArrayList<>();
  62   }
  63
  64   /**
  65    * Add a contact feature to the lists that hold them ordered by start (first
  66    * contact) and by end (second contact) position, ensuring the lists remain
  67    * ordered, and returns true. This method allows duplicate features to be
  68    * added, so test before calling to avoid this.
  69    *
  70    * @param feature
  71    * @return
  72    */
  73   @Override
  74   protected synchronized boolean addContactFeature(SequenceFeature feature)
  75   {
  76     if (contactFeatureStarts == null)
  77     {
  78       contactFeatureStarts = new ArrayList<>();
  79       contactFeatureEnds = new ArrayList<>();
  80     }
  81     contactFeatureStarts.add(
  82             findFirstBegin(contactFeatureStarts, feature.begin), feature);
  83     contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
  84             feature);
  85     return true;
  86   }
  87
  88   // The following methods use a linked list of containment in SequenceFeature
  89   // rather than IntervalStore.
  90   //
  91   // There are two parts --- initialization, and overlap searching.
  92   //
  93   // Initialization involves two steps:
  94   //
  95   // (1) sorting of features by start position using a standard Array.sort with
  96   // Comparator.
  97   // (2) linking of features, effectively nesting them.
  98   //
  99   // Searching involves three steps:
 100   //
 101   // (1) binary search for a starting point within the sorted features array.
 102   // (2) traverse the linked lists with an end check to read out the
 103   // overlapped features at this position.
 104   // (3) For an interval, find the last feature that starts in this interval,
 105   // and add all features up through that feature.
 106   //
 107   // All of this is done with very simple standard methods.
 108
 109   // Initialization
 110
 111   /**
 112    * Adds one feature to the IntervalStore that can manage nested features
 113    * (creating the IntervalStore if necessary)
 114    */
 115   @Override
 116   protected synchronized void addPositionalFeature(SequenceFeature feature)
 117   {
 118     featureList.add(findFirstBegin(featureList, feature.begin), feature);
 119     isTainted = true;
 120   }
 121
 122   @Override
 123   protected boolean containsFeature(SequenceFeature feature)
 124   {
 125
 126     return getEquivalentFeatureIndex(featureList, feature) >= 0;
 127   }
 128
 129   @Override
 130   protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
 131   {
 132     int pos = getEquivalentFeatureIndex(featureList, sf);
 133     if (pos < 0)
 134     {
 135       return false;
 136     }
 137     featureList.remove(pos);
 138     return (isTainted = true);
 139   }
 140
 141   /**
 142    * Adds contact features to the result list where either the second or the
 143    * first contact position lies within the target range
 144    *
 145    * @param from
 146    * @param to
 147    * @param result
 148    */
 149   @Override
 150   protected void findContactFeatures(long from, long to,
 151           List<SequenceFeature> result)
 152   {
 153     getContactStartOverlaps(from, to, result);
 154     getContactEndOverlaps(from, to, result);
 155   }
 156
 157   @Override
 158   protected int findFirstBegin(List<SequenceFeature> list, long pos)
 159   {
 160     int start = 0;
 161     int end = list.size() - 1;
 162     int matched = list.size();
 163
 164     while (start <= end)
 165     {
 166       int mid = (start + end) / 2;
 167       if (list.get(mid).begin >= pos)
 168       {
 169         matched = mid;
 170         end = mid - 1;
 171       }
 172       else
 173       {
 174         start = mid + 1;
 175       }
 176     }
 177     return matched;
 178   }
 179
 180   @Override
 181   protected int findFirstEnd(List<SequenceFeature> list, long pos)
 182   {
 183     int start = 0;
 184     int end = list.size() - 1;
 185     int matched = list.size();
 186
 187     while (start <= end)
 188     {
 189       int mid = (start + end) / 2;
 190       if (list.get(mid).end >= pos)
 191       {
 192         matched = mid;
 193         end = mid - 1;
 194       }
 195       else
 196       {
 197         start = mid + 1;
 198       }
 199     }
 200     return matched;
 201   }
 202
 203   /**
 204    * Returns a (possibly empty) list of features whose extent overlaps the given
 205    * range. The returned list is not ordered. Contact features are included if
 206    * either of the contact points lies within the range.
 207    *
 208    * @param start
 209    *          start position of overlap range (inclusive)
 210    * @param end
 211    *          end position of overlap range (inclusive)
 212    * @return
 213    */
 214
 215   @Override
 216   public List<SequenceFeature> findOverlappingFeatures(long start, long end,
 217           List<SequenceFeature> result)
 218   {
 219     if (result == null)
 220     {
 221       result = new ArrayList<>();
 222     }
 223     if (contactFeatureStarts != null)
 224     {
 225       if (start == end)
 226       {
 227         getContactPoints(contactFeatureStarts, start, result, true);
 228         getContactPoints(contactFeatureEnds, start, result, false);
 229       }
 230       else
 231       {
 232         findContactFeatures(start, end, result);
 233       }
 234     }
 235     if (featureList.size() > 0)
 236     {
 237       getOverlaps(start, end, result);
 238     }
 239     return result;
 240   }
 241
 242   /**
 243    * A binary search identical to the one used for contact start/end, but here
 244    * we return the feature itself. Unlike Collection.BinarySearch, all we have
 245    * to be is close, not exact, and we make sure if there is a string of
 246    * identical starts, then we slide to the end so that we can check all of
 247    * them.
 248    *
 249    * @param l
 250    * @param pos
 251    * @return
 252    */
 253   private int getClosestFeature(SequenceFeature[] l, long pos)
 254   {
 255     int low = 0;
 256     int high = l.length - 1;
 257     while (low <= high)
 258     {
 259       int mid = (low + high) >>> 1;
 260       SequenceFeature f = l[mid];
 261       switch (Long.signum(f.begin - pos))
 262       {
 263       case -1:
 264         low = mid + 1;
 265         continue;
 266       case 1:
 267         high = mid - 1;
 268         continue;
 269       case 0:
 270
 271         while (++mid <= high && l[mid].begin == pos)
 272         {
 273           ;
 274         }
 275         return --mid;
 276       }
 277     }
 278     return (high < 0 ? -1 : high);
 279   }
 280
 281   /**
 282    * Adds to the result list any contact features whose end (second contact
 283    * point), but not start (first contact point), lies in the query from-to
 284    * range
 285    *
 286    * @param from
 287    * @param to
 288    * @param result
 289    */
 290
 291   private void getContactEndOverlaps(long from, long to,
 292           List<SequenceFeature> result)
 293   {
 294     // find the first contact feature (if any)
 295     // with end point not before the target range
 296
 297     for (int i = findFirstEnd(contactFeatureEnds,
 298             from), n = contactFeatureEnds.size(); i < n; i++)
 299     {
 300       SequenceFeature sf = contactFeatureEnds.get(i);
 301       if (sf.begin >= from && sf.begin <= to)
 302       {
 303         // this feature's first contact position lies in the search range
 304         // so we don't include it in results a second time
 305         continue;
 306       }
 307
 308       if (sf.end > to)
 309       {
 310         // this feature (and all following) has end point after the target range
 311         break;
 312       }
 313
 314       // feature has end >= from and end <= to
 315       // i.e. contact end point lies within overlap search range
 316       result.add(sf);
 317     }
 318   }
 319
 320   /**
 321    * Binary search for contact start or end at a given (Overview) position.
 322    *
 323    * @param l
 324    * @param pos
 325    * @param result
 326    * @param isStart
 327    *
 328    * @author Bob Hanson 2019.07.30
 329    */
 330   private void getContactPoints(List<SequenceFeature> l, long pos,
 331           List<SequenceFeature> result, boolean isStart)
 332   {
 333     int low = 0;
 334     int high = l.size() - 1;
 335     while (low <= high)
 336     {
 337       int mid = (low + high) >>> 1;
 338       SequenceFeature f = l.get(mid);
 339       switch (Long.signum((isStart ? f.begin : f.end) - pos))
 340       {
 341       case -1:
 342         low = mid + 1;
 343         continue;
 344       case 1:
 345         high = mid - 1;
 346         continue;
 347       case 0:
 348         int m = mid;
 349         result.add(f);
 350         // could be "5" in 12345556788 ?
 351         while (++mid <= high && (f = l.get(mid)) != null
 352                 && (isStart ? f.begin : f.end) == pos)
 353         {
 354           result.add(f);
 355         }
 356         while (--m >= low && (f = l.get(m)) != null
 357                 && (isStart ? f.begin : f.end) == pos)
 358         {
 359           result.add(f);
 360         }
 361         return;
 362       }
 363     }
 364   }
 365
 366   /**
 367    * Adds contact features whose start position lies in the from-to range to the
 368    * result list
 369    *
 370    * @param from
 371    * @param to
 372    * @param result
 373    */
 374
 375   private void getContactStartOverlaps(long from, long to,
 376           List<SequenceFeature> result)
 377   {
 378     for (int i = findFirstBegin(contactFeatureStarts,
 379             from), n = contactFeatureStarts.size(); i < n; i++)
 380     {
 381       SequenceFeature sf = contactFeatureStarts.get(i);
 382       if (sf.begin > to)
 383       {
 384         break;
 385       }
 386       result.add(sf);
 387     }
 388   }
 389
 390   /**
 391    * Since we are traversing the sorted feature array in a forward direction,
 392    * all elements prior to the one we are working on have been fully linked. All
 393    * we are doing is following those links until we find the first array feature
 394    * with a containedBy element that has an end &gt;= our begin point. It is
 395    * generally a very short list -- maybe one or two depths. But it might be
 396    * more than that.
 397    *
 398    * @param sf
 399    * @param sf0
 400    * @return
 401    */
 402   private SequenceFeature getContainedBy(SequenceFeature sf,
 403           SequenceFeature sf0)
 404   {
 405     int begin = sf0.begin;
 406     while (sf != null)
 407     {
 408       if (begin <= sf.end)
 409       {
 410         System.out.println("\nFS found " + sf0 + "\nFS in " + sf);
 411         return sf;
 412       }
 413       sf = sf.containedBy;
 414     }
 415     return null;
 416   }
 417
 418   /**
 419    * Fast find of known features already on the list; slower removal of
 420    * equivalent feature, not necessarily identical.
 421    *
 422    * @param feature
 423    * @return 0-based index for this feature in featureList
 424    */
 425   @Override
 426   protected int getEquivalentFeatureIndex(List<SequenceFeature> list,
 427           SequenceFeature feature)
 428   {
 429     int pos = feature.index1 - 1;
 430     if (!isTainted && pos >= 0)
 431     {
 432       return pos;
 433     }
 434     return super.getEquivalentFeatureIndex(list, feature);
 435   }
 436
 437   /**
 438    * Find all overlaps; special case when there is only one feature. The
 439    * required array of start-sorted SequenceFeature is created lazily.
 440    *
 441    * @param start
 442    * @param end
 443    * @param result
 444    */
 445   private void getOverlaps(long start, long end,
 446           List<SequenceFeature> result)
 447   {
 448     int n = featureList.size();
 449     switch (n)
 450     {
 451     case 0:
 452       return;
 453     case 1:
 454       justCheckOne(featureList.get(0), start, end, result);
 455       return;
 456     default:
 457       if (isTainted)
 458       {
 459         orderedFeatureStarts = featureList
 460                 .toArray(new SequenceFeature[featureList.size()]);
 461         linkFeatures(orderedFeatureStarts);
 462         isTainted = false;
 463       }
 464       break;
 465     }
 466
 467     // (1) Find the closest feature to this position.
 468
 469     int index = getClosestFeature(orderedFeatureStarts, start);
 470     SequenceFeature sf = (index < 0 ? null : orderedFeatureStarts[index]);
 471
 472     // (2) Traverse the containedBy field, checking for overlap.
 473
 474     while (sf != null)
 475     {
 476       if (sf.end >= start)
 477       {
 478         result.add(sf);
 479       }
 480       sf = sf.containedBy;
 481     }
 482
 483     // (3) For an interval, find the last feature that starts in this interval,
 484     // and add all features up through that feature.
 485
 486     if (end > start)
 487     {
 488       // fill in with all features that start within this interval, fully
 489       // inclusive
 490       int index2 = getClosestFeature(orderedFeatureStarts, end);
 491       while (++index <= index2)
 492       {
 493         result.add(orderedFeatureStarts[index]);
 494       }
 495
 496     }
 497   }
 498
 499   /**
 500    * Quick check when we only have one feature.
 501    *
 502    * @param sf
 503    * @param start
 504    * @param end
 505    * @param result
 506    */
 507   private void justCheckOne(SequenceFeature sf, long start, long end,
 508           List<SequenceFeature> result)
 509   {
 510     if (sf.begin <= end && sf.end >= start)
 511     {
 512       result.add(sf);
 513     }
 514     return;
 515   }
 516
 517   /**
 518    * Run through the sorted sequence array once, building the containedBy linked
 519    * list references. Does a check first to make sure there is actually
 520    * something out there that is overlapping. A null for sf.containedBy means
 521    * there are no overlaps for this feature.
 522    *
 523    * @param features
 524    */
 525   private void linkFeatures(SequenceFeature[] features)
 526   {
 527     int n = features.length;
 528     switch (n)
 529     {
 530     case 0:
 531       return;
 532     case 1:
 533       features[0].index1 = 1;
 534       return;
 535     }
 536     int maxEnd = features[0].end;
 537     for (int i = 1; i < n;)
 538     {
 539       SequenceFeature sf = features[i];
 540       if (sf.begin <= maxEnd)
 541       {
 542         sf.containedBy = getContainedBy(features[i - 1], sf);
 543       }
 544       if (sf.end > maxEnd)
 545       {
 546         maxEnd = sf.end;
 547       }
 548       sf.index1 = ++i;
 549     }
 550   }
 551 }