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