1 files changed, 78 insertions, 0 deletions
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/raw_iter.go b/vendor/github.com/hashicorp/go-immutable-radix/raw_iter.go
new file mode 100644
index 000000000..04814c132
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/raw_iter.go
@@ -0,0 +1,78 @@
+package iradix
+
+// rawIterator visits each of the nodes in the tree, even the ones that are not
+// leaves. It keeps track of the effective path (what a leaf at a given node
+// would be called), which is useful for comparing trees.
+type rawIterator struct {
+	// node is the starting node in the tree for the iterator.
+	node *Node
+
+	// stack keeps track of edges in the frontier.
+	stack []rawStackEntry
+
+	// pos is the current position of the iterator.
+	pos *Node
+
+	// path is the effective path of the current iterator position,
+	// regardless of whether the current node is a leaf.
+	path string
+}
+
+// rawStackEntry is used to keep track of the cumulative common path as well as
+// its associated edges in the frontier.
+type rawStackEntry struct {
+	path  string
+	edges edges
+}
+
+// Front returns the current node that has been iterated to.
+func (i *rawIterator) Front() *Node {
+	return i.pos
+}
+
+// Path returns the effective path of the current node, even if it's not actually
+// a leaf.
+func (i *rawIterator) Path() string {
+	return i.path
+}
+
+// Next advances the iterator to the next node.
+func (i *rawIterator) Next() {
+	// Initialize our stack if needed.
+	if i.stack == nil && i.node != nil {
+		i.stack = []rawStackEntry{
+			rawStackEntry{
+				edges: edges{
+					edge{node: i.node},
+				},
+			},
+		}
+	}
+
+	for len(i.stack) > 0 {
+		// Inspect the last element of the stack.
+		n := len(i.stack)
+		last := i.stack[n-1]
+		elem := last.edges[0].node
+
+		// Update the stack.
+		if len(last.edges) > 1 {
+			i.stack[n-1].edges = last.edges[1:]
+		} else {
+			i.stack = i.stack[:n-1]
+		}
+
+		// Push the edges onto the frontier.
+		if len(elem.edges) > 0 {
+			path := last.path + string(elem.prefix)
+			i.stack = append(i.stack, rawStackEntry{path, elem.edges})
+		}
+
+		i.pos = elem
+		i.path = last.path + string(elem.prefix)
+		return
+	}
+
+	i.pos = nil
+	i.path = ""
+}