Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/fourtyone11/origin-hugo-theme.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to 'assets/node_modules/source-map/lib/binary-search.js')
-rw-r--r--assets/node_modules/source-map/lib/binary-search.js111
1 files changed, 0 insertions, 111 deletions
diff --git a/assets/node_modules/source-map/lib/binary-search.js b/assets/node_modules/source-map/lib/binary-search.js
deleted file mode 100644
index 010ac94..0000000
--- a/assets/node_modules/source-map/lib/binary-search.js
+++ /dev/null
@@ -1,111 +0,0 @@
-/* -*- 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
- */
-
-exports.GREATEST_LOWER_BOUND = 1;
-exports.LEAST_UPPER_BOUND = 2;
-
-/**
- * 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.
- * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
- * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
- * closest element that is smaller than or greater than the one we are
- * searching for, respectively, if the exact element cannot be found.
- */
-function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) {
- // 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.
- //
- // 3. We did not find the exact element, and there is no next-closest
- // element 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) {
- // Our needle is greater than aHaystack[mid].
- if (aHigh - mid > 1) {
- // The element is in the upper half.
- return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
- }
-
- // The exact needle element was not found in this haystack. Determine if
- // we are in termination case (3) or (2) and return the appropriate thing.
- if (aBias == exports.LEAST_UPPER_BOUND) {
- return aHigh < aHaystack.length ? aHigh : -1;
- } else {
- return mid;
- }
- }
- else {
- // Our needle is less than aHaystack[mid].
- if (mid - aLow > 1) {
- // The element is in the lower half.
- return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
- }
-
- // we are in termination case (3) or (2) and return the appropriate thing.
- if (aBias == exports.LEAST_UPPER_BOUND) {
- return mid;
- } else {
- return aLow < 0 ? -1 : aLow;
- }
- }
-}
-
-/**
- * This is an implementation of binary search which will always try and return
- * the index of the closest element 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.
- * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
- * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
- * closest element that is smaller than or greater than the one we are
- * searching for, respectively, if the exact element cannot be found.
- * Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
- */
-exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
- if (aHaystack.length === 0) {
- return -1;
- }
-
- var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack,
- aCompare, aBias || exports.GREATEST_LOWER_BOUND);
- if (index < 0) {
- return -1;
- }
-
- // We have found either the exact element, or the next-closest element than
- // the one we are searching for. However, there may be more than one such
- // element. Make sure we always return the smallest of these.
- while (index - 1 >= 0) {
- if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
- break;
- }
- --index;
- }
-
- return index;
-};