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

export class PriorityQueue<T> {
  private compareFn: ICompareFn<T>;
  private data: T[];

  constructor(compareFn?: ICompareFn<T>);
  constructor(items: T[], compareFn?: ICompareFn<T>);
  constructor(...args: any[]) {
    const [arg0 = defaultCompareFn, arg1 = defaultCompareFn] = args;

    if (Array.isArray(arg0)) {
      this.compareFn = arg1;
      this.data = [];

      for (let i = 0, l = arg0.length; i < l; ++i) {
        this.insert(arg0[i]);
      }
    } else {
      this.compareFn = arg0;
      this.data = [];
    }
  }

  private exch(i: number, j: number) {
    const tmp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = tmp;
  }

  private less(i: number, j: number) {
    return this.compareFn(this.data[i], this.data[j]) > 0;
  }

  private swim(i: number) {
    while (i > 1 && this.less(i >> 1, i)) {
      this.exch(i >> 1, i);
      i >>= 1;
    }
  }

  private sink(i: number) {
    const N = this.size();

    while (2 * i <= N) {
      let j = 2 * i;
      if (j < N && this.less(j, j + 1)) j++;
      if (!this.less(i, j)) break;
      this.exch(i, j);
      i = j;
    }
  }

  public insert(val: T) {
    const i = this.size() + 1;
    this.data[i] = val;
    this.swim(i);
  }

  public top(): T | null {
    return this.isEmpty() ? null : this.data[1];
  }

  public delTop(): T | null {
    if (this.isEmpty()) {
      return null;
    } else {
      const N = this.size();

      this.data[0] = this.data[1];
      this.data[1] = this.data[N];
      this.data.length = N;

      if (N > 1) {
        this.sink(1);
      }

      return this.data[0];
    }
  }

  public size(): number {
    return Math.max(0, this.data.length - 1);
  }

  public isEmpty(): boolean {
    return this.size() === 0;
  }
}