src2/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 import intervalstore.impl.BinarySearcher.Compare;
  43
  44 /**
  45  * A collection class to store interval-associated data, with O(log N)
  46  * performance for overlap queries, insertion and deletion (where N is the size
  47  * of the store). Accepts duplicate entries but not null values.
  48  *
  49  * @author gmcarstairs
  50  *
  51  * @param <T>
  52  *          any type providing <code>getBegin()</code> and <code>getEnd()</code>
  53  */
  54 public class IntervalStore<T extends IntervalI>
  55         extends AbstractCollection<T> implements IntervalStoreI<T>
  56 {
  57   /**
  58    * An iterator over the intervals held in this store, with no particular
  59    * ordering guaranteed. The iterator does not support the optional
  60    * <code>remove</code> operation (throws
  61    * <code>UnsupportedOperationException</code> if attempted).
  62    *
  63    * @author gmcarstairs
  64    *
  65    * @param <V>
  66    */
  67   private class IntervalIterator<V extends IntervalI> implements Iterator<V>
  68   {
  69     /*
  70      * iterator over top level non-nested intervals
  71      */
  72     Iterator<? extends IntervalI> topLevelIterator;
  73
  74     /*
  75      * iterator over NCList (if any)
  76      */
  77     Iterator<? extends IntervalI> nestedIterator;
  78
  79     /**
  80      * Constructor initialises iterators over the top level list and any nested
  81      * NCList
  82      *
  83      * @param intervalStore
  84      */
  85     public IntervalIterator(
  86             IntervalStore<? extends IntervalI> intervalStore)
  87     {
  88       topLevelIterator = nonNested.iterator();
  89       if (nested != null)
  90       {
  91         nestedIterator = nested.iterator();
  92       }
  93     }
  94
  95     @Override
  96     public boolean hasNext()
  97     {
  98       return topLevelIterator.hasNext() ? true
  99               : (nestedIterator != null && nestedIterator.hasNext());
 100     }
 101
 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. Answers true unless the feature is a
 180    * duplicate (already contained), in which case it is not added.
 181    *
 182    * @param interval
 183    */
 184   @Override
 185   public boolean add(T interval)
 186   {
 187     return add(interval, true);
 188   }
 189
 190   @Override
 191   public boolean add(T interval, boolean allowDuplicates)
 192   {
 193     if (interval == null)
 194     {
 195       return false;
 196     }
 197     if (!allowDuplicates && contains(interval))
 198     {
 199       return false;
 200     }
 201
 202     if (!addNonNestedInterval(interval))
 203     {
 204       /*
 205        * detected a nested interval - put it in the NCList structure
 206        */
 207       addNestedInterval(interval);
 208     }
 209     return true;
 210   }
 211
 212   @Override
 213   public boolean contains(Object entry)
 214   {
 215     if (listContains(nonNested, entry))
 216     {
 217       return true;
 218     }
 219
 220     return nested == null ? false : nested.contains(entry);
 221   }
 222
 223   protected boolean addNonNestedInterval(T entry)
 224   {
 225     synchronized (nonNested)
 226     {
 227       /*
 228        * find the first stored interval which doesn't precede the new one
 229        */
 230       int insertPosition = BinarySearcher.findFirst(nonNested, true,
 231               Compare.GE, entry.getBegin());
 232       /*
 233        * fail if we detect interval enclosure
 234        * - of the new interval by the one before or after it
 235        * - of the next interval by the new one
 236        */
 237       if (insertPosition > 0)
 238       {
 239         if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry))
 240         {
 241           return false;
 242         }
 243       }
 244       if (insertPosition < nonNested.size())
 245       {
 246         T following = nonNested.get(insertPosition);
 247         if (entry.properlyContainsInterval(following)
 248                 || following.properlyContainsInterval(entry))
 249         {
 250           return false;
 251         }
 252       }
 253
 254       /*
 255        * checks passed - add the interval
 256        */
 257       nonNested.add(insertPosition, entry);
 258
 259       return true;
 260     }
 261   }
 262
 263   @Override
 264   public List<T> findOverlaps(long from, long to)
 265   {
 266     return findOverlaps(from, to, new ArrayList<>());
 267   }
 268
 269   @Override
 270   public List<T> findOverlaps(long from, long to, List<T> result)
 271   {
 272     if (result == null)
 273     {
 274       result = new ArrayList<>();
 275     }
 276
 277     findNonNestedOverlaps(from, to, result);
 278
 279     if (nested != null)
 280     {
 281       nested.findOverlaps(from, to, result);
 282     }
 283
 284     return result;
 285   }
 286
 287   @Override
 288   public String prettyPrint()
 289   {
 290     String pp = nonNested.toString();
 291     if (nested != null)
 292     {
 293       pp += System.lineSeparator() + nested.prettyPrint();
 294     }
 295     return pp;
 296   }
 297
 298   /**
 299    * Inspects the data store and answers true if it is validly constructed, else
 300    * false. Provided for use in verification by test classes. *
 301    *
 302    * @return
 303    */
 304   public boolean isValid()
 305   {
 306     for (int i = 0; i < nonNested.size() - 1; i++)
 307     {
 308       IntervalI i1 = nonNested.get(i);
 309       IntervalI i2 = nonNested.get(i + 1);
 310
 311       if (i2.getBegin() < i1.getBegin())
 312       {
 313         System.err.println("nonNested wrong start order : " + i1.toString()
 314                 + ", " + i2.toString());
 315         return false;
 316       }
 317       if (i1.properlyContainsInterval(i2)
 318               || i2.properlyContainsInterval(i1))
 319       {
 320         System.err.println("nonNested invalid containment!: "
 321                 + i1.toString()
 322                 + ", " + i2.toString());
 323         return false;
 324       }
 325     }
 326     return nested == null ? true : nested.isValid();
 327   }
 328
 329   @Override
 330   public int size()
 331   {
 332     int i = nonNested.size();
 333     if (nested != null)
 334     {
 335       i += nested.size();
 336     }
 337     return i;
 338   }
 339
 340   @Override
 341   public synchronized boolean remove(Object o)
 342   {
 343     if (o == null)
 344     {
 345       return false;
 346     }
 347     try
 348     {
 349       @SuppressWarnings("unchecked")
 350       T entry = (T) o;
 351
 352       /*
 353        * try the non-nested positional intervals first
 354        */
 355       boolean removed = removeNonNested(entry);
 356
 357       /*
 358        * if not found, try nested intervals
 359        */
 360       if (!removed && nested != null)
 361       {
 362         removed = nested.remove(entry);
 363       }
 364
 365       return removed;
 366     } catch (ClassCastException e)
 367     {
 368       return false;
 369     }
 370   }
 371
 372   /**
 373    * Removes the given entry from the list of non-nested entries, returning true
 374    * if found and removed, or false if not found. Specifically, removes the
 375    * first item in the list for which <code>item.equals(entry)</code>.
 376    *
 377    * @param entry
 378    * @return
 379    */
 380   protected boolean removeNonNested(T entry)
 381   {
 382     /*
 383      * find the first interval that might match, i.e. whose
 384      * start position is not less than the target range start
 385      * (NB inequality test ensures the first match if any is found)
 386      */
 387     int startIndex = BinarySearcher.findFirst(nonNested, true, Compare.GE,
 388             entry.getBegin());
 389
 390     /*
 391      * traverse intervals to look for a match
 392      */
 393     int from = entry.getBegin();
 394     int i = startIndex;
 395     int size = nonNested.size();
 396     while (i < size)
 397     {
 398       T sf = nonNested.get(i);
 399       if (sf.getBegin() > from)
 400       {
 401         break;
 402       }
 403       if (sf.equals(entry))
 404       {
 405         nonNested.remove(i);
 406         return true;
 407       }
 408       i++;
 409     }
 410     return false;
 411   }
 412
 413   /**
 414    * Answers 0 if the store is empty, 1 if there are only top level intervals,
 415    * else 1 plus the depth of the nested intervals (NCList)
 416    */
 417   @Override
 418   public int getDepth()
 419   {
 420     if (size() == 0)
 421     {
 422       return 0;
 423     }
 424     return (nonNested.isEmpty() ? 0 : 1)
 425             + (nested == null ? 0 : nested.getDepth());
 426   }
 427
 428   /**
 429    * Adds one interval to the NCList that can manage nested intervals (creating
 430    * the NCList if necessary)
 431    */
 432   protected synchronized void addNestedInterval(T interval)
 433   {
 434     if (nested == null)
 435     {
 436       nested = new NCList<>();
 437     }
 438     nested.add(interval);
 439   }
 440
 441   /**
 442    * Answers true if the list contains the interval, else false. This method is
 443    * optimised for the condition that the list is sorted on interval start
 444    * position ascending, and will give unreliable results if this does not hold.
 445    *
 446    * @param intervals
 447    * @param entry
 448    * @return
 449    */
 450   protected boolean listContains(List<T> intervals, Object entry)
 451   {
 452     if (intervals == null || entry == null || !(entry instanceof IntervalI))
 453     {
 454       return false;
 455     }
 456
 457     IntervalI interval = (IntervalI) entry;
 458
 459     /*
 460      * locate the first entry in the list which does not precede the interval
 461      */
 462     int pos = BinarySearcher.findFirst(intervals, true, Compare.GE,
 463             interval.getBegin());
 464     int len = intervals.size();
 465     while (pos < len)
 466     {
 467       T sf = intervals.get(pos);
 468       if (sf.getBegin() > interval.getBegin())
 469       {
 470         return false; // no match found
 471       }
 472       if (sf.equals(interval))
 473       {
 474         return true;
 475       }
 476       pos++;
 477     }
 478     return false;
 479   }
 480
 481   /**
 482    * Answers an iterator over the intervals in the store, with no particular
 483    * ordering guaranteed. The iterator does not support the optional
 484    * <code>remove</code> operation (throws
 485    * <code>UnsupportedOperationException</code> if attempted).
 486    */
 487   @Override
 488   public Iterator<T> iterator()
 489   {
 490     return new IntervalIterator<>(this);
 491   }
 492
 493   @Override
 494   public void clear()
 495   {
 496     this.nonNested.clear();
 497     this.nested = new NCList<>();
 498   }
 499
 500   /**
 501    * Adds non-nested intervals to the result list that lie within the target
 502    * range
 503    *
 504    * @param from
 505    * @param to
 506    * @param result
 507    */
 508   protected void findNonNestedOverlaps(long from, long to,
 509           List<T> result)
 510   {
 511     /*
 512      * find the first interval whose end position is
 513      * after the target range start
 514      */
 515     int startIndex = BinarySearcher.findFirst(nonNested, false, Compare.GE,
 516             (int) from);
 517
 518     final int startIndex1 = startIndex;
 519     int i = startIndex1;
 520     while (i < nonNested.size())
 521     {
 522       T sf = nonNested.get(i);
 523       if (sf.getBegin() > to)
 524       {
 525         break;
 526       }
 527       if (sf.getBegin() <= to && sf.getEnd() >= from)
 528       {
 529         result.add(sf);
 530       }
 531       i++;
 532     }
 533   }
 534
 535   @Override
 536   public String toString()
 537   {
 538     String s = nonNested.toString();
 539     if (nested != null)
 540     {
 541       s = s + System.lineSeparator() + nested.toString();
 542     }
 543     return s;
 544   }
 545 }