| 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 = "" |
| } |