-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathpov_test.py
173 lines (152 loc) · 6.2 KB
/
pov_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
# These tests are auto-generated with test data from:
# https://github.com/exercism/problem-specifications/tree/main/exercises/pov/canonical-data.json
# File last updated on 2023-07-19
import unittest
from pov import (
Tree,
)
class PovTest(unittest.TestCase):
def test_results_in_the_same_tree_if_the_input_tree_is_a_singleton(self):
tree = Tree("x")
expected = Tree("x")
self.assertTreeEquals(tree.from_pov("x"), expected)
def test_can_reroot_a_tree_with_a_parent_and_one_sibling(self):
tree = Tree("parent", [Tree("x"), Tree("sibling")])
expected = Tree("x", [Tree("parent", [Tree("sibling")])])
self.assertTreeEquals(tree.from_pov("x"), expected)
def test_can_reroot_a_tree_with_a_parent_and_many_siblings(self):
tree = Tree("parent", [Tree("a"), Tree("x"), Tree("b"), Tree("c")])
expected = Tree("x", [Tree("parent", [Tree("a"), Tree("b"), Tree("c")])])
self.assertTreeEquals(tree.from_pov("x"), expected)
def test_can_reroot_a_tree_with_new_root_deeply_nested_in_tree(self):
tree = Tree(
"level-0",
[Tree("level-1", [Tree("level-2", [Tree("level-3", [Tree("x")])])])],
)
expected = Tree(
"x",
[Tree("level-3", [Tree("level-2", [Tree("level-1", [Tree("level-0")])])])],
)
self.assertTreeEquals(tree.from_pov("x"), expected)
def test_moves_children_of_the_new_root_to_same_level_as_former_parent(self):
tree = Tree("parent", [Tree("x", [Tree("kid-0"), Tree("kid-1")])])
expected = Tree("x", [Tree("kid-0"), Tree("kid-1"), Tree("parent")])
self.assertTreeEquals(tree.from_pov("x"), expected)
def test_can_reroot_a_complex_tree_with_cousins(self):
tree = Tree(
"grandparent",
[
Tree(
"parent",
[
Tree("x", [Tree("kid-0"), Tree("kid-1")]),
Tree("sibling-0"),
Tree("sibling-1"),
],
),
Tree("uncle", [Tree("cousin-0"), Tree("cousin-1")]),
],
)
expected = Tree(
"x",
[
Tree("kid-1"),
Tree("kid-0"),
Tree(
"parent",
[
Tree("sibling-0"),
Tree("sibling-1"),
Tree(
"grandparent",
[Tree("uncle", [Tree("cousin-0"), Tree("cousin-1")])],
),
],
),
],
)
self.assertTreeEquals(tree.from_pov("x"), expected)
def test_errors_if_target_does_not_exist_in_a_singleton_tree(self):
tree = Tree("x")
with self.assertRaises(ValueError) as err:
tree.from_pov("nonexistent")
self.assertEqual(type(err.exception), ValueError)
self.assertEqual(err.exception.args[0], "Tree could not be reoriented")
def test_errors_if_target_does_not_exist_in_a_large_tree(self):
tree = Tree(
"parent",
[
Tree("x", [Tree("kid-0"), Tree("kid-1")]),
Tree("sibling-0"),
Tree("sibling-1"),
],
)
with self.assertRaises(ValueError) as err:
tree.from_pov("nonexistent")
self.assertEqual(type(err.exception), ValueError)
self.assertEqual(err.exception.args[0], "Tree could not be reoriented")
def test_can_find_path_to_parent(self):
tree = Tree("parent", [Tree("x"), Tree("sibling")])
expected = ["x", "parent"]
self.assertEqual(tree.path_to("x", "parent"), expected)
def test_can_find_path_to_sibling(self):
tree = Tree("parent", [Tree("a"), Tree("x"), Tree("b"), Tree("c")])
expected = ["x", "parent", "b"]
self.assertEqual(tree.path_to("x", "b"), expected)
def test_can_find_path_to_cousin(self):
tree = Tree(
"grandparent",
[
Tree(
"parent",
[
Tree("x", [Tree("kid-0"), Tree("kid-1")]),
Tree("sibling-0"),
Tree("sibling-1"),
],
),
Tree("uncle", [Tree("cousin-0"), Tree("cousin-1")]),
],
)
expected = ["x", "parent", "grandparent", "uncle", "cousin-1"]
self.assertEqual(tree.path_to("x", "cousin-1"), expected)
def test_can_find_path_not_involving_root(self):
tree = Tree(
"grandparent",
[Tree("parent", [Tree("x"), Tree("sibling-0"), Tree("sibling-1")])],
)
expected = ["x", "parent", "sibling-1"]
self.assertEqual(tree.path_to("x", "sibling-1"), expected)
def test_can_find_path_from_nodes_other_than_x(self):
tree = Tree("parent", [Tree("a"), Tree("x"), Tree("b"), Tree("c")])
expected = ["a", "parent", "c"]
self.assertEqual(tree.path_to("a", "c"), expected)
def test_errors_if_destination_does_not_exist(self):
tree = Tree(
"parent",
[
Tree("x", [Tree("kid-0"), Tree("kid-1")]),
Tree("sibling-0"),
Tree("sibling-1"),
],
)
with self.assertRaises(ValueError) as err:
tree.path_to("x", "nonexistent")
self.assertEqual(type(err.exception), ValueError)
self.assertEqual(err.exception.args[0], "No path found")
def test_errors_if_source_does_not_exist(self):
tree = Tree(
"parent",
[
Tree("x", [Tree("kid-0"), Tree("kid-1")]),
Tree("sibling-0"),
Tree("sibling-1"),
],
)
with self.assertRaises(ValueError) as err:
tree.path_to("nonexistent", "x")
self.assertEqual(type(err.exception), ValueError)
self.assertEqual(err.exception.args[0], "Tree could not be reoriented")
# Custom Utility Functions
def assertTreeEquals(self, result, expected):
self.assertEqual(result, expected, "{} != {}".format(result, expected))