src/jalview/datamodel/features/FeatureStore.java

   1 package jalview.datamodel.features;
   2
   3 import jalview.datamodel.SequenceFeature;
   4
   5 import java.util.ArrayList;
   6 import java.util.Collections;
   7 import java.util.Comparator;
   8 import java.util.HashSet;
   9 import java.util.List;
  10 import java.util.Set;
  11
  12 /**
  13  * A data store for a set of sequence features that supports efficient lookup of
  14  * features overlapping a given range. Intended for (but not limited to) storage
  15  * of features for one sequence and feature type.
  16  *
  17  * @author gmcarstairs
  18  *
  19  */
  20 public class FeatureStore
  21 {
  22   Comparator<ContiguousI> startOrdering = new RangeComparator(true);
  23
  24   Comparator<ContiguousI> endOrdering = new RangeComparator(false);
  25
  26   /*
  27    * Non-positional features have no (zero) start/end position.
  28    * Kept as a separate list in case this criterion changes in future.
  29    */
  30   List<SequenceFeature> nonPositionalFeatures;
  31
  32   /*
  33    * An ordered list of features, with the promise that no feature in the list
  34    * properly contains any other. This constraint allows bounded linear search
  35    * of the list for features overlapping a region.
  36    * Contact features are not included in this list.
  37    */
  38   List<SequenceFeature> nonNestedFeatures;
  39
  40   /*
  41    * contact features ordered by first contact position
  42    */
  43   List<SequenceFeature> contactFeatureStarts;
  44
  45   /*
  46    * contact features ordered by second contact position
  47    */
  48   List<SequenceFeature> contactFeatureEnds;
  49
  50   /*
  51    * Nested Containment List is used to hold any features that are nested
  52    * within (properly contained by) any other feature. This is a recursive tree
  53    * which supports depth-first scan for features overlapping a range.
  54    * It is used here as a 'catch-all' fallback for features that cannot be put
  55    * into a simple ordered list without invalidating the search methods.
  56    */
  57   NCList<SequenceFeature> nestedFeatures;
  58
  59   /*
  60    * Feature groups represented in the stored features
  61    * (possibly including null)
  62    */
  63   Set<String> featureGroups;
  64
  65   /**
  66    * Constructor
  67    */
  68   public FeatureStore()
  69   {
  70     nonNestedFeatures = new ArrayList<SequenceFeature>();
  71     featureGroups = new HashSet<String>();
  72
  73     // we only construct nonPositionalFeatures, contactFeatures
  74     // or the NCList if we need to
  75   }
  76
  77   /**
  78    * Adds one sequence feature to the store, and returns true, unless the
  79    * feature is already contained in the store, in which case this method
  80    * returns false. Containment is determined by SequenceFeature.equals()
  81    * comparison.
  82    *
  83    * @param feature
  84    */
  85   public boolean addFeature(SequenceFeature feature)
  86   {
  87     featureGroups.add(feature.getFeatureGroup());
  88
  89     boolean added = false;
  90
  91     if (feature.isContactFeature())
  92     {
  93       added = addContactFeature(feature);
  94     }
  95     else if (feature.isNonPositional())
  96     {
  97       added = addNonPositionalFeature(feature);
  98     }
  99     else
 100     {
 101       if (!nonNestedFeatures.contains(feature))
 102       {
 103         added = addNonNestedFeature(feature);
 104         if (!added)
 105         {
 106           /*
 107            * detected a nested feature - put it in the NCList structure
 108            */
 109           added = addNestedFeature(feature);
 110         }
 111       }
 112     }
 113
 114     return added;
 115   }
 116
 117   /**
 118    * Adds the feature to the list of non-positional features (with lazy
 119    * instantiation of the list if it is null), and returns true. If the
 120    * non-positional features already include the new feature (by equality test),
 121    * then it is not added, and this method returns false.
 122    *
 123    * @param feature
 124    */
 125   protected boolean addNonPositionalFeature(SequenceFeature feature)
 126   {
 127     if (nonPositionalFeatures == null)
 128     {
 129       nonPositionalFeatures = new ArrayList<SequenceFeature>();
 130     }
 131     if (nonPositionalFeatures.contains(feature))
 132     {
 133       return false;
 134     }
 135     nonPositionalFeatures.add(feature);
 136     return true;
 137   }
 138
 139   /**
 140    * Adds one feature to the NCList that can manage nested features (creating
 141    * the NCList if necessary), and returns true. If the feature is already
 142    * stored in the NCList (by equality test), then it is not added, and this
 143    * method returns false.
 144    */
 145   protected synchronized boolean addNestedFeature(SequenceFeature feature)
 146   {
 147     if (nestedFeatures == null)
 148     {
 149       nestedFeatures = new NCList<SequenceFeature>(feature);
 150       return true;
 151     }
 152     return nestedFeatures.add(feature, false);
 153   }
 154
 155   /**
 156    * Add a feature to the list of non-nested features, maintaining the ordering
 157    * of the list. A check is made for whether the feature is nested in (properly
 158    * contained by) an existing feature. If there is no nesting, the feature is
 159    * added to the list and the method returns true. If nesting is found, the
 160    * feature is not added and the method returns false.
 161    * <p>
 162    * Contact features are added at the position of their first contact point
 163    *
 164    * @param feature
 165    * @return
 166    */
 167   protected boolean addNonNestedFeature(SequenceFeature feature)
 168   {
 169     synchronized (nonNestedFeatures)
 170     {
 171       int insertPosition = binarySearchForAdd(nonNestedFeatures, feature);
 172
 173       /*
 174        * fail if we detect feature enclosure - of the new feature by
 175        * the one preceding it, or of the next feature by the new one
 176        */
 177       if (insertPosition > 0)
 178       {
 179         if (encloses(nonNestedFeatures.get(insertPosition - 1), feature))
 180         {
 181           return false;
 182         }
 183       }
 184       if (insertPosition < nonNestedFeatures.size())
 185       {
 186         if (encloses(feature, nonNestedFeatures.get(insertPosition)))
 187         {
 188           return false;
 189         }
 190       }
 191
 192       /*
 193        * checks passed - add or append the feature
 194        */
 195       if (insertPosition == nonNestedFeatures.size())
 196       {
 197         nonNestedFeatures.add(feature);
 198       }
 199       else
 200       {
 201         nonNestedFeatures.add(insertPosition, feature);
 202       }
 203       return true;
 204     }
 205   }
 206
 207   /**
 208    * Answers true if range1 properly encloses range2, else false
 209    *
 210    * @param range1
 211    * @param range2
 212    * @return
 213    */
 214   protected boolean encloses(ContiguousI range1, ContiguousI range2)
 215   {
 216     int begin1 = range1.getBegin();
 217     int begin2 = range2.getBegin();
 218     int end1 = range1.getEnd();
 219     int end2 = range2.getEnd();
 220     if (begin1 == begin2 && end1 > end2)
 221     {
 222       return true;
 223     }
 224     if (begin1 < begin2 && end1 >= end2)
 225     {
 226       return true;
 227     }
 228     return false;
 229   }
 230
 231   /**
 232    * Answers the index of the first element in the given list which follows or
 233    * matches the given feature in the sort order. If no such element, answers
 234    * the length of the list.
 235    *
 236    * @param list
 237    * @param feature
 238    *
 239    * @return
 240    */
 241   protected int binarySearchForAdd(List<SequenceFeature> list, SequenceFeature feature)
 242   {
 243     // TODO binary search!
 244     int i = 0;
 245     while (i < list.size())
 246     {
 247       if (startOrdering.compare(nonNestedFeatures.get(i), feature) >= 0)
 248       {
 249         break;
 250       }
 251       i++;
 252     }
 253     return i;
 254   }
 255
 256   /**
 257    * Add a contact feature to the lists that hold them ordered by start (first
 258    * contact) and by end (second contact) position, ensuring the lists remain
 259    * ordered, and returns true. If the contact feature lists already contain the
 260    * given feature (by test for equality), does not add it and returns false.
 261    *
 262    * @param feature
 263    * @return
 264    */
 265   protected synchronized boolean addContactFeature(SequenceFeature feature)
 266   {
 267     if (contactFeatureStarts == null)
 268     {
 269       contactFeatureStarts = new ArrayList<SequenceFeature>();
 270     }
 271     if (contactFeatureEnds == null)
 272     {
 273       contactFeatureEnds = new ArrayList<SequenceFeature>();
 274     }
 275
 276     // TODO binary search for insertion points!
 277     if (contactFeatureStarts.contains(feature))
 278     {
 279       return false;
 280     }
 281
 282     contactFeatureStarts.add(feature);
 283     Collections.sort(contactFeatureStarts, startOrdering);
 284     contactFeatureEnds.add(feature);
 285     Collections.sort(contactFeatureEnds, endOrdering);
 286
 287     return true;
 288   }
 289
 290   /**
 291    * Returns a (possibly empty) list of entries whose range overlaps the given
 292    * range. The returned list is not ordered. Contact features are included if
 293    * either of the contact points lies within the range.
 294    *
 295    * @param start
 296    *          start position of overlap range (inclusive)
 297    * @param end
 298    *          end position of overlap range (inclusive)
 299    * @return
 300    */
 301   public List<SequenceFeature> findOverlappingFeatures(long start, long end)
 302   {
 303     List<SequenceFeature> result = new ArrayList<SequenceFeature>();
 304
 305     findNonNestedFeatures(start, end, result);
 306
 307     findContactFeatures(start, end, result);
 308
 309     if (nestedFeatures != null)
 310     {
 311       result.addAll(nestedFeatures.findOverlaps(start, end));
 312     }
 313
 314     return result;
 315   }
 316
 317   /**
 318    * Adds contact features to the result list where either the second or the
 319    * first contact position lies within the target range.
 320    *
 321    * @param from
 322    * @param to
 323    * @param result
 324    */
 325   protected void findContactFeatures(long from, long to,
 326           List<SequenceFeature> result)
 327   {
 328     if (contactFeatureStarts != null)
 329     {
 330       findContactStartFeatures(from, to, result);
 331     }
 332     if (contactFeatureEnds != null)
 333     {
 334       findContactEndFeatures(from, to, result);
 335     }
 336   }
 337
 338   /**
 339    * @param from
 340    * @param to
 341    * @param result
 342    */
 343   protected void findContactEndFeatures(long from, long to,
 344           List<SequenceFeature> result)
 345   {
 346     // TODO binary search for startPosition
 347     for (int startPosition = 0; startPosition < contactFeatureEnds.size(); startPosition++)
 348     {
 349       SequenceFeature sf = contactFeatureEnds.get(startPosition);
 350       if (!sf.isContactFeature())
 351       {
 352         System.err.println("Error! non-contact feature type "
 353                 + sf.getType() + " in contact features list");
 354         continue;
 355       }
 356       int begin = sf.getBegin();
 357       if (begin >= from && begin <= to)
 358       {
 359         /*
 360          * this feature's first contact position lies in the search range
 361          * so we don't include it in results a second time
 362          */
 363         continue;
 364       }
 365       int end = sf.getEnd();
 366       if (end >= from && end <= to)
 367       {
 368         result.add(sf);
 369       }
 370     }
 371   }
 372
 373   /**
 374    * Returns the index of the first contact feature found whose end (second
 375    * contact position) is not before the given start position. If no such
 376    * feature is found, returns the length of the contact features list.
 377    *
 378    * @param start
 379    * @return
 380    */
 381   protected int contactsBinarySearch(long start)
 382   {
 383     // TODO binary search!!
 384     int i = 0;
 385     while (i < contactFeatureEnds.size())
 386     {
 387       if (contactFeatureEnds.get(i).getEnd() >= start)
 388       {
 389         break;
 390       }
 391       i++;
 392     }
 393
 394     return i;
 395   }
 396
 397   /**
 398    * Adds features to the result list that are at a single position which lies
 399    * within the target range. Non-positional features (start=end=0) and contact
 400    * features are excluded.
 401    *
 402    * @param from
 403    * @param to
 404    * @param result
 405    */
 406   protected void findNonNestedFeatures(long from, long to,
 407           List<SequenceFeature> result)
 408   {
 409     int startIndex = binarySearch(nonNestedFeatures, from);
 410     findNonNestedFeatures(startIndex, from, to, result);
 411   }
 412
 413   /**
 414    * Scans the list of non-nested features, starting from startIndex, to find
 415    * those that overlap the from-to range, and adds them to the result list.
 416    * Returns the index of the first feature whose start position is after the
 417    * target range (or the length of the whole list if none such feature exists).
 418    *
 419    * @param startIndex
 420    * @param from
 421    * @param to
 422    * @param result
 423    * @return
 424    */
 425   protected int findNonNestedFeatures(final int startIndex, long from,
 426           long to,
 427           List<SequenceFeature> result)
 428   {
 429     int i = startIndex;
 430     while (i < nonNestedFeatures.size())
 431     {
 432       SequenceFeature sf = nonNestedFeatures.get(i);
 433       if (sf.getBegin() > to)
 434       {
 435         break;
 436       }
 437       int start = sf.getBegin();
 438       int end = sf.getEnd();
 439       if (start <= to && end >= from)
 440       {
 441         result.add(sf);
 442       }
 443       i++;
 444     }
 445     return i;
 446   }
 447
 448   /**
 449    * Performs a binary search of the (sorted) list to find the index of the
 450    * first entry whose end position is not less than the target position (i.e.
 451    * skip all features that properly precede the given position)
 452    *
 453    * @param features
 454    * @param target
 455    * @return
 456    */
 457   protected int binarySearch(List<SequenceFeature> features, long target)
 458   {
 459     int width = features.size() / 2;
 460     int lastpos = width;
 461     while (width > 0)
 462     {
 463       int end = features.get(lastpos).getEnd();
 464       width = width / 2;
 465       if (end > target)
 466       {
 467         lastpos -= width;
 468       }
 469       else
 470       {
 471         lastpos += width;
 472       }
 473     }
 474     // todo correct binary search
 475     return lastpos > 1 ? lastpos - 2 : 0;
 476     // return lastpos;
 477   }
 478
 479   /**
 480    * Adds contact features whose start position lies in the from-to range to the
 481    * result list
 482    *
 483    * @param from
 484    * @param to
 485    * @param result
 486    */
 487   protected void findContactStartFeatures(long from, long to,
 488           List<SequenceFeature> result)
 489   {
 490     // TODO binary search for startPosition
 491     for (int startPosition = 0; startPosition < contactFeatureStarts.size(); startPosition++)
 492     {
 493       SequenceFeature sf = contactFeatureStarts.get(startPosition);
 494       if (!sf.isContactFeature())
 495       {
 496         System.err.println("Error! non-contact feature type "
 497                 + sf.getType() + " in contact features list");
 498         continue;
 499       }
 500       int begin = sf.getBegin();
 501       if (begin >= from && begin <= to)
 502       {
 503         result.add(sf);
 504       }
 505     }
 506   }
 507
 508   /**
 509    * Answers a list of all features stored (including any non-positional
 510    * features), in no guaranteed order
 511    *
 512    * @return
 513    */
 514   public List<SequenceFeature> getFeatures()
 515   {
 516     /*
 517      * add non-nested features (may be all features for many cases)
 518      */
 519     List<SequenceFeature> result = new ArrayList<SequenceFeature>();
 520     result.addAll(nonNestedFeatures);
 521
 522     /*
 523      * add any contact features - from the list by start position
 524      */
 525     if (contactFeatureStarts != null)
 526     {
 527       result.addAll(contactFeatureStarts);
 528     }
 529
 530     /*
 531      * add any non-positional features
 532      */
 533     if (nonPositionalFeatures != null)
 534     {
 535       result.addAll(nonPositionalFeatures);
 536     }
 537
 538     /*
 539      * add any nested features
 540      */
 541     if (nestedFeatures != null)
 542     {
 543       result.addAll(nestedFeatures.getEntries());
 544     }
 545
 546     return result;
 547   }
 548
 549   /**
 550    * Answers a list of all contact features. If there are none, returns an
 551    * immutable empty list.
 552    *
 553    * @return
 554    */
 555   public List<SequenceFeature> getContactFeatures()
 556   {
 557     if (contactFeatureStarts == null)
 558     {
 559       return Collections.emptyList();
 560     }
 561     return new ArrayList<SequenceFeature>(contactFeatureStarts);
 562   }
 563
 564   /**
 565    * Answers a list of all non-positional features. If there are none, returns
 566    * an immutable empty list.
 567    *
 568    * @return
 569    */
 570   public List<SequenceFeature> getNonPositionalFeatures()
 571   {
 572     if (nonPositionalFeatures == null)
 573     {
 574       return Collections.emptyList();
 575     }
 576     return new ArrayList<SequenceFeature>(nonPositionalFeatures);
 577   }
 578
 579   /**
 580    * Deletes the given feature from the store, returning true if it was found
 581    * (and deleted), else false. This method makes no assumption that the feature
 582    * is in the 'expected' place in the store, in case it has been modified since
 583    * it was added.
 584    *
 585    * @param sf
 586    */
 587   public synchronized boolean delete(SequenceFeature sf)
 588   {
 589     /*
 590      * try the non-nested positional features first
 591      */
 592     boolean removed = nonNestedFeatures.remove(sf);
 593
 594     /*
 595      * if not found, try contact positions (and if found, delete
 596      * from both lists of contact positions)
 597      */
 598     if (!removed && contactFeatureStarts != null)
 599     {
 600       removed = contactFeatureStarts.remove(sf);
 601       if (removed)
 602       {
 603         contactFeatureEnds.remove(sf);
 604       }
 605     }
 606
 607     /*
 608      * if not found, try non-positional features
 609      */
 610     if (!removed && nonPositionalFeatures != null)
 611     {
 612       removed = nonPositionalFeatures.remove(sf);
 613     }
 614
 615     /*
 616      * if not found, try nested features
 617      */
 618     if (!removed && nestedFeatures != null)
 619     {
 620       removed = nestedFeatures.delete(sf);
 621     }
 622
 623     if (removed)
 624     {
 625       /*
 626        * if this was the only feature for its feature group,
 627        * remove the group from the stored set
 628        */
 629       String featureGroup = sf.getFeatureGroup();
 630       if (!findFeatureGroup(featureGroup))
 631       {
 632         featureGroups.remove(featureGroup);
 633       }
 634     }
 635
 636     return removed;
 637   }
 638
 639   /**
 640    * Scans all features to check whether the given feature group is found, and
 641    * returns true if found, else false
 642    *
 643    * @param featureGroup
 644    * @return
 645    */
 646   protected boolean findFeatureGroup(String featureGroup)
 647   {
 648     for (SequenceFeature sf : getFeatures())
 649     {
 650       String group = sf.getFeatureGroup();
 651       if (group == featureGroup
 652               || (group != null && group.equals(featureGroup)))
 653       {
 654         return true;
 655       }
 656     }
 657     return false;
 658   }
 659
 660   /**
 661    * Answers true if this store has no features, else false
 662    *
 663    * @return
 664    */
 665   public boolean isEmpty()
 666   {
 667     boolean hasFeatures = !nonNestedFeatures.isEmpty()
 668             || (contactFeatureStarts != null && !contactFeatureStarts
 669                     .isEmpty())
 670             || (nonPositionalFeatures != null && !nonPositionalFeatures
 671                     .isEmpty())
 672             || (nestedFeatures != null && nestedFeatures.size() > 0);
 673
 674     return !hasFeatures;
 675   }
 676
 677   /**
 678    * Answers the set of distinct feature groups stored, possibly including null,
 679    * as an unmodifiable view of the set.
 680    *
 681    * @return
 682    */
 683   public Set<String> getFeatureGroups()
 684   {
 685     return Collections.unmodifiableSet(featureGroups);
 686   }
 687 }