| /* -*- 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 |
| */ |
| |
| exports.GREATEST_LOWER_BOUND = 1; |
| exports.LEAST_UPPER_BOUND = 2; |
| |
| /** |
| * Recursive implementation of binary search. |
| * |
| * @param aLow Indices here and lower do not contain the needle. |
| * @param aHigh Indices here and higher do not contain the needle. |
| * @param aNeedle The element being searched for. |
| * @param aHaystack The non-empty array being searched. |
| * @param aCompare Function which takes two elements and returns -1, 0, or 1. |
| * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or |
| * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the |
| * closest element that is smaller than or greater than the one we are |
| * searching for, respectively, if the exact element cannot be found. |
| */ |
| function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) { |
| // This function terminates when one of the following is true: |
| // |
| // 1. We find the exact element we are looking for. |
| // |
| // 2. We did not find the exact element, but we can return the index of |
| // the next-closest element. |
| // |
| // 3. We did not find the exact element, and there is no next-closest |
| // element than the one we are searching for, so we return -1. |
| var mid = Math.floor((aHigh - aLow) / 2) + aLow; |
| var cmp = aCompare(aNeedle, aHaystack[mid], true); |
| if (cmp === 0) { |
| // Found the element we are looking for. |
| return mid; |
| } |
| else if (cmp > 0) { |
| // Our needle is greater than aHaystack[mid]. |
| if (aHigh - mid > 1) { |
| // The element is in the upper half. |
| return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias); |
| } |
| |
| // The exact needle element was not found in this haystack. Determine if |
| // we are in termination case (3) or (2) and return the appropriate thing. |
| if (aBias == exports.LEAST_UPPER_BOUND) { |
| return aHigh < aHaystack.length ? aHigh : -1; |
| } else { |
| return mid; |
| } |
| } |
| else { |
| // Our needle is less than aHaystack[mid]. |
| if (mid - aLow > 1) { |
| // The element is in the lower half. |
| return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias); |
| } |
| |
| // we are in termination case (3) or (2) and return the appropriate thing. |
| if (aBias == exports.LEAST_UPPER_BOUND) { |
| return mid; |
| } else { |
| return aLow < 0 ? -1 : aLow; |
| } |
| } |
| } |
| |
| /** |
| * This is an implementation of binary search which will always try and return |
| * the index of the closest element if there is no exact hit. This is because |
| * mappings between original and generated line/col pairs are single points, |
| * and there is an implicit region between each of them, so a miss just means |
| * that you aren't on the very start of a region. |
| * |
| * @param aNeedle The element you are looking for. |
| * @param aHaystack The array that is being searched. |
| * @param aCompare A function which takes the needle and an element in the |
| * array and returns -1, 0, or 1 depending on whether the needle is less |
| * than, equal to, or greater than the element, respectively. |
| * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or |
| * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the |
| * closest element that is smaller than or greater than the one we are |
| * searching for, respectively, if the exact element cannot be found. |
| * Defaults to 'binarySearch.GREATEST_LOWER_BOUND'. |
| */ |
| exports.search = function search(aNeedle, aHaystack, aCompare, aBias) { |
| if (aHaystack.length === 0) { |
| return -1; |
| } |
| |
| var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack, |
| aCompare, aBias || exports.GREATEST_LOWER_BOUND); |
| if (index < 0) { |
| return -1; |
| } |
| |
| // We have found either the exact element, or the next-closest element than |
| // the one we are searching for. However, there may be more than one such |
| // element. Make sure we always return the smallest of these. |
| while (index - 1 >= 0) { |
| if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) { |
| break; |
| } |
| --index; |
| } |
| |
| return index; |
| }; |