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/** 65 * Given a sorted array of numbers (|haystack|) and a |needle| return the 66 * half open range [i, j) of indexes where |haystack| is equal to needle. 67 */ 68export function searchEq( 69 haystack: Numbers, needle: number, optRange?: Range): Range { 70 const range = searchRange(haystack, needle, optRange); 71 const [i, j] = range; 72 if (haystack[i] === needle) return range; 73 return [j, j]; 74} 75 76/** 77 * Given a sorted array of numbers (|haystack|) and a |needle| return the 78 * smallest half open range [i, j) of indexes which contains |needle|. 79 */ 80export function searchRange( 81 haystack: Numbers, needle: number, optRange?: Range): Range { 82 const [left, right] = optRange ? optRange : [0, haystack.length]; 83 return searchRangeImpl(haystack, needle, left, right); 84} 85 86/** 87 * Given a sorted array of numbers (|haystack|) and a |needle| return a 88 * pair of indexes [i, j] such that: 89 * If there is at least one element in |haystack| smaller than |needle| 90 * i is the index of the largest such number otherwise -1; 91 * If there is at least one element in |haystack| larger than |needle| 92 * j is the index of the smallest such element otherwise -1. 93 * 94 * So we try to get the indexes of the two data points around needle 95 * or -1 if there is no such datapoint. 96 */ 97export function searchSegment(haystack: Numbers, needle: number): Range { 98 if (!haystack.length) return [-1, -1]; 99 100 const left = search(haystack, needle); 101 if (left === -1) { 102 return [left, 0]; 103 } else if (left + 1 === haystack.length) { 104 return [left, -1]; 105 } else { 106 return [left, left + 1]; 107 } 108} 109