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