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