• file
• revisions
• annotate
• diff
• comparison
• raw

toolkit/modules/tests/xpcshell/test_BinarySearch.js@6474c204b198 (annotated)

toolkit/modules/tests/xpcshell/test_BinarySearch.js

Wed, 31 Dec 2014 06:09:35 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Wed, 31 Dec 2014 06:09:35 +0100

changeset 0

6474c204b198

permissions

-rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

michael@0	1	/* Any copyright is dedicated to the Public Domain.
michael@0	2	* http://creativecommons.org/publicdomain/zero/1.0/ */
michael@0	3
michael@0	4	Components.utils.import("resource://gre/modules/BinarySearch.jsm");
michael@0	5
michael@0	6	function run_test() {
michael@0	7	// empty array
michael@0	8	ok([], 1, false, 0);
michael@0	9
michael@0	10	// one-element array
michael@0	11	ok([2], 2, true, 0);
michael@0	12	ok([2], 1, false, 0);
michael@0	13	ok([2], 3, false, 1);
michael@0	14
michael@0	15	// two-element array
michael@0	16	ok([2, 4], 2, true, 0);
michael@0	17	ok([2, 4], 4, true, 1);
michael@0	18	ok([2, 4], 1, false, 0);
michael@0	19	ok([2, 4], 3, false, 1);
michael@0	20	ok([2, 4], 5, false, 2);
michael@0	21
michael@0	22	// three-element array
michael@0	23	ok([2, 4, 6], 2, true, 0);
michael@0	24	ok([2, 4, 6], 4, true, 1);
michael@0	25	ok([2, 4, 6], 6, true, 2);
michael@0	26	ok([2, 4, 6], 1, false, 0);
michael@0	27	ok([2, 4, 6], 3, false, 1);
michael@0	28	ok([2, 4, 6], 5, false, 2);
michael@0	29	ok([2, 4, 6], 7, false, 3);
michael@0	30
michael@0	31	// duplicates
michael@0	32	ok([2, 2], 2, true, 0);
michael@0	33	ok([2, 2], 1, false, 0);
michael@0	34	ok([2, 2], 3, false, 2);
michael@0	35
michael@0	36	// duplicates on the left
michael@0	37	ok([2, 2, 4], 2, true, 1);
michael@0	38	ok([2, 2, 4], 4, true, 2);
michael@0	39	ok([2, 2, 4], 1, false, 0);
michael@0	40	ok([2, 2, 4], 3, false, 2);
michael@0	41	ok([2, 2, 4], 5, false, 3);
michael@0	42
michael@0	43	// duplicates on the right
michael@0	44	ok([2, 4, 4], 2, true, 0);
michael@0	45	ok([2, 4, 4], 4, true, 1);
michael@0	46	ok([2, 4, 4], 1, false, 0);
michael@0	47	ok([2, 4, 4], 3, false, 1);
michael@0	48	ok([2, 4, 4], 5, false, 3);
michael@0	49
michael@0	50	// duplicates in the middle
michael@0	51	ok([2, 4, 4, 6], 2, true, 0);
michael@0	52	ok([2, 4, 4, 6], 4, true, 1);
michael@0	53	ok([2, 4, 4, 6], 6, true, 3);
michael@0	54	ok([2, 4, 4, 6], 1, false, 0);
michael@0	55	ok([2, 4, 4, 6], 3, false, 1);
michael@0	56	ok([2, 4, 4, 6], 5, false, 3);
michael@0	57	ok([2, 4, 4, 6], 7, false, 4);
michael@0	58
michael@0	59	// duplicates all around
michael@0	60	ok([2, 2, 4, 4, 6, 6], 2, true, 0);
michael@0	61	ok([2, 2, 4, 4, 6, 6], 4, true, 2);
michael@0	62	ok([2, 2, 4, 4, 6, 6], 6, true, 4);
michael@0	63	ok([2, 2, 4, 4, 6, 6], 1, false, 0);
michael@0	64	ok([2, 2, 4, 4, 6, 6], 3, false, 2);
michael@0	65	ok([2, 2, 4, 4, 6, 6], 5, false, 4);
michael@0	66	ok([2, 2, 4, 4, 6, 6], 7, false, 6);
michael@0	67	}
michael@0	68
michael@0	69	function ok(array, target, expectedFound, expectedIdx) {
michael@0	70	let [found, idx] = BinarySearch.search(array, target, cmp);
michael@0	71	do_check_eq(found, expectedFound);
michael@0	72	do_check_eq(idx, expectedIdx);
michael@0	73
michael@0	74	idx = expectedFound ? expectedIdx : -1;
michael@0	75	do_check_eq(BinarySearch.indexOf(array, target, cmp), idx);
michael@0	76	do_check_eq(BinarySearch.insertionIndexOf(array, target, cmp), expectedIdx);
michael@0	77	}
michael@0	78
michael@0	79	function cmp(num1, num2) {
michael@0	80	return num1 - num2;
michael@0	81	}