toolkit/modules/BinarySearch.jsm@129ffea94266
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.
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/. */
5 "use strict";
7 this.EXPORTED_SYMBOLS = [
8 "BinarySearch",
9 ];
11 this.BinarySearch = Object.freeze({
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 },
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 },
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 });
