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