Traversing Hierarchies

traverse_children.ion

// Depth first traversal algorithm.
//
// (credit to Alexander Stepanov in Elements Of Programming)
//
// One of the benefits is that the visitor can implement pre or post traversal algorithms, and combine them in one single piece.
//
// @generic in T, the node value type
func traverse_children_recursively(tree_root: T*, step_visitor: func(step: TraversalStep, node: T*))
{
  step_visitor(TraversalStep_PRE, tree_root);
  last_child := children_last(tree_root);
  child := children_first(tree_root);
  while (child != last_child) {
    traverse_children_recursively(child, step_visitor);
    child = next_child(child);
  }
  step_visitor(TraversalStep_POST, tree_root);
}

enum TraversalStep
{
  TraversalStep_PRE,
  TraversalStep_POST,
}