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               entry.getBegin(),
 220               BinarySearcher.fbegin);
 221       /*
 222        * fail if we detect interval enclosure
 223        * - of the new interval by the one before or after it
 224        * - of the next interval by the new one
 225        */
 226       if (insertPosition > 0)
 227       {
 228         if (nonNested.get(insertPosition - 1)
 229                 .properlyContainsInterval(entry))
 230         {
 231           return false;
 232         }
 233       }
 234       if (insertPosition < nonNested.size())
 235       {
 236         T following = nonNested.get(insertPosition);
 237         if (entry.properlyContainsInterval(following)
 238                 || following.properlyContainsInterval(entry))
 239         {
 240           return false;
 241         }
 242       }
 243
 244       /*
 245        * checks passed - add the interval
 246        */
 247       nonNested.add(insertPosition, entry);
 248
 249       return true;
 250     }
 251   }
 252
 253   @Override
 254   public List<T> findOverlaps(long from, long to)
 255   {
 256     List<T> result = new ArrayList<>();
 257
 258     findNonNestedOverlaps(from, to, result);
 259
 260     if (nested != null)
 261     {
 262       nested.findOverlaps(from, to, result);
 263     }
 264
 265     return result;
 266   }
 267
 268   @Override
 269   public String prettyPrint()
 270   {
 271     String pp = nonNested.toString();
 272     if (nested != null)
 273     {
 274       pp += '\n' + nested.prettyPrint();
 275     }
 276     return pp;
 277   }
 278
 279   @Override
 280   public boolean isValid()
 281   {
 282     for (int i = 0; i < nonNested.size() - 1; i++)
 283     {
 284       IntervalI i1 = nonNested.get(i);
 285       IntervalI i2 = nonNested.get(i + 1);
 286
 287       if (i2.getBegin() < i1.getBegin())
 288       {
 289         System.err.println("nonNested wrong start order : " + i1.toString()
 290                 + ", " + i2.toString());
 291         return false;
 292       }
 293       if (i1.properlyContainsInterval(i2)
 294               || i2.properlyContainsInterval(i1))
 295       {
 296         System.err.println("nonNested invalid containment!: "
 297                 + i1.toString()
 298                 + ", " + i2.toString());
 299         return false;
 300       }
 301     }
 302     return nested == null ? true : nested.isValid();
 303   }
 304
 305   @Override
 306   public int size()
 307   {
 308     int i = nonNested.size();
 309     if (nested != null)
 310     {
 311       i += nested.size();
 312     }
 313     return i;
 314   }
 315
 316   @Override
 317   public synchronized boolean remove(Object o)
 318   {
 319     if (o == null)
 320     {
 321       return false;
 322     }
 323     try
 324     {
 325       @SuppressWarnings("unchecked")
 326       T entry = (T) o;
 327
 328       /*
 329        * try the non-nested positional intervals first
 330        */
 331       boolean removed = removeNonNested(entry);
 332
 333       /*
 334        * if not found, try nested intervals
 335        */
 336       if (!removed && nested != null)
 337       {
 338         removed = nested.remove(entry);
 339       }
 340
 341       return removed;
 342     } catch (ClassCastException e)
 343     {
 344       return false;
 345     }
 346   }
 347
 348   /**
 349    * Removes the given entry from the list of non-nested entries, returning true
 350    * if found and removed, or false if not found. Specifically, removes the
 351    * first item in the list for which <code>item.equals(entry)</code>.
 352    *
 353    * @param entry
 354    * @return
 355    */
 356   protected boolean removeNonNested(T entry)
 357   {
 358     /*
 359      * find the first interval that might match, i.e. whose
 360      * start position is not less than the target range start
 361      * (NB inequality test ensures the first match if any is found)
 362      */
 363     int from = entry.getBegin();
 364     int startIndex = BinarySearcher.findFirst(nonNested, from,
 365             BinarySearcher.fbegin);
 366
 367     /*
 368      * traverse intervals to look for a match
 369      */
 370
 371     int i = startIndex;
 372     int size = nonNested.size();
 373     while (i < size)
 374     {
 375       T sf = nonNested.get(i);
 376       if (sf.getBegin() > from)
 377       {
 378         break;
 379       }
 380       if (sf.equals(entry))
 381       {
 382         nonNested.remove(i);
 383         return true;
 384       }
 385       i++;
 386     }
 387     return false;
 388   }
 389
 390   @Override
 391   public int getDepth()
 392   {
 393     if (size() == 0)
 394     {
 395       return 0;
 396     }
 397     return (nonNested.isEmpty() ? 0 : 1)
 398             + (nested == null ? 0 : nested.getDepth());
 399   }
 400
 401   /**
 402    * Adds one interval to the NCList that can manage nested intervals (creating
 403    * the NCList if necessary)
 404    */
 405   protected synchronized void addNestedInterval(T interval)
 406   {
 407     if (nested == null)
 408     {
 409       nested = new NCList<>();
 410     }
 411     nested.add(interval);
 412   }
 413
 414   /**
 415    * Answers true if the list contains the interval, else false. This method is
 416    * optimised for the condition that the list is sorted on interval start
 417    * position ascending, and will give unreliable results if this does not hold.
 418    *
 419    * @param intervals
 420    * @param entry
 421    * @return
 422    */
 423   protected boolean listContains(List<T> intervals, Object entry)
 424   {
 425     if (intervals == null || entry == null || !(entry instanceof IntervalI))
 426     {
 427       return false;
 428     }
 429
 430     IntervalI interval = (IntervalI) entry;
 431
 432     /*
 433      * locate the first entry in the list which does not precede the interval
 434      */
 435     int from = interval.getBegin();
 436     int pos = BinarySearcher.findFirst(intervals, from,
 437             BinarySearcher.fbegin);
 438     int len = intervals.size();
 439     while (pos < len)
 440     {
 441       T sf = intervals.get(pos);
 442       if (sf.getBegin() > from)
 443       {
 444         return false; // no match found
 445       }
 446       if (sf.equals(interval))
 447       {
 448         return true;
 449       }
 450       pos++;
 451     }
 452     return false;
 453   }
 454
 455   /**
 456    * Answers an iterator over the intervals in the store, with no particular
 457    * ordering guaranteed. The iterator does not support the optional
 458    * <code>remove</code> operation (throws
 459    * <code>UnsupportedOperationException</code> if attempted).
 460    */
 461   @Override
 462   public Iterator<T> iterator()
 463   {
 464     return new IntervalIterator<>(this);
 465   }
 466
 467   @Override
 468   public void clear()
 469   {
 470     this.nonNested.clear();
 471     this.nested = new NCList<>();
 472   }
 473
 474   /**
 475    * Adds non-nested intervals to the result list that lie within the target
 476    * range
 477    *
 478    * @param from
 479    * @param to
 480    * @param result
 481    */
 482   protected void findNonNestedOverlaps(long from, long to,
 483           List<T> result)
 484   {
 485     /*
 486      * find the first interval whose end position is
 487      * after the target range start
 488      */
 489     int startIndex = BinarySearcher.findFirst(nonNested, (int) from,
 490             BinarySearcher.fend);
 491     for (int i = startIndex, n = nonNested.size(); i < n; i++)
 492     {
 493       T sf = nonNested.get(i);
 494       if (sf.getBegin() > to)
 495       {
 496         break;
 497       }
 498       if (sf.getEnd() >= from)
 499       {
 500         result.add(sf);
 501       }
 502     }
 503   }
 504
 505   @Override
 506   public String toString()
 507   {
 508     String s = nonNested.toString();
 509     if (nested != null)
 510     {
 511       s = s + '\n'// + System.lineSeparator()
 512               + nested.toString();
 513     }
 514     return s;
 515   }
 516
 517   @Override
 518   public int getWidth()
 519   {
 520     return (nonNested == null ? 0 : nonNested.size())
 521             + (nested == null ? 0 : nested.size());
 522   }
 523
 524   @Override
 525   public List<T> findOverlaps(long start, long end, List<T> result)
 526   {
 527     return findOverlaps(start, end);
 528   }
 529
 530   @Override
 531   public boolean revalidate()
 532   {
 533     // not applicable
 534     return true;
 535   }
 536
 537   @Override
 538   public IntervalI get(int i)
 539   {
 540     // not supported (but could be)
 541     return null;
 542   }
 543
 544   @Override
 545   public boolean canCheckForDuplicates()
 546   {
 547     return false;
 548   }
 549
 550   @Override
 551   public boolean add(T interval, boolean checkForDuplicate)
 552   {
 553     return add(interval);
 554   }
 555 }