/
grf_entry_tree.go
95 lines (77 loc) · 1.45 KB
/
grf_entry_tree.go
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
package grf
import "github.com/pkg/errors"
type EntryTree struct {
Root *EntryTreeNode
}
func (t *EntryTree) Traverse(n *EntryTreeNode, f func(*EntryTreeNode)) {
if n == nil {
return
}
t.Traverse(n.Left, f)
f(n)
t.Traverse(n.Right, f)
}
func (t *EntryTree) Insert(value string, data []*Entry) error {
if t.Root == nil {
t.Root = &EntryTreeNode{Value: value, Data: data}
return nil
}
return t.Root.Insert(value, data)
}
func (t *EntryTree) Find(s string) ([]*Entry, bool) {
if t.Root == nil {
return nil, false
}
return t.Root.Find(s)
}
type EntryTreeNode struct {
Value string
Data []*Entry
Left *EntryTreeNode
Right *EntryTreeNode
}
func (n *EntryTreeNode) Insert(value string, data []*Entry) error {
if n == nil {
return errors.New("could not insert value: nil tree")
}
switch {
case value == n.Value:
return nil
case value < n.Value:
{
if n.Left == nil {
n.Left = &EntryTreeNode{
Value: value,
Data: data,
}
return nil
}
return n.Left.Insert(value, data)
}
case value > n.Value:
{
if n.Right == nil {
n.Right = &EntryTreeNode{
Value: value,
Data: data,
}
return nil
}
return n.Right.Insert(value, data)
}
}
return nil
}
func (n *EntryTreeNode) Find(s string) ([]*Entry, bool) {
if n == nil {
return nil, false
}
switch {
case s == n.Value:
return n.Data, true
case s < n.Value:
return n.Left.Find(s)
default:
return n.Right.Find(s)
}
}