source: trip-planner-front/node_modules/source-map-js/lib/binary-search.js

Last change on this file was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 4.1 KB
Line 
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
8exports.GREATEST_LOWER_BOUND = 1;
9exports.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 */
24function 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 */
89exports.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};
Note: See TracBrowser for help on using the repository browser.