/
tree.go
91 lines (80 loc) · 1.88 KB
/
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
package finder
import (
"fmt"
jsoniter "github.com/json-iterator/go"
)
//
var (
ErrNotJSONObject = fmt.Errorf("Not JSON Object")
)
// KeyNode key node
type KeyNode struct {
Name string `json:"name"` // 键名
IsRoot bool `json:"is_root"` // 是否顶结点
Level int `json:"level"` // 层级
Data interface{} `json:"data"` // 值
ChildNode *KeyNode `json:"child_node"` // 子结点
BrotherNode *KeyNode `json:"brother_node"` // 兄弟结点
}
func (k *KeyNode) String() string {
buf, _ := jsoniter.ConfigCompatibleWithStandardLibrary.Marshal(k)
return string(buf)
}
// BuildKeyTree build tree
func BuildKeyTree(keys []string) (*KeyNode, error) {
var rootNode = &KeyNode{
IsRoot: true,
Level: 0,
Name: "root",
}
for _, key := range keys {
var cache = make([]string, 0, 16)
var begin int
var flag bool
for i := 0; i < len(key); i++ {
if key[i] == '.' && !flag {
cache = append(cache, key[begin:i])
begin = i + 1
}
if key[i] == '\\' {
flag = true
} else {
flag = false
}
}
if begin != len(key) {
cache = append(cache, key[begin:])
}
rootNode = buildNode(rootNode, 0, cache)
}
return rootNode, nil
}
func buildNode(rootNode *KeyNode, index int, keys []string) *KeyNode {
var currentNode = rootNode
for i, key := range keys {
if currentNode.ChildNode == nil {
currentNode.ChildNode = &KeyNode{
Name: key,
Level: i,
}
currentNode = currentNode.ChildNode
} else {
currentNode = currentNode.ChildNode
if currentNode.Name == key {
continue
}
for currentNode.BrotherNode != nil {
currentNode = currentNode.BrotherNode
if currentNode.Name == key {
continue
}
}
currentNode.BrotherNode = &KeyNode{
Name: key,
Level: i,
}
currentNode = currentNode.BrotherNode
}
}
return rootNode
}