# Path: common/data_structures.py
# class Node(object):
# 
#     def __init__(self):
#         self.children = list()
# 
#     def add_child(self, child):
#         self.children.append(child)
# 
#     def get_child(self, index):
#         return self.children[index]
# 
#     def __iter__(self):
#         return iter(self.children)
# 
#     def __eq__(self, other):
#         return self.value == other.value
# 
# Path: search/uninformed_search.py
# def bfs(node, target, comparator=lambda x, y: x == y):
#     queue = [node]
#     visited_nodes = []
# 
#     while len(queue) != 0:
#         current_node = queue.pop(0)
#         if current_node not in visited_nodes:
#             if comparator(current_node.value, target):
#                 return current_node
#             queue.extend(current_node)
#             visited_nodes.append(current_node)
# 
#     return None
# 
# def dfs(node, target, comparator=lambda x, y: x == y):
#     queue = [node]
#     visited_nodes = []
# 
#     while len(queue) != 0:
#         current_node = queue.pop()
#         if current_node not in visited_nodes:
#             if comparator(current_node.value, target):
#                 return current_node
#             queue.extend(current_node)
#             visited_nodes.append(current_node)
# 
#     return None
# 
# def iterative_deepening_search(node, target, comparator=lambda x, y: x == y):
#     level = 0
#     found_level = 0
# 
#     while level == found_level:
#         level += 1
#         result, found_level = dls(node, target, level, comparator)
#         if result is not None:
#             return result
# 
# 
#     return None


from unittest import TestCase
from common.data_structures import Node
from search.uninformed_search import bfs, dfs, iterative_deepening_search

    def test_tree_with_comparator1(self):
        node = UninformedSearchTest.prepare_tree1()
        result = self.algorithm(node, 5, comparator=lambda x, y: int(x) == y)
        self.assertTrue(result.value == '5')

    def test_graph1(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '1')
        self.assertTrue(result.value == '1')

    def test_graph2(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '10')
        self.assertTrue(result is None)

    def test_graph3(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '5')
        self.assertTrue(result.value == '5')

    def test_graph4(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '6')
        self.assertTrue(result.value == '6')


class BfsTest(UninformedSearchTest, TestCase):

    def setUp(self):

# Path: common/data_structures.py
# class Node(object):
# 
#     def __init__(self):
#         self.children = list()
# 
#     def add_child(self, child):
#         self.children.append(child)
# 
#     def get_child(self, index):
#         return self.children[index]
# 
#     def __iter__(self):
#         return iter(self.children)
# 
#     def __eq__(self, other):
#         return self.value == other.value
# 
# Path: search/uninformed_search.py
# def bfs(node, target, comparator=lambda x, y: x == y):
#     queue = [node]
#     visited_nodes = []
# 
#     while len(queue) != 0:
#         current_node = queue.pop(0)
#         if current_node not in visited_nodes:
#             if comparator(current_node.value, target):
#                 return current_node
#             queue.extend(current_node)
#             visited_nodes.append(current_node)
# 
#     return None
# 
# def dfs(node, target, comparator=lambda x, y: x == y):
#     queue = [node]
#     visited_nodes = []
# 
#     while len(queue) != 0:
#         current_node = queue.pop()
#         if current_node not in visited_nodes:
#             if comparator(current_node.value, target):
#                 return current_node
#             queue.extend(current_node)
#             visited_nodes.append(current_node)
# 
#     return None
# 
# def iterative_deepening_search(node, target, comparator=lambda x, y: x == y):
#     level = 0
#     found_level = 0
# 
#     while level == found_level:
#         level += 1
#         result, found_level = dls(node, target, level, comparator)
#         if result is not None:
#             return result
# 
# 
#     return None


# Path: tests/search/uninformed_search_test.py
from unittest import TestCase
from common.data_structures import Node
from search.uninformed_search import bfs, dfs, iterative_deepening_search


    def test_tree_with_comparator1(self):
        node = UninformedSearchTest.prepare_tree1()
        result = self.algorithm(node, 5, comparator=lambda x, y: int(x) == y)
        self.assertTrue(result.value == '5')

    def test_graph1(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '1')
        self.assertTrue(result.value == '1')

    def test_graph2(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '10')
        self.assertTrue(result is None)

    def test_graph3(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '5')
        self.assertTrue(result.value == '5')

    def test_graph4(self):
        node = UninformedSearchTest.prepare_graph1()
        result = self.algorithm(node, '6')
        self.assertTrue(result.value == '6')


class BfsTest(UninformedSearchTest, TestCase):

    def setUp(self):

        self.algorithm = bfs