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