package merkletrie

// this files contains fixtures for testing the Iter.
//
// - iter... functions returns iterators for newly created trees
//   for example:
//
//   + iterLeaf returns an iterator for simple tree with just the root.
//
//   + iter2Horizontal returns an iterator for a tree with 2 nodes, both
//     childs of the root.
//
// - runs... contains sets of tests, indexed by a string that helps
//   to understand each test: "nsn" means next, then step, then next
//   again.  The test also contains the expected keys of the nodes you
//   will get when calling the operations over the correspoding trees:
//   Example: runs2HorizontalSorted with iter2HorizontalSorted and so on.

func iterLeaf() *Iter {
	root := newNode(hash, "root", empty)
	return NewIter(root)
}

var runs0 = map[string][]test{
	"nn": {{next, ""}, {next, ""}},
	"ns": {{next, ""}, {step, ""}},
	"sn": {{step, ""}, {next, ""}},
	"ss": {{step, ""}, {step, ""}},
}

//   root
//    |
//    a
func iter1() *Iter {
	a := newNode(hash, "a", empty)
	root := newNode(hash, "root", []*node{a})
	return NewIter(root)
}

var runs1 = map[string][]test{
	"nn": {{next, "a"}, {next, ""}},
	"ns": {{next, "a"}, {step, ""}},
	"sn": {{step, "a"}, {next, ""}},
	"ss": {{step, "a"}, {step, ""}},
}

//     root
//      / \
//     a   b
func iter2HorizontalSorted() *Iter {
	a := newNode(hash, "a", empty)
	b := newNode(hash, "b", empty)
	root := newNode(hash, "root", []*node{a, b})
	return NewIter(root)
}

//     root
//      / \
//     b   a
func iter2HorizontalReverse() *Iter {
	a := newNode(hash, "a", empty)
	b := newNode(hash, "b", empty)
	root := newNode(hash, "root", []*node{b, a})
	return NewIter(root)
}

var runs2Horizontal = map[string][]test{
	"nnn": {{next, "a"}, {next, "b"}, {next, ""}},
	"nns": {{next, "a"}, {next, "b"}, {step, ""}},
	"nsn": {{next, "a"}, {step, "b"}, {next, ""}},
	"nss": {{next, "a"}, {step, "b"}, {step, ""}},
	"snn": {{step, "a"}, {next, "b"}, {next, ""}},
	"sns": {{step, "a"}, {next, "b"}, {step, ""}},
	"ssn": {{step, "a"}, {step, "b"}, {next, ""}},
	"sss": {{step, "a"}, {step, "b"}, {step, ""}},
}

//     root
//      |
//      a
//      |
//      b
func iter2VerticalSorted() *Iter {
	b := newNode(hash, "b", empty)
	a := newNode(hash, "a", []*node{b})
	root := newNode(hash, "root", []*node{a})
	return NewIter(root)
}

var runs2VerticalSorted = map[string][]test{
	"nnn": {{next, "a"}, {next, ""}, {next, ""}},
	"nns": {{next, "a"}, {next, ""}, {step, ""}},
	"nsn": {{next, "a"}, {step, "b"}, {next, ""}},
	"nss": {{next, "a"}, {step, "b"}, {step, ""}},
	"snn": {{step, "a"}, {next, ""}, {next, ""}},
	"sns": {{step, "a"}, {next, ""}, {step, ""}},
	"ssn": {{step, "a"}, {step, "b"}, {next, ""}},
	"sss": {{step, "a"}, {step, "b"}, {step, ""}},
}

//     root
//      |
//      b
//      |
//      a
func iter2VerticalReverse() *Iter {
	a := newNode(hash, "a", empty)
	b := newNode(hash, "b", []*node{a})
	root := newNode(hash, "root", []*node{b})
	return NewIter(root)
}

var runs2VerticalReverse = map[string][]test{
	"nnn": {{next, "b"}, {next, ""}, {next, ""}},
	"nns": {{next, "b"}, {next, ""}, {step, ""}},
	"nsn": {{next, "b"}, {step, "a"}, {next, ""}},
	"nss": {{next, "b"}, {step, "a"}, {step, ""}},
	"snn": {{step, "b"}, {next, ""}, {next, ""}},
	"sns": {{step, "b"}, {next, ""}, {step, ""}},
	"ssn": {{step, "b"}, {step, "a"}, {next, ""}},
	"sss": {{step, "b"}, {step, "a"}, {step, ""}},
}

//     root
//      /|\
//     c a b
func iter3Horizontal() *Iter {
	a := newNode(hash, "a", empty)
	b := newNode(hash, "b", empty)
	c := newNode(hash, "c", empty)
	root := newNode(hash, "root", []*node{c, a, b})
	return NewIter(root)
}

