PerformanceTests/Animometer/tests/resources/algorithm.js

   1 function Heap(maxSize, compare)
   2 {
   3     this._maxSize = maxSize;
   4     this._compare = compare;
   5     this._size = 0;
   6     this._values = new Array(this._maxSize);
   7 }
   8
   9 Heap.prototype =
  10 {
  11     // This is a binary heap represented in an array. The root element is stored
  12     // in the first element in the array. The root is followed by its two children.
  13     // Then its four grandchildren and so on. So every level in the binary heap is
  14     // doubled in the following level. Here is an example of the node indices and
  15     // how they are related to their parents and children.
  16     // ===========================================================================
  17     //              0       1       2       3       4       5       6
  18     // PARENT       -1      0       0       1       1       2       2
  19     // LEFT         1       3       5       7       9       11      13
  20     // RIGHT        2       4       6       8       10      12      14
  21     // ===========================================================================
  22     _parentIndex: function(i)
  23     {
  24         return i > 0 ? Math.floor((i - 1) / 2) : -1;
  25     },
  26
  27     _leftIndex: function(i)
  28     {
  29         var leftIndex = i * 2 + 1;
  30         return leftIndex < this._size ? leftIndex : -1;
  31     },
  32
  33     _rightIndex: function(i)
  34     {
  35         var rightIndex = i * 2 + 2;
  36         return rightIndex < this._size ? rightIndex : -1;
  37     },
  38
  39     // Return the child index that may violate the heap property at index i.
  40     _childIndex: function(i)
  41     {
  42         var left = this._leftIndex(i);
  43         var right = this._rightIndex(i);
  44
  45         if (left != -1 && right != -1)
  46             return this._compare(this._values[left], this._values[right]) > 0 ? left : right;
  47
  48         return left != -1 ? left : right;
  49     },
  50
  51     init: function()
  52     {
  53         this._size = 0;
  54     },
  55
  56     top: function()
  57     {
  58         return this._size ? this._values[0] : NaN;
  59     },
  60
  61     push: function(value)
  62     {
  63         if (this._size == this._maxSize) {
  64             // If size is bounded and the new value can be a parent of the top()
  65             // if the size were unbounded, just ignore the new value.
  66             if (this._compare(value, this.top()) > 0)
  67                 return;
  68             this.pop();
  69         }
  70         this._values[this._size++] = value;
  71         this._bubble(this._size - 1);
  72     },
  73
  74     pop: function()
  75     {
  76         if (!this._size)
  77             return NaN;
  78
  79         this._values[0] = this._values[--this._size];
  80         this._sink(0);
  81     },
  82
  83     _bubble: function(i)
  84     {
  85         // Fix the heap property at index i given that parent is the only node that
  86         // may violate the heap property.
  87         for (var pi = this._parentIndex(i); pi != -1; i = pi, pi = this._parentIndex(pi)) {
  88             if (this._compare(this._values[pi], this._values[i]) > 0)
  89                 break;
  90
  91             this._values.swap(pi, i);
  92         }
  93     },
  94
  95     _sink: function(i)
  96     {
  97         // Fix the heap property at index i given that each of the left and the right
  98         // sub-trees satisfies the heap property.
  99         for (var ci = this._childIndex(i); ci != -1; i = ci, ci = this._childIndex(ci)) {
 100             if (this._compare(this._values[i], this._values[ci]) > 0)
 101                 break;
 102
 103             this._values.swap(ci, i);
 104         }
 105     },
 106
 107     str: function()
 108     {
 109         var out = "Heap[" + this._size + "] = [";
 110         for (var i = 0; i < this._size; ++i) {
 111             out += this._values[i];
 112             if (i < this._size - 1)
 113                 out += ", ";
 114         }
 115         return out + "]";
 116     },
 117
 118     values: function(size) {
 119         // Return the last "size" heap elements values.
 120         var values = this._values.slice(0, this._size);
 121         return values.sort(this._compare).slice(0, Math.min(size, this._size));
 122     }
 123 }
 124
 125 var Algorithm = {
 126     createMinHeap: function(maxSize)
 127     {
 128         return new Heap(maxSize, function(a, b) { return b - a; });
 129     },
 130
 131     createMaxHeap: function(maxSize) {
 132         return new Heap(maxSize, function(a, b) { return a - b; });
 133     }
 134 }