forked from aosabook/500lines
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtest_binary_tree.py
More file actions
122 lines (99 loc) · 3.36 KB
/
Copy pathtest_binary_tree.py
File metadata and controls
122 lines (99 loc) · 3.36 KB
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
import pickle
import random
from nose.tools import assert_raises, eq_
from dbdb.binary_tree import BinaryNode, BinaryTree, BinaryNodeRef, ValueRef
class StubStorage(object):
def __init__(self):
self.d = [0]
self.locked = False
def lock(self):
if not self.locked:
self.locked = True
return True
else:
return False
def unlock(self):
pass
def get_root_address(self):
return 0
def write(self, string):
address = len(self.d)
self.d.append(string)
return address
def read(self, address):
return self.d[address]
class TestBinaryTree(object):
def setup(self):
self.tree = BinaryTree(StubStorage())
def test_get_missing_key_raises_key_error(self):
with assert_raises(KeyError):
self.tree.get('Not A Key In The Tree')
def test_set_and_get_key(self):
self.tree.set('a', 'b')
eq_(self.tree.get('a'), 'b')
def test_random_set_and_get_keys(self):
ten_k = list(range(10000))
pairs = list(zip(random.sample(ten_k, 10), random.sample(ten_k, 10)))
for i, (k, v) in enumerate(pairs, start=1):
self.tree.set(k, v)
eq_(len(self.tree), i)
for k, v in pairs:
eq_(self.tree.get(k), v)
random.shuffle(pairs)
for i, (k, v) in enumerate(pairs, start=1):
self.tree.pop(k)
eq_(len(self.tree), len(pairs) - i)
def test_overwrite_and_get_key(self):
self.tree.set('a', 'b')
self.tree.set('a', 'c')
eq_(self.tree.get('a'), 'c')
def test_pop_non_existent_key(self):
with assert_raises(KeyError):
self.tree.pop('Not A Key In The Tree')
def test_del_leaf_key(self):
self.tree.set('b', '2')
self.tree.pop('b')
with assert_raises(KeyError):
self.tree.get('b')
def test_del_left_node_key(self):
self.tree.set('b', '2')
self.tree.set('a', '1')
self.tree.pop('b')
with assert_raises(KeyError):
self.tree.get('b')
self.tree.get('a')
def test_del_right_node_key(self):
self.tree.set('b', '2')
self.tree.set('c', '3')
self.tree.pop('b')
with assert_raises(KeyError):
self.tree.get('b')
self.tree.get('c')
def test_del_full_node_key(self):
self.tree.set('b', '2')
self.tree.set('a', '1')
self.tree.set('c', '3')
self.tree.pop('b')
with assert_raises(KeyError):
self.tree.get('b')
self.tree.get('a')
self.tree.get('c')
class TestBinaryNodeRef(object):
def test_to_string_leaf(self):
n = BinaryNode(BinaryNodeRef(), 'k', ValueRef(address=999), BinaryNodeRef(), 1)
pickled = BinaryNodeRef.referent_to_string(n)
d = pickle.loads(pickled)
eq_(d['left'], 0)
eq_(d['key'], 'k')
eq_(d['value'], 999)
eq_(d['right'], 0)
def test_to_string_nonleaf(self):
left_ref = BinaryNodeRef(address=123)
right_ref = BinaryNodeRef(address=321)
n = BinaryNode(left_ref, 'k', ValueRef(address=999), right_ref, 3)
pickled = BinaryNodeRef.referent_to_string(n)
d = pickle.loads(pickled)
eq_(d['left'], 123)
eq_(d['key'], 'k')
eq_(d['value'], 999)
eq_(d['right'], 321)