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

* add merkletrie iterator and its helper frame type

* requested changes by mcuadros

* reuqested changes: smola

2 files changed, 199 insertions, 0 deletions

diff --git a/utils/merkletrie/internal/frame/frame.go b/utils/merkletrie/internal/frame/frame.go
new file mode 100644
index 0000000..fd06307
--- /dev/null
+++ b/utils/merkletrie/internal/frame/frame.go
@@ -0,0 +1,91 @@
+package frame
+
+import (
+	"bytes"
+	"fmt"
+	"sort"
+	"strings"
+
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+// A Frame is a collection of siblings in a trie, sorted alphabetically
+// by name.
+type Frame struct {
+	// siblings, sorted in reverse alphabetical order by name
+	stack []noder.Noder
+}
+
+type byName []noder.Noder
+
+func (a byName) Len() int      { return len(a) }
+func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a byName) Less(i, j int) bool {
+	return strings.Compare(a[i].Name(), a[j].Name()) < 0
+}
+
+// New returns a frame with the children of the provided node.
+func New(n noder.Noder) (*Frame, error) {
+	children, err := n.Children()
+	if err != nil {
+		return nil, err
+	}
+
+	sort.Sort(sort.Reverse(byName(children)))
+	return &Frame{
+		stack: children,
+	}, nil
+}
+
+// String returns the quoted names of the noders in the frame sorted in
+// alphabeticall order by name, surrounded by square brackets and
+// separated by comas.
+//
+// Examples:
+//     []
+//     ["a", "b"]
+func (f *Frame) String() string {
+	var buf bytes.Buffer
+	_ = buf.WriteByte('[')
+
+	sep := ""
+	for i := f.Len() - 1; i >= 0; i-- {
+		_, _ = buf.WriteString(sep)
+		sep = ", "
+		_, _ = buf.WriteString(fmt.Sprintf("%q", f.stack[i].Name()))
+	}
+
+	_ = buf.WriteByte(']')
+
+	return buf.String()
+}
+
+// First returns, but dont extract, the noder with the alphabetically
+// smaller name in the frame and true if the frame was not empy.
+// Otherwise it returns nil and false.
+func (f *Frame) First() (noder.Noder, bool) {
+	if f.Len() == 0 {
+		return nil, false
+	}
+
+	top := f.Len() - 1
+
+	return f.stack[top], true
+}
+
+// Drop extracts the noder with the alphabetically smaller name in the
+// frame or does nothing if the frame was empty.
+func (f *Frame) Drop() {
+	if f.Len() == 0 {
+		return
+	}
+
+	top := f.Len() - 1
+	f.stack[top] = nil
+	f.stack = f.stack[:top]
+}
+
+// Len returns the number of noders in the frame.
+func (f *Frame) Len() int {
+	return len(f.stack)
+}
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))
+}