1// Copyright (C) 2018 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15 16type Numbers = Float64Array|Uint32Array|number[]; 17type Range = [number, number]; 18 19function searchImpl( 20 haystack: Numbers, needle: number, i: number, j: number): number { 21 if (i === j) return -1; 22 if (i + 1 === j) { 23 return (needle >= haystack[i]) ? i : -1; 24 } 25 26 const mid = Math.floor((j - i) / 2) + i; 27 const midValue = haystack[mid]; 28 if (needle < midValue) { 29 return searchImpl(haystack, needle, i, mid); 30 } else { 31 return searchImpl(haystack, needle, mid, j); 32 } 33} 34 35function searchRangeImpl( 36 haystack: Numbers, needle: number, i: number, j: number): Range { 37 if (i === j) return [i, j]; 38 if (i + 1 === j) { 39 if (haystack[i] <= needle) { 40 return [i, j]; 41 } else { 42 return [i, i]; 43 } 44 } 45 46 const mid = Math.floor((j - i) / 2) + i; 47 const midValue = haystack[mid]; 48 49 if (needle < midValue) { 50 return searchRangeImpl(haystack, needle, i, mid); 51 } else if (needle > midValue) { 52 return searchRangeImpl(haystack, needle, mid, j); 53 } else { 54 while (haystack[i] !== needle) i++; 55 while (haystack[j - 1] !== needle) j--; 56 return [i, j]; 57 } 58} 59 60export function search(haystack: Numbers, needle: number): number { 61 return searchImpl(haystack, needle, 0, haystack.length); 62} 63 64// Given a sorted array of numbers (|haystack|) and a |needle| return the 65// half open range [i, j) of indexes where |haystack| is equal to needle. 66export function searchEq( 67 haystack: Numbers, needle: number, optRange?: Range): Range { 68 const range = searchRange(haystack, needle, optRange); 69 const [i, j] = range; 70 if (haystack[i] === needle) return range; 71 return [j, j]; 72} 73 74// Given a sorted array of numbers (|haystack|) and a |needle| return the 75// smallest half open range [i, j) of indexes which contains |needle|. 76export function searchRange( 77 haystack: Numbers, needle: number, optRange?: Range): Range { 78 const [left, right] = optRange ? optRange : [0, haystack.length]; 79 return searchRangeImpl(haystack, needle, left, right); 80} 81 82// Given a sorted array of numbers (|haystack|) and a |needle| return a 83// pair of indexes [i, j] such that: 84// If there is at least one element in |haystack| smaller than |needle| 85// i is the index of the largest such number otherwise -1; 86// If there is at least one element in |haystack| larger than |needle| 87// j is the index of the smallest such element otherwise -1. 88// 89// So we try to get the indexes of the two data points around needle 90// or -1 if there is no such datapoint. 91export function searchSegment(haystack: Numbers, needle: number): Range { 92 if (!haystack.length) return [-1, -1]; 93 94 const left = search(haystack, needle); 95 if (left === -1) { 96 return [left, 0]; 97 } else if (left + 1 === haystack.length) { 98 return [left, -1]; 99 } else { 100 return [left, left + 1]; 101 } 102} 103