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