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