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    var mid = Math.floor((aHigh - aLow) / 2) + aLow;
 35    var cmp = aCompare(aNeedle, aHaystack[mid], true);
 36    if (cmp === 0) {
 37      // Found the element we are looking for.
 38      return mid;
 39    }
 40    else if (cmp > 0) {
 41      // Our needle is greater than aHaystack[mid].
 42      if (aHigh - mid > 1) {
 43        // The element is in the upper half.
 44        return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
 45      }
 46  
 47      // The exact needle element was not found in this haystack. Determine if
 48      // we are in termination case (3) or (2) and return the appropriate thing.
 49      if (aBias == exports.LEAST_UPPER_BOUND) {
 50        return aHigh < aHaystack.length ? aHigh : -1;
 51      } else {
 52        return mid;
 53      }
 54    }
 55    else {
 56      // Our needle is less than aHaystack[mid].
 57      if (mid - aLow > 1) {
 58        // The element is in the lower half.
 59        return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
 60      }
 61  
 62      // we are in termination case (3) or (2) and return the appropriate thing.
 63      if (aBias == exports.LEAST_UPPER_BOUND) {
 64        return mid;
 65      } else {
 66        return aLow < 0 ? -1 : aLow;
 67      }
 68    }
 69  }
 70  
 71  /**
 72   * This is an implementation of binary search which will always try and return
 73   * the index of the closest element if there is no exact hit. This is because
 74   * mappings between original and generated line/col pairs are single points,
 75   * and there is an implicit region between each of them, so a miss just means
 76   * that you aren't on the very start of a region.
 77   *
 78   * @param aNeedle The element you are looking for.
 79   * @param aHaystack The array that is being searched.
 80   * @param aCompare A function which takes the needle and an element in the
 81   *     array and returns -1, 0, or 1 depending on whether the needle is less
 82   *     than, equal to, or greater than the element, respectively.
 83   * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
 84   *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
 85   *     closest element that is smaller than or greater than the one we are
 86   *     searching for, respectively, if the exact element cannot be found.
 87   *     Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
 88   */
 89  exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
 90    if (aHaystack.length === 0) {
 91      return -1;
 92    }
 93  
 94    var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack,
 95                                aCompare, aBias || exports.GREATEST_LOWER_BOUND);
 96    if (index < 0) {
 97      return -1;
 98    }
 99  
100    // We have found either the exact element, or the next-closest element than
101    // the one we are searching for. However, there may be more than one such
102    // element. Make sure we always return the smallest of these.
103    while (index - 1 >= 0) {
104      if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
105        break;
106      }
107      --index;
108    }
109  
110    return index;
111  };