www.aleph1.co.uk Git - yaffs-website/blob - node_modules/source-map/lib/binary-search.js

   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
   8 exports.GREATEST_LOWER_BOUND = 1;
   9 exports.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' or
  20  *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
  21  *     closest element that is smaller than or greater than the one we are
  22  *     searching for, respectively, if the exact element cannot be found.
  23  */
  24 function 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 of
  30   //      the next-closest element.
  31   //
  32   //   3. We did not find the exact element, and there is no next-closest
  33   //      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 if
  48     // 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 return
  73  * the index of the closest element if there is no exact hit. This is because
  74  * 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 means
  76  * 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 the
  81  *     array and returns -1, 0, or 1 depending on whether the needle is less
  82  *     than, equal to, or greater than the element, respectively.
  83  * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
  84  *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
  85  *     closest element that is smaller than or greater than the one we are
  86  *     searching for, respectively, if the exact element cannot be found.
  87  *     Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
  88  */
  89 exports.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 than
 101   // the one we are searching for. However, there may be more than one such
 102   // 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 };