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