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 15type Numbers = Float64Array|Uint32Array|number[]; 16type Range = [number, number]; 17 18function searchImpl( 19 haystack: Numbers, needle: number, i: number, j: number): number { 20 if (i === j) return -1; 21 if (i + 1 === j) { 22 return (needle >= haystack[i]) ? i : -1; 23 } 24 25 const mid = Math.floor((j - i) / 2) + i; 26 const midValue = haystack[mid]; 27 if (needle < midValue) { 28 return searchImpl(haystack, needle, i, mid); 29 } else { 30 return searchImpl(haystack, needle, mid, j); 31 } 32} 33 34function searchRangeImpl( 35 haystack: Numbers, needle: number, i: number, j: number): Range { 36 if (i === j) return [i, j]; 37 if (i + 1 === j) { 38 if (haystack[i] <= needle) { 39 return [i, j]; 40 } else { 41 return [i, i]; 42 } 43 } 44 45 const mid = Math.floor((j - i) / 2) + i; 46 const midValue = haystack[mid]; 47 48 if (needle < midValue) { 49 return searchRangeImpl(haystack, needle, i, mid); 50 } else if (needle > midValue) { 51 return searchRangeImpl(haystack, needle, mid, j); 52 } else { 53 while (haystack[i] !== needle) i++; 54 while (haystack[j - 1] !== needle) j--; 55 return [i, j]; 56 } 57} 58 59export function search(haystack: Numbers, needle: number): number { 60 return searchImpl(haystack, needle, 0, haystack.length); 61} 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. 66 */ 67export function searchEq( 68 haystack: Numbers, needle: number, optRange?: Range): Range { 69 const range = searchRange(haystack, needle, optRange); 70 const [i, j] = range; 71 if (haystack[i] === needle) return range; 72 return [j, j]; 73} 74 75/** 76 * Given a sorted array of numbers (|haystack|) and a |needle| return the 77 * smallest half open range [i, j) of indexes which contains |needle|. 78 */ 79export function searchRange( 80 haystack: Numbers, needle: number, optRange?: Range): Range { 81 const [left, right] = optRange ? optRange : [0, haystack.length]; 82 return searchRangeImpl(haystack, needle, left, right); 83} 84 85/** 86 * Given a sorted array of numbers (|haystack|) and a |needle| return a 87 * pair of indexes [i, j] such that: 88 * If there is at least one element in |haystack| smaller than |needle| 89 * i is the index of the largest such number otherwise -1; 90 * If there is at least one element in |haystack| larger than |needle| 91 * j is the index of the smallest such element otherwise -1. 92 * 93 * So we try to get the indexes of the two data points around needle 94 * or -1 if there is no such datapoint. 95 */ 96export function searchSegment(haystack: Numbers, needle: number): Range { 97 if (!haystack.length) return [-1, -1]; 98 99 const left = search(haystack, needle); 100 if (left === -1) { 101 return [left, 0]; 102 } else if (left + 1 === haystack.length) { 103 return [left, -1]; 104 } else { 105 return [left, left + 1]; 106 } 107} 108