toolkit/modules/BinarySearch.jsm@129ffea94266 (annotated)
toolkit/modules/BinarySearch.jsm
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
| michael@0 | 1 | /* This Source Code Form is subject to the terms of the Mozilla Public |
| michael@0 | 2 | * License, v. 2.0. If a copy of the MPL was not distributed with this file, |
| michael@0 | 3 | * You can obtain one at http://mozilla.org/MPL/2.0/. */ |
| michael@0 | 4 | |
| michael@0 | 5 | "use strict"; |
| michael@0 | 6 | |
| michael@0 | 7 | this.EXPORTED_SYMBOLS = [ |
| michael@0 | 8 | "BinarySearch", |
| michael@0 | 9 | ]; |
| michael@0 | 10 | |
| michael@0 | 11 | this.BinarySearch = Object.freeze({ |
| michael@0 | 12 | |
| michael@0 | 13 | /** |
| michael@0 | 14 | * Returns the index of the given target in the given array or -1 if the |
| michael@0 | 15 | * target is not found. |
| michael@0 | 16 | * |
| michael@0 | 17 | * See search() for a description of this function's parameters. |
| michael@0 | 18 | * |
| michael@0 | 19 | * @return The index of `target` in `array` or -1 if `target` is not found. |
| michael@0 | 20 | */ |
| michael@0 | 21 | indexOf: function (array, target, comparator) { |
| michael@0 | 22 | let [found, idx] = this.search(array, target, comparator); |
| michael@0 | 23 | return found ? idx : -1; |
| michael@0 | 24 | }, |
| michael@0 | 25 | |
| michael@0 | 26 | /** |
| michael@0 | 27 | * Returns the index within the given array where the given target may be |
| michael@0 | 28 | * inserted to keep the array ordered. |
| michael@0 | 29 | * |
| michael@0 | 30 | * See search() for a description of this function's parameters. |
| michael@0 | 31 | * |
| michael@0 | 32 | * @return The index in `array` where `target` may be inserted to keep `array` |
| michael@0 | 33 | * ordered. |
| michael@0 | 34 | */ |
| michael@0 | 35 | insertionIndexOf: function (array, target, comparator) { |
| michael@0 | 36 | return this.search(array, target, comparator)[1]; |
| michael@0 | 37 | }, |
| michael@0 | 38 | |
| michael@0 | 39 | /** |
| michael@0 | 40 | * Searches for the given target in the given array. |
| michael@0 | 41 | * |
| michael@0 | 42 | * @param array |
| michael@0 | 43 | * An array whose elements are ordered by `comparator`. |
| michael@0 | 44 | * @param target |
| michael@0 | 45 | * The value to search for. |
| michael@0 | 46 | * @param comparator |
| michael@0 | 47 | * A function that takes two arguments and compares them, returning a |
| michael@0 | 48 | * negative number if the first should be ordered before the second, |
| michael@0 | 49 | * zero if the first and second have the same ordering, or a positive |
| michael@0 | 50 | * number if the second should be ordered before the first. The first |
| michael@0 | 51 | * argument is always `target`, and the second argument is a value |
| michael@0 | 52 | * from the array. |
| michael@0 | 53 | * @return An array with two elements. If `target` is found, the first |
| michael@0 | 54 | * element is true, and the second element is its index in the array. |
| michael@0 | 55 | * If `target` is not found, the first element is false, and the |
| michael@0 | 56 | * second element is the index where it may be inserted to keep the |
| michael@0 | 57 | * array ordered. |
| michael@0 | 58 | */ |
| michael@0 | 59 | search: function (array, target, comparator) { |
| michael@0 | 60 | let low = 0; |
| michael@0 | 61 | let high = array.length - 1; |
| michael@0 | 62 | while (low <= high) { |
| michael@0 | 63 | let mid = Math.floor((low + high) / 2); |
| michael@0 | 64 | let cmp = comparator(target, array[mid]); |
| michael@0 | 65 | if (cmp == 0) |
| michael@0 | 66 | return [true, mid]; |
| michael@0 | 67 | if (cmp < 0) |
| michael@0 | 68 | high = mid - 1; |
| michael@0 | 69 | else |
| michael@0 | 70 | low = mid + 1; |
| michael@0 | 71 | } |
| michael@0 | 72 | return [false, low]; |
| michael@0 | 73 | }, |
| michael@0 | 74 | }); |
