Trie matching paths

router.go

package router

import "strings"

type trie struct {
	root trieNode
}

func newTrie() *trie {
	return &trie{
		root: &trieBaseNode{},
	}
}

func (t *trie) add(path string) {
	segments := strings.Split(path, ":")
	curr := t.root
	for _, segment := range segments {
		curr = findOrAdd(curr, segment)
	}
}

type trieStack struct {
	s []trieNode
}

func (s *trieStack) push(n trieNode) {
	s.s = append(s.s, n)
}

func (s *trieStack) pushall(o trieStack) {
	s.s = append(s.s, o.s...)
}

func (s *trieStack) pop() trieNode {
	top := len(s.s) - 1
	n := s.s[top]
	s.s = s.s[:top]
	return n
}

func (s *trieStack) len() int {
	return len(s.s)
}

func (t *trie) match(path string) trieNode {
	segments := strings.Split(path, ":")

	var stack trieStack
	stack.push(t.root)
	bestScore := 0
	bestNode := t.root
	for _, segment := range segments {
		var next trieStack
		for stack.len() > 0 {
			node := stack.pop()
			for _, child := range node.nodes() {
				if child.match(segment) {
					next.push(child)
					if child.pathScore() > bestScore {
						bestScore = child.pathScore()
						bestNode = child
					}
				}
			}
		}
		stack.pushall(next)
	}
	return bestNode
}

func findOrAdd(parent trieNode, segment string) trieNode {
	for _, node := range parent.nodes() {
		if strings.EqualFold(node.pattern(), segment) {
			return node
		}
	}

	var node trieNode
	if strings.HasPrefix(segment, "{") && strings.HasSuffix(segment, "}") {
		node = newTrieParamNode(segment, parent)
	} else {
		node = newTrieLitNode(segment, parent)
	}
	parent.add(node)
	return node
}

type trieNode interface {
	pattern() string
	matchScore() int
	pathScore() int
	match(segment string) bool
	nodes() []trieNode
	add(node trieNode)
}

type trieBaseNode struct {
	pat    string
	nds    []trieNode
	pscore int
}

func (n *trieBaseNode) pattern() string {
	return n.pat
}

func (n *trieBaseNode) matchScore() int {
	return 0
}

func (n *trieBaseNode) pathScore() int {
	return n.pscore
}

func (n *trieBaseNode) match(segment string) bool {
	return strings.EqualFold(n.pattern(), segment)
}

func (n *trieBaseNode) nodes() []trieNode {
	return n.nds
}

func (n *trieBaseNode) add(node trieNode) {
	n.nds = append(n.nds, node)
}

type trieLitNode struct {
	trieBaseNode
}

func newTrieLitNode(pattern string, parent trieNode) *trieLitNode {
	n := &trieLitNode{
		trieBaseNode: trieBaseNode{pat: pattern},
	}
	n.pscore = parent.pathScore() + n.matchScore()
	return n
}

func (n *trieLitNode) matchScore() int {
	return 10000
}

type trieParamNode struct {
	trieBaseNode
}

func newTrieParamNode(pattern string, parent trieNode) *trieParamNode {
	n := &trieParamNode{
		trieBaseNode: trieBaseNode{pat: pattern},
	}
	n.pscore = parent.pathScore() + n.matchScore()
	return n
}

func (n *trieParamNode) match(segment string) bool {
	return true
}

func (n *trieParamNode) matchScore() int {
	return 1000
}