1  // Generated by CoffeeScript 1.8.0
  2  (function() {
  3    var Heap, defaultCmp, floor, heapify, heappop, heappush, heappushpop, heapreplace, insort, min, nlargest, nsmallest, updateItem, _siftdown, _siftup;
  4  
  5    floor = Math.floor, min = Math.min;
  6  
  7  
  8    /*
  9    Default comparison function to be used
 10     */
 11  
 12    defaultCmp = function(x, y) {
 13      if (x < y) {
 14        return -1;
 15      }
 16      if (x > y) {
 17        return 1;
 18      }
 19      return 0;
 20    };
 21  
 22  
 23    /*
 24    Insert item x in list a, and keep it sorted assuming a is sorted.
 25    
 26    If x is already in a, insert it to the right of the rightmost x.
 27    
 28    Optional args lo (default 0) and hi (default a.length) bound the slice
 29    of a to be searched.
 30     */
 31  
 32    insort = function(a, x, lo, hi, cmp) {
 33      var mid;
 34      if (lo == null) {
 35        lo = 0;
 36      }
 37      if (cmp == null) {
 38        cmp = defaultCmp;
 39      }
 40      if (lo < 0) {
 41        throw new Error('lo must be non-negative');
 42      }
 43      if (hi == null) {
 44        hi = a.length;
 45      }
 46      while (lo < hi) {
 47        mid = floor((lo + hi) / 2);
 48        if (cmp(x, a[mid]) < 0) {
 49          hi = mid;
 50        } else {
 51          lo = mid + 1;
 52        }
 53      }
 54      return ([].splice.apply(a, [lo, lo - lo].concat(x)), x);
 55    };
 56  
 57  
 58    /*
 59    Push item onto heap, maintaining the heap invariant.
 60     */
 61  
 62    heappush = function(array, item, cmp) {
 63      if (cmp == null) {
 64        cmp = defaultCmp;
 65      }
 66      array.push(item);
 67      return _siftdown(array, 0, array.length - 1, cmp);
 68    };
 69  
 70  
 71    /*
 72    Pop the smallest item off the heap, maintaining the heap invariant.
 73     */
 74  
 75    heappop = function(array, cmp) {
 76      var lastelt, returnitem;
 77      if (cmp == null) {
 78        cmp = defaultCmp;
 79      }
 80      lastelt = array.pop();
 81      if (array.length) {
 82        returnitem = array[0];
 83        array[0] = lastelt;
 84        _siftup(array, 0, cmp);
 85      } else {
 86        returnitem = lastelt;
 87      }
 88      return returnitem;
 89    };
 90  
 91  
 92    /*
 93    Pop and return the current smallest value, and add the new item.
 94    
 95    This is more efficient than heappop() followed by heappush(), and can be
 96    more appropriate when using a fixed size heap. Note that the value
 97    returned may be larger than item! That constrains reasonable use of
 98    this routine unless written as part of a conditional replacement:
 99        if item > array[0]
100          item = heapreplace(array, item)
101     */
102  
103    heapreplace = function(array, item, cmp) {
104      var returnitem;
105      if (cmp == null) {
106        cmp = defaultCmp;
107      }
108      returnitem = array[0];
109      array[0] = item;
110      _siftup(array, 0, cmp);
111      return returnitem;
112    };
113  
114  
115    /*
116    Fast version of a heappush followed by a heappop.
117     */
118  
119    heappushpop = function(array, item, cmp) {
120      var _ref;
121      if (cmp == null) {
122        cmp = defaultCmp;
123      }
124      if (array.length && cmp(array[0], item) < 0) {
125        _ref = [array[0], item], item = _ref[0], array[0] = _ref[1];
126        _siftup(array, 0, cmp);
127      }
128      return item;
129    };
130  
131  
132    /*
133    Transform list into a heap, in-place, in O(array.length) time.
134     */
135  
136    heapify = function(array, cmp) {
137      var i, _i, _j, _len, _ref, _ref1, _results, _results1;
138      if (cmp == null) {
139        cmp = defaultCmp;
140      }
141      _ref1 = (function() {
142        _results1 = [];
143        for (var _j = 0, _ref = floor(array.length / 2); 0 <= _ref ? _j < _ref : _j > _ref; 0 <= _ref ? _j++ : _j--){ _results1.push(_j); }
144        return _results1;
145      }).apply(this).reverse();
146      _results = [];
147      for (_i = 0, _len = _ref1.length; _i < _len; _i++) {
148        i = _ref1[_i];
149        _results.push(_siftup(array, i, cmp));
150      }
151      return _results;
152    };
153  
154  
155    /*
156    Update the position of the given item in the heap.
157    This function should be called every time the item is being modified.
158     */
159  
160    updateItem = function(array, item, cmp) {
161      var pos;
162      if (cmp == null) {
163        cmp = defaultCmp;
164      }
165      pos = array.indexOf(item);
166      if (pos === -1) {
167        return;
168      }
169      _siftdown(array, 0, pos, cmp);
170      return _siftup(array, pos, cmp);
171    };
172  
173  
174    /*
175    Find the n largest elements in a dataset.
176     */
177  
178    nlargest = function(array, n, cmp) {
179      var elem, result, _i, _len, _ref;
180      if (cmp == null) {
181        cmp = defaultCmp;
182      }
183      result = array.slice(0, n);
184      if (!result.length) {
185        return result;
186      }
187      heapify(result, cmp);
188      _ref = array.slice(n);
189      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
190        elem = _ref[_i];
191        heappushpop(result, elem, cmp);
192      }
193      return result.sort(cmp).reverse();
194    };
195  
196  
197    /*
198    Find the n smallest elements in a dataset.
199     */
200  
201    nsmallest = function(array, n, cmp) {
202      var elem, i, los, result, _i, _j, _len, _ref, _ref1, _results;
203      if (cmp == null) {
204        cmp = defaultCmp;
205      }
206      if (n * 10 <= array.length) {
207        result = array.slice(0, n).sort(cmp);
208        if (!result.length) {
209          return result;
210        }
211        los = result[result.length - 1];
212        _ref = array.slice(n);
213        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
214          elem = _ref[_i];
215          if (cmp(elem, los) < 0) {
216            insort(result, elem, 0, null, cmp);
217            result.pop();
218            los = result[result.length - 1];
219          }
220        }
221        return result;
222      }
223      heapify(array, cmp);
224      _results = [];
225      for (i = _j = 0, _ref1 = min(n, array.length); 0 <= _ref1 ? _j < _ref1 : _j > _ref1; i = 0 <= _ref1 ? ++_j : --_j) {
226        _results.push(heappop(array, cmp));
227      }
228      return _results;
229    };
230  
231    _siftdown = function(array, startpos, pos, cmp) {
232      var newitem, parent, parentpos;
233      if (cmp == null) {
234        cmp = defaultCmp;
235      }
236      newitem = array[pos];
237      while (pos > startpos) {
238        parentpos = (pos - 1) >> 1;
239        parent = array[parentpos];
240        if (cmp(newitem, parent) < 0) {
241          array[pos] = parent;
242          pos = parentpos;
243          continue;
244        }
245        break;
246      }
247      return array[pos] = newitem;
248    };
249  
250    _siftup = function(array, pos, cmp) {
251      var childpos, endpos, newitem, rightpos, startpos;
252      if (cmp == null) {
253        cmp = defaultCmp;
254      }
255      endpos = array.length;
256      startpos = pos;
257      newitem = array[pos];
258      childpos = 2 * pos + 1;
259      while (childpos < endpos) {
260        rightpos = childpos + 1;
261        if (rightpos < endpos && !(cmp(array[childpos], array[rightpos]) < 0)) {
262          childpos = rightpos;
263        }
264        array[pos] = array[childpos];
265        pos = childpos;
266        childpos = 2 * pos + 1;
267      }
268      array[pos] = newitem;
269      return _siftdown(array, startpos, pos, cmp);
270    };
271  
272    Heap = (function() {
273      Heap.push = heappush;
274  
275      Heap.pop = heappop;
276  
277      Heap.replace = heapreplace;
278  
279      Heap.pushpop = heappushpop;
280  
281      Heap.heapify = heapify;
282  
283      Heap.updateItem = updateItem;
284  
285      Heap.nlargest = nlargest;
286  
287      Heap.nsmallest = nsmallest;
288  
289      function Heap(cmp) {
290        this.cmp = cmp != null ? cmp : defaultCmp;
291        this.nodes = [];
292      }
293  
294      Heap.prototype.push = function(x) {
295        return heappush(this.nodes, x, this.cmp);
296      };
297  
298      Heap.prototype.pop = function() {
299        return heappop(this.nodes, this.cmp);
300      };
301  
302      Heap.prototype.peek = function() {
303        return this.nodes[0];
304      };
305  
306      Heap.prototype.contains = function(x) {
307        return this.nodes.indexOf(x) !== -1;
308      };
309  
310      Heap.prototype.replace = function(x) {
311        return heapreplace(this.nodes, x, this.cmp);
312      };
313  
314      Heap.prototype.pushpop = function(x) {
315        return heappushpop(this.nodes, x, this.cmp);
316      };
317  
318      Heap.prototype.heapify = function() {
319        return heapify(this.nodes, this.cmp);
320      };
321  
322      Heap.prototype.updateItem = function(x) {
323        return updateItem(this.nodes, x, this.cmp);
324      };
325  
326      Heap.prototype.clear = function() {
327        return this.nodes = [];
328      };
329  
330      Heap.prototype.empty = function() {
331        return this.nodes.length === 0;
332      };
333  
334      Heap.prototype.size = function() {
335        return this.nodes.length;
336      };
337  
338      Heap.prototype.clone = function() {
339        var heap;
340        heap = new Heap();
341        heap.nodes = this.nodes.slice(0);
342        return heap;
343      };
344  
345      Heap.prototype.toArray = function() {
346        return this.nodes.slice(0);
347      };
348  
349      Heap.prototype.insert = Heap.prototype.push;
350  
351      Heap.prototype.top = Heap.prototype.peek;
352  
353      Heap.prototype.front = Heap.prototype.peek;
354  
355      Heap.prototype.has = Heap.prototype.contains;
356  
357      Heap.prototype.copy = Heap.prototype.clone;
358  
359      return Heap;
360  
361    })();
362  
363    (function(root, factory) {
364      if (typeof define === 'function' && define.amd) {
365        return define([], factory);
366      } else if (typeof exports === 'object') {
367        return module.exports = factory();
368      } else {
369        return root.Heap = factory();
370      }
371    })(this, function() {
372      return Heap;
373    });
374  
375  }).call(this);