src/intervalstore/impl/NCList.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.Collections;
  37 import java.util.Iterator;
  38 import java.util.List;
  39 import java.util.NoSuchElementException;
  40
  41 import intervalstore.api.IntervalI;
  42 import intervalstore.impl.Range;
  43
  44 /**
  45  * An adapted implementation of NCList as described in the paper
  46  *
  47  * <pre>
  48  * Nested Containment List (NCList): a new algorithm for accelerating
  49  * interval query of genome alignment and interval databases
  50  * - Alexander V. Alekseyenko, Christopher J. Lee
  51  * https://doi.org/10.1093/bioinformatics/btl647
  52  * </pre>
  53  */
  54 public class NCList<T extends IntervalI> extends AbstractCollection<T>
  55 {
  56   /**
  57    * A depth-first iterator over the elements stored in the NCList
  58    */
  59   private class NCListIterator implements Iterator<T>
  60   {
  61     int subrangeIndex;
  62
  63     Iterator<T> nodeIterator;
  64
  65     /**
  66      * Constructor bootstraps a pointer to an iterator over the first subrange
  67      * (if any)
  68      */
  69     NCListIterator()
  70     {
  71       subrangeIndex = nextSubrange(-1);
  72     }
  73
  74     /**
  75      * Moves the subrange iterator to the next subrange, and answers its index
  76      * in the list of subranges. If there are no more, sets the iterator to null
  77      * and answers -1.
  78      *
  79      * @return
  80      */
  81     private int nextSubrange(int after)
  82     {
  83       int nextIndex = after + 1;
  84       if (nextIndex < subranges.size())
  85       {
  86         nodeIterator = subranges.get(nextIndex).iterator();
  87         return nextIndex;
  88       }
  89       nodeIterator = null;
  90       return -1;
  91     }
  92
  93     @Override
  94     public boolean hasNext()
  95     {
  96       return nodeIterator != null && nodeIterator.hasNext();
  97     }
  98
  99     /**
 100      * Answers the next element returned by the current NCNode's iterator, and
 101      * advances the iterator (to the next NCNode if necessary)
 102      */
 103     @Override
 104     public T next()
 105     {
 106       if (nodeIterator == null || !nodeIterator.hasNext())
 107       {
 108         throw new NoSuchElementException();
 109       }
 110       T result = nodeIterator.next();
 111
 112       if (!nodeIterator.hasNext())
 113       {
 114         subrangeIndex = nextSubrange(subrangeIndex);
 115       }
 116       return result;
 117     }
 118
 119   }
 120
 121   /*
 122    * the number of interval instances represented
 123    */
 124   private int size;
 125
 126   /*
 127    * a list, in start position order, of sublists of ranges ordered so
 128    * that each contains (or is the same as) the one that follows it
 129    */
 130   private List<NCNode<T>> subranges;
 131
 132   /**
 133    * Constructor given a list of things that are each located on a contiguous
 134    * interval. Note that the constructor may reorder the list.
 135    * <p>
 136    * We assume here that for each range, start &lt;= end. Behaviour for reverse
 137    * ordered ranges is undefined.
 138    *
 139    * @param ranges
 140    */
 141   public NCList(List<T> ranges)
 142   {
 143     this();
 144     build(ranges);
 145   }
 146
 147   /**
 148    * Sorts and groups ranges into sublists where each sublist represents an
 149    * interval and its contained subintervals
 150    *
 151    * @param ranges
 152    */
 153   protected void build(List<T> ranges)
 154   {
 155     /*
 156      * sort and partition into subranges
 157      * which have no mutual containment
 158      */
 159     List<IntervalI> sublists = partitionNestedSublists(ranges);
 160
 161     /*
 162      * convert each subrange to an NCNode consisting of a range and
 163      * (possibly) its contained NCList
 164      */
 165     for (IntervalI sublist : sublists)
 166     {
 167       subranges.add(new NCNode<>(
 168               ranges.subList(sublist.getBegin(), sublist.getEnd() + 1)));
 169     }
 170
 171     size = ranges.size();
 172   }
 173
 174   /**
 175    * Default constructor
 176    */
 177   public NCList()
 178   {
 179     subranges = new ArrayList<>();
 180   }
 181
 182   /**
 183    * Sorts and traverses the ranges to identify sublists, whose start intervals
 184    * are overlapping or disjoint but not mutually contained. Answers a list of
 185    * start-end indices of the sorted list of ranges.
 186    *
 187    * @param ranges
 188    * @return
 189    */
 190   protected List<IntervalI> partitionNestedSublists(List<T> ranges)
 191   {
 192     List<IntervalI> sublists = new ArrayList<>();
 193
 194     if (ranges.isEmpty())
 195     {
 196       return sublists;
 197     }
 198
 199     /*
 200      * sort by start ascending, length descending, so that
 201      * contained intervals follow their containing interval
 202      */
 203     Collections.sort(ranges, new NCListBuilder<>().getComparator());
 204
 205     int listStartIndex = 0;
 206
 207     IntervalI lastParent = ranges.get(0);
 208     boolean first = true;
 209
 210     for (int i = 0; i < ranges.size(); i++)
 211     {
 212       IntervalI nextInterval = ranges.get(i);
 213       if (!first && !lastParent.properlyContainsInterval(nextInterval))
 214       {
 215         /*
 216          * this interval is not properly contained in the parent;
 217          * close off the last sublist
 218          */
 219         sublists.add(new Range(listStartIndex, i - 1));
 220         listStartIndex = i;
 221         lastParent = nextInterval;
 222       }
 223       first = false;
 224     }
 225
 226     sublists.add(new Range(listStartIndex, ranges.size() - 1));
 227     return sublists;
 228   }
 229
 230   /**
 231    * Adds one entry to the stored set
 232    *
 233    * @param entry
 234    */
 235   @Override
 236   public synchronized boolean add(final T entry)
 237   {
 238     final NCNode<T> newNode = new NCNode<>(entry);
 239     addNode(newNode);
 240     return true;
 241   }
 242
 243   /**
 244    * Adds one NCNode to this NCList
 245    * <p>
 246    * This method does not update the <code>size</code> (interval count) of this
 247    * NCList, as it may be used to rearrange nodes without changing their count.
 248    * Callers should increment the count if needed.
 249    *
 250    * @param newNode
 251    */
 252   protected void addNode(final NCNode<T> newNode)
 253   {
 254     final long start = newNode.getBegin();
 255     final long end = newNode.getEnd();
 256     size += newNode.size();
 257
 258     /*
 259      * cases:
 260      * 1) precedes all subranges - add as NCNode on front of list
 261      * 2) follows all subranges - add as NCNode on end of list
 262      * 3) matches a subrange - add as a sibling in the list
 263      * 4) properly enclosed by a subrange - add recursively to subrange
 264      * 5) properly encloses one or more subranges - push them inside it
 265      * 6) spans two subranges - insert between them
 266      */
 267
 268     /*
 269      * find the first subrange whose end does not precede entry's start
 270      */
 271     int candidateIndex = findFirstOverlap(start);
 272
 273     /*
 274      * search for maximal span of subranges i-k that the new entry
 275      * encloses; or a subrange that encloses the new entry
 276      */
 277     boolean enclosing = false;
 278     int firstEnclosed = 0;
 279     int lastEnclosed = 0;
 280
 281     for (int j = candidateIndex; j < subranges.size(); j++)
 282     {
 283       NCNode<T> subrange = subranges.get(j);
 284
 285       if (subrange.equalsInterval(newNode))
 286       {
 287         /*
 288          * matching interval - insert adjacent
 289          */
 290         subranges.add(j, newNode);
 291         return;
 292       }
 293
 294       if (end < subrange.getBegin() && !enclosing)
 295       {
 296         /*
 297          * new entry lies between subranges j-1 j
 298          */
 299         subranges.add(j, newNode);
 300         return;
 301       }
 302
 303       if (subrange.properlyContainsInterval(newNode))
 304       {
 305         /*
 306          * push new entry inside this subrange as it encloses it
 307          */
 308         subrange.addNode(newNode);
 309         return;
 310       }
 311
 312       if (start <= subrange.getBegin())
 313       {
 314         if (end >= subrange.getEnd())
 315         {
 316           /*
 317            * new entry encloses this subrange (and possibly preceding ones);
 318            * continue to find the maximal list it encloses
 319            */
 320           if (!enclosing)
 321           {
 322             firstEnclosed = j;
 323           }
 324           lastEnclosed = j;
 325           enclosing = true;
 326           continue;
 327         }
 328         else
 329         {
 330           /*
 331            * entry spans from before this subrange to inside it
 332            */
 333           if (enclosing)
 334           {
 335             /*
 336              * entry encloses one or more preceding subranges
 337              */
 338             push(newNode, firstEnclosed, lastEnclosed);
 339           }
 340           else
 341           {
 342             /*
 343              * entry overlaps two subranges but doesn't enclose either
 344              * so just add it
 345              */
 346             subranges.add(j, newNode);
 347           }
 348           return;
 349         }
 350       }
 351     }
 352
 353     /*
 354      * drops through to here if new range encloses all others
 355      * or overlaps the last one
 356      */
 357     if (enclosing)
 358     {
 359       push(newNode, firstEnclosed, lastEnclosed);
 360     }
 361     else
 362     {
 363       subranges.add(newNode);
 364     }
 365   }
 366
 367   @Override
 368   public boolean contains(Object entry)
 369   {
 370     if (!(entry instanceof IntervalI))
 371     {
 372       return false;
 373     }
 374     IntervalI interval = (IntervalI) entry;
 375
 376     /*
 377      * find the first sublist that might overlap, i.e.
 378      * the first whose end position is >= from
 379      */
 380     int candidateIndex = findFirstOverlap(interval.getBegin());
 381
 382     int to = interval.getEnd();
 383
 384     for (int i = candidateIndex; i < subranges.size(); i++)
 385     {
 386       NCNode<T> candidate = subranges.get(i);
 387       if (candidate.getBegin() > to)
 388       {
 389         /*
 390          * we are past the end of our target range
 391          */
 392         break;
 393       }
 394       if (candidate.contains(interval))
 395       {
 396         return true;
 397       }
 398     }
 399     return false;
 400   }
 401
 402   /**
 403    * Update the tree so that the new node encloses current subranges i to j
 404    * (inclusive). That is, replace subranges i-j (inclusive) with a new subrange
 405    * that contains them.
 406    *
 407    * @param node
 408    * @param i
 409    * @param j
 410    * @throws IllegalArgumentException
 411    *           if any of the subranges is not contained by the node's start-end
 412    *           range
 413    */
 414   protected synchronized void push(NCNode<T> node, final int i,
 415           final int j)
 416   {
 417     for (int k = i; k <= j; k++)
 418     {
 419       NCNode<T> n = subranges.get(k);
 420       if (!node.containsInterval(n)) {
 421         throw new IllegalArgumentException("Can't push " + n.toString()
 422                 + " inside " + node.toString());
 423       }
 424       node.addNode(n);
 425     }
 426
 427     for (int k = j; k >= i; k--)
 428     {
 429       subranges.remove(k);
 430     }
 431     subranges.add(i, node);
 432   }
 433
 434   /**
 435    * Answers a list of contained intervals that overlap the given range
 436    *
 437    * @param from
 438    * @param to
 439    * @return
 440    */
 441   public List<T> findOverlaps(long from, long to)
 442   {
 443     List<T> result = new ArrayList<>();
 444
 445     findOverlaps(from, to, result);
 446
 447     return result;
 448   }
 449
 450   /**
 451    * Recursively searches the NCList adding any items that overlap the from-to
 452    * range to the result list
 453    *
 454    * @param from
 455    * @param to
 456    * @param result
 457    */
 458   protected void findOverlaps(long from, long to, List<T> result)
 459   {
 460     /*
 461      * find the first sublist that might overlap, i.e.
 462      * the first whose end position is >= from
 463      */
 464     int candidateIndex = findFirstOverlap(from);
 465
 466     for (int i = candidateIndex; i < subranges.size(); i++)
 467     {
 468       NCNode<T> candidate = subranges.get(i);
 469       if (candidate.getBegin() > to)
 470       {
 471         /*
 472          * we are past the end of our target range
 473          */
 474         break;
 475       }
 476       candidate.findOverlaps(from, to, result);
 477     }
 478
 479   }
 480
 481   /**
 482    * Search subranges for the first one whose end position is not before the
 483    * target range's start position, i.e. the first one that may overlap the
 484    * target range. Returns the index in the list of the first such range found,
 485    * or the length of the list if none found.
 486    *
 487    * @param from
 488    * @return
 489    */
 490   protected int findFirstOverlap(final long from)
 491   {
 492     return BinarySearcher.findFirst(subranges,
 493             val -> val.getEnd() >= from);
 494   }
 495
 496   /**
 497    * Formats the tree as a bracketed list e.g.
 498    *
 499    * <pre>
 500    * [1-100 [10-30 [10-20]], 15-30 [20-20]]
 501    * </pre>
 502    */
 503   @Override
 504   public String toString()
 505   {
 506     return subranges.toString();
 507   }
 508
 509   /**
 510    * Answers the NCList as an indented list
 511    *
 512    * @return
 513    */
 514   public String prettyPrint()
 515   {
 516     StringBuilder sb = new StringBuilder(512);
 517     int offset = 0;
 518     int indent = 2;
 519     prettyPrint(sb, offset, indent);
 520     sb.append(System.lineSeparator());
 521     return sb.toString();
 522   }
 523
 524   /**
 525    * @param sb
 526    * @param offset
 527    * @param indent
 528    */
 529   void prettyPrint(StringBuilder sb, int offset, int indent)
 530   {
 531     boolean first = true;
 532     for (NCNode<T> subrange : subranges)
 533     {
 534       if (!first)
 535       {
 536         sb.append(System.lineSeparator());
 537       }
 538       first = false;
 539       subrange.prettyPrint(sb, offset, indent);
 540     }
 541   }
 542
 543   /**
 544    * Answers true if the store's structure is valid (nesting containment rules
 545    * are obeyed), else false. For use in testing and debugging.
 546    *
 547    * @return
 548    */
 549   public boolean isValid()
 550   {
 551     int count = 0;
 552     for (NCNode<T> subrange : subranges)
 553     {
 554       count += subrange.size();
 555     }
 556     if (count != size)
 557     {
 558       return false;
 559     }
 560     return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE);
 561   }
 562
 563   /**
 564    * Answers true if the data held satisfy the rules of construction of an
 565    * NCList bounded within the given start-end range, else false.
 566    * <p>
 567    * Each subrange must lie within start-end (inclusive). Subranges must be
 568    * ordered by start position ascending, and within that by end position
 569    * descending.
 570    * <p>
 571    *
 572    * @param start
 573    * @param end
 574    * @return
 575    */
 576   boolean isValid(final int start, final int end)
 577   {
 578     NCNode<T> lastRange = null;
 579
 580     for (NCNode<T> subrange : subranges)
 581     {
 582       if (subrange.getBegin() < start)
 583       {
 584         System.err.println("error in NCList: range " + subrange.toString()
 585                 + " starts before " + end);
 586         return false;
 587       }
 588       if (subrange.getEnd() > end)
 589       {
 590         System.err.println("error in NCList: range " + subrange.toString()
 591                 + " ends after " + end);
 592         return false;
 593       }
 594
 595       if (lastRange != null)
 596       {
 597         if (subrange.getBegin() < lastRange.getBegin())
 598         {
 599           System.err.println("error in NCList: range " + subrange.toString()
 600                   + " starts before " + lastRange.toString());
 601           return false;
 602         }
 603         if (subrange.properlyContainsInterval(lastRange))
 604         {
 605           System.err.println("error in NCList: range " + subrange.toString()
 606                   + " encloses preceding: " + lastRange.toString());
 607           return false;
 608         }
 609         if (lastRange.properlyContainsInterval(subrange))
 610         {
 611           System.err.println("error in NCList: range " + subrange.toString()
 612                   + " enclosed by preceding: " + lastRange.toString());
 613           return false;
 614         }
 615       }
 616       lastRange = subrange;
 617
 618       if (!subrange.isValid())
 619       {
 620         return false;
 621       }
 622     }
 623     return true;
 624   }
 625
 626   /**
 627    * Answers the number of intervals stored
 628    *
 629    * @return
 630    */
 631   @Override
 632   public int size()
 633   {
 634     return size;
 635   }
 636
 637   /**
 638    * Answers a list of all entries stored, in no guaranteed order. This method
 639    * is not synchronized, so is not thread-safe.
 640    */
 641   public List<T> getEntries()
 642   {
 643     List<T> result = new ArrayList<>();
 644     getEntries(result);
 645     return result;
 646   }
 647
 648   /**
 649    * Adds all contained entries to the given list
 650    *
 651    * @param result
 652    */
 653   void getEntries(List<T> result)
 654   {
 655     for (NCNode<T> subrange : subranges)
 656     {
 657       subrange.getEntries(result);
 658     }
 659   }
 660
 661   /**
 662    * Removes the first interval <code>I</code>found that is equal to T
 663    * (<code>I.equals(T)</code>). Answers true if an interval is removed, false
 664    * if no match is found. This method is synchronized so thread-safe.
 665    *
 666    * @param entry
 667    * @return
 668    */
 669   public synchronized boolean remove(T entry)
 670   {
 671     if (entry == null)
 672     {
 673       return false;
 674     }
 675     int i = findFirstOverlap(entry.getBegin());
 676
 677     for (; i < subranges.size(); i++)
 678     {
 679       NCNode<T> subrange = subranges.get(i);
 680       if (subrange.getBegin() > entry.getBegin())
 681       {
 682         /*
 683          * not found
 684          */
 685         return false;
 686       }
 687       NCList<T> subRegions = subrange.getSubRegions();
 688
 689       if (subrange.getRegion().equals(entry))
 690       {
 691         /*
 692          * if the subrange is rooted on this entry, remove it,
 693          * and remove and promote its subregions (if any)
 694          */
 695         subranges.remove(i);
 696         size -= subrange.size();
 697         if (subRegions != null)
 698         {
 699           for (NCNode<T> r : subRegions.subranges)
 700           {
 701             addNode(r);
 702           }
 703         }
 704         return true;
 705       }
 706       else
 707       {
 708         if (subrange.remove(entry))
 709         {
 710           size--;
 711           return true;
 712         }
 713       }
 714     }
 715     return false;
 716   }
 717
 718   /**
 719    * Answers the depth of interval nesting of this object, where 1 means there
 720    * are no nested sub-intervals
 721    *
 722    * @return
 723    */
 724   public int getDepth()
 725   {
 726     int subDepth = 0;
 727     for (NCNode<T> subrange : subranges)
 728     {
 729       subDepth = Math.max(subDepth, subrange.getDepth());
 730     }
 731
 732     return subDepth;
 733   }
 734
 735   /**
 736    * Answers an iterator over the contained intervals, with no particular order
 737    * guaranteed. The iterator does not support the optional <code>remove</code>
 738    * operation (throws <code>UnsupportedOperationException</code> if attempted).
 739    */
 740   @Override
 741   public Iterator<T> iterator()
 742   {
 743     return new NCListIterator();
 744   }
 745
 746   @Override
 747   public synchronized void clear()
 748   {
 749     subranges.clear();
 750     size = 0;
 751   }
 752 }