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