import { AutomationPoint } from './derivedTiming';

/**
 * Binary search that returns the index of the first element >= target.
 * If no such element exists, returns arr.length.
 */
export function binarySearchUpperBound(
  arr: AutomationPoint[],
  target: number
): number {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = (low + high) >>> 1;
    const midVal = arr[mid].beats;
    if (midVal < target) {
      low = mid + 1;
    } else if (midVal > target) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return low;
}

/**
 * Binary search that returns the index of the last element < target.
 * Result is clamped to [0, length - 1].
 */
export function binarySearchLowerBound<T>(
  arr: T[],
  length: number,
  target: number,
  getElement?: (v: T) => number
): number {
  let low = 0;
  let high = length - 1;
  while (low <= high) {
    const mid = (low + high) >>> 1;
    const midVal = getElement ? getElement(arr[mid]) : (arr[mid] as number);
    if (midVal < target) {
      low = mid + 1;
    } else if (midVal > target) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  if (low <= 0) {
    return 0;
  } else if (low > length - 1) {
    return length - 1;
  } else {
    return low - 1;
  }
}

/**
 * Binary search for Float32Array that returns the index of the last element < target.
 * Result is clamped to [0, length - 1].
 */
export function binarySearchFloat32Array(
  arr: Float32Array,
  length: number,
  target: number
): number {
  let low = 0;
  let high = length - 1;
  while (low <= high) {
    const mid = (low + high) >>> 1;
    const midVal = arr[mid];
    if (midVal < target) {
      low = mid + 1;
    } else if (midVal > target) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  if (low <= 0) {
    return 0;
  } else if (low > length - 1) {
    return length - 1;
  } else {
    return low - 1;
  }
}