循环查找前缀树

package route_trie

import (
	"strings"

	"github.com/golang-collections/collections/stack"
)

type HandlerFunc *string

type Node struct {
	ISWild   bool
	Path     string
	Children []*Node
	Handler  HandlerFunc
}

// 该结构体用于路由前缀树查询
type pairNode struct {
	Node  *Node
	Index int
}

// 拆分路径
func splitPath(path string) []string {
	return strings.Split(path, "/")
}

func newNode(path string) *Node {
	// 判断path[0]是否为通配符，如果是，则将ISWild字段设置为true
	if len(path) != 0 {
		if path[0] == '*' || path[0] == ':' {
			return &Node{ISWild: true, Path: path, Children: make([]*Node, 0)}
		} else {
			return &Node{ISWild: false, Path: path, Children: make([]*Node, 0)}
		}
	} else {
		return &Node{ISWild: false, Path: path, Children: make([]*Node, 0)}
	}
}

// 找到单个节点，不使用通配符。该函数用于插入。
func (n *Node) searchChild(path string) *Node {
	if n.Children == nil {
		return nil
	}
	for _, child := range n.Children {
		if child == nil {
			continue
		}
		if child.Path == path {
			return child
		}
	}
	return nil
}

// 找到所有匹配的子节点，使用通配符。该函数用于查询。
func (n *Node) searchChildren(path string) []*Node {
	children := make([]*Node, 0)
	for _, child := range n.Children {
		// 查找合适的节点，添加进children
		if child.Path == path || child.ISWild {
			children = append(children, child)
		}
	}

	// 返回所有匹配的结果
	return children
}

// 路由树的插入操作
func (n *Node) Insert(path string, handler HandlerFunc) {
	// 分割路由
	paths := splitPath(path)
	p_len := len(paths)

	// 初始化root节点
	root := n
	for i := 0; i < p_len; i++ {
		child := root.searchChild(paths[i])

		// 没有找到匹配的子节点，所以新建一个子节点
		if child == nil {
			child = newNode(paths[i])
			root.Children = append(root.Children, child)
		}

		// 将root赋值为子节点，用于下一层路由的插入
		root = child
	}
	root.Handler = handler
}

// 查找路由对应的handler
func (n *Node) Search(path string) HandlerFunc {
	// 初始化必要变量
	paths := splitPath(path)
	p_len := len(paths)
	nstack := stack.New()
	index := 0

	// pairNode.Index记录当前层级，Node记录子节点
	root := &pairNode{Node: n, Index: index}
	for {
		// 栈已经空了，查找不到结果，返回nil
		if root == nil {
			return nil
		}
		index = root.Index
		// 判断是否是最后一层
		if index == p_len {
			return root.Node.Handler
		}

		// 查找匹配的子节点，将子节点全部压栈
		children := root.Node.searchChildren(paths[index])
		for _, child := range children {
			nstack.Push(&pairNode{Index: index + 1, Node: child})
		}

		// 判断栈顶是否为空
		if nstack.Peek() != nil {
			root = nstack.Pop().(*pairNode)
		} else {
			root = nil
		}
	}
}

package main

import (
	"fmt"
	route_tire "route_trie"
)

func main() {
	var root route_tire.Node
	root.Children = make([]*route_tire.Node, 0)
	s := "hey!"
	root.Insert("/*hello/hey", &s)
	fmt.Println(root.Children)
	fmt.Println("This is handler: ")
	fmt.Println(*root.Search("/hello/hey"))
}