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