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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
package bst
// BST ...
type BST struct {
// registered topic, not unique
topic string
// associated connections with the topic
uuids map[string]struct{}
// left and right subtrees
left *BST
right *BST
}
func NewBST() Storage {
return &BST{
uuids: make(map[string]struct{}, 10),
}
}
// Insert uuid to the topic
func (b *BST) Insert(uuid string, topic string) {
curr := b
for {
if topic == curr.topic {
curr.uuids[uuid] = struct{}{}
return
}
// if topic less than curr topic
if topic < curr.topic {
if curr.left == nil {
curr.left = &BST{
topic: topic,
uuids: map[string]struct{}{uuid: {}},
}
return
}
// move forward
curr = curr.left
} else {
if curr.right == nil {
curr.right = &BST{
topic: topic,
uuids: map[string]struct{}{uuid: {}},
}
return
}
curr = curr.right
}
}
}
func (b *BST) Contains(topic string) bool {
curr := b
for curr != nil {
switch {
case topic < curr.topic:
curr = curr.left
case topic > curr.topic:
curr = curr.right
case topic == curr.topic:
return true
}
}
return false
}
func (b *BST) Get(topic string) map[string]struct{} {
curr := b
for curr != nil {
switch {
case topic < curr.topic:
curr = curr.left
case topic > curr.topic:
curr = curr.right
case topic == curr.topic:
return curr.uuids
}
}
return nil
}
func (b *BST) Remove(uuid string, topic string) {
b.removeHelper(uuid, topic, nil)
}
func (b *BST) removeHelper(uuid string, topic string, parent *BST) {
curr := b
for curr != nil {
if topic < curr.topic { //nolint:gocritic
parent = curr
curr = curr.left
} else if topic > curr.topic {
parent = curr
curr = curr.right
} else {
// if more than 1 topic - remove only topic, do not remove the whole vertex
if len(curr.uuids) > 1 {
if _, ok := curr.uuids[uuid]; ok {
delete(curr.uuids, uuid)
return
}
}
if curr.left != nil && curr.right != nil { //nolint:gocritic
curr.topic, curr.uuids = curr.right.traverseForMinString()
curr.right.removeHelper(curr.topic, uuid, curr)
} else if parent == nil {
if curr.left != nil { //nolint:gocritic
curr.topic = curr.left.topic
curr.uuids = curr.left.uuids
curr.right = curr.left.right
curr.left = curr.left.left
} else if curr.right != nil {
curr.topic = curr.right.topic
curr.uuids = curr.right.uuids
curr.left = curr.right.left
curr.right = curr.right.right
} else { //nolint:staticcheck
// single node tree
}
} else if parent.left == curr {
if curr.left != nil {
parent.left = curr.left
} else {
parent.left = curr.right
}
} else if parent.right == curr {
if curr.left != nil {
parent.right = curr.left
} else {
parent.right = curr.right
}
}
break
}
}
}
//go:inline
func (b *BST) traverseForMinString() (string, map[string]struct{}) {
if b.left == nil {
return b.topic, b.uuids
}
return b.left.traverseForMinString()
}
|
