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   /*
  19    * a list, in start position order, of sublists of ranges ordered so
  20    * that each contains (or is the same as) the one that follows it
  21    */
  22   private List<NCNode<T>> subranges;
  23
  24   /*
  25    * a comparator to sort intervals by start position ascending, with
  26    * longer (enclosing) intervals preceding those they enclose
  27    */
  28   Comparator<ContiguousI> intervalSorter = new RangeComparator(true);
  29
  30   /**
  31    * Constructor given a list of things that are each located on a contiguous
  32    * interval. Note that the constructor may reorder the list.
  33    * <p>
  34    * We assume here that for each range, start &lt;= end. Behaviour for reverse
  35    * ordered ranges is undefined.
  36    *
  37    * @param ranges
  38    */
  39   public NCList(List<T> ranges)
  40   {
  41     build(ranges);
  42   }
  43
  44   /**
  45    * @param ranges
  46    */
  47   protected void build(List<T> ranges)
  48   {
  49     /*
  50      * sort by start ascending so that contained intervals
  51      * follow their containing interval
  52      */
  53     Collections.sort(ranges, intervalSorter);
  54
  55     List<SubList> sublists = findSubranges(ranges);
  56
  57     subranges = new ArrayList<NCNode<T>>();
  58
  59     /*
  60      * convert each subrange to an NCNode consisting of a range and
  61      * (possibly) its contained NCList
  62      */
  63     for (SubList sublist : sublists)
  64     {
  65       subranges.add(new NCNode<T>(ranges.subList(sublist.startIndex,
  66               sublist.endIndex + 1)));
  67     }
  68     sublists.clear();
  69   }
  70
  71   public NCList(T entry)
  72   {
  73     List<T> ranges = new ArrayList<T>();
  74     ranges.add(entry);
  75     build(ranges);
  76   }
  77
  78   /**
  79    * Traverses the sorted ranges to identify sublists, within which each
  80    * interval contains the one that follows it
  81    *
  82    * @param ranges
  83    * @return
  84    */
  85   protected List<SubList> findSubranges(List<T> ranges)
  86   {
  87     List<SubList> sublists = new ArrayList<SubList>();
  88
  89     int listStartIndex = 0;
  90     long lastEndPos = Long.MAX_VALUE;
  91
  92     for (int i = 0; i < ranges.size(); i++)
  93     {
  94       ContiguousI nextInterval = ranges.get(i);
  95       long nextStart = nextInterval.getBegin();
  96       long nextEnd = nextInterval.getEnd();
  97       if (nextStart > lastEndPos || nextEnd > lastEndPos)
  98       {
  99         /*
 100          * this interval is not contained in the preceding one
 101          * close off the last sublist
 102          */
 103         sublists.add(new SubList(listStartIndex, i - 1));
 104         listStartIndex = i;
 105       }
 106       lastEndPos = nextEnd;
 107     }
 108
 109     sublists.add(new SubList(listStartIndex, ranges.size() - 1));
 110     return sublists;
 111   }
 112
 113   /**
 114    * Adds one entry to the stored set
 115    *
 116    * @param entry
 117    */
 118   public synchronized void add(T entry)
 119   {
 120     long start = entry.getBegin();
 121     long end = entry.getEnd();
 122
 123     /*
 124      * cases:
 125      * - precedes all subranges: add as NCNode on front of list
 126      * - follows all subranges: add as NCNode on end of list
 127      * - enclosed by a subrange - add recursively to subrange
 128      * - encloses one or more subranges - push them inside it
 129      * - none of the above - add as a new node and resort nodes list (?)
 130      */
 131
 132     /*
 133      * find the first subrange whose end does not precede entry's start
 134      */
 135     int candidateIndex = findFirstOverlap(start);
 136     if (candidateIndex == -1)
 137     {
 138       /*
 139        * all subranges precede this one - add it on the end
 140        */
 141       subranges.add(new NCNode<T>(entry));
 142       return;
 143     }
 144
 145     /*
 146      * search for maximal span of subranges i-k that the new entry
 147      * encloses; or a subrange that encloses the new entry
 148      */
 149     int i = candidateIndex;
 150     boolean enclosing = false;
 151     boolean overlapping = false;
 152
 153     for (int j = candidateIndex; j < subranges.size(); j++)
 154     {
 155       NCNode<T> subrange = subranges.get(j);
 156
 157       if (end < subrange.getStart() && !overlapping)
 158       {
 159         /*
 160          * new entry lies between subranges j-1 j
 161          */
 162         subranges.add(j, new NCNode<T>(entry));
 163         return;
 164       }
 165
 166       if (subrange.getStart() <= start && subrange.getEnd() >= end)
 167       {
 168         /*
 169          * push new entry inside this subrange as it encloses it
 170          */
 171         subrange.add(entry);
 172         return;
 173       }
 174
 175       if (start <= subrange.getStart())
 176       {
 177         if (end >= subrange.getEnd())
 178         {
 179           /*
 180            * new entry encloses this subrange (and possibly preceding ones);
 181            * continue to find the maximal list it encloses
 182            */
 183           enclosing = true;
 184           continue;
 185         }
 186         else
 187         {
 188           /*
 189            * entry spans from before this subrange to inside it
 190            */
 191           if (enclosing)
 192           {
 193             /*
 194              * entry encloses one or more preceding subranges
 195              */
 196             addEnclosingRange(entry, i, j - 1);
 197             return;
 198           }
 199           else
 200           {
 201             /*
 202              * entry spans two subranges but doesn't enclose any
 203              * so just add it
 204              */
 205             subranges.add(j, new NCNode<T>(entry));
 206             return;
 207           }
 208         }
 209       }
 210     }
 211   }
 212
 213   /**
 214    * Update the tree so that the range of the new entry encloses subranges i to
 215    * j (inclusive). That is, replace subranges i-j with a new subrange that
 216    * contains them.
 217    *
 218    * @param entry
 219    * @param i
 220    * @param j
 221    */
 222   protected synchronized void addEnclosingRange(T entry, int i, int j)
 223   {
 224     // TODO how to rebuild the subranges as an NCList?
 225
 226   }
 227
 228   /**
 229    * Returns a (possibly empty) list of items whose extent overlaps the given
 230    * range
 231    *
 232    * @param from
 233    *          start of overlap range (inclusive)
 234    * @param to
 235    *          end of overlap range (inclusive)
 236    * @return
 237    */
 238   public List<T> findOverlaps(long from, long to)
 239   {
 240     List<T> result = new ArrayList<T>();
 241
 242     findOverlaps(from, to, result);
 243
 244     return result;
 245   }
 246
 247   /**
 248    * Recursively searches the NCList adding any items that overlap the from-to
 249    * range to the result list
 250    *
 251    * @param from
 252    * @param to
 253    * @param result
 254    */
 255   protected void findOverlaps(long from, long to,
 256  List<T> result)
 257   {
 258     /*
 259      * find the first sublist that might overlap, i.e.
 260      * the first whose end position is >= from
 261      */
 262     int candidateIndex = findFirstOverlap(from);
 263
 264     if (candidateIndex == -1)
 265     {
 266       return;
 267     }
 268
 269     for (int i = candidateIndex; i < subranges.size(); i++)
 270     {
 271       NCNode<T> candidate = subranges.get(i);
 272       if (candidate.getStart() > to)
 273       {
 274         /*
 275          * we are past the end of our target range
 276          */
 277         break;
 278       }
 279       candidate.addOverlaps(from, to, result);
 280     }
 281
 282   }
 283
 284   /**
 285    * Search subranges for the first one whose end position is not before the
 286    * target range's start position, i.e. the first one that may overlap the
 287    * target range. Returns the index in the list of the first such range found,
 288    * or -1 if none found.
 289    *
 290    * @param from
 291    * @return
 292    */
 293   protected int findFirstOverlap(long from)
 294   {
 295     // TODO binary search
 296     // for now quick cheat linear search
 297     int i = 0;
 298     if (subranges != null)
 299     {
 300       for (NCNode<T> subrange : subranges)
 301       {
 302         if (subrange.getEnd() >= from)
 303         {
 304           return i;
 305         }
 306         i++;
 307       }
 308     }
 309     return -1;
 310   }
 311
 312   /**
 313    * Formats the tree as a bracketed list e.g.
 314    *
 315    * <pre>
 316    * [1-100 [10-30 [10-20]], 15-30 [20-20]]
 317    * </pre>
 318    */
 319   @Override
 320   public String toString()
 321   {
 322     return subranges.toString();
 323   }
 324 }