That sounds like a bug/limitation in @sschwarzer's algorithm to me, but maybe
he can verify. Good catch, @e.
Another pretty different approach that I use in `cligen/tern.nim` (that does
not support in-iteration deletion) is something like this:
const NUL* = '\0'
type
NodeOb*[T] {.acyclic.} = object
ch*: char
cnt*: int
when T isnot void: val*: T
kid*: array[3, ref NodeOb[T]] #0,1,2 ~ <,=,>
Node*[T] = ref NodeOb[T]
Tern*[T] = object ## A Tern can be used as either a mapping from strings
root*: Node[T] ## to type ``T`` or as a set(strings) if ``T`` is
void.
count: int ## Number of elements
depth: int ## Depth of Tree
iterator leaves[T](r: Node[T], depth:int, pfx=""): tuple[k:string,
n:Node[T]] =
type #Nim iterators should
grow
Which = enum st0, st1, st2, stR #..recursion
capability so
State = tuple[st: Which, k: string, n: Node[T]] #..this headache can
be as
if r != nil: #..easy as `print`.
var stack = newSeqOfCap[State](depth)
stack.add (st: st0, k: pfx, n: r)
while stack.len > 0:
let state = stack[^1].addr
if state.n == nil: break
case state.st
of st0:
state.st = st1
if state.n.kid[0] != nil:
stack.add (st: st0, k: state.k, n: state.n.kid[0])
of st1:
state.st = st2
if state.n.ch == NUL:
yield (k: state.k, n: state.n)
elif state.n.kid[1] != nil:
stack.add (st: st0, k: state.k & $state.n.ch, n: state.n.kid[1])
of st2:
state.st = stR
if state.n.kid[2] != nil:
stack.add (st: st0, k: state.k, n: state.n.kid[2])
of stR: discard stack.pop
Run
The above is probably pretty close to what compilers generate for recursive
function calls. Of course, as mentioned I think things like this are more
elegant/easy to understand:
proc print*[T](p: Node[T], depth=0) = #2,1,0 gives std emoji-orientation
if p == nil: return #..i.e. ":-)" head-tilt not "(-:".
print(p.kid[2], depth + 1)
echo strutils.repeat(" ", depth), cast[int](p), " ch: ", p.ch.repr, "
cnt: ", p.cnt
print(p.kid[1], depth + 1)
print(p.kid[0], depth + 1)
Run
For `cligen/trie.nim` since I was already using a super wasteful uncompressed
trie, I just punted on all that and spent memory proportional to the answer,
i.e.:
proc collect*[T](n: Node[T], key: var string, d=0, pfx="", i=0):
seq[tuple[k: string, n: Node[T]]] =
if n == nil:
return
if n.term:
result.add (k: (if i > 0: pfx[0..<i] & key else: key), n: n)
for h, ch in n.kidc:
key.setLen d + 1
key[d] = ch
result.add collect(n.kidp[h], key, d + 1, pfx, i)
proc leaves[T](r: Node[T], depth=99, pfx="", i=0, d=0):
seq[tuple[k: string, n: Node[T]]] =
var key = "" #Would be nicer to do iterator w/state
bounded
collect(r, key, d, pfx, i) #..by depth, but seemed tricky &
unimportant.
Run
It sounds like @JohnAD might find the trie variant of `leaves` an interesting
challenge to do The Right Way. PRs welcome. ;-)
