#include <stdio.h>
#include <stdlib.h>
static int debug = (0==0);

typedef struct
{
    char *op;           // '+', '-', '*', '/', etc., or terminal.
    int left;           // -1 means no child
    int right;          // ditto
} CELL;

static CELL ast[256];   // abstract syntax tree represented by a tree of
                        // cells

//       row  col
char pic[256][256];

void mknode(int nodeno, char *op, int left, int right)
{
  ast[nodeno].op = op;
  ast[nodeno].left = left;
  ast[nodeno].right = right;
}

int textblit(int row, int col, char *src)
{
  // relies on [row][col] layout.  I.e. not [x][y]!
  int l = 0;
  for (;;) {
    if (*src == '\0') break;
    if (debug) fprintf(stderr, "1: Planting '%c' at [%d][%d]\n", *src, row, col);
    pic[row][col++] = *src++;
    l += 1;
  }
  return l;
}

void layout(int id, int idx, int rowoff, int coloff, int *depth, int *width)
{
  char *operator;
  int leftchild, rightchild;
  int leftchilddepth = 0, leftchildwidth = 0;
  int rightchilddepth = 0, rightchildwidth = 0;
  int deltadepth = 0, deltawidth = 0;
  int i;

/*

Our simple trivial-case terminal example:

   + -- jim
   |
   fred

deltawidth = 5 ("+ -- ")
deltaheight = 2 ("+, |") (spacer below rightchild)

rightchildwidth = 3
rightchilddepth = 1

leftchildwidth = 4 ("fred")
leftchilddepth = 1

width = 8
depth = 3

*/

  if (debug) fprintf(stderr, ">> %d:layout(%d, rowcol[%d][%d], depth %d, width %d);\n", id, idx, rowoff, coloff, *depth, *width);

  //  Next hack might look like this...
  //
  //            =
  //           /  \
  //          *    .
  //        /     /  \
  //      []     x    y
  //     /  \
  //    2   []
  //       /
  //      3

  //  TODO: implement a 'cuddle-up' procedure in both X and Y
  //  to minimise space used
  //
  //   = -- . -- y
  //   |    |
  //   *    x
  //   |
  //   [] - []
  //   |    |
  //   2    3
  //

  operator = ast[idx].op;
  leftchild = ast[idx].left;
  rightchild = ast[idx].right;

  // Anchor the corner node.
  deltawidth += textblit(rowoff, coloff, operator); /* not strcpy - don't copy NUL */

  if (rightchild >= 0) {
    deltawidth += textblit(rowoff, coloff+strlen(operator), " -- "); /* not strcpy - don't copy NUL */
    // attach the RHS tree
    if (debug) fprintf(stderr, "Recursing to right node %d\n", rightchild);
    layout(2*id, rightchild, rowoff, coloff+deltawidth, &rightchilddepth, &rightchildwidth);
    deltadepth = rightchilddepth;
  } else deltadepth = 1; /* The op itself */

  if (leftchild >= 0) {
    // draw the down link
    for (i = 1; i < deltadepth+1 /* +1 for spacer row */; i++) {
      if (debug) fprintf(stderr, "2: Planting '%c' at [%d][%d]\n", '|', rowoff+i, coloff);
      pic[rowoff+i][coloff] = '|';
    }
    // recurse on the LHS tree
    if (debug) fprintf(stderr, "Recursing to left node %d\n", leftchild);
    layout(2*id+1, leftchild, rowoff+deltadepth+1, coloff, &leftchilddepth, &leftchildwidth);
    *depth = (*depth) + leftchilddepth + deltadepth + 1;
  } else *depth = (*depth) + deltadepth;

  if (rightchildwidth+deltawidth > leftchildwidth) {
    *width = (rightchildwidth+deltawidth);
  } else {
    *width = leftchildwidth;
  }

  if (debug) fprintf(stderr, "<< %d:layout(%d, rowcol[%d][%d], depth %d, width %d);\n", id, idx, rowoff, coloff, *depth, *width);
#undef image
}

int main(int argc, char **argv)
{
  int depth = 0, width = 0, row, col;

  // Init.
  for (col = 0; col < 256; col++) {
    for (row = 0; row < 256; row++) {
      pic[row][col] = ' ';
    }
  }

  /* build example tree - this will actually be done by a parser */
  mknode(1, "[]", 5, 6);
  mknode(0, "=", 1, 2);
  mknode(2, "+", 3, 4);
  mknode(3, "longvarname", -1, -1);
  mknode(4, "->", 7, 8);
  mknode(5, "arrayname", -1, -1);
  mknode(6, "5", -1, -1);
  mknode(7, "structname", -1, -1);
  mknode(8, "fieldname", -1, -1);

  /* Generate layout */
  layout(1, 0, 0, 0, &depth, &width);

  if (debug) fprintf(stderr, "Dump layout: rows = %d cols = %d\n", depth, width);
  if (debug) fflush(stderr);

  fprintf(stdout, "arrayname[5] = longvarname + structname->fieldname;\n\n");
  /* display tree */
  for (row = 0; row <= depth; row++) {
    for (col = 0; col <= width; col++) {
      putchar(pic[row][col]);
    }
    putchar('\n');
  }

  /*  Output from the above is:
     arrayname[5] = longvarname + structname->fieldname;

     = -- + -- -> -- fieldname
     |    |    |
     |    |    structname
     |    |
     |    longvarname
     |
     [] -- 5
     |
     arrayname

     TODO: alternative with 'cuddle-up' and horizontal stretch:

     = ----- + ----- -> -- fieldname
     |       |       |
     [] -- 5 varname structname
     |
     longarrayname

   */

  fflush(stdout);
  exit(0);
  return 0;
}