func (t *Tree) LongestPrefix(s string) (string, interface{}, bool) {
	var last *leafNode
	n := t.root
	search := s
	for {
		if n.isLeaf() {
			last = n.leaf
		}
		if len(search) == 0 {
			break
		}
		n = n.getEdge(search[0])
		if n == nil {
			break
		}
		if strings.HasPrefix(search, n.prefix) {
			search = search[len(n.prefix):]
		} else {
			break
		}
	}
	if last != nil {
		return last.key, last.val, true
	}
	return "", nil, false
}
LongestPrefix is like Get, but instead of an
exact match, it will return the longest prefix match.
package radix
import (
	"sort"
	"strings"
)
type WalkFn func(s string, v interface{}) bool
type leafNode struct {
	key string
	val interface{}
}
type edge struct {
	label byte
	node  *node
}
type node struct {
	leaf *leafNode
	prefix string
	edges edges
}
func (n *node) isLeaf() bool {
	return n.leaf != nil
}
func (n *node) addEdge(e edge) {
	n.edges = append(n.edges, e)
	n.edges.Sort()
}
func (n *node) replaceEdge(e edge) {
	num := len(n.edges)
	idx := sort.Search(num, func(i int) bool {
		return n.edges[i].label >= e.label
	})
	if idx < num && n.edges[idx].label == e.label {
		n.edges[idx].node = e.node
		return
	}
	panic("replacing missing edge")
}
func (n *node) getEdge(label byte) *node {
	num := len(n.edges)
	idx := sort.Search(num, func(i int) bool {
		return n.edges[i].label >= label
	})
	if idx < num && n.edges[idx].label == label {
		return n.edges[idx].node
	}
	return nil
}
type edges []edge
func (e edges) Len() int {
	return len(e)
}
func (e edges) Less(i, j int) bool {
	return e[i].label < e[j].label
}
func (e edges) Swap(i, j int) {
	e[i], e[j] = e[j], e[i]
}
func (e edges) Sort() {
	sort.Sort(e)
}
type Tree struct {
	root *node
	size int
}
func New() *Tree {
	return NewFromMap(nil)
}
func NewFromMap(m map[string]interface{}) *Tree {
	t := &Tree{root: &node{}}
	for k, v := range m {
		t.Insert(k, v)
	}
	return t
}
func (t *Tree) Len() int {
	return t.size
}
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 (t *Tree) Insert(s string, v interface{}) (interface{}, bool) {
	var parent *node
	n := t.root
	search := s
	for {
		if len(search) == 0 {
			if n.isLeaf() {
				old := n.leaf.val
				n.leaf.val = v
				return old, true
			} else {
				n.leaf = &leafNode{
					key: s,
					val: v,
				}
				t.size++
				return nil, false
			}
		}
		parent = n
		n = n.getEdge(search[0])
		if n == nil {
			e := edge{
				label: search[0],
				node: &node{
					leaf: &leafNode{
						key: s,
						val: v,
					},
					prefix: search,
				},
			}
			parent.addEdge(e)
			t.size++
			return nil, false
		}
		commonPrefix := longestPrefix(search, n.prefix)
		if commonPrefix == len(n.prefix) {
			search = search[commonPrefix:]
			continue
		}
		t.size++
		child := &node{
			prefix: search[:commonPrefix],
		}
		parent.replaceEdge(edge{
			label: search[0],
			node:  child,
		})
		child.addEdge(edge{
			label: n.prefix[commonPrefix],
			node:  n,
		})
		n.prefix = n.prefix[commonPrefix:]
		leaf := &leafNode{
			key: s,
			val: v,
		}
		search = search[commonPrefix:]
		if len(search) == 0 {
			child.leaf = leaf
			return nil, false
		}
		child.addEdge(edge{
			label: search[0],
			node: &node{
				leaf:   leaf,
				prefix: search,
			},
		})
		return nil, false
	}
	return nil, false
}
func (t *Tree) Delete(s string) (interface{}, bool) {
	n := t.root
	search := s
	for {
		if len(search) == 0 {
			if !n.isLeaf() {
				break
			}
			goto DELETE
		}
		n = n.getEdge(search[0])
		if n == nil {
			break
		}
		if strings.HasPrefix(search, n.prefix) {
			search = search[len(n.prefix):]
		} else {
			break
		}
	}
	return nil, false
DELETE:
	leaf := n.leaf
	n.leaf = nil
	t.size--
	if len(n.edges) == 1 {
		e := n.edges[0]
		child := e.node
		n.prefix = n.prefix + child.prefix
		n.leaf = child.leaf
		n.edges = child.edges
	}
	return leaf.val, true
}
func (t *Tree) Get(s string) (interface{}, bool) {
	n := t.root
	search := s
	for {
		if len(search) == 0 {
			if n.isLeaf() {
				return n.leaf.val, true
			}
			break
		}
		n = n.getEdge(search[0])
		if n == nil {
			break
		}
		if strings.HasPrefix(search, n.prefix) {
			search = search[len(n.prefix):]
		} else {
			break
		}
	}
	return nil, false
}