src/jalview/datamodel/features/NCList.java

   1 package jalview.datamodel.features;
   2
   3 import java.util.ArrayList;
   4 import java.util.Collections;
   5 import java.util.Comparator;
   6 import java.util.List;
   7
   8 /**
   9  * An adapted implementation of NCList as described in the paper
  10  *
  11  * <pre>
  12  * Nested Containment List (NCList): a new algorithm for accelerating
  13  * interval query of genome alignment and interval databases
  14  * - Alexander V. Alekseyenko, Christopher J. Lee
  15  * https://doi.org/10.1093/bioinformatics/btl647
  16  * </pre>
  17  */
  18 public class NCList<T extends ContiguousI>
  19 {
  20   /*
  21    * the number of ranges represented
  22    */
  23   private int size;
  24
  25   /*
  26    * a list, in start position order, of sublists of ranges ordered so
  27    * that each contains (or is the same as) the one that follows it
  28    */
  29   private List<NCNode<T>> subranges;
  30
  31   /*
  32    * a comparator to sort intervals by start position ascending, with
  33    * longer (enclosing) intervals preceding those they enclose
  34    */
  35   Comparator<ContiguousI> intervalSorter = new RangeComparator(true);
  36
  37   /**
  38    * Constructor given a list of things that are each located on a contiguous
  39    * interval. Note that the constructor may reorder the list.
  40    * <p>
  41    * We assume here that for each range, start &lt;= end. Behaviour for reverse
  42    * ordered ranges is undefined.
  43    *
  44    * @param ranges
  45    */
  46   public NCList(List<T> ranges)
  47   {
  48     this();
  49     build(ranges);
  50   }
  51
  52   /**
  53    * @param ranges
  54    */
  55   protected void build(List<T> ranges)
  56   {
  57     /*
  58      * sort by start ascending so that contained intervals
  59      * follow their containing interval
  60      */
  61     Collections.sort(ranges, intervalSorter);
  62
  63     List<SubList> sublists = buildSubranges(ranges);
  64
  65     /*
  66      * convert each subrange to an NCNode consisting of a range and
  67      * (possibly) its contained NCList
  68      */
  69     for (SubList sublist : sublists)
  70     {
  71       subranges.add(new NCNode<T>(ranges.subList(sublist.startIndex,
  72               sublist.endIndex + 1)));
  73     }
  74
  75     size = ranges.size();
  76   }
  77
  78   public NCList(T entry)
  79   {
  80     this();
  81     List<T> ranges = new ArrayList<T>();
  82     ranges.add(entry);
  83     build(ranges);
  84   }
  85
  86   public NCList()
  87   {
  88     subranges = new ArrayList<NCNode<T>>();
  89   }
  90
  91   /**
  92    * Traverses the sorted ranges to identify sublists, within which each
  93    * interval contains the one that follows it
  94    *
  95    * @param ranges
  96    * @return
  97    */
  98   protected List<SubList> buildSubranges(List<T> ranges)
  99   {
 100     List<SubList> sublists = new ArrayList<SubList>();
 101
 102     int listStartIndex = 0;
 103     long lastEndPos = Long.MAX_VALUE;
 104
 105     for (int i = 0; i < ranges.size(); i++)
 106     {
 107       ContiguousI nextInterval = ranges.get(i);
 108       long nextStart = nextInterval.getBegin();
 109       long nextEnd = nextInterval.getEnd();
 110       if (nextStart > lastEndPos || nextEnd > lastEndPos)
 111       {
 112         /*
 113          * this interval is not contained in the preceding one
 114          * close off the last sublist
 115          */
 116         sublists.add(new SubList(listStartIndex, i - 1));
 117         listStartIndex = i;
 118       }
 119       lastEndPos = nextEnd;
 120     }
 121
 122     sublists.add(new SubList(listStartIndex, ranges.size() - 1));
 123     return sublists;
 124   }
 125
 126   /**
 127    * Adds one entry to the stored set (with duplicates allowed)
 128    *
 129    * @param entry
 130    */
 131   public void add(T entry)
 132   {
 133     add(entry, true);
 134   }
 135
 136   /**
 137    * Adds one entry to the stored set, and returns true, unless allowDuplicates
 138    * is set to false and it is already contained (by object equality test), in
 139    * which case it is not added and this method returns false.
 140    *
 141    * @param entry
 142    * @param allowDuplicates
 143    * @return
 144    */
 145   public synchronized boolean add(T entry, boolean allowDuplicates)
 146   {
 147     if (!allowDuplicates && contains(entry))
 148     {
 149       return false;
 150     }
 151
 152     size++;
 153     long start = entry.getBegin();
 154     long end = entry.getEnd();
 155
 156     /*
 157      * cases:
 158      * - precedes all subranges: add as NCNode on front of list
 159      * - follows all subranges: add as NCNode on end of list
 160      * - enclosed by a subrange - add recursively to subrange
 161      * - encloses one or more subranges - push them inside it
 162      * - none of the above - add as a new node and resort nodes list (?)
 163      */
 164
 165     /*
 166      * find the first subrange whose end does not precede entry's start
 167      */
 168     int candidateIndex = findFirstOverlap(start);
 169     if (candidateIndex == -1)
 170     {
 171       /*
 172        * all subranges precede this one - add it on the end
 173        */
 174       subranges.add(new NCNode<T>(entry));
 175       return true;
 176     }
 177
 178     /*
 179      * search for maximal span of subranges i-k that the new entry
 180      * encloses; or a subrange that encloses the new entry
 181      */
 182     boolean enclosing = false;
 183     int firstEnclosed = 0;
 184     int lastEnclosed = 0;
 185     boolean overlapping = false;
 186
 187     for (int j = candidateIndex; j < subranges.size(); j++)
 188     {
 189       NCNode<T> subrange = subranges.get(j);
 190
 191       if (end < subrange.getStart() && !overlapping && !enclosing)
 192       {
 193         /*
 194          * new entry lies between subranges j-1 j
 195          */
 196         subranges.add(j, new NCNode<T>(entry));
 197         return true;
 198       }
 199
 200       if (subrange.getStart() <= start && subrange.getEnd() >= end)
 201       {
 202         /*
 203          * push new entry inside this subrange as it encloses it
 204          */
 205         subrange.add(entry);
 206         return true;
 207       }
 208
 209       if (start <= subrange.getStart())
 210       {
 211         if (end >= subrange.getEnd())
 212         {
 213           /*
 214            * new entry encloses this subrange (and possibly preceding ones);
 215            * continue to find the maximal list it encloses
 216            */
 217           if (!enclosing)
 218           {
 219             firstEnclosed = j;
 220           }
 221           lastEnclosed = j;
 222           enclosing = true;
 223           continue;
 224         }
 225         else
 226         {
 227           /*
 228            * entry spans from before this subrange to inside it
 229            */
 230           if (enclosing)
 231           {
 232             /*
 233              * entry encloses one or more preceding subranges
 234              */
 235             addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 236             return true;
 237           }
 238           else
 239           {
 240             /*
 241              * entry spans two subranges but doesn't enclose any
 242              * so just add it
 243              */
 244             subranges.add(j, new NCNode<T>(entry));
 245             return true;
 246           }
 247         }
 248       }
 249       else
 250       {
 251         overlapping = true;
 252       }
 253     }
 254
 255     /*
 256      * drops through to here if new range encloses all others
 257      * or overlaps the last one
 258      */
 259     if (enclosing)
 260     {
 261       addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 262     }
 263     else
 264     {
 265       subranges.add(new NCNode<T>(entry));
 266     }
 267
 268     return true;
 269   }
 270
 271   /**
 272    * Answers true if this NCList contains the given entry (by object equality
 273    * test), else false
 274    *
 275    * @param entry
 276    * @return
 277    */
 278   public boolean contains(T entry)
 279   {
 280     /*
 281      * find the first sublist that might overlap, i.e.
 282      * the first whose end position is >= from
 283      */
 284     int candidateIndex = findFirstOverlap(entry.getBegin());
 285
 286     if (candidateIndex == -1)
 287     {
 288       return false;
 289     }
 290
 291     int to = entry.getEnd();
 292
 293     for (int i = candidateIndex; i < subranges.size(); i++)
 294     {
 295       NCNode<T> candidate = subranges.get(i);
 296       if (candidate.getStart() > to)
 297       {
 298         /*
 299          * we are past the end of our target range
 300          */
 301         break;
 302       }
 303       if (candidate.contains(entry))
 304       {
 305         return true;
 306       }
 307     }
 308     return false;
 309   }
 310
 311   /**
 312    * Update the tree so that the range of the new entry encloses subranges i to
 313    * j (inclusive). That is, replace subranges i-j (inclusive) with a new
 314    * subrange that contains them.
 315    *
 316    * @param entry
 317    * @param i
 318    * @param j
 319    */
 320   protected synchronized void addEnclosingRange(T entry, final int i,
 321           final int j)
 322   {
 323     NCList<T> newNCList = new NCList<T>();
 324     newNCList.subranges.addAll(subranges.subList(i, j + 1));
 325     NCNode<T> newNode = new NCNode<T>(entry, newNCList);
 326     for (int k = j; k >= i; k--)
 327     {
 328       subranges.remove(k);
 329     }
 330     subranges.add(i, newNode);
 331   }
 332
 333   /**
 334    * Returns a (possibly empty) list of items whose extent overlaps the given
 335    * range
 336    *
 337    * @param from
 338    *          start of overlap range (inclusive)
 339    * @param to
 340    *          end of overlap range (inclusive)
 341    * @return
 342    */
 343   public List<T> findOverlaps(long from, long to)
 344   {
 345     List<T> result = new ArrayList<T>();
 346
 347     findOverlaps(from, to, result);
 348
 349     return result;
 350   }
 351
 352   /**
 353    * Recursively searches the NCList adding any items that overlap the from-to
 354    * range to the result list
 355    *
 356    * @param from
 357    * @param to
 358    * @param result
 359    */
 360   protected void findOverlaps(long from, long to, List<T> result)
 361   {
 362     /*
 363      * find the first sublist that might overlap, i.e.
 364      * the first whose end position is >= from
 365      */
 366     int candidateIndex = findFirstOverlap(from);
 367
 368     if (candidateIndex == -1)
 369     {
 370       return;
 371     }
 372
 373     for (int i = candidateIndex; i < subranges.size(); i++)
 374     {
 375       NCNode<T> candidate = subranges.get(i);
 376       if (candidate.getStart() > to)
 377       {
 378         /*
 379          * we are past the end of our target range
 380          */
 381         break;
 382       }
 383       candidate.findOverlaps(from, to, result);
 384     }
 385
 386   }
 387
 388   /**
 389    * Search subranges for the first one whose end position is not before the
 390    * target range's start position, i.e. the first one that may overlap the
 391    * target range. Returns the index in the list of the first such range found,
 392    * or -1 if none found.
 393    *
 394    * @param from
 395    * @return
 396    */
 397   protected int findFirstOverlap(long from)
 398   {
 399     // TODO binary search
 400     // for now quick cheat linear search
 401     int i = 0;
 402     if (subranges != null)
 403     {
 404       for (NCNode<T> subrange : subranges)
 405       {
 406         if (subrange.getEnd() >= from)
 407         {
 408           return i;
 409         }
 410         i++;
 411       }
 412     }
 413     return -1;
 414   }
 415
 416   /**
 417    * Formats the tree as a bracketed list e.g.
 418    *
 419    * <pre>
 420    * [1-100 [10-30 [10-20]], 15-30 [20-20]]
 421    * </pre>
 422    */
 423   @Override
 424   public String toString()
 425   {
 426     return subranges.toString();
 427   }
 428
 429   /**
 430    * Returns a string representation of the data where containment is shown bgy
 431    * indentation on new lines
 432    *
 433    * @return
 434    */
 435   public String prettyPrint()
 436   {
 437     StringBuilder sb = new StringBuilder(512);
 438     int offset = 0;
 439     int indent = 2;
 440     prettyPrint(sb, offset, indent);
 441     return sb.toString();
 442   }
 443
 444   /**
 445    * @param sb
 446    * @param offset
 447    * @param indent
 448    */
 449   void prettyPrint(StringBuilder sb, int offset, int indent)
 450   {
 451     boolean first = true;
 452     for (NCNode<T> subrange : subranges)
 453     {
 454       if (!first)
 455       {
 456         sb.append(System.lineSeparator());
 457       }
 458       first = false;
 459       subrange.prettyPrint(sb, offset, indent);
 460     }
 461   }
 462
 463   /**
 464    * Answers true if the data held satisfy the rules of construction of an
 465    * NCList, else false.
 466    *
 467    * @return
 468    */
 469   public boolean isValid()
 470   {
 471     return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE);
 472   }
 473
 474   /**
 475    * Answers true if the data held satisfy the rules of construction of an
 476    * NCList bounded within the given start-end range, else false.
 477    * <p>
 478    * Each subrange must lie within start-end (inclusive). Subranges must be
 479    * ordered by start position ascending.
 480    * <p>
 481    *
 482    * @param start
 483    * @param end
 484    * @return
 485    */
 486   boolean isValid(final int start, final int end)
 487   {
 488     int lastStart = start;
 489     for (NCNode<T> subrange : subranges)
 490     {
 491       if (subrange.getStart() < lastStart)
 492       {
 493         System.err.println("error in NCList: range " + subrange.toString()
 494                 + " starts before " + lastStart);
 495         return false;
 496       }
 497       if (subrange.getEnd() > end)
 498       {
 499         System.err.println("error in NCList: range " + subrange.toString()
 500                 + " ends after " + end);
 501         return false;
 502       }
 503       lastStart = subrange.getStart();
 504
 505       if (!subrange.isValid())
 506       {
 507         return false;
 508       }
 509     }
 510     return true;
 511   }
 512
 513   /**
 514    * Answers the lowest start position enclosed by the ranges
 515    *
 516    * @return
 517    */
 518   public int getStart()
 519   {
 520     return subranges.isEmpty() ? 0 : subranges.get(0).getStart();
 521   }
 522
 523   /**
 524    * Returns the number of ranges held (deep count)
 525    *
 526    * @return
 527    */
 528   public int getSize()
 529   {
 530     return size;
 531   }
 532
 533   /**
 534    * Returns a list of all entries stored
 535    *
 536    * @return
 537    */
 538   public List<T> getEntries()
 539   {
 540     List<T> result = new ArrayList<T>();
 541     getEntries(result);
 542     return result;
 543   }
 544
 545   /**
 546    * Adds all contained entries to the given list
 547    *
 548    * @param result
 549    */
 550   void getEntries(List<T> result)
 551   {
 552     for (NCNode<T> subrange : subranges)
 553     {
 554       subrange.getEntries(result);
 555     }
 556   }
 557
 558   /**
 559    * Deletes the given entry from the store, returning true if it was found (and
 560    * deleted), else false. This method makes no assumption that the entry is in
 561    * the 'expected' place in the store, in case it has been modified since it
 562    * was added. Only the first 'same object' match is deleted, not 'equal' or
 563    * multiple objects.
 564    *
 565    * @param entry
 566    */
 567   public synchronized boolean delete(T entry)
 568   {
 569     if (entry == null)
 570     {
 571       return false;
 572     }
 573     for (int i = 0; i < subranges.size(); i++)
 574     {
 575       NCNode<T> subrange = subranges.get(i);
 576       NCList<T> subRegions = subrange.getSubRegions();
 577
 578       if (subrange.getRegion() == entry)
 579       {
 580         /*
 581          * if the subrange is rooted on this entry, promote its
 582          * subregions (if any) to replace the subrange here
 583          */
 584         subranges.remove(i);
 585         if (subRegions != null)
 586         {
 587           subranges.addAll(i, subRegions.subranges);
 588         }
 589         size--;
 590         return true;
 591       }
 592       else
 593       {
 594         if (subRegions != null && subRegions.delete(entry))
 595         {
 596           size--;
 597           return true;
 598         }
 599       }
 600     }
 601     return false;
 602   }
 603
 604   /**
 605    * Answers true if this contains no ranges
 606    *
 607    * @return
 608    */
 609   public boolean isEmpty()
 610   {
 611     return getSize() == 0;
 612   }
 613
 614   /**
 615    * Answer the list of subranges held in this NCList
 616    *
 617    * @return
 618    */
 619   List<NCNode<T>> getSubregions()
 620   {
 621     return subranges;
 622   }
 623 }