var runs3Horizontal = map[string][]test{
	"nnnn": {{next, "a"}, {next, "b"}, {next, "c"}, {next, ""}},
	"nnns": {{next, "a"}, {next, "b"}, {next, "c"}, {step, ""}},
	"nnsn": {{next, "a"}, {next, "b"}, {step, "c"}, {next, ""}},
	"nnss": {{next, "a"}, {next, "b"}, {step, "c"}, {step, ""}},
	"nsnn": {{next, "a"}, {step, "b"}, {next, "c"}, {next, ""}},
	"nsns": {{next, "a"}, {step, "b"}, {next, "c"}, {step, ""}},
	"nssn": {{next, "a"}, {step, "b"}, {step, "c"}, {next, ""}},
	"nsss": {{next, "a"}, {step, "b"}, {step, "c"}, {step, ""}},
	"snnn": {{step, "a"}, {next, "b"}, {next, "c"}, {next, ""}},
	"snns": {{step, "a"}, {next, "b"}, {next, "c"}, {step, ""}},
	"snsn": {{step, "a"}, {next, "b"}, {step, "c"}, {next, ""}},
	"snss": {{step, "a"}, {next, "b"}, {step, "c"}, {step, ""}},
	"ssnn": {{step, "a"}, {step, "b"}, {next, "c"}, {next, ""}},
	"ssns": {{step, "a"}, {step, "b"}, {next, "c"}, {step, ""}},
	"sssn": {{step, "a"}, {step, "b"}, {step, "c"}, {next, ""}},
	"ssss": {{step, "a"}, {step, "b"}, {step, "c"}, {step, ""}},
}

//     root
//      |
//      b
//      |
//      c
//      |
//      a
func iter3Vertical() *Iter {
	a := newNode(hash, "a", empty)
	c := newNode(hash, "c", []*node{a})
	b := newNode(hash, "b", []*node{c})
	root := newNode(hash, "root", []*node{b})
	return NewIter(root)
}

var runs3Vertical = map[string][]test{
	"nnnn": {{next, "b"}, {next, ""}, {next, ""}, {next, ""}},
	"nnns": {{next, "b"}, {next, ""}, {next, ""}, {step, ""}},
	"nnsn": {{next, "b"}, {next, ""}, {step, ""}, {next, ""}},
	"nnss": {{next, "b"}, {next, ""}, {step, ""}, {step, ""}},
	"nsnn": {{next, "b"}, {step, "c"}, {next, ""}, {next, ""}},
	"nsns": {{next, "b"}, {step, "c"}, {next, ""}, {step, ""}},
	"nssn": {{next, "b"}, {step, "c"}, {step, "a"}, {next, ""}},
	"nsss": {{next, "b"}, {step, "c"}, {step, "a"}, {step, ""}},
	"snnn": {{step, "b"}, {next, ""}, {next, ""}, {next, ""}},
	"snns": {{step, "b"}, {next, ""}, {next, ""}, {step, ""}},
	"snsn": {{step, "b"}, {next, ""}, {step, ""}, {next, ""}},
	"snss": {{step, "b"}, {next, ""}, {step, ""}, {step, ""}},
	"ssnn": {{step, "b"}, {step, "c"}, {next, ""}, {next, ""}},
	"ssns": {{step, "b"}, {step, "c"}, {next, ""}, {step, ""}},
	"sssn": {{step, "b"}, {step, "c"}, {step, "a"}, {next, ""}},
	"ssss": {{step, "b"}, {step, "c"}, {step, "a"}, {step, ""}},
}

//     root
//      / \
//     c   a
//     |
//     b
func iter3Mix1() *Iter {
	a := newNode(hash, "a", empty)
	b := newNode(hash, "b", empty)
	c := newNode(hash, "c", []*node{b})
	root := newNode(hash, "root", []*node{c, a})
	return NewIter(root)
}

