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