| /* -*- 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 |
| */ |
| if (typeof define !== 'function') { |
| var define = require('amdefine')(module, require); |
| } |
| define(function (require, exports, module) { |
| |
| /** |
| * 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. |
| */ |
| function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare) { |
| // 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 that is less than that element. |
| // |
| // 3. We did not find the exact element, and there is no next-closest |
| // element which is less 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) { |
| // aHaystack[mid] is greater than our needle. |
| if (aHigh - mid > 1) { |
| // The element is in the upper half. |
| return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare); |
| } |
| // We did not find an exact match, return the next closest one |
| // (termination case 2). |
| return mid; |
| } |
| else { |
| // aHaystack[mid] is less than our needle. |
| if (mid - aLow > 1) { |
| // The element is in the lower half. |
| return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare); |
| } |
| // The exact needle element was not found in this haystack. Determine if |
| // we are in termination case (2) or (3) and return the appropriate thing. |
| return aLow < 0 ? -1 : aLow; |
| } |
| } |
| |
| /** |
| * This is an implementation of binary search which will always try and return |
| * the index of next lowest value checked 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. |
| */ |
| exports.search = function search(aNeedle, aHaystack, aCompare) { |
| if (aHaystack.length === 0) { |
| return -1; |
| } |
| return recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack, aCompare) |
| }; |
| |
| }); |
