Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(994)

Side by Side Diff: webkit/data/test_shell/sort/sort-heap.js

Issue 401923005: webkit: Remove all files from test_shell/. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
1 // heapsort
2
3 function sort_heap(sort, end) {
4 if (arguments.length == 1) {
5 var mid = Math.floor(sort.size/2 - 1);
6 sort.add_work(function() { build_heap(sort, mid); }, "build_heap");
7 } else if (end > 0) {
8 sort.swap(end, 0);
9 end--;
10 sort.add_work(function() { sort_heap(sort, end); }, "sort_heap");
11 sort.add_work(function() { sift_down(sort, 0, end, 0); }, "sift_down");
12 }
13 }
14
15 function build_heap(sort, start) {
16 if (start >= 0) {
17 sort.add_work(function() { build_heap(sort, start-1); }, "build_heap");
18 sort.add_work(function() { sift_down(sort, start, sort.size-1, start); },
19 "sift_down");
20 } else {
21 sort.add_work(function() { sort_heap(sort, sort.size-1); },
22 "sort_heap");
23 }
24 }
25
26 function sift_down(sort, start, end, root) {
27 var child = root * 2 + 1;
28 if (child <= end) {
29 if (child < end && sort.compare(child, child + 1) < 0) {
30 child++;
31 }
32 if (sort.compare(root, child) < 0) {
33 sort.swap(root, child);
34 root = child;
35 sort.add_work(function() { sift_down(sort, start, end, root); },
36 "sift_down");
37 }
38 }
39 }
40
41 function validate_heap(sort) {
42 var i = Math.floor(sort.size/2 - 1);
43 while (i >= 0) {
44 child = i * 2 + 1;
45 if (sort.compare(i, child) < 0)
46 return 0;
47 if (child + 1 < sort.size)
48 if (sort.compare(i, child + 1) < 0)
49 return 0;
50 i--;
51 }
52 return 1;
53 }
OLDNEW
« no previous file with comments | « webkit/data/test_shell/sort/sort-bubble.js ('k') | webkit/data/test_shell/sort/sort-insertion.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698