aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/internal
diff options
context:
space:
mode:
authorAlberto Cortés <alcortesm@gmail.com>2017-02-06 17:40:38 +0100
committerGitHub <noreply@github.com>2017-02-06 17:40:38 +0100
commit41e5a1ff6f16ec13fa1cebe6e1d872bfe0951cee (patch)
tree6952a48ac8a6bb23c86f1568faca70614badfeaa /utils/merkletrie/internal
parent8d45daf52a46b8b2cd496c9e885a1ac6d78007e3 (diff)
downloadgo-git-41e5a1ff6f16ec13fa1cebe6e1d872bfe0951cee.tar.gz
add merkletrie iterator and its helper frame type (#252)
* add merkletrie iterator and its helper frame type * requested changes by mcuadros * reuqested changes: smola
Diffstat (limited to 'utils/merkletrie/internal')
-rw-r--r--utils/merkletrie/internal/frame/frame.go91
-rw-r--r--utils/merkletrie/internal/frame/frame_test.go108
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))
+}