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