-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.go
113 lines (98 loc) · 2.11 KB
/
trie.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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package simple
import "strings"
type node struct {
fullPath string
path string
child []*node
wildChild bool
handlers HandlersChain
}
type nodeOptions struct {
fullPath string
path string
wildChild bool
handlers HandlersChain
}
func newNode(opts *nodeOptions) *node {
if opts == nil {
return &node{
child: make([]*node, 0),
}
}
return &node{
child: make([]*node, 0),
fullPath: opts.fullPath,
path: opts.path,
wildChild: opts.wildChild,
handlers: opts.handlers,
}
}
func (n *node) addRoute(fullPath string, handlers HandlersChain) {
parts := fullPathToPaths(fullPath)
n.insert(fullPath, parts, handlers)
}
func (n *node) getRoute(fullPath string) *node {
parts := fullPathToPaths(fullPath)
return n.search(parts)
}
func (n *node) findOneChild(path string) *node {
for _, child := range n.child {
if child.path == path || child.wildChild {
return child
}
}
return nil
}
func (n *node) insert(pattern string, parts []string, handlers HandlersChain) {
curr := n
for _, part := range parts {
child := curr.findOneChild(part)
if child == nil {
child = newNode(&nodeOptions{
path: part,
wildChild: part[0] == ':' || part[0] == '*',
})
curr.child = append(curr.child, child)
}
curr = child
}
curr.fullPath = pattern
curr.handlers = handlers
}
func (n *node) IsWilcard() bool {
return n.path[0] == '*'
}
func (n *node) search(parts []string) *node {
child := n
for _, part := range parts {
child = child.findOneChild(part)
if child == nil {
return nil
}
if child.IsWilcard() {
return child
}
}
return child
}
func (n *node) parseParams(fullPath string) map[string]string {
params := make(map[string]string)
reqPaths := fullPathToPaths(fullPath)
paths := fullPathToPaths(n.fullPath)
for idx, path := range paths {
if reqPaths[idx] != path && path[0] != ':' {
break
}
params[path[1:]] = reqPaths[idx]
}
return params
}
func fullPathToPaths(fullPath string) []string {
paths := []string{}
for _, path := range strings.Split(fullPath, "/") {
if path != "" {
paths = append(paths, path)
}
}
return paths
}