func (ns nodes) tailSort() {
	for i := len(ns) - 1; i >= 0; i-- {
		if ns[i].typ > ntStatic && ns[i].tail == '/' {
			ns.Swap(i, len(ns)-1)
			return
		}
	}
}
tailSort pushes nodes with '/' as the tail to the end of the list for param nodes.
The list order determines the traversal order.
package chi
import (
	"fmt"
	"net/http"
	"regexp"
	"sort"
	"strconv"
	"strings"
)
type methodTyp uint
const (
	mSTUB methodTyp = 1 << iota
	mCONNECT
	mDELETE
	mGET
	mHEAD
	mOPTIONS
	mPATCH
	mPOST
	mPUT
	mTRACE
)
var mALL = mCONNECT | mDELETE | mGET | mHEAD |
	mOPTIONS | mPATCH | mPOST | mPUT | mTRACE
var methodMap = map[string]methodTyp{
	http.MethodConnect: mCONNECT,
	http.MethodDelete:  mDELETE,
	http.MethodGet:     mGET,
	http.MethodHead:    mHEAD,
	http.MethodOptions: mOPTIONS,
	http.MethodPatch:   mPATCH,
	http.MethodPost:    mPOST,
	http.MethodPut:     mPUT,
	http.MethodTrace:   mTRACE,
}
func RegisterMethod(method string) {
	if method == "" {
		return
	}
	method = strings.ToUpper(method)
	if _, ok := methodMap[method]; ok {
		return
	}
	n := len(methodMap)
	if n > strconv.IntSize-2 {
		panic(fmt.Sprintf("chi: max number of methods reached (%d)", strconv.IntSize))
	}
	mt := methodTyp(2 << n)
	methodMap[method] = mt
	mALL |= mt
}
type nodeTyp uint8
const (
	ntStatic   nodeTyp = iota  
	ntRegexp                   
	ntParam                    
	ntCatchAll                 
)
type node struct {
	subroutes Routes
	rex *regexp.Regexp
	endpoints endpoints
	prefix string
	children [ntCatchAll + 1]nodes
	tail byte
	typ nodeTyp
	label byte
}
type endpoints map[methodTyp]*endpoint
type endpoint struct {
	handler http.Handler
	pattern string
	paramKeys []string
}
func (s endpoints) Value(method methodTyp) *endpoint {
	mh, ok := s[method]
	if !ok {
		mh = &endpoint{}
		s[method] = mh
	}
	return mh
}
func (n *node) InsertRoute(method methodTyp, pattern string, handler http.Handler) *node {
	var parent *node
	search := pattern
	for {
		if len(search) == 0 {
			n.setEndpoint(method, handler, pattern)
			return n
		}
		var label = search[0]
		var segTail byte
		var segEndIdx int
		var segTyp nodeTyp
		var segRexpat string
		if label == '{' || label == '*' {
			segTyp, _, segRexpat, segTail, _, segEndIdx = patNextSegment(search)
		}
		var prefix string
		if segTyp == ntRegexp {
			prefix = segRexpat
		}
		parent = n
		n = n.getEdge(segTyp, label, segTail, prefix)
		if n == nil {
			child := &node{label: label, tail: segTail, prefix: search}
			hn := parent.addChild(child, search)
			hn.setEndpoint(method, handler, pattern)
			return hn
		}
		if n.typ > ntStatic {
			search = search[segEndIdx:]
			continue
		}
		commonPrefix := longestPrefix(search, n.prefix)
		if commonPrefix == len(n.prefix) {
			search = search[commonPrefix:]
			continue
		}
		child := &node{
			typ:    ntStatic,
			prefix: search[:commonPrefix],
		}
		parent.replaceChild(search[0], segTail, child)
		n.label = n.prefix[commonPrefix]
		n.prefix = n.prefix[commonPrefix:]
		child.addChild(n, n.prefix)
		search = search[commonPrefix:]
		if len(search) == 0 {
			child.setEndpoint(method, handler, pattern)
			return child
		}
		subchild := &node{
			typ:    ntStatic,
			label:  search[0],
			prefix: search,
		}
		hn := child.addChild(subchild, search)
		hn.setEndpoint(method, handler, pattern)
		return hn
	}
}
func (n *node) addChild(child *node, prefix string) *node {
	search := prefix
	hn := child
	segTyp, _, segRexpat, segTail, segStartIdx, segEndIdx := patNextSegment(search)
	switch segTyp {
	case ntStatic:
	default:
		if segTyp == ntRegexp {
			rex, err := regexp.Compile(segRexpat)
			if err != nil {
				panic(fmt.Sprintf("chi: invalid regexp pattern '%s' in route param", segRexpat))
			}
			child.prefix = segRexpat
			child.rex = rex
		}
		if segStartIdx == 0 {
			child.typ = segTyp
			if segTyp == ntCatchAll {
				segStartIdx = -1
			} else {
				segStartIdx = segEndIdx
			}
			if segStartIdx < 0 {
				segStartIdx = len(search)
			}
			child.tail = segTail  
			if segStartIdx != len(search) {
				search = search[segStartIdx:]  
				nn := &node{
					typ:    ntStatic,
					label:  search[0],
					prefix: search,
				}
				hn = child.addChild(nn, search)
			}
		} else if segStartIdx > 0 {
			child.typ = ntStatic
			child.prefix = search[:segStartIdx]
			child.rex = nil
			search = search[segStartIdx:]
			nn := &node{
				typ:   segTyp,
				label: search[0],
				tail:  segTail,
			}
			hn = child.addChild(nn, search)
		}
	}
	n.children[child.typ] = append(n.children[child.typ], child)
	n.children[child.typ].Sort()
	return hn
}
func (n *node) replaceChild(label, tail byte, child *node) {
	for i := 0; i < len(n.children[child.typ]); i++ {
		if n.children[child.typ][i].label == label && n.children[child.typ][i].tail == tail {
			n.children[child.typ][i] = child
			n.children[child.typ][i].label = label
			n.children[child.typ][i].tail = tail
			return
		}
	}
	panic("chi: replacing missing child")
}
func (n *node) getEdge(ntyp nodeTyp, label, tail byte, prefix string) *node {
	nds := n.children[ntyp]
	for i := 0; i < len(nds); i++ {
		if nds[i].label == label && nds[i].tail == tail {
			if ntyp == ntRegexp && nds[i].prefix != prefix {
				continue
			}
			return nds[i]
		}
	}
	return nil
}
func (n *node) setEndpoint(method methodTyp, handler http.Handler, pattern string) {
	if n.endpoints == nil {
		n.endpoints = make(endpoints)
	}
	paramKeys := patParamKeys(pattern)
	if method&mSTUB == mSTUB {
		n.endpoints.Value(mSTUB).handler = handler
	}
	if method&mALL == mALL {
		h := n.endpoints.Value(mALL)
		h.handler = handler
		h.pattern = pattern
		h.paramKeys = paramKeys
		for _, m := range methodMap {
			h := n.endpoints.Value(m)
			h.handler = handler
			h.pattern = pattern
			h.paramKeys = paramKeys
		}
	} else {
		h := n.endpoints.Value(method)
		h.handler = handler
		h.pattern = pattern
		h.paramKeys = paramKeys
	}
}
func (n *node) FindRoute(rctx *Context, method methodTyp, path string) (*node, endpoints, http.Handler) {
	rctx.routePattern = ""
	rctx.routeParams.Keys = rctx.routeParams.Keys[:0]
	rctx.routeParams.Values = rctx.routeParams.Values[:0]
	rn := n.findRoute(rctx, method, path)
	if rn == nil {
		return nil, nil, nil
	}
	rctx.URLParams.Keys = append(rctx.URLParams.Keys, rctx.routeParams.Keys...)
	rctx.URLParams.Values = append(rctx.URLParams.Values, rctx.routeParams.Values...)
	if rn.endpoints[method].pattern != "" {
		rctx.routePattern = rn.endpoints[method].pattern
		rctx.RoutePatterns = append(rctx.RoutePatterns, rctx.routePattern)
	}
	return rn, rn.endpoints, rn.endpoints[method].handler
}
func (n *node) findRoute(rctx *Context, method methodTyp, path string) *node {
	nn := n
	search := path
	for t, nds := range nn.children {
		ntyp := nodeTyp(t)
		if len(nds) == 0 {
			continue
		}
		var xn *node
		xsearch := search
		var label byte
		if search != "" {
			label = search[0]
		}
		switch ntyp {
		case ntStatic:
			xn = nds.findEdge(label)
			if xn == nil || !strings.HasPrefix(xsearch, xn.prefix) {
				continue
			}
			xsearch = xsearch[len(xn.prefix):]
		case ntParam, ntRegexp:
			if xsearch == "" {
				continue
			}
			for idx := 0; idx < len(nds); idx++ {
				xn = nds[idx]
				p := strings.IndexByte(xsearch, xn.tail)
				if p < 0 {
					if xn.tail == '/' {
						p = len(xsearch)
					} else {
						continue
					}
				} else if ntyp == ntRegexp && p == 0 {
					continue
				}
				if ntyp == ntRegexp && xn.rex != nil {
					if !xn.rex.MatchString(xsearch[:p]) {
						continue
					}
				} else if strings.IndexByte(xsearch[:p], '/') != -1 {
					continue
				}
				prevlen := len(rctx.routeParams.Values)
				rctx.routeParams.Values = append(rctx.routeParams.Values, xsearch[:p])
				xsearch = xsearch[p:]
				if len(xsearch) == 0 {
					if xn.isLeaf() {
						h := xn.endpoints[method]
						if h != nil && h.handler != nil {
							rctx.routeParams.Keys = append(rctx.routeParams.Keys, h.paramKeys...)
							return xn
						}
						rctx.methodNotAllowed = true
					}
				}
				fin := xn.findRoute(rctx, method, xsearch)
				if fin != nil {
					return fin
				}
				rctx.routeParams.Values = rctx.routeParams.Values[:prevlen]
				xsearch = search
			}
			rctx.routeParams.Values = append(rctx.routeParams.Values, "")
		default:
			rctx.routeParams.Values = append(rctx.routeParams.Values, search)
			xn = nds[0]
			xsearch = ""
		}
		if xn == nil {
			continue
		}
		if len(xsearch) == 0 {
			if xn.isLeaf() {
				h := xn.endpoints[method]
				if h != nil && h.handler != nil {
					rctx.routeParams.Keys = append(rctx.routeParams.Keys, h.paramKeys...)
					return xn
				}
				rctx.methodNotAllowed = true
			}
		}
		fin := xn.findRoute(rctx, method, xsearch)
		if fin != nil {
			return fin
		}
		if xn.typ > ntStatic {
			if len(rctx.routeParams.Values) > 0 {
				rctx.routeParams.Values = rctx.routeParams.Values[:len(rctx.routeParams.Values)-1]
			}
		}
	}
	return nil
}
func (n *node) findEdge(ntyp nodeTyp, label byte) *node {
	nds := n.children[ntyp]
	num := len(nds)
	idx := 0
	switch ntyp {
	case ntStatic, ntParam, ntRegexp:
		i, j := 0, num-1
		for i <= j {
			idx = i + (j-i)/2
			if label > nds[idx].label {
				i = idx + 1
			} else if label < nds[idx].label {
				j = idx - 1
			} else {
				i = num  
			}
		}
		if nds[idx].label != label {
			return nil
		}
		return nds[idx]
	default:  
		return nds[idx]
	}
}
func (n *node) isLeaf() bool {
	return n.endpoints != nil
}
func (n *node) findPattern(pattern string) bool {
	nn := n
	for _, nds := range nn.children {
		if len(nds) == 0 {
			continue
		}
		n = nn.findEdge(nds[0].typ, pattern[0])
		if n == nil {
			continue
		}
		var idx int
		var xpattern string
		switch n.typ {
		case ntStatic:
			idx = longestPrefix(pattern, n.prefix)
			if idx < len(n.prefix) {
				continue
			}
		case ntParam, ntRegexp:
			idx = strings.IndexByte(pattern, '}') + 1
		case ntCatchAll:
			idx = longestPrefix(pattern, "*")
		default:
			panic("chi: unknown node type")
		}
		xpattern = pattern[idx:]
		if len(xpattern) == 0 {
			return true
		}
		return n.findPattern(xpattern)
	}
	return false
}
func (n *node) routes() []Route {
	rts := []Route{}
	n.walk(func(eps endpoints, subroutes Routes) bool {
		if eps[mSTUB] != nil && eps[mSTUB].handler != nil && subroutes == nil {
			return false
		}
		pats := make(map[string]endpoints)
		for mt, h := range eps {
			if h.pattern == "" {
				continue
			}
			p, ok := pats[h.pattern]
			if !ok {
				p = endpoints{}
				pats[h.pattern] = p
			}
			p[mt] = h
		}
		for p, mh := range pats {
			hs := make(map[string]http.Handler)
			if mh[mALL] != nil && mh[mALL].handler != nil {
				hs["*"] = mh[mALL].handler
			}
			for mt, h := range mh {
				if h.handler == nil {
					continue
				}
				m := methodTypString(mt)
				if m == "" {
					continue
				}
				hs[m] = h.handler
			}
			rt := Route{subroutes, hs, p}
			rts = append(rts, rt)
		}
		return false
	})
	return rts
}
func (n *node) walk(fn func(eps endpoints, subroutes Routes) bool) bool {
	if (n.endpoints != nil || n.subroutes != nil) && fn(n.endpoints, n.subroutes) {
		return true
	}
	for _, ns := range n.children {
		for _, cn := range ns {
			if cn.walk(fn) {
				return true
			}
		}
	}
	return false
}
func patNextSegment(pattern string) (nodeTyp, string, string, byte, int, int) {
	ps := strings.Index(pattern, "{")
	ws := strings.Index(pattern, "*")
	if ps < 0 && ws < 0 {
		return ntStatic, "", "", 0, 0, len(pattern)  
	}
	if ps >= 0 && ws >= 0 && ws < ps {
		panic("chi: wildcard '*' must be the last pattern in a route, otherwise use a '{param}'")
	}
	var tail byte = '/'  
	if ps >= 0 {
		nt := ntParam
		cc := 0
		pe := ps
		for i, c := range pattern[ps:] {
			if c == '{' {
				cc++
			} else if c == '}' {
				cc--
				if cc == 0 {
					pe = ps + i
					break
				}
			}
		}
		if pe == ps {
			panic("chi: route param closing delimiter '}' is missing")
		}
		key := pattern[ps+1 : pe]
		pe++  
		if pe < len(pattern) {
			tail = pattern[pe]
		}
		var rexpat string
		if idx := strings.Index(key, ":"); idx >= 0 {
			nt = ntRegexp
			rexpat = key[idx+1:]
			key = key[:idx]
		}
		if len(rexpat) > 0 {
			if rexpat[0] != '^' {
				rexpat = "^" + rexpat
			}
			if rexpat[len(rexpat)-1] != '$' {
				rexpat += "$"
			}
		}
		return nt, key, rexpat, tail, ps, pe
	}
	if ws < len(pattern)-1 {
		panic("chi: wildcard '*' must be the last value in a route. trim trailing text or use a '{param}' instead")
	}
	return ntCatchAll, "*", "", 0, ws, len(pattern)
}
func patParamKeys(pattern string) []string {
	pat := pattern
	paramKeys := []string{}
	for {
		ptyp, paramKey, _, _, _, e := patNextSegment(pat)
		if ptyp == ntStatic {
			return paramKeys
		}
		for i := 0; i < len(paramKeys); i++ {
			if paramKeys[i] == paramKey {
				panic(fmt.Sprintf("chi: routing pattern '%s' contains duplicate param key, '%s'", pattern, paramKey))
			}
		}
		paramKeys = append(paramKeys, paramKey)
		pat = pat[e:]
	}
}
func longestPrefix(k1, k2 string) int {
	max := len(k1)
	if l := len(k2); l < max {
		max = l
	}
	var i int
	for i = 0; i < max; i++ {
		if k1[i] != k2[i] {
			break
		}
	}
	return i
}
func methodTypString(method methodTyp) string {
	for s, t := range methodMap {
		if method == t {
			return s
		}
	}
	return ""
}
type nodes []*node
func (ns nodes) Sort()              { sort.Sort(ns); ns.tailSort() }
func (ns nodes) Len() int           { return len(ns) }
func (ns nodes) Swap(i, j int)      { ns[i], ns[j] = ns[j], ns[i] }
func (ns nodes) Less(i, j int) bool { return ns[i].label < ns[j].label }