import { rand, PriorityQueue, defaultCompareFn } from '../../src';

describe('Test New PriorityQueue', () => {
  test('new ()', () => {
    const p = new PriorityQueue();
    expect(p.top()).toBe(null);
    expect(p.delTop()).toBe(null);
    expect(p.size()).toBe(0);
    expect(p.isEmpty()).toBe(true);
  });

  test('new (items)', () => {
    const n = 20;
    const d = rand.intArray(n);
    const p = new PriorityQueue(d);
    expect(p.size()).toBe(n);
    expect(p.isEmpty()).toBe(false);

    for (let i = 0; i < n; ++i) {
      expect(p.top()).toBe(i);
      expect(p.delTop()).toBe(i);
    }

    expect(p.size()).toBe(0);
    expect(p.isEmpty()).toBe(true);
  });
});

describe('Test Sort.', () => {
  test('random number duplicate array.', () => {
    const N = 60;
    const c = 40;
    const d = rand.array(() => rand.int(c), N);
    const p = new PriorityQueue<number>(defaultCompareFn);
    const dSorted = d.sort(defaultCompareFn);

    for (let i = 0; i < N; ++i) {
      p.insert(d[i]);
    }
    for (let i = 0; i < N; ++i) {
      expect(p.delTop()).toBe(dSorted[i]);
    }
  });

  test('random number not duplicate array.', () => {
    const N = 60;
    const d = rand.intArray(N);
    const p = new PriorityQueue<number>(defaultCompareFn);
    const dSorted = d.sort(defaultCompareFn);

    for (let i = 0; i < N; ++i) {
      p.insert(d[i]);
    }
    for (let i = 0; i < N; ++i) {
      expect(p.delTop()).toBe(dSorted[i]);
    }
  });
});

describe('Test Algorithm', () => {
  test('eval topK.', () => {
    const n = 50;
    const k = 10;
    const d = rand.intArray(n);
    const r = d
      .slice(0)
      .sort((a: number, b: number) => a - b)
      .slice(0, k);
    const p = new PriorityQueue<number>((a: number, b: number) => b - a);

    for (let i = 0; i < n; ++i) {
      if (p.size() < k) {
        p.insert(d[i]);
      } else {
        if (d[i] < p.top()!) {
          p.delTop();
          p.insert(d[i]);
        }
      }
    }

    expect(p.size()).toBe(k);

    for (let i = k - 1; i >= 0; --i) {
      expect(p.delTop()).toBe(r[i]);
    }

    expect(p.isEmpty()).toBe(true);
  });
});