# Path: rebulk/toposort.py
# def toposort(data):
#     """
#     Dependencies are expressed as a dictionary whose keys are items
#     and whose values are a set of dependent items. Output is a list of
#     sets in topological order. The first set consists of items with no
#     dependences, each subsequent set consists of items that depend upon
#     items in the preceeding sets.
#     :param data:
#     :type data:
#     :return:
#     :rtype:
#     """
# 
#     # Special case empty input.
#     if len(data) == 0:
#         return
# 
#     # Copy the input so as to leave it unmodified.
#     data = data.copy()
# 
#     # Ignore self dependencies.
#     for k, v in data.items():
#         v.discard(k)
#     # Find all items that don't depend on anything.
#     extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
#     # Add empty dependences where needed.
#     data.update(dict((item, set()) for item in extra_items_in_deps))
#     while True:
#         ordered = set(item for item, dep in data.items() if len(dep) == 0)
#         if not ordered:
#             break
#         yield ordered
#         data = dict((item, (dep - ordered))
#                 for item, dep in data.items()
#                 if item not in ordered)
#     if len(data) != 0:
#         raise CyclicDependency(data)
# 
# def toposort_flatten(data, sort=True):
#     """
#     Returns a single list of dependencies. For any set returned by
#     toposort(), those items are sorted and appended to the result (just to
#     make the results deterministic).
#     :param data:
#     :type data:
#     :param sort:
#     :type sort:
#     :return: Single list of dependencies.
#     :rtype: list
#     """
# 
#     result = []
#     for d in toposort(data):
#         result.extend((sorted if sort else list)(d))
#     return result
# 
# class CyclicDependency(ValueError):
#     def __init__(self, cyclic):
#         s = 'Cyclic dependencies exist among these items: {0}'.format(', '.join(repr(x) for x in cyclic.items()))
#         super().__init__(s)
#         self.cyclic = cyclic


import pytest
from ..toposort import toposort, toposort_flatten, CyclicDependency
        assert list(toposort({1: set([2]), 3: set([4]), 5: set([6])})) == [set([2, 4, 6]), set([1, 3, 5])]
        assert list(toposort({1: set(), 3: set(), 5: set()})) == [set([1, 3, 5])]

    def test_empty(self):
        assert list(toposort({})) == []

    def test_strings(self):
        results = list(toposort({'2': set(['11']), '9': set(['11', '8']), '10': set(['11', '3']), '11': set(['7', '5']), '8': set(['7', '3'])}))
        expected = [set(['3', '5', '7']), set(['8', '11']), set(['2', '9', '10'])]
        assert results == expected

    def test_objects(self):
        o2 = object()
        o3 = object()
        o5 = object()
        o7 = object()
        o8 = object()
        o9 = object()
        o10 = object()
        o11 = object()
        results = list(toposort({o2: set([o11]), o9: set([o11, o8]), o10: set([o11, o3]), o11: set([o7, o5]), o8: set([o7, o3, o8])}))
        expected = [set([o3, o5, o7]), set([o8, o11]), set([o2, o9, o10])]
        assert results == expected

    def test_cycle(self):
        # a simple, 2 element cycle
        with pytest.raises(CyclicDependency):
            list(toposort({1: set([2]), 2: set([1])}))

        # an indirect cycle

# Path: rebulk/toposort.py
# def toposort(data):
#     """
#     Dependencies are expressed as a dictionary whose keys are items
#     and whose values are a set of dependent items. Output is a list of
#     sets in topological order. The first set consists of items with no
#     dependences, each subsequent set consists of items that depend upon
#     items in the preceeding sets.
#     :param data:
#     :type data:
#     :return:
#     :rtype:
#     """
# 
#     # Special case empty input.
#     if len(data) == 0:
#         return
# 
#     # Copy the input so as to leave it unmodified.
#     data = data.copy()
# 
#     # Ignore self dependencies.
#     for k, v in data.items():
#         v.discard(k)
#     # Find all items that don't depend on anything.
#     extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
#     # Add empty dependences where needed.
#     data.update(dict((item, set()) for item in extra_items_in_deps))
#     while True:
#         ordered = set(item for item, dep in data.items() if len(dep) == 0)
#         if not ordered:
#             break
#         yield ordered
#         data = dict((item, (dep - ordered))
#                 for item, dep in data.items()
#                 if item not in ordered)
#     if len(data) != 0:
#         raise CyclicDependency(data)
# 
# def toposort_flatten(data, sort=True):
#     """
#     Returns a single list of dependencies. For any set returned by
#     toposort(), those items are sorted and appended to the result (just to
#     make the results deterministic).
#     :param data:
#     :type data:
#     :param sort:
#     :type sort:
#     :return: Single list of dependencies.
#     :rtype: list
#     """
# 
#     result = []
#     for d in toposort(data):
#         result.extend((sorted if sort else list)(d))
#     return result
# 
# class CyclicDependency(ValueError):
#     def __init__(self, cyclic):
#         s = 'Cyclic dependencies exist among these items: {0}'.format(', '.join(repr(x) for x in cyclic.items()))
#         super().__init__(s)
#         self.cyclic = cyclic


# Path: rebulk/test/test_toposort.py
import pytest
from ..toposort import toposort, toposort_flatten, CyclicDependency

        assert list(toposort({1: set([2]), 3: set([4]), 5: set([6])})) == [set([2, 4, 6]), set([1, 3, 5])]
        assert list(toposort({1: set(), 3: set(), 5: set()})) == [set([1, 3, 5])]

    def test_empty(self):
        assert list(toposort({})) == []

    def test_strings(self):
        results = list(toposort({'2': set(['11']), '9': set(['11', '8']), '10': set(['11', '3']), '11': set(['7', '5']), '8': set(['7', '3'])}))
        expected = [set(['3', '5', '7']), set(['8', '11']), set(['2', '9', '10'])]
        assert results == expected

    def test_objects(self):
        o2 = object()
        o3 = object()
        o5 = object()
        o7 = object()
        o8 = object()
        o9 = object()
        o10 = object()
        o11 = object()
        results = list(toposort({o2: set([o11]), o9: set([o11, o8]), o10: set([o11, o3]), o11: set([o7, o5]), o8: set([o7, o3, o8])}))
        expected = [set([o3, o5, o7]), set([o8, o11]), set([o2, o9, o10])]
        assert results == expected

    def test_cycle(self):
        # a simple, 2 element cycle
        with pytest.raises(CyclicDependency):
            list(toposort({1: set([2]), 2: set([1])}))

        # an indirect cycle

        with pytest.raises(CyclicDependency):