var runs3Mix1 = map[string][]test{
	"nnnn": {{next, "a"}, {next, "c"}, {next, ""}, {next, ""}},
	"nnns": {{next, "a"}, {next, "c"}, {next, ""}, {step, ""}},
	"nnsn": {{next, "a"}, {next, "c"}, {step, "b"}, {next, ""}},
	"nnss": {{next, "a"}, {next, "c"}, {step, "b"}, {step, ""}},
	"nsnn": {{next, "a"}, {step, "c"}, {next, ""}, {next, ""}},
	"nsns": {{next, "a"}, {step, "c"}, {next, ""}, {step, ""}},
	"nssn": {{next, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
	"nsss": {{next, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
	"snnn": {{step, "a"}, {next, "c"}, {next, ""}, {next, ""}},
	"snns": {{step, "a"}, {next, "c"}, {next, ""}, {step, ""}},
	"snsn": {{step, "a"}, {next, "c"}, {step, "b"}, {next, ""}},
	"snss": {{step, "a"}, {next, "c"}, {step, "b"}, {step, ""}},
	"ssnn": {{step, "a"}, {step, "c"}, {next, ""}, {next, ""}},
	"ssns": {{step, "a"}, {step, "c"}, {next, ""}, {step, ""}},
	"sssn": {{step, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
	"ssss": {{step, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
}

//     root
//      / \
//     b   a
//         |
//         c
func iter3Mix2() *Iter {
	b := newNode(hash, "b", empty)
	c := newNode(hash, "c", empty)
	a := newNode(hash, "a", []*node{c})
	root := newNode(hash, "root", []*node{b, a})
	return NewIter(root)
}

var runs3Mix2 = map[string][]test{
	"nnnn": {{next, "a"}, {next, "b"}, {next, ""}, {next, ""}},
	"nnns": {{next, "a"}, {next, "b"}, {next, ""}, {step, ""}},
	"nnsn": {{next, "a"}, {next, "b"}, {step, ""}, {next, ""}},
	"nnss": {{next, "a"}, {next, "b"}, {step, ""}, {step, ""}},
	"nsnn": {{next, "a"}, {step, "c"}, {next, "b"}, {next, ""}},
	"nsns": {{next, "a"}, {step, "c"}, {next, "b"}, {step, ""}},
	"nssn": {{next, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
	"nsss": {{next, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
	"snnn": {{step, "a"}, {next, "b"}, {next, ""}, {next, ""}},
	"snns": {{step, "a"}, {next, "b"}, {next, ""}, {step, ""}},
	"snsn": {{step, "a"}, {next, "b"}, {step, ""}, {next, ""}},
	"snss": {{step, "a"}, {next, "b"}, {step, ""}, {step, ""}},
	"ssnn": {{step, "a"}, {step, "c"}, {next, "b"}, {next, ""}},
	"ssns": {{step, "a"}, {step, "c"}, {next, "b"}, {step, ""}},
	"sssn": {{step, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
	"ssss": {{step, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
}

//      root
//      / | \
//     /  |  ----
//    f   d      h --------
//   /\         /  \      |
//  e   a      j   b      g
//  |  / \     |
//  l  n  k    icm
//     |
//     o
//     |
//     p
func iterCrazy() *Iter {
	l := newNode(hash, "l", empty)
	e := newNode(hash, "e", []*node{l})

	p := newNode(hash, "p", empty)
	o := newNode(hash, "o", []*node{p})
	n := newNode(hash, "n", []*node{o})
	k := newNode(hash, "k", empty)
	a := newNode(hash, "a", []*node{n, k})
	f := newNode(hash, "f", []*node{e, a})

	d := newNode(hash, "d", empty)

	i := newNode(hash, "i", empty)
	c := newNode(hash, "c", empty)
	m := newNode(hash, "m", empty)
	j := newNode(hash, "j", []*node{i, c, m})
	b := newNode(hash, "b", empty)
	g := newNode(hash, "g", empty)
	h := newNode(hash, "h", []*node{j, b, g})

	root := newNode(hash, "root", []*node{f, d, h})
	return NewIter(root)
}

var (
	n = next
	s = step
)

var runsCrazy = map[string][]test{
	"nn nn n": {{n, "d"}, {n, "f"}, {n, "h"}, {n, ""}, {n, ""}},
	"nn nn s": {{n, "d"}, {n, "f"}, {n, "h"}, {n, ""}, {s, ""}},
	"nn ns n": {{n, "d"}, {n, "f"}, {n, "h"}, {s, "b"}, {n, "g"}},
	"nn ns s": {{n, "d"}, {n, "f"}, {n, "h"}, {s, "b"}, {s, "g"}},
	"nn sn n": {{n, "d"}, {n, "f"}, {s, "a"}, {n, "e"}, {n, "h"}},
	"nn sn s": {{n, "d"}, {n, "f"}, {s, "a"}, {n, "e"}, {s, "l"}},
	"nn ss n": {{n, "d"}, {n, "f"}, {s, "a"}, {s, "k"}, {n, "n"}},
	"nn ss s": {{n, "d"}, {n, "f"}, {s, "a"}, {s, "k"}, {s, "n"}},
	"ns nn n": {{n, "d"}, {s, "f"}, {n, "h"}, {n, ""}, {n, ""}},
	"ns nn s": {{n, "d"}, {s, "f"}, {n, "h"}, {n, ""}, {s, ""}},
	"ns ns n": {{n, "d"}, {s, "f"}, {n, "h"}, {s, "b"}, {n, "g"}},
	"ns ns s": {{n, "d"}, {s, "f"}, {n, "h"}, {s, "b"}, {s, "g"}},
	"ns sn n": {{n, "d"}, {s, "f"}, {s, "a"}, {n, "e"}, {n, "h"}},

	"ns ss ns ss": {
		{n, "d"}, {s, "f"},
		{s, "a"}, {s, "k"},
		{n, "n"}, {s, "o"},
		{s, "p"}, {s, "e"},
	},

	"ns ss ns sn": {
		{n, "d"}, {s, "f"},
		{s, "a"}, {s, "k"},
		{n, "n"}, {s, "o"},
		{s, "p"}, {n, "e"},
	},

	"nn ns ns ss nn": {
		{n, "d"}, {n, "f"},
		{n, "h"}, {s, "b"},
		{n, "g"}, {s, "j"},
		{s, "c"}, {s, "i"},
		{n, "m"}, {n, ""},
	},
}