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