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