From 8966c042795509ed17730e50d352ad69901c3da8 Mon Sep 17 00:00:00 2001
From: Alberto Cortés <alcortesm@gmail.com>
Date: Thu, 24 Nov 2016 15:29:22 +0100
Subject: mv difftree/internal/radixmerkle to difftre/internal/merkletrie
 (#138)

---
 difftree/internal/radixmerkle/iter.go | 167 ----------------------------------
 1 file changed, 167 deletions(-)
 delete mode 100644 difftree/internal/radixmerkle/iter.go

(limited to 'difftree/internal/radixmerkle/iter.go')

diff --git a/difftree/internal/radixmerkle/iter.go b/difftree/internal/radixmerkle/iter.go
deleted file mode 100644
index e175966..0000000
--- a/difftree/internal/radixmerkle/iter.go
+++ /dev/null
@@ -1,167 +0,0 @@
-package merkletrie
-
-// Iter is a radix tree iterator that will traverse the trie in
-// depth-first pre-order.  Entries are traversed in (case-sensitive)
-// alphabetical order for each level.
-//
-// This is the kind of traversal you will expect when listing
-// ordinary files and directories recursively, for example:
-//
-//             Trie           Traversal order
-//             ----           ---------------
-//              .
-//            / | \           a
-//           /  |  \          b
-//          b   a   z   ===>  b/a
-//         / \                b/c
-//        c   a               z
-//
-//
-// The Step method will return the next item, the Next method will do
-// the same but without descending deeper into the tree (i.e. skipping
-// the contents of "directories").
-//
-// The name of the type and its methods are based on the well known "next"
-// and "step" operations, quite common in debuggers, like gdb.
-type Iter struct {
-	// tells if the iteration has started.
-	hasStarted bool
-	// Each level of the tree is represented as a frame, this stack
-	// keeps track of the frames wrapping the current iterator position.
-	// The iterator will "step" into a node by adding its frame to the
-	// stack, or go to the next element at the same level by poping the
-	// current frame.
-	frameStack []*frame
-}
-
-// NewIter returns a new iterator for the trie with its root at n.
-func NewIter(n Noder) *Iter {
-	ret := &Iter{}
-	ret.push(newFrame("", n))
-
-	return ret
-}
-
-func (iter *Iter) top() (*frame, bool) {
-	if len(iter.frameStack) == 0 {
-		return nil, false
-	}
-
-	top := len(iter.frameStack) - 1
-
-	return iter.frameStack[top], true
-}
-
-func (iter *Iter) pop() (*frame, bool) {
-	if len(iter.frameStack) == 0 {
-		return nil, false
-	}
-
-	top := len(iter.frameStack) - 1
-	ret := iter.frameStack[top]
-	iter.frameStack[top] = nil
-	iter.frameStack = iter.frameStack[:top]
-
-	return ret, true
-}
-
-func (iter *Iter) push(f *frame) {
-	iter.frameStack = append(iter.frameStack, f)
-}
-
-const (
-	descend     = true
-	dontDescend = false
-)
-
-// Next returns the next node without descending deeper into the tree
-// and true.  If there are no more entries it returns nil and false.
-func (iter *Iter) Next() (Noder, bool) {
-	return iter.advance(dontDescend)
-}
-
-// Step returns the next node in the tree, descending deeper into it if
-// needed. If there are no more nodes in the tree, it returns nil and
-// false.
-func (iter *Iter) Step() (Noder, bool) {
-	return iter.advance(descend)
-}
-
-// advances the iterator in whatever direction you want: descend or
-// dontDescend.
-func (iter *Iter) advance(mustDescend bool) (Noder, bool) {
-	node, ok := iter.current()
-	if !ok {
-		return nil, false
-	}
-
-	// The first time we just return the current node.
-	if !iter.hasStarted {
-		iter.hasStarted = true
-		return node, ok
-	}
-	// following advances will involve dropping already seen nodes
-	// or getting into their children
-
-	ignoreChildren := node.NumChildren() == 0 || !mustDescend
-	if ignoreChildren {
-		// if we must ignore the current node children, just drop
-		// it and find the next one in the existing frames.
-		_ = iter.drop()
-		node, ok = iter.current()
-		return node, ok
-	}
-
-	// if we must descend into the current's node children, drop the
-	// parent and add a new frame with its children.
-	_ = iter.drop()
-	iter.push(newFrame(node.Key(), node))
-	node, _ = iter.current()
-
-	return node, true
-}
-
-// returns the current frame and the current node (i.e. the ones at the
-// top of their respective stacks.
-func (iter *Iter) current() (Noder, bool) {
-	f, ok := iter.top()
-	if !ok {
-		return nil, false
-	}
-
-	n, ok := f.top()
-	if !ok {
-		return nil, false
-	}
-
-	return n, true
-}
-
-// removes the current node and all the frames that become empty as a
-// consecuence of this action. It returns true if something was dropped,
-// and false if there were no more nodes in the iterator.
-func (iter *Iter) drop() bool {
-	frame, ok := iter.top()
-	if !ok {
-		return false
-	}
-
-	_, ok = frame.pop()
-	if !ok {
-		return false
-	}
-
-	for { // remove empty frames
-		if len(frame.stack) != 0 {
-			break
-		}
-
-		_, _ = iter.pop()
-		frame, ok = iter.top()
-		if !ok {
-			break
-		}
-	}
-
-	return true
-}
-- 
cgit