add merkletrie iterator and its helper frame type (#252)

* add merkletrie iterator and its helper frame type

* requested changes by mcuadros

* reuqested changes: smola

1 files changed, 108 insertions, 0 deletions

diff --git a/utils/merkletrie/internal/frame/frame_test.go b/utils/merkletrie/internal/frame/frame_test.go
new file mode 100644
index 0000000..9cc0994
--- /dev/null
+++ b/utils/merkletrie/internal/frame/frame_test.go
@@ -0,0 +1,108 @@
+package frame
+
+import (
+	"fmt"
+	"testing"
+
+	"srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+
+	. "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type FrameSuite struct{}
+
+var _ = Suite(&FrameSuite{})
+
+func (s *FrameSuite) TestNewFrameFromEmptyDir(c *C) {
+	A, err := fsnoder.New("A()")
+	c.Assert(err, IsNil)
+
+	frame, err := New(A)
+	c.Assert(err, IsNil)
+
+	expectedString := `[]`
+	c.Assert(frame.String(), Equals, expectedString)
+
+	first, ok := frame.First()
+	c.Assert(first, IsNil)
+	c.Assert(ok, Equals, false)
+
+	first, ok = frame.First()
+	c.Assert(first, IsNil)
+	c.Assert(ok, Equals, false)
+
+	l := frame.Len()
+	c.Assert(l, Equals, 0)
+}
+
+func (s *FrameSuite) TestNewFrameFromNonEmpty(c *C) {
+	//        _______A/________
+	//        |     /  \       |
+	//        x    y    B/     C/
+	//                         |
+	//                         z
+	root, err := fsnoder.New("A(x<> y<> B() C(z<>))")
+	c.Assert(err, IsNil)
+	frame, err := New(root)
+	c.Assert(err, IsNil)
+
+	expectedString := `["B", "C", "x", "y"]`
+	c.Assert(frame.String(), Equals, expectedString)
+
+	l := frame.Len()
+	c.Assert(l, Equals, 4)
+
+	checkFirstAndDrop(c, frame, "B", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 3)
+
+	checkFirstAndDrop(c, frame, "C", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 2)
+
+	checkFirstAndDrop(c, frame, "x", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 1)
+
+	checkFirstAndDrop(c, frame, "y", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 0)
+
+	checkFirstAndDrop(c, frame, "", false)
+	l = frame.Len()
+	c.Assert(l, Equals, 0)
+
+	checkFirstAndDrop(c, frame, "", false)
+}
+
+func checkFirstAndDrop(c *C, f *Frame, expectedNodeName string, expectedOK bool) {
+	first, ok := f.First()
+	c.Assert(ok, Equals, expectedOK)
+	if expectedOK {
+		c.Assert(first.Name(), Equals, expectedNodeName)
+	}
+
+	f.Drop()
+}
+
+// a mock noder that returns error when Children() is called
+type errorNoder struct{}
+
+func (e *errorNoder) Hash() []byte   { return nil }
+func (e *errorNoder) Name() string   { return "" }
+func (e *errorNoder) String() string { return "" }
+func (e *errorNoder) IsDir() bool    { return true }
+func (e *errorNoder) Children() ([]noder.Noder, error) {
+	return nil, fmt.Errorf("mock error")
+}
+func (e *errorNoder) NumChildren() (int, error) {
+	return 0, fmt.Errorf("mock error")
+}
+
+func (s *FrameSuite) TestNewFrameErrors(c *C) {
+	_, err := New(&errorNoder{})
+	c.Assert(err, Not(IsNil))
+}