src/jalview/datamodel/features/FeatureStore.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.Collections;
  27 import java.util.HashSet;
  28 import java.util.List;
  29 import java.util.Set;
  30
  31 import intervalstore.api.IntervalStoreI;
  32 import intervalstore.impl.BinarySearcher;
  33 import intervalstore.impl.IntervalStore;
  34
  35 /**
  36  * A data store for a set of sequence features that supports efficient lookup of
  37  * features overlapping a given range. Intended for (but not limited to) storage
  38  * of features for one sequence and feature type.
  39  *
  40  * @author gmcarstairs
  41  *
  42  */
  43 public class FeatureStore
  44 {
  45   /*
  46    * Non-positional features have no (zero) start/end position.
  47    * Kept as a separate list in case this criterion changes in future.
  48    */
  49   List<SequenceFeature> nonPositionalFeatures;
  50
  51   /*
  52    * contact features ordered by first contact position
  53    */
  54   List<SequenceFeature> contactFeatureStarts;
  55
  56   /*
  57    * contact features ordered by second contact position
  58    */
  59   List<SequenceFeature> contactFeatureEnds;
  60
  61   /*
  62    * IntervalStore holds remaining features and provides efficient
  63    * query for features overlapping any given interval
  64    */
  65   IntervalStoreI<SequenceFeature> features;
  66
  67   /*
  68    * Feature groups represented in stored positional features
  69    * (possibly including null)
  70    */
  71   Set<String> positionalFeatureGroups;
  72
  73   /*
  74    * Feature groups represented in stored non-positional features
  75    * (possibly including null)
  76    */
  77   Set<String> nonPositionalFeatureGroups;
  78
  79   /*
  80    * the total length of all positional features; contact features count 1 to
  81    * the total and 1 to size(), consistent with an average 'feature length' of 1
  82    */
  83   int totalExtent;
  84
  85   float positionalMinScore;
  86
  87   float positionalMaxScore;
  88
  89   float nonPositionalMinScore;
  90
  91   float nonPositionalMaxScore;
  92
  93   private SequenceFeature[] temp = new SequenceFeature[3];
  94
  95   private boolean isTainted;
  96
  97   /**
  98    * Constructor
  99    */
 100   public FeatureStore()
 101   {
 102     features = new IntervalStore<>();
 103     positionalFeatureGroups = new HashSet<>();
 104     nonPositionalFeatureGroups = new HashSet<>();
 105     positionalMinScore = Float.NaN;
 106     positionalMaxScore = Float.NaN;
 107     nonPositionalMinScore = Float.NaN;
 108     nonPositionalMaxScore = Float.NaN;
 109
 110     // we only construct nonPositionalFeatures, contactFeatures if we need to
 111   }
 112
 113   /**
 114    * Adds one sequence feature to the store, and returns true, unless the
 115    * feature is already contained in the store, in which case this method
 116    * returns false. Containment is determined by SequenceFeature.equals()
 117    * comparison.
 118    *
 119    * @param feature
 120    */
 121   public boolean addFeature(SequenceFeature feature)
 122   {
 123     if (contains(feature))
 124     {
 125       return false;
 126     }
 127
 128     /*
 129      * keep a record of feature groups
 130      */
 131     if (!feature.isNonPositional())
 132     {
 133       positionalFeatureGroups.add(feature.getFeatureGroup());
 134     }
 135
 136     if (feature.isContactFeature())
 137     {
 138       addContactFeature(feature);
 139     }
 140     else if (feature.isNonPositional())
 141     {
 142       addNonPositionalFeature(feature);
 143     }
 144     else
 145     {
 146       addNestedFeature(feature);
 147     }
 148
 149     /*
 150      * record the total extent of positional features, to make
 151      * getTotalFeatureLength possible; we count the length of a
 152      * contact feature as 1
 153      */
 154     totalExtent += getFeatureLength(feature);
 155
 156     /*
 157      * record the minimum and maximum score for positional
 158      * and non-positional features
 159      */
 160     float score = feature.getScore();
 161     if (!Float.isNaN(score))
 162     {
 163       if (feature.isNonPositional())
 164       {
 165         nonPositionalMinScore = min(nonPositionalMinScore, score);
 166         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 167       }
 168       else
 169       {
 170         positionalMinScore = min(positionalMinScore, score);
 171         positionalMaxScore = max(positionalMaxScore, score);
 172       }
 173     }
 174
 175     return true;
 176   }
 177
 178   /**
 179    * Answers true if this store contains the given feature (testing by
 180    * SequenceFeature.equals), else false
 181    *
 182    * @param feature
 183    * @return
 184    */
 185   public boolean contains(SequenceFeature feature)
 186   {
 187     if (feature.isNonPositional())
 188     {
 189       return nonPositionalFeatures == null ? false : nonPositionalFeatures
 190               .contains(feature);
 191     }
 192
 193     if (feature.isContactFeature())
 194     {
 195       return contactFeatureStarts == null ? false : listContains(
 196               contactFeatureStarts, feature);
 197     }
 198
 199     return features == null ? false : features
 200             .contains(feature);
 201   }
 202
 203   /**
 204    * Answers the 'length' of the feature, counting 0 for non-positional features
 205    * and 1 for contact features
 206    *
 207    * @param feature
 208    * @return
 209    */
 210   protected static int getFeatureLength(SequenceFeature feature)
 211   {
 212     if (feature.isNonPositional())
 213     {
 214       return 0;
 215     }
 216     if (feature.isContactFeature())
 217     {
 218       return 1;
 219     }
 220     return 1 + feature.getEnd() - feature.getBegin();
 221   }
 222
 223   /**
 224    * Adds the feature to the list of non-positional features (with lazy
 225    * instantiation of the list if it is null), and returns true. The feature
 226    * group is added to the set of distinct feature groups for non-positional
 227    * features. This method allows duplicate features, so test before calling to
 228    * prevent this.
 229    *
 230    * @param feature
 231    */
 232   protected boolean addNonPositionalFeature(SequenceFeature feature)
 233   {
 234     if (nonPositionalFeatures == null)
 235     {
 236       nonPositionalFeatures = new ArrayList<>();
 237     }
 238
 239     nonPositionalFeatures.add(feature);
 240
 241     nonPositionalFeatureGroups.add(feature.getFeatureGroup());
 242
 243     return true;
 244   }
 245
 246   /**
 247    * Adds one feature to the IntervalStore that can manage nested features
 248    * (creating the IntervalStore if necessary)
 249    */
 250   protected synchronized void addNestedFeature(SequenceFeature feature)
 251   {
 252     if (features == null)
 253     {
 254       features = new IntervalStore<>();
 255     }
 256     features.add(feature);
 257     isTainted = true;
 258   }
 259
 260   /**
 261    * Add a contact feature to the lists that hold them ordered by start (first
 262    * contact) and by end (second contact) position, ensuring the lists remain
 263    * ordered, and returns true. This method allows duplicate features to be
 264    * added, so test before calling to avoid this.
 265    *
 266    * @param feature
 267    * @return
 268    */
 269   protected synchronized boolean addContactFeature(SequenceFeature feature)
 270   {
 271     if (contactFeatureStarts == null)
 272     {
 273       contactFeatureStarts = new ArrayList<>();
 274     }
 275     if (contactFeatureEnds == null)
 276     {
 277       contactFeatureEnds = new ArrayList<>();
 278     }
 279
 280     /*
 281      * insert into list sorted by start (first contact position):
 282      * binary search the sorted list to find the insertion point
 283      */
 284     int insertPosition = BinarySearcher.findFirst(contactFeatureStarts,
 285             f -> f.getBegin() >= feature.getBegin());
 286     contactFeatureStarts.add(insertPosition, feature);
 287
 288
 289     /*
 290      * insert into list sorted by end (second contact position):
 291      * binary search the sorted list to find the insertion point
 292      */
 293     insertPosition = BinarySearcher.findFirst(contactFeatureEnds,
 294             f -> f.getEnd() >= feature.getEnd());
 295     contactFeatureEnds.add(insertPosition, feature);
 296
 297     return true;
 298   }
 299
 300   /**
 301    * Answers true if the list contains the feature, else false. This method is
 302    * optimised for the condition that the list is sorted on feature start
 303    * position ascending, and will give unreliable results if this does not hold.
 304    *
 305    * @param features
 306    * @param feature
 307    * @return
 308    */
 309   protected static boolean listContains(List<SequenceFeature> features,
 310           SequenceFeature feature)
 311   {
 312     if (features == null || feature == null)
 313     {
 314       return false;
 315     }
 316
 317     /*
 318      * locate the first entry in the list which does not precede the feature
 319      */
 320     // int pos = binarySearch(features,
 321     // SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
 322     int pos = BinarySearcher.findFirst(features,
 323             val -> val.getBegin() >= feature.getBegin());
 324     int len = features.size();
 325     while (pos < len)
 326     {
 327       SequenceFeature sf = features.get(pos);
 328       if (sf.getBegin() > feature.getBegin())
 329       {
 330         return false; // no match found
 331       }
 332       if (sf.equals(feature))
 333       {
 334         return true;
 335       }
 336       pos++;
 337     }
 338     return false;
 339   }
 340
 341   /**
 342    * Returns a (possibly empty) list of features whose extent overlaps the given
 343    * range. The returned list is not ordered. Contact features are included if
 344    * either of the contact points lies within the range.
 345    *
 346    * @param start
 347    *          start position of overlap range (inclusive)
 348    * @param end
 349    *          end position of overlap range (inclusive)
 350    * @return
 351    */
 352   public List<SequenceFeature> findOverlappingFeatures(long start, long end)
 353   {
 354     List<SequenceFeature> result = new ArrayList<>();
 355
 356     findContactFeatures(start, end, result);
 357
 358     if (features != null)
 359     {
 360       result.addAll(features.findOverlaps(start, end));
 361     }
 362
 363     return result;
 364   }
 365
 366   /**
 367    * Adds contact features to the result list where either the second or the
 368    * first contact position lies within the target range
 369    *
 370    * @param from
 371    * @param to
 372    * @param result
 373    */
 374   protected void findContactFeatures(long from, long to,
 375           List<SequenceFeature> result)
 376   {
 377     if (contactFeatureStarts != null)
 378     {
 379       findContactStartOverlaps(from, to, result);
 380     }
 381     if (contactFeatureEnds != null)
 382     {
 383       findContactEndOverlaps(from, to, result);
 384     }
 385   }
 386
 387   /**
 388    * Adds to the result list any contact features whose end (second contact
 389    * point), but not start (first contact point), lies in the query from-to
 390    * range
 391    *
 392    * @param from
 393    * @param to
 394    * @param result
 395    */
 396   protected void findContactEndOverlaps(long from, long to,
 397           List<SequenceFeature> result)
 398   {
 399     /*
 400      * find the first contact feature (if any)
 401      * whose end point is not before the target range
 402      */
 403     int index = BinarySearcher.findFirst(contactFeatureEnds,
 404             f -> f.getEnd() >= from);
 405
 406     while (index < contactFeatureEnds.size())
 407     {
 408       SequenceFeature sf = contactFeatureEnds.get(index);
 409       if (!sf.isContactFeature())
 410       {
 411         System.err.println("Error! non-contact feature type "
 412                 + sf.getType() + " in contact features list");
 413         index++;
 414         continue;
 415       }
 416
 417       int begin = sf.getBegin();
 418       if (begin >= from && begin <= to)
 419       {
 420         /*
 421          * this feature's first contact position lies in the search range
 422          * so we don't include it in results a second time
 423          */
 424         index++;
 425         continue;
 426       }
 427
 428       if (sf.getEnd() > to)
 429       {
 430         /*
 431          * this feature (and all following) has end point after the target range
 432          */
 433         break;
 434       }
 435
 436       /*
 437        * feature has end >= from and end <= to
 438        * i.e. contact end point lies within overlap search range
 439        */
 440       result.add(sf);
 441       index++;
 442     }
 443   }
 444
 445   /**
 446    * Adds contact features whose start position lies in the from-to range to the
 447    * result list
 448    *
 449    * @param from
 450    * @param to
 451    * @param result
 452    */
 453   protected void findContactStartOverlaps(long from, long to,
 454           List<SequenceFeature> result)
 455   {
 456     int index = BinarySearcher.findFirst(contactFeatureStarts,
 457             f -> f.getBegin() >= from);
 458
 459     while (index < contactFeatureStarts.size())
 460     {
 461       SequenceFeature sf = contactFeatureStarts.get(index);
 462       if (!sf.isContactFeature())
 463       {
 464         System.err.println("Error! non-contact feature " + sf.toString()
 465                 + " in contact features list");
 466         index++;
 467         continue;
 468       }
 469       if (sf.getBegin() > to)
 470       {
 471         /*
 472          * this feature's start (and all following) follows the target range
 473          */
 474         break;
 475       }
 476
 477       /*
 478        * feature has begin >= from and begin <= to
 479        * i.e. contact start point lies within overlap search range
 480        */
 481       result.add(sf);
 482       index++;
 483     }
 484   }
 485
 486   /**
 487    * Answers a list of all positional features stored, in no guaranteed order
 488    *
 489    * @return
 490    */
 491   public List<SequenceFeature> getPositionalFeatures()
 492   {
 493     List<SequenceFeature> result = new ArrayList<>();
 494
 495     /*
 496      * add any contact features - from the list by start position
 497      */
 498     if (contactFeatureStarts != null)
 499     {
 500       result.addAll(contactFeatureStarts);
 501     }
 502
 503     /*
 504      * add any nested features
 505      */
 506     if (features != null)
 507     {
 508       result.addAll(features);
 509     }
 510
 511     return result;
 512   }
 513
 514   /**
 515    * Answers a list of all contact features. If there are none, returns an
 516    * immutable empty list.
 517    *
 518    * @return
 519    */
 520   public List<SequenceFeature> getContactFeatures()
 521   {
 522     if (contactFeatureStarts == null)
 523     {
 524       return Collections.emptyList();
 525     }
 526     return new ArrayList<>(contactFeatureStarts);
 527   }
 528
 529   /**
 530    * Answers a list of all non-positional features. If there are none, returns
 531    * an immutable empty list.
 532    *
 533    * @return
 534    */
 535   public List<SequenceFeature> getNonPositionalFeatures()
 536   {
 537     if (nonPositionalFeatures == null)
 538     {
 539       return Collections.emptyList();
 540     }
 541     return new ArrayList<>(nonPositionalFeatures);
 542   }
 543
 544   /**
 545    * Deletes the given feature from the store, returning true if it was found
 546    * (and deleted), else false. This method makes no assumption that the feature
 547    * is in the 'expected' place in the store, in case it has been modified since
 548    * it was added.
 549    *
 550    * @param sf
 551    */
 552   public synchronized boolean delete(SequenceFeature sf)
 553   {
 554     boolean removed = false;
 555
 556     /*
 557      * try contact positions (and if found, delete
 558      * from both lists of contact positions)
 559      */
 560     if (!removed && contactFeatureStarts != null)
 561     {
 562       removed = contactFeatureStarts.remove(sf);
 563       if (removed)
 564       {
 565         contactFeatureEnds.remove(sf);
 566       }
 567     }
 568
 569     boolean removedNonPositional = false;
 570
 571     /*
 572      * if not found, try non-positional features
 573      */
 574     if (!removed && nonPositionalFeatures != null)
 575     {
 576       removedNonPositional = nonPositionalFeatures.remove(sf);
 577       removed = removedNonPositional;
 578     }
 579
 580     /*
 581      * if not found, try nested features
 582      */
 583     if (!removed && features != null)
 584     {
 585       removed = features.remove(sf);
 586     }
 587
 588     if (removed)
 589     {
 590       rescanAfterDelete();
 591     }
 592
 593     return removed;
 594   }
 595
 596   /**
 597    * Rescan all features to recompute any cached values after an entry has been
 598    * deleted. This is expected to be an infrequent event, so performance here is
 599    * not critical.
 600    */
 601   protected synchronized void rescanAfterDelete()
 602   {
 603     positionalFeatureGroups.clear();
 604     nonPositionalFeatureGroups.clear();
 605     totalExtent = 0;
 606     positionalMinScore = Float.NaN;
 607     positionalMaxScore = Float.NaN;
 608     nonPositionalMinScore = Float.NaN;
 609     nonPositionalMaxScore = Float.NaN;
 610     isTainted = true;
 611     /*
 612      * scan non-positional features for groups and scores
 613      */
 614     for (SequenceFeature sf : getNonPositionalFeatures())
 615     {
 616       nonPositionalFeatureGroups.add(sf.getFeatureGroup());
 617       float score = sf.getScore();
 618       nonPositionalMinScore = min(nonPositionalMinScore, score);
 619       nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 620     }
 621
 622     /*
 623      * scan positional features for groups, scores and extents
 624      */
 625     for (SequenceFeature sf : getPositionalFeatures())
 626     {
 627       positionalFeatureGroups.add(sf.getFeatureGroup());
 628       float score = sf.getScore();
 629       positionalMinScore = min(positionalMinScore, score);
 630       positionalMaxScore = max(positionalMaxScore, score);
 631       totalExtent += getFeatureLength(sf);
 632     }
 633   }
 634
 635   /**
 636    * A helper method to return the minimum of two floats, where a non-NaN value
 637    * is treated as 'less than' a NaN value (unlike Math.min which does the
 638    * opposite)
 639    *
 640    * @param f1
 641    * @param f2
 642    */
 643   protected static float min(float f1, float f2)
 644   {
 645     if (Float.isNaN(f1))
 646     {
 647       return Float.isNaN(f2) ? f1 : f2;
 648     }
 649     else
 650     {
 651       return Float.isNaN(f2) ? f1 : Math.min(f1, f2);
 652     }
 653   }
 654
 655   /**
 656    * A helper method to return the maximum of two floats, where a non-NaN value
 657    * is treated as 'greater than' a NaN value (unlike Math.max which does the
 658    * opposite)
 659    *
 660    * @param f1
 661    * @param f2
 662    */
 663   protected static float max(float f1, float f2)
 664   {
 665     if (Float.isNaN(f1))
 666     {
 667       return Float.isNaN(f2) ? f1 : f2;
 668     }
 669     else
 670     {
 671       return Float.isNaN(f2) ? f1 : Math.max(f1, f2);
 672     }
 673   }
 674
 675   /**
 676    * Answers true if this store has no features, else false
 677    *
 678    * @return
 679    */
 680   public boolean isEmpty()
 681   {
 682     boolean hasFeatures = (contactFeatureStarts != null
 683             && !contactFeatureStarts
 684                     .isEmpty())
 685             || (nonPositionalFeatures != null && !nonPositionalFeatures
 686                     .isEmpty())
 687             || (features != null && features.size() > 0);
 688
 689     return !hasFeatures;
 690   }
 691
 692   /**
 693    * Answers the set of distinct feature groups stored, possibly including null,
 694    * as an unmodifiable view of the set. The parameter determines whether the
 695    * groups for positional or for non-positional features are returned.
 696    *
 697    * @param positionalFeatures
 698    * @return
 699    */
 700   public Set<String> getFeatureGroups(boolean positionalFeatures)
 701   {
 702     if (positionalFeatures)
 703     {
 704       return Collections.unmodifiableSet(positionalFeatureGroups);
 705     }
 706     else
 707     {
 708       return nonPositionalFeatureGroups == null ? Collections
 709               .<String> emptySet() : Collections
 710               .unmodifiableSet(nonPositionalFeatureGroups);
 711     }
 712   }
 713
 714   /**
 715    * Answers the number of positional (or non-positional) features stored.
 716    * Contact features count as 1.
 717    *
 718    * @param positional
 719    * @return
 720    */
 721   public int getFeatureCount(boolean positional)
 722   {
 723     if (!positional)
 724     {
 725       return nonPositionalFeatures == null ? 0 : nonPositionalFeatures
 726               .size();
 727     }
 728
 729     int size = 0;
 730
 731     if (contactFeatureStarts != null)
 732     {
 733       // note a contact feature (start/end) counts as one
 734       size += contactFeatureStarts.size();
 735     }
 736
 737     if (features != null)
 738     {
 739       size += features.size();
 740     }
 741
 742     return size;
 743   }
 744
 745   /**
 746    * Answers the total length of positional features (or zero if there are
 747    * none). Contact features contribute a value of 1 to the total.
 748    *
 749    * @return
 750    */
 751   public int getTotalFeatureLength()
 752   {
 753     return totalExtent;
 754   }
 755
 756   /**
 757    * Answers the minimum score held for positional or non-positional features.
 758    * This may be Float.NaN if there are no features, are none has a non-NaN
 759    * score.
 760    *
 761    * @param positional
 762    * @return
 763    */
 764   public float getMinimumScore(boolean positional)
 765   {
 766     return positional ? positionalMinScore : nonPositionalMinScore;
 767   }
 768
 769   /**
 770    * Answers the maximum score held for positional or non-positional features.
 771    * This may be Float.NaN if there are no features, are none has a non-NaN
 772    * score.
 773    *
 774    * @param positional
 775    * @return
 776    */
 777   public float getMaximumScore(boolean positional)
 778   {
 779     return positional ? positionalMaxScore : nonPositionalMaxScore;
 780   }
 781
 782   /**
 783    * Answers a list of all either positional or non-positional features whose
 784    * feature group matches the given group (which may be null)
 785    *
 786    * @param positional
 787    * @param group
 788    * @return
 789    */
 790   public List<SequenceFeature> getFeaturesForGroup(boolean positional,
 791           String group)
 792   {
 793     List<SequenceFeature> result = new ArrayList<>();
 794
 795     /*
 796      * if we know features don't include the target group, no need
 797      * to inspect them for matches
 798      */
 799     if (positional && !positionalFeatureGroups.contains(group)
 800             || !positional && !nonPositionalFeatureGroups.contains(group))
 801     {
 802       return result;
 803     }
 804
 805     List<SequenceFeature> sfs = positional ? getPositionalFeatures()
 806             : getNonPositionalFeatures();
 807     for (SequenceFeature sf : sfs)
 808     {
 809       String featureGroup = sf.getFeatureGroup();
 810       if (group == null && featureGroup == null || group != null
 811               && group.equals(featureGroup))
 812       {
 813         result.add(sf);
 814       }
 815     }
 816     return result;
 817   }
 818
 819   /**
 820    * Adds the shift amount to the start and end of all positional features whose
 821    * start position is at or after fromPosition. Returns true if at least one
 822    * feature was shifted, else false.
 823    *
 824    * @param fromPosition
 825    * @param shiftBy
 826    * @return
 827    */
 828   public synchronized boolean shiftFeatures(int fromPosition, int shiftBy)
 829   {
 830     /*
 831      * Because begin and end are final fields (to ensure the data store's
 832      * integrity), we have to delete each feature and re-add it as amended.
 833      * (Although a simple shift of all values would preserve data integrity!)
 834      */
 835     boolean modified = false;
 836     for (SequenceFeature sf : getPositionalFeatures())
 837     {
 838       if (sf.getBegin() >= fromPosition)
 839       {
 840         modified = true;
 841         int newBegin = sf.getBegin() + shiftBy;
 842         int newEnd = sf.getEnd() + shiftBy;
 843
 844         /*
 845          * sanity check: don't shift left of the first residue
 846          */
 847         if (newEnd > 0)
 848         {
 849           newBegin = Math.max(1, newBegin);
 850           SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd,
 851                   sf.getFeatureGroup(), sf.getScore());
 852           addFeature(sf2);
 853         }
 854         delete(sf);
 855       }
 856     }
 857     return modified;
 858   }
 859
 860   /**
 861    * Find all features containing this position.
 862    * Uses isTainted field to know when to reconstruct its temporary array.
 863    *
 864    * @param pos
 865    * @return list of SequenceFeatures
 866    * @author Bob Hanson 2019.07.30
 867    */
 868   public void findOverlappingFeatures(int pos, List<SequenceFeature> result)
 869   {
 870
 871     if (contactFeatureStarts != null)
 872     {
 873       findContacts(contactFeatureStarts, pos, result, true);
 874       findContacts(contactFeatureEnds, pos, result, false);
 875     }
 876     if (features != null)
 877     {
 878       int n = features.size();
 879       if (isTainted)
 880       {
 881         isTainted = false;
 882         if (temp.length < n)
 883         {
 884           temp = new SequenceFeature[n << 1];
 885         }
 886         features.toArray(temp);
 887       }
 888       findOverlaps(temp, n, pos, result);
 889     }
 890   }
 891
 892   /**
 893    * Binary search for contact start or end at a given (Overview) position.
 894    *
 895    * @param l
 896    * @param pos
 897    * @param result
 898    * @param isStart
 899    *
 900    * @author Bob Hanson 2019.07.30
 901    */
 902   private static void findContacts(List<SequenceFeature> l, int pos,
 903           List<SequenceFeature> result, boolean isStart)
 904   {
 905     int low = 0;
 906     int high = l.size() - 1;
 907     while (low <= high)
 908     {
 909       int mid = (low + high) >>> 1;
 910       SequenceFeature f = l.get(mid);
 911       switch (Long.signum((isStart ? f.begin : f.end) - pos))
 912       {
 913       case -1:
 914         low = mid + 1;
 915         continue;
 916       case 1:
 917         high = mid - 1;
 918         continue;
 919       case 0:
 920         int m = mid;
 921         result.add(f);
 922         // could be "5" in 12345556788 ?
 923         while (++mid <= high && (f = l.get(mid)) != null
 924                 && (isStart ? f.begin : f.end) == pos)
 925         {
 926           result.add(f);
 927         }
 928         while (--m >= low && (f = l.get(m)) != null
 929                 && (isStart ? f.begin : f.end) == pos)
 930         {
 931           result.add(f);
 932         }
 933         return;
 934       }
 935     }
 936   }
 937
 938   /**
 939    * Brute force point-interval overlap test
 940    *
 941    * @param features
 942    * @param n
 943    * @param pos
 944    * @param result
 945    */
 946   private static void findOverlaps(SequenceFeature[] features, int n,
 947           int pos,
 948           List<SequenceFeature> result)
 949   {
 950     // BH I know, brute force. We need a single-position overlap
 951     // method for IntervalStore, I think.
 952     for (int i = n; --i >= 0;)
 953     {
 954       SequenceFeature f = features[i];
 955       if (f.begin <= pos && f.end >= pos)
 956       {
 957         result.add(f);
 958       }
 959     }
 960   }
 961
 962 }