import { ICompareFn } from '../common';
import { defaultCompareFn } from './common';

export function quickSelect<T>(data: T[], k: number, compareFn: ICompareFn<T> = defaultCompareFn): T | null {
  let a = 0;
  let b = data.length - 1;

  if (b < 0 || k <= 0 || k > b + 1) {
    return null;
  }

  while (true) {
    const v = data[a];
    let l = a;
    let r = b;

    while (l < r) {
      while (l < r && compareFn(v, data[r]) <= 0) r--;
      data[l] = data[r];
      while (l < r && compareFn(v, data[l]) >= 0) l++;
      data[r] = data[l];
    }

    data[l] = v;

    if (l + 1 === k) return v;
    else if (l + 1 > k) b = l - 1;
    else a = l + 1;
  }
}