func (da *doubleArray) setCheck(i int, check byte) {
	da.bc[i].SetCheck(check)
}
setCheck sets CHECK.
package denco
import (
	"fmt"
	"sort"
	"strings"
)
const (
	ParamCharacter = ':'
	WildcardCharacter = '*'
	TerminationCharacter = '#'
	MaxSize = (1 << 22) - 1
)
type Router struct {
	SizeHint int
	static map[string]interface{}
	param  *doubleArray
}
func New() *Router {
	return &Router{
		SizeHint: -1,
		static:   make(map[string]interface{}),
		param:    newDoubleArray(),
	}
}
func (rt *Router) Lookup(path string) (data interface{}, params Params, found bool) {
	if data, found := rt.static[path]; found {
		return data, nil, true
	}
	if len(rt.param.node) == 1 {
		return nil, nil, false
	}
	nd, params, found := rt.param.lookup(path, make([]Param, 0, rt.SizeHint), 1)
	if !found {
		return nil, nil, false
	}
	for i := 0; i < len(params); i++ {
		params[i].Name = nd.paramNames[i]
	}
	return nd.data, params, true
}
func (rt *Router) Build(records []Record) error {
	statics, params := makeRecords(records)
	if len(params) > MaxSize {
		return fmt.Errorf("denco: too many records")
	}
	if rt.SizeHint < 0 {
		rt.SizeHint = 0
		for _, p := range params {
			size := 0
			for _, k := range p.Key {
				if k == ParamCharacter || k == WildcardCharacter {
					size++
				}
			}
			if size > rt.SizeHint {
				rt.SizeHint = size
			}
		}
	}
	for _, r := range statics {
		rt.static[r.Key] = r.Value
	}
	if err := rt.param.build(params, 1, 0, make(map[int]struct{})); err != nil {
		return err
	}
	return nil
}
type Param struct {
	Name  string
	Value string
}
type Params []Param
func (ps Params) Get(name string) string {
	for _, p := range ps {
		if p.Name == name {
			return p.Value
		}
	}
	return ""
}
type doubleArray struct {
	bc   []baseCheck
	node []*node
}
func newDoubleArray() *doubleArray {
	return &doubleArray{
		bc:   []baseCheck{0},
		node: []*node{nil},  
	}
}
type baseCheck uint32
func (bc baseCheck) Base() int {
	return int(bc >> 10)
}
func (bc *baseCheck) SetBase(base int) {
	*bc |= baseCheck(base) << 10
}
func (bc baseCheck) Check() byte {
	return byte(bc)
}
func (bc *baseCheck) SetCheck(check byte) {
	*bc |= baseCheck(check)
}
func (bc baseCheck) IsEmpty() bool {
	return bc&0xfffffcff == 0
}
func (bc baseCheck) IsSingleParam() bool {
	return bc&paramTypeSingle == paramTypeSingle
}
func (bc baseCheck) IsWildcardParam() bool {
	return bc&paramTypeWildcard == paramTypeWildcard
}
func (bc baseCheck) IsAnyParam() bool {
	return bc&paramTypeAny != 0
}
func (bc *baseCheck) SetSingleParam() {
	*bc |= (1 << 8)
}
func (bc *baseCheck) SetWildcardParam() {
	*bc |= (1 << 9)
}
const (
	paramTypeSingle   = 0x0100
	paramTypeWildcard = 0x0200
	paramTypeAny      = 0x0300
)
func (da *doubleArray) lookup(path string, params []Param, idx int) (*node, []Param, bool) {
	indices := make([]uint64, 0, 1)
	for i := 0; i < len(path); i++ {
		if da.bc[idx].IsAnyParam() {
			indices = append(indices, (uint64(i)<<32)|(uint64(idx)&0xffffffff))
		}
		c := path[i]
		if idx = nextIndex(da.bc[idx].Base(), c); idx >= len(da.bc) || da.bc[idx].Check() != c {
			goto BACKTRACKING
		}
	}
	if next := nextIndex(da.bc[idx].Base(), TerminationCharacter); next < len(da.bc) && da.bc[next].Check() == TerminationCharacter {
		return da.node[da.bc[next].Base()], params, true
	}
	if len(indices) > 0 {
		goto BACKTRACKING
	}
	return nil, nil, false
BACKTRACKING:
	for j := len(indices) - 1; j >= 0; j-- {
		i, idx := int(indices[j]>>32), int(indices[j]&0xffffffff)
		if da.bc[idx].IsSingleParam() {
			idx := nextIndex(da.bc[idx].Base(), ParamCharacter)
			if idx >= len(da.bc) {
				break
			}
			next := NextSeparator(path, i)
			params := append(params, Param{Value: path[i:next]})
			if nd, params, found := da.lookup(path[next:], params, idx); found {
				return nd, params, true
			}
		}
		if da.bc[idx].IsWildcardParam() {
			idx := nextIndex(da.bc[idx].Base(), WildcardCharacter)
			params := append(params, Param{Value: path[i:]})
			return da.node[da.bc[idx].Base()], params, true
		}
	}
	return nil, nil, false
}
func (da *doubleArray) build(srcs []*record, idx, depth int, usedBase map[int]struct{}) error {
	sort.Stable(recordSlice(srcs))
	base, siblings, leaf, err := da.arrange(srcs, idx, depth, usedBase)
	if err != nil {
		return err
	}
	if leaf != nil {
		nd, err := makeNode(leaf)
		if err != nil {
			return err
		}
		da.bc[idx].SetBase(len(da.node))
		da.node = append(da.node, nd)
	}
	for _, sib := range siblings {
		da.setCheck(nextIndex(base, sib.c), sib.c)
	}
	for _, sib := range siblings {
		records := srcs[sib.start:sib.end]
		switch sib.c {
		case ParamCharacter:
			for _, r := range records {
				next := NextSeparator(r.Key, depth+1)
				name := r.Key[depth+1 : next]
				r.paramNames = append(r.paramNames, name)
				r.Key = r.Key[next:]
			}
			da.bc[idx].SetSingleParam()
			if err := da.build(records, nextIndex(base, sib.c), 0, usedBase); err != nil {
				return err
			}
		case WildcardCharacter:
			r := records[0]
			name := r.Key[depth+1 : len(r.Key)-1]
			r.paramNames = append(r.paramNames, name)
			r.Key = ""
			da.bc[idx].SetWildcardParam()
			if err := da.build(records, nextIndex(base, sib.c), 0, usedBase); err != nil {
				return err
			}
		default:
			if err := da.build(records, nextIndex(base, sib.c), depth+1, usedBase); err != nil {
				return err
			}
		}
	}
	return nil
}
func (da *doubleArray) setBase(i, base int) {
	da.bc[i].SetBase(base)
}