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.
  13  *
  14  * @author gmcarstairs
  15  *
  16  */
  17 public class FeatureStore
  18 {
  19   Comparator<ContiguousI> startOrdering = new RangeComparator(true);
  20
  21   Comparator<ContiguousI> endOrdering = new RangeComparator(false);
  22
  23   /*
  24    * An ordered list of features, with the promise that no feature in the list
  25    * properly contains any other. This constraint allows bounded linear search
  26    * of the list for features overlapping a region.
  27    * Contact features are not included in this list.
  28    */
  29   List<SequenceFeature> nonNestedFeatures;
  30
  31   /*
  32    * contact features ordered by first contact position
  33    */
  34   List<SequenceFeature> contactFeatureStarts;
  35
  36   /*
  37    * contact features ordered by second contact position
  38    */
  39   List<SequenceFeature> contactFeatureEnds;
  40
  41   /*
  42    * Nested Containment List is used to hold any features that are nested
  43    * within (properly contained by) any other feature. This is a recursive tree
  44    * which supports depth-first scan for features overlapping a range.
  45    * It is used here as a 'catch-all' fallback for features that cannot be put
  46    * into a simple ordered list without invalidating the search methods.
  47    */
  48   NCList<SequenceFeature> nestedFeatures;
  49
  50   /**
  51    * Constructor
  52    */
  53   public FeatureStore()
  54   {
  55     nonNestedFeatures = new ArrayList<SequenceFeature>();
  56     // we only construct contactFeatures and the NCList if we need to
  57   }
  58
  59   /**
  60    * Add one entry to the data store
  61    *
  62    * @param feature
  63    */
  64   public void addFeature(SequenceFeature feature)
  65   {
  66     if (feature.isContactFeature())
  67     {
  68       addContactFeature(feature);
  69     }
  70     else
  71     {
  72       boolean added = addNonNestedFeature(feature);
  73       if (!added)
  74       {
  75         /*
  76          * detected a nested feature - put it in the NCList structure
  77          */
  78         addNestedFeature(feature);
  79       }
  80     }
  81   }
  82
  83   /**
  84    * Adds one feature to the NCList that can manage nested features (creating
  85    * the NCList if necessary)
  86    */
  87   protected synchronized void addNestedFeature(SequenceFeature feature)
  88   {
  89     if (nestedFeatures == null)
  90     {
  91       nestedFeatures = new NCList<SequenceFeature>(feature);
  92     }
  93     else
  94     {
  95       nestedFeatures.add(feature);
  96     }
  97   }
  98
  99   /**
 100    * Add a feature to the list of non-nested features, maintaining the ordering
 101    * of the list. A check is made for whether the feature is nested in (properly
 102    * contained by) an existing feature. If there is no nesting, the feature is
 103    * added to the list and the method returns true. If nesting is found, the
 104    * feature is not added and the method returns false.
 105    * <p>
 106    * Contact features are added at the position of their first contact point
 107    *
 108    * @param feature
 109    * @return
 110    */
 111   protected boolean addNonNestedFeature(SequenceFeature feature)
 112   {
 113     synchronized (nonNestedFeatures)
 114     {
 115       int insertPosition = binarySearchForAdd(nonNestedFeatures, feature);
 116
 117       /*
 118        * fail if we detect feature enclosure - of the new feature by
 119        * the one preceding it, or of the next feature by the new one
 120        */
 121       if (insertPosition > 0)
 122       {
 123         if (encloses(nonNestedFeatures.get(insertPosition - 1), feature))
 124         {
 125           return false;
 126         }
 127       }
 128       if (insertPosition < nonNestedFeatures.size())
 129       {
 130         if (encloses(feature, nonNestedFeatures.get(insertPosition)))
 131         {
 132           return false;
 133         }
 134       }
 135
 136       /*
 137        * checks passed - add or append the feature
 138        */
 139       if (insertPosition == nonNestedFeatures.size())
 140       {
 141         nonNestedFeatures.add(feature);
 142       }
 143       else
 144       {
 145         nonNestedFeatures.add(insertPosition, feature);
 146       }
 147       return true;
 148     }
 149   }
 150
 151   /**
 152    * Answers true if range1 properly encloses range2, else false
 153    *
 154    * @param range1
 155    * @param range2
 156    * @return
 157    */
 158   protected boolean encloses(ContiguousI range1, ContiguousI range2)
 159   {
 160     int begin1 = range1.getBegin();
 161     int begin2 = range2.getBegin();
 162     int end1 = range1.getEnd();
 163     int end2 = range2.getEnd();
 164     if (begin1 == begin2 && end1 > end2)
 165     {
 166       return true;
 167     }
 168     if (begin1 < begin2 && end1 >= end2)
 169     {
 170       return true;
 171     }
 172     return false;
 173   }
 174
 175   /**
 176    * Answers the index of the first element in the given list which follows or
 177    * matches the given feature in the sort order. If no such element, answers
 178    * the length of the list.
 179    *
 180    * @param list
 181    * @param feature
 182    *
 183    * @return
 184    */
 185   protected int binarySearchForAdd(List<SequenceFeature> list, SequenceFeature feature)
 186   {
 187     // TODO binary search!
 188     int i = 0;
 189     while (i < list.size())
 190     {
 191       if (startOrdering.compare(nonNestedFeatures.get(i), feature) >= 0)
 192       {
 193         break;
 194       }
 195       i++;
 196     }
 197     return i;
 198   }
 199
 200   /**
 201    * Add a contact feature to the lists that hold them ordered by start (first
 202    * contact) and by end (second contact) position, ensuring the lists remain
 203    * ordered
 204    *
 205    * @param feature
 206    */
 207   protected synchronized void addContactFeature(SequenceFeature feature)
 208   {
 209     // TODO binary search for insertion points!
 210     if (contactFeatureStarts == null)
 211     {
 212       contactFeatureStarts = new ArrayList<SequenceFeature>();
 213     }
 214     if (contactFeatureEnds == null)
 215     {
 216       contactFeatureEnds = new ArrayList<SequenceFeature>();
 217     }
 218     contactFeatureStarts.add(feature);
 219     Collections.sort(contactFeatureStarts, startOrdering);
 220     contactFeatureEnds.add(feature);
 221     Collections.sort(contactFeatureEnds, endOrdering);
 222   }
 223
 224   /**
 225    * Returns a (possibly empty) list of entries whose range overlaps the given
 226    * range. The returned list is not ordered. Contact features are included if
 227    * either of the contact points lies within the range.
 228    *
 229    * @param start
 230    *          start position of overlap range (inclusive)
 231    * @param end
 232    *          end position of overlap range (inclusive)
 233    * @return
 234    */
 235   public List<SequenceFeature> findOverlappingFeatures(long start, long end)
 236   {
 237     List<SequenceFeature> result = new ArrayList<SequenceFeature>();
 238
 239     findNonNestedFeatures(start, end, result);
 240
 241     findContactFeatures(start, end, result);
 242
 243     if (nestedFeatures != null)
 244     {
 245       result.addAll(nestedFeatures.findOverlaps(start, end));
 246     }
 247
 248     return result;
 249   }
 250
 251   /**
 252    * Adds contact features to the result list where either the second or the
 253    * first contact position lies within the target range.
 254    *
 255    * @param from
 256    * @param to
 257    * @param result
 258    */
 259   protected void findContactFeatures(long from, long to,
 260           List<SequenceFeature> result)
 261   {
 262     if (contactFeatureStarts != null)
 263     {
 264       findContactStartFeatures(from, to, result);
 265     }
 266     if (contactFeatureEnds != null)
 267     {
 268       findContactEndFeatures(from, to, result);
 269     }
 270   }
 271
 272   /**
 273    * @param from
 274    * @param to
 275    * @param result
 276    */
 277   protected void findContactEndFeatures(long from, long to,
 278           List<SequenceFeature> result)
 279   {
 280     // TODO binary search for startPosition
 281     for (int startPosition = 0; startPosition < contactFeatureEnds.size(); startPosition++)
 282     {
 283       SequenceFeature sf = contactFeatureEnds.get(startPosition);
 284       if (!sf.isContactFeature())
 285       {
 286         System.err.println("Error! non-contact feature type "
 287                 + sf.getType() + " in contact features list");
 288         continue;
 289       }
 290       int begin = sf.getBegin();
 291       if (begin >= from && begin <= to)
 292       {
 293         /*
 294          * this feature's first contact position lies in the search range
 295          * so we don't include it in results a second time
 296          */
 297         continue;
 298       }
 299       int end = sf.getEnd();
 300       if (end >= from && end <= to)
 301       {
 302         result.add(sf);
 303       }
 304     }
 305   }
 306
 307   /**
 308    * Returns the index of the first contact feature found whose end (second
 309    * contact position) is not before the given start position. If no such
 310    * feature is found, returns the length of the contact features list.
 311    *
 312    * @param start
 313    * @return
 314    */
 315   protected int contactsBinarySearch(long start)
 316   {
 317     // TODO binary search!!
 318     int i = 0;
 319     while (i < contactFeatureEnds.size())
 320     {
 321       if (contactFeatureEnds.get(i).getEnd() >= start)
 322       {
 323         break;
 324       }
 325       i++;
 326     }
 327
 328     return i;
 329   }
 330
 331   /**
 332    * Adds features to the result list that are at a single position which lies
 333    * within the target range. Non-positional features (start=end=0) and contact
 334    * features are excluded.
 335    *
 336    * @param from
 337    * @param to
 338    * @param result
 339    */
 340   protected void findNonNestedFeatures(long from, long to,
 341           List<SequenceFeature> result)
 342   {
 343     int startIndex = binarySearch(nonNestedFeatures, from);
 344     findNonNestedFeatures(startIndex, from, to, result);
 345   }
 346
 347   /**
 348    * Scans the list of non-nested features, starting from startIndex, to find
 349    * those that overlap the from-to range, and adds them to the result list.
 350    * Returns the index of the first feature whose start position is after the
 351    * target range (or the length of the whole list if none such feature exists).
 352    *
 353    * @param startIndex
 354    * @param from
 355    * @param to
 356    * @param result
 357    * @return
 358    */
 359   protected int findNonNestedFeatures(final int startIndex, long from,
 360           long to,
 361           List<SequenceFeature> result)
 362   {
 363     int i = startIndex;
 364     while (i < nonNestedFeatures.size())
 365     {
 366       SequenceFeature sf = nonNestedFeatures.get(i);
 367       if (sf.getBegin() > to)
 368       {
 369         break;
 370       }
 371       int start = sf.getBegin();
 372       int end = sf.getEnd();
 373       if (sf.isContactFeature())
 374       {
 375         end = start;
 376       }
 377       if (start <= to && end >= from)
 378       {
 379         result.add(sf);
 380       }
 381       i++;
 382     }
 383     return i;
 384   }
 385
 386   /**
 387    * Performs a binary search of the (sorted) list to find the index of the
 388    * first entry whose end position is not less than the target position (i.e.
 389    * skip all features that properly precede the given position)
 390    *
 391    * @param features
 392    * @param target
 393    * @return
 394    */
 395   protected int binarySearch(List<SequenceFeature> features, long target)
 396   {
 397     int width = features.size() / 2;
 398     int lastpos = width;
 399     while (width > 0)
 400     {
 401       int end = features.get(lastpos).getEnd();
 402       width = width / 2;
 403       if (end > target)
 404       {
 405         lastpos -= width;
 406       }
 407       else
 408       {
 409         lastpos += width;
 410       }
 411     }
 412     // todo correct binary search
 413     return lastpos > 1 ? lastpos - 2 : 0;
 414     // return lastpos;
 415   }
 416
 417   /**
 418    * Adds contact features whose start position lies in the from-to range to the
 419    * result list
 420    *
 421    * @param from
 422    * @param to
 423    * @param result
 424    */
 425   protected void findContactStartFeatures(long from, long to,
 426           List<SequenceFeature> result)
 427   {
 428     // TODO binary search for startPosition
 429     for (int startPosition = 0; startPosition < contactFeatureStarts.size(); startPosition++)
 430     {
 431       SequenceFeature sf = contactFeatureStarts.get(startPosition);
 432       if (!sf.isContactFeature())
 433       {
 434         System.err.println("Error! non-contact feature type "
 435                 + sf.getType() + " in contact features list");
 436         continue;
 437       }
 438       int begin = sf.getBegin();
 439       if (begin >= from && begin <= to)
 440       {
 441         result.add(sf);
 442       }
 443     }
 444   }
 445 }