src/intervalstore/impl/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.impl;
  33
  34 import java.util.AbstractCollection;
  35 import java.util.ArrayList;
  36 import java.util.Iterator;
  37 import java.util.List;
  38 import java.util.NoSuchElementException;
  39
  40 import intervalstore.api.IntervalI;
  41 import intervalstore.api.IntervalStoreI;
  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> implements IntervalStoreI<T>
  55 {
  56   /**
  57    * An iterator over the intervals held in this store, with no particular
  58    * ordering guaranteed. The iterator does not support the optional
  59    * <code>remove</code> operation (throws
  60    * <code>UnsupportedOperationException</code> if attempted).
  61    *
  62    * @author gmcarstairs
  63    *
  64    * @param <V>
  65    */
  66   private class IntervalIterator<V extends IntervalI> implements Iterator<V>
  67   {
  68     /*
  69      * iterator over top level non-nested intervals
  70      */
  71     Iterator<? extends IntervalI> topLevelIterator;
  72
  73     /*
  74      * iterator over NCList (if any)
  75      */
  76     Iterator<? extends IntervalI> nestedIterator;
  77
  78     /**
  79      * Constructor initialises iterators over the top level list and any nested
  80      * NCList
  81      *
  82      * @param intervalStore
  83      */
  84     public IntervalIterator(
  85             IntervalStore<? extends IntervalI> intervalStore)
  86     {
  87       topLevelIterator = nonNested.iterator();
  88       if (nested != null)
  89       {
  90         nestedIterator = nested.iterator();
  91       }
  92     }
  93
  94     @Override
  95     public boolean hasNext()
  96     {
  97       return topLevelIterator.hasNext() ? true
  98               : (nestedIterator != null && nestedIterator.hasNext());
  99     }
 100
 101     @SuppressWarnings("unchecked")
 102     @Override
 103     public V next()
 104     {
 105       if (topLevelIterator.hasNext())
 106       {
 107         return (V) topLevelIterator.next();
 108       }
 109       if (nestedIterator != null)
 110       {
 111         return (V) nestedIterator.next();
 112       }
 113       throw new NoSuchElementException();
 114     }
 115
 116   }
 117
 118   private List<T> nonNested;
 119
 120   private NCList<T> nested;
 121
 122   /**
 123    * Constructor
 124    */
 125   public IntervalStore()
 126   {
 127     nonNested = new ArrayList<>();
 128   }
 129
 130   /**
 131    * Constructor given a list of intervals. Note that the list may get sorted as
 132    * a side-effect of calling this constructor.
 133    */
 134   public IntervalStore(List<T> intervals)
 135   {
 136     this();
 137
 138     /*
 139      * partition into subranges whose root intervals
 140      * have no mutual containment (if no intervals are nested,
 141      * each subrange is of length 1 i.e. a single interval)
 142      */
 143     List<IntervalI> sublists = new NCListBuilder<T>()
 144             .partitionNestedSublists(intervals);
 145
 146     /*
 147      * add all 'subrange root intervals' (and any co-located intervals)
 148      * to our top level list of 'non-nested' intervals;
 149      * put aside any left over for our NCList
 150      */
 151     List<T> nested = new ArrayList<>();
 152
 153     for (IntervalI subrange : sublists)
 154     {
 155       int listIndex = subrange.getBegin();
 156       IntervalI root = intervals.get(listIndex);
 157       while (listIndex <= subrange.getEnd())
 158       {
 159         T t = intervals.get(listIndex);
 160         if (root.equalsInterval(t))
 161         {
 162           nonNested.add(t);
 163         }
 164         else
 165         {
 166           nested.add(t);
 167         }
 168         listIndex++;
 169       }
 170     }
 171
 172     if (!nested.isEmpty())
 173     {
 174       this.nested = new NCList<>(nested);
 175     }
 176   }
 177
 178   /**
 179    * Adds one interval to the store.
 180    *
 181    * @param interval
 182    */
 183   @Override
 184   public boolean add(T interval)
 185   {
 186     if (interval == null)
 187     {
 188       return false;
 189     }
 190     if (!addNonNestedInterval(interval))
 191     {
 192       /*
 193        * detected a nested interval - put it in the NCList structure
 194        */
 195       addNestedInterval(interval);
 196     }
 197     return true;
 198   }
 199
 200   @Override
 201   public boolean contains(Object entry)
 202   {
 203     if (listContains(nonNested, entry))
 204     {
 205       return true;
 206     }
 207
 208     return nested == null ? false : nested.contains(entry);
 209   }
 210
 211   protected boolean addNonNestedInterval(T entry)
 212   {
 213     synchronized (nonNested)
 214     {
 215       /*
 216        * find the first stored interval which doesn't precede the new one
 217        */
 218       int insertPosition = BinarySearcher.findFirst(nonNested,
 219               val -> val.getBegin() >= entry.getBegin());
 220       /*
 221        * fail if we detect interval enclosure
 222        * - of the new interval by the one before or after it
 223        * - of the next interval by the new one
 224        */
 225       if (insertPosition > 0)
 226       {
 227         if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry))
 228         {
 229           return false;
 230         }
 231       }
 232       if (insertPosition < nonNested.size())
 233       {
 234         T following = nonNested.get(insertPosition);
 235         if (entry.properlyContainsInterval(following)
 236                 || following.properlyContainsInterval(entry))
 237         {
 238           return false;
 239         }
 240       }
 241
 242       /*
 243        * checks passed - add the interval
 244        */
 245       nonNested.add(insertPosition, entry);
 246
 247       return true;
 248     }
 249   }
 250
 251   @Override
 252   public List<T> findOverlaps(long from, long to)
 253   {
 254     List<T> result = new ArrayList<>();
 255
 256     findNonNestedOverlaps(from, to, result);
 257
 258     if (nested != null)
 259     {
 260       result.addAll(nested.findOverlaps(from, to));
 261     }
 262
 263     return result;
 264   }
 265
 266   @Override
 267   public String prettyPrint()
 268   {
 269     String pp = nonNested.toString();
 270     if (nested != null)
 271     {
 272       pp += System.lineSeparator() + nested.prettyPrint();
 273     }
 274     return pp;
 275   }
 276
 277   @Override
 278   public boolean isValid()
 279   {
 280     for (int i = 0; i < nonNested.size() - 1; i++)
 281     {
 282       IntervalI i1 = nonNested.get(i);
 283       IntervalI i2 = nonNested.get(i + 1);
 284
 285       if (i2.getBegin() < i1.getBegin())
 286       {
 287         System.err.println("nonNested wrong start order : " + i1.toString()
 288                 + ", " + i2.toString());
 289         return false;
 290       }
 291       if (i1.properlyContainsInterval(i2)
 292               || i2.properlyContainsInterval(i1))
 293       {
 294         System.err.println("nonNested invalid containment!: "
 295                 + i1.toString()
 296                 + ", " + i2.toString());
 297         return false;
 298       }
 299     }
 300     return nested == null ? true : nested.isValid();
 301   }
 302
 303   @Override
 304   public int size()
 305   {
 306     int i = nonNested.size();
 307     if (nested != null)
 308     {
 309       i += nested.size();
 310     }
 311     return i;
 312   }
 313
 314   @Override
 315   public synchronized boolean remove(Object o)
 316   {
 317     if (o == null)
 318     {
 319       return false;
 320     }
 321     try
 322     {
 323       @SuppressWarnings("unchecked")
 324       T entry = (T) o;
 325
 326       /*
 327        * try the non-nested positional intervals first
 328        */
 329       boolean removed = removeNonNested(entry);
 330
 331       /*
 332        * if not found, try nested intervals
 333        */
 334       if (!removed && nested != null)
 335       {
 336         removed = nested.remove(entry);
 337       }
 338
 339       return removed;
 340     } catch (ClassCastException e)
 341     {
 342       return false;
 343     }
 344   }
 345
 346   /**
 347    * Removes the given entry from the list of non-nested entries, returning true
 348    * if found and removed, or false if not found. Specifically, removes the
 349    * first item in the list for which <code>item.equals(entry)</code>.
 350    *
 351    * @param entry
 352    * @return
 353    */
 354   protected boolean removeNonNested(T entry)
 355   {
 356     /*
 357      * find the first interval that might match, i.e. whose
 358      * start position is not less than the target range start
 359      * (NB inequality test ensures the first match if any is found)
 360      */
 361     int startIndex = BinarySearcher.findFirst(nonNested,
 362             val -> val.getBegin() >= entry.getBegin());
 363
 364     /*
 365      * traverse intervals to look for a match
 366      */
 367     int from = entry.getBegin();
 368     int i = startIndex;
 369     int size = nonNested.size();
 370     while (i < size)
 371     {
 372       T sf = nonNested.get(i);
 373       if (sf.getBegin() > from)
 374       {
 375         break;
 376       }
 377       if (sf.equals(entry))
 378       {
 379         nonNested.remove(i);
 380         return true;
 381       }
 382       i++;
 383     }
 384     return false;
 385   }
 386
 387   @Override
 388   public int getDepth()
 389   {
 390     if (size() == 0)
 391     {
 392       return 0;
 393     }
 394     return (nonNested.isEmpty() ? 0 : 1)
 395             + (nested == null ? 0 : nested.getDepth());
 396   }
 397
 398   /**
 399    * Adds one interval to the NCList that can manage nested intervals (creating
 400    * the NCList if necessary)
 401    */
 402   protected synchronized void addNestedInterval(T interval)
 403   {
 404     if (nested == null)
 405     {
 406       nested = new NCList<>();
 407     }
 408     nested.add(interval);
 409   }
 410
 411   /**
 412    * Answers true if the list contains the interval, else false. This method is
 413    * optimised for the condition that the list is sorted on interval start
 414    * position ascending, and will give unreliable results if this does not hold.
 415    *
 416    * @param intervals
 417    * @param entry
 418    * @return
 419    */
 420   protected boolean listContains(List<T> intervals, Object entry)
 421   {
 422     if (intervals == null || entry == null || !(entry instanceof IntervalI))
 423     {
 424       return false;
 425     }
 426
 427     IntervalI interval = (IntervalI) entry;
 428
 429     /*
 430      * locate the first entry in the list which does not precede the interval
 431      */
 432     int pos = BinarySearcher.findFirst(intervals,
 433             val -> val.getBegin() >= interval.getBegin());
 434     int len = intervals.size();
 435     while (pos < len)
 436     {
 437       T sf = intervals.get(pos);
 438       if (sf.getBegin() > interval.getBegin())
 439       {
 440         return false; // no match found
 441       }
 442       if (sf.equals(interval))
 443       {
 444         return true;
 445       }
 446       pos++;
 447     }
 448     return false;
 449   }
 450
 451   /**
 452    * Answers an iterator over the intervals in the store, with no particular
 453    * ordering guaranteed. The iterator does not support the optional
 454    * <code>remove</code> operation (throws
 455    * <code>UnsupportedOperationException</code> if attempted).
 456    */
 457   @Override
 458   public Iterator<T> iterator()
 459   {
 460     return new IntervalIterator<>(this);
 461   }
 462
 463   @Override
 464   public void clear()
 465   {
 466     this.nonNested.clear();
 467     this.nested = new NCList<>();
 468   }
 469
 470   /**
 471    * Adds non-nested intervals to the result list that lie within the target
 472    * range
 473    *
 474    * @param from
 475    * @param to
 476    * @param result
 477    */
 478   protected void findNonNestedOverlaps(long from, long to,
 479           List<T> result)
 480   {
 481     /*
 482      * find the first interval whose end position is
 483      * after the target range start
 484      */
 485     int startIndex = BinarySearcher.findFirst(nonNested,
 486             val -> val.getEnd() >= from);
 487
 488     final int startIndex1 = startIndex;
 489     int i = startIndex1;
 490     while (i < nonNested.size())
 491     {
 492       T sf = nonNested.get(i);
 493       if (sf.getBegin() > to)
 494       {
 495         break;
 496       }
 497       if (sf.getBegin() <= to && sf.getEnd() >= from)
 498       {
 499         result.add(sf);
 500       }
 501       i++;
 502     }
 503   }
 504
 505   @Override
 506   public String toString()
 507   {
 508     String s = nonNested.toString();
 509     if (nested != null)
 510     {
 511       s = s + System.lineSeparator() + nested.toString();
 512     }
 513     return s;
 514   }
 515
 516   @Override
 517   public int getWidth()
 518   {
 519     // TODO Auto-generated method stub
 520     return 0;
 521   }
 522
 523   @Override
 524   public List<T> findOverlaps(long start, long end, List<T> result)
 525   {
 526     // TODO Auto-generated method stub
 527     return null;
 528   }
 529
 530   @Override
 531   public boolean revalidate()
 532   {
 533     // TODO Auto-generated method stub
 534     return false;
 535   }
 536
 537   @Override
 538   public IntervalI get(int i)
 539   {
 540     // TODO Auto-generated method stub
 541     return null;
 542   }
 543 }