[Vala] General tree walking question

[Donn Ingle <donn ingle gmail com>]

Hi,
Apologies if this is OT. I am trying to do this in Vala.

This is a general tree walking question. I'm a bit thick and trees
really kill my brain. Here's the situation:

I have a "Thing" class that contains an ArrayList of (potentially)
many other Things. This all results in a tree where Things can have
many children and siblings.

I want to walk through this tree (from the root node) and create a
list that represents the tree.

Example tree:
ROOT has children A1, A2
A1 has children B1, B2
A2 has children C1, C2

Walk result in a stack:
ROOT (starts)
A1 (starts)
B1 (starts)
B1 (ends)
B2 (starts)
B2 (ends)
A1 (ends)
A2 (starts)
C1 (starts)
C1 (ends)
C2 (starts)
C2 (ends)
A2 (ends)
ROOT (ends)

I need those start/end markers and the whole stack kind of looks like
a flattened tree. You can imagine it with tabs showing the structure.

Questions:
Should one do this kind of thing with recursion, or is making lists
and iterating better?
(I worry that recursion might hit stack limits because my tree could
get quite large.)

I have been trying an iterative solution, but it's not really working
and I'm stuck. Code below.
Any suggestions?

Thanks,
\d

--
/*
Compile with:
valac --pkg gee-1.0 -X -lm -X -w $SRCNAME -o test
*/

using Gee;

public class Thing : Object {
  public string id;
  public ArrayList<weak Thing> w_children;

  public Thing(string id) {
    this.id = id;
    this.w_children = new ArrayList<weak Thing>();
  }
}


public ArrayList<weak Thing> walk( Thing o ) {
  var nodes = new ArrayList<weak Thing>();
  nodes.add(o);

  Thing lastnode = null;

  //This list is going to be returned.
  var results = new ArrayList<weak Thing>();

  ArrayList<weak Thing> newnodes;

  while (true) {
    //Make a NEW newnodes list: equiv of Python newnodes=[]
    newnodes = new ArrayList<weak Thing>();

    if (nodes.size == 0) break;

    foreach ( weak Thing node in nodes) { //siblings

      stdout.printf( "Pushing sibling node %s to results.\n", node.id);
      results.add(node);

      if (node.w_children.size >0) {
        foreach( weak Thing child in node.w_children ){ //children
          newnodes.add(child);
          stdout.printf("Visiting child %s of node:%s\n",child.id, node.id);
        }
      } else {
        stdout.printf("No kids for %s\n",node.id);
        //Trying to keep a record of where we came from.
        lastnode = node;
        stdout.printf( "lastnode set to:%s\n", lastnode.id);
      } //Children

    stdout.printf("CLOSE %s NOW.\n", node.id); //Not the right solution...
    } //siblings

    stdout.printf( "About to swap nodes and newnodes. Newnodes is:\n");
    foreach (weak Thing nn in newnodes) stdout.printf("%s,",nn.id);
    stdout.printf("\n\n");
    nodes = newnodes;
  }
  stdout.printf("inside func walk:\n");
  foreach( weak Thing n in results )
    stdout.printf( "Thing ID %s. Thing rc:%u\n", n.id, n.ref_count );
  return results;
}

int main() {
  var bag = new ArrayList<Thing>(); //bag will be main owner of Thing instances.
  {
  var o1 = new Thing("ROOT");
  var o2 = new Thing("A1");
  var o3 = new Thing("A2");
  var o4 = new Thing("B1");
  var o5 = new Thing("B2");
  var o6 = new Thing("C1");
  var o7 = new Thing("C2");

  bag.add(o1); //0 ROOT
  bag.add(o2); //1 A1
  bag.add(o3); //2 A2
  bag.add(o4); //3 B1
  bag.add(o5); //4 B2
  bag.add(o6); //5 C1
  bag.add(o7); //6 C2
  }

  //Assign some children to nodes
  bag[0].w_children.add( bag[1] ); //root -> A1 + A2
  bag[0].w_children.add( bag[2] );
  bag[1].w_children.add( bag[3] ); //A1 -> B1
  bag[1].w_children.add( bag[4] ); //A1 -> B2
  bag[2].w_children.add( bag[5] ); //A2 -> C1
  bag[2].w_children.add( bag[6] ); //A2 -> C2

  var results = walk( bag[0] );

  return 0;
}


--