| 1 | import { isNil } from '@antv/util';
|
| 2 |
|
| 3 | type GetterFunc<T> = (o: T) => number;
|
| 4 |
|
| 5 | /**
|
| 6 | * 二分右侧查找
|
| 7 | * https://github.com/d3/d3-array/blob/master/src/bisector.js
|
| 8 | */
|
| 9 | export default function<T>(getter: GetterFunc<T>) {
|
| 10 | /**
|
| 11 | * x: 目标值
|
| 12 | * lo: 起始位置
|
| 13 | * hi: 结束位置
|
| 14 | */
|
| 15 | return function(a: T[], x: number, _lo?: number, _hi?: number) {
|
| 16 | let lo = isNil(_lo) ? 0 : _lo;
|
| 17 | let hi = isNil(_hi) ? a.length : _hi;
|
| 18 | while (lo < hi) {
|
| 19 | const mid = (lo + hi) >>> 1;
|
| 20 | if (getter(a[mid]) > x) {
|
| 21 | hi = mid;
|
| 22 | } else {
|
| 23 | lo = mid + 1;
|
| 24 | }
|
| 25 | }
|
| 26 | return lo;
|
| 27 | };
|
| 28 | }
|