PerformanceTests/Animometer/resources/algorithm.js

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