1 // MODEL
  2 
  3 /**
  4 
  5 Nested containment list.
  6 
  7 @class
  8 
  9 After
 10 <pre>
 11   Alekseyenko, A., and Lee, C. (2007).
 12   Nested Containment List (NCList): A new algorithm for accelerating
 13      interval query of genome alignment and interval databases.
 14   Bioinformatics, doi:10.1093/bioinformatics/btl647
 15 </pre>
 16 
 17 <a href="http://bioinformatics.oxfordjournals.org/cgi/content/abstract/btl647v1">http://bioinformatics.oxfordjournals.org/cgi/content/abstract/btl647v1</a>
 18 
 19  */
 20 
 21 function NCList() {
 22 }
 23 
 24 NCList.prototype.importExisting = function(nclist, attrs, baseURL,
 25                                            lazyUrlTemplate, lazyClass) {
 26     this.topList = nclist;
 27     this.attrs = attrs;
 28     this.start = attrs.makeFastGetter("Start");
 29     this.end = attrs.makeFastGetter("End");
 30     this.lazyClass = lazyClass;
 31     this.baseURL = baseURL;
 32     this.lazyUrlTemplate = lazyUrlTemplate;
 33     this.lazyChunks = {};
 34 };
 35 
 36 NCList.prototype.fill = function(intervals, attrs) {
 37     //intervals: array of arrays of [start, end, ...]
 38     //attrs: an ArrayRepr object
 39     //half-open?
 40     this.attrs = attrs;
 41     this.start = attrs.makeFastGetter("Start");
 42     this.end = attrs.makeFastGetter("End");
 43     var sublist = attrs.makeSetter("Sublist");
 44     var start = this.start;
 45     var end = this.end;
 46     var myIntervals = intervals;
 47     //sort by OL
 48     myIntervals.sort(function(a, b) {
 49         if (start(a) != start(b))
 50             return start(a) - start(b());
 51         else
 52             return end(b) - end(a);
 53     });
 54     var sublistStack = new Array();
 55     var curList = new Array();
 56     this.topList = curList;
 57     curList.push(myIntervals[0]);
 58     var curInterval, topSublist;
 59     for (var i = 1, len = myIntervals.length; i < len; i++) {
 60         curInterval = myIntervals[i];
 61         //if this interval is contained in the previous interval,
 62         if (end(curInterval) < end(myIntervals[i - 1])) {
 63             //create a new sublist starting with this interval
 64             sublistStack.push(curList);
 65             curList = new Array(curInterval);
 66             sublist(myIntervals[i - 1], curList);
 67         } else {
 68             //find the right sublist for this interval
 69             while (true) {
 70                 if (0 == sublistStack.length) {
 71                     curList.push(curInterval);
 72                     break;
 73                 } else {
 74                     topSublist = sublistStack[sublistStack.length - 1];
 75                     if (end(topSublist[topSublist.length - 1])
 76                         > end(curInterval)) {
 77                         //curList is the first (deepest) sublist that
 78                         //curInterval fits into
 79                         curList.push(curInterval);
 80                         break;
 81                     } else {
 82                         curList = sublistStack.pop();
 83                     }
 84                 }
 85             }
 86         }
 87     }
 88 };
 89 
 90 NCList.prototype.binarySearch = function(arr, item, getter) {
 91     var low = -1;
 92     var high = arr.length;
 93     var mid;
 94 
 95     while (high - low > 1) {
 96         mid = (low + high) >>> 1;
 97         if (getter(arr[mid]) > item)
 98             high = mid;
 99         else
100             low = mid;
101     }
102 
103     //if we're iterating rightward, return the high index;
104     //if leftward, the low index
105     if (getter === this.end) return high; else return low;
106 };
107 
108 NCList.prototype.iterHelper = function(arr, from, to, fun, finish,
109                                        inc, searchGet, testGet, path) {
110     var len = arr.length;
111     var i = this.binarySearch(arr, from, searchGet);
112     var getChunk = this.attrs.makeGetter("Chunk");
113     var getSublist = this.attrs.makeGetter("Sublist");
114 
115     while ((i < len)
116            && (i >= 0)
117            && ((inc * testGet(arr[i])) < (inc * to)) ) {
118 
119         if (arr[i][0] == this.lazyClass) {
120             var ncl = this;
121             var chunkNum = getChunk(arr[i]);
122             if (!(chunkNum in this.lazyChunks)) {
123                 this.lazyChunks[chunkNum] = {};
124             }
125             var chunk = this.lazyChunks[chunkNum];
126             finish.inc();
127             Util.maybeLoad({ url: Util.resolveUrl(this.baseURL,
128                                            this.lazyUrlTemplate.replace(
129                                                    /\{Chunk\}/g, chunkNum
130                                            ) ),
131                              handleAs: 'json'
132                            },
133                            chunk,
134                            (function (myChunkNum) {
135                                return function(o) {
136                                    ncl.iterHelper(o, from, to, fun, finish,
137                                                   inc, searchGet, testGet,
138                                                   [myChunkNum]);
139                                    finish.dec();
140                                };
141                             })(chunkNum),
142                            function() {
143                                finish.dec();
144                            }
145                           );
146         } else {
147             fun(arr[i], path.concat(i));
148         }
149 
150         var sublist = getSublist(arr[i]);
151         if (sublist)
152             this.iterHelper(sublist, from, to,
153                             fun, finish, inc, searchGet, testGet,
154                             path.concat(i));
155         i += inc;
156     }
157 };
158 
159 NCList.prototype.iterate = function(from, to, fun, postFun) {
160     // calls the given function once for each of the
161     // intervals that overlap the given interval
162     //if from <= to, iterates left-to-right, otherwise iterates right-to-left
163 
164     //inc: iterate leftward or rightward
165     var inc = (from > to) ? -1 : 1;
166     //searchGet: search on start or end
167     var searchGet = (from > to) ? this.start : this.end;
168     //testGet: test on start or end
169     var testGet = (from > to) ? this.end : this.start;
170     var finish = new Finisher(postFun);
171     this.iterHelper(this.topList, from, to, fun, finish,
172                     inc, searchGet, testGet, [0]);
173     finish.finish();
174 };
175 
176 NCList.prototype.histogram = function(from, to, numBins, callback) {
177     //calls callback with a histogram of the feature density
178     //in the given interval
179 
180     var result = new Array(numBins);
181     var binWidth = (to - from) / numBins;
182     var start = this.start;
183     var end = this.end;
184     for (var i = 0; i < numBins; i++) result[i] = 0;
185     this.iterate(from, to,
186                  function(feat) {
187 	             var firstBin =
188                          Math.max(0, ((start(feat) - from) / binWidth) | 0);
189                      var lastBin =
190                          Math.min(numBins, ((end(feat) - from) / binWidth) | 0);
191 	             for (var bin = firstBin; bin <= lastBin; bin++)
192                          result[bin]++;
193                  },
194                  function() {
195                      callback(result);
196                  }
197                  );
198 };
199 
200 /*
201 
202 Copyright (c) 2007-2009 The Evolutionary Software Foundation
203 
204 Created by Mitchell Skinner <mitch_skinner@berkeley.edu>
205 
206 This package and its accompanying libraries are free software; you can
207 redistribute it and/or modify it under the terms of the LGPL (either
208 version 2.1, or at your option, any later version) or the Artistic
209 License 2.0.  Refer to LICENSE for the full license text.
210 
211 */
212