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