diff options
Diffstat (limited to 'difftree/internal/merkletrie/iter_fixtures_test.go')
| -rw-r--r-- | difftree/internal/merkletrie/iter_fixtures_test.go | 330 |
1 files changed, 330 insertions, 0 deletions
diff --git a/difftree/internal/merkletrie/iter_fixtures_test.go b/difftree/internal/merkletrie/iter_fixtures_test.go new file mode 100644 index 0000000..20bddaf --- /dev/null +++ b/difftree/internal/merkletrie/iter_fixtures_test.go @@ -0,0 +1,330 @@ +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, ""}, + }, +} |