* Helper function to do binary search when possible * @param {object} metaset - the dataset meta * @param {string} axis - the axis mode. x|y|xy|r * @param {number} value - the value to find * @param {boolean} [intersect] - should the element intersect * @returns {{lo:number, hi:number}} indices
(metaset, axis, value, intersect)
| 20 | * @returns {{lo:number, hi:number}} indices to search data array between |
| 21 | */ |
| 22 | function binarySearch(metaset, axis, value, intersect) { |
| 23 | const {controller, data, _sorted} = metaset; |
| 24 | const iScale = controller._cachedMeta.iScale; |
| 25 | const spanGaps = metaset.dataset ? metaset.dataset.options ? metaset.dataset.options.spanGaps : null : null; |
| 26 | |
| 27 | if (iScale && axis === iScale.axis && axis !== 'r' && _sorted && data.length) { |
| 28 | const lookupMethod = iScale._reversePixels ? _rlookupByKey : _lookupByKey; |
| 29 | if (!intersect) { |
| 30 | const result = lookupMethod(data, axis, value); |
| 31 | if (spanGaps) { |
| 32 | const {vScale} = controller._cachedMeta; |
| 33 | const {_parsed} = metaset; |
| 34 | |
| 35 | const distanceToDefinedLo = (_parsed |
| 36 | .slice(0, result.lo + 1) |
| 37 | .reverse() |
| 38 | .findIndex( |
| 39 | point => !isNullOrUndef(point[vScale.axis]))); |
| 40 | result.lo -= Math.max(0, distanceToDefinedLo); |
| 41 | |
| 42 | const distanceToDefinedHi = (_parsed |
| 43 | .slice(result.hi) |
| 44 | .findIndex( |
| 45 | point => !isNullOrUndef(point[vScale.axis]))); |
| 46 | result.hi += Math.max(0, distanceToDefinedHi); |
| 47 | } |
| 48 | return result; |
| 49 | } else if (controller._sharedOptions) { |
| 50 | // _sharedOptions indicates that each element has equal options -> equal proportions |
| 51 | // So we can do a ranged binary search based on the range of first element and |
| 52 | // be confident to get the full range of indices that can intersect with the value. |
| 53 | const el = data[0]; |
| 54 | const range = typeof el.getRange === 'function' && el.getRange(axis); |
| 55 | if (range) { |
| 56 | const start = lookupMethod(data, axis, value - range); |
| 57 | const end = lookupMethod(data, axis, value + range); |
| 58 | return {lo: start.lo, hi: end.hi}; |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | // Default to all elements, when binary search can not be used. |
| 63 | return {lo: 0, hi: data.length - 1}; |
| 64 | } |
| 65 | |
| 66 | /** |
| 67 | * Helper function to select candidate elements for interaction |
no test coverage detected
searching dependent graphs…