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 (containsContactFeature(feature))
 278       {
 279         return false;
 280       }
 281       positionalFeatureGroups.add(feature.getFeatureGroup());
 282       if (feature.begin > lastContactStart)
 283       {
 284         lastContactStart = feature.begin;
 285       }
 286       addContactFeature(feature);
 287     }
 288     else if (feature.isNonPositional())
 289     {
 290       if (containsNonPositional(feature))
 291       {
 292         return false;
 293       }
 294
 295       addNonPositionalFeature(feature);
 296     }
 297     else
 298     {
 299       // allow for check with
 300       if (checkContainsPositionalFeatureForAdd(feature)
 301               || !addPositionalFeature(feature))
 302       {
 303         return false;
 304       }
 305       positionalFeatureGroups.add(feature.getFeatureGroup());
 306       // addPositionalFeature(feature);
 307       if (feature.begin > lastStart)
 308       {
 309         lastStart = feature.begin;
 310       }
 311     }
 312
 313     /*
 314      * record the total extent of positional features, to make
 315      * getTotalFeatureLength possible; we count the length of a
 316      * contact feature as 1
 317      */
 318     totalExtent += getFeatureLength(feature);
 319
 320     /*
 321      * record the minimum and maximum score for positional
 322      * and non-positional features
 323      */
 324     float score = feature.getScore();
 325     if (!Float.isNaN(score))
 326     {
 327       if (feature.isNonPositional())
 328       {
 329         nonPositionalMinScore = min(nonPositionalMinScore, score);
 330         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 331       }
 332       else
 333       {
 334         positionalMinScore = min(positionalMinScore, score);
 335         positionalMaxScore = max(positionalMaxScore, score);
 336       }
 337     }
 338
 339     return true;
 340   }
 341
 342   private void addFeaturesForGroup(String group,
 343           Collection<SequenceFeature> sfs, List<SequenceFeature> result)
 344   {
 345     if (sfs == null)
 346     {
 347       return;
 348     }
 349     for (SequenceFeature sf : sfs)
 350     {
 351       String featureGroup = sf.getFeatureGroup();
 352       if (group == null && featureGroup == null
 353               || group != null && group.equals(featureGroup))
 354       {
 355         result.add(sf);
 356       }
 357     }
 358   }
 359
 360   /**
 361    * Adds one feature to the IntervalStore that can manage nested features
 362    * (creating the IntervalStore if necessary)
 363    *
 364    * @return true if added -- allowing for late checking during addition
 365    */
 366   abstract protected boolean addPositionalFeature(SequenceFeature feature);
 367
 368   /**
 369    * Adds the feature to the list of non-positional features (with lazy
 370    * instantiation of the list if it is null), and returns true. The feature
 371    * group is added to the set of distinct feature groups for non-positional
 372    * features. This method allows duplicate features, so test before calling to
 373    * prevent this.
 374    *
 375    * @param feature
 376    */
 377   protected boolean addNonPositionalFeature(SequenceFeature feature)
 378   {
 379     if (nonPositionalFeatures == null)
 380     {
 381       nonPositionalFeatures = new ArrayList<>();
 382     }
 383
 384     nonPositionalFeatures.add(feature);
 385
 386     nonPositionalFeatureGroups.add(feature.getFeatureGroup());
 387
 388     return true;
 389   }
 390
 391   /**
 392    * Answers true if this store contains the given feature (testing by
 393    * SequenceFeature.equals), else false
 394    *
 395    * @param feature
 396    * @return
 397    */
 398   @Override
 399   public boolean contains(SequenceFeature feature)
 400   {
 401     if (feature.isNonPositional())
 402     {
 403       return containsNonPositional(feature);
 404
 405     }
 406
 407     if (feature.isContactFeature())
 408     {
 409       return containsContactFeature(feature);
 410
 411     }
 412
 413     return containsPositionalFeature(feature);
 414
 415   }
 416
 417   /**
 418    * A check that can be overridden if the check is being done during the add
 419    * operation itself.
 420    *
 421    * @param feature
 422    * @return
 423    */
 424   protected boolean checkContainsPositionalFeatureForAdd(
 425           SequenceFeature feature)
 426   {
 427     return containsPositionalFeature(feature);
 428   }
 429
 430   private boolean containsPositionalFeature(SequenceFeature feature)
 431   {
 432     return features == null || feature.begin > lastStart ? false
 433             : containsFeature(feature);
 434   }
 435
 436   private boolean containsContactFeature(SequenceFeature feature)
 437   {
 438     return contactFeatureStarts != null && feature.begin <= lastContactStart
 439             && listContains(contactFeatureStarts, feature);
 440   }
 441
 442   private boolean containsNonPositional(SequenceFeature feature)
 443   {
 444     return nonPositionalFeatures == null ? false
 445             : nonPositionalFeatures.contains(feature);
 446   }
 447
 448   abstract protected boolean containsFeature(SequenceFeature feature);
 449
 450   /**
 451    * Deletes the given feature from the store, returning true if it was found
 452    * (and deleted), else false. This method makes no assumption that the feature
 453    * is in the 'expected' place in the store, in case it has been modified since
 454    * it was added.
 455    *
 456    * @param sf
 457    */
 458
 459   @Override
 460   public synchronized boolean delete(SequenceFeature sf)
 461   {
 462     boolean removed = false;
 463
 464     /*
 465      * try contact positions (and if found, delete
 466      * from both lists of contact positions)
 467      */
 468     if (!removed && contactFeatureStarts != null)
 469     {
 470       removed = contactFeatureStarts.remove(sf);
 471       if (removed)
 472       {
 473         contactFeatureEnds.remove(sf);
 474       }
 475     }
 476
 477     /*
 478      * if not found, try non-positional features
 479      */
 480     if (!removed && nonPositionalFeatures != null)
 481     {
 482       removed = nonPositionalFeatures.remove(sf);
 483     }
 484
 485     /*
 486      * if not found, try nested features
 487      */
 488     if (!removed && features != null)
 489     {
 490       removed = findAndRemoveNonContactFeature(sf);
 491     }
 492
 493     if (removed)
 494     {
 495       rescanAfterDelete();
 496     }
 497
 498     return removed;
 499   }
 500
 501   abstract protected boolean findAndRemoveNonContactFeature(SequenceFeature sf);
 502
 503   abstract protected void findContactFeatures(long from, long to,
 504           List<SequenceFeature> result);
 505
 506   abstract protected int findFirstBegin(List<SequenceFeature> list,
 507           long pos);
 508
 509   abstract protected int findFirstEnd(List<SequenceFeature> list, long pos);
 510
 511   @Override
 512   public List<SequenceFeature> findOverlappingFeatures(long start, long end)
 513   {
 514     return findOverlappingFeatures(start, end, null);
 515   }
 516
 517   @Override
 518   public List<SequenceFeature> getContactFeatures()
 519   {
 520     return getContactFeatures(new ArrayList<>());
 521   }
 522
 523   /**
 524    * Answers a list of all contact features. If there are none, returns an
 525    * immutable empty list.
 526    *
 527    * @return
 528    */
 529
 530   @Override
 531   public List<SequenceFeature> getContactFeatures(
 532           List<SequenceFeature> result)
 533   {
 534     if (contactFeatureStarts != null)
 535     {
 536       result.addAll(contactFeatureStarts);
 537     }
 538     return result;
 539   }
 540
 541   /**
 542    * Answers the number of positional (or non-positional) features stored.
 543    * Contact features count as 1.
 544    *
 545    * @param positional
 546    * @return
 547    */
 548
 549   @Override
 550   public int getFeatureCount(boolean positional)
 551   {
 552     if (!positional)
 553     {
 554       return nonPositionalFeatures == null ? 0
 555               : nonPositionalFeatures.size();
 556     }
 557
 558     return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size())
 559             + features.size();
 560
 561   }
 562
 563   /**
 564    * Answers the set of distinct feature groups stored, possibly including null,
 565    * as an unmodifiable view of the set. The parameter determines whether the
 566    * groups for positional or for non-positional features are returned.
 567    *
 568    * @param positionalFeatures
 569    * @return
 570    */
 571
 572   @Override
 573   public Set<String> getFeatureGroups(boolean positionalFeatures)
 574   {
 575     if (positionalFeatures)
 576     {
 577       return Collections.unmodifiableSet(positionalFeatureGroups);
 578     }
 579     else
 580     {
 581       return nonPositionalFeatureGroups == null
 582               ? Collections.<String> emptySet()
 583               : Collections.unmodifiableSet(nonPositionalFeatureGroups);
 584     }
 585   }
 586
 587   @Override
 588   public Collection<SequenceFeature> getFeatures()
 589   {
 590     return features;
 591   }
 592
 593   /**
 594    * Answers a list of all either positional or non-positional features whose
 595    * feature group matches the given group (which may be null)
 596    *
 597    * @param positional
 598    * @param group
 599    * @return
 600    */
 601
 602   @Override
 603   public List<SequenceFeature> getFeaturesForGroup(boolean positional,
 604           String group)
 605   {
 606     List<SequenceFeature> result = new ArrayList<>();
 607
 608     /*
 609      * if we know features don't include the target group, no need
 610      * to inspect them for matches
 611      */
 612     if (positional && !positionalFeatureGroups.contains(group)
 613             || !positional && !nonPositionalFeatureGroups.contains(group))
 614     {
 615       return result;
 616     }
 617
 618     if (positional)
 619     {
 620       addFeaturesForGroup(group, contactFeatureStarts, result);
 621       addFeaturesForGroup(group, features, result);
 622     }
 623     else
 624     {
 625       addFeaturesForGroup(group, nonPositionalFeatures, result);
 626     }
 627     return result;
 628   }
 629
 630   /**
 631    * Answers the maximum score held for positional or non-positional features.
 632    * This may be Float.NaN if there are no features, are none has a non-NaN
 633    * score.
 634    *
 635    * @param positional
 636    * @return
 637    */
 638
 639   @Override
 640   public float getMaximumScore(boolean positional)
 641   {
 642     return positional ? positionalMaxScore : nonPositionalMaxScore;
 643   }
 644
 645   /**
 646    * Answers the minimum score held for positional or non-positional features.
 647    * This may be Float.NaN if there are no features, are none has a non-NaN
 648    * score.
 649    *
 650    * @param positional
 651    * @return
 652    */
 653
 654   @Override
 655   public float getMinimumScore(boolean positional)
 656   {
 657     return positional ? positionalMinScore : nonPositionalMinScore;
 658   }
 659
 660   @Override
 661   public List<SequenceFeature> getNonPositionalFeatures()
 662   {
 663     return getNonPositionalFeatures(new ArrayList<>());
 664   }
 665
 666   /**
 667    * Answers a list of all non-positional features. If there are none, returns
 668    * an immutable empty list.
 669    *
 670    * @return
 671    */
 672
 673   @Override
 674   public List<SequenceFeature> getNonPositionalFeatures(
 675           List<SequenceFeature> result)
 676   {
 677     if (nonPositionalFeatures != null)
 678     {
 679       result.addAll(nonPositionalFeatures);
 680     }
 681     return result;
 682   }
 683
 684   @Override
 685   public List<SequenceFeature> getPositionalFeatures()
 686   {
 687     return getPositionalFeatures(new ArrayList<>());
 688   }
 689
 690   /**
 691    * Answers a list of all positional features stored, in no guaranteed order
 692    *
 693    * @return
 694    */
 695
 696   @Override
 697   public List<SequenceFeature> getPositionalFeatures(
 698           List<SequenceFeature> result)
 699   {
 700
 701     /*
 702      * add any contact features - from the list by start position
 703      */
 704     if (contactFeatureStarts != null)
 705     {
 706       result.addAll(contactFeatureStarts);
 707     }
 708
 709     /*
 710      * add any nested features
 711      */
 712     if (features != null)
 713     {
 714       result.addAll(features);
 715     }
 716
 717     return result;
 718   }
 719
 720   /**
 721    * Answers the total length of positional features (or zero if there are
 722    * none). Contact features contribute a value of 1 to the total.
 723    *
 724    * @return
 725    */
 726
 727   @Override
 728   public int getTotalFeatureLength()
 729   {
 730     return totalExtent;
 731   }
 732
 733   /**
 734    * Answers true if this store has no features, else false
 735    *
 736    * @return
 737    */
 738
 739   @Override
 740   public boolean isEmpty()
 741   {
 742     boolean hasFeatures = (contactFeatureStarts != null
 743             && !contactFeatureStarts.isEmpty())
 744             || (nonPositionalFeatures != null
 745                     && !nonPositionalFeatures.isEmpty())
 746             || features.size() > 0;
 747
 748     return !hasFeatures;
 749   }
 750
 751   /**
 752    * Rescan all features to recompute any cached values after an entry has been
 753    * deleted. This is expected to be an infrequent event, so performance here is
 754    * not critical.
 755    */
 756   protected synchronized void rescanAfterDelete()
 757   {
 758     positionalFeatureGroups.clear();
 759     nonPositionalFeatureGroups.clear();
 760     totalExtent = 0;
 761     positionalMinScore = Float.NaN;
 762     positionalMaxScore = Float.NaN;
 763     nonPositionalMinScore = Float.NaN;
 764     nonPositionalMaxScore = Float.NaN;
 765     /*
 766      * scan non-positional features for groups and scores
 767      */
 768     if (nonPositionalFeatures != null)
 769     {
 770       List<SequenceFeature> list = nonPositionalFeatures;
 771       for (int i = 0, n = list.size(); i < n; i++)
 772       {
 773         SequenceFeature sf = list.get(i);
 774         nonPositionalFeatureGroups.add(sf.getFeatureGroup());
 775         float score = sf.getScore();
 776         nonPositionalMinScore = min(nonPositionalMinScore, score);
 777         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 778       }
 779     }
 780
 781     /*
 782      * scan positional features for groups, scores and extents
 783      */
 784
 785     rescanPositional(contactFeatureStarts);
 786     rescanPositional(features);
 787   }
 788
 789   private void rescanPositional(Collection<SequenceFeature> sfs)
 790   {
 791     if (sfs == null)
 792     {
 793       return;
 794     }
 795     for (SequenceFeature sf : sfs)
 796     {
 797       positionalFeatureGroups.add(sf.getFeatureGroup());
 798       float score = sf.getScore();
 799       positionalMinScore = min(positionalMinScore, score);
 800       positionalMaxScore = max(positionalMaxScore, score);
 801       totalExtent += getFeatureLength(sf);
 802     }
 803   }
 804
 805   /**
 806    * Adds the shift amount to the start and end of all positional features whose
 807    * start position is at or after fromPosition. Returns true if at least one
 808    * feature was shifted, else false.
 809    *
 810    * @param fromPosition
 811    * @param shiftBy
 812    * @return
 813    */
 814
 815   @Override
 816   public synchronized boolean shiftFeatures(int fromPosition, int shiftBy)
 817   {
 818     /*
 819      * Because begin and end are final fields (to ensure the data store's
 820      * integrity), we have to delete each feature and re-add it as amended.
 821      * (Although a simple shift of all values would preserve data integrity!)
 822      */
 823     boolean modified = false;
 824     List<SequenceFeature> list = getPositionalFeatures();
 825     for (int i = 0, n = list.size(); i < n; i++)
 826     {
 827       SequenceFeature sf = list.get(i);
 828       if (sf.getBegin() >= fromPosition)
 829       {
 830         modified = true;
 831         int newBegin = sf.getBegin() + shiftBy;
 832         int newEnd = sf.getEnd() + shiftBy;
 833
 834         /*
 835          * sanity check: don't shift left of the first residue
 836          */
 837         if (newEnd > 0)
 838         {
 839           newBegin = Math.max(1, newBegin);
 840           SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd,
 841                   sf.getFeatureGroup(), sf.getScore());
 842           addFeature(sf2);
 843         }
 844         delete(sf);
 845       }
 846     }
 847     return modified;
 848   }
 849
 850 }