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