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