-
Notifications
You must be signed in to change notification settings - Fork 14
/
Binary_tree_lock.cpp
94 lines (83 loc) · 2.35 KB
/
Binary_tree_lock.cpp
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
// Copyright (c) 2013 Elements of Programming Interviews. All rights reserved.
#include <cassert>
#include <iostream>
#include <memory>
using std::boolalpha;
using std::cout;
using std::endl;
using std::make_shared;
using std::shared_ptr;
// @include
class BinaryTreeNode {
public:
bool isLocked() const { return locked_; }
void lock() {
if (numChildreLocks_ == 0 && !locked_) {
// Make sure all parents do not lock.
shared_ptr<BinaryTreeNode> n = parent_;
while (n) {
if (n->locked_) {
return;
}
n = n->parent_;
}
// Lock itself and update its parents.
locked_ = true;
n = parent_;
while (n) {
++n->numChildreLocks_;
n = n->parent_;
}
}
}
void unLock() {
if (locked_) {
// Unlock itself and update its parents.
locked_ = false;
shared_ptr<BinaryTreeNode> n = parent_;
while (n) {
--n->numChildreLocks_;
n = n->parent_;
}
}
}
// @exclude
shared_ptr<BinaryTreeNode>& left() { return left_; }
shared_ptr<BinaryTreeNode>& right() { return right_; }
shared_ptr<BinaryTreeNode>& parent() { return parent_; }
// @include
private:
shared_ptr<BinaryTreeNode> left_, right_, parent_;
bool locked_;
int numChildreLocks_;
};
// @exclude
int main(int argc, char* argv[]) {
auto root = make_shared<BinaryTreeNode>(BinaryTreeNode());
root->left() = make_shared<BinaryTreeNode>(BinaryTreeNode());
root->left()->parent() = root;
root->right() = make_shared<BinaryTreeNode>(BinaryTreeNode());
root->right()->parent() = root;
root->left()->left() = make_shared<BinaryTreeNode>(BinaryTreeNode());
root->left()->left()->parent() = root->left();
root->left()->right() = make_shared<BinaryTreeNode>(BinaryTreeNode());
root->left()->right()->parent() = root->left();
// Should output false.
assert(!root->isLocked());
cout << boolalpha << root->isLocked() << endl;
root->lock();
// Should output true.
assert(root->isLocked());
cout << boolalpha << root->isLocked() << endl;
root->unLock();
root->left()->lock();
root->lock();
// Should output false.
assert(!root->isLocked());
cout << boolalpha << root->isLocked() << endl;
root->right()->lock();
// Should output true.
assert(root->right()->isLocked());
cout << boolalpha << root->right()->isLocked() << endl;
return 0;
}