-
Notifications
You must be signed in to change notification settings - Fork 287
/
Copy pathprune_tree.py
125 lines (93 loc) · 4.44 KB
/
prune_tree.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
from tree import Tree
def prune_tree(tree, keys_to_discard):
'''
Returns a new tree with that is identical to the original tree, except
that any node whose key is in keys_to_discard is removed, along with its
descendants. If the key of the root is in keys_to_discard, then
<replace this with a description of how your code behaves in this case>
Inputs:
tree: a Tree instance.
keys_to_discard: set of keys.
Returns: (Tree) the pruned tree.
'''
pass
#############################################################
### ###
### Testing code. ###
### !!! DO NOT MODIFY ANY CODE BELOW THIS POINT !!! ###
### ###
#############################################################
import sys
import pytest
import util
sys.path.append('../')
import test_utils as utils
import tree_test_utils as tree_utils
def do_test_prune_tree(trees_original_expected, tree_name, keys_to_prune):
trees, original_trees, expected_trees = trees_original_expected
recreate_msg = tree_utils.gen_recreate_msg_with_trees('prune_tree',
tree_name, keys_to_prune)
actual = prune_tree(trees[tree_name], keys_to_prune)
utils.check_none(actual, recreate_msg)
utils.check_type(actual, expected_trees[tree_name], recreate_msg)
tree_utils.check_tree_equals(actual, expected_trees[tree_name], recreate_msg)
tree_utils.check_tree_unmodified(trees[tree_name], original_trees[tree_name],
recreate_msg)
def test_prune_tree_1(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_1", {'D', 'B'})
def test_prune_tree_2(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_2", {'C', 'E'})
def test_prune_tree_3(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_3", {'E'})
def test_prune_tree_4(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_4", {'b', 'I', 'J', 'c', 'M'})
def test_prune_tree_5(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_5", {'Q', 'G', 'C'})
def test_prune_tree_6(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_6", {'V2'})
def test_prune_tree_7(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_7", {'V9'})
def test_prune_tree_8(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_8", set())
def test_prune_tree_9(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_9", {'V9', 'V8'})
def test_prune_tree_10(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_10",
{'V11', 'V8', 'V7', 'V4', 'V5'})
def test_prune_tree_11(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_11", {'V80', 'V90'})
def test_prune_tree_12(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_12",
{'V26', 'V9', 'V1', 'V6', 'V27'})
def test_prune_tree_13(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_13", {'V0', 'V1', 'V4', 'V3'})
def test_prune_tree_14(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_14",
{'V2', 'V0', 'V1', 'V7', 'V4', 'V6', 'V3', 'V5'})
def test_prune_tree_15(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_15",
{'V2', 'V48', 'V49', 'V46', 'V45', 'V47'})
def test_prune_tree_16(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_16", {'V10', 'V20', 'V30'})
def test_prune_tree_17(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_17", {'V3', 'V7'})
def test_prune_tree_18(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_18",
{'V26', 'V27', 'V24', 'V21', 'V28', 'V25', 'V23', 'V22'})
def test_prune_tree_19(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_19", {'V18'})
def test_prune_tree_20(trees_prune_tree):
do_test_prune_tree(trees_prune_tree, "tree_20",
{'V12', 'V42', 'V46', 'V7', 'V30', 'V29', 'V60', 'V17', 'V36'})
@pytest.fixture(scope="session")
def trees_prune_tree():
"""
Fixture for loading the trees for prune_tree
"""
trees, original_trees = get_trees()
expected_trees = util.load_trees("sample_trees_pruned.json")
return trees, original_trees, expected_trees
def get_trees():
trees = util.load_trees("sample_trees.json")
original_trees = util.load_trees("sample_trees.json")
return trees, original_trees