src/jalview/datamodel/features/FeatureStore.java

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