C[omp]ute

From: "andrew cooke" <andrew@...>

Date: Mon, 25 Aug 2008 15:30:09 -0400 (CLT)

I just had to convert a stream (list) of values to a tree.  Each list item
had a "depth" that could be one more than the previous value (a child),
the same (a sibling) or a smaller value (some ancestor).

This seems trivial, I know, but it took me some thinking.  On the other
hand the final code is quite simple (and uses an accumulator to keep
sibling order), so here it is for future reference.  Note that some slight
oddities are necessary because of Python's strange list (more like arrays)
data type.

    def build_tree(lines, level=0, acc=[]):
        while lines and lines[0][0] == level:
            (depth, key, text, description) = lines[0]
            (lines, children) = build_tree(lines[1:], level+1, [])
            acc.append([key, text, description, children])
        return (lines, acc)

The each entry in the list has the structure (depth, key, text,
description) where depth is as described earlier.  So the lines[0][0] is a
peek into the next depth.  And the resulting tree nodes have the form
(key, text, description, children).  There's nothing special about key,
text and description - that's just the particulars of the data I was
working with.

It's quite succinct, IMHO.  I assume that it's some kind of banana
(catamorphism) or related gubbins that I can no longer remember and never
completely understood anyway...

Andrew