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    * the total length of all positional features; contact features count 1 to
 126    * the total and 1 to size(), consistent with an average 'feature length' of 1
 127    */
 128   int totalExtent;
 129
 130   /**
 131    * Constructor
 132    */
 133   public FeatureStore()
 134   {
 135     nonNestedFeatures = new ArrayList<SequenceFeature>();
 136     positionalFeatureGroups = new HashSet<String>();
 137
 138     // we only construct nonPositionalFeatures, contactFeatures
 139     // or the NCList if we need to
 140   }
 141
 142   /**
 143    * Adds one sequence feature to the store, and returns true, unless the
 144    * feature is already contained in the store, in which case this method
 145    * returns false. Containment is determined by SequenceFeature.equals()
 146    * comparison.
 147    *
 148    * @param feature
 149    */
 150   public boolean addFeature(SequenceFeature feature)
 151   {
 152     /*
 153      * keep a record of feature groups
 154      */
 155     if (!feature.isNonPositional())
 156     {
 157       positionalFeatureGroups.add(feature.getFeatureGroup());
 158     }
 159
 160     boolean added = false;
 161
 162     if (feature.isContactFeature())
 163     {
 164       added = addContactFeature(feature);
 165     }
 166     else if (feature.isNonPositional())
 167     {
 168       added = addNonPositionalFeature(feature);
 169     }
 170     else
 171     {
 172       if (!nonNestedFeatures.contains(feature))
 173       {
 174         added = addNonNestedFeature(feature);
 175         if (!added)
 176         {
 177           /*
 178            * detected a nested feature - put it in the NCList structure
 179            */
 180           added = addNestedFeature(feature);
 181         }
 182       }
 183     }
 184
 185     /*
 186      * record the total extent of positional features, to make
 187      * getTotalFeatureLength possible; we count the length of a
 188      * contact feature as 1
 189      */
 190     if (added)
 191     {
 192       totalExtent += getFeatureLength(feature);
 193     }
 194
 195     return added;
 196   }
 197
 198   /**
 199    * Answers the 'length' of the feature, counting 0 for non-positional features
 200    * and 1 for contact features
 201    *
 202    * @param feature
 203    * @return
 204    */
 205   protected static int getFeatureLength(SequenceFeature feature)
 206   {
 207     if (feature.isNonPositional())
 208     {
 209       return 0;
 210     }
 211     if (feature.isContactFeature())
 212     {
 213       return 1;
 214     }
 215     return 1 + feature.getEnd() - feature.getBegin();
 216   }
 217
 218   /**
 219    * Adds the feature to the list of non-positional features (with lazy
 220    * instantiation of the list if it is null), and returns true. If the
 221    * non-positional features already include the new feature (by equality test),
 222    * then it is not added, and this method returns false. The feature group is
 223    * added to the set of distinct feature groups for non-positional features.
 224    *
 225    * @param feature
 226    */
 227   protected boolean addNonPositionalFeature(SequenceFeature feature)
 228   {
 229     if (nonPositionalFeatures == null)
 230     {
 231       nonPositionalFeatures = new ArrayList<SequenceFeature>();
 232       nonPositionalFeatureGroups = new HashSet<String>();
 233     }
 234     if (nonPositionalFeatures.contains(feature))
 235     {
 236       return false;
 237     }
 238
 239     nonPositionalFeatures.add(feature);
 240
 241     nonPositionalFeatureGroups.add(feature.getFeatureGroup());
 242
 243     return true;
 244   }
 245
 246   /**
 247    * Adds one feature to the NCList that can manage nested features (creating
 248    * the NCList if necessary), and returns true. If the feature is already
 249    * stored in the NCList (by equality test), then it is not added, and this
 250    * method returns false.
 251    */
 252   protected synchronized boolean addNestedFeature(SequenceFeature feature)
 253   {
 254     if (nestedFeatures == null)
 255     {
 256       nestedFeatures = new NCList<SequenceFeature>(feature);
 257       return true;
 258     }
 259     return nestedFeatures.add(feature, false);
 260   }
 261
 262   /**
 263    * Add a feature to the list of non-nested features, maintaining the ordering
 264    * of the list. A check is made for whether the feature is nested in (properly
 265    * contained by) an existing feature. If there is no nesting, the feature is
 266    * added to the list and the method returns true. If nesting is found, the
 267    * feature is not added and the method returns false.
 268    *
 269    * @param feature
 270    * @return
 271    */
 272   protected boolean addNonNestedFeature(SequenceFeature feature)
 273   {
 274     synchronized (nonNestedFeatures)
 275     {
 276       /*
 277        * find the first stored feature which doesn't precede the new one
 278        */
 279       int insertPosition = binarySearch(nonNestedFeatures,
 280               SearchCriterion.byFeature(feature, startOrdering));
 281
 282       /*
 283        * fail if we detect feature enclosure - of the new feature by
 284        * the one preceding it, or of the next feature by the new one
 285        */
 286       if (insertPosition > 0)
 287       {
 288         if (encloses(nonNestedFeatures.get(insertPosition - 1), feature))
 289         {
 290           return false;
 291         }
 292       }
 293       if (insertPosition < nonNestedFeatures.size())
 294       {
 295         if (encloses(feature, nonNestedFeatures.get(insertPosition)))
 296         {
 297           return false;
 298         }
 299       }
 300
 301       /*
 302        * checks passed - add the feature
 303        */
 304       nonNestedFeatures.add(insertPosition, feature);
 305
 306       return true;
 307     }
 308   }
 309
 310   /**
 311    * Answers true if range1 properly encloses range2, else false
 312    *
 313    * @param range1
 314    * @param range2
 315    * @return
 316    */
 317   protected boolean encloses(ContiguousI range1, ContiguousI range2)
 318   {
 319     int begin1 = range1.getBegin();
 320     int begin2 = range2.getBegin();
 321     int end1 = range1.getEnd();
 322     int end2 = range2.getEnd();
 323     if (begin1 == begin2 && end1 > end2)
 324     {
 325       return true;
 326     }
 327     if (begin1 < begin2 && end1 >= end2)
 328     {
 329       return true;
 330     }
 331     return false;
 332   }
 333
 334   /**
 335    * Add a contact feature to the lists that hold them ordered by start (first
 336    * contact) and by end (second contact) position, ensuring the lists remain
 337    * ordered, and returns true. If the contact feature lists already contain the
 338    * given feature (by test for equality), does not add it and returns false.
 339    *
 340    * @param feature
 341    * @return
 342    */
 343   protected synchronized boolean addContactFeature(SequenceFeature feature)
 344   {
 345     if (contactFeatureStarts == null)
 346     {
 347       contactFeatureStarts = new ArrayList<SequenceFeature>();
 348     }
 349     if (contactFeatureEnds == null)
 350     {
 351       contactFeatureEnds = new ArrayList<SequenceFeature>();
 352     }
 353
 354     // TODO binary search for insertion points!
 355     if (contactFeatureStarts.contains(feature))
 356     {
 357       return false;
 358     }
 359
 360     contactFeatureStarts.add(feature);
 361     Collections.sort(contactFeatureStarts, startOrdering);
 362     contactFeatureEnds.add(feature);
 363     Collections.sort(contactFeatureEnds, endOrdering);
 364
 365     return true;
 366   }
 367
 368   /**
 369    * Returns a (possibly empty) list of features whose extent overlaps the given
 370    * range. The returned list is not ordered. Contact features are included if
 371    * either of the contact points lies within the range.
 372    *
 373    * @param start
 374    *          start position of overlap range (inclusive)
 375    * @param end
 376    *          end position of overlap range (inclusive)
 377    * @return
 378    */
 379   public List<SequenceFeature> findOverlappingFeatures(long start, long end)
 380   {
 381     List<SequenceFeature> result = new ArrayList<SequenceFeature>();
 382
 383     findNonNestedFeatures(start, end, result);
 384
 385     findContactFeatures(start, end, result);
 386
 387     if (nestedFeatures != null)
 388     {
 389       result.addAll(nestedFeatures.findOverlaps(start, end));
 390     }
 391
 392     return result;
 393   }
 394
 395   /**
 396    * Adds contact features to the result list where either the second or the
 397    * first contact position lies within the target range
 398    *
 399    * @param from
 400    * @param to
 401    * @param result
 402    */
 403   protected void findContactFeatures(long from, long to,
 404           List<SequenceFeature> result)
 405   {
 406     if (contactFeatureStarts != null)
 407     {
 408       findContactStartFeatures(from, to, result);
 409     }
 410     if (contactFeatureEnds != null)
 411     {
 412       findContactEndFeatures(from, to, result);
 413     }
 414   }
 415
 416   /**
 417    * Adds to the result list any contact features whose end (second contact
 418    * point), but not start (first contact point), lies in the query from-to
 419    * range
 420    *
 421    * @param from
 422    * @param to
 423    * @param result
 424    */
 425   protected void findContactEndFeatures(long from, long to,
 426           List<SequenceFeature> result)
 427   {
 428     /*
 429      * find the first contact feature (if any) that does not lie
 430      * entirely before the target range
 431      */
 432     int startPosition = binarySearch(contactFeatureEnds,
 433             SearchCriterion.byEnd(from));
 434     for (; startPosition < contactFeatureEnds.size(); startPosition++)
 435     {
 436       SequenceFeature sf = contactFeatureEnds.get(startPosition);
 437       if (!sf.isContactFeature())
 438       {
 439         System.err.println("Error! non-contact feature type "
 440                 + sf.getType() + " in contact features list");
 441         continue;
 442       }
 443
 444       int begin = sf.getBegin();
 445       if (begin >= from && begin <= to)
 446       {
 447         /*
 448          * this feature's first contact position lies in the search range
 449          * so we don't include it in results a second time
 450          */
 451         continue;
 452       }
 453
 454       int end = sf.getEnd();
 455       if (end >= from && end <= to)
 456       {
 457         result.add(sf);
 458       }
 459       if (end > to)
 460       {
 461         break;
 462       }
 463     }
 464   }
 465
 466   /**
 467    * Adds non-nested features to the result list that lie within the target
 468    * range. Non-positional features (start=end=0), contact features and nested
 469    * features are excluded.
 470    *
 471    * @param from
 472    * @param to
 473    * @param result
 474    */
 475   protected void findNonNestedFeatures(long from, long to,
 476           List<SequenceFeature> result)
 477   {
 478     int startIndex = binarySearch(nonNestedFeatures,
 479             SearchCriterion.byEnd(from));
 480
 481     findNonNestedFeatures(startIndex, from, to, result);
 482   }
 483
 484   /**
 485    * Scans the list of non-nested features, starting from startIndex, to find
 486    * those that overlap the from-to range, and adds them to the result list.
 487    * Returns the index of the first feature whose start position is after the
 488    * target range (or the length of the whole list if none such feature exists).
 489    *
 490    * @param startIndex
 491    * @param from
 492    * @param to
 493    * @param result
 494    * @return
 495    */
 496   protected int findNonNestedFeatures(final int startIndex, long from,
 497           long to, List<SequenceFeature> result)
 498   {
 499     int i = startIndex;
 500     while (i < nonNestedFeatures.size())
 501     {
 502       SequenceFeature sf = nonNestedFeatures.get(i);
 503       if (sf.getBegin() > to)
 504       {
 505         break;
 506       }
 507       int start = sf.getBegin();
 508       int end = sf.getEnd();
 509       if (start <= to && end >= from)
 510       {
 511         result.add(sf);
 512       }
 513       i++;
 514     }
 515     return i;
 516   }
 517
 518   /**
 519    * Adds contact features whose start position lies in the from-to range to the
 520    * result list
 521    *
 522    * @param from
 523    * @param to
 524    * @param result
 525    */
 526   protected void findContactStartFeatures(long from, long to,
 527           List<SequenceFeature> result)
 528   {
 529     int startPosition = binarySearch(contactFeatureStarts,
 530             SearchCriterion.byStart(from));
 531
 532     for (; startPosition < contactFeatureStarts.size(); startPosition++)
 533     {
 534       SequenceFeature sf = contactFeatureStarts.get(startPosition);
 535       if (!sf.isContactFeature())
 536       {
 537         System.err.println("Error! non-contact feature type "
 538                 + sf.getType() + " in contact features list");
 539         continue;
 540       }
 541       int begin = sf.getBegin();
 542       if (begin >= from && begin <= to)
 543       {
 544         result.add(sf);
 545       }
 546     }
 547   }
 548
 549   /**
 550    * Answers a list of all positional features stored, in no guaranteed order
 551    *
 552    * @return
 553    */
 554   public List<SequenceFeature> getPositionalFeatures()
 555   {
 556     /*
 557      * add non-nested features (may be all features for many cases)
 558      */
 559     List<SequenceFeature> result = new ArrayList<SequenceFeature>();
 560     result.addAll(nonNestedFeatures);
 561
 562     /*
 563      * add any contact features - from the list by start position
 564      */
 565     if (contactFeatureStarts != null)
 566     {
 567       result.addAll(contactFeatureStarts);
 568     }
 569
 570     /*
 571      * add any nested features
 572      */
 573     if (nestedFeatures != null)
 574     {
 575       result.addAll(nestedFeatures.getEntries());
 576     }
 577
 578     return result;
 579   }
 580
 581   /**
 582    * Answers a list of all contact features. If there are none, returns an
 583    * immutable empty list.
 584    *
 585    * @return
 586    */
 587   public List<SequenceFeature> getContactFeatures()
 588   {
 589     if (contactFeatureStarts == null)
 590     {
 591       return Collections.emptyList();
 592     }
 593     return new ArrayList<SequenceFeature>(contactFeatureStarts);
 594   }
 595
 596   /**
 597    * Answers a list of all non-positional features. If there are none, returns
 598    * an immutable empty list.
 599    *
 600    * @return
 601    */
 602   public List<SequenceFeature> getNonPositionalFeatures()
 603   {
 604     if (nonPositionalFeatures == null)
 605     {
 606       return Collections.emptyList();
 607     }
 608     return new ArrayList<SequenceFeature>(nonPositionalFeatures);
 609   }
 610
 611   /**
 612    * Deletes the given feature from the store, returning true if it was found
 613    * (and deleted), else false. This method makes no assumption that the feature
 614    * is in the 'expected' place in the store, in case it has been modified since
 615    * it was added.
 616    *
 617    * @param sf
 618    */
 619   public synchronized boolean delete(SequenceFeature sf)
 620   {
 621     /*
 622      * try the non-nested positional features first
 623      */
 624     boolean removed = nonNestedFeatures.remove(sf);
 625
 626     /*
 627      * if not found, try contact positions (and if found, delete
 628      * from both lists of contact positions)
 629      */
 630     if (!removed && contactFeatureStarts != null)
 631     {
 632       removed = contactFeatureStarts.remove(sf);
 633       if (removed)
 634       {
 635         contactFeatureEnds.remove(sf);
 636       }
 637     }
 638
 639     boolean removedNonPositional = false;
 640
 641     /*
 642      * if not found, try non-positional features
 643      */
 644     if (!removed && nonPositionalFeatures != null)
 645     {
 646       removedNonPositional = nonPositionalFeatures.remove(sf);
 647       removed = removedNonPositional;
 648     }
 649
 650     /*
 651      * if not found, try nested features
 652      */
 653     if (!removed && nestedFeatures != null)
 654     {
 655       removed = nestedFeatures.delete(sf);
 656     }
 657
 658     if (removed)
 659     {
 660       /*
 661        * rescan (positional or non-positional) features to rebuild the
 662        * set of distinct feature groups present
 663        */
 664       rebuildFeatureGroups(sf.getFeatureGroup(), removedNonPositional);
 665
 666       /*
 667        * subtract deleted feature's length from stored total length
 668        * TODO: can start/end have changed since the feature was added?
 669        */
 670       int extent = getFeatureLength(sf);
 671       totalExtent = Math.max(0, totalExtent - extent);
 672     }
 673
 674     return removed;
 675   }
 676
 677   /**
 678    * Check whether the given feature group is still represented, in either
 679    * positional or non-positional features, and if not, remove it from the set
 680    * of feature groups
 681    *
 682    * @param featureGroup
 683    * @param nonPositional
 684    */
 685   protected void rebuildFeatureGroups(String featureGroup,
 686           boolean nonPositional)
 687   {
 688     if (nonPositional && nonPositionalFeatures != null)
 689     {
 690       boolean found = false;
 691       for (SequenceFeature sf : nonPositionalFeatures)
 692       {
 693         String group = sf.getFeatureGroup();
 694         if (featureGroup == group
 695                 || (featureGroup != null && featureGroup.equals(group)))
 696         {
 697           found = true;
 698           break;
 699         }
 700       }
 701       if (!found)
 702       {
 703         nonPositionalFeatureGroups.remove(featureGroup);
 704       }
 705     }
 706     else if (!findFeatureGroup(featureGroup))
 707     {
 708       positionalFeatureGroups.remove(featureGroup);
 709     }
 710   }
 711
 712   /**
 713    * Scans all positional features to check whether the given feature group is
 714    * found, and returns true if found, else false
 715    *
 716    * @param featureGroup
 717    * @return
 718    */
 719   protected boolean findFeatureGroup(String featureGroup)
 720   {
 721     for (SequenceFeature sf : getPositionalFeatures())
 722     {
 723       String group = sf.getFeatureGroup();
 724       if (group == featureGroup
 725               || (group != null && group.equals(featureGroup)))
 726       {
 727         return true;
 728       }
 729     }
 730     return false;
 731   }
 732
 733   /**
 734    * Answers true if this store has no features, else false
 735    *
 736    * @return
 737    */
 738   public boolean isEmpty()
 739   {
 740     boolean hasFeatures = !nonNestedFeatures.isEmpty()
 741             || (contactFeatureStarts != null && !contactFeatureStarts
 742                     .isEmpty())
 743             || (nonPositionalFeatures != null && !nonPositionalFeatures
 744                     .isEmpty())
 745             || (nestedFeatures != null && nestedFeatures.size() > 0);
 746
 747     return !hasFeatures;
 748   }
 749
 750   /**
 751    * Answers the set of distinct feature groups stored, possibly including null,
 752    * as an unmodifiable view of the set. The parameter determines whether the
 753    * groups for positional or for non-positional features are returned.
 754    *
 755    * @param positionalFeatures
 756    * @return
 757    */
 758   public Set<String> getFeatureGroups(boolean positionalFeatures)
 759   {
 760     if (positionalFeatures)
 761     {
 762       return Collections.unmodifiableSet(positionalFeatureGroups);
 763     }
 764     else
 765     {
 766       return nonPositionalFeatureGroups == null ? Collections
 767               .<String> emptySet() : Collections
 768               .unmodifiableSet(nonPositionalFeatureGroups);
 769     }
 770   }
 771
 772   /**
 773    * Performs a binary search of the (sorted) list to find the index of the
 774    * first entry which returns true for the given comparator function. Returns
 775    * the length of the list if there is no such entry.
 776    *
 777    * @param features
 778    * @param sc
 779    * @return
 780    */
 781   protected int binarySearch(List<SequenceFeature> features,
 782           SearchCriterion sc)
 783   {
 784     int start = 0;
 785     int end = features.size() - 1;
 786     int matched = features.size();
 787
 788     while (start <= end)
 789     {
 790       int mid = (start + end) / 2;
 791       SequenceFeature entry = features.get(mid);
 792       boolean compare = sc.compare(entry);
 793       if (compare)
 794       {
 795         matched = mid;
 796         end = mid - 1;
 797       }
 798       else
 799       {
 800         start = mid + 1;
 801       }
 802     }
 803
 804     return matched;
 805   }
 806
 807   /**
 808    * Answers the number of positional (or non-positional) features stored.
 809    * Contact features count as 1.
 810    *
 811    * @param positional
 812    * @return
 813    */
 814   public int getFeatureCount(boolean positional)
 815   {
 816     if (!positional)
 817     {
 818       return nonPositionalFeatures == null ? 0 : nonPositionalFeatures
 819               .size();
 820     }
 821
 822     int size = nonNestedFeatures.size();
 823
 824     if (contactFeatureStarts != null)
 825     {
 826       // note a contact feature (start/end) counts as one
 827       size += contactFeatureStarts.size();
 828     }
 829
 830     if (nestedFeatures != null)
 831     {
 832       size += nestedFeatures.size();
 833     }
 834
 835     return size;
 836   }
 837
 838   /**
 839    * Answers the total length of positional features (or zero if there are
 840    * none). Contact features contribute a value of 1 to the total.
 841    *
 842    * @return
 843    */
 844   public int getTotalFeatureLength()
 845   {
 846     return totalExtent;
 847   }
 848 }