package routes

import (
	"fmt"
	"strings"
)

type matchType int

func (m matchType) String() string {
	switch m {
	case literal:
		return "literal"
	case wildcard:
		return "wildcard"
	case glob:
		return "glob"
	default:
		return "unknown"
	}
}

const (
	literal matchType = iota
	wildcard
	glob

	debug = false
)

func debugf(msg string, args ...interface{}) {
	if debug {
		fmt.Printf(msg, args...)
	}
}

// node represents a string prefix matcher in a radix tree.
//
type node struct {
	// name is the name of the path matched at this node. this is left
	// empty if the node does not match any particular path.
	name string
	// path is the path component that this node matches
	path string
	// matcher is the matchType of the node: it can be a wildcard
	// which matches up to a / character, a glob which matches
	// anything, or a literal matcher which matches the input URI's
	// prefix versus node.path.
	matcher matchType
	// children is the list of nodes which are immediate descendents
	// of this one in the tree
	children []*node
	// prio is the priority level to use for this node when resolving
	// multiple matches for a URI path. Higher priorities are
	// considered better matches.
	prio int
	// wildcardTerminator is the rune that ends the wildcard capture group, if
	// this node represents a wildcard match. This will usually be '/', but might
	// be something else for partial matches.
	wildcardTerminator rune
}

func printNode(level int, node *node) {
	indent := ""
	for i := 0; i < level; i++ {
		indent += "\t"
	}
	debugf("%s%v\n", indent, node)
	for _, child := range node.children {
		printNode(level+1, child)
	}
}

func newRadixTree() *node {
	return &node{children: []*node{}}
}

// size returns the number of nodes in the entire subtree starting
// with this node as the root.
func (n *node) size() int {
	i := 1
	for _, c := range n.children {
		i += c.size()
	}
	return i
}

// increment priorities increases the `prio` of all nodes in the
// subtree by one.
func (n *node) incrementPriorities() {
	n.prio += 1
	for _, c := range n.children {
		c.incrementPriorities()
	}
}

// Find the highest-priority name in the tree.
func (n *node) lookup(path string) string {
	match, _ := n.match(path)
	debugf("lookup %v: %v\n", path, match)
	return match
}

// Find the highest-priority name in the subtree with this node as the
// root. Returns (name, priority) so that a caller can fan out and
// pick the highest priority themseves.
func (n *node) match(path string) (s string, i int) {
	if debug {
		debugf("matching %v to %v\n", path, n)
		defer func() {
			debugf("%v result: %s: %q, %d\n", path, n.matcher, s, i)
		}()
	}
	switch n.matcher {
	case literal:
		return n.matchLiteral(path)
	case glob:
		return n.matchGlob(path)
	case wildcard:
		return n.matchWildcard(path)
	default:
		return "", 0
	}
}

// a literal match occurs if the input path is prefixed with n.path.
func (n *node) matchLiteral(path string) (string, int) {
	if !strings.HasPrefix(path, n.path) {
		// no match
		return "", 0
	}

	var (
		name, bestName string
		prio, bestPrio int
	)
	// See if the current node is an exact match
	if path == n.path {
		// this node matches exactly - consider it a candidate result.
		// n.name and n.prio will be "" and 0 if this node has no
		// data, which is just like leaving them unset, so this is safe.
		bestName, bestPrio = n.name, n.prio
	}

	// Check in children, removing this node's prefix. Find the child
	// which matches with best priority and return it if it has a
	// better priority than this node.
	path = path[len(n.path):]
	for _, child := range n.children {
		name, prio = child.match(path)
		if prio > bestPrio {
			bestName, bestPrio = name, prio
		}
	}
	return bestName, bestPrio
}

// a wildcard match occurs if the input path contains no slash
// characters.
func (n *node) matchWildcard(path string) (string, int) {
	var (
		name, bestName string
		prio, bestPrio int
	)
	// Wildcards match up to a terminating character
	if strings.IndexRune(path, n.wildcardTerminator) == -1 {
		bestName, bestPrio = n.name, n.prio
	}
	// For each child, figure out where the wildcard would end; trim
	// that from the prefix of the input path, and return the
	// highest-priority path out of all children.
	for _, child := range n.children {
		pos := strings.Index(path, child.path)
		if pos == -1 {
			continue
		}
		name, prio = child.match(path[pos:])
		if prio > bestPrio {
			bestName, bestPrio = name, prio
		}
	}
	return bestName, bestPrio
}

// a glob always matches any path.
func (n *node) matchGlob(path string) (string, int) {
	// Globs eat the whole path and immediately match.
	return n.name, n.prio
}

// set the data on the node to the given values
func (n *node) setVal(path string, name string, prio int) {
	switch {
	case isWildcard(path):
		n.matcher = wildcard
		n.path = wildcardSymbol
	case isGlob(path):
		n.matcher = glob
		n.path = globSymbol
	default:
		n.matcher = literal
		n.path = literalPart(path)
	}
	if len(n.path) == len(path) {
		// then this node fully describes the path, so this is a leaf,
		// and it gets data.
		n.name = name
		n.prio = prio
	}
}

// returns the string up to the next wildcard or glob symbol
func literalPart(path string) string {
	i := strings.IndexAny(path, wildcardSymbol+globSymbol)
	if i == -1 {
		return path
	}
	return path[:i]
}

// compute the dangling part of the path which is not covered by this
// node
func (n *node) childPath(path string) string {
	switch n.matcher {
	case wildcard:
		return path[len(wildcardSymbol):]
	case glob:
		return path[len(globSymbol):]
	case literal:
		if len(n.path) < len(path) {
			return path[len(n.path):]
		} else {
			return ""
		}
	default:
		return ""
	}
}

// append a path to the trie, giving it lowest priority
func (n *node) add(path string, name string) {
	n.incrementPriorities()
	n.insert(path, name, 1)
}

// insert a path into the trie
func (n *node) insert(path string, name string, prio int) {
	if n.name == "" && (n.path == "" || n.path == path) {
		// This node has no data, so it is an empty leaf. Fill it in.
		n.setVal(path, name, prio)
		// If there is a remainder (because we split on a wildcard or
		// glob symbol, add that)
		remainder := n.childPath(path)
		if len(remainder) > 0 {
			n.findChild(remainder).insert(remainder, name, prio)
			n.wildcardTerminator = rune(remainder[0])
		} else {
			n.wildcardTerminator = '/'
		}
		return
	}

	if path == n.path {
		// The new data would overwrite the current data - skip it, because the
		// existing data is higher priority.
		return
	}

	// The node is not empty and has a path already. How many
	// characters match?
	pos := n.pathmatch(path)

	if pos == len(n.path) {
		// This node is a prefix for the input path, so the input node
		// should be on the best-fit child node.
		path = path[pos:]
		n.findChild(path).insert(path, name, prio)
		return
	}

	// This node is a partial prefix of the input path. We need to
	// split this node up.
	n.split(pos)
	// Now the current node should be a perfect match.
	n.insert(path, name, prio)
}

// findChild returns the child node with the longest common prefix.
func (n *node) findChild(path string) *node {
	var (
		longestSoFar int = 0
		prefixLen    int
		bestChild    *node
	)
	for _, child := range n.children {
		prefixLen = child.pathmatch(path)
		if prefixLen > longestSoFar {
			longestSoFar = prefixLen
			bestChild = child
		}
	}
	if bestChild != nil {
		return bestChild
	}
	// No children share a common prefix, so this path is a new leaf.
	return n.newEmptyChild()
}

func (n *node) newEmptyChild() *node {
	new := &node{
		children: []*node{},
	}
	n.children = append(n.children, new)
	return new
}

// pathmatch returns the number of characters in the path string which
// match the prefix at this node.
func (n *node) pathmatch(path string) int {
	maxMatches := min(len(n.path), len(path))
	for i := 0; i < maxMatches; i++ {
		if n.path[i] != path[i] {
			return i
		}
	}
	// All characters match.
	return maxMatches
}

// split a node in place at the given character index, so that
// "someprefix" (eg) would be split into "som" and its child,
// "eprefix" if the input is `3`. Any data (path, prio, and pointers
// to children) on the current node are moved down to the new child.
func (n *node) split(idx int) *node {
	new := &node{
		name:     n.name,
		path:     n.path[idx:],
		children: n.children,
		prio:     n.prio,
	}
	n.name = ""
	n.path = n.path[:idx]
	n.children = []*node{new}
	n.prio = 0
	return new
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}

}

func isWildcard(path string) bool {
	return string(path[0]) == wildcardSymbol
}

func isGlob(path string) bool {
	return string(path[0]) == globSymbol
}
