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