1 /**
  2  * Legacy-compatible NCList for 1.2.1 backcompat.
  3  * @extends
  4  */
  5 function NCList_v0() {}
  6 
  7 NCList_v0.prototype.importExisting = function(nclist, sublistIndex,
  8                                            lazyIndex, baseURL,
  9                                            lazyUrlTemplate) {
 10     this.topList = nclist;
 11     this.sublistIndex = sublistIndex;
 12     this.lazyIndex = lazyIndex;
 13     this.baseURL = baseURL;
 14     this.lazyUrlTemplate = lazyUrlTemplate;
 15 };
 16 
 17 NCList_v0.prototype.fill = function(intervals, sublistIndex) {
 18     //intervals: array of arrays of [start, end, ...]
 19     //sublistIndex: index into a [start, end] array for storing a sublist
 20     //              array. this is so you can use those arrays for something
 21     //              else, and keep the NCList_v0 bookkeeping from interfering.
 22     //              That's hacky, but keeping a separate copy of the intervals
 23     //              in the NCList_v0 seems like a waste (TODO: measure that waste).
 24     //half-open?
 25     this.sublistIndex = sublistIndex;
 26     var myIntervals = intervals;//.concat();
 27     //sort by OL
 28     myIntervals.sort(function(a, b) {
 29         if (a[0] != b[0])
 30             return a[0] - b[0];
 31         else
 32             return b[1] - a[1];
 33     });
 34     var sublistStack = new Array();
 35     var curList = new Array();
 36     this.topList = curList;
 37     curList.push(myIntervals[0]);
 38     var curInterval, topSublist;
 39     for (var i = 1, len = myIntervals.length; i < len; i++) {
 40         curInterval = myIntervals[i];
 41         //if this interval is contained in the previous interval,
 42         if (curInterval[1] < myIntervals[i - 1][1]) {
 43             //create a new sublist starting with this interval
 44             sublistStack.push(curList);
 45             curList = new Array(curInterval);
 46             myIntervals[i - 1][sublistIndex] = curList;
 47         } else {
 48             //find the right sublist for this interval
 49             while (true) {
 50                 if (0 == sublistStack.length) {
 51                     curList.push(curInterval);
 52                     break;
 53                 } else {
 54                     topSublist = sublistStack[sublistStack.length - 1];
 55                     if (topSublist[topSublist.length - 1][1] > curInterval[1]) {
 56                         //curList is the first (deepest) sublist that
 57                         //curInterval fits into
 58                         curList.push(curInterval);
 59                         break;
 60                     } else {
 61                         curList = sublistStack.pop();
 62                     }
 63                 }
 64             }
 65         }
 66     }
 67 };
 68 
 69 NCList_v0.prototype.binarySearch = function(arr, item, itemIndex) {
 70     var low = -1;
 71     var high = arr.length;
 72     var mid;
 73 
 74     while (high - low > 1) {
 75         mid = (low + high) >>> 1;
 76         if (arr[mid][itemIndex] > item)
 77             high = mid;
 78         else
 79             low = mid;
 80     }
 81 
 82     //if we're iterating rightward, return the high index;
 83     //if leftward, the low index
 84     if (1 == itemIndex) return high; else return low;
 85 };
 86 
 87 NCList_v0.prototype.iterHelper = function(arr, from, to, fun, finish,
 88                                        inc, searchIndex, testIndex, path) {
 89     var len = arr.length;
 90     var i = this.binarySearch(arr, from, searchIndex);
 91     while ((i < len)
 92            && (i >= 0)
 93            && ((inc * arr[i][testIndex]) < (inc * to)) ) {
 94 
 95         if ("object" == typeof arr[i][this.lazyIndex]) {
 96             var ncl = this;
 97             // lazy node
 98             if (arr[i][this.lazyIndex].state) {
 99                 if ("loading" == arr[i][this.lazyIndex].state) {
100                     // node is currenly loading; finish this query once it
101                     // has been loaded
102                     finish.inc();
103                     arr[i][this.lazyIndex].callbacks.push(
104                         function(parentIndex) {
105                             return function(o) {
106                                 ncl.iterHelper(o, from, to, fun, finish, inc,
107                                                searchIndex, testIndex,
108                                                path.concat(parentIndex));
109                                 finish.dec();
110                             };
111                         }(i)
112                     );
113                 } else if ("loaded" == arr[i][this.lazyIndex].state) {
114                     // just continue below
115                 } else {
116                     console.log("unknown lazy type: " + arr[i]);
117                 }
118             } else {
119                 // no "state" property means this node hasn't been loaded,
120                 // start loading
121                 arr[i][this.lazyIndex].state = "loading";
122                 arr[i][this.lazyIndex].callbacks = [];
123                 finish.inc();
124                 dojo.xhrGet(
125                     {
126                         url: Util.resolveUrl(
127                                 this.baseURL,
128                                 this.lazyUrlTemplate.replace(
129                                     /\{chunk\}/g,
130                                    arr[i][this.lazyIndex].chunk
131                                 )
132                              ),
133                         handleAs: "json",
134                         load: function(lazyFeat, lazyObj,
135                                        sublistIndex, parentIndex) {
136                             return function(o) {
137                                 lazyObj.state = "loaded";
138                                 lazyFeat[sublistIndex] = o;
139                                 ncl.iterHelper(o, from, to,
140                                                fun, finish, inc,
141                                                searchIndex, testIndex,
142                                                path.concat(parentIndex));
143                                 for (var c = 0;
144                                      c < lazyObj.callbacks.length;
145                                      c++)
146                                      lazyObj.callbacks[c](o);
147                                 finish.dec();
148                             };
149                         }(arr[i], arr[i][this.lazyIndex], this.sublistIndex, i),
150                         error: function() {
151                             finish.dec();
152                         }
153                     });
154             }
155         } else {
156             fun(arr[i], path.concat(i));
157         }
158 
159         if (arr[i][this.sublistIndex])
160             this.iterHelper(arr[i][this.sublistIndex], from, to,
161                             fun, finish, inc, searchIndex, testIndex,
162                             path.concat(i));
163         i += inc;
164     }
165 };
166 
167 NCList_v0.prototype.iterate = function(from, to, fun, postFun) {
168     // calls the given function once for each of the
169     // intervals that overlap the given interval
170     //if from <= to, iterates left-to-right, otherwise iterates right-to-left
171 
172     //inc: iterate leftward or rightward
173     var inc = (from > to) ? -1 : 1;
174     //searchIndex: search on start or end
175     var searchIndex = (from > to) ? 0 : 1;
176     //testIndex: test on start or end
177     var testIndex = (from > to) ? 1 : 0;
178     var finish = new Finisher(postFun);
179     this.iterHelper(this.topList, from, to, fun, finish,
180                     inc, searchIndex, testIndex, []);
181     finish.finish();
182 };
183 
184 NCList_v0.prototype.histogram = function(from, to, numBins, callback) {
185     //calls callback with a histogram of the feature density
186     //in the given interval
187 
188     var result = new Array(numBins);
189     var binWidth = (to - from) / numBins;
190     for (var i = 0; i < numBins; i++) result[i] = 0;
191     //this.histHelper(this.topList, from, to, result, numBins, (to - from) / numBins);
192     this.iterate(from, to,
193                  function(feat) {
194 	             var firstBin =
195                          Math.max(0, ((feat[0] - from) / binWidth) | 0);
196                      var lastBin =
197                          Math.min(numBins, ((feat[1] - from) / binWidth) | 0);
198 	             for (var bin = firstBin; bin <= lastBin; bin++)
199                          result[bin]++;
200                  },
201                  function() {
202                      callback(result);
203                  }
204                  );
205 };
206 
207 /*
208 
209 Copyright (c) 2007-2009 The Evolutionary Software Foundation
210 
211 Created by Mitchell Skinner <mitch_skinner@berkeley.edu>
212 
213 This package and its accompanying libraries are free software; you can
214 redistribute it and/or modify it under the terms of the LGPL (either
215 version 2.1, or at your option, any later version) or the Artistic
216 License 2.0.  Refer to LICENSE for the full license text.
217 
218 */
219