57 lines
1.5 KiB
JavaScript
57 lines
1.5 KiB
JavaScript
import ascending from "./ascending.js";
|
||
import descending from "./descending.js";
|
||
|
||
export default function bisector(f) {
|
||
let compare1, compare2, delta;
|
||
|
||
// If an accessor is specified, promote it to a comparator. In this case we
|
||
// can test whether the search value is (self-) comparable. We can’t do this
|
||
// for a comparator (except for specific, known comparators) because we can’t
|
||
// tell if the comparator is symmetric, and an asymmetric comparator can’t be
|
||
// used to test whether a single value is comparable.
|
||
if (f.length !== 2) {
|
||
compare1 = ascending;
|
||
compare2 = (d, x) => ascending(f(d), x);
|
||
delta = (d, x) => f(d) - x;
|
||
} else {
|
||
compare1 = f === ascending || f === descending ? f : zero;
|
||
compare2 = f;
|
||
delta = f;
|
||
}
|
||
|
||
function left(a, x, lo = 0, hi = a.length) {
|
||
if (lo < hi) {
|
||
if (compare1(x, x) !== 0) return hi;
|
||
do {
|
||
const mid = (lo + hi) >>> 1;
|
||
if (compare2(a[mid], x) < 0) lo = mid + 1;
|
||
else hi = mid;
|
||
} while (lo < hi);
|
||
}
|
||
return lo;
|
||
}
|
||
|
||
function right(a, x, lo = 0, hi = a.length) {
|
||
if (lo < hi) {
|
||
if (compare1(x, x) !== 0) return hi;
|
||
do {
|
||
const mid = (lo + hi) >>> 1;
|
||
if (compare2(a[mid], x) <= 0) lo = mid + 1;
|
||
else hi = mid;
|
||
} while (lo < hi);
|
||
}
|
||
return lo;
|
||
}
|
||
|
||
function center(a, x, lo = 0, hi = a.length) {
|
||
const i = left(a, x, lo, hi - 1);
|
||
return i > lo && delta(a[i - 1], x) > -delta(a[i], x) ? i - 1 : i;
|
||
}
|
||
|
||
return {left, center, right};
|
||
}
|
||
|
||
function zero() {
|
||
return 0;
|
||
}
|