text: /* */ 
  "format cjs";
  /* -*- 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 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 null.
      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 aHaystack[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 aHaystack[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
          ? null
          : aHaystack[aLow];
      }
    }
  
    /**
     * This is an implementation of binary search which will always try and return
     * the 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) {
      return aHaystack.length > 0
        ? recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack, aCompare)
        : null;
    };
  
  });
  