1
var LockingTree = function (parent) {
2
  this.parents = parent;
3
  this.children = [];
4
  this.locked = new Map();
5

6
  for (let i = 0; i < this.parents.length; ++i) {
7
    this.children[i] = [];
8
  }
9

10
  for (let i = 1; i < this.parents.length; ++i) {
11
    const parent = this.parents[i];
12

13
    this.children[parent].push(i);
14
  }
15
};
16

17
LockingTree.prototype.lock = function (num, user) {
18
  if (this.locked.has(num)) return false;
19

20
  this.locked.set(num, user);
21

22
  return true;
23
};
24

25
LockingTree.prototype.unlock = function (num, user) {
26
  if (!this.locked.has(num) || this.locked.get(num) != user) return false;
27

28
  this.locked.delete(num);
29

30
  return true;
31
};
32

33
LockingTree.prototype.upgrade = function (num, user) {
34
  let isLocked = traverseUp(num, this.parents, this.locked);
35

36
  if (isLocked) return false;
37

38
  const queue = [];
39

40
  isLocked = false;
41

42
  queue.push(num);
43

44
  while (queue.length > 0) {
45
    const node = queue.shift();
46

47
    if (node != num && this.locked.has(node)) {
48
      isLocked = true;
49
      this.locked.delete(node);
50
    }
51

52
    for (let i = 0; i < this.children[node].length; ++i) {
53
      queue.push(this.children[node][i]);
54
    }
55
  }
56

57
  if (!isLocked) return false;
58

59
  this.locked.set(num, user);
60

61
  return true;
62

63
  function traverseUp(num, parents, locked) {
64
    if (locked.has(num)) return true;
65
    if (num === 0) return false;
66

67
    const parentIdx = parents[num];
68

69
    return traverseUp(parentIdx, parents, locked);
70
  }
71
};