The Tor Browser / file diff

     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/toolkit/modules/tests/xpcshell/test_BinarySearch.js	Wed Dec 31 06:09:35 2014 +0100
     1.3 @@ -0,0 +1,81 @@
     1.4 +/* Any copyright is dedicated to the Public Domain.
     1.5 + * http://creativecommons.org/publicdomain/zero/1.0/ */
     1.6 +
     1.7 +Components.utils.import("resource://gre/modules/BinarySearch.jsm");
     1.8 +
     1.9 +function run_test() {
    1.10 +  // empty array
    1.11 +  ok([], 1, false, 0);
    1.12 +
    1.13 +  // one-element array
    1.14 +  ok([2], 2, true, 0);
    1.15 +  ok([2], 1, false, 0);
    1.16 +  ok([2], 3, false, 1);
    1.17 +
    1.18 +  // two-element array
    1.19 +  ok([2, 4], 2, true, 0);
    1.20 +  ok([2, 4], 4, true, 1);
    1.21 +  ok([2, 4], 1, false, 0);
    1.22 +  ok([2, 4], 3, false, 1);
    1.23 +  ok([2, 4], 5, false, 2);
    1.24 +
    1.25 +  // three-element array
    1.26 +  ok([2, 4, 6], 2, true, 0);
    1.27 +  ok([2, 4, 6], 4, true, 1);
    1.28 +  ok([2, 4, 6], 6, true, 2);
    1.29 +  ok([2, 4, 6], 1, false, 0);
    1.30 +  ok([2, 4, 6], 3, false, 1);
    1.31 +  ok([2, 4, 6], 5, false, 2);
    1.32 +  ok([2, 4, 6], 7, false, 3);
    1.33 +
    1.34 +  // duplicates
    1.35 +  ok([2, 2], 2, true, 0);
    1.36 +  ok([2, 2], 1, false, 0);
    1.37 +  ok([2, 2], 3, false, 2);
    1.38 +
    1.39 +  // duplicates on the left
    1.40 +  ok([2, 2, 4], 2, true, 1);
    1.41 +  ok([2, 2, 4], 4, true, 2);
    1.42 +  ok([2, 2, 4], 1, false, 0);
    1.43 +  ok([2, 2, 4], 3, false, 2);
    1.44 +  ok([2, 2, 4], 5, false, 3);
    1.45 +
    1.46 +  // duplicates on the right
    1.47 +  ok([2, 4, 4], 2, true, 0);
    1.48 +  ok([2, 4, 4], 4, true, 1);
    1.49 +  ok([2, 4, 4], 1, false, 0);
    1.50 +  ok([2, 4, 4], 3, false, 1);
    1.51 +  ok([2, 4, 4], 5, false, 3);
    1.52 +
    1.53 +  // duplicates in the middle
    1.54 +  ok([2, 4, 4, 6], 2, true, 0);
    1.55 +  ok([2, 4, 4, 6], 4, true, 1);
    1.56 +  ok([2, 4, 4, 6], 6, true, 3);
    1.57 +  ok([2, 4, 4, 6], 1, false, 0);
    1.58 +  ok([2, 4, 4, 6], 3, false, 1);
    1.59 +  ok([2, 4, 4, 6], 5, false, 3);
    1.60 +  ok([2, 4, 4, 6], 7, false, 4);
    1.61 +
    1.62 +  // duplicates all around
    1.63 +  ok([2, 2, 4, 4, 6, 6], 2, true, 0);
    1.64 +  ok([2, 2, 4, 4, 6, 6], 4, true, 2);
    1.65 +  ok([2, 2, 4, 4, 6, 6], 6, true, 4);
    1.66 +  ok([2, 2, 4, 4, 6, 6], 1, false, 0);
    1.67 +  ok([2, 2, 4, 4, 6, 6], 3, false, 2);
    1.68 +  ok([2, 2, 4, 4, 6, 6], 5, false, 4);
    1.69 +  ok([2, 2, 4, 4, 6, 6], 7, false, 6);
    1.70 +}
    1.71 +
    1.72 +function ok(array, target, expectedFound, expectedIdx) {
    1.73 +  let [found, idx] = BinarySearch.search(array, target, cmp);
    1.74 +  do_check_eq(found, expectedFound);
    1.75 +  do_check_eq(idx, expectedIdx);
    1.76 +
    1.77 +  idx = expectedFound ? expectedIdx : -1;
    1.78 +  do_check_eq(BinarySearch.indexOf(array, target, cmp), idx);
    1.79 +  do_check_eq(BinarySearch.insertionIndexOf(array, target, cmp), expectedIdx);
    1.80 +}
    1.81 +
    1.82 +function cmp(num1, num2) {
    1.83 +  return num1 - num2;
    1.84 +}