unused/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
  43 /**
  44  * A collection class to store interval-associated data, with O(log N)
  45  * performance for overlap queries, insertion and deletion (where N is the size
  46  * of the store). Accepts duplicate entries but not null values.
  47  *
  48  * @author gmcarstairs
  49  *
  50  * @param <T>
  51  *          any type providing <code>getBegin()</code> and <code>getEnd()</code>
  52  */
  53 public class IntervalStore<T extends IntervalI>
  54         extends AbstractCollection<T>
  55         implements intervalstore.api.IntervalStoreI<T>
  56 {
  57   private List<T> intervals;
  58
  59   private boolean isTainted;
  60
  61   private IntervalI[] orderedIntervalStarts;
  62
  63   /**
  64    * Constructor
  65    */
  66   public IntervalStore()
  67   {
  68     intervals = new ArrayList<>();
  69   }
  70
  71   class IntervalComparator implements Comparator<T>
  72   {
  73
  74     @Override
  75     public int compare(IntervalI o1, IntervalI o2)
  76     {
  77
  78           int order = Integer.compare(o1.getBegin(), o2.getBegin());
  79           if (order == 0)
  80           {
  81             /*
  82              * if tied on start position, longer length sorts to left
  83              * i.e. the negation of normal ordering by length
  84              */
  85             order = Integer.compare(o2.getEnd(), o1.getEnd());
  86           }
  87           return order;
  88
  89     }
  90
  91   };
  92
  93   /**
  94    * Constructor given a list of intervals. Note that the list may get sorted as
  95    * a side-effect of calling this constructor.
  96    */
  97   public IntervalStore(List<T> intervals)
  98   {
  99     Collections.sort(this.intervals = intervals,
 100               new IntervalComparator());
 101       isTainted = true;
 102     findOverlaps(0, -1); // ensure this is ordered
 103   }
 104
 105   /**
 106    * Adds one interval to the store.
 107    *
 108    * @param interval
 109    */
 110   @Override
 111   public boolean add(T interval)
 112   {
 113     if (interval == null)
 114     {
 115       return false;
 116     }
 117
 118     synchronized (intervals)
 119     {
 120       int insertPosition = findFirstBegin(intervals, interval.getBegin());
 121       intervals.add(insertPosition, interval);
 122       isTainted = true;
 123       return true;
 124     }
 125   }
 126
 127   @Override
 128   public void clear()
 129   {
 130     intervals.clear();
 131     orderedIntervalStarts = null;
 132     isTainted = true;
 133   }
 134
 135   @Override
 136   public boolean contains(Object entry)
 137   {
 138     return listContains(intervals, entry);
 139   }
 140
 141   protected int findFirstBegin(List<T> list, long pos)
 142   {
 143     int start = 0;
 144     int end = list.size() - 1;
 145     int matched = list.size();
 146
 147     while (start <= end)
 148     {
 149       int mid = (start + end) / 2;
 150       if (list.get(mid).getBegin() >= pos)
 151       {
 152         matched = mid;
 153         end = mid - 1;
 154       }
 155       else
 156       {
 157         start = mid + 1;
 158       }
 159     }
 160     return matched;
 161   }
 162
 163   protected int findFirstEnd(List<T> list, long pos)
 164   {
 165     int start = 0;
 166     int end = list.size() - 1;
 167     int matched = list.size();
 168
 169     while (start <= end)
 170     {
 171       int mid = (start + end) / 2;
 172       if (list.get(mid).getEnd() >= pos)
 173       {
 174         matched = mid;
 175         end = mid - 1;
 176       }
 177       else
 178       {
 179         start = mid + 1;
 180       }
 181     }
 182     return matched;
 183   }
 184
 185   /**
 186    * Adds non-nested intervals to the result list that lie within the target
 187    * range
 188    *
 189    * @param from
 190    * @param to
 191    * @param result
 192    */
 193   protected void findIntervalOverlaps(long from, long to,
 194           List<T> result)
 195   {
 196
 197     int startIndex = findFirstEnd(intervals, from);
 198     final int startIndex1 = startIndex;
 199     int i = startIndex1;
 200     while (i < intervals.size())
 201     {
 202       T sf = intervals.get(i);
 203       if (sf.getBegin() > to)
 204       {
 205         break;
 206       }
 207       if (sf.getBegin() <= to && sf.getEnd() >= from)
 208       {
 209         result.add(sf);
 210       }
 211       i++;
 212     }
 213   }
 214
 215   @Override
 216   public List<T> findOverlaps(long start, long end)
 217   {
 218
 219     List<T> result = new ArrayList<>();
 220
 221     int n = intervals.size();
 222     switch (n)
 223     {
 224     case 0:
 225       return result;
 226     case 1:
 227       justCheckOne(intervals.get(0), start, end, result);
 228       return result;
 229     default:
 230
 231       if (isTainted)
 232       {
 233         orderedIntervalStarts = intervals.toArray(new IntervalI[0]);
 234         linkFeatures(orderedIntervalStarts);
 235         isTainted = false;
 236       }
 237       break;
 238     }
 239
 240     if (end < start)
 241     {
 242       // just ensuring not tainted -- fully loaded
 243       return result;
 244     }
 245
 246     // (1) Find the closest feature to this position.
 247
 248     int index = getClosestFeature(orderedIntervalStarts, start);
 249     IntervalI sf = (index < 0 ? null : orderedIntervalStarts[index]);
 250
 251     // (2) Traverse the containedBy field, checking for overlap.
 252
 253     while (sf != null)
 254     {
 255       if (sf.getEnd() >= start)
 256       {
 257         result.add((T) sf);
 258       }
 259       sf = sf.getContainedBy();
 260     }
 261
 262     // (3) For an interval, find the last feature that starts in this interval,
 263     // and add all features up through that feature.
 264
 265     if (end >= start)
 266     {
 267       // fill in with all features that start within this interval, fully
 268       // inclusive
 269       int index2 = getClosestFeature(orderedIntervalStarts, end);
 270       while (++index <= index2)
 271       {
 272         result.add((T) orderedIntervalStarts[index]);
 273       }
 274
 275     }
 276     return result;
 277   }
 278
 279   private int getClosestFeature(IntervalI[] l, long pos)
 280   {
 281     int low = 0;
 282     int high = l.length - 1;
 283     while (low <= high)
 284     {
 285       int mid = (low + high) >>> 1;
 286       IntervalI f = l[mid];
 287       switch (Long.signum(f.getBegin() - pos))
 288       {
 289       case -1:
 290         low = mid + 1;
 291         continue;
 292       case 1:
 293         high = mid - 1;
 294         continue;
 295       case 0:
 296
 297         while (++mid <= high && l[mid].getBegin() == pos)
 298         {
 299           ;
 300         }
 301         return --mid;
 302       }
 303     }
 304     return (high < 0 ? -1 : high);
 305   }
 306
 307   @SuppressWarnings("unchecked")
 308   public T getContainedBy(T sf, T sf0)
 309   {
 310     int begin = sf0.getBegin();
 311     while (sf != null)
 312     {
 313       if (begin <= sf.getEnd())
 314       {
 315         // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
 316         // + "\nFS in " + sf.getIndex1() + ":" + sf);
 317         return sf;
 318       }
 319       sf = (T) sf.getContainedBy();
 320     }
 321     return null;
 322   }
 323
 324   @Override
 325   public int getDepth()
 326   {
 327     if (size() == 0)
 328     {
 329       return 0;
 330     }
 331     int maxDepth = 0;
 332     for (int i = intervals.size(); --i >= 0;)
 333     {
 334       T element = intervals.get(i);
 335       T container = element;
 336       int depth = 0;
 337       while ((container = (T) container.getContainedBy()) != null)
 338       {
 339         if (++depth > maxDepth && container == this)
 340         {
 341           maxDepth = depth;
 342           break;
 343         }
 344       }
 345     }
 346     return maxDepth;
 347   }
 348
 349   @Override
 350   public boolean isValid()
 351   {
 352     for (int i = 0; i < intervals.size() - 1; i++)
 353     {
 354       T i1 = intervals.get(i);
 355       T i2 = intervals.get(i + 1);
 356
 357       if (i2.getBegin() < i1.getBegin())
 358       {
 359         System.err.println("nonNested wrong start order : " + i1.toString()
 360                 + ", " + i2.toString());
 361         return false;
 362       }
 363     }
 364     return true;
 365   }
 366
 367   /**
 368    * Answers an iterator over the intervals in the store, with no particular
 369    * ordering guaranteed. The iterator does not support the optional
 370    * <code>remove</code> operation (throws
 371    * <code>UnsupportedOperationException</code> if attempted).
 372    */
 373   @Override
 374   public Iterator<T> iterator()
 375   {
 376     return intervals.iterator();
 377
 378   }
 379
 380   private void justCheckOne(T sf, long start, long end, List<T> result)
 381   {
 382     if (sf.getBegin() <= end && sf.getEnd() >= start)
 383     {
 384       result.add(sf);
 385     }
 386     return;
 387   }
 388
 389   private void linkFeatures(IntervalI[] features)
 390   {
 391     int n = features.length;
 392     switch (n)
 393     {
 394     case 0:
 395       return;
 396     case 1:
 397       features[0].setIndex1(1);
 398       return;
 399     }
 400     int maxEnd = features[0].getEnd();
 401     for (int i = 1; i < n;)
 402     {
 403       T sf = (T) features[i];
 404       sf.setIndex1(++i);
 405       if (sf.getBegin() <= maxEnd)
 406       {
 407         sf.setContainedBy(getContainedBy((T) features[i - 2], sf));
 408       }
 409       if (sf.getEnd() > maxEnd)
 410       {
 411         maxEnd = sf.getEnd();
 412       }
 413     }
 414
 415   }
 416
 417   /**
 418    * Answers true if the list contains the interval, else false. This method is
 419    * optimised for the condition that the list is sorted on interval start
 420    * position ascending, and will give unreliable results if this does not hold.
 421    *
 422    * @param intervals
 423    * @param entry
 424    * @return
 425    */
 426   protected boolean listContains(List<T> intervals, Object entry)
 427   {
 428     if (intervals == null || entry == null)
 429     {
 430       return false;
 431     }
 432
 433     T interval = (T) entry;
 434
 435     /*
 436      * locate the first entry in the list which does not precede the interval
 437      */
 438     int pos = findFirstBegin(intervals, interval.getBegin());
 439     int len = intervals.size();
 440     while (pos < len)
 441     {
 442       T sf = intervals.get(pos);
 443       if (sf.getBegin() > interval.getBegin())
 444       {
 445         return false; // no match found
 446       }
 447       if (sf.getEnd() == interval.getEnd() && sf.equals(interval))
 448       {
 449         return true;
 450       }
 451       pos++;
 452     }
 453     return false;
 454   }
 455
 456   @Override
 457   public String prettyPrint()
 458   {
 459     return toString();
 460   }
 461
 462   @Override
 463   public synchronized boolean remove(Object o)
 464   {
 465     if (o == null || !(o instanceof IntervalI))
 466     {
 467       return false;
 468     }
 469
 470     T entry = (T) o;
 471
 472     /*
 473      * try the non-nested positional intervals first
 474      */
 475     boolean removed = removeInterval(entry);
 476     if (removed)
 477     {
 478       isTainted = true;
 479     }
 480
 481     return removed;
 482
 483   }
 484
 485   /**
 486    * Removes the given entry from the list of non-nested entries, returning true
 487    * if found and removed, or false if not found. Specifically, removes the
 488    * first item in the list for which <code>item.equals(entry)</code>.
 489    *
 490    * @param entry
 491    * @return
 492    */
 493   protected boolean removeInterval(T entry)
 494   {
 495     /*
 496      * find the first interval that might match, i.e. whose
 497      * start position is not less than the target range start
 498      * (NB inequality test ensures the first match if any is found)
 499      */
 500     int startIndex = findFirstBegin(intervals, entry.getBegin());
 501
 502     /*
 503      * traverse intervals to look for a match
 504      */
 505     int from = entry.getBegin();
 506     int i = startIndex;
 507     int size = intervals.size();
 508     while (i < size)
 509     {
 510       T sf = intervals.get(i);
 511       if (sf.getBegin() > from)
 512       {
 513         break;
 514       }
 515       if (sf.equals(entry))
 516       {
 517         intervals.remove(i);
 518         return true;
 519       }
 520       i++;
 521     }
 522     return false;
 523   }
 524
 525   @Override
 526   public int size()
 527   {
 528     return intervals.size();
 529   }
 530
 531   @Override
 532   public String toString()
 533   {
 534     ensureFinalized();
 535     StringBuffer sb = new StringBuffer();
 536
 537     return sb.toString();
 538   }
 539
 540 }