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