Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / cdjs / red_black_tree.js
1 /*
2  * Copyright (C) 2010, 2011, 2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 var RedBlackTree = (function(){
30     function compare(a, b) {
31         return a.compareTo(b);
32     }
33     
34     function treeMinimum(x) {
35         while (x.left)
36             x = x.left;
37         return x;
38     }
39     
40     function treeMaximum(x) {
41         while (x.right)
42             x = x.right;
43         return x;
44     }
45     
46     function Node(key, value) {
47         this.key = key;
48         this.value = value;
49         this.left = null;
50         this.right = null;
51         this.parent = null;
52         this.color = "red";
53     }
54     
55     Node.prototype.successor = function() {
56         var x = this;
57         if (x.right)
58             return treeMinimum(x.right);
59         var y = x.parent;
60         while (y && x == y.right) {
61             x = y;
62             y = y.parent;
63         }
64         return y;
65     };
66     
67     Node.prototype.predecessor = function() {
68         var x = this;
69         if (x.left)
70             return treeMaximum(x.left);
71         var y = x.parent;
72         while (y && x == y.left) {
73             x = y;
74             y = y.parent;
75         }
76         return y;
77     };
78     
79     Node.prototype.toString = function() {
80         return this.key + "=>" + this.value + " (" + this.color + ")";
81     };
82     
83     function RedBlackTree() {
84         this._root = null;
85     }
86     
87     RedBlackTree.prototype.put = function(key, value) {
88         var insertionResult = this._treeInsert(key, value);
89         if (!insertionResult.isNewEntry)
90             return insertionResult.oldValue;
91         var x = insertionResult.newNode;
92         
93         while (x != this._root && x.parent.color == "red") {
94             if (x.parent == x.parent.parent.left) {
95                 var y = x.parent.parent.right;
96                 if (y && y.color == "red") {
97                     // Case 1
98                     x.parent.color = "black";
99                     y.color = "black";
100                     x.parent.parent.color = "red";
101                     x = x.parent.parent;
102                 } else {
103                     if (x == x.parent.right) {
104                         // Case 2
105                         x = x.parent;
106                         this._leftRotate(x);
107                     }
108                     // Case 3
109                     x.parent.color = "black";
110                     x.parent.parent.color = "red";
111                     this._rightRotate(x.parent.parent);
112                 }
113             } else {
114                 // Same as "then" clause with "right" and "left" exchanged.
115                 var y = x.parent.parent.left;
116                 if (y && y.color == "red") {
117                     // Case 1
118                     x.parent.color = "black";
119                     y.color = "black";
120                     x.parent.parent.color = "red";
121                     x = x.parent.parent;
122                 } else {
123                     if (x == x.parent.left) {
124                         // Case 2
125                         x = x.parent;
126                         this._rightRotate(x);
127                     }
128                     // Case 3
129                     x.parent.color = "black";
130                     x.parent.parent.color = "red";
131                     this._leftRotate(x.parent.parent);
132                 }
133             }
134         }
135         
136         this._root.color = "black";
137         return null;
138     };
139     
140     RedBlackTree.prototype.remove = function(key) {
141         var z = this._findNode(key);
142         if (!z)
143             return null;
144         
145         // Y is the node to be unlinked from the tree.
146         var y;
147         if (!z.left || !z.right)
148             y = z;
149         else
150             y = z.successor();
151
152         // Y is guaranteed to be non-null at this point.
153         var x;
154         if (y.left)
155             x = y.left;
156         else
157             x = y.right;
158         
159         // X is the child of y which might potentially replace y in the tree. X might be null at
160         // this point.
161         var xParent;
162         if (x) {
163             x.parent = y.parent;
164             xParent = x.parent;
165         } else
166             xParent = y.parent;
167         if (!y.parent)
168             this._root = x;
169         else {
170             if (y == y.parent.left)
171                 y.parent.left = x;
172             else
173                 y.parent.right = x;
174         }
175         
176         if (y != z) {
177             if (y.color == "black")
178                 this._removeFixup(x, xParent);
179             
180             y.parent = z.parent;
181             y.color = z.color;
182             y.left = z.left;
183             y.right = z.right;
184             
185             if (z.left)
186                 z.left.parent = y;
187             if (z.right)
188                 z.right.parent = y;
189             if (z.parent) {
190                 if (z.parent.left == z)
191                     z.parent.left = y;
192                 else
193                     z.parent.right = y;
194             } else
195                 this._root = y;
196         } else if (y.color == "black")
197             this._removeFixup(x, xParent);
198         
199         return z.value;
200     };
201     
202     RedBlackTree.prototype.get = function(key) {
203         var node = this._findNode(key);
204         if (!node)
205             return null;
206         return node.value;
207     };
208     
209     RedBlackTree.prototype.forEach = function(callback) {
210         if (!this._root)
211             return;
212         for (var current = treeMinimum(this._root); current; current = current.successor())
213             callback(current.key, current.value);
214     };
215     
216     RedBlackTree.prototype.asArray = function() {
217         var result = [];
218         this.forEach(function(key, value) {
219             result.push({key: key, value: value});
220         });
221         return result;
222     };
223     
224     RedBlackTree.prototype.toString = function() {
225         var result = "[";
226         var first = true;
227         this.forEach(function(key, value) {
228             if (first)
229                 first = false;
230             else
231                 result += ", ";
232             result += key + "=>" + value;
233         });
234         return result + "]";
235     };
236     
237     RedBlackTree.prototype._findNode = function(key) {
238         for (var current = this._root; current;) {
239             var comparisonResult = compare(key, current.key);
240             if (!comparisonResult)
241                 return current;
242             if (comparisonResult < 0)
243                 current = current.left;
244             else
245                 current = current.right;
246         }
247         return null;
248     };
249     
250     RedBlackTree.prototype._treeInsert = function(key, value) {
251         var y = null;
252         var x = this._root;
253         while (x) {
254             y = x;
255             var comparisonResult = key.compareTo(x.key);
256             if (comparisonResult < 0)
257                 x = x.left;
258             else if (comparisonResult > 0)
259                 x = x.right;
260             else {
261                 var oldValue = x.value;
262                 x.value = value;
263                 return {isNewEntry:false, oldValue:oldValue};
264             }
265         }
266         var z = new Node(key, value);
267         z.parent = y;
268         if (!y)
269             this._root = z;
270         else {
271             if (key.compareTo(y.key) < 0)
272                 y.left = z;
273             else
274                 y.right = z;
275         }
276         return {isNewEntry:true, newNode:z};
277     };
278     
279     RedBlackTree.prototype._leftRotate = function(x) {
280         var y = x.right;
281         
282         // Turn y's left subtree into x's right subtree.
283         x.right = y.left;
284         if (y.left)
285             y.left.parent = x;
286         
287         // Link x's parent to y.
288         y.parent = x.parent;
289         if (!x.parent)
290             this._root = y;
291         else {
292             if (x == x.parent.left)
293                 x.parent.left = y;
294             else
295                 x.parent.right = y;
296         }
297         
298         // Put x on y's left.
299         y.left = x;
300         x.parent = y;
301         
302         return y;
303     };
304     
305     RedBlackTree.prototype._rightRotate = function(y) {
306         var x = y.left;
307         
308         // Turn x's right subtree into y's left subtree.
309         y.left = x.right;
310         if (x.right)
311             x.right.parent = y;
312         
313         // Link y's parent to x;
314         x.parent = y.parent;
315         if (!y.parent)
316             this._root = x;
317         else {
318             if (y == y.parent.left)
319                 y.parent.left = x;
320             else
321                 y.parent.right = x;
322         }
323         
324         x.right = y;
325         y.parent = x;
326         
327         return x;
328     };
329     
330     RedBlackTree.prototype._removeFixup = function(x, xParent) {
331         while (x != this._root && (!x || x.color == "black")) {
332             if (x == xParent.left) {
333                 // Note: the text points out that w cannot be null. The reason is not obvious from
334                 // simply looking at the code; it comes about from the properties of the red-black
335                 // tree.
336                 var w = xParent.right;
337                 if (w.color == "red") {
338                     // Case 1
339                     w.color = "black";
340                     xParent.color = "red";
341                     this._leftRotate(xParent);
342                     w = xParent.right;
343                 }
344                 if ((!w.left || w.left.color == "black")
345                     && (!w.right || w.right.color == "black")) {
346                     // Case 2
347                     w.color = "red";
348                     x = xParent;
349                     xParent = x.parent;
350                 } else {
351                     if (!w.right || w.right.color == "black") {
352                         // Case 3
353                         w.left.color = "black";
354                         w.color = "red";
355                         this._rightRotate(w);
356                         w = xParent.right;
357                     }
358                     // Case 4
359                     w.color = xParent.color;
360                     xParent.color = "black";
361                     if (w.right)
362                         w.right.color = "black";
363                     this._leftRotate(xParent);
364                     x = this._root;
365                     xParent = x.parent;
366                 }
367             } else {
368                 // Same as "then" clause with "right" and "left" exchanged.
369                 
370                 var w = xParent.left;
371                 if (w.color == "red") {
372                     // Case 1
373                     w.color = "black";
374                     xParent.color = "red";
375                     this._rightRotate(xParent);
376                     w = xParent.left;
377                 }
378                 if ((!w.right || w.right.color == "black")
379                     && (!w.left || w.left.color == "black")) {
380                     // Case 2
381                     w.color = "red";
382                     x = xParent;
383                     xParent = x.parent;
384                 } else {
385                     if (!w.left || w.left.color == "black") {
386                         // Case 3
387                         w.right.color = "black";
388                         w.color = "red";
389                         this._leftRotate(w);
390                         w = xParent.left;
391                     }
392                     // Case 4
393                     w.color = xParent.color;
394                     xParent.color = "black";
395                     if (w.left)
396                         w.left.color = "black";
397                     this._rightRotate(xParent);
398                     x = this._root;
399                     xParent = x.parent;
400                 }
401             }
402         }
403         if (x)
404             x.color = "black";
405     };
406     
407     return RedBlackTree;
408 })();
409