from galaxy.util import topsort


def test_topsort_level_stability():
    data = [
        (0, 2),
        (1, 2),
        (2, 3),
        (2, 4),
        (3, 4),
        (3, 5),
        (6, 2),
    ]
    assert topsort.topsort_levels( data )[ 0 ] == [ 0, 1, 6 ]
    assert topsort.topsort( data ) == [ 0, 1, 6, 2, 3, 4, 5 ]
    # Swap first two edges - so 1 appears first
    swap( data, 0, 1 )
    assert topsort.topsort_levels( data )[ 0 ] == [ 1, 0, 6 ]
    assert topsort.topsort( data ) == [ 1, 0, 6, 2, 3, 4, 5 ]

    # Shouldn't really affect sorting of 1 0 6
    swap( data, 3, 4 )
    assert topsort.topsort_levels( data )[ 0 ] == [ 1, 0, 6 ]
    assert topsort.topsort( data ) == [ 1, 0, 6, 2, 3, 4, 5 ]

    # Place 0 before 6 in original list
    swap( data, 1, 6 )
    assert topsort.topsort_levels( data )[ 0 ] == [ 1, 6, 0 ]
    assert topsort.topsort( data ) == [ 1, 6, 0, 2, 3, 4, 5 ]


def test_topsort_doc():
    assert topsort.topsort([(1, 2), (3, 3)]) == [1, 3, 2]


def swap(lst, i, j):
    tmp = lst[j]
    lst[j] = lst[i]
    lst[i] = tmp