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  * todo
  13  * </pre>
  14  */
  15 public class NCList<T extends ContiguousI>
  16 {
  17   /*
  18    * the number of ranges represented
  19    */
  20   private int size;
  21
  22   /*
  23    * a list, in start position order, of sublists of ranges ordered so
  24    * that each contains (or is the same as) the one that follows it
  25    */
  26   private List<NCNode<T>> subranges;
  27
  28   /*
  29    * a comparator to sort intervals by start position ascending, with
  30    * longer (enclosing) intervals preceding those they enclose
  31    */
  32   Comparator<ContiguousI> intervalSorter = new RangeComparator(true);
  33
  34   /**
  35    * Constructor given a list of things that are each located on a contiguous
  36    * interval. Note that the constructor may reorder the list.
  37    * <p>
  38    * We assume here that for each range, start &lt;= end. Behaviour for reverse
  39    * ordered ranges is undefined.
  40    *
  41    * @param ranges
  42    */
  43   public NCList(List<T> ranges)
  44   {
  45     this();
  46     build(ranges);
  47   }
  48
  49   /**
  50    * @param ranges
  51    */
  52   protected void build(List<T> ranges)
  53   {
  54     /*
  55      * sort by start ascending so that contained intervals
  56      * follow their containing interval
  57      */
  58     Collections.sort(ranges, intervalSorter);
  59
  60     List<SubList> sublists = findSubranges(ranges);
  61
  62     /*
  63      * convert each subrange to an NCNode consisting of a range and
  64      * (possibly) its contained NCList
  65      */
  66     for (SubList sublist : sublists)
  67     {
  68       subranges.add(new NCNode<T>(ranges.subList(sublist.startIndex,
  69               sublist.endIndex + 1)));
  70     }
  71
  72     size = ranges.size();
  73   }
  74
  75   public NCList(T entry)
  76   {
  77     this();
  78     List<T> ranges = new ArrayList<T>();
  79     ranges.add(entry);
  80     build(ranges);
  81   }
  82
  83   public NCList()
  84   {
  85     subranges = new ArrayList<NCNode<T>>();
  86   }
  87
  88   /**
  89    * Traverses the sorted ranges to identify sublists, within which each
  90    * interval contains the one that follows it
  91    *
  92    * @param ranges
  93    * @return
  94    */
  95   protected List<SubList> findSubranges(List<T> ranges)
  96   {
  97     List<SubList> sublists = new ArrayList<SubList>();
  98
  99     int listStartIndex = 0;
 100     long lastEndPos = Long.MAX_VALUE;
 101
 102     for (int i = 0; i < ranges.size(); i++)
 103     {
 104       ContiguousI nextInterval = ranges.get(i);
 105       long nextStart = nextInterval.getBegin();
 106       long nextEnd = nextInterval.getEnd();
 107       if (nextStart > lastEndPos || nextEnd > lastEndPos)
 108       {
 109         /*
 110          * this interval is not contained in the preceding one
 111          * close off the last sublist
 112          */
 113         sublists.add(new SubList(listStartIndex, i - 1));
 114         listStartIndex = i;
 115       }
 116       lastEndPos = nextEnd;
 117     }
 118
 119     sublists.add(new SubList(listStartIndex, ranges.size() - 1));
 120     return sublists;
 121   }
 122
 123   /**
 124    * Adds one entry to the stored set
 125    *
 126    * @param entry
 127    */
 128   public synchronized void add(T entry)
 129   {
 130     size++;
 131     long start = entry.getBegin();
 132     long end = entry.getEnd();
 133
 134     /*
 135      * cases:
 136      * - precedes all subranges: add as NCNode on front of list
 137      * - follows all subranges: add as NCNode on end of list
 138      * - enclosed by a subrange - add recursively to subrange
 139      * - encloses one or more subranges - push them inside it
 140      * - none of the above - add as a new node and resort nodes list (?)
 141      */
 142
 143     /*
 144      * find the first subrange whose end does not precede entry's start
 145      */
 146     int candidateIndex = findFirstOverlap(start);
 147     if (candidateIndex == -1)
 148     {
 149       /*
 150        * all subranges precede this one - add it on the end
 151        */
 152       subranges.add(new NCNode<T>(entry));
 153       return;
 154     }
 155
 156     /*
 157      * search for maximal span of subranges i-k that the new entry
 158      * encloses; or a subrange that encloses the new entry
 159      */
 160     boolean enclosing = false;
 161     int firstEnclosed = 0;
 162     int lastEnclosed = 0;
 163     boolean overlapping = false;
 164
 165     for (int j = candidateIndex; j < subranges.size(); j++)
 166     {
 167       NCNode<T> subrange = subranges.get(j);
 168
 169       if (end < subrange.getStart() && !overlapping && !enclosing)
 170       {
 171         /*
 172          * new entry lies between subranges j-1 j
 173          */
 174         subranges.add(j, new NCNode<T>(entry));
 175         return;
 176       }
 177
 178       if (subrange.getStart() <= start && subrange.getEnd() >= end)
 179       {
 180         /*
 181          * push new entry inside this subrange as it encloses it
 182          */
 183         subrange.add(entry);
 184         return;
 185       }
 186
 187       if (start <= subrange.getStart())
 188       {
 189         if (end >= subrange.getEnd())
 190         {
 191           /*
 192            * new entry encloses this subrange (and possibly preceding ones);
 193            * continue to find the maximal list it encloses
 194            */
 195           if (!enclosing)
 196           {
 197             firstEnclosed = j;
 198           }
 199           lastEnclosed = j;
 200           enclosing = true;
 201           continue;
 202         }
 203         else
 204         {
 205           /*
 206            * entry spans from before this subrange to inside it
 207            */
 208           if (enclosing)
 209           {
 210             /*
 211              * entry encloses one or more preceding subranges
 212              */
 213             addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 214             return;
 215           }
 216           else
 217           {
 218             /*
 219              * entry spans two subranges but doesn't enclose any
 220              * so just add it
 221              */
 222             subranges.add(j, new NCNode<T>(entry));
 223             return;
 224           }
 225         }
 226       }
 227       else
 228       {
 229         overlapping = true;
 230       }
 231     }
 232
 233     /*
 234      * drops through to here if new range encloses all others
 235      */
 236     if (enclosing)
 237     {
 238       addEnclosingRange(entry, firstEnclosed, lastEnclosed);
 239     }
 240   }
 241
 242   /**
 243    * Update the tree so that the range of the new entry encloses subranges i to
 244    * j (inclusive). That is, replace subranges i-j (inclusive) with a new
 245    * subrange that contains them.
 246    *
 247    * @param entry
 248    * @param i
 249    * @param j
 250    */
 251   protected synchronized void addEnclosingRange(T entry, final int i,
 252           final int j)
 253   {
 254     NCList<T> newNCList = new NCList<T>();
 255     newNCList.subranges.addAll(subranges.subList(i, j + 1));
 256     NCNode<T> newNode = new NCNode<T>(entry, newNCList);
 257     for (int k = j; k >= i; k--)
 258     {
 259       subranges.remove(k);
 260     }
 261     subranges.add(i, newNode);
 262   }
 263
 264   /**
 265    * Returns a (possibly empty) list of items whose extent overlaps the given
 266    * range
 267    *
 268    * @param from
 269    *          start of overlap range (inclusive)
 270    * @param to
 271    *          end of overlap range (inclusive)
 272    * @return
 273    */
 274   public List<T> findOverlaps(long from, long to)
 275   {
 276     List<T> result = new ArrayList<T>();
 277
 278     findOverlaps(from, to, result);
 279
 280     return result;
 281   }
 282
 283   /**
 284    * Recursively searches the NCList adding any items that overlap the from-to
 285    * range to the result list
 286    *
 287    * @param from
 288    * @param to
 289    * @param result
 290    */
 291   protected void findOverlaps(long from, long to,
 292  List<T> result)
 293   {
 294     /*
 295      * find the first sublist that might overlap, i.e.
 296      * the first whose end position is >= from
 297      */
 298     int candidateIndex = findFirstOverlap(from);
 299
 300     if (candidateIndex == -1)
 301     {
 302       return;
 303     }
 304
 305     for (int i = candidateIndex; i < subranges.size(); i++)
 306     {
 307       NCNode<T> candidate = subranges.get(i);
 308       if (candidate.getStart() > to)
 309       {
 310         /*
 311          * we are past the end of our target range
 312          */
 313         break;
 314       }
 315       candidate.addOverlaps(from, to, result);
 316     }
 317
 318   }
 319
 320   /**
 321    * Search subranges for the first one whose end position is not before the
 322    * target range's start position, i.e. the first one that may overlap the
 323    * target range. Returns the index in the list of the first such range found,
 324    * or -1 if none found.
 325    *
 326    * @param from
 327    * @return
 328    */
 329   protected int findFirstOverlap(long from)
 330   {
 331     // TODO binary search
 332     // for now quick cheat linear search
 333     int i = 0;
 334     if (subranges != null)
 335     {
 336       for (NCNode<T> subrange : subranges)
 337       {
 338         if (subrange.getEnd() >= from)
 339         {
 340           return i;
 341         }
 342         i++;
 343       }
 344     }
 345     return -1;
 346   }
 347
 348   /**
 349    * Formats the tree as a bracketed list e.g.
 350    *
 351    * <pre>
 352    * [1-100 [10-30 [10-20]], 15-30 [20-20]]
 353    * </pre>
 354    */
 355   @Override
 356   public String toString()
 357   {
 358     return subranges.toString();
 359   }
 360
 361   /**
 362    * Returns a string representation of the data where containment is shown bgy
 363    * indentation on new lines
 364    *
 365    * @return
 366    */
 367   public String prettyPrint()
 368   {
 369     StringBuilder sb = new StringBuilder(512);
 370     int offset = 0;
 371     int indent = 2;
 372     prettyPrint(sb, offset, indent);
 373     return sb.toString();
 374   }
 375
 376   /**
 377    * @param sb
 378    * @param offset
 379    * @param indent
 380    */
 381   void prettyPrint(StringBuilder sb, int offset, int indent)
 382   {
 383     boolean first = true;
 384     for (NCNode<T> subrange : subranges)
 385     {
 386       if (!first)
 387       {
 388         sb.append(System.lineSeparator());
 389       }
 390       first = false;
 391       subrange.prettyPrint(sb, offset, indent);
 392     }
 393   }
 394
 395   /**
 396    * Answers true if the data held satisfy the rules of construction of an
 397    * NCList, else false.
 398    *
 399    * @return
 400    */
 401   public boolean isValid()
 402   {
 403     return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE);
 404   }
 405
 406   /**
 407    * Answers true if the data held satisfy the rules of construction of an
 408    * NCList bounded within the given start-end range, else false.
 409    * <p>
 410    * Each subrange must lie within start-end (inclusive). Subranges must be
 411    * ordered by start position ascending.
 412    * <p>
 413    *
 414    * @param start
 415    * @param end
 416    * @return
 417    */
 418   boolean isValid(final int start, final int end)
 419   {
 420     int lastStart = start;
 421     for (NCNode<T> subrange : subranges)
 422     {
 423       if (subrange.getStart() < lastStart)
 424       {
 425         System.err.println("error in NCList: range " + subrange.toString()
 426                 + " starts before " + lastStart);
 427         return false;
 428       }
 429       if (subrange.getEnd() > end)
 430       {
 431         System.err.println("error in NCList: range " + subrange.toString()
 432                 + " ends after " + end);
 433         return false;
 434       }
 435       lastStart = subrange.getStart();
 436
 437       if (!subrange.isValid())
 438       {
 439         return false;
 440       }
 441     }
 442     return true;
 443   }
 444
 445   /**
 446    * Answers the lowest start position enclosed by the ranges
 447    *
 448    * @return
 449    */
 450   public int getStart()
 451   {
 452     return subranges.isEmpty() ? 0 : subranges.get(0).getStart();
 453   }
 454
 455   /**
 456    * Returns the number of ranges held (deep count)
 457    *
 458    * @return
 459    */
 460   public int getSize()
 461   {
 462     return size;
 463   }
 464 }