func (t Tree) TraceByte(c byte) Tree {
	return t.Trace([]byte{c})
}
TraceByte is shorthand for Trace([]byte{c}).
package trie
import (
	"fmt"
	"sort"
)
type Tree []node
type node struct {
	value interface{}
	next  int
	label byte
	match bool
	leaf  bool
}
type kv struct {
	k []byte
	v interface{}
}
func New(keys [][]byte, values []interface{}) Tree {
	if len(keys) != len(values) {
		panic("length mismatch of keys and values")
	}
	kvs := make([]kv, 0, len(keys))
	for i, k := range keys {
		kvs = append(kvs, kv{k, values[i]})
	}
	sort.Slice(kvs, func(i, j int) bool {
		a, b := kvs[i].k, kvs[j].k
		for i := 0; i < len(a) && i < len(b); i++ {
			if a[i] == b[i] {
				continue
			}
			return a[i] < b[i]
		}
		if len(a) == len(b) {
			panic(fmt.Sprintf("2 same key is passed: %v", kvs[i].k))
		}
		return len(a) < len(b)
	})
	t := Tree{node{next: 1}}
	t = t.construct(kvs, 0, 0)
	return t
}
func (t Tree) construct(kvs []kv, depth, current int) Tree {
	if depth == len(kvs[0].k) {
		t[current].match = true
		t[current].value = kvs[0].v
		kvs = kvs[1:]
		if len(kvs) == 0 {
			t[current].leaf = true
			return t
		}
	}
	p := []int{0}
	for i := 0; i < len(kvs); {
		t = append(t, node{
			label: kvs[i].k[depth],
		})
		for c := kvs[i].k[depth]; i < len(kvs) && kvs[i].k[depth] == c; i++ {
		}
		p = append(p, i)
	}
	for i := 0; i < len(p)-1; i++ {
		t[t.nextOf(current)+i].next = len(t) - t.nextOf(current) - i
		t = t.construct(kvs[p[i]:p[i+1]], depth+1, t.nextOf(current)+i)
	}
	return t
}
func (t Tree) Trace(path []byte) Tree {
	if t == nil {
		return nil
	}
	var u int
	for _, c := range path {
		if t[u].leaf {
			return nil
		}
		u = t.nextOf(u)
		v := t.nextOf(u)
		if v-u > 40 {
			u += sort.Search(v-u, func(m int) bool {
				return t[u+m].label >= c
			})
		} else {
			for ; u != v-1 && t[u].label < c; u++ {
			}
		}
		if u > v || t[u].label != c {
			return nil
		}
	}
	return t[u:]
}