src/intervalstore/nonc/IntervalStore.java

   1 /*
   2 BSD 3-Clause License
   3
   4 Copyright (c) 2018, Mungo Carstairs
   5 All rights reserved.
   6
   7 Redistribution and use in source and binary forms, with or without
   8 modification, are permitted provided that the following conditions are met:
   9
  10 * Redistributions of source code must retain the above copyright notice, this
  11   list of conditions and the following disclaimer.
  12
  13 * Redistributions in binary form must reproduce the above copyright notice,
  14   this list of conditions and the following disclaimer in the documentation
  15   and/or other materials provided with the distribution.
  16
  17 * Neither the name of the copyright holder nor the names of its
  18   contributors may be used to endorse or promote products derived from
  19   this software without specific prior written permission.
  20
  21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31 */
  32 package intervalstore.nonc;
  33
  34 import java.util.AbstractCollection;
  35 import java.util.ArrayList;
  36 import java.util.Collections;
  37 import java.util.Comparator;
  38 import java.util.Iterator;
  39 import java.util.List;
  40
  41 import intervalstore.api.IntervalI;
  42 import intervalstore.api.IntervalStoreI;
  43
  44
  45 /**
  46  *
  47  * A Collection class to store interval-associated data, with options for "lazy"
  48  * sorting so as to speed incremental construction of the data prior to issuing
  49  * a findOverlap call.
  50  *
  51  *
  52  * with O(log N) performance for overlap queries, insertion and deletion (where
  53  * N is the size of the store).
  54  *
  55  * Accepts duplicate entries but not null values.
  56  *
  57  * @author Bob Hanson 2019.08.06
  58  *
  59  * @param <T>
  60  *          any type providing <code>getBegin()</code>, <code>getEnd()</code>
  61  *          <code>getContainedBy()</code>, and <code>setContainedBy()</code>
  62  */
  63 public class IntervalStore<T extends IntervalI>
  64         extends AbstractCollection<T> implements IntervalStoreI<T>
  65 {
  66
  67   private final boolean DO_PRESORT;
  68
  69   private boolean isSorted;
  70
  71   private List<T> intervals;
  72
  73   private boolean isTainted;
  74
  75   private IntervalI[] orderedIntervalStarts;
  76
  77   private static Comparator<IntervalI> icompare = new IntervalComparator();
  78
  79   static
  80   {
  81     System.out.println("intervalstore.nonc.IntervalStore initialized");
  82   }
  83
  84   // private Comparator<IntervalI> icompare = new IntervalComparator();
  85
  86   /**
  87    * Constructor
  88    */
  89   public IntervalStore()
  90   {
  91
  92     intervals = new ArrayList<>();
  93     DO_PRESORT = true;
  94   };
  95
  96   public IntervalStore(boolean presort)
  97   {
  98     intervals = new ArrayList<>();
  99     DO_PRESORT = presort;
 100   };
 101
 102   /**
 103    * Constructor given a list of intervals. Note that the list may get sorted as
 104    * a side-effect of calling this constructor.
 105    */
 106   public IntervalStore(List<T> intervals)
 107   {
 108     this(intervals, true);
 109   }
 110
 111   /**
 112    * Allows a presort option, which can speed up initial loading of individual
 113    * features but will delay the first findOverlap if set to true.
 114    *
 115    * @param intervals
 116    * @param presort
 117    */
 118   public IntervalStore(List<T> intervals, boolean presort)
 119   {
 120     this.intervals = intervals;
 121     DO_PRESORT = presort;
 122     if (DO_PRESORT)
 123     {
 124       sort();
 125     }
 126     isTainted = true;
 127   }
 128
 129   /**
 130    * Adds one interval to the store.
 131    *
 132    * @param interval
 133    */
 134   @Override
 135   public boolean add(T interval)
 136   {
 137     if (interval == null)
 138     {
 139       return false;
 140     }
 141
 142     synchronized (intervals)
 143     {
 144       if (DO_PRESORT)
 145       {
 146         int insertPosition = findFirstBegin(intervals, interval.getBegin());
 147         intervals.add(insertPosition, interval);
 148         isSorted = true;
 149       }
 150       else
 151       {
 152         intervals.add(interval);
 153         isSorted = false;
 154       }
 155       isTainted = true;
 156       return true;
 157     }
 158   }
 159
 160   @Override
 161   public void clear()
 162   {
 163     intervals.clear();
 164     orderedIntervalStarts = null;
 165     isTainted = true;
 166   }
 167
 168   @Override
 169   public boolean contains(Object entry)
 170   {
 171     return listContains(intervals, entry);
 172   }
 173
 174   private void ensureFinalized()
 175   {
 176     if (isTainted && intervals.size() >= 2)
 177     {
 178       if (!isSorted)
 179       {
 180         sort();
 181       }
 182       orderedIntervalStarts = intervals.toArray(new IntervalI[0]);
 183       linkFeatures(orderedIntervalStarts);
 184       isTainted = false;
 185     }
 186   }
 187
 188   /**
 189    * Sort intervals by start (lowest first) and end (highest first).
 190    */
 191   private void sort()
 192   {
 193     Collections.sort(intervals, icompare);
 194     isSorted = true;
 195   }
 196
 197   protected int findFirstBegin(List<T> list, long pos)
 198   {
 199     int start = 0;
 200     int end = list.size() - 1;
 201     int matched = list.size();
 202
 203     while (start <= end)
 204     {
 205       int mid = (start + end) / 2;
 206       if (list.get(mid).getBegin() >= pos)
 207       {
 208         matched = mid;
 209         end = mid - 1;
 210       }
 211       else
 212       {
 213         start = mid + 1;
 214       }
 215     }
 216     return matched;
 217   }
 218
 219   protected int findFirstEnd(List<T> list, long pos)
 220   {
 221     int start = 0;
 222     int end = list.size() - 1;
 223     int matched = list.size();
 224
 225     while (start <= end)
 226     {
 227       int mid = (start + end) / 2;
 228       if (list.get(mid).getEnd() >= pos)
 229       {
 230         matched = mid;
 231         end = mid - 1;
 232       }
 233       else
 234       {
 235         start = mid + 1;
 236       }
 237     }
 238     return matched;
 239   }
 240
 241   /**
 242    * Adds non-nested intervals to the result list that lie within the target
 243    * range
 244    *
 245    * @param from
 246    * @param to
 247    * @param result
 248    */
 249   protected void findIntervalOverlaps(long from, long to,
 250           List<T> result)
 251   {
 252
 253     int startIndex = findFirstEnd(intervals, from);
 254     final int startIndex1 = startIndex;
 255     int i = startIndex1;
 256     while (i < intervals.size())
 257     {
 258       T sf = intervals.get(i);
 259       if (sf.getBegin() > to)
 260       {
 261         break;
 262       }
 263       if (sf.getBegin() <= to && sf.getEnd() >= from)
 264       {
 265         result.add(sf);
 266       }
 267       i++;
 268     }
 269   }
 270
 271
 272   @Override
 273   public List<T> findOverlaps(long start, long end)
 274   {
 275     return findOverlaps(start, end, null);
 276   }
 277
 278   @SuppressWarnings("unchecked")
 279   @Override
 280   public List<T> findOverlaps(long start, long end, List<T> result)
 281   {
 282
 283     if (result == null)
 284     {
 285       result = new ArrayList<>();
 286     }
 287     int n = intervals.size();
 288     switch (n)
 289     {
 290     case 0:
 291       return result;
 292     case 1:
 293       T sf = intervals.get(0);
 294       if (sf.getBegin() <= end && sf.getEnd() >= start)
 295       {
 296         result.add(sf);
 297       }
 298       return result;
 299     }
 300
 301     ensureFinalized();
 302
 303     // (1) Find the closest feature to this position.
 304
 305     int index = getClosestFeature(orderedIntervalStarts, start);
 306     IntervalI sf = (index < 0 ? null : orderedIntervalStarts[index]);
 307
 308     // (2) Traverse the containedBy field, checking for overlap.
 309
 310     while (sf != null)
 311     {
 312       if (sf.getEnd() >= start)
 313       {
 314         result.add((T) sf);
 315       }
 316       sf = sf.getContainedBy();
 317     }
 318
 319     // (3) For an interval, find the last feature that starts in this interval,
 320     // and add all features up through that feature.
 321
 322     if (end >= start)
 323     {
 324       // fill in with all features that start within this interval, fully
 325       // inclusive
 326       int index2 = getClosestFeature(orderedIntervalStarts, end);
 327       while (++index <= index2)
 328       {
 329         result.add((T) orderedIntervalStarts[index]);
 330       }
 331
 332     }
 333     return result;
 334   }
 335
 336   private int getClosestFeature(IntervalI[] l, long pos)
 337   {
 338     int low = 0;
 339     int high = l.length - 1;
 340     while (low <= high)
 341     {
 342       int mid = (low + high) >>> 1;
 343       IntervalI f = l[mid];
 344       switch (Long.signum(f.getBegin() - pos))
 345       {
 346       case -1:
 347         low = mid + 1;
 348         continue;
 349       case 1:
 350         high = mid - 1;
 351         continue;
 352       case 0:
 353
 354         while (++mid <= high && l[mid].getBegin() == pos)
 355         {
 356           ;
 357         }
 358         return --mid;
 359       }
 360     }
 361     return (high < 0 ? -1 : high);
 362   }
 363
 364   @SuppressWarnings("unchecked")
 365   public T getContainedBy(T sf, T sf0)
 366   {
 367     int begin = sf0.getBegin();
 368     while (sf != null)
 369     {
 370       if (begin <= sf.getEnd())
 371       {
 372         // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
 373         // + "\nFS in " + sf.getIndex1() + ":" + sf);
 374         return sf;
 375       }
 376       sf = (T) sf.getContainedBy();
 377     }
 378     return null;
 379   }
 380
 381   @Override
 382   public int getDepth()
 383   {
 384     int n = intervals.size();
 385     if (n < 2)
 386     {
 387       return n;
 388     }
 389     ensureFinalized();
 390     int maxDepth = 1;
 391     T root = null;
 392     for (int i = 0; i < n; i++)
 393     {
 394       T element = intervals.get(i);
 395       IntervalI container = element;
 396       if (element.getContainedBy() == null)
 397       {
 398         root = element;
 399       }
 400       int depth = 1;
 401       while ((container = container.getContainedBy()) != null)
 402       {
 403         if (++depth > maxDepth && container == root)
 404         {
 405           maxDepth = depth;
 406           break;
 407         }
 408       }
 409     }
 410     return maxDepth;
 411   }
 412
 413   @Override
 414   public boolean isValid()
 415   {
 416     ensureFinalized();
 417     return true;
 418   }
 419
 420   /**
 421    * Answers an iterator over the intervals in the store, with no particular
 422    * ordering guaranteed. The iterator does not support the optional
 423    * <code>remove</code> operation (throws
 424    * <code>UnsupportedOperationException</code> if attempted).
 425    */
 426   @Override
 427   public Iterator<T> iterator()
 428   {
 429     return intervals.iterator();
 430
 431   }
 432
 433   @SuppressWarnings("unchecked")
 434   private void linkFeatures(IntervalI[] features)
 435   {
 436     int n = features.length;
 437     if (n < 2)
 438     {
 439       return;
 440     }
 441     int maxEnd = features[0].getEnd();
 442     for (int i = 1; i < n; i++)
 443     {
 444       T sf = (T) features[i];
 445       if (sf.getBegin() <= maxEnd)
 446       {
 447         sf.setContainedBy(getContainedBy((T) features[i - 1], sf));
 448       }
 449       if (sf.getEnd() > maxEnd)
 450       {
 451         maxEnd = sf.getEnd();
 452       }
 453     }
 454
 455   }
 456
 457   /**
 458    * Answers true if the list contains the interval, else false. This method is
 459    * optimised for the condition that the list is sorted on interval start
 460    * position ascending, and will give unreliable results if this does not hold.
 461    *
 462    * @param intervals
 463    * @param entry
 464    * @return
 465    */
 466   protected boolean listContains(List<T> intervals, Object entry)
 467   {
 468     if (intervals == null || entry == null)
 469     {
 470       return false;
 471     }
 472
 473     if (!isSorted)
 474     {
 475       return intervals.contains(entry);
 476     }
 477
 478     @SuppressWarnings("unchecked")
 479     T interval = (T) entry;
 480
 481     /*
 482      * locate the first entry in the list which does not precede the interval
 483      */
 484     int pos = findFirstBegin(intervals, interval.getBegin());
 485     int len = intervals.size();
 486     while (pos < len)
 487     {
 488       T sf = intervals.get(pos);
 489       if (sf.getBegin() > interval.getBegin())
 490       {
 491         return false; // no match found
 492       }
 493       if (sf.getEnd() == interval.getEnd() && sf.equals(interval))
 494       {
 495         return true;
 496       }
 497       pos++;
 498     }
 499     return false;
 500   }
 501
 502   @Override
 503   public synchronized boolean remove(Object o)
 504   {
 505     // if (o == null)
 506     // {
 507     // throw new NullPointerException();
 508     // }
 509     return (o != null && intervals.size() > 0
 510             && removeInterval((IntervalI) o));
 511   }
 512
 513   /**
 514    * Uses a binary search to find the entry and removes it if found.
 515    *
 516    * @param entry
 517    * @return
 518    */
 519   protected boolean removeInterval(IntervalI entry)
 520   {
 521     if (!isSorted)
 522     {
 523       return intervals.remove(entry);
 524     }
 525
 526     /*
 527      * find the first interval that might match, i.e. whose
 528      * start position is not less than the target range start
 529      * (NB inequality test ensures the first match if any is found)
 530      */
 531     int startIndex = findFirstBegin(intervals, entry.getBegin());
 532
 533     /*
 534      * traverse intervals to look for a match
 535      */
 536     int from = entry.getBegin();
 537     int to = entry.getEnd();
 538     for (int i = startIndex, size = intervals.size(); i < size; i++)
 539     {
 540       T sf = intervals.get(i);
 541       if (sf.getBegin() > from)
 542       {
 543         return false;
 544       }
 545       if (sf.getEnd() == to && sf.equals(entry))
 546       {
 547         intervals.remove(i).setContainedBy(null);
 548         return (isTainted = true);
 549       }
 550     }
 551     return false;
 552   }
 553
 554   @Override
 555   public int size()
 556   {
 557     return intervals.size();
 558   }
 559
 560   @Override
 561   public String toString()
 562   {
 563     return prettyPrint();
 564   }
 565
 566   @Override
 567   public int getWidth()
 568   {
 569     ensureFinalized();
 570     int w = 0;
 571     for (int i = intervals.size(); --i >= 0;)
 572     {
 573       if (intervals.get(i).getContainedBy() == null)
 574       {
 575         w++;
 576       }
 577     }
 578     return w;
 579   }
 580
 581   @Override
 582   public String prettyPrint()
 583   {
 584     int n = intervals.size();
 585     if (n == 0)
 586     {
 587       return "";
 588     }
 589     if (n == 1)
 590     {
 591       return intervals.get(0) + "\n";
 592     }
 593     ensureFinalized();
 594     String sep = "\t";
 595     StringBuffer sb = new StringBuffer();
 596     for (int i = 0; i < n; i++)
 597     {
 598       IntervalI range = orderedIntervalStarts[i];
 599       IntervalI container = range.getContainedBy();
 600       while (container != null)
 601       {
 602         sb.append(sep);
 603         container = container.getContainedBy();
 604       }
 605       sb.append(range.toString()).append('\n');
 606     }
 607     return sb.toString();
 608   }
 609
 610   @Override
 611   public boolean revalidate()
 612   {
 613     isTainted = true;
 614     isSorted = true;
 615     ensureFinalized();
 616     return true;
 617   }
 618
 619   @Override
 620   public IntervalI get(int i)
 621   {
 622     ensureFinalized();
 623     return (i < 0 || i >= orderedIntervalStarts.length ? null
 624             : orderedIntervalStarts[i]);
 625   }
 626
 627 }