url路由的副产品。
代码语言：javascript复制package utils
/*
PrefixTree 前缀树
使用姿势：
tree := utils.BuildTree([]string{
"/yuedu/account",
"/yuedu",
"/yuedu/master",
})
fmt.Println(tree.Match("/yuedu"))
fmt.Println(tree.Match("/yuedu/details"))
fmt.Println(tree.Match("/yuedu/account"))
fmt.Println(tree.Match("/yuedu/account/user"))
fmt.Println(tree.Match("/yuedu/master/"))
result:
/yuedu true
/yuedu false
/yuedu/account true
/yuedu/account false
/yuedu/master false
*/
type PrefixTree struct {
root *treeNode
}
// BuildTree 生成这棵前缀树
func BuildTree(keys []string) *PrefixTree {
tree := new(PrefixTree)
root := makeNode()
for _, key := range keys {
buildNode(key, root)
}
tree.root = root
return tree
}
// Match 尝试匹配一个Path，返回最终匹配的结果和是否完全匹配
func (t PrefixTree) Match(path string) (string, bool) {
tpnode := t.root
result := ""
for _, pathpart := range path {
_, ok := tpnode.subNode[pathpart]
if !ok {
return result, false
}
tpnode = tpnode.subNode[pathpart]
if tpnode.value != "" {
result = tpnode.value
}
}
return result, tpnode.value != ""
}
type treeNode struct {
subNode map[rune]*treeNode
value string
}
func makeNode() *treeNode {
node := new(treeNode)
node.subNode = make(map[rune]*treeNode)
return node
}
func buildNode(key string, root *treeNode) {
tpnode := root
for _, keypart := range key {
_, ok := tpnode.subNode[keypart]
if ok {
tpnode = tpnode.subNode[keypart]
} else {
tpnode.subNode[keypart] = makeNode()
tpnode = tpnode.subNode[keypart]
}
}
tpnode.value = key
}
