Update benchmark test suite
[WebKit-https.git] / 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 }