1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/modules/BinarySearch.jsm Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,74 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this file,
1.6 + * You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +"use strict";
1.9 +
1.10 +this.EXPORTED_SYMBOLS = [
1.11 + "BinarySearch",
1.12 +];
1.13 +
1.14 +this.BinarySearch = Object.freeze({
1.15 +
1.16 + /**
1.17 + * Returns the index of the given target in the given array or -1 if the
1.18 + * target is not found.
1.19 + *
1.20 + * See search() for a description of this function's parameters.
1.21 + *
1.22 + * @return The index of `target` in `array` or -1 if `target` is not found.
1.23 + */
1.24 + indexOf: function (array, target, comparator) {
1.25 + let [found, idx] = this.search(array, target, comparator);
1.26 + return found ? idx : -1;
1.27 + },
1.28 +
1.29 + /**
1.30 + * Returns the index within the given array where the given target may be
1.31 + * inserted to keep the array ordered.
1.32 + *
1.33 + * See search() for a description of this function's parameters.
1.34 + *
1.35 + * @return The index in `array` where `target` may be inserted to keep `array`
1.36 + * ordered.
1.37 + */
1.38 + insertionIndexOf: function (array, target, comparator) {
1.39 + return this.search(array, target, comparator)[1];
1.40 + },
1.41 +
1.42 + /**
1.43 + * Searches for the given target in the given array.
1.44 + *
1.45 + * @param array
1.46 + * An array whose elements are ordered by `comparator`.
1.47 + * @param target
1.48 + * The value to search for.
1.49 + * @param comparator
1.50 + * A function that takes two arguments and compares them, returning a
1.51 + * negative number if the first should be ordered before the second,
1.52 + * zero if the first and second have the same ordering, or a positive
1.53 + * number if the second should be ordered before the first. The first
1.54 + * argument is always `target`, and the second argument is a value
1.55 + * from the array.
1.56 + * @return An array with two elements. If `target` is found, the first
1.57 + * element is true, and the second element is its index in the array.
1.58 + * If `target` is not found, the first element is false, and the
1.59 + * second element is the index where it may be inserted to keep the
1.60 + * array ordered.
1.61 + */
1.62 + search: function (array, target, comparator) {
1.63 + let low = 0;
1.64 + let high = array.length - 1;
1.65 + while (low <= high) {
1.66 + let mid = Math.floor((low + high) / 2);
1.67 + let cmp = comparator(target, array[mid]);
1.68 + if (cmp == 0)
1.69 + return [true, mid];
1.70 + if (cmp < 0)
1.71 + high = mid - 1;
1.72 + else
1.73 + low = mid + 1;
1.74 + }
1.75 + return [false, low];
1.76 + },
1.77 +});
