Add shared code for a new a graphics benchmark
[WebKit-https.git] / 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 }