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