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