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