# Path: sprinter/lib/dependencytree.py
# class DependencyTree(object):
#     """
#     DependencyTree takes a dictionary of nodes and their dependencies (also need to be included in the dependencies)
#     """
# 
#     order = []  # a valid ordering of the dependency tree
# 
#     def __init__(self, node_dict):
#         self.order = self.__calculate_order(node_dict)
# 
#     def __calculate_order(self, node_dict):
#         """
#         Determine a valid ordering of the nodes in which a node is not called before all of it's dependencies.
# 
#         Raise an error if there is a cycle, or nodes are missing.
#         """
#         if len(node_dict.keys()) != len(set(node_dict.keys())):
#             raise DependencyTreeException("Duplicate Keys Exist in node dictionary!")
#         valid_order = [node for node, dependencies in node_dict.items() if len(dependencies) == 0]
#         remaining_nodes = [node for node in node_dict.keys() if node not in valid_order]
#         while len(remaining_nodes) > 0:
#             node_added = False
#             for node in remaining_nodes:
#                 dependencies = [d for d in node_dict[node] if d not in valid_order]
#                 if len(dependencies) == 0:
#                     valid_order.append(node)
#                     remaining_nodes.remove(node)
#                     node_added = True
#             if not node_added:
#                 # the tree must be invalid, as it was not possible to remove a node.
#                 # it's hard to find all the errors, so just spit out the first one you can find.
#                 invalid_node = remaining_nodes[0]
#                 invalid_dependency = ', '.join(node_dict[invalid_node])
#                 if invalid_dependency not in remaining_nodes:
#                     raise DependencyTreeException(
#                         "Missing dependency! One or more of ({dependency}) are missing for {dependant}.".format(
#                             dependant=invalid_node, dependency=invalid_dependency))
#                 else:
#                     raise DependencyTreeException("The dependency %s is cyclic or dependent on a cyclic dependency" % invalid_dependency)
#         return valid_order
# 
# class DependencyTreeException(Exception):
#     """
#     Wrapper class for dependency tree exceptions
#     """
#     pass


from sprinter.lib.dependencytree import DependencyTree, DependencyTreeException

LEGAL_ORDER = []


class TestDependencyTree(object):

    def test_proper_tree(self):
        """ Test whether a proper dependency tree generated the correct output. """
        dt = DependencyTree(LEGAL_TREE)
        order = dt.order
        added_elements = []
        for el in order:
            for dependency in LEGAL_TREE[el]:
                assert dependency in added_elements, \
                    "Element %s depends on %s and not added yet with order of %s!" % \
                    (el, dependency, added_elements)
            added_elements.append(el)

    def test_missing_entry_tree(self):
        """ Test if dependencytree catches a missing tree """
        try:
            DependencyTree(MISSING_ENTRY_TREE)
        except DependencyTreeException:
            return
        raise("Missing entry tree did not raise an error!")

    def test_cyclic_tree(self):
        """ Test if dependencytree catches a cycle """
        try:
            DependencyTree(CYCLIC_TREE)

# Path: sprinter/lib/dependencytree.py
# class DependencyTree(object):
#     """
#     DependencyTree takes a dictionary of nodes and their dependencies (also need to be included in the dependencies)
#     """
# 
#     order = []  # a valid ordering of the dependency tree
# 
#     def __init__(self, node_dict):
#         self.order = self.__calculate_order(node_dict)
# 
#     def __calculate_order(self, node_dict):
#         """
#         Determine a valid ordering of the nodes in which a node is not called before all of it's dependencies.
# 
#         Raise an error if there is a cycle, or nodes are missing.
#         """
#         if len(node_dict.keys()) != len(set(node_dict.keys())):
#             raise DependencyTreeException("Duplicate Keys Exist in node dictionary!")
#         valid_order = [node for node, dependencies in node_dict.items() if len(dependencies) == 0]
#         remaining_nodes = [node for node in node_dict.keys() if node not in valid_order]
#         while len(remaining_nodes) > 0:
#             node_added = False
#             for node in remaining_nodes:
#                 dependencies = [d for d in node_dict[node] if d not in valid_order]
#                 if len(dependencies) == 0:
#                     valid_order.append(node)
#                     remaining_nodes.remove(node)
#                     node_added = True
#             if not node_added:
#                 # the tree must be invalid, as it was not possible to remove a node.
#                 # it's hard to find all the errors, so just spit out the first one you can find.
#                 invalid_node = remaining_nodes[0]
#                 invalid_dependency = ', '.join(node_dict[invalid_node])
#                 if invalid_dependency not in remaining_nodes:
#                     raise DependencyTreeException(
#                         "Missing dependency! One or more of ({dependency}) are missing for {dependant}.".format(
#                             dependant=invalid_node, dependency=invalid_dependency))
#                 else:
#                     raise DependencyTreeException("The dependency %s is cyclic or dependent on a cyclic dependency" % invalid_dependency)
#         return valid_order
# 
# class DependencyTreeException(Exception):
#     """
#     Wrapper class for dependency tree exceptions
#     """
#     pass


# Path: sprinter/lib/tests/test_dependencytree.py
from sprinter.lib.dependencytree import DependencyTree, DependencyTreeException


LEGAL_ORDER = []


class TestDependencyTree(object):

    def test_proper_tree(self):
        """ Test whether a proper dependency tree generated the correct output. """
        dt = DependencyTree(LEGAL_TREE)
        order = dt.order
        added_elements = []
        for el in order:
            for dependency in LEGAL_TREE[el]:
                assert dependency in added_elements, \
                    "Element %s depends on %s and not added yet with order of %s!" % \
                    (el, dependency, added_elements)
            added_elements.append(el)

    def test_missing_entry_tree(self):
        """ Test if dependencytree catches a missing tree """
        try:
            DependencyTree(MISSING_ENTRY_TREE)
        except DependencyTreeException:
            return
        raise("Missing entry tree did not raise an error!")

    def test_cyclic_tree(self):
        """ Test if dependencytree catches a cycle """
        try:
            DependencyTree(CYCLIC_TREE)

        except DependencyTreeException: