/* Stackless tree-traversal with R-technology */

/* This is the translation of the Algol-68 code from ca. 1987,
   to make it more understandable and approachable.
   It is worth comparing with the original Algol-68,
   files bldg.bld and dumptree.a68 in this directory.

   The original traversal code was part of a large 
   (train scheduling) program. The tree it operated upon represented
   train schedules. Therefore, tree nodes had a number of fields
   related to scheduling. We replace all this payload with 
   the simple integer: our goal here is just to show off the traversal.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


/* Linked tree data structure */
/* It is like a simple linked list, but with two extra pointers,
   for the parent and the first-born--child nodes.
*/

typedef struct _node node;      /* forward declaration */

struct _node {
  node * up;                    /* parent pointer */
  node * down;                  /* first-born child */
  node * right;                 /* brother */
  int data;                     /* payload: just an int in our example */
};

const node * const nil = (node *)NULL;

node * new_node(const int x){
  node * n = (node *)calloc(1,sizeof(node));
  n->data = x;
  return n;
}

/* Traverse the tree depth-first and print out the payload of
   the traversed nodes: tree dump
   The following function mirrors the Algol68 code in dumptree.a68
*/
void dump(const node * const tree) {
  const node * n = tree;        /* current node */
  enum {finish,down,right_up} state = down;

  /* The R-machine execution, with two states */
  while(state != finish)
    switch(state) {
    case down:
      if(n->down == nil) {printf("data %d----- leaf\n",n->data);
                                                            state = right_up;}
      else               {printf("data %d\n",n->data); n = n->down;
                                                            state = down;}
      break;

    case right_up:
      if      (n->right != nil) {n = n->right; state=down;}
      else if (n->up == nil)    {n = nil;      state=finish;}
      else                      {n = n->up;    state=right_up;}
      break;

    case finish: break;
    }
}

/* The following function builds a sample tree. It was not a
   part of the original Algol-68 code. In the original, all nodes
   were first pre-allocated and put on the free list, from which
   they were taken as needed, and returned to by a special GC.
*/

/* Build a sample tree: full binary tree at the given depth (positive). 
   The data field of each node is the sequential count.
*/

node * sample_tree(const int depth) {
  int count = 0;
  node * n;
  int level;
  enum {finish, down_left, down_right, up} state = down_left;

  assert(depth>0);
  n = new_node(count++);
  level = 1;

  while(state != finish)
    switch(state) {
    case down_left:
      if(level >= depth) { state = up; }
      else {
        node * nnew = new_node(count++);
        nnew->up = n;
        n->down = nnew;
        n = nnew;
        level++;
        state = down_left;}
      break;

    case up:
      if (n->up == nil) { state = finish; }
      else              {n = n->up; level--; state = down_right;}
      break;

    case down_right:
      assert(n->down != nil);
      if(n->down->right == nil) { 
        node * left_brother = n->down;
        node * nnew = new_node(count++);
        nnew->up = n;
        left_brother->right = nnew;
        n = nnew;
        level++;
        state = down_left;}
      else { state = up; }
      break;

    case finish: break;
    }
 
  return n;
}

int main(void){
  const node * tree;
  printf("Example of R-technology: tree traversal\n");
  tree = sample_tree(4);
  printf("Constructed a sample tree\n");
  printf("Traversing the tree and printing out its nodes, with R-tran\n");
  dump(tree);
  printf("\nDone\n");
  return 0;
}