/*! * Copyright (c) 2017-2018 by The Funfix Project Developers. * Some rights reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ import { IllegalArgumentError } from "funfix-core" /** * Given a sorted array, searches for an insert position for a given search * element such that, if inserted in the array at the returned position, * the array would remain sorted. * * @Hidden */ export function arrayBSearchInsertPos(array: Array, f: (a: A) => number): ((search: number) => number) { return search => { let minIndex = 0 let maxIndex = array.length - 1 while (minIndex <= maxIndex) { const index = (minIndex + maxIndex) / 2 | 0 const current = f(array[index]) const next = index + 1 <= maxIndex ? f(array[index + 1]) : undefined if (current <= search && (next === undefined || search < next)) { return index + 1 } else if (current <= search) { minIndex = index + 1 } else { /* if (current > search) */ maxIndex = index - 1 } } return 0 } } /** * Internal utility that builds an iterator out of an `Iterable` or an `Array`. * * @hidden */ export function iterableToArray(values: Iterable): A[] { if (!values) return [] if (Object.prototype.toString.call(values) === "[object Array]") return values as A[] const cursor = values[Symbol.iterator]() const arr: A[] = [] while (true) { const item = cursor.next() if (item.value) arr.push(item.value) if (item.done) return arr } } /** * Natural log of 2. * @hidden */ export const lnOf2 = Math.log(2) /** * Calculates the base 2 logarithm of the given argument. * * @hidden * @return a number such that 2^nr^ is equal to our argument. */ export function log2(x: number): number { return Math.log(x) / lnOf2 } /** * The maximum number that can be returned by {@link nextPowerOf2}. * @hidden */ export const maxPowerOf2: number = 1 << 30 /** * Given a positive integer, returns the next power of 2 that is bigger * than our argument, or the maximum that this function can * return which is 2^30^ (or 1,073,741,824). * * @return an integer that is a power of 2, that is bigger or * equal with our argument and that is "closest" to it. * * @hidden */ export function nextPowerOf2(nr: number): number { if (nr < 0) throw new IllegalArgumentError("nr must be positive") const bit = Math.ceil(log2(nr)) return 1 << (bit > 30 ? 30 : (bit & bit)) }