1/* 2 * Copyright (C) 2022 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16type TypedArray = 17 | Int8Array 18 | Uint8Array 19 | Uint8ClampedArray 20 | Int16Array 21 | Uint16Array 22 | Int32Array 23 | Uint32Array 24 | Float32Array 25 | Float64Array; 26 27export class ArrayUtils { 28 static equal<T>( 29 a: T[] | TypedArray, 30 b: T[] | TypedArray, 31 predicate: (a: T | number, b: T | number) => boolean = (a, b) => a === b, 32 ): boolean { 33 if (a.length !== b.length) { 34 return false; 35 } 36 37 for (let i = 0; i < a.length; i++) { 38 if (!predicate(a[i], b[i])) { 39 return false; 40 } 41 } 42 43 return true; 44 } 45 46 static searchSubarray<T>( 47 array: T[] | TypedArray, 48 subarray: T[] | TypedArray, 49 ): number | undefined { 50 for (let i = 0; i + subarray.length <= array.length; ++i) { 51 let match = true; 52 53 for (let j = 0; j < subarray.length; ++j) { 54 if (array[i + j] !== subarray[j]) { 55 match = false; 56 break; 57 } 58 } 59 60 if (match) { 61 return i; 62 } 63 } 64 65 return undefined; 66 } 67 68 static binarySearchFirstGreaterOrEqual<T>( 69 values: T[] | TypedArray, 70 target: T, 71 ): number | undefined { 72 if (values.length === 0) { 73 return undefined; 74 } 75 76 let low = 0; 77 let high = values.length - 1; 78 79 let result: number | undefined = undefined; 80 81 while (low <= high) { 82 const mid = (low + high) >> 1; 83 84 if (values[mid] < target) { 85 low = mid + 1; 86 } else if (values[mid] > target) { 87 if (result === undefined || result > mid) { 88 result = mid; 89 } 90 high = mid - 1; 91 } else { 92 result = mid; 93 high = mid - 1; 94 } 95 } 96 97 return result; 98 } 99 100 static binarySearchFirstGreater<T>( 101 values: T[] | TypedArray, 102 target: T, 103 ): number | undefined { 104 if (values.length === 0) { 105 return undefined; 106 } 107 108 let low = 0; 109 let high = values.length - 1; 110 111 let result: number | undefined = undefined; 112 113 while (low <= high) { 114 const mid = (low + high) >> 1; 115 116 if (values[mid] < target) { 117 low = mid + 1; 118 } else if (values[mid] > target) { 119 if (result === undefined || result > mid) { 120 result = mid; 121 } 122 high = mid - 1; 123 } else { 124 low = mid + 1; 125 } 126 } 127 128 return result; 129 } 130 131 static toUintLittleEndian( 132 buffer: Uint8Array, 133 start: number, 134 end: number, 135 ): bigint { 136 let result = 0n; 137 for (let i = end - 1; i >= start; --i) { 138 result *= 256n; 139 result += BigInt(buffer[i]); 140 } 141 return result; 142 } 143 144 static toIntLittleEndian( 145 buffer: Uint8Array, 146 start: number, 147 end: number, 148 ): bigint { 149 const numOfBits = BigInt(Math.max(0, 8 * (end - start))); 150 if (numOfBits <= 0n) { 151 return 0n; 152 } 153 154 let result = ArrayUtils.toUintLittleEndian(buffer, start, end); 155 const maxSignedValue = 2n ** (numOfBits - 1n) - 1n; 156 if (result > maxSignedValue) { 157 const valuesRange = 2n ** numOfBits; 158 result -= valuesRange; 159 } 160 161 return result; 162 } 163} 164