Mercurial > releases > mozilla-beta / file revision / toolkit/modules/BinarySearch.jsm@432e6a592cf9421be66464e466f88c72e308c20c

summary |
shortlog |
changelog |
pushlog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

toolkit/modules/BinarySearch.jsm

author | Rail Aliiev <rail@mozilla.com> |

Thu, 02 Jul 2015 18:14:36 -0400 | |

changeset 281369 | 432e6a592cf9421be66464e466f88c72e308c20c |

parent 230091 | c105e80ce9239dc18770fcc55cde6f969ad9b34e |

child 367766 | 4873321befff7cc0c251b34b29192140070f1702 |

permissions | -rw-r--r-- |

Bug 1178945 - Add 'tsz' and 'cak' locales to the Fennec build. r=Pike,a=rkothari

/* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this file, * You can obtain one at http://mozilla.org/MPL/2.0/. */ "use strict"; this.EXPORTED_SYMBOLS = [ "BinarySearch", ]; this.BinarySearch = Object.freeze({ /** * Returns the index of the given target in the given array or -1 if the * target is not found. * * See search() for a description of this function's parameters. * * @return The index of `target` in `array` or -1 if `target` is not found. */ indexOf: function (comparator, array, target) { let [found, idx] = this.search(comparator, array, target); return found ? idx : -1; }, /** * Returns the index within the given array where the given target may be * inserted to keep the array ordered. * * See search() for a description of this function's parameters. * * @return The index in `array` where `target` may be inserted to keep `array` * ordered. */ insertionIndexOf: function (comparator, array, target) { return this.search(comparator, array, target)[1]; }, /** * Searches for the given target in the given array. * * @param comparator * A function that takes two arguments and compares them, returning a * negative number if the first should be ordered before the second, * zero if the first and second have the same ordering, or a positive * number if the second should be ordered before the first. The first * argument is always `target`, and the second argument is a value * from the array. * @param array * An array whose elements are ordered by `comparator`. * @param target * The value to search for. * @return An array with two elements. If `target` is found, the first * element is true, and the second element is its index in the array. * If `target` is not found, the first element is false, and the * second element is the index where it may be inserted to keep the * array ordered. */ search: function (comparator, array, target) { let low = 0; let high = array.length - 1; while (low <= high) { // Thanks to http://jsperf.com/code-review-1480 for this tip. let mid = (low + high) >> 1; let cmp = comparator(target, array[mid]); if (cmp == 0) return [true, mid]; if (cmp < 0) high = mid - 1; else low = mid + 1; } return [false, low]; }, });