Diffusion Open Access Compliance Check Tool (OACCT) (paginated-inlines) Browse

rOACCT/node_modules/source-map-js/lib/binary-search.js
f646e1f695a7paginated-inlines

binary-search.js
View Options

			/* -- 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;
			};