Generic Trie for storing bytes

trie.go

package trie

const (
	// Number of possible values represented by a single byte.
	byteValues = 1 << 8
)

type Trie struct {
	culDeSac bool
	children []*Trie
}

func NewTrie() *Trie {
	return &Trie{
		culDeSac: false,
		children: make([]*Trie, byteValues),
	}
}

func (t *Trie) Add(data []byte) {
	t.children[data[0]] = NewTrie()
	if len(data) == 1 {
		t.children[data[0]].culDeSac = true
		return
	}
	t.children[data[0]].Add(data[1:])
}

func (t *Trie) Contains(data []byte) bool {
	next := t.children[data[0]]
	if next == nil {
		return false
	}
	if len(data) == 1 {
		return next.culDeSac
	}
	return next.Contains(data[1:])
}