const assert = require('chai').assert;

const { toposort, CyclicalDependencyError } = require('./toposort.js');

describe('toposort', () => {
  it('should be sorted correctly', () => {
    assert.deepEqual(
      toposort([
        ['3', '2'],
        ['2', '1'],
        ['6', '5'],
        ['5', '2'],
        ['5', '4'],
      ]),
      ['3', '6', '5', '2', '1', '4']
    );
  });

  it('error on simple cyclic graphs', () => {
    assert.throws(() => {
      toposort([
        ['foo', 'bar'],
        ['bar', 'foo'], // cyclic dependency
      ]);
    }, CyclicalDependencyError);
  });

  it('error on complex cyclic graphs', () => {
    assert.throws(() => {
      toposort([
        ['foo', 'bar'],
        ['bar', 'ron'],
        ['john', 'bar'],
        ['tom', 'john'],
        ['ron', 'tom'], // cyclic dependency
      ]);
    }, CyclicalDependencyError);
  });

  it('should sort triangular dependency', () => {
    assert.deepEqual(
      toposort([
        ['a', 'b'],
        ['a', 'c'],
        ['b', 'c'],
      ]),
      ['a', 'b', 'c']
    );
  });

  it('should sort giant graphs quickly', () => {
    const graph = [];
    for (let i = 0; i < 100000; i++) {
      graph.push([i, i + 1]);
    }

    const start = Date.now();
    toposort(graph);
    const end = Date.now();

    assert.isBelow(end - start, 1000);
  });

  it('should handle objects', () => {
    const o1 = { k1: 'v1', nested: { k2: 'v2' } };
    const o2 = { k2: 'v2' };
    const o3 = { k3: 'v3' };
    assert.deepEqual(
      toposort([
        [o1, o2],
        [o2, o3],
      ]),
      [{ k1: 'v1', nested: { k2: 'v2' } }, { k2: 'v2' }, { k3: 'v3' }]
    );
  });
});