-
Notifications
You must be signed in to change notification settings - Fork 892
/
problem_024.py
72 lines (59 loc) · 1.64 KB
/
problem_024.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
def is_parent_locked(node):
if not node.parent:
return False
elif node.parent.locked:
return True
return is_parent_locked(node.parent)
def update_parent(node, enable_locks):
increment = 1 if enable_locks else -1
if node.parent:
node.parent.locked_descendants += increment
update_parent(node.parent, enable_locks)
class Node:
def __init__(self, val, parent):
self.val = val
self.parent = parent
self.left = None
self.right = None
self.locked = False
self.locked_descendants = 0
def __str__(self):
return "val={}; locked={}; locked_descendants={}".format(
self.val, self.locked, self.locked_descendants)
def lock(self):
if is_parent_locked(self) or self.locked_descendants:
return False
else:
self.locked = True
update_parent(node=self, enable_locks=True)
return True
def unlock(self):
if is_parent_locked(self) or self.locked_descendants:
return False
else:
self.locked = False
update_parent(node=self, enable_locks=False)
return True
def is_locked(self):
return self.locked
a = Node("a", None)
b = Node("b", a)
c = Node("c", a)
d = Node("d", b)
e = Node("e", b)
f = Node("f", c)
g = Node("g", c)
assert b.lock()
assert b.is_locked()
assert c.lock()
assert b.unlock()
assert not b.is_locked()
assert d.lock()
assert not g.lock()
assert c.unlock()
assert g.lock()
assert f.lock()
assert e.lock()
assert a.locked_descendants == 4
assert b.locked_descendants == 2
assert c.locked_descendants == 2