vnfmarket/src/main/webapp/vnfmarket/node_modules/source-map/lib/source-map/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 if (typeof define !== 'function') {
   8     var define = require('amdefine')(module, require);
   9 }
  10 define(function (require, exports, module) {
  11
  12   exports.GREATEST_LOWER_BOUND = 1;
  13   exports.LEAST_UPPER_BOUND = 2;
  14
  15   /**
  16    * Recursive implementation of binary search.
  17    *
  18    * @param aLow Indices here and lower do not contain the needle.
  19    * @param aHigh Indices here and higher do not contain the needle.
  20    * @param aNeedle The element being searched for.
  21    * @param aHaystack The non-empty array being searched.
  22    * @param aCompare Function which takes two elements and returns -1, 0, or 1.
  23    * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
  24    *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
  25    *     closest element that is smaller than or greater than the one we are
  26    *     searching for, respectively, if the exact element cannot be found.
  27    */
  28   function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) {
  29     // This function terminates when one of the following is true:
  30     //
  31     //   1. We find the exact element we are looking for.
  32     //
  33     //   2. We did not find the exact element, but we can return the index of
  34     //      the next-closest element.
  35     //
  36     //   3. We did not find the exact element, and there is no next-closest
  37     //      element than the one we are searching for, so we return -1.
  38     var mid = Math.floor((aHigh - aLow) / 2) + aLow;
  39     var cmp = aCompare(aNeedle, aHaystack[mid], true);
  40     if (cmp === 0) {
  41       // Found the element we are looking for.
  42       return mid;
  43     }
  44     else if (cmp > 0) {
  45       // Our needle is greater than aHaystack[mid].
  46       if (aHigh - mid > 1) {
  47         // The element is in the upper half.
  48         return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
  49       }
  50
  51       // The exact needle element was not found in this haystack. Determine if
  52       // we are in termination case (3) or (2) and return the appropriate thing.
  53       if (aBias == exports.LEAST_UPPER_BOUND) {
  54         return aHigh < aHaystack.length ? aHigh : -1;
  55       } else {
  56         return mid;
  57       }
  58     }
  59     else {
  60       // Our needle is less than aHaystack[mid].
  61       if (mid - aLow > 1) {
  62         // The element is in the lower half.
  63         return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
  64       }
  65
  66       // we are in termination case (3) or (2) and return the appropriate thing.
  67       if (aBias == exports.LEAST_UPPER_BOUND) {
  68         return mid;
  69       } else {
  70         return aLow < 0 ? -1 : aLow;
  71       }
  72     }
  73   }
  74
  75   /**
  76    * This is an implementation of binary search which will always try and return
  77    * the index of the closest element if there is no exact hit. This is because
  78    * mappings between original and generated line/col pairs are single points,
  79    * and there is an implicit region between each of them, so a miss just means
  80    * that you aren't on the very start of a region.
  81    *
  82    * @param aNeedle The element you are looking for.
  83    * @param aHaystack The array that is being searched.
  84    * @param aCompare A function which takes the needle and an element in the
  85    *     array and returns -1, 0, or 1 depending on whether the needle is less
  86    *     than, equal to, or greater than the element, respectively.
  87    * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
  88    *     'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
  89    *     closest element that is smaller than or greater than the one we are
  90    *     searching for, respectively, if the exact element cannot be found.
  91    *     Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
  92    */
  93   exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
  94     if (aHaystack.length === 0) {
  95       return -1;
  96     }
  97
  98     var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack,
  99                                 aCompare, aBias || exports.GREATEST_LOWER_BOUND);
 100     if (index < 0) {
 101       return -1;
 102     }
 103
 104     // We have found either the exact element, or the next-closest element than
 105     // the one we are searching for. However, there may be more than one such
 106     // element. Make sure we always return the smallest of these.
 107     while (index - 1 >= 0) {
 108       if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
 109         break;
 110       }
 111       --index;
 112     }
 113
 114     return index;
 115   };
 116
 117 });