-
Notifications
You must be signed in to change notification settings - Fork 49
/
path_trie.go
123 lines (94 loc) · 2.3 KB
/
path_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
114
115
116
117
118
119
120
121
122
123
package pathpolicy
import (
"sort"
"strings"
)
// splits the path into its individual components. Retruns the
// empty list if the path is just the absolute root, i.e. "/".
func pathTrieSplitPath(path string) []string {
path = strings.Trim(path, "/")
if path == "" {
return []string{}
}
return strings.Split(path, "/")
}
type PathTrie struct {
Name []string
Paths []*PathTrie
Payload interface{}
}
// match checks if the given trie is a prefix of path
func (trie *PathTrie) match(path []string) bool {
if len(trie.Name) > len(path) {
return false
}
for i := range trie.Name {
if path[i] != trie.Name[i] {
return false
}
}
return true
}
func (trie *PathTrie) get(path []string) (*PathTrie, []string) {
if len(path) < 1 {
panic("programming error: expected root node")
}
var node *PathTrie
for i := range trie.Paths {
if trie.Paths[i].match(path) {
node = trie.Paths[i]
break
}
}
// no subpath match, we are the best match
if node == nil {
return trie, path
}
// node, or one of its sub-nodes, is a match
prefix := len(node.Name)
// the node is a perfect match, return it
if len(path) == prefix {
return node, nil
}
// check if any sub-path's of node match
return node.get(path[prefix:])
}
func (trie *PathTrie) add(path []string) *PathTrie {
node := &PathTrie{Name: path}
if trie.Paths == nil {
trie.Paths = make([]*PathTrie, 0, 1)
}
trie.Paths = append(trie.Paths, node)
return node
}
// Construct a new trie from a map of paths to their payloads.
// Returns the root node of the trie.
func NewPathTrieFromMap(entries map[string]interface{}) *PathTrie {
root := &PathTrie{Name: []string{}}
keys := make([]string, 0, len(entries))
for k := range entries {
keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
node, left := root.Lookup(k)
if len(left) > 0 {
node = node.add(left)
}
node.Payload = entries[k]
}
return root
}
// Lookup returns the node that is the prefix of path and
// the unmatched path segment. Must be called on the root
// trie node.
func (root *PathTrie) Lookup(path string) (*PathTrie, []string) {
if len(root.Name) != 0 {
panic("programming error: lookup on non-root trie node")
}
elements := pathTrieSplitPath(path)
if len(elements) == 0 {
return root, elements
}
return root.get(elements)
}