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 = findSubranges(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> findSubranges(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
 128    *
 129    * @param entry
 130    */
 131   public synchronized void add(T entry)
 132   {
 133     size++;
 134     long start = entry.getBegin();
 135     long end = entry.getEnd();
 136
 137     /*
 138      * cases:
 139      * - precedes all subranges: add as NCNode on front of list
 140      * - follows all subranges: add as NCNode on end of list
 141      * - enclosed by a subrange - add recursively to subrange
 142      * - encloses one or more subranges - push them inside it
 143      * - none of the above - add as a new node and resort nodes list (?)
 144      */
 145
 146     /*
 147      * find the first subrange whose end does not precede entry's start
 148      */
 149     int candidateIndex = findFirstOverlap(start);
 150     if (candidateIndex == -1)
 151     {
 152       /*
 153        * all subranges precede this one - add it on the end
 154        */
 155       subranges.add(new NCNode<T>(entry));
 156       return;
 157     }
 158
 159     /*
 160      * search for maximal span of subranges i-k that the new entry
 161      * encloses; or a subrange that encloses the new entry
 162      */
 163     boolean enclosing = false;
 164     int firstEnclosed = 0;
 165     int lastEnclosed = 0;
 166     boolean overlapping = false;
 167
 168     for (int j = candidateIndex; j < subranges.size(); j++)
 169     {
 170       NCNode<T> subrange = subranges.get(j);
 171
 172       if (end < subrange.getStart() && !overlapping && !enclosing)
 173       {
 174         /*
 175          * new entry lies between subranges j-1 j
 176          */
 177         subranges.add(j, new NCNode<T>(entry));
 178         return;
 179       }
 180
 181       if (subrange.getStart() <= start && subrange.getEnd() >= end)
 182       {
 183         /*
 184          * push new entry inside this subrange as it encloses it
 185          */
 186         subrange.add(entry);
 187         return;
 188       }
 189
 190       if (start <= subrange.getStart())
 191       {
 192         if (end >= subrange.getEnd())
 193         {
 194           /*
 195            * new entry encloses this subrange (and possibly preceding ones);
 196            * continue to find the maximal list it encloses
 197            */
 198           if (!enclosing)
 199           {
 200             firstEnclosed = j;
 201           }
 202           lastEnclosed = j;
 203           enclosing = true;
 204           continue;
 205         }
 206         else
 207         {
 208           /*
 209            * entry spans from before this subrange to inside it
 210            */
 211           if (enclosing)
 212           {
 213             /*
 214              * entry encloses one or more preceding subranges
 215              */
 216             addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 217             return;
 218           }
 219           else
 220           {
 221             /*
 222              * entry spans two subranges but doesn't enclose any
 223              * so just add it
 224              */
 225             subranges.add(j, new NCNode<T>(entry));
 226             return;
 227           }
 228         }
 229       }
 230       else
 231       {
 232         overlapping = true;
 233       }
 234     }
 235
 236     /*
 237      * drops through to here if new range encloses all others
 238      */
 239     if (enclosing)
 240     {
 241       addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 242     }
 243   }
 244
 245   /**
 246    * Update the tree so that the range of the new entry encloses subranges i to
 247    * j (inclusive). That is, replace subranges i-j (inclusive) with a new
 248    * subrange that contains them.
 249    *
 250    * @param entry
 251    * @param i
 252    * @param j
 253    */
 254   protected synchronized void addEnclosingRange(T entry, final int i,
 255           final int j)
 256   {
 257     NCList<T> newNCList = new NCList<T>();
 258     newNCList.subranges.addAll(subranges.subList(i, j + 1));
 259     NCNode<T> newNode = new NCNode<T>(entry, newNCList);
 260     for (int k = j; k >= i; k--)
 261     {
 262       subranges.remove(k);
 263     }
 264     subranges.add(i, newNode);
 265   }
 266
 267   /**
 268    * Returns a (possibly empty) list of items whose extent overlaps the given
 269    * range
 270    *
 271    * @param from
 272    *          start of overlap range (inclusive)
 273    * @param to
 274    *          end of overlap range (inclusive)
 275    * @return
 276    */
 277   public List<T> findOverlaps(long from, long to)
 278   {
 279     List<T> result = new ArrayList<T>();
 280
 281     findOverlaps(from, to, result);
 282
 283     return result;
 284   }
 285
 286   /**
 287    * Recursively searches the NCList adding any items that overlap the from-to
 288    * range to the result list
 289    *
 290    * @param from
 291    * @param to
 292    * @param result
 293    */
 294   protected void findOverlaps(long from, long to,
 295  List<T> result)
 296   {
 297     /*
 298      * find the first sublist that might overlap, i.e.
 299      * the first whose end position is >= from
 300      */
 301     int candidateIndex = findFirstOverlap(from);
 302
 303     if (candidateIndex == -1)
 304     {
 305       return;
 306     }
 307
 308     for (int i = candidateIndex; i < subranges.size(); i++)
 309     {
 310       NCNode<T> candidate = subranges.get(i);
 311       if (candidate.getStart() > to)
 312       {
 313         /*
 314          * we are past the end of our target range
 315          */
 316         break;
 317       }
 318       candidate.findOverlaps(from, to, result);
 319     }
 320
 321   }
 322
 323   /**
 324    * Search subranges for the first one whose end position is not before the
 325    * target range's start position, i.e. the first one that may overlap the
 326    * target range. Returns the index in the list of the first such range found,
 327    * or -1 if none found.
 328    *
 329    * @param from
 330    * @return
 331    */
 332   protected int findFirstOverlap(long from)
 333   {
 334     // TODO binary search
 335     // for now quick cheat linear search
 336     int i = 0;
 337     if (subranges != null)
 338     {
 339       for (NCNode<T> subrange : subranges)
 340       {
 341         if (subrange.getEnd() >= from)
 342         {
 343           return i;
 344         }
 345         i++;
 346       }
 347     }
 348     return -1;
 349   }
 350
 351   /**
 352    * Formats the tree as a bracketed list e.g.
 353    *
 354    * <pre>
 355    * [1-100 [10-30 [10-20]], 15-30 [20-20]]
 356    * </pre>
 357    */
 358   @Override
 359   public String toString()
 360   {
 361     return subranges.toString();
 362   }
 363
 364   /**
 365    * Returns a string representation of the data where containment is shown bgy
 366    * indentation on new lines
 367    *
 368    * @return
 369    */
 370   public String prettyPrint()
 371   {
 372     StringBuilder sb = new StringBuilder(512);
 373     int offset = 0;
 374     int indent = 2;
 375     prettyPrint(sb, offset, indent);
 376     return sb.toString();
 377   }
 378
 379   /**
 380    * @param sb
 381    * @param offset
 382    * @param indent
 383    */
 384   void prettyPrint(StringBuilder sb, int offset, int indent)
 385   {
 386     boolean first = true;
 387     for (NCNode<T> subrange : subranges)
 388     {
 389       if (!first)
 390       {
 391         sb.append(System.lineSeparator());
 392       }
 393       first = false;
 394       subrange.prettyPrint(sb, offset, indent);
 395     }
 396   }
 397
 398   /**
 399    * Answers true if the data held satisfy the rules of construction of an
 400    * NCList, else false.
 401    *
 402    * @return
 403    */
 404   public boolean isValid()
 405   {
 406     return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE);
 407   }
 408
 409   /**
 410    * Answers true if the data held satisfy the rules of construction of an
 411    * NCList bounded within the given start-end range, else false.
 412    * <p>
 413    * Each subrange must lie within start-end (inclusive). Subranges must be
 414    * ordered by start position ascending.
 415    * <p>
 416    *
 417    * @param start
 418    * @param end
 419    * @return
 420    */
 421   boolean isValid(final int start, final int end)
 422   {
 423     int lastStart = start;
 424     for (NCNode<T> subrange : subranges)
 425     {
 426       if (subrange.getStart() < lastStart)
 427       {
 428         System.err.println("error in NCList: range " + subrange.toString()
 429                 + " starts before " + lastStart);
 430         return false;
 431       }
 432       if (subrange.getEnd() > end)
 433       {
 434         System.err.println("error in NCList: range " + subrange.toString()
 435                 + " ends after " + end);
 436         return false;
 437       }
 438       lastStart = subrange.getStart();
 439
 440       if (!subrange.isValid())
 441       {
 442         return false;
 443       }
 444     }
 445     return true;
 446   }
 447
 448   /**
 449    * Answers the lowest start position enclosed by the ranges
 450    *
 451    * @return
 452    */
 453   public int getStart()
 454   {
 455     return subranges.isEmpty() ? 0 : subranges.get(0).getStart();
 456   }
 457
 458   /**
 459    * Returns the number of ranges held (deep count)
 460    *
 461    * @return
 462    */
 463   public int getSize()
 464   {
 465     return size;
 466   }
 467
 468   /**
 469    * Returns a list of all entries stored
 470    *
 471    * @return
 472    */
 473   public List<T> getEntries()
 474   {
 475     List<T> result = new ArrayList<T>();
 476     getEntries(result);
 477     return result;
 478   }
 479
 480   /**
 481    * Adds all contained entries to the given list
 482    *
 483    * @param result
 484    */
 485   void getEntries(List<T> result)
 486   {
 487     for (NCNode<T> subrange : subranges)
 488     {
 489       subrange.getEntries(result);
 490     }
 491   }
 492 }