test_binary_search.js

/*
 * WARNING!
 *
 * Do not edit this file directly, it is built from the sources at
 * https://github.com/mozilla/source-map/
 */

Components.utils.import('resource://test/Utils.jsm');
/* -*- Mode: js; js-indent-level: 2; -*- */
/*
 * Copyright 2011 Mozilla Foundation and contributors
 * Licensed under the New BSD license. See LICENSE or:
 * http://opensource.org/licenses/BSD-3-Clause
 */
define("test/source-map/test-binary-search", ["require", "exports", "module"], function (require, exports, module) {

  var binarySearch = require('source-map/binary-search');

  function numberCompare(a, b) {
    return a - b;
  }

  exports['test too high with lub bias'] = function (assert, util) {
    var needle = 30;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.doesNotThrow(function () {
      binarySearch.search(needle, haystack, numberCompare);
    });

    assert.equal(binarySearch.search(needle, haystack, numberCompare), -1);
  };

  exports['test too low with lub bias'] = function (assert, util) {
    var needle = 1;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.doesNotThrow(function () {
      binarySearch.search(needle, haystack, numberCompare, true);
    });

    assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare)], 2);
  };

  exports['test exact search with lub bias'] = function (assert, util) {
    var needle = 4;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare)], 4);
  };

  exports['test fuzzy search with lub bias'] = function (assert, util) {
    var needle = 19;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare)], 20);
  };

  exports['test too high with glb bias'] = function (assert, util) {
    var needle = 30;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.doesNotThrow(function () {
      binarySearch.search(needle, haystack, numberCompare);
    });

    assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare,
                                              binarySearch.GREATEST_LOWER_BOUND)], 20);
  };

  exports['test too low with glb bias'] = function (assert, util) {
    var needle = 1;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.doesNotThrow(function () {
      binarySearch.search(needle, haystack, numberCompare,
                          binarySearch.GREATEST_LOWER_BOUND);
    });

    assert.equal(binarySearch.search(needle, haystack, numberCompare,
                                     binarySearch.GREATEST_LOWER_BOUND), -1);
  };

  exports['test exact search with glb bias'] = function (assert, util) {
    var needle = 4;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare,
                          binarySearch.GREATEST_LOWER_BOUND)], 4);
  };

  exports['test fuzzy search with glb bias'] = function (assert, util) {
    var needle = 19;
    var haystack = [2,4,6,8,10,12,14,16,18,20];

    assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare,
                          binarySearch.GREATEST_LOWER_BOUND)], 18);
  };
});
function run_test() {
  runSourceMapTests('test/source-map/test-binary-search', do_throw);
}