src/jalview/datamodel/features/SequenceFeatures.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 import jalview.io.gff.SequenceOntologyFactory;
  25 import jalview.io.gff.SequenceOntologyI;
  26 import jalview.util.Platform;
  27
  28 import java.util.ArrayList;
  29 import java.util.Arrays;
  30 import java.util.HashSet;
  31 import java.util.List;
  32 import java.util.Map;
  33 import java.util.Map.Entry;
  34 import java.util.Set;
  35 import java.util.TreeMap;
  36
  37 import intervalstore.api.IntervalI;
  38
  39 /**
  40  * A class that stores sequence features in a way that supports efficient
  41  * querying by type and location (overlap). Intended for (but not limited to)
  42  * storage of features for one sequence.
  43  *
  44  * @author gmcarstairs
  45  *
  46  */
  47 public class SequenceFeatures implements SequenceFeaturesI
  48 {
  49
  50   /*
  51    * map from feature type to structured store of features for that type
  52    * null types are permitted (but not a good idea!)
  53    */
  54   private Map<String, FeatureStoreI> featureStore;
  55
  56   /**
  57    * original NCList-based IntervalStore
  58    */
  59   private final static int INTERVAL_STORE_NCLIST = 0;
  60
  61   /**
  62    * linked-list deferred-sort IntervalStore
  63    */
  64   private final static int INTERVAL_STORE_NOCLKIST = 1;
  65
  66   /**
  67    * no-IntervalStore option for JavaScript
  68    */
  69   private final static int INTERVAL_STORE_LINKED_LIST = -1;
  70
  71   private final int INTERVAL_STORE_MODE = (
  72   // can be set differently for testing, but default is
  73   // LINKED_LIST for JalviewJS and NCLIST for Java
  74   Platform.isJS() ? //
  75           INTERVAL_STORE_LINKED_LIST //
  76           : INTERVAL_STORE_NCLIST//
  77   );
  78
  79   /**
  80    * Constructor
  81    */
  82   public SequenceFeatures()
  83   {
  84     /*
  85      * use a TreeMap so that features are returned in alphabetical order of type
  86      * ? wrap as a synchronized map for add and delete operations
  87      */
  88     // featureStore = Collections
  89     // .synchronizedSortedMap(new TreeMap<String, FeatureStoreI>());
  90     featureStore = new TreeMap<>();
  91   }
  92
  93   /**
  94    * Constructor given a list of features
  95    */
  96   public SequenceFeatures(List<SequenceFeature> features)
  97   {
  98     this();
  99     if (features != null)
 100     {
 101       for (SequenceFeature feature : features)
 102       {
 103         add(feature);
 104       }
 105     }
 106   }
 107
 108   /**
 109    * {@inheritDoc}
 110    */
 111   @Override
 112   public boolean add(SequenceFeature sf)
 113   {
 114     String type = sf.getType();
 115     if (type == null)
 116     {
 117       System.err.println("Feature type may not be null: " + sf.toString());
 118       return false;
 119     }
 120
 121     if (featureStore.get(type) == null)
 122     {
 123       featureStore.put(type, newFeatureStore());
 124     }
 125     return featureStore.get(type).addFeature(sf);
 126   }
 127
 128   private FeatureStoreI newFeatureStore()
 129   {
 130     switch (INTERVAL_STORE_MODE)
 131     {
 132     default:
 133     case INTERVAL_STORE_NCLIST:
 134       return new FeatureStoreImpl(true);
 135     case INTERVAL_STORE_NOCLKIST:
 136       return new FeatureStoreImpl(false);
 137     case INTERVAL_STORE_LINKED_LIST:
 138       return new FeatureStoreJS();
 139     }
 140   }
 141
 142   /**
 143    * {@inheritDoc}
 144    */
 145   @Override
 146   public List<SequenceFeature> findFeatures(int from, int to,
 147           String... type)
 148   {
 149     List<SequenceFeature> result = new ArrayList<>();
 150     for (FeatureStoreI featureSet : varargToTypes(type))
 151     {
 152       // System.err.println("SF findFeature " + System.currentTimeMillis()
 153       // + " " + from + " " + to + " "
 154       // + featureSet.getPositionalFeatures().get(0).type);
 155       //
 156       result.addAll(featureSet.findOverlappingFeatures(from, to, null));
 157     }
 158     return result;
 159   }
 160
 161   /**
 162    * {@inheritDoc}
 163    */
 164   @Override
 165   public List<SequenceFeature> getAllFeatures(String... type)
 166   {
 167     List<SequenceFeature> result = new ArrayList<>();
 168
 169     result.addAll(getPositionalFeatures(type));
 170
 171     result.addAll(getNonPositionalFeatures());
 172
 173     return result;
 174   }
 175
 176   /**
 177    * {@inheritDoc}
 178    */
 179   @Override
 180   public List<SequenceFeature> getFeaturesByOntology(String... ontologyTerm)
 181   {
 182     if (ontologyTerm == null || ontologyTerm.length == 0)
 183     {
 184       return new ArrayList<>();
 185     }
 186
 187     Set<String> featureTypes = getFeatureTypes(ontologyTerm);
 188     if (featureTypes.isEmpty())
 189     {
 190       /*
 191        * no features of the specified type or any sub-type
 192        */
 193       return new ArrayList<>();
 194     }
 195
 196     return getAllFeatures(
 197             featureTypes.toArray(new String[featureTypes.size()]));
 198   }
 199
 200   /**
 201    * {@inheritDoc}
 202    */
 203   @Override
 204   public int getFeatureCount(boolean positional, String... type)
 205   {
 206     int result = 0;
 207
 208     for (FeatureStoreI featureSet : varargToTypes(type))
 209     {
 210       result += featureSet.getFeatureCount(positional);
 211     }
 212     return result;
 213   }
 214
 215   /**
 216    * {@inheritDoc}
 217    */
 218   @Override
 219   public int getTotalFeatureLength(String... type)
 220   {
 221     int result = 0;
 222
 223     for (FeatureStoreI featureSet : varargToTypes(type))
 224     {
 225       result += featureSet.getTotalFeatureLength();
 226     }
 227     return result;
 228   }
 229
 230   /**
 231    * {@inheritDoc}
 232    */
 233   @Override
 234   public List<SequenceFeature> getPositionalFeatures(String... type)
 235   {
 236     List<SequenceFeature> result = new ArrayList<>();
 237
 238     for (FeatureStoreI featureSet : varargToTypes(type))
 239     {
 240       featureSet.getPositionalFeatures(result);
 241     }
 242     return result;
 243   }
 244
 245   /**
 246    * A convenience method that converts a vararg for feature types to an
 247    * Iterable over matched feature sets in key order
 248    *
 249    * @param type
 250    * @return
 251    */
 252   protected Iterable<FeatureStoreI> varargToTypes(String... type)
 253   {
 254     if (type == null || type.length == 0)
 255     {
 256       /*
 257        * no vararg parameter supplied - return all
 258        */
 259       return featureStore.values();
 260     }
 261
 262     List<FeatureStoreI> types = new ArrayList<>();
 263     List<String> args = Arrays.asList(type);
 264     for (Entry<String, FeatureStoreI> featureType : featureStore.entrySet())
 265     {
 266       if (args.contains(featureType.getKey()))
 267       {
 268         types.add(featureType.getValue());
 269       }
 270     }
 271     return types;
 272   }
 273
 274   /**
 275    * {@inheritDoc}
 276    */
 277   @Override
 278   public List<SequenceFeature> getContactFeatures(String... type)
 279   {
 280     List<SequenceFeature> result = new ArrayList<>();
 281
 282     for (FeatureStoreI featureSet : varargToTypes(type))
 283     {
 284       featureSet.getContactFeatures(result);
 285     }
 286     return result;
 287   }
 288
 289   /**
 290    * {@inheritDoc}
 291    */
 292   @Override
 293   public List<SequenceFeature> getNonPositionalFeatures(String... type)
 294   {
 295     List<SequenceFeature> result = new ArrayList<>();
 296
 297     for (FeatureStoreI featureSet : varargToTypes(type))
 298     {
 299       featureSet.getNonPositionalFeatures(result);
 300     }
 301     return result;
 302   }
 303
 304   /**
 305    * {@inheritDoc}
 306    */
 307   @Override
 308   public boolean delete(SequenceFeature sf)
 309   {
 310     for (FeatureStoreI featureSet : featureStore.values())
 311     {
 312       if (featureSet.delete(sf))
 313       {
 314         return true;
 315       }
 316     }
 317     return false;
 318   }
 319
 320   /**
 321    * {@inheritDoc}
 322    */
 323   @Override
 324   public boolean hasFeatures()
 325   {
 326     for (FeatureStoreI featureSet : featureStore.values())
 327     {
 328       if (!featureSet.isEmpty())
 329       {
 330         return true;
 331       }
 332     }
 333     return false;
 334   }
 335
 336   /**
 337    * {@inheritDoc}
 338    */
 339   @Override
 340   public Set<String> getFeatureGroups(boolean positionalFeatures,
 341           String... type)
 342   {
 343     Set<String> groups = new HashSet<>();
 344
 345     for (FeatureStoreI featureSet : varargToTypes(type))
 346     {
 347       groups.addAll(featureSet.getFeatureGroups(positionalFeatures));
 348     }
 349
 350     return groups;
 351   }
 352
 353   /**
 354    * {@inheritDoc}
 355    */
 356   @Override
 357   public Set<String> getFeatureTypesForGroups(boolean positionalFeatures,
 358           String... groups)
 359   {
 360     Set<String> result = new HashSet<>();
 361
 362     for (Entry<String, FeatureStoreI> featureType : featureStore.entrySet())
 363     {
 364       Set<String> featureGroups = featureType.getValue()
 365               .getFeatureGroups(positionalFeatures);
 366       for (String group : groups)
 367       {
 368         if (featureGroups.contains(group))
 369         {
 370           /*
 371            * yes this feature type includes one of the query groups
 372            */
 373           result.add(featureType.getKey());
 374           break;
 375         }
 376       }
 377     }
 378
 379     return result;
 380   }
 381
 382   /**
 383    * {@inheritDoc}
 384    */
 385   @Override
 386   public Set<String> getFeatureTypes(String... soTerm)
 387   {
 388     Set<String> types = new HashSet<>();
 389     for (Entry<String, FeatureStoreI> entry : featureStore.entrySet())
 390     {
 391       String type = entry.getKey();
 392       if (!entry.getValue().isEmpty() && isOntologyTerm(type, soTerm))
 393       {
 394         types.add(type);
 395       }
 396     }
 397     return types;
 398   }
 399
 400   /**
 401    * Answers true if the given type matches one of the specified terms (or is a
 402    * sub-type of one in the Sequence Ontology), or if no terms are supplied.
 403    * Answers false if filter terms are specified and the given term does not
 404    * match any of them.
 405    *
 406    * @param type
 407    * @param soTerm
 408    * @return
 409    */
 410   protected boolean isOntologyTerm(String type, String... soTerm)
 411   {
 412     if (soTerm == null || soTerm.length == 0)
 413     {
 414       return true;
 415     }
 416     SequenceOntologyI so = SequenceOntologyFactory.getSequenceOntology();
 417     for (String term : soTerm)
 418     {
 419       if (type.equals(term) || so.isA(type, term))
 420       {
 421         return true;
 422       }
 423     }
 424     return false;
 425   }
 426
 427   /**
 428    * {@inheritDoc}
 429    */
 430   @Override
 431   public float getMinimumScore(String type, boolean positional)
 432   {
 433     return featureStore.containsKey(type)
 434             ? featureStore.get(type).getMinimumScore(positional)
 435             : Float.NaN;
 436   }
 437
 438   /**
 439    * {@inheritDoc}
 440    */
 441   @Override
 442   public float getMaximumScore(String type, boolean positional)
 443   {
 444     return featureStore.containsKey(type)
 445             ? featureStore.get(type).getMaximumScore(positional)
 446             : Float.NaN;
 447   }
 448
 449   /**
 450    * A convenience method to sort features by start position ascending (if on
 451    * forward strand), or end position descending (if on reverse strand)
 452    *
 453    * @param features
 454    * @param forwardStrand
 455    */
 456   public static void sortFeatures(List<? extends IntervalI> features,
 457           final boolean forwardStrand)
 458   {
 459     IntervalI.sortIntervals(features, forwardStrand);
 460   }
 461
 462   /**
 463    * {@inheritDoc} This method is 'semi-optimised': it only inspects features
 464    * for types that include the specified group, but has to inspect every
 465    * feature of those types for matching feature group. This is efficient unless
 466    * a sequence has features that share the same type but are in different
 467    * groups - an unlikely case.
 468    * <p>
 469    * For example, if RESNUM feature is created with group = PDBID, then features
 470    * would only be retrieved for those sequences associated with the target
 471    * PDBID (group).
 472    */
 473   @Override
 474   public List<SequenceFeature> getFeaturesForGroup(boolean positional,
 475           String group, String... type)
 476   {
 477     List<SequenceFeature> result = new ArrayList<>();
 478     for (FeatureStoreI featureSet : varargToTypes(type))
 479     {
 480       if (featureSet.getFeatureGroups(positional).contains(group))
 481       {
 482         result.addAll(featureSet.getFeaturesForGroup(positional, group));
 483       }
 484     }
 485     return result;
 486   }
 487
 488   /**
 489    * {@inheritDoc}
 490    */
 491   @Override
 492   public boolean shiftFeatures(int fromPosition, int shiftBy)
 493   {
 494     boolean modified = false;
 495     for (FeatureStoreI fs : featureStore.values())
 496     {
 497       modified |= fs.shiftFeatures(fromPosition, shiftBy);
 498     }
 499     return modified;
 500   }
 501
 502   /**
 503    * {@inheritDoc}
 504    */
 505   @Override
 506   public void deleteAll()
 507   {
 508     featureStore.clear();
 509   }
 510
 511   /**
 512    * Simplified find for features associated with a given position.
 513    *
 514    * JavaScript set to not use IntervalI, but easily testable by setting false
 515    * to true in javadoc
 516    *
 517    * FeatureRenderer has checked already that featureStore does contain type.
 518    *
 519    * @author Bob Hanson 2019.07.30
 520    */
 521   @Override
 522   public List<SequenceFeature> findFeatures(int pos, String type,
 523           List<SequenceFeature> list)
 524   {
 525     FeatureStoreI fs = featureStore.get(type);
 526     return fs.findOverlappingFeatures(pos, pos, list);
 527   }
 528
 529   // Chrome; developer console closed
 530
 531   // BH 2019.08.01 useIntervalStore true, redraw false:
 532   // Platform: timer mark 13.848 0.367 overviewrender 16000 pixels row:14
 533   // Platform: timer mark 15.391 0.39 overviewrender 16000 pixels row:14
 534   // Platform: timer mark 16.498 0.39 overviewrender 16000 pixels row:14
 535   // Platform: timer mark 17.596 0.401 overviewrender 16000 pixels row:14
 536   // Platform: timer mark 18.738 0.363 overviewrender 16000 pixels row:14
 537   // Platform: timer mark 19.659 0.358 overviewrender 16000 pixels row:14
 538   // Platform: timer mark 20.737 0.359 overviewrender 16000 pixels row:14
 539   // Platform: timer mark 21.797 0.391 overviewrender 16000 pixels row:14
 540   // Platform: timer mark 22.851 0.361 overviewrender 16000 pixels row:14
 541   // Platform: timer mark 24.019 0.395 overviewrender 16000 pixels row:14
 542
 543   // BH 2019.08.01 useIntervalStore false, redraw false:
 544   // Platform: timer mark 19.011 0.181 overviewrender 16000 pixels row:14
 545   // Platform: timer mark 20.311 0.183 overviewrender 16000 pixels row:14
 546   // Platform: timer mark 21.368 0.175 overviewrender 16000 pixels row:14
 547   // Platform: timer mark 22.347 0.178 overviewrender 16000 pixels row:14
 548   // Platform: timer mark 23.605 0.216 overviewrender 16000 pixels row:14
 549   // Platform: timer mark 24.836 0.191 overviewrender 16000 pixels row:14
 550   // Platform: timer mark 26.016 0.181 overviewrender 16000 pixels row:14
 551   // Platform: timer mark 27.278 0.178 overviewrender 16000 pixels row:14
 552   // Platform: timer mark 28.158 0.181 overviewrender 16000 pixels row:14
 553   // Platform: timer mark 29.227 0.196 overviewrender 16000 pixels row:14
 554   // Platform: timer mark 30.1 0.171 overviewrender 16000 pixels row:14
 555   // Platform: timer mark 31.684 0.196 overviewrender 16000 pixels row:14
 556   // Platform: timer mark 32.779 0.18 overviewrender 16000 pixels row:14
 557   // Platform: timer mark 52.355 0.185 overviewrender 16000 pixels row:14
 558   // Platform: timer mark 53.829 0.186 overviewrender 16000 pixels row:14
 559
 560   /**
 561    * @author Bob Hanson 2019.08.01
 562    */
 563   @Override
 564   public boolean hasFeatures(String type)
 565   {
 566     return featureStore.containsKey(type);
 567   }
 568
 569 }