function shuffle<T>(array: T[]): T[] {
  const shuffled = [...array];
  for (let i = shuffled.length - 1; i > 0; i -= 1) {
    const j = Math.floor(Math.random() * (i + 1));
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
  }
  return shuffled;
}

function reservoirSampling<T>(stream: T[], k: number): T[] {
  const reservoir: T[] = [];

  // 填充前 k 个元素
  for (let i = 0; i < k && i < stream.length; i += 1) {
    reservoir.push(stream[i]);
  }

  // 对剩余元素进行随机替换
  for (let i = k; i < stream.length; i += 1) {
    const j = Math.floor(Math.random() * (i + 1));
    if (j < k) {
      reservoir[j] = stream[i];
    }
  }

  return reservoir;
}

function quickSelect<T>(arr: T[], k: number, compare: (a: T, b: T) => number): T {
  if (arr.length === 1) return arr[0];

  const pivotIndex = Math.floor(Math.random() * arr.length);
  const pivot = arr[pivotIndex];

  const left: T[] = [];
  const right: T[] = [];
  const equal: T[] = [];

  for (const item of arr) {
    const cmp = compare(item, pivot);
    if (cmp < 0) left.push(item);
    else if (cmp > 0) right.push(item);
    else equal.push(item);
  }

  if (k < left.length) {
    return quickSelect(left, k, compare);
  } else if (k < left.length + equal.length) {
    return pivot;
  } else {
    return quickSelect(right, k - left.length - equal.length, compare);
  }
}

function estimatePi(numPoints: number): number {
  let insideCircle = 0;

  for (let i = 0; i < numPoints; i += 1) {
    const x = Math.random();
    const y = Math.random();

    if (x * x + y * y <= 1) {
      insideCircle += 1;
    }
  }

  return (insideCircle / numPoints) * 4;
}

function randomizedQuickSort<T>(arr: T[], compare: (a: T, b: T) => number): T[] {
  if (arr.length <= 1) return arr;

  const pivotIndex = Math.floor(Math.random() * arr.length);
  const pivot = arr[pivotIndex];

  const left: T[] = [];
  const right: T[] = [];

  for (let i = 0; i < arr.length; i += 1) {
    if (i === pivotIndex) continue;
    if (compare(arr[i], pivot) <= 0) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...randomizedQuickSort(left, compare), pivot, ...randomizedQuickSort(right, compare)];
}

class Random {
  private seed: number;

  constructor(seed?: number) {
    this.seed = seed ?? Math.floor(Math.random() * 1000000);
  }

  next(): number {
    this.seed = (this.seed * 9301 + 49297) % 233280;
    return this.seed / 233280;
  }

  nextInt(min: number, max: number): number {
    return Math.floor(this.next() * (max - min + 1)) + min;
  }
}