package routes

import "testing"

func assertTreeLookup(tree *node, path string, want string, t *testing.T) {
	have := tree.lookup(path)
	if have != want {
		t.Errorf("lookup  path=%q  have=%q  want=%q", path, have, want)
	}
}

func TestRadixTree(t *testing.T) {
	tree := newRadixTree()
	tree.add("/some/path", "somepath")
	tree.add("/some/otherpath", "someotherpath")
	tree.add("/something/tricky", "tricky")
	if len(tree.children) != 2 {
		t.Errorf("expected 2 children in radix tree")
	}
	tree.add("/somebody/else", "somebody")
	if len(tree.children) != 3 {
		t.Errorf("expected 3 children in radix tree")
	}
	have, _ := tree.match("/something/tricky")
	if have != "tricky" {
		t.Errorf("have=%q  want=%q", have, "tricky")
	}
}

func TestRadixTreeRootPath(t *testing.T) {
	tree := newRadixTree()
	tree.add("/", "root")
	tree.add("/path", "path")
	assertTreeLookup(tree, "/", "root", t)
	assertTreeLookup(tree, "/path", "path", t)
	assertTreeLookup(tree, "/notreal", "", t)
}

func TestRadixTreeWildcards(t *testing.T) {
	tree := newRadixTree()
	tree.add("/some/path", "somepath")
	tree.add("/some/*/otherstuff", "otherstuff")
	tree.add("/some/*", "wildcard")
	tree.add("/$", "404")
	assertTreeLookup(tree, "/some/path", "somepath", t)
	assertTreeLookup(tree, "/some/gibberish", "wildcard", t)
	assertTreeLookup(tree, "/some/gibberish/otherstuff", "otherstuff", t)
	assertTreeLookup(tree, "/notreal", "404", t)
	assertTreeLookup(tree, "/also/notreal", "404", t)
}

func TestRadixTreePartialWildcards(t *testing.T) {
	tree := newRadixTree()
	tree.add("/literal", "literal")
	tree.add("/literal.*", "literal_with_fmt")
	tree.add("/*.*", "wildcard_with_fmt")
	tree.add("/*", "wildcard")
	assertTreeLookup(tree, "/literal", "literal", t)
	assertTreeLookup(tree, "/literal.", "literal_with_fmt", t)
	assertTreeLookup(tree, "/literal.json", "literal_with_fmt", t)
	assertTreeLookup(tree, "/literal.json/bogus", "", t)
	assertTreeLookup(tree, "/wc", "wildcard", t)
	assertTreeLookup(tree, "/wc.json", "wildcard_with_fmt", t)
	assertTreeLookup(tree, "/wc.json.morejson", "wildcard_with_fmt", t)
	assertTreeLookup(tree, "/wc.json/bogus", "", t)
}

func TestRadixTreeGlobbing(t *testing.T) {
	tree := newRadixTree()
	tree.add("/*", "wc")
	assertTreeLookup(tree, "/foo", "wc", t)
	assertTreeLookup(tree, "/foo/bar", "", t)
	tree.add("/$", "glob")
	assertTreeLookup(tree, "/foo/bar", "glob", t)
}

func BenchmarkLookupDeepRouteRadix(b *testing.B) {
	tree := newRadixTree()
	tree.add("/1/2/3/4/5/6/7/8/9/10", "route")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		tree.match("/1/2/3/4/5/6/7/8/9/10")
	}
}

func BenchmarkLookupShallowRouteRadix(b *testing.B) {
	tree := newRadixTree()
	tree.add("/1", "route")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		tree.match("/1")
	}
}

func BenchmarkLookupBranchingRouteRadix(b *testing.B) {
	tree := newRadixTree()
	tree.add("/very/very/exact/match", "vvem")
	tree.add("/*/very/exact/match", "*vem")
	tree.add("/*/*/exact/match", "**em")
	tree.add("/*/*/*/match", "***m")
	tree.add("/*/*/*/*", "****")
	tree.add("/very/*/*/*", "v***")
	tree.add("/very/very/*/*", "vv**")
	tree.add("/very/very/exact/*", "vve*")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		tree.match("/very/very/exact/match")
	}
}
