Pinsave/counterstrike

1/* -*- Mode: js; js-indent-level: 2; -*- */2/*3 * Copyright 2011 Mozilla Foundation and contributors4 * Licensed under the New BSD license. See LICENSE or:5 * http://opensource.org/licenses/BSD-3-Clause6 */7 8exports.GREATEST_LOWER_BOUND = 1;9exports.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' or20 *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the21 *     closest element that is smaller than or greater than the one we are22 *     searching for, respectively, if the exact element cannot be found.23 */24function 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 of30  //      the next-closest element.31  //32  //   3. We did not find the exact element, and there is no next-closest33  //      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 if48    // 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 return73 * the index of the closest element if there is no exact hit. This is because74 * 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 means76 * 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 the81 *     array and returns -1, 0, or 1 depending on whether the needle is less82 *     than, equal to, or greater than the element, respectively.83 * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or84 *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the85 *     closest element that is smaller than or greater than the one we are86 *     searching for, respectively, if the exact element cannot be found.87 *     Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.88 */89exports.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 than101  // the one we are searching for. However, there may be more than one such102  // 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};112