package merkletrie
import . "gopkg.in/check.v1"
type IterSuite struct{}
var _ = Suite(&IterSuite{})
// we don't care about hashes for iterating the tree, so
// use this hash for every object
var hash = []byte{}
// leafs have no children, use this empty list.
var empty = []*node{}
// test a defined as an operation to run on an iterator and the key of
// the node expected to be returned by the operation. Use "" as the
// expected key for when there are no more objects in the tree.
type test struct {
operation int // next or step
expected string // key of the expected node, "" for nil node
}
// test.operation
const (
next = iota
step
)
// goes over a list of tests, calling each operation on the iter and
// checking that the obtained result is equal to the expected result
func runTests(c *C, description string, iter *Iter, list []test) {
var obtained Noder
var ok bool
var comment CommentInterface
for i, t := range list {
comment = Commentf("description %q, operation #%d",
description, i+1)
switch t.operation {
case next:
obtained, ok = iter.Next()
case step:
obtained, ok = iter.Step()
default:
c.Fatalf("invalid operation %d", t.operation)
}
if t.expected == "" {
c.Assert(ok, Equals, false, comment)
c.Assert(obtained, IsNil, comment)
} else {
c.Assert(ok, Equals, true, comment)
c.Assert(obtained.Key(), Equals, t.expected, comment)
}
}
}
// a simple tree consisting on just a leaf
func (s *IterSuite) TestLeaf(c *C) {
for description, tests := range runs0 {
runTests(c, description, iterLeaf(), tests)
}
}
// root
// |
// a
func (s *IterSuite) TestOneChild(c *C) {
for description, tests := range runs1 {
runTests(c, description, iter1(), tests)
}
}
// root
// / \
// a b
func (s *IterSuite) Test2HorizontalSorted(c *C) {
for description, tests := range runs2Horizontal {
runTests(c, description, iter2HorizontalSorted(), tests)
}
}
// root
// / \
// b a
func (s *IterSuite) Test2HorizontalReverse(c *C) {
for description, tests := range runs2Horizontal {
runTests(c, description, iter2HorizontalReverse(), tests)
}
}
// root
// |
// a
// |
// b
func (s *IterSuite) Test2VerticalSorted(c *C) {
for description, tests := range runs2VerticalSorted {
runTests(c, description, iter2VerticalSorted(), tests)
}
}
// root
// |
// b
// |
// a
func (s *IterSuite) Test2VerticalReverse(c *C) {
for description, tests := range runs2VerticalReverse {
runTests(c, description, iter2VerticalReverse(), tests)
}
}
// root
// /|\
// c a b
func (s *IterSuite) Test3Horizontal(c *C) {
for description, tests := range runs3Horizontal {
runTests(c, description, iter3Horizontal(), tests)
}
}
// root
// |
// b
// |
// c
// |
// a
func (s *IterSuite) Test3Vertical(c *C) {
for description, tests := range runs3Vertical {
runTests(c, description, iter3Vertical(), tests)
}
}
// root
// / \
// c a
// |
// b
func (s *IterSuite) Test3Mix1(c *C) {
for description, tests := range runs3Mix1 {
runTests(c, description, iter3Mix1(), tests)
}
}
// root
// / \
// b a
// |
// c
func (s *IterSuite) Test3Mix2(c *C) {
for description, tests := range runs3Mix2 {
runTests(c, description, iter3Mix2(), tests)
}
}
// root
// / | \
// / | ----
// f d h --------
// /\ / \ |
// e a j b g
// | / \ |
// l n k icm
// |
// o
// |
// p
func (s *IterSuite) TestCrazy(c *C) {
for description, tests := range runsCrazy {
runTests(c, description, iterCrazy(), tests)
}
}
