src/jalview/datamodel/features/NCList.java

   1 package jalview.datamodel.features;
   2
   3 import jalview.datamodel.ContiguousI;
   4 import jalview.datamodel.Range;
   5
   6 import java.util.ArrayList;
   7 import java.util.Collections;
   8 import java.util.List;
   9
  10 /**
  11  * An adapted implementation of NCList as described in the paper
  12  *
  13  * <pre>
  14  * Nested Containment List (NCList): a new algorithm for accelerating
  15  * interval query of genome alignment and interval databases
  16  * - Alexander V. Alekseyenko, Christopher J. Lee
  17  * https://doi.org/10.1093/bioinformatics/btl647
  18  * </pre>
  19  */
  20 public class NCList<T extends ContiguousI>
  21 {
  22   /*
  23    * the number of ranges represented
  24    */
  25   private int size;
  26
  27   /*
  28    * a list, in start position order, of sublists of ranges ordered so
  29    * that each contains (or is the same as) the one that follows it
  30    */
  31   private List<NCNode<T>> subranges;
  32
  33   /**
  34    * Constructor given a list of things that are each located on a contiguous
  35    * interval. Note that the constructor may reorder the list.
  36    * <p>
  37    * We assume here that for each range, start &lt;= end. Behaviour for reverse
  38    * ordered ranges is undefined.
  39    *
  40    * @param ranges
  41    */
  42   public NCList(List<T> ranges)
  43   {
  44     this();
  45     build(ranges);
  46   }
  47
  48   /**
  49    * Sort and group ranges into sublists where each sublist represents a region
  50    * and its contained subregions
  51    *
  52    * @param ranges
  53    */
  54   protected void build(List<T> ranges)
  55   {
  56     /*
  57      * sort by start ascending so that contained intervals
  58      * follow their containing interval
  59      */
  60     Collections.sort(ranges, RangeComparator.BY_START_POSITION);
  61
  62     List<Range> sublists = buildSubranges(ranges);
  63
  64     /*
  65      * convert each subrange to an NCNode consisting of a range and
  66      * (possibly) its contained NCList
  67      */
  68     for (Range sublist : sublists)
  69     {
  70       subranges.add(new NCNode<T>(ranges.subList(sublist.start,
  71               sublist.end + 1)));
  72     }
  73
  74     size = ranges.size();
  75   }
  76
  77   public NCList(T entry)
  78   {
  79     this();
  80     subranges.add(new NCNode<T>(entry));
  81     size = 1;
  82   }
  83
  84   public NCList()
  85   {
  86     subranges = new ArrayList<NCNode<T>>();
  87   }
  88
  89   /**
  90    * Traverses the sorted ranges to identify sublists, within which each
  91    * interval contains the one that follows it
  92    *
  93    * @param ranges
  94    * @return
  95    */
  96   protected List<Range> buildSubranges(List<T> ranges)
  97   {
  98     List<Range> sublists = new ArrayList<Range>();
  99
 100     if (ranges.isEmpty())
 101     {
 102       return sublists;
 103     }
 104
 105     int listStartIndex = 0;
 106     long lastEndPos = Long.MAX_VALUE;
 107
 108     for (int i = 0; i < ranges.size(); i++)
 109     {
 110       ContiguousI nextInterval = ranges.get(i);
 111       long nextStart = nextInterval.getBegin();
 112       long nextEnd = nextInterval.getEnd();
 113       if (nextStart > lastEndPos || nextEnd > lastEndPos)
 114       {
 115         /*
 116          * this interval is not contained in the preceding one
 117          * close off the last sublist
 118          */
 119         sublists.add(new Range(listStartIndex, i - 1));
 120         listStartIndex = i;
 121       }
 122       lastEndPos = nextEnd;
 123     }
 124
 125     sublists.add(new Range(listStartIndex, ranges.size() - 1));
 126     return sublists;
 127   }
 128
 129   /**
 130    * Adds one entry to the stored set (with duplicates allowed)
 131    *
 132    * @param entry
 133    */
 134   public void add(T entry)
 135   {
 136     add(entry, true);
 137   }
 138
 139   /**
 140    * Adds one entry to the stored set, and returns true, unless allowDuplicates
 141    * is set to false and it is already contained (by object equality test), in
 142    * which case it is not added and this method returns false.
 143    *
 144    * @param entry
 145    * @param allowDuplicates
 146    * @return
 147    */
 148   public synchronized boolean add(T entry, boolean allowDuplicates)
 149   {
 150     if (!allowDuplicates && contains(entry))
 151     {
 152       return false;
 153     }
 154
 155     size++;
 156     long start = entry.getBegin();
 157     long end = entry.getEnd();
 158
 159     /*
 160      * cases:
 161      * - precedes all subranges: add as NCNode on front of list
 162      * - follows all subranges: add as NCNode on end of list
 163      * - enclosed by a subrange - add recursively to subrange
 164      * - encloses one or more subranges - push them inside it
 165      * - none of the above - add as a new node and resort nodes list (?)
 166      */
 167
 168     /*
 169      * find the first subrange whose end does not precede entry's start
 170      */
 171     int candidateIndex = findFirstOverlap(start);
 172     if (candidateIndex == -1)
 173     {
 174       /*
 175        * all subranges precede this one - add it on the end
 176        */
 177       subranges.add(new NCNode<T>(entry));
 178       return true;
 179     }
 180
 181     /*
 182      * search for maximal span of subranges i-k that the new entry
 183      * encloses; or a subrange that encloses the new entry
 184      */
 185     boolean enclosing = false;
 186     int firstEnclosed = 0;
 187     int lastEnclosed = 0;
 188     boolean overlapping = false;
 189
 190     for (int j = candidateIndex; j < subranges.size(); j++)
 191     {
 192       NCNode<T> subrange = subranges.get(j);
 193
 194       if (end < subrange.getBegin() && !overlapping && !enclosing)
 195       {
 196         /*
 197          * new entry lies between subranges j-1 j
 198          */
 199         subranges.add(j, new NCNode<T>(entry));
 200         return true;
 201       }
 202
 203       if (subrange.getBegin() <= start && subrange.getEnd() >= end)
 204       {
 205         /*
 206          * push new entry inside this subrange as it encloses it
 207          */
 208         subrange.add(entry);
 209         return true;
 210       }
 211
 212       if (start <= subrange.getBegin())
 213       {
 214         if (end >= subrange.getEnd())
 215         {
 216           /*
 217            * new entry encloses this subrange (and possibly preceding ones);
 218            * continue to find the maximal list it encloses
 219            */
 220           if (!enclosing)
 221           {
 222             firstEnclosed = j;
 223           }
 224           lastEnclosed = j;
 225           enclosing = true;
 226           continue;
 227         }
 228         else
 229         {
 230           /*
 231            * entry spans from before this subrange to inside it
 232            */
 233           if (enclosing)
 234           {
 235             /*
 236              * entry encloses one or more preceding subranges
 237              */
 238             addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 239             return true;
 240           }
 241           else
 242           {
 243             /*
 244              * entry spans two subranges but doesn't enclose any
 245              * so just add it
 246              */
 247             subranges.add(j, new NCNode<T>(entry));
 248             return true;
 249           }
 250         }
 251       }
 252       else
 253       {
 254         overlapping = true;
 255       }
 256     }
 257
 258     /*
 259      * drops through to here if new range encloses all others
 260      * or overlaps the last one
 261      */
 262     if (enclosing)
 263     {
 264       addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 265     }
 266     else
 267     {
 268       subranges.add(new NCNode<T>(entry));
 269     }
 270
 271     return true;
 272   }
 273
 274   /**
 275    * Answers true if this NCList contains the given entry (by object equality
 276    * test), else false
 277    *
 278    * @param entry
 279    * @return
 280    */
 281   public boolean contains(T entry)
 282   {
 283     /*
 284      * find the first sublist that might overlap, i.e.
 285      * the first whose end position is >= from
 286      */
 287     int candidateIndex = findFirstOverlap(entry.getBegin());
 288
 289     if (candidateIndex == -1)
 290     {
 291       return false;
 292     }
 293
 294     int to = entry.getEnd();
 295
 296     for (int i = candidateIndex; i < subranges.size(); i++)
 297     {
 298       NCNode<T> candidate = subranges.get(i);
 299       if (candidate.getBegin() > to)
 300       {
 301         /*
 302          * we are past the end of our target range
 303          */
 304         break;
 305       }
 306       if (candidate.contains(entry))
 307       {
 308         return true;
 309       }
 310     }
 311     return false;
 312   }
 313
 314   /**
 315    * Update the tree so that the range of the new entry encloses subranges i to
 316    * j (inclusive). That is, replace subranges i-j (inclusive) with a new
 317    * subrange that contains them.
 318    *
 319    * @param entry
 320    * @param i
 321    * @param j
 322    */
 323   protected synchronized void addEnclosingRange(T entry, final int i,
 324           final int j)
 325   {
 326     NCList<T> newNCList = new NCList<T>();
 327     newNCList.addNodes(subranges.subList(i, j + 1));
 328     NCNode<T> newNode = new NCNode<T>(entry, newNCList);
 329     for (int k = j; k >= i; k--)
 330     {
 331       subranges.remove(k);
 332     }
 333     subranges.add(i, newNode);
 334   }
 335
 336   protected void addNodes(List<NCNode<T>> nodes)
 337   {
 338     for (NCNode<T> node : nodes)
 339     {
 340       subranges.add(node);
 341       size += node.size();
 342     }
 343   }
 344
 345   /**
 346    * Returns a (possibly empty) list of items whose extent overlaps the given
 347    * range
 348    *
 349    * @param from
 350    *          start of overlap range (inclusive)
 351    * @param to
 352    *          end of overlap range (inclusive)
 353    * @return
 354    */
 355   public List<T> findOverlaps(long from, long to)
 356   {
 357     List<T> result = new ArrayList<T>();
 358
 359     findOverlaps(from, to, result);
 360
 361     return result;
 362   }
 363
 364   /**
 365    * Recursively searches the NCList adding any items that overlap the from-to
 366    * range to the result list
 367    *
 368    * @param from
 369    * @param to
 370    * @param result
 371    */
 372   protected void findOverlaps(long from, long to, List<T> result)
 373   {
 374     /*
 375      * find the first sublist that might overlap, i.e.
 376      * the first whose end position is >= from
 377      */
 378     int candidateIndex = findFirstOverlap(from);
 379
 380     if (candidateIndex == -1)
 381     {
 382       return;
 383     }
 384
 385     for (int i = candidateIndex; i < subranges.size(); i++)
 386     {
 387       NCNode<T> candidate = subranges.get(i);
 388       if (candidate.getBegin() > to)
 389       {
 390         /*
 391          * we are past the end of our target range
 392          */
 393         break;
 394       }
 395       candidate.findOverlaps(from, to, result);
 396     }
 397
 398   }
 399
 400   /**
 401    * Search subranges for the first one whose end position is not before the
 402    * target range's start position, i.e. the first one that may overlap the
 403    * target range. Returns the index in the list of the first such range found,
 404    * or -1 if none found.
 405    *
 406    * @param from
 407    * @return
 408    */
 409   protected int findFirstOverlap(long from)
 410   {
 411     /*
 412      * The NCList paper describes binary search for this step,
 413      * but this not implemented here as (a) I haven't understood it yet
 414      * and (b) it seems to imply complications for adding to an NCList
 415      */
 416
 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, RangeComparator.BY_START_POSITION);
 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 }