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.impl.BinarySearcher;
  33
  34 public abstract class FeatureStore implements FeatureStoreI
  35 {
  36
  37   /*
  38    * Non-positional features have no (zero) start/end position.
  39    * Kept as a separate list in case this criterion changes in future.
  40    */
  41   List<SequenceFeature> nonPositionalFeatures;
  42
  43   /*
  44    * contact features ordered by first contact position
  45    */
  46   List<SequenceFeature> contactFeatureStarts;
  47
  48   /*
  49    * contact features ordered by second contact position
  50    */
  51   List<SequenceFeature> contactFeatureEnds;
  52
  53   /*
  54    * IntervalStore holds remaining features and provides efficient
  55    * query for features overlapping any given interval
  56    */
  57   Collection<SequenceFeature> features;
  58
  59   @Override
  60   public Collection<SequenceFeature> getFeatures()
  61   {
  62     return features;
  63   }
  64
  65   /*
  66    * Feature groups represented in stored positional features
  67    * (possibly including null)
  68    */
  69   Set<String> positionalFeatureGroups;
  70
  71   /*
  72    * Feature groups represented in stored non-positional features
  73    * (possibly including null)
  74    */
  75   Set<String> nonPositionalFeatureGroups;
  76
  77   /*
  78    * the total length of all positional features; contact features count 1 to
  79    * the total and 1 to size(), consistent with an average 'feature length' of 1
  80    */
  81   int totalExtent;
  82
  83   float positionalMinScore;
  84
  85   float positionalMaxScore;
  86
  87   float nonPositionalMinScore;
  88
  89   float nonPositionalMaxScore;
  90
  91   /**
  92    * Constructor
  93    */
  94   public FeatureStore()
  95   {
  96     positionalFeatureGroups = new HashSet<>();
  97     nonPositionalFeatureGroups = new HashSet<>();
  98     positionalMinScore = Float.NaN;
  99     positionalMaxScore = Float.NaN;
 100     nonPositionalMinScore = Float.NaN;
 101     nonPositionalMaxScore = Float.NaN;
 102
 103     // we only construct nonPositionalFeatures, contactFeatures if we need to
 104   }
 105
 106   /**
 107    * Adds one sequence feature to the store, and returns true, unless the
 108    * feature is already contained in the store, in which case this method
 109    * returns false. Containment is determined by SequenceFeature.equals()
 110    * comparison.
 111    *
 112    * @param feature
 113    */
 114
 115   @Override
 116   public boolean addFeature(SequenceFeature feature)
 117   {
 118     if (contains(feature))
 119     {
 120       return false;
 121     }
 122
 123     /*
 124      * keep a record of feature groups
 125      */
 126     if (!feature.isNonPositional())
 127     {
 128       positionalFeatureGroups.add(feature.getFeatureGroup());
 129     }
 130
 131     if (feature.isContactFeature())
 132     {
 133       addContactFeature(feature);
 134     }
 135     else if (feature.isNonPositional())
 136     {
 137       addNonPositionalFeature(feature);
 138     }
 139     else
 140     {
 141       addNestedFeature(feature);
 142     }
 143
 144     /*
 145      * record the total extent of positional features, to make
 146      * getTotalFeatureLength possible; we count the length of a
 147      * contact feature as 1
 148      */
 149     totalExtent += getFeatureLength(feature);
 150
 151     /*
 152      * record the minimum and maximum score for positional
 153      * and non-positional features
 154      */
 155     float score = feature.getScore();
 156     if (!Float.isNaN(score))
 157     {
 158       if (feature.isNonPositional())
 159       {
 160         nonPositionalMinScore = min(nonPositionalMinScore, score);
 161         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 162       }
 163       else
 164       {
 165         positionalMinScore = min(positionalMinScore, score);
 166         positionalMaxScore = max(positionalMaxScore, score);
 167       }
 168     }
 169
 170     return true;
 171   }
 172
 173   /**
 174    * Answers true if this store contains the given feature (testing by
 175    * SequenceFeature.equals), else false
 176    *
 177    * @param feature
 178    * @return
 179    */
 180   @Override
 181   public boolean contains(SequenceFeature feature)
 182   {
 183     if (feature.isNonPositional())
 184     {
 185       return nonPositionalFeatures == null ? false
 186               : nonPositionalFeatures.contains(feature);
 187     }
 188
 189     if (feature.isContactFeature())
 190     {
 191       return contactFeatureStarts != null
 192               && listContains(contactFeatureStarts, feature);
 193     }
 194
 195     return features == null ? false : features.contains(feature);
 196   }
 197
 198   /**
 199    * Answers the 'length' of the feature, counting 0 for non-positional features
 200    * and 1 for contact features
 201    *
 202    * @param feature
 203    * @return
 204    */
 205   protected static int getFeatureLength(SequenceFeature feature)
 206   {
 207     if (feature.isNonPositional())
 208     {
 209       return 0;
 210     }
 211     if (feature.isContactFeature())
 212     {
 213       return 1;
 214     }
 215     return 1 + feature.getEnd() - feature.getBegin();
 216   }
 217
 218   /**
 219    * Adds the feature to the list of non-positional features (with lazy
 220    * instantiation of the list if it is null), and returns true. The feature
 221    * group is added to the set of distinct feature groups for non-positional
 222    * features. This method allows duplicate features, so test before calling to
 223    * prevent this.
 224    *
 225    * @param feature
 226    */
 227   protected boolean addNonPositionalFeature(SequenceFeature feature)
 228   {
 229     if (nonPositionalFeatures == null)
 230     {
 231       nonPositionalFeatures = new ArrayList<>();
 232     }
 233
 234     nonPositionalFeatures.add(feature);
 235
 236     nonPositionalFeatureGroups.add(feature.getFeatureGroup());
 237
 238     return true;
 239   }
 240
 241   /**
 242    * Adds one feature to the IntervalStore that can manage nested features
 243    * (creating the IntervalStore if necessary)
 244    */
 245   protected synchronized void addNestedFeature(SequenceFeature feature)
 246   {
 247     features.add(feature);
 248   }
 249   /**
 250    * Add a contact feature to the lists that hold them ordered by start (first
 251    * contact) and by end (second contact) position, ensuring the lists remain
 252    * ordered, and returns true. This method allows duplicate features to be
 253    * added, so test before calling to avoid this.
 254    *
 255    * @param feature
 256    * @return
 257    */
 258   protected synchronized boolean addContactFeature(SequenceFeature feature)
 259   {
 260     if (contactFeatureStarts == null)
 261     {
 262       contactFeatureStarts = new ArrayList<>();
 263       contactFeatureEnds = new ArrayList<>();
 264     }
 265
 266     /*
 267      * insert into list sorted by start (first contact position):
 268      * binary search the sorted list to find the insertion point
 269      */
 270     int insertPosition = BinarySearcher.findFirst(contactFeatureStarts,
 271             f -> f.getBegin() >= feature.getBegin());
 272     contactFeatureStarts.add(insertPosition, feature);
 273
 274     /*
 275      * insert into list sorted by end (second contact position):
 276      * binary search the sorted list to find the insertion point
 277      */
 278     insertPosition = BinarySearcher.findFirst(contactFeatureEnds,
 279             f -> f.getEnd() >= feature.getEnd());
 280     contactFeatureEnds.add(insertPosition, feature);
 281
 282     return true;
 283   }
 284
 285   /**
 286    * Answers true if the list contains the feature, else false. This method is
 287    * optimised for the condition that the list is sorted on feature start
 288    * position ascending, and will give unreliable results if this does not hold.
 289    *
 290    * @param features
 291    * @param feature
 292    * @return
 293    */
 294   protected static boolean listContains(List<SequenceFeature> features,
 295           SequenceFeature feature)
 296   {
 297     if (features == null || feature == null)
 298     {
 299       return false;
 300     }
 301
 302     /*
 303      * locate the first entry in the list which does not precede the feature
 304      */
 305     // int pos = binarySearch(features,
 306     // SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
 307     int pos = BinarySearcher.findFirst(features,
 308             val -> val.getBegin() >= feature.getBegin());
 309     int len = features.size();
 310     while (pos < len)
 311     {
 312       SequenceFeature sf = features.get(pos);
 313       if (sf.getBegin() > feature.getBegin())
 314       {
 315         return false; // no match found
 316       }
 317       if (sf.equals(feature))
 318       {
 319         return true;
 320       }
 321       pos++;
 322     }
 323     return false;
 324   }
 325
 326   abstract protected void findContactFeatures(long from, long to,
 327           List<SequenceFeature> result);
 328
 329   /**
 330    * Answers a list of all positional features stored, in no guaranteed order
 331    *
 332    * @return
 333    */
 334
 335   @Override
 336   public List<SequenceFeature> getPositionalFeatures(
 337           List<SequenceFeature> result)
 338   {
 339
 340     /*
 341      * add any contact features - from the list by start position
 342      */
 343     if (contactFeatureStarts != null)
 344     {
 345       result.addAll(contactFeatureStarts);
 346     }
 347
 348     /*
 349      * add any nested features
 350      */
 351     if (features != null)
 352     {
 353       result.addAll(features);
 354     }
 355
 356     return result;
 357   }
 358
 359   /**
 360    * Answers a list of all contact features. If there are none, returns an
 361    * immutable empty list.
 362    *
 363    * @return
 364    */
 365
 366   @Override
 367   public List<SequenceFeature> getContactFeatures(
 368           List<SequenceFeature> result)
 369   {
 370     if (contactFeatureStarts != null)
 371     {
 372       result.addAll(contactFeatureStarts);
 373     }
 374     return result;
 375   }
 376
 377   /**
 378    * Answers a list of all non-positional features. If there are none, returns
 379    * an immutable empty list.
 380    *
 381    * @return
 382    */
 383
 384   @Override
 385   public List<SequenceFeature> getNonPositionalFeatures(
 386           List<SequenceFeature> result)
 387   {
 388     if (nonPositionalFeatures != null)
 389     {
 390       result.addAll(nonPositionalFeatures);
 391     }
 392     return result;
 393   }
 394
 395   /**
 396    * Deletes the given feature from the store, returning true if it was found
 397    * (and deleted), else false. This method makes no assumption that the feature
 398    * is in the 'expected' place in the store, in case it has been modified since
 399    * it was added.
 400    *
 401    * @param sf
 402    */
 403
 404   @Override
 405   public synchronized boolean delete(SequenceFeature sf)
 406   {
 407     boolean removed = false;
 408
 409     /*
 410      * try contact positions (and if found, delete
 411      * from both lists of contact positions)
 412      */
 413     if (!removed && contactFeatureStarts != null)
 414     {
 415       removed = contactFeatureStarts.remove(sf);
 416       if (removed)
 417       {
 418         contactFeatureEnds.remove(sf);
 419       }
 420     }
 421
 422     boolean removedNonPositional = false;
 423
 424     /*
 425      * if not found, try non-positional features
 426      */
 427     if (!removed && nonPositionalFeatures != null)
 428     {
 429       removedNonPositional = nonPositionalFeatures.remove(sf);
 430       removed = removedNonPositional;
 431     }
 432
 433     /*
 434      * if not found, try nested features
 435      */
 436     if (!removed && features != null)
 437     {
 438       removed = features.remove(sf);
 439     }
 440
 441     if (removed)
 442     {
 443       rescanAfterDelete();
 444     }
 445
 446     return removed;
 447   }
 448
 449   /**
 450    * Rescan all features to recompute any cached values after an entry has been
 451    * deleted. This is expected to be an infrequent event, so performance here is
 452    * not critical.
 453    */
 454   protected synchronized void rescanAfterDelete()
 455   {
 456     positionalFeatureGroups.clear();
 457     nonPositionalFeatureGroups.clear();
 458     totalExtent = 0;
 459     positionalMinScore = Float.NaN;
 460     positionalMaxScore = Float.NaN;
 461     nonPositionalMinScore = Float.NaN;
 462     nonPositionalMaxScore = Float.NaN;
 463     /*
 464      * scan non-positional features for groups and scores
 465      */
 466     if (nonPositionalFeatures != null)
 467     {
 468       for (SequenceFeature sf : nonPositionalFeatures)
 469       {
 470         nonPositionalFeatureGroups.add(sf.getFeatureGroup());
 471         float score = sf.getScore();
 472         nonPositionalMinScore = min(nonPositionalMinScore, score);
 473         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 474       }
 475     }
 476
 477     /*
 478      * scan positional features for groups, scores and extents
 479      */
 480
 481     rescanPositional(contactFeatureStarts);
 482     rescanPositional(features);
 483   }
 484
 485   private void rescanPositional(Collection<SequenceFeature> sfs)
 486   {
 487     if (sfs == null)
 488     {
 489       return;
 490     }
 491     for (SequenceFeature sf : sfs)
 492     {
 493       positionalFeatureGroups.add(sf.getFeatureGroup());
 494       float score = sf.getScore();
 495       positionalMinScore = min(positionalMinScore, score);
 496       positionalMaxScore = max(positionalMaxScore, score);
 497       totalExtent += getFeatureLength(sf);
 498     }
 499   }
 500
 501   /**
 502    * A helper method to return the minimum of two floats, where a non-NaN value
 503    * is treated as 'less than' a NaN value (unlike Math.min which does the
 504    * opposite)
 505    *
 506    * @param f1
 507    * @param f2
 508    */
 509   protected static float min(float f1, float f2)
 510   {
 511     if (Float.isNaN(f1))
 512     {
 513       return Float.isNaN(f2) ? f1 : f2;
 514     }
 515     else
 516     {
 517       return Float.isNaN(f2) ? f1 : Math.min(f1, f2);
 518     }
 519   }
 520
 521   /**
 522    * A helper method to return the maximum of two floats, where a non-NaN value
 523    * is treated as 'greater than' a NaN value (unlike Math.max which does the
 524    * opposite)
 525    *
 526    * @param f1
 527    * @param f2
 528    */
 529   protected static float max(float f1, float f2)
 530   {
 531     if (Float.isNaN(f1))
 532     {
 533       return Float.isNaN(f2) ? f1 : f2;
 534     }
 535     else
 536     {
 537       return Float.isNaN(f2) ? f1 : Math.max(f1, f2);
 538     }
 539   }
 540
 541
 542   /**
 543    * Answers true if this store has no features, else false
 544    *
 545    * @return
 546    */
 547
 548   @Override
 549   public boolean isEmpty()
 550   {
 551     boolean hasFeatures = (contactFeatureStarts != null
 552             && !contactFeatureStarts.isEmpty())
 553             || (nonPositionalFeatures != null
 554                     && !nonPositionalFeatures.isEmpty())
 555             || features.size() > 0;
 556
 557     return !hasFeatures;
 558   }
 559
 560   /**
 561    * Answers the set of distinct feature groups stored, possibly including null,
 562    * as an unmodifiable view of the set. The parameter determines whether the
 563    * groups for positional or for non-positional features are returned.
 564    *
 565    * @param positionalFeatures
 566    * @return
 567    */
 568
 569   @Override
 570   public Set<String> getFeatureGroups(boolean positionalFeatures)
 571   {
 572     if (positionalFeatures)
 573     {
 574       return Collections.unmodifiableSet(positionalFeatureGroups);
 575     }
 576     else
 577     {
 578       return nonPositionalFeatureGroups == null
 579               ? Collections.<String> emptySet()
 580               : Collections.unmodifiableSet(nonPositionalFeatureGroups);
 581     }
 582   }
 583
 584   /**
 585    * Answers a list of all either positional or non-positional features whose
 586    * feature group matches the given group (which may be null)
 587    *
 588    * @param positional
 589    * @param group
 590    * @return
 591    */
 592
 593   @Override
 594   public List<SequenceFeature> getFeaturesForGroup(boolean positional,
 595           String group)
 596   {
 597     List<SequenceFeature> result = new ArrayList<>();
 598
 599     /*
 600      * if we know features don't include the target group, no need
 601      * to inspect them for matches
 602      */
 603     if (positional && !positionalFeatureGroups.contains(group)
 604             || !positional && !nonPositionalFeatureGroups.contains(group))
 605     {
 606       return result;
 607     }
 608
 609     if (positional)
 610     {
 611       addFeaturesForGroup(group, contactFeatureStarts, result);
 612       addFeaturesForGroup(group, features, result);
 613     }
 614     else
 615     {
 616       addFeaturesForGroup(group, nonPositionalFeatures, result);
 617     }
 618     return result;
 619   }
 620
 621   private void addFeaturesForGroup(String group,
 622           Collection<SequenceFeature> sfs, List<SequenceFeature> result)
 623   {
 624     if (sfs == null)
 625     {
 626       return;
 627     }
 628     for (SequenceFeature sf : sfs)
 629     {
 630       String featureGroup = sf.getFeatureGroup();
 631       if (group == null && featureGroup == null
 632               || group != null && group.equals(featureGroup))
 633       {
 634         result.add(sf);
 635       }
 636     }
 637   }
 638
 639   /**
 640    * Answers the number of positional (or non-positional) features stored.
 641    * Contact features count as 1.
 642    *
 643    * @param positional
 644    * @return
 645    */
 646
 647   @Override
 648   public int getFeatureCount(boolean positional)
 649   {
 650     if (!positional)
 651     {
 652       return nonPositionalFeatures == null ? 0
 653               : nonPositionalFeatures.size();
 654     }
 655
 656     return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size())
 657             + features.size();
 658
 659   }
 660
 661
 662   /**
 663    * Answers the total length of positional features (or zero if there are
 664    * none). Contact features contribute a value of 1 to the total.
 665    *
 666    * @return
 667    */
 668
 669   @Override
 670   public int getTotalFeatureLength()
 671   {
 672     return totalExtent;
 673   }
 674
 675   /**
 676    * Answers the minimum score held for positional or non-positional features.
 677    * This may be Float.NaN if there are no features, are none has a non-NaN
 678    * score.
 679    *
 680    * @param positional
 681    * @return
 682    */
 683
 684   @Override
 685   public float getMinimumScore(boolean positional)
 686   {
 687     return positional ? positionalMinScore : nonPositionalMinScore;
 688   }
 689
 690   /**
 691    * Answers the maximum score held for positional or non-positional features.
 692    * This may be Float.NaN if there are no features, are none has a non-NaN
 693    * score.
 694    *
 695    * @param positional
 696    * @return
 697    */
 698
 699   @Override
 700   public float getMaximumScore(boolean positional)
 701   {
 702     return positional ? positionalMaxScore : nonPositionalMaxScore;
 703   }
 704
 705
 706   /**
 707    * Adds the shift amount to the start and end of all positional features whose
 708    * start position is at or after fromPosition. Returns true if at least one
 709    * feature was shifted, else false.
 710    *
 711    * @param fromPosition
 712    * @param shiftBy
 713    * @return
 714    */
 715
 716   @Override
 717   public synchronized boolean shiftFeatures(int fromPosition, int shiftBy)
 718   {
 719     /*
 720      * Because begin and end are final fields (to ensure the data store's
 721      * integrity), we have to delete each feature and re-add it as amended.
 722      * (Although a simple shift of all values would preserve data integrity!)
 723      */
 724     boolean modified = false;
 725     for (SequenceFeature sf : getPositionalFeatures())
 726     {
 727       if (sf.getBegin() >= fromPosition)
 728       {
 729         modified = true;
 730         int newBegin = sf.getBegin() + shiftBy;
 731         int newEnd = sf.getEnd() + shiftBy;
 732
 733         /*
 734          * sanity check: don't shift left of the first residue
 735          */
 736         if (newEnd > 0)
 737         {
 738           newBegin = Math.max(1, newBegin);
 739           SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd,
 740                   sf.getFeatureGroup(), sf.getScore());
 741           addFeature(sf2);
 742         }
 743         delete(sf);
 744       }
 745     }
 746     return modified;
 747   }
 748
 749
 750   @Override
 751   public List<SequenceFeature> findOverlappingFeatures(long start, long end)
 752   {
 753     return findOverlappingFeatures(start, end, null);
 754   }
 755
 756   @Override
 757   public List<SequenceFeature> getPositionalFeatures()
 758   {
 759     return getPositionalFeatures(new ArrayList<>());
 760   }
 761
 762   @Override
 763   public List<SequenceFeature> getContactFeatures()
 764   {
 765     return getContactFeatures(new ArrayList<>());
 766   }
 767
 768   @Override
 769   public List<SequenceFeature> getNonPositionalFeatures()
 770   {
 771     return getNonPositionalFeatures(new ArrayList<>());
 772   }
 773
 774 }