Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | 780x 780x 780x 1980x 1980x 563x 1417x 780x 431x 431x 431x 1218x 1218x 479x 739x 431x 50x 50x 50x 75x 75x 56x 19x 50x | /**
* @packageDocumentation
*
* Generic binary search utilities for sorted arrays.
*
* These are small, pure functions with no dependencies. They are used by
* multiple packlets (timing-engine, hit-testing, visible-object queries) so
* they live in their own packlet to avoid duplication.
*/
/**
* Returns the index of the first element in `arr` that is >= `x`.
* Equivalent to Python's `bisect_left`.
*/
export function bisectLeft(arr: number[], x: number): number {
let lo = 0;
let hi = arr.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
/**
* Returns the index of the first element in `arr` that is > `x`.
* Equivalent to Python's `bisect_right`.
*/
export function bisectRight(arr: number[], x: number): number {
let lo = 0;
let hi = arr.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] <= x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
/**
* Returns the index of the first element in `arr` whose extracted key is > `x`.
* Uses a `getKey` function to extract the comparison key from each element.
*/
export function bisectRightBy<T>(arr: T[], x: number, getKey: (item: T) => number): number {
let lo = 0;
let hi = arr.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (getKey(arr[mid]) <= x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
|