func TestTrie_compact(t *testing.T) {
	trie := NewTrie()
	trie.Insert(Prefix("a"), 0)
	trie.Insert(Prefix("ab"), 0)
	trie.Insert(Prefix("abc"), 0)
	trie.Insert(Prefix("abcd"), 0)
	trie.Insert(Prefix("abcde"), 0)
	trie.Insert(Prefix("abcdef"), 0)
	trie.Insert(Prefix("abcdefg"), 0)
	trie.Insert(Prefix("abcdefgi"), 0)
	trie.Insert(Prefix("abcdefgij"), 0)
	trie.Insert(Prefix("abcdefgijk"), 0)
	trie.Delete(Prefix("abcdef"))
	trie.Delete(Prefix("abcde"))
	trie.Delete(Prefix("abcdefg"))
	trie.Delete(Prefix("a"))
	trie.Delete(Prefix("abc"))
	trie.Delete(Prefix("ab"))
	trie.Visit(func(prefix Prefix, item Item) error {
		for ch := byte(97); ch <= 107; ch++ {
			if c := bytes.Count(prefix, []byte{ch}); c > 1 {
				t.Errorf("%q appeared in %q %v times", ch, prefix, c)
			}
		}
		return nil
	})
}
/*
func TestTrie_Dump(t *testing.T) {
trie := NewTrie()

data := []testData{
{"Honda", nil, success},
{"Honza", nil, success},
{"Jenik", nil, success},
{"Pepan", nil, success},
{"Pepin", nil, success},
}

for i, v := range data {
if _, ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
t.Logf("INSERT %v %v", v.key, v.value)
t.Fatalf("Unexpected return value, expected=%v, got=%v", i, ok)
}
}

dump := `
+--+--+ Hon +--+--+ da
|           |
|           +--+ za
|
+--+ Jenik
|
+--+ Pep +--+--+ an
|
+--+ in
`

var buf bytes.Buffer
trie.Dump(buf)

if !bytes.Equal(buf.Bytes(), dump) {
t.Logf("DUMP")
t.Fatalf("Unexpected dump generated, expected\n\n%v\ngot\n\n%v", dump, buf.String())
}
}
package patricia
import (
	"bytes"
	"errors"
	"fmt"
	"strings"
	"testing"
)
const (
	success = true
	failure = false
)
type testData struct {
	key    string
	value  interface{}
	retVal bool
}
func TestTrie_InsertDifferentPrefixes(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepaneeeeeeeeeeeeee", "Pepan Zdepan", success},
		{"Honzooooooooooooooo", "Honza Novak", success},
		{"Jenikuuuuuuuuuuuuuu", "Jenik Poustevnicek", success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
}
func TestTrie_InsertDuplicatePrefixes(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Pepan", "Pepan Zdepan", failure},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
}
func TestTrie_InsertVariousPrefixes(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Pepin", "Pepin Omacka", success},
		{"Honza", "Honza Novak", success},
		{"Jenik", "Jenik Poustevnicek", success},
		{"Pepan", "Pepan Dupan", failure},
		{"Karel", "Karel Pekar", success},
		{"Jenik", "Jenik Poustevnicek", failure},
		{"Pepanek", "Pepanek Zemlicka", success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
}
func TestTrie_InsertAndMatchPrefix(t *testing.T) {
	trie := NewTrie()
	t.Log("INSERT prefix=by week")
	trie.Insert(Prefix("by week"), 2)
	t.Log("INSERT prefix=by")
	trie.Insert(Prefix("by"), 1)
	if !trie.Match(Prefix("by")) {
		t.Error("MATCH prefix=by, expected=true, got=false")
	}
}
func TestTrie_SetGet(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Pepin", "Pepin Omacka", success},
		{"Honza", "Honza Novak", success},
		{"Jenik", "Jenik Poustevnicek", success},
		{"Pepan", "Pepan Dupan", failure},
		{"Karel", "Karel Pekar", success},
		{"Jenik", "Jenik Poustevnicek", failure},
		{"Pepanek", "Pepanek Zemlicka", success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	for _, v := range data {
		t.Logf("SET %q to 10", v.key)
		trie.Set(Prefix(v.key), 10)
	}
	for _, v := range data {
		value := trie.Get(Prefix(v.key))
		t.Logf("GET %q => %v", v.key, value)
		if value.(int) != 10 {
			t.Errorf("Unexpected return value, != 10", value)
		}
	}
	if value := trie.Get(Prefix("random crap")); value != nil {
		t.Errorf("Unexpected return value, %v != <nil>", value)
	}
}
func TestTrie_Match(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Pepin", "Pepin Omacka", success},
		{"Honza", "Honza Novak", success},
		{"Jenik", "Jenik Poustevnicek", success},
		{"Pepan", "Pepan Dupan", failure},
		{"Karel", "Karel Pekar", success},
		{"Jenik", "Jenik Poustevnicek", failure},
		{"Pepanek", "Pepanek Zemlicka", success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	for _, v := range data {
		matched := trie.Match(Prefix(v.key))
		t.Logf("MATCH %q => %v", v.key, matched)
		if !matched {
			t.Errorf("Inserted key %q was not matched", v.key)
		}
	}
	if trie.Match(Prefix("random crap")) {
		t.Errorf("Key that was not inserted matched: %q", "random crap")
	}
}
func TestTrie_MatchFalsePositive(t *testing.T) {
	trie := NewTrie()
	if ok := trie.Insert(Prefix("A"), 1); !ok {
		t.Fatal("INSERT prefix=A, item=1 not ok")
	}
	resultMatchSubtree := trie.MatchSubtree(Prefix("A extra"))
	resultMatch := trie.Match(Prefix("A extra"))
	if resultMatchSubtree != false {
		t.Error("MatchSubtree returned false positive")
	}
	if resultMatch != false {
		t.Error("Match returned false positive")
	}
}
func TestTrie_MatchSubtree(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Pepin", "Pepin Omacka", success},
		{"Honza", "Honza Novak", success},
		{"Jenik", "Jenik Poustevnicek", success},
		{"Pepan", "Pepan Dupan", failure},
		{"Karel", "Karel Pekar", success},
		{"Jenik", "Jenik Poustevnicek", failure},
		{"Pepanek", "Pepanek Zemlicka", success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert(Prefix(v.key), v.value); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	for _, v := range data {
		key := Prefix(v.key[:3])
		matched := trie.MatchSubtree(key)
		t.Logf("MATCH_SUBTREE %q => %v", key, matched)
		if !matched {
			t.Errorf("Subtree %q was not matched", v.key)
		}
	}
}
func TestTrie_Visit(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepa", 0, success},
		{"Pepa Zdepa", 1, success},
		{"Pepa Kuchar", 2, success},
		{"Honza", 3, success},
		{"Jenik", 4, success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	if err := trie.Visit(func(prefix Prefix, item Item) error {
		name := data[item.(int)].key
		t.Logf("VISITING prefix=%q, item=%v", prefix, item)
		if !strings.HasPrefix(string(prefix), name) {
			t.Errorf("Unexpected prefix encountered, %q not a prefix of %q", prefix, name)
		}
		return nil
	}); err != nil {
		t.Fatal(err)
	}
}
func TestTrie_VisitSkipSubtree(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepa", 0, success},
		{"Pepa Zdepa", 1, success},
		{"Pepa Kuchar", 2, success},
		{"Honza", 3, success},
		{"Jenik", 4, success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	if err := trie.Visit(func(prefix Prefix, item Item) error {
		t.Logf("VISITING prefix=%q, item=%v", prefix, item)
		if item.(int) == 0 {
			t.Logf("SKIP %q", prefix)
			return SkipSubtree
		}
		if strings.HasPrefix(string(prefix), "Pepa") {
			t.Errorf("Unexpected prefix encountered, %q", prefix)
		}
		return nil
	}); err != nil {
		t.Fatal(err)
	}
}
func TestTrie_VisitReturnError(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepa", 0, success},
		{"Pepa Zdepa", 1, success},
		{"Pepa Kuchar", 2, success},
		{"Honza", 3, success},
		{"Jenik", 4, success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	someErr := errors.New("Something exploded")
	if err := trie.Visit(func(prefix Prefix, item Item) error {
		t.Logf("VISITING prefix=%q, item=%v", prefix, item)
		if item.(int) == 0 {
			return someErr
		}
		if item.(int) != 0 {
			t.Errorf("Unexpected prefix encountered, %q", prefix)
		}
		return nil
	}); err != nil && err != someErr {
		t.Fatal(err)
	}
}
func TestTrie_VisitSubtree(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepa", 0, success},
		{"Pepa Zdepa", 1, success},
		{"Pepa Kuchar", 2, success},
		{"Honza", 3, success},
		{"Jenik", 4, success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	var counter int
	subtreePrefix := []byte("Pep")
	t.Log("VISIT Pep")
	if err := trie.VisitSubtree(subtreePrefix, func(prefix Prefix, item Item) error {
		t.Logf("VISITING prefix=%q, item=%v", prefix, item)
		if !bytes.HasPrefix(prefix, subtreePrefix) {
			t.Errorf("Unexpected prefix encountered, %q does not extend %q",
				prefix, subtreePrefix)
		}
		if len(prefix) > len(data[item.(int)].key) {
			t.Fatalf("Something is rather fishy here, prefix=%q", prefix)
		}
		counter++
		return nil
	}); err != nil {
		t.Fatal(err)
	}
	if counter != 3 {
		t.Error("Unexpected number of nodes visited")
	}
}
func TestTrie_VisitPrefixes(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"P", 0, success},
		{"Pe", 1, success},
		{"Pep", 2, success},
		{"Pepa", 3, success},
		{"Pepa Zdepa", 4, success},
		{"Pepa Kuchar", 5, success},
		{"Honza", 6, success},
		{"Jenik", 7, success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	var counter int
	word := []byte("Pepa")
	if err := trie.VisitPrefixes(word, func(prefix Prefix, item Item) error {
		t.Logf("VISITING prefix=%q, item=%v", prefix, item)
		if !bytes.HasPrefix(word, prefix) {
			t.Errorf("Unexpected prefix encountered, %q is not a prefix of %q",
				prefix, word)
		}
		counter++
		return nil
	}); err != nil {
		t.Fatal(err)
	}
	if counter != 4 {
		t.Error("Unexpected number of nodes visited")
	}
}
func TestParticiaTrie_Delete(t *testing.T) {
	trie := NewTrie()
	data := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Honza", "Honza Novak", success},
		{"Jenik", "Jenik Poustevnicek", success},
	}
	for _, v := range data {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	for _, v := range data {
		t.Logf("DELETE word=%v, success=%v", v.key, v.retVal)
		if ok := trie.Delete([]byte(v.key)); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
}
func TestParticiaTrie_DeleteNonExistent(t *testing.T) {
	trie := NewTrie()
	insertData := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Honza", "Honza Novak", success},
		{"Jenik", "Jenik Poustevnicek", success},
	}
	deleteData := []testData{
		{"Pepan", "Pepan Zdepan", success},
		{"Honza", "Honza Novak", success},
		{"Pepan", "Pepan Zdepan", failure},
		{"Jenik", "Jenik Poustevnicek", success},
		{"Honza", "Honza Novak", failure},
	}
	for _, v := range insertData {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	for _, v := range deleteData {
		t.Logf("DELETE word=%v, success=%v", v.key, v.retVal)
		if ok := trie.Delete([]byte(v.key)); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
}
func TestParticiaTrie_DeleteSubtree(t *testing.T) {
	trie := NewTrie()
	insertData := []testData{
		{"P", 0, success},
		{"Pe", 1, success},
		{"Pep", 2, success},
		{"Pepa", 3, success},
		{"Pepa Zdepa", 4, success},
		{"Pepa Kuchar", 5, success},
		{"Honza", 6, success},
		{"Jenik", 7, success},
	}
	deleteData := []testData{
		{"Pe", -1, success},
		{"Pe", -1, failure},
		{"Honzik", -1, failure},
		{"Honza", -1, success},
		{"Honza", -1, failure},
		{"Pep", -1, failure},
		{"P", -1, success},
		{"Nobody", -1, failure},
		{"", -1, success},
	}
	for _, v := range insertData {
		t.Logf("INSERT prefix=%v, item=%v, success=%v", v.key, v.value, v.retVal)
		if ok := trie.Insert([]byte(v.key), v.value); ok != v.retVal {
			t.Fatalf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
	for _, v := range deleteData {
		t.Logf("DELETE_SUBTREE prefix=%v, success=%v", v.key, v.retVal)
		if ok := trie.DeleteSubtree([]byte(v.key)); ok != v.retVal {
			t.Errorf("Unexpected return value, expected=%v, got=%v", v.retVal, ok)
		}
	}
}