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