git.r.bdr.sh - rbdr/dotfiles/blob

   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 if (typeof define !== 'function') {
   8     var define = require('amdefine')(module, require);
   9 }
  10 define(function (require, exports, module) {
  11
  12   /**
  13    * Recursive implementation of binary search.
  14    *
  15    * @param aLow Indices here and lower do not contain the needle.
  16    * @param aHigh Indices here and higher do not contain the needle.
  17    * @param aNeedle The element being searched for.
  18    * @param aHaystack The non-empty array being searched.
  19    * @param aCompare Function which takes two elements and returns -1, 0, or 1.
  20    */
  21   function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare) {
  22     // This function terminates when one of the following is true:
  23     //
  24     //   1. We find the exact element we are looking for.
  25     //
  26     //   2. We did not find the exact element, but we can return the index of
  27     //      the next closest element that is less than that element.
  28     //
  29     //   3. We did not find the exact element, and there is no next-closest
  30     //      element which is less than the one we are searching for, so we
  31     //      return -1.
  32     var mid = Math.floor((aHigh - aLow) / 2) + aLow;
  33     var cmp = aCompare(aNeedle, aHaystack[mid], true);
  34     if (cmp === 0) {
  35       // Found the element we are looking for.
  36       return mid;
  37     }
  38     else if (cmp > 0) {
  39       // aHaystack[mid] is greater than our needle.
  40       if (aHigh - mid > 1) {
  41         // The element is in the upper half.
  42         return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare);
  43       }
  44       // We did not find an exact match, return the next closest one
  45       // (termination case 2).
  46       return mid;
  47     }
  48     else {
  49       // aHaystack[mid] is less than our needle.
  50       if (mid - aLow > 1) {
  51         // The element is in the lower half.
  52         return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare);
  53       }
  54       // The exact needle element was not found in this haystack. Determine if
  55       // we are in termination case (2) or (3) and return the appropriate thing.
  56       return aLow < 0 ? -1 : aLow;
  57     }
  58   }
  59
  60   /**
  61    * This is an implementation of binary search which will always try and return
  62    * the index of next lowest value checked if there is no exact hit. This is
  63    * because mappings between original and generated line/col pairs are single
  64    * points, and there is an implicit region between each of them, so a miss
  65    * just means that you aren't on the very start of a region.
  66    *
  67    * @param aNeedle The element you are looking for.
  68    * @param aHaystack The array that is being searched.
  69    * @param aCompare A function which takes the needle and an element in the
  70    *     array and returns -1, 0, or 1 depending on whether the needle is less
  71    *     than, equal to, or greater than the element, respectively.
  72    */
  73   exports.search = function search(aNeedle, aHaystack, aCompare) {
  74     if (aHaystack.length === 0) {
  75       return -1;
  76     }
  77     return recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack, aCompare)
  78   };
  79
  80 });