import sys, os
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from toposort_kahn import toposort

def test_dag():
    g = {"a":["b","c"],"b":["d"],"c":["d"],"d":[]}
    o,c = toposort(g)
    assert c is None
    # a before b,c; d last
    assert o.index("a") < o.index("b")
    assert o.index("a") < o.index("c")
    assert o.index("b") < o.index("d")
    assert o.index("c") < o.index("d")
    print("dag ok", o)

def test_cycle():
    g = {"a":["b"],"b":["c"],"c":["a"]}
    o,c = toposort(g)
    assert c is not None
    assert set(c[:-1]) <= {"a","b","c"}
    print("cycle ok", c)

def test_empty():
    o,c = toposort({})
    assert o == [] and c is None
    print("empty ok")

def test_single():
    o,c = toposort({"x":[]})
    assert o == ["x"] and c is None
    print("single ok")

def test_disconnected():
    g = {"a":[],"b":[]}
    o,c = toposort(g)
    assert c is None and o == ["a","b"]
    print("disconnected ok", o)

if __name__ == "__main__":
    test_dag(); test_cycle(); test_empty(); test_single(); test_disconnected()
    print("ALL PASS")