// Speed tests done on the tailopt-js.xhtml page.
// Guillaume Lathoud, 2010
//
// These tests work on several browsers (Firefox 3.6, Safari 4.04,
// Google Chrome 3.0, IE8), as well as under Rhino and Google V8:
//
// rhino -e "load('tailopt-js-rerun.js');rerun(null,10);"
//
// d8 -e "load('tailopt-js-rerun.js');rerun(null,10);"
//
/*jslint evil:true */
(function (/*global context object*/global) {
// Mainly for Rhino and Google V8
if (global.load) { global.load("tailopt.js"); }
if (global.load) { global.load("tailcatch.js"); }
if (global.load) { global.load("tailtramp.js"); }
var queue,
setTimeout = global.setTimeout || function (f) {
(queue = queue || []).push(f);
};
//
var a, sanity, BUTTON_NAME = "rerun_button",
list = (global.list = []);
// The unavoidable:
var is_not_IE = !((global.navigator && global.navigator.appVersion && parseFloat(global.navigator.appVersion.split("MSIE ")[1])) || false);
function log() {
var f;
if ((f = global.console && global.console.log) && f && f.apply) {
// Mainly for browsers
f.apply(global.console, arguments);
} else if ((!global.document) && (f = global.print) && f && f.apply) {
// Mainly for Rhino and Google V8
f.apply(global, ["[LOG]"].concat(Array.prototype.slice.apply(arguments)));
}
}
function error() {
var f;
if ((f = global.console && global.console.log) && f && f.apply) {
// Mainly for browsers
f.apply(global.console, arguments);
} else if ((!global.document) && (f = global.print) && f && f.apply) {
// Mainly for Rhino and Google V8
f.apply(global, ["[ERROR]"].concat(Array.prototype.slice.apply(arguments)));
}
}
function alert(s) {
var f;
if (global.alert) {
// Mainly for browsers
global.alert(s);
} else if (!global.document) {
// Mainly for Rhino and Google V8
(f = global.print) && f && f.call && f.call(global, "[ALERT] " + s);
}
}
function assert(/*boolean*/result, /*string*/message) {
if (global.console && global.console.assert) {
global.console.assert(result, message);
return;
}
if (! result) {
alert('assert() failure: ' + message);
}
}
// https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference/Objects/Array/IndexOf
if (!Array.prototype.indexOf)
{
Array.prototype.indexOf = function(elt /*, from*/)
{
var len = this.length >>> 0;
var from = Number(arguments[1]) || 0;
from = (from < 0)
? Math.ceil(from)
: Math.floor(from);
if (from < 0)
from += len;
for (; from < len; from++)
{
if (from in this &&
this[from] === elt)
return from;
}
return -1;
};
}
function string_fill( /*string*/s, /*string*/filler, /*number*/width, /*?boolean?*/left ) {
s = s + '';
for (var a = s.length; a < width; a++) {
s = left ? (filler + s) : (s + filler);
}
return s;
}
function byId(id) { return global.document && global.document.getElementById(id); }
function now() { return (new Date()).getTime(); }
function nb_prec(n, prec) { return (new Number(n)).toExponential(prec || 3); }
function all_nodes() {
var ret = global.document && global.document.getElementsByTagName('*');
if (ret && ret.length) { return ret; }
ret = [];
DOMtreeforeach_tailopt && DOMtreeforeach_tailopt(global.document, function (node) { ret.push(node); });
return ret;
}
function mixin(/*Object*/dest, /*Object*/src) {
// Simplistic, but enough for what we need here
for (var a in src) {
dest[a] = src[a];
}
return dest;
}
function stat(/*Array of numbers*/arr) {
var sum = 0, sumsq = 0, a, n = arr.length, ret, tmp, x;
for (a = 0; a < n; a++) {
sum += arr[a];
sumsq += (arr[a] * arr[a]);
}
ret = {
sum: sum,
sumsq: sumsq,
mean: sum / n
};
// For the variance we redo the loop, to reduce imprecision,
// also not:
// ret.variance = sumsq / n - ret.mean * ret.mean;
// but instead:
tmp = 0;
for (a = 0; a < n; a++) {
x = arr[a] - ret.mean;
tmp += x * x;
}
ret.variance = tmp / n;
ret.std = Math.sqrt( ret.variance );
return ret;
}
function get_by_class(class_name) {
if (!global.document) { return []; }
var a, b, c, arr = all_nodes(), ret = [];
for (a = 0; a < arr.length; a++) {
b = arr[a].className.split(' ');
for (c = 0; c < b.length; c++) {
if (b[c] === class_name) {
ret.push(arr[a]);
break;
}
}
}
return ret;
}
function write_to_many(target_name, what, how) {
var a,
arr = get_by_class(target_name),
amax = arr.length;
for (a = 0; a < amax; a++) {
how(arr[a], what);
}
}
function set_rerun_button(/*boolean*/ enabled) {
var a, arr = get_by_class(BUTTON_NAME);
for (a = 0; a < arr.length; a++) {
arr[a].disabled = enabled ? undefined : "disabled";
}
}
global.get_by_class = get_by_class;
// Asynchronous implementation of all duration tests, to avoid blocking the browser.
set_rerun_button(true);
global.rerun = function (/*?number | array of strings | string?*/subset, /*?number?*/nrunmin, /*?number?*/nruntoforget) {
if (typeof subset === 'number') {
return global.rerun.apply(global, [null].concat(Array.prototype.slice.apply(arguments)));
}
subset = (typeof subset === 'string') ? [subset] : subset;
log("rerun() started, subset:", subset, ", nrunmin:", nrunmin, ", nruntoforget:", nruntoforget, ", global.runs:", global.runs);
set_rerun_button(false);
global.result = global.result || {};
global.runs = global.runs || 0;
global.result_string = "";
if (global.document) { for (var a in list) { list[a].write_result('*'); } }
log("rerun() started, subset:", subset, " -> calling next_later()");
next_later(0, subset, nrunmin, nruntoforget);
// Fake support for setTimeout (mainly for Rhino and Google V8)
while (queue && queue.length) {
queue.shift()();
}
};
function next_later(n, /*?array of strings?*/subset, /*?number?*/nrunmin, /*?number?*/nruntoforget) {
// Let the browser breath a bit
setTimeout(function () {
if (subset) {
for (; (n < list.length) && (subset.indexOf( list[n].name ) < 0); n++) { }
}
next(n, subset, nrunmin, nruntoforget);
}, 2000); // A long pause to finish the DOM effect of the write_result()
}
function next(n, /*?array of strings?*/subset, /*?number?*/nrunmin, /*?number?*/nruntoforget) {
nrunmin = Math.max(1, nrunmin || 3);
nruntoforget = Math.max(0, (typeof nruntoforget === 'number') ? nruntoforget : 10);
if (n > list.length - 1) {
global.runs++;
// Make sure to have meaningful results
// -> run multiple times
if (global.runs < nrunmin) {
global.rerun(subset, nrunmin, nruntoforget);
return;
}
set_rerun_button(true);
print_additional_info();
log("next(): all tests done.");
alert("All tests done.");
return;
}
var a, x = list[n], test = x.test, start, end, total_sec, iter_sec,
r = global.result && global.result[x.name],
niter, s_rel, basename, o, o_new, s, s_stat;
if (r && r.niter) {
// Target a fixed test duration (e.g. 1 second),
// to make the test conditions as equal as possible.
//
// (This requires to have run the tests already once.)
if (r.total_sec > 0) {
niter = r.niter * ((is_not_IE ? 1.0 : 0.1) / r.total_sec );
} else {
niter = 1e3 * r.niter;
}
} else {
if (!global.document) { niter = 10; } // Rhino and Google V8
}
start = now();
niter = x.test(niter);
end = now();
total_sec = (end - start) / 1000;
iter_sec = total_sec / niter;
// Save the results
global.result[x.name] = global.result[x.name] || {fun : x.fun};
o_new = {
niter : niter,
total_sec : total_sec,
iter_sec : iter_sec,
runs : (global.result[x.name].runs || 0) + 1
};
o = mixin(global.result[x.name], o_new);
// Save the results (for example for std dev computation)
if (o.runs > nruntoforget) {
o.history = o.history || {};
for (var a in o_new) {
(o.history[a] = o.history[a] || []).push(o_new[a]);
if (typeof o_new[a] === 'number') {
o.stat = o.stat || {};
var toto = stat(o.history[a]);
o.stat[a] = toto;
}
}
}
// Try to compare to the base (base=recursive implementation)
s_rel = '';
basename = list[n].name.substr(0, list[n].name.lastIndexOf('_')) + '_rec';
if ((list[n].name === basename) || (global.result[basename] && global.result[basename].iter_sec)) {
s_rel = (list[n].name === basename)
? '(100: base)'
: ('(' + Math.round(100 * iter_sec / global.result[basename].iter_sec) + ')');
}
// Try to access stats (stddev etc.)
s_stat = "";
if (o.stat) {
s_stat = " [mean:" + nb_prec(o.stat.iter_sec.mean) +
", std:" + nb_prec(o.stat.iter_sec.std) + ", ratio:" +
nb_prec(o.stat.iter_sec.std / o.stat.iter_sec.mean) +
"]";
}
// Write out
s = "next(): test #" + string_fill( n, ' ', 2 ) + " -> niter: " + nb_prec(niter) +
", total_sec: " + nb_prec(total_sec) + " -> " + string_fill(list[n].name, '_', 25) + " iter_sec: " + nb_prec(iter_sec) +
" " + string_fill(s_rel,' ',11) + s_stat;
log(s);
global.result_string += s + '\n';
x.write_result(nb_prec(iter_sec) + " s");
// Let the browser breath a bit
next_later(n + 1, subset, nrunmin, nruntoforget);
}
// ---------- Toy example ----------
function fact_rec(n) {
return n > 1 ? n * fact_rec(n - 1) : 1;
}
list.push({
name: "fact_rec",
fun: fact_rec,
sanity: function () {
var s;
s = "fact_rec(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rec(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rec(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rec(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rec(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rec(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 2e5 : 2e4);
for (a = 0; a < amax; a++) {
fact_rec(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_rec_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_rec_result", " (100: base)", function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var fact_rectailcatch = global.tailcatch( function (n) {
return n > 1 ? n * fact_rectailcatch(n - 1) : 1;
});
list.push({
name: "fact_rectailcatch",
fun: fact_rectailcatch,
sanity: function () {
var s;
s = "fact_rectailcatch(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailcatch(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailcatch(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailcatch(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailcatch(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailcatch(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e2 : 1e1);
for (a = 0; a < amax; a++) {
fact_rectailcatch(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_rectailcatch_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_rectailcatch_result", " (" + Math.round(100 * (global.result.fact_rectailcatch.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var fact_rectailtramp = global.tailtramp( function (n) {
return n > 1 ? n * fact_rectailtramp(n - 1) : 1;
});
list.push({
name: "fact_rectailtramp",
fun: fact_rectailtramp,
sanity: function () {
var s;
s = "fact_rectailtramp(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailtramp(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailtramp(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailtramp(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailtramp(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_rectailtramp(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e3 : 1e2);
for (a = 0; a < amax; a++) {
fact_rectailtramp(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_rectailtramp_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_rectailtramp_result", " (" + Math.round(100 * (global.result.fact_rectailtramp.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
// Javascript implementation similar to the following Scheme:
//
// (define (fact n)
// (let fact_sub ((p n) (tmp 1))
// (if (< p 2)
// tmp
// (fact_sub (- p 1) (* p tmp))))
//
// More concise implementation in fact_tail2() (further below):
// return p ? fact_sub(p - 1, p * tmp) : tmp;
// (same performance).
function fact_tail(n) {
return (function fact_sub(p, tmp) {
if (p) {
return fact_sub(p - 1, p * tmp);
}
return tmp;
})(n, 1);
}
list.push({
name: "fact_tail",
fun: fact_tail,
sanity: function () {
var s;
s = "fact_tail(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 4e4 : 4e3);
for (a = 0; a < amax; a++) {
fact_tail(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_tail_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_tail_result", " (" + Math.round(100 * (global.result.fact_tail.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
// Javascript implementation similar to the following Scheme:
//
// (define (fact n)
// (let fact_sub ((p n) (tmp 1))
// (if (< p 2)
// tmp
// (fact_sub (- p 1) (* p tmp))))
//
function fact_tail2(n) {
return (function fact_sub(p, tmp) {
return p ? fact_sub(p - 1, p * tmp) : tmp;
})(n, 1);
}
list.push({
name: "fact_tail2",
fun: fact_tail2,
sanity: function () {
var s;
s = "fact_tail2(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail2(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail2(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail2(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail2(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tail2(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 4e4 : 4e3);
for (a = 0; a < amax; a++) {
fact_tail2(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_tail2_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_tail2_result", " (" + Math.round(100 * (global.result.fact_tail2.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// Javascript implementation similar to the following Scheme:
//
// (define (fact n)
// (let fact_sub ((p n) (tmp 1))
// (if (< p 2)
// tmp
// (fact_sub (- p 1) (* p tmp))))
//
// Tailcall optimization through tailcatch()
var fact_tailcatch = (function () {
var fact_sub = global.tailcatch( function (p, tmp) {
return p ? fact_sub(p - 1, p * tmp) : tmp;
});
return function (n) { return fact_sub(n, 1); }
})();
list.push({
name: "fact_tailcatch",
fun: fact_tailcatch,
sanity: function () {
var s;
s = "fact_tailcatch(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailcatch(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailcatch(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailcatch(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailcatch(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailcatch(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e2 : 1e1);
for (a = 0; a < amax; a++) {
fact_tailcatch(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_tailcatch_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_tailcatch_result", " (" + Math.round(100 * (global.result.fact_tailcatch.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// Javascript implementation similar to the following Scheme:
//
// (define (fact n)
// (let fact_sub ((p n) (tmp 1))
// (if (< p 2)
// tmp
// (fact_sub (- p 1) (* p tmp))))
//
// Tailcall optimization through tailtramp()
var fact_tailtramp = (function () {
var fact_sub = global.tailtramp( function (p, tmp) {
return p ? fact_sub(p - 1, p * tmp) : tmp;
});
return function (n) { return fact_sub(n, 1); }
})();
list.push({
name: "fact_tailtramp",
fun: fact_tailtramp,
sanity: function () {
var s;
s = "fact_tailtramp(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailtramp(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailtramp(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailtramp(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailtramp(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailtramp(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e3 : 1e2);
for (a = 0; a < amax; a++) {
fact_tailtramp(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_tailtramp_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_tailtramp_result", " (" + Math.round(100 * (global.result.fact_tailtramp.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var fact_tailopt = global.tailopt(fact_tail);
list.push({
name: "fact_tailopt",
fun: fact_tailopt,
sanity: function () {
var s;
s = "fact_tailopt(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 4e5: 4e4);
for (a = 0; a < amax; a++) {
fact_tailopt(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_tailopt_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_tailopt_result",
" (" + Math.round(100 * (global.result.fact_tailopt.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var fact_tailopt2 = global.tailopt(fact_tail2);
list.push({
name: "fact_tailopt2",
fun: fact_tailopt2,
sanity: function () {
var s;
s = "fact_tailopt2(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt2(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt2(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt2(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt2(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_tailopt2(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 4e5: 4e4);
for (a = 0; a < amax; a++) {
fact_tailopt2(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_tailopt2_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_tailopt2_result",
" (" + Math.round(100 * (global.result.fact_tailopt2.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
function fact_iter(n) {
var a, ret = 1;
for (a = 2; a <= n; a++) {
ret = ret * a;
}
return ret;
}
list.push({
name: "fact_iter",
fun: fact_iter,
sanity: function () {
var s;
s = "fact_iter(0) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_iter(1) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_iter(2) === 2"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_iter(3) === 6"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_iter(5) === 120"; assert(eval(s), "Failed sanity check: " + s);
s = "fact_iter(6) === 720"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 4e5 : 4e4);
for (a = 0; a < amax; a++) {
fact_iter(13);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("fact_iter_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("fact_iter_result", " (" + Math.round(100 * (global.result.fact_iter.iter_sec / global.result.fact_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// Greatest Common Divisor (GCD) Example
// Inspired by http://www.refactoring.com/catalog/replaceIterationWithRecursion.html
function gcd_rec(a, b) {
if (a > b) {
return gcd_rec(a-b, b);
} else if (a < b) {
return gcd_rec(a, b-a);
}
// a === b
return a;
}
list.push({
name: "gcd_rec",
fun: gcd_rec,
sanity: function () {
var s;
s = "gcd_rec(17, 13) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "gcd_rec(2*3*3*5*7*11*37*113, 2*2*2*3*5*5*11*47) === 2*3*5*11"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e4: 1e3);
for (a = 0; a < amax; a++) {
gcd_rec(28974330, 310200);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("gcd_rec_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("gcd_rec_result",
" (100: base)",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var gcd_rectailcatch = global.tailcatch( function (a, b) {
if (a > b) {
return gcd_rectailcatch(a-b, b);
} else if (a < b) {
return gcd_rectailcatch(a, b-a);
}
// a === b
return a;
});
list.push({
name: "gcd_rectailcatch",
fun: gcd_rectailcatch,
sanity: function () {
var s;
s = "gcd_rectailcatch(17, 13) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "gcd_rectailcatch(2*3*3*5*7*11*37*113, 2*2*2*3*5*5*11*47) === 2*3*5*11"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e1: 1e0);
for (a = 0; a < amax; a++) {
gcd_rectailcatch(28974330, 310200);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("gcd_rectailcatch_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("gcd_rectailcatch_result",
" (" + Math.round(100 * (global.result.gcd_rectailcatch.iter_sec / global.result.gcd_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var gcd_rectailtramp = global.tailtramp( function (a, b) {
if (a > b) {
return gcd_rectailtramp(a-b, b);
} else if (a < b) {
return gcd_rectailtramp(a, b-a);
}
// a === b
return a;
});
list.push({
name: "gcd_rectailtramp",
fun: gcd_rectailtramp,
sanity: function () {
var s;
s = "gcd_rectailtramp(17, 13) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "gcd_rectailtramp(2*3*3*5*7*11*37*113, 2*2*2*3*5*5*11*47) === 2*3*5*11"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e2: 1e1);
for (a = 0; a < amax; a++) {
gcd_rectailtramp(28974330, 310200);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("gcd_rectailtramp_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("gcd_rectailtramp_result",
" (" + Math.round(100 * (global.result.gcd_rectailtramp.iter_sec / global.result.gcd_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var gcd_tailopt = tailopt(gcd_rec);
list.push({
name: "gcd_tailopt",
fun: gcd_tailopt,
sanity: function () {
var s;
s = "gcd_tailopt(17, 13) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "gcd_tailopt(2*3*3*5*7*11*37*113, 2*2*2*3*5*5*11*47) === 2*3*5*11"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e4: 1e3);
for (a = 0; a < amax; a++) {
gcd_tailopt(28974330, 310200);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("gcd_tailopt_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("gcd_tailopt_result",
" (" + Math.round(100 * (global.result.gcd_tailopt.iter_sec / global.result.gcd_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
function gcd_iter(a, b) {
while (true) {
if (a > b) {
a -= b;
} else if (b > a) {
b -= a;
} else {
break;
}
}
return a;
}
list.push({
name: "gcd_iter",
fun: gcd_iter,
sanity: function () {
var s;
s = "gcd_iter(17, 13) === 1"; assert(eval(s), "Failed sanity check: " + s);
s = "gcd_iter(2*3*3*5*7*11*37*113, 2*2*2*3*5*5*11*47) === 2*3*5*11"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 5e4: 5e3);
for (a = 0; a < amax; a++) {
gcd_iter(28974330, 310200);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("gcd_iter_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("gcd_iter_result",
" (" + Math.round(100 * (global.result.gcd_iter.iter_sec / global.result.gcd_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// String replication: first work on arrays, then do a join('') at
// the end. Reason: concatenating strings directly leads to
// memory usage explosion in some Javascript environments.
function string_repli_rec(s, n) {
if (!((n > 0) && s)) { return ''; }
return (function sub(s, n) {
if (n < 1) { return ['']; }
if (n === 1) { return [s]; }
var half = Math.floor(n / 2), a = sub(s, half);
return a.concat(a, sub(s, n - 2 * half));
})(s, n).join('');
}
list.push({
name: "string_repli_rec",
fun: string_repli_rec,
sanity: function () {
var s;
s = "string_repli_rec('abc', 0) === ''"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_rec('abc', 1) === 'abc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_rec('abc', 2) === 'abcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_rec('abc', 5) === 'abcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_rec('abc', 6) === 'abcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_rec('abc', 7) === 'abcabcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 5e3: 5e2);
for (a = 0; a < amax; a++) {
string_repli_rec('abc', 123);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("string_repli_rec_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("string_repli_rec_result",
" (100: base)",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// String replication: first work on arrays, then do a join('') at
// the end. Reason: concatenating strings directly leads to
// memory usage explosion in some Javascript environments.
function string_repli_tail(s0, n0){
if (!((n0 > 0) && s0)) { return ''; }
return (function sub(s, n, tmp){
if (n & 1) { tmp.push(s); }
return n ? sub(s + s, n >> 1, tmp) : tmp.join('');
})(s0, n0, []);
}
list.push({
name: "string_repli_tail",
fun: string_repli_tail,
sanity: function () {
var s;
s = "string_repli_tail('abc', 0) === ''"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tail('abc', 1) === 'abc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tail('abc', 2) === 'abcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tail('abc', 5) === 'abcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tail('abc', 6) === 'abcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tail('abc', 7) === 'abcabcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 5e3: 5e2);
for (a = 0; a < amax; a++) {
string_repli_tail('abc', 123);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("string_repli_tail_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("string_repli_tail_result",
" (" + Math.round(100 * (global.result.string_repli_tail.iter_sec / global.result.string_repli_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var string_repli_tailopt = tailopt( string_repli_tail );
list.push({
name: "string_repli_tailopt",
fun: string_repli_tailopt,
sanity: function () {
var s;
s = "string_repli_tailopt('abc', 0) === ''"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tailopt('abc', 1) === 'abc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tailopt('abc', 2) === 'abcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tailopt('abc', 5) === 'abcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tailopt('abc', 6) === 'abcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_tailopt('abc', 7) === 'abcabcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 5e3: 5e2);
for (a = 0; a < amax; a++) {
string_repli_tailopt('abc', 123);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("string_repli_tailopt_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("string_repli_tailopt_result",
" (" + Math.round(100 * (global.result.string_repli_tailopt.iter_sec / global.result.string_repli_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
// from dojo 1.4.1 http://svn.dojotoolkit.org/src/dojo/trunk/string.js
// as of 2010-02-28
function string_repli_iter(str, num){
if(num <= 0 || !str){ return ''; }
var buf = [];
for(;;){
if(num & 1){
buf.push(str);
}
if(!(num >>= 1)){ break; }
str += str;
}
return buf.join('');
}
list.push({
name: "string_repli_iter",
fun: string_repli_iter,
sanity: function () {
var s;
s = "string_repli_iter('abc', 0) === ''"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_iter('abc', 1) === 'abc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_iter('abc', 2) === 'abcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_iter('abc', 5) === 'abcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_iter('abc', 6) === 'abcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
s = "string_repli_iter('abc', 7) === 'abcabcabcabcabcabcabc'"; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 5e3: 5e2);
for (a = 0; a < amax; a++) {
string_repli_iter('abc', 123);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("string_repli_iter_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("string_repli_iter_result",
" (" + Math.round(100 * (global.result.string_repli_iter.iter_sec / global.result.string_repli_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// Tree traversal example
var tree = {"12040":{"name":"skiFreeride","parent":"12240","children":[],"nextSibling":"12090"},"12090":{"name":"sledging","parent":"12240","children":[],"nextSibling":"12130"},"12130":{"name":"winterHiking","parent":"12240","children":[],"nextSibling":"12010"},"12010":{"name":"skitour","parent":"12240","children":[],"nextSibling":"12100"},"12100":{"name":"snowshoehiking","parent":"12240","children":[],"nextSibling":"5610"},"5610":{"name":"skitrailCrosscountry","parent":"12240","children":[]},"12320":{"name":"trailRunning","parent":"12310","children":[],"nextSibling":"13000"},"13000":{"name":"nordicwalkingTrail","parent":"12310","children":[],"nextSibling":"12150"},"12150":{"name":"running","parent":"12310","children":[],"nextSibling":"12080"},"12080":{"name":"inlineSkating","parent":"12310","children":[]},"12000":{"name":"hikingTourTrail","parent":"12160","children":[],"nextSibling":"12400"},"12400":{"name":"longDistanceHikingTrail","parent":"12160","children":[],"nextSibling":"12410"},"12410":{"name":"pilgrimTrack","parent":"12160","children":[],"nextSibling":"12200"},"12200":{"name":"themeTrail","parent":"12160","children":[]},"12060":{"name":"mountainbiking","parent":"12230","children":[],"nextSibling":"12020"},"12020":{"name":"transalpMountainbiking","parent":"12230","children":[],"nextSibling":"12070"},"12070":{"name":"racingBike","parent":"12230","children":[],"nextSibling":"12030"},"12030":{"name":"cycling","parent":"12230","children":[]},"12220":{"name":"cityTrail","parent":"12600","children":[]},"12510":{"name":"alpineTour","parent":"12500","children":[],"nextSibling":"12120"},"12120":{"name":"viaferrata","parent":"12500","children":[],"nextSibling":"12050"},"12050":{"name":"mountaineering","parent":"12500","children":[]},"12280":{"name":"canyoning","parent":"12270","children":[],"nextSibling":"12300"},"12300":{"name":"waterHiking","parent":"12270","children":[]},"12370":{"name":"carriageRideTour","parent":"12350","children":[],"nextSibling":"12360"},"12360":{"name":"horsebackRidingTour","parent":"12350","children":[]},"12240":{"name":"winter","children":["12040","12090","12130","12010","12100","5610"],"parent":"4000","firstChild":"12040","nextSibling":"12310"},"12310":{"name":"walking","children":["12320","13000","12150","12080"],"parent":"4000","firstChild":"12320","nextSibling":"12160"},"12160":{"name":"hikingTour","children":["12000","12400","12410","12200"],"parent":"4000","firstChild":"12000","nextSibling":"12230"},"12230":{"name":"cycleTour","children":["12060","12020","12070","12030"],"parent":"4000","firstChild":"12060","nextSibling":"12600"},"12600":{"name":"cityTour","children":["12220"],"parent":"4000","firstChild":"12220","nextSibling":"12500"},"12500":{"name":"mountains","children":["12510","12120","12050"],"parent":"4000","firstChild":"12510","nextSibling":"12270"},"12270":{"name":"water","children":["12280","12300"],"parent":"4000","firstChild":"12280","nextSibling":"12350"},"12350":{"name":"horses","children":["12370","12360"],"parent":"4000","firstChild":"12370"},"13320":{"name":"apartment","parent":"2510","children":[],"nextSibling":"10011168"},"10011168":{"name":"recreationHome","parent":"2510","children":[],"nextSibling":"10011169"},"10011169":{"name":"motel","parent":"2510","children":[],"nextSibling":"10011142"},"10011142":{"name":"privateRoom","parent":"2510","children":[],"nextSibling":"10011141"},"10011141":{"name":"holidayHouse","parent":"2510","children":[],"nextSibling":"13230"},"13230":{"name":"guesthouse","parent":"2510","children":[],"nextSibling":"10011162"},"10011162":{"name":"horsebackRidingHof","parent":"2510","children":[],"nextSibling":"10011161"},"10011161":{"name":"farm","parent":"2510","children":[],"nextSibling":"10011167"},"10011167":{"name":"caravanLot","parent":"2510","children":[],"nextSibling":"13090"},"13090":{"name":"holidayFlat","parent":"2510","children":[],"nextSibling":"10011166"},"10011166":{"name":"camping","parent":"2510","children":[],"nextSibling":"2520"},"2520":{"name":"hotel","parent":"2510","children":[],"nextSibling":"10011165"},"10011165":{"name":"youthHostel","parent":"2510","children":[],"nextSibling":"13040"},"13040":{"name":"mountainCottage","parent":"2510","children":[],"nextSibling":"10011152"},"10011152":{"name":"innSeasonal","parent":"2510","children":[],"nextSibling":"13160"},"13160":{"name":"lodge","parent":"2510","children":[],"nextSibling":"13130"},"13130":{"name":"inn","parent":"2510","children":[]},"10012501":{"name":"circus","parent":"10012500","children":[],"nextSibling":"10012502"},"10012502":{"name":"excursion","parent":"10012500","children":[],"nextSibling":"10012512"},"10012512":{"name":"sportingEvent","parent":"10012500","children":[],"nextSibling":"10012513"},"10012513":{"name":"meetingPoint","parent":"10012500","children":[],"nextSibling":"10012509"},"10012509":{"name":"culture","parent":"10012500","children":[],"nextSibling":"10012508"},"10012508":{"name":"folklore","parent":"10012500","children":[],"nextSibling":"10012511"},"10012511":{"name":"cabaret","parent":"10012500","children":[],"nextSibling":"10012510"},"10012510":{"name":"reading","parent":"10012500","children":[],"nextSibling":"10012505"},"10012505":{"name":"dissertation","parent":"10012500","children":[],"nextSibling":"10012504"},"10012504":{"name":"concert","parent":"10012500","children":[]},"10011605":{"name":"paragliding","parent":"10011600","children":[],"nextSibling":"10011606"},"10011606":{"name":"shootingSports","parent":"10011600","children":[],"nextSibling":"10011607"},"10011607":{"name":"iceSports","parent":"10011600","children":[],"nextSibling":"10011601"},"10011601":{"name":"stadion","parent":"10011600","children":[],"nextSibling":"10011602"},"10011602":{"name":"sportsField","parent":"10011600","children":[],"nextSibling":"10011603"},"10011603":{"name":"climbing","parent":"10011600","children":[],"nextSibling":"10011612"},"10011612":{"name":"tennis","parent":"10011600","children":[],"nextSibling":"10011614"},"10011614":{"name":"golfCourse","parent":"10011600","children":[],"nextSibling":"10011615"},"10011615":{"name":"horsebackRidingPoi","parent":"10011600","children":[],"nextSibling":"10011608"},"10011608":{"name":"football","parent":"10011600","children":[],"nextSibling":"10011611"},"10011611":{"name":"beachVolleyball","parent":"10011600","children":[],"nextSibling":"10011620"},"10011620":{"name":"skijump","parent":"10011600","children":[],"nextSibling":"10011619"},"10011619":{"name":"motocross","parent":"10011600","children":[],"nextSibling":"10011617"},"10011617":{"name":"bmx","parent":"10011600","children":[]},"10011301":{"name":"medic","parent":"10011300","children":[],"nextSibling":"10011303"},"10011303":{"name":"hospital","parent":"10011300","children":[],"nextSibling":"10011302"},"10011302":{"name":"pharmacy","parent":"10011300","children":[],"nextSibling":"10011305"},"10011305":{"name":"rehabilitationClinic","parent":"10011300","children":[],"nextSibling":"10011304"},"10011304":{"name":"foresightClinic","parent":"10011300","children":[],"nextSibling":"10011307"},"10011307":{"name":"curInstitute","parent":"10011300","children":[],"nextSibling":"10011306"},"10011306":{"name":"sanatorium","parent":"10011300","children":[]},"10012302":{"name":"panorama","parent":"10012300","children":[],"nextSibling":"10012304"},"10012304":{"name":"audio","parent":"10012300","children":[],"nextSibling":"13100"},"13100":{"name":"photoLocation","parent":"10012300","children":[]},"10012202":{"name":"lookout","parent":"10012200","children":[],"nextSibling":"10012204"},"10012204":{"name":"pass","parent":"10012200","children":[],"nextSibling":"10012205"},"10012205":{"name":"cave","parent":"10012200","children":[],"nextSibling":"10012206"},"10012206":{"name":"mine","parent":"10012200","children":[],"nextSibling":"10012207"},"10012207":{"name":"canyon","parent":"10012200","children":[],"nextSibling":"10012209"},"10012209":{"name":"swamp","parent":"10012200","children":[],"nextSibling":"10012211"},"10012211":{"name":"naturalMonument","parent":"10012200","children":[],"nextSibling":"10012210"},"10012210":{"name":"biotope","parent":"10012200","children":[],"nextSibling":"10012213"},"10012213":{"name":"glacier","parent":"10012200","children":[],"nextSibling":"10012212"},"10012212":{"name":"naturalPark","parent":"10012200","children":[],"nextSibling":"10012215"},"10012215":{"name":"fauna","parent":"10012200","children":[],"nextSibling":"10012214"},"10012214":{"name":"forest","parent":"10012200","children":[],"nextSibling":"10012217"},"10012217":{"name":"barbecueArea","parent":"10012200","children":[],"nextSibling":"10012216"},"10012216":{"name":"flora","parent":"10012200","children":[],"nextSibling":"13010"},"13010":{"name":"viewpoint","parent":"10012200","children":[],"nextSibling":"10012219"},"10012219":{"name":"alpClosed","parent":"10012200","children":[],"nextSibling":"10012218"},"10012218":{"name":"forestersHouse","parent":"10012200","children":[],"nextSibling":"10012221"},"10012221":{"name":"mill","parent":"10012200","children":[],"nextSibling":"10012220"},"10012220":{"name":"observatory","parent":"10012200","children":[],"nextSibling":"10012223"},"10012223":{"name":"bridge","parent":"10012200","children":[],"nextSibling":"10012222"},"10012222":{"name":"smithy","parent":"10012200","children":[],"nextSibling":"10012503"},"10012503":{"name":"guidedTourPoi","parent":"10012200","children":[],"nextSibling":"10012228"},"10012228":{"name":"estate","parent":"10012200","children":[],"nextSibling":"10012229"},"10012229":{"name":"island","parent":"10012200","children":[],"nextSibling":"13310"},"13310":{"name":"waterfall","parent":"10012200","children":[],"nextSibling":"10012227"},"10012227":{"name":"geotope","parent":"10012200","children":[],"nextSibling":"10012224"},"10012224":{"name":"footbridge","parent":"10012200","children":[],"nextSibling":"10012225"},"10012225":{"name":"spring","parent":"10012200","children":[],"nextSibling":"13030"},"13030":{"name":"mountainTop","parent":"10012200","children":[]},"13170":{"name":"snackBar","parent":"10011200","children":[],"nextSibling":"10011212"},"10011212":{"name":"publicHouseSeasonal","parent":"10011200","children":[],"nextSibling":"13140"},"13140":{"name":"publicHouse","parent":"10011200","children":[],"nextSibling":"13240"},"13240":{"name":"restaurant","parent":"10011200","children":[],"nextSibling":"10011236"},"10011236":{"name":"cheeseDiary","parent":"10011200","children":[],"nextSibling":"10011237"},"10011237":{"name":"wineTavern","parent":"10011200","children":[],"nextSibling":"13080"},"13080":{"name":"coffeeHouse","parent":"10011200","children":[],"nextSibling":"10011232"},"10011232":{"name":"bar","parent":"10011200","children":[],"nextSibling":"10011233"},"10011233":{"name":"nightLife","parent":"10011200","children":[],"nextSibling":"10011234"},"10011234":{"name":"vinotheque","parent":"10011200","children":[],"nextSibling":"10011235"},"10011235":{"name":"winery","parent":"10011200","children":[],"nextSibling":"10011231"},"10011231":{"name":"brewery","parent":"10011200","children":[],"nextSibling":"10011230"},"10011230":{"name":"beerGarden","parent":"10011200","children":[],"nextSibling":"10011229"},"10011229":{"name":"alpOpened","parent":"10011200","children":[],"nextSibling":"10011227"},"10011227":{"name":"mountainInn","parent":"10011200","children":[],"nextSibling":"10011225"},"10011225":{"name":"tavern","parent":"10011200","children":[],"nextSibling":"10011224"},"10011224":{"name":"pizzeria","parent":"10011200","children":[],"nextSibling":"10011223"},"10011223":{"name":"pub","parent":"10011200","children":[],"nextSibling":"10011222"},"10011222":{"name":"bistro","parent":"10011200","children":[]},"10011417":{"name":"waysideShrine","parent":"10011400","children":[],"nextSibling":"10011416"},"10011416":{"name":"monument","parent":"10011400","children":[],"nextSibling":"10011419"},"10011419":{"name":"multiPurposeHall","parent":"10011400","children":[],"nextSibling":"10011418"},"10011418":{"name":"library","parent":"10011400","children":[],"nextSibling":"10011421"},"10011421":{"name":"waysideCross","parent":"10011400","children":[],"nextSibling":"10011420"},"10011420":{"name":"clubHouse","parent":"10011400","children":[],"nextSibling":"10011422"},"10011422":{"name":"cemetery","parent":"10011400","children":[],"nextSibling":"10011408"},"10011408":{"name":"historicPlace","parent":"10011400","children":[],"nextSibling":"10011411"},"10011411":{"name":"religiousInstitute","parent":"10011400","children":[],"nextSibling":"10011412"},"10011412":{"name":"monastery","parent":"10011400","children":[],"nextSibling":"13200"},"13200":{"name":"church","parent":"10011400","children":[],"nextSibling":"10011415"},"10011415":{"name":"ruin","parent":"10011400","children":[],"nextSibling":"10011401"},"10011401":{"name":"theater","parent":"10011400","children":[],"nextSibling":"13060"},"13060":{"name":"fortress","parent":"10011400","children":[],"nextSibling":"10011402"},"10011402":{"name":"opera","parent":"10011400","children":[],"nextSibling":"10011403"},"10011403":{"name":"museum","parent":"10011400","children":[],"nextSibling":"10011404"},"10011404":{"name":"gallery","parent":"10011400","children":[],"nextSibling":"10011405"},"10011405":{"name":"fair","parent":"10011400","children":[],"nextSibling":"10011406"},"10011406":{"name":"openAirTheater","parent":"10011400","children":[],"nextSibling":"10011407"},"10011407":{"name":"archaeologicalPlace","parent":"10011400","children":[],"nextSibling":"13190"},"13190":{"name":"chapel","parent":"10011400","children":[],"nextSibling":"13250"},"13250":{"name":"castle","parent":"10011400","children":[]},"10011714":{"name":"ferry","parent":"10011700","children":[],"nextSibling":"13110"},"13110":{"name":"outdoorSwimmingPool","parent":"10011700","children":[],"nextSibling":"10011715"},"10011715":{"name":"fishing","parent":"10011700","children":[],"nextSibling":"10011712"},"10011712":{"name":"yachtHarbour","parent":"10011700","children":[],"nextSibling":"10011713"},"10011713":{"name":"navy","parent":"10011700","children":[],"nextSibling":"10011716"},"10011716":{"name":"pond","parent":"10011700","children":[],"nextSibling":"13150"},"13150":{"name":"indoorSwimmingPool","parent":"10011700","children":[],"nextSibling":"13290"},"13290":{"name":"hotSprings","parent":"10011700","children":[],"nextSibling":"10011701"},"10011701":{"name":"lake","parent":"10011700","children":[],"nextSibling":"10011703"},"10011703":{"name":"coastalSwimmingPool","parent":"10011700","children":[],"nextSibling":"13050"},"13050":{"name":"boatHire","parent":"10011700","children":[],"nextSibling":"10011702"},"10011702":{"name":"fount","parent":"10011700","children":[],"nextSibling":"10011709"},"10011709":{"name":"waterSports","parent":"10011700","children":[],"nextSibling":"10011708"},"10011708":{"name":"treadWater","parent":"10011700","children":[],"nextSibling":"10011710"},"10011710":{"name":"diving","parent":"10011700","children":[],"nextSibling":"10011704"},"10011704":{"name":"holidaySwimmingPool","parent":"10011700","children":[]},"10011519":{"name":"gardenRailway","parent":"10011500","children":[],"nextSibling":"10011518"},"10011518":{"name":"gocart","parent":"10011500","children":[],"nextSibling":"10011517"},"10011517":{"name":"youthClub","parent":"10011500","children":[],"nextSibling":"10011516"},"10011516":{"name":"carriageRidePoi","parent":"10011500","children":[],"nextSibling":"10011514"},"10011514":{"name":"regeneration","parent":"10011500","children":[],"nextSibling":"10011513"},"10011513":{"name":"casino","parent":"10011500","children":[],"nextSibling":"13210"},"13210":{"name":"miniatureGolfCourse","parent":"10011500","children":[],"nextSibling":"10011512"},"10011512":{"name":"pedestrianZone","parent":"10011500","children":[],"nextSibling":"10011511"},"10011511":{"name":"cinema","parent":"10011500","children":[],"nextSibling":"10011509"},"10011509":{"name":"amusementPark","parent":"10011500","children":[],"nextSibling":"10011508"},"10011508":{"name":"fitness","parent":"10011500","children":[],"nextSibling":"10011507"},"10011507":{"name":"wellness","parent":"10011500","children":[],"nextSibling":"10011506"},"10011506":{"name":"sauna","parent":"10011500","children":[],"nextSibling":"13300"},"13300":{"name":"zoo","parent":"10011500","children":[],"nextSibling":"13270"},"13270":{"name":"playground","parent":"10011500","children":[],"nextSibling":"10011504"},"10011504":{"name":"geocachingPoi","parent":"10011500","children":[],"nextSibling":"10011502"},"10011502":{"name":"bowling","parent":"10011500","children":[],"nextSibling":"10011520"},"10011520":{"name":"museumRailway","parent":"10011500","children":[],"nextSibling":"13260"},"13260":{"name":"dryLudgeRunPoi","parent":"10011500","children":[]},"10012019":{"name":"bikeRental","parent":"10012000","children":[],"nextSibling":"10012018"},"10012018":{"name":"toilet","parent":"10012000","children":[],"nextSibling":"13180"},"13180":{"name":"helpDesk","parent":"10012000","children":[],"nextSibling":"13120"},"13120":{"name":"guestOffice","parent":"10012000","children":[],"nextSibling":"10012003"},"10012003":{"name":"cureHouse","parent":"10012000","children":[],"nextSibling":"10012006"},"10012006":{"name":"citizensAdviceBureau","parent":"10012000","children":[],"nextSibling":"10012007"},"10012007":{"name":"police","parent":"10012000","children":[],"nextSibling":"10012004"},"10012004":{"name":"districtOffice","parent":"10012000","children":[],"nextSibling":"10012005"},"10012005":{"name":"cityHall","parent":"10012000","children":[],"nextSibling":"10012010"},"10012010":{"name":"bank","parent":"10012000","children":[],"nextSibling":"10012011"},"10012011":{"name":"post","parent":"10012000","children":[],"nextSibling":"10012008"},"10012008":{"name":"school","parent":"10012000","children":[],"nextSibling":"10012009"},"10012009":{"name":"kindergarten","parent":"10012000","children":[],"nextSibling":"10012015"},"10012015":{"name":"petrolStation","parent":"10012000","children":[],"nextSibling":"10012012"},"10012012":{"name":"haircutter","parent":"10012000","children":[],"nextSibling":"10012013"},"10012013":{"name":"handcraft","parent":"10012000","children":[]},"10011806":{"name":"fashion","parent":"10011800","children":[],"nextSibling":"10011805"},"10011805":{"name":"store","parent":"10011800","children":[],"nextSibling":"10011802"},"10011802":{"name":"eatables","parent":"10011800","children":[],"nextSibling":"10011803"},"10011803":{"name":"souvenirs","parent":"10011800","children":[],"nextSibling":"10011801"},"10011801":{"name":"market","parent":"10011800","children":[],"nextSibling":"13280"},"13280":{"name":"sportsOutfitters","parent":"10011800","children":[],"nextSibling":"10011808"},"10011808":{"name":"mediaKiosk","parent":"10011800","children":[]},"10012113":{"name":"busParkingLot","parent":"10012100","children":[],"nextSibling":"10012114"},"10012114":{"name":"harbour","parent":"10012100","children":[],"nextSibling":"10012115"},"10012115":{"name":"landingStage","parent":"10012100","children":[],"nextSibling":"10012116"},"10012116":{"name":"inclineBase","parent":"10012100","children":[],"nextSibling":"10012117"},"10012117":{"name":"inclineTop","parent":"10012100","children":[],"nextSibling":"10012105"},"10012105":{"name":"uStation","parent":"10012100","children":[],"nextSibling":"10012104"},"10012104":{"name":"sStation","parent":"10012100","children":[],"nextSibling":"10012106"},"10012106":{"name":"tramStation","parent":"10012100","children":[],"nextSibling":"10012109"},"10012109":{"name":"parkingGarage","parent":"10012100","children":[],"nextSibling":"10012111"},"10012111":{"name":"taxi","parent":"10012100","children":[],"nextSibling":"13020"},"13020":{"name":"station","parent":"10012100","children":[],"nextSibling":"10012110"},"10012110":{"name":"restingPlace","parent":"10012100","children":[],"nextSibling":"13220"},"13220":{"name":"parkingLot","parent":"10012100","children":[],"nextSibling":"13070"},"13070":{"name":"busStop","parent":"10012100","children":[],"nextSibling":"10012101"},"10012101":{"name":"airport","parent":"10012100","children":[],"nextSibling":"10012102"},"10012102":{"name":"airfield","parent":"10012100","children":[]},"2510":{"name":"lodging","children":["13320","10011168","10011169","10011142","10011141","13230","10011162","10011161","10011167","13090","10011166","2520","10011165","13040","10011152","13160","13130"],"parent":"3500","firstChild":"13320","nextSibling":"10012500"},"10012500":{"name":"event","children":["10012501","10012502","10012512","10012513","10012509","10012508","10012511","10012510","10012505","10012504"],"parent":"3500","firstChild":"10012501","nextSibling":"10011600"},"10011600":{"name":"sports","children":["10011605","10011606","10011607","10011601","10011602","10011603","10011612","10011614","10011615","10011608","10011611","10011620","10011619","10011617"],"parent":"3500","firstChild":"10011605","nextSibling":"10011300"},"10011300":{"name":"health","children":["10011301","10011303","10011302","10011305","10011304","10011307","10011306"],"parent":"3500","firstChild":"10011301","nextSibling":"10012300"},"10012300":{"name":"media","children":["10012302","10012304","13100"],"parent":"3500","firstChild":"10012302","nextSibling":"10012200"},"10012200":{"name":"landmarks","children":["10012202","10012204","10012205","10012206","10012207","10012209","10012211","10012210","10012213","10012212","10012215","10012214","10012217","10012216","13010","10012219","10012218","10012221","10012220","10012223","10012222","10012503","10012228","10012229","13310","10012227","10012224","10012225","13030"],"parent":"3500","firstChild":"10012202","nextSibling":"10011200"},"10011200":{"name":"catering","children":["13170","10011212","13140","13240","10011236","10011237","13080","10011232","10011233","10011234","10011235","10011231","10011230","10011229","10011227","10011225","10011224","10011223","10011222"],"parent":"3500","firstChild":"13170","nextSibling":"10011400"},"10011400":{"name":"artCulture","children":["10011417","10011416","10011419","10011418","10011421","10011420","10011422","10011408","10011411","10011412","13200","10011415","10011401","13060","10011402","10011403","10011404","10011405","10011406","10011407","13190","13250"],"parent":"3500","firstChild":"10011417","nextSibling":"10011700"},"10011700":{"name":"waterAttractions","children":["10011714","13110","10011715","10011712","10011713","10011716","13150","13290","10011701","10011703","13050","10011702","10011709","10011708","10011710","10011704"],"parent":"3500","firstChild":"10011714","nextSibling":"10011500"},"10011500":{"name":"freetime","children":["10011519","10011518","10011517","10011516","10011514","10011513","13210","10011512","10011511","10011509","10011508","10011507","10011506","13300","13270","10011504","10011502","10011520","13260"],"parent":"3500","firstChild":"10011519","nextSibling":"10012000"},"10012000":{"name":"services","children":["10012019","10012018","13180","13120","10012003","10012006","10012007","10012004","10012005","10012010","10012011","10012008","10012009","10012015","10012012","10012013"],"parent":"3500","firstChild":"10012019","nextSibling":"10011800"},"10011800":{"name":"shopping","children":["10011806","10011805","10011802","10011803","10011801","13280","10011808"],"parent":"3500","firstChild":"10011806","nextSibling":"10012100"},"10012100":{"name":"traffics","children":["10012113","10012114","10012115","10012116","10012117","10012105","10012104","10012106","10012109","10012111","13020","10012110","13220","13070","10012101","10012102"],"parent":"3500","firstChild":"10012113"},"4000":{"name":"tour","children":["12240","12310","12160","12230","12600","12500","12270","12350"],"parent":"3000","firstChild":"12240","nextSibling":"3500"},"3500":{"name":"poi","children":["2510","10012500","10011600","10011300","10012300","10012200","10011200","10011400","10011700","10011500","10012000","10011800","10012100"],"parent":"3000","firstChild":"2510"},"3000":{"name":"ooi","children":["4000","3500"],"firstChild":"4000"}};
var count = {"12000":779,"13010":271,"10011415":37,"10012202":7,"13240":45,"13140":168,"13220":322,"10012102":2,"10011417":4,"10011408":56,"10012217":13,"10011802":2,"13100":220,"13190":142,"13070":91,"10011701":135,"13130":120,"13200":198,"10012225":13,"13030":176,"10012205":19,"10011421":8,"10012227":13,"10011407":4,"10011161":40,"10011514":10,"10012005":13,"10012216":54,"10011403":44,"10012211":30,"13160":125,"10012212":13,"10012503":49,"13250":50,"10012302":9,"12060":335,"2520":48,"13080":45,"13020":52,"13060":20,"10011162":9,"10011152":3,"12400":2,"10012223":121,"10011412":29,"10011507":2,"10012502":4,"12030":120,"13310":33,"10012228":3,"10011512":4,"12150":42,"10011602":13,"10012509":14,"13110":44,"10012114":3,"10012207":29,"13180":82,"10012214":17,"10011166":25,"10011703":26,"13260":6,"10011231":17,"10012013":3,"10011702":7,"10011416":30,"10012221":19,"10011615":3,"10011404":2,"13290":4,"13170":7,"10011704":7,"10011714":1,"10012229":2,"13150":9,"10012209":29,"13000":198,"13300":9,"13050":6,"10012210":28,"10012206":2,"3500":193,"13210":7,"10011716":8,"10011236":9,"12080":2,"10011513":2,"10012215":8,"10012110":27,"12410":1,"12020":32,"10011307":8,"10011227":57,"10012219":159,"10011608":4,"12070":17,"10012003":3,"10011801":9,"10011411":6,"10012508":4,"12130":157,"5610":144,"13270":28,"10011708":6,"10011614":9,"12090":156,"12100":46,"13040":95,"10011229":137,"10011603":8,"10012117":41,"10099999":4,"10012116":54,"10012512":1,"13280":3,"10012019":3,"12320":3,"12220":4,"10011422":3,"10011302":1,"13120":6,"10012008":1,"10012109":2,"12370":2,"12010":46,"10011303":7,"10012204":22,"12050":24,"12040":3,"10012218":13,"12120":20,"13230":4,"10011601":8,"10011607":2,"10011418":1,"10011620":3,"10011212":1,"10011808":1,"10011709":1,"10011712":3,"10011401":3,"10011715":1,"10012220":1,"10011306":1,"10011509":1,"10012200":2,"10011508":3,"12280":2,"10012213":1,"10011713":11,"12510":1,"10012104":9,"12200":28,"10011805":1,"10012105":2,"10011230":4,"10011612":4,"10011419":1,"10011234":1,"10011803":3,"10012018":1,"10011617":1,"10011222":3,"10011225":1,"10011301":2,"10011165":1,"10011606":1,"10011710":2,"10011168":1};
function count_cat(catid, tfe) {
var ret = 0;
function f(tree, catid) {
if (count[catid] !== undefined) { ret += count[catid]; }
}
tfe(tree, catid, f, false);
return ret;
}
//
function treeforeach_rec(tree, node_id, fun) {
// Execute fun on all nodes of the subtree tree[node_id]
var a, b, node = tree[node_id];
// Breadth
fun(tree, node_id);
// Depth
for (b = 0; b < node.children.length; b++) {
treeforeach_rec(tree, node.children[b], fun);
}
}
list.push({
name: "treeforeach_rec",
fun: treeforeach_rec,
sanity: function () {
var s;
s = 'count_cat("3000", treeforeach_rec) === 6514'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("3500", treeforeach_rec) === 4350'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12160", treeforeach_rec) === 810'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12040", treeforeach_rec) === 3'; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e3 : 1e2);
for (a = 0; a < amax; a++) {
count_cat("3000", treeforeach_rec);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("tfe_rec_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("tfe_rec_result",
" (100: base)",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
function treeforeach_tail(tree, node_id, fun) {
// Execute fun on all nodes of the subtree tree[node_id]
return (function sub(_tree, _node_id, _fun, _from_below) {
var _node = _tree[_node_id];
if (! _from_below) { // _fun is called one and only one time per node
_fun(_tree, _node_id);
if (_node.firstChild) return sub(_tree, _node.firstChild, _fun, false);
}
if (_node_id === node_id) return; // Done
if (_node.nextSibling) return sub(_tree, _node.nextSibling, _fun, false);
if (_node.parent) return sub(_tree, _node.parent, _fun, true);
return;
})(tree, node_id, fun, false);
}
list.push({
name: "treeforeach_tail",
fun: treeforeach_tail,
sanity: function () {
var s;
s = 'count_cat("3000", treeforeach_tail) === 6514'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("3500", treeforeach_tail) === 4350'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12160", treeforeach_tail) === 810'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12040", treeforeach_tail) === 3'; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e3 : 1e2);
for (a = 0; a < amax; a++) {
count_cat("3000", treeforeach_tail);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("tfe_tail_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("tfe_tail_result",
" (" + Math.round(100 * (global.result.treeforeach_tail.iter_sec / global.result.treeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var treeforeach_tailcatch = (function () {
// Execute fun on all nodes of the subtree tree[node_id]
var sub = global.tailcatch( function (_tree, _node_id, _fun, _from_below, topnode_id) {
var _node = _tree[_node_id];
if (! _from_below) { // _fun is called one and only one time per node
_fun(_tree, _node_id);
if (_node.firstChild) return sub(_tree, _node.firstChild, _fun, false, topnode_id);
}
if (_node_id === topnode_id) return; // Done
if (_node.nextSibling) return sub(_tree, _node.nextSibling, _fun, false, topnode_id);
if (_node.parent) return sub(_tree, _node.parent, _fun, true, topnode_id);
return;
});
return function (tree, node_id, fun) { return sub(tree, node_id, fun, false, node_id); }
})();
list.push({
name: "treeforeach_tailcatch",
fun: treeforeach_tailcatch,
sanity: function () {
var s;
s = 'count_cat("3000", treeforeach_tailcatch) === 6514'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("3500", treeforeach_tailcatch) === 4350'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12160", treeforeach_tailcatch) === 810'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12040", treeforeach_tailcatch) === 3'; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e0 : 1e0);
for (a = 0; a < amax; a++) {
count_cat("3000", treeforeach_tailcatch);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("tfe_tailcatch_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("tfe_tailcatch_result",
" (" + Math.round(100 * (global.result.treeforeach_tailcatch.iter_sec / global.result.treeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var treeforeach_tailtramp = (function () {
// Execute fun on all nodes of the subtree tree[node_id]
var sub = global.tailtramp( function (_tree, _node_id, _fun, _from_below, topnode_id) {
var _node = _tree[_node_id];
if (! _from_below) { // _fun is called one and only one time per node
_fun(_tree, _node_id);
if (_node.firstChild) return sub(_tree, _node.firstChild, _fun, false, topnode_id);
}
if (_node_id === topnode_id) return; // Done
if (_node.nextSibling) return sub(_tree, _node.nextSibling, _fun, false, topnode_id);
if (_node.parent) return sub(_tree, _node.parent, _fun, true, topnode_id);
return;
});
return function (tree, node_id, fun) { return sub(tree, node_id, fun, false, node_id); }
})();
list.push({
name: "treeforeach_tailtramp",
fun: treeforeach_tailtramp,
sanity: function () {
var s;
s = 'count_cat("3000", treeforeach_tailtramp) === 6514'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("3500", treeforeach_tailtramp) === 4350'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12160", treeforeach_tailtramp) === 810'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12040", treeforeach_tailtramp) === 3'; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e1 : 1e0);
for (a = 0; a < amax; a++) {
count_cat("3000", treeforeach_tailtramp);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("tfe_tailtramp_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("tfe_tailtramp_result",
" (" + Math.round(100 * (global.result.treeforeach_tailtramp.iter_sec / global.result.treeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var treeforeach_tailopt = global.tailopt(treeforeach_tail);
list.push({
name: "treeforeach_tailopt",
fun: treeforeach_tailopt,
sanity: function () {
var s;
s = 'count_cat("3000", treeforeach_tailopt) === 6514'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("3500", treeforeach_tailopt) === 4350'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12160", treeforeach_tailopt) === 810'; assert(eval(s), "Failed sanity check: " + s);
s = 'count_cat("12040", treeforeach_tailopt) === 3'; assert(eval(s), "Failed sanity check: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e3 : 1e2);
for (a = 0; a < amax; a++) {
count_cat("3000", treeforeach_tailopt);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("tfe_tailopt_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("tfe_tailopt_result",
" (" + Math.round(100 * (global.result.treeforeach_tailopt.iter_sec / global.result.treeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// DOM tree traversal example
var node_list = [];
function node_check(node) {
var s = (node.nodeName === '#text') && (node[is_not_IE ? 'textContent' : 'nodeValue'] || node.data || node.nodeValue); // node.data and node.nodeValue for ugly IE
if (s && (s.indexOf('.js') > -1)) {
node_list.push(node);
}
}
//
function DOMtreeforeach_rec(node, fun) {
fun(node);
var a, c = node.childNodes;
for (a = 0; a < c.length; a++) {
DOMtreeforeach_rec(c[a], fun);
}
}
global.document && list.push({
name: "DOMtreeforeach_rec",
fun: DOMtreeforeach_rec,
sanity: function () {
var s;
// Check that no exception gets thrown
node_list = [];
DOMtreeforeach_rec(global.document, node_check);
// Check that something is found
s = "node_list && (typeof node_list.length === 'number') && (node_list.length > 3)";
assert(eval(s), "Failed sanity check for DOMtreeforeach_rec: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e2 : 1e1);
for (a = 0; a < amax; a++) {
node_list = [];
DOMtreeforeach_rec(global.document, node_check);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("domtfe_rec_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("domtfe_rec_result",
" (100: base)",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
function DOMtreeforeach_tail(node, fun) {
return (function sub(_node, _fun, _from_below) {
if (! _from_below) { // _fun is called one and only one time per node
_fun(_node);
if (_node.firstChild) return sub(_node.firstChild, _fun, false);
}
if (_node.nextSibling) return sub(_node.nextSibling, _fun, false);
if (_node.parentNode) return sub(_node.parentNode, _fun, true);
return;
})(node, fun, false);
}
global.document && list.push({
name: "DOMtreeforeach_tail",
fun: DOMtreeforeach_tail,
sanity: function () {
var s;
// Check that no exception gets thrown
node_list = [];
DOMtreeforeach_tail(global.document, node_check);
// Check that something is found
s = "node_list && (typeof node_list.length === 'number') && (node_list.length > 3)";
assert(eval(s), "Failed sanity check for DOMtreeforeach_tail: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e2 : 1e1);
for (a = 0; a < amax; a++) {
node_list = [];
DOMtreeforeach_tail(global.document, node_check);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("domtfe_tail_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("domtfe_tail_result",
" (" + Math.round(100 * (global.result.DOMtreeforeach_tail.iter_sec / global.result.DOMtreeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
DOMtreeforeach_tailcatch = (function(){
var sub = global.tailcatch( function sub(_node, _fun, _from_below) {
if (! _from_below) { // _fun is called one and only one time per node
_fun(_node);
if (_node.firstChild) return sub(_node.firstChild, _fun, false);
}
if (_node.nextSibling) return sub(_node.nextSibling, _fun, false);
if (_node.parentNode) return sub(_node.parentNode, _fun, true);
return;
});
return function(node, fun) { return sub(node, fun, false); };
})();
global.document && list.push({
name: "DOMtreeforeach_tailcatch",
fun: DOMtreeforeach_tailcatch,
sanity: function () {
var s;
// Check that no exception gets thrown
node_list = [];
DOMtreeforeach_tailcatch(global.document, node_check);
// Check that something is found
s = "node_list && (typeof node_list.length === 'number') && (node_list.length > 3)";
assert(eval(s), "Failed sanity check for DOMtreeforeach_tailcatch: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e1 : 1e0);
for (a = 0; a < amax; a++) {
node_list = [];
DOMtreeforeach_tailcatch(global.document, node_check);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("domtfe_tailcatch_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("domtfe_tailcatch_result",
" (" + Math.round(100 * (global.result.DOMtreeforeach_tailcatch.iter_sec / global.result.DOMtreeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
DOMtreeforeach_tailtramp = (function(){
var sub = global.tailtramp( function sub(_node, _fun, _from_below) {
if (! _from_below) { // _fun is called one and only one time per node
_fun(_node);
if (_node.firstChild) return sub(_node.firstChild, _fun, false);
}
if (_node.nextSibling) return sub(_node.nextSibling, _fun, false);
if (_node.parentNode) return sub(_node.parentNode, _fun, true);
return;
});
return function(node, fun) { return sub(node, fun, false); };
})();
global.document && list.push({
name: "DOMtreeforeach_tailtramp",
fun: DOMtreeforeach_tailtramp,
sanity: function () {
var s;
// Check that no exception gets thrown
node_list = [];
DOMtreeforeach_tailtramp(global.document, node_check);
// Check that something is found
s = "node_list && (typeof node_list.length === 'number') && (node_list.length > 3)";
assert(eval(s), "Failed sanity check for DOMtreeforeach_tailtramp: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e1 : 1e0);
for (a = 0; a < amax; a++) {
node_list = [];
DOMtreeforeach_tailtramp(global.document, node_check);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("domtfe_tailtramp_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("domtfe_tailtramp_result",
" (" + Math.round(100 * (global.result.DOMtreeforeach_tailtramp.iter_sec / global.result.DOMtreeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
//
var DOMtreeforeach_tailopt = global.tailopt(DOMtreeforeach_tail);
global.document && list.push({
name: "DOMtreeforeach_tailopt",
fun: DOMtreeforeach_tailopt,
sanity: function () {
var s;
// Check that no exception gets thrown
node_list = [];
DOMtreeforeach_tailopt(global.document, node_check);
// Check that something is found
s = "node_list && (typeof node_list.length === 'number') && (node_list.length > 3)";
assert(eval(s), "Failed sanity check for DOMtreeforeach_tailopt: " + s);
},
test: function (/*?number?*/ niter) {
var a, amax = niter || (is_not_IE ? 1e3 : 1e2);
for (a = 0; a < amax; a++) {
node_list = [];
DOMtreeforeach_tailopt(global.document, node_check);
}
return a;
},
write_result: function (iter_sec) {
global.document && write_to_many("domtfe_tailopt_result", iter_sec, function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] = s); });
},
write_result_relative: function () {
global.document && write_to_many("domtfe_tailopt_result",
" (" + Math.round(100 * (global.result.DOMtreeforeach_tailopt.iter_sec / global.result.DOMtreeforeach_rec.iter_sec)) + ")",
function (x, s) { x && x.firstChild && (x.firstChild[is_not_IE ? 'textContent' : 'nodeValue'] += s); });
}
});
// ---------- Print additional info about the current DOM, for the DOM traversal tests
function print_additional_info() {
if (!global.document) { return; }
var dom_nb_nodes, a;
dom_nb_nodes = all_nodes().length;
write_to_many('dom_nb_nodes', dom_nb_nodes, function (x, s) { x[is_not_IE ? 'textContent' : 'nodeValue'] = s; });
// Here is a good example where recursive is better:
// - used only once.
// - simpler implementation.
var dom_max_depth = 0;
function f_rec(node, depth) {
dom_max_depth = Math.max(dom_max_depth, depth);
var a, c = node.childNodes;
for (a = 0; a < c.length; a++) {
f_rec(c[a], depth+1);
}
}
f_rec(global.document, 1);
write_to_many('dom_max_depth', dom_max_depth, function (x, s) { x[is_not_IE ? 'textContent' : 'nodeValue'] = s; });
// Also add relative results
for (a = 0; a < list.length; a++) {
if (list[a].write_result_relative && result[list[a].name]) {
list[a].write_result_relative();
}
}
}
// ---------- Run sanity checks
for (a = 0; a < list.length; a++) {
sanity = list[a].sanity;
if (!sanity) {
continue;
}
try {
sanity();
} catch(e) {
assert(false, 'Failed sanity check for a: ' + a + ', caught e:' + e);
}
}
log('All sanity checks done.')
})(/*global context object*/this);