tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

binary-search.js (4186B)

      1 /* -*- Mode: js; js-indent-level: 2; -*- */
      2 /*
      3 * Copyright 2011 Mozilla Foundation and contributors
      4 * Licensed under the New BSD license. See LICENSE or:
      5 * http://opensource.org/licenses/BSD-3-Clause
      6 */
      7 
      8 exports.GREATEST_LOWER_BOUND = 1;
      9 exports.LEAST_UPPER_BOUND = 2;
     10 
     11 /**
     12 * Recursive implementation of binary search.
     13 *
     14 * @param aLow Indices here and lower do not contain the needle.
     15 * @param aHigh Indices here and higher do not contain the needle.
     16 * @param aNeedle The element being searched for.
     17 * @param aHaystack The non-empty array being searched.
     18 * @param aCompare Function which takes two elements and returns -1, 0, or 1.
     19 * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
     20 *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
     21 *     closest element that is smaller than or greater than the one we are
     22 *     searching for, respectively, if the exact element cannot be found.
     23 */
     24 function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) {
     25  // This function terminates when one of the following is true:
     26  //
     27  //   1. We find the exact element we are looking for.
     28  //
     29  //   2. We did not find the exact element, but we can return the index of
     30  //      the next-closest element.
     31  //
     32  //   3. We did not find the exact element, and there is no next-closest
     33  //      element than the one we are searching for, so we return -1.
     34  const mid = Math.floor((aHigh - aLow) / 2) + aLow;
     35  const cmp = aCompare(aNeedle, aHaystack[mid], true);
     36  if (cmp === 0) {
     37    // Found the element we are looking for.
     38    return mid;
     39  } else if (cmp > 0) {
     40    // Our needle is greater than aHaystack[mid].
     41    if (aHigh - mid > 1) {
     42      // The element is in the upper half.
     43      return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
     44    }
     45 
     46    // The exact needle element was not found in this haystack. Determine if
     47    // we are in termination case (3) or (2) and return the appropriate thing.
     48    if (aBias === exports.LEAST_UPPER_BOUND) {
     49      return aHigh < aHaystack.length ? aHigh : -1;
     50    }
     51    return mid;
     52  }
     53 
     54  // Our needle is less than aHaystack[mid].
     55  if (mid - aLow > 1) {
     56    // The element is in the lower half.
     57    return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
     58  }
     59 
     60  // we are in termination case (3) or (2) and return the appropriate thing.
     61  if (aBias == exports.LEAST_UPPER_BOUND) {
     62    return mid;
     63  }
     64  return aLow < 0 ? -1 : aLow;
     65 }
     66 
     67 /**
     68 * This is an implementation of binary search which will always try and return
     69 * the index of the closest element if there is no exact hit. This is because
     70 * mappings between original and generated line/col pairs are single points,
     71 * and there is an implicit region between each of them, so a miss just means
     72 * that you aren't on the very start of a region.
     73 *
     74 * @param aNeedle The element you are looking for.
     75 * @param aHaystack The array that is being searched.
     76 * @param aCompare A function which takes the needle and an element in the
     77 *     array and returns -1, 0, or 1 depending on whether the needle is less
     78 *     than, equal to, or greater than the element, respectively.
     79 * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
     80 *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
     81 *     closest element that is smaller than or greater than the one we are
     82 *     searching for, respectively, if the exact element cannot be found.
     83 *     Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
     84 */
     85 exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
     86  if (aHaystack.length === 0) {
     87    return -1;
     88  }
     89 
     90  let index = recursiveSearch(
     91    -1,
     92    aHaystack.length,
     93    aNeedle,
     94    aHaystack,
     95    aCompare,
     96    aBias || exports.GREATEST_LOWER_BOUND
     97  );
     98  if (index < 0) {
     99    return -1;
    100  }
    101 
    102  // We have found either the exact element, or the next-closest element to
    103  // the one we are searching for. However, there may be more than one such
    104  // element. Make sure we always return the smallest of these.
    105  while (index - 1 >= 0) {
    106    if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
    107      break;
    108    }
    109    --index;
    110  }
    111 
    112  return index;
    113 };