The Tor Browser / file comparison
comparison: toolkit/modules/BinarySearch.jsm
toolkit/modules/BinarySearch.jsm
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:61dc8ab59054 |
|---|---|
| 1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 2 * License, v. 2.0. If a copy of the MPL was not distributed with this file, | |
| 3 * You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 4 | |
| 5 "use strict"; | |
| 6 | |
| 7 this.EXPORTED_SYMBOLS = [ | |
| 8 "BinarySearch", | |
| 9 ]; | |
| 10 | |
| 11 this.BinarySearch = Object.freeze({ | |
| 12 | |
| 13 /** | |
| 14 * Returns the index of the given target in the given array or -1 if the | |
| 15 * target is not found. | |
| 16 * | |
| 17 * See search() for a description of this function's parameters. | |
| 18 * | |
| 19 * @return The index of `target` in `array` or -1 if `target` is not found. | |
| 20 */ | |
| 21 indexOf: function (array, target, comparator) { | |
| 22 let [found, idx] = this.search(array, target, comparator); | |
| 23 return found ? idx : -1; | |
| 24 }, | |
| 25 | |
| 26 /** | |
| 27 * Returns the index within the given array where the given target may be | |
| 28 * inserted to keep the array ordered. | |
| 29 * | |
| 30 * See search() for a description of this function's parameters. | |
| 31 * | |
| 32 * @return The index in `array` where `target` may be inserted to keep `array` | |
| 33 * ordered. | |
| 34 */ | |
| 35 insertionIndexOf: function (array, target, comparator) { | |
| 36 return this.search(array, target, comparator)[1]; | |
| 37 }, | |
| 38 | |
| 39 /** | |
| 40 * Searches for the given target in the given array. | |
| 41 * | |
| 42 * @param array | |
| 43 * An array whose elements are ordered by `comparator`. | |
| 44 * @param target | |
| 45 * The value to search for. | |
| 46 * @param comparator | |
| 47 * A function that takes two arguments and compares them, returning a | |
| 48 * negative number if the first should be ordered before the second, | |
| 49 * zero if the first and second have the same ordering, or a positive | |
| 50 * number if the second should be ordered before the first. The first | |
| 51 * argument is always `target`, and the second argument is a value | |
| 52 * from the array. | |
| 53 * @return An array with two elements. If `target` is found, the first | |
| 54 * element is true, and the second element is its index in the array. | |
| 55 * If `target` is not found, the first element is false, and the | |
| 56 * second element is the index where it may be inserted to keep the | |
| 57 * array ordered. | |
| 58 */ | |
| 59 search: function (array, target, comparator) { | |
| 60 let low = 0; | |
| 61 let high = array.length - 1; | |
| 62 while (low <= high) { | |
| 63 let mid = Math.floor((low + high) / 2); | |
| 64 let cmp = comparator(target, array[mid]); | |
| 65 if (cmp == 0) | |
| 66 return [true, mid]; | |
| 67 if (cmp < 0) | |
| 68 high = mid - 1; | |
| 69 else | |
| 70 low = mid + 1; | |
| 71 } | |
| 72 return [false, low]; | |
| 73 }, | |
| 74 }); |
