#include <stdio.h>
/*

Only known misfeature:

./drawtree -t2 -nh -nv
  =-+-->d
  | | |
  | | c
  | |
  | a
  |
  []5
  |
  b

Need to take into account width of operator strings on leftchild

 */

static int debug = (0!=0);
static int vertical = (0==0);
static int horizontal = (0==0);
static int wide = (0!=0);
static int trim = (0==0);
static int testone = (0==0);

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

#define ast AST
#define op opd[0]
#define left opd[1]
#define right opd[2]
// static CELL ast[256];   // abstract syntax tree represented by a tree of
                        // cells

//       row  col
long pic[256][256]; // 0..255 is char, >= 256 is ptr to string

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

int oldtextblit(int row, int col, char *src)
{
  // post-processing string expansion
  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;
}

int textblit(int row, int col, char *src)
{
  // store pointer to string, unpack later on output
  int l = strlen(src);
  pic[row][col] = (int)src;
  return (l+(wide?3:1))>>(wide?2:1); // half size because on diagonal
}


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;

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

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

  // Anchor the corner node.
  (void)textblit(rowoff, coloff, operator); /* not strcpy - don't copy NUL */
  deltawidth = 1;
  if (rightchild >= 0) {
    int len = ((strlen(ast[leftchild].op)+(wide?3:1))>>(wide?2:1))+1; // text on the diagonal
    while (len-- > 1) {deltawidth += 1; pic[rowoff][coloff-1+deltawidth] = (vertical ? '\\' : '-');}
    // 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 */
  }
// testing: correcting a typo
  if (((strlen(operator)+(wide?3:1))>>(wide?2:1)) >= deltawidth) deltawidth = ((strlen(operator)+(wide?3:1))>>(wide?2:1))+2;

  if (leftchild >= 0) {
    // draw the down link

    // calculate extra height
    if ((((strlen(ast[leftchild].op)+(wide?3:1))>>(wide?2:1))) > deltadepth) {
      deltadepth = ((strlen(ast[leftchild].op)+(wide?3:1))>>(wide?2:1));
    }

    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] = (horizontal ? '/' : '|');
    }
    // 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);
}

int draw_tree(void)
{
  int depth = 0, width = 0, row, col, offset, trimmable;

  /* Generate layout */
  layout(1, 0/* index of root of code to be dumped */, 128, 0, &depth, &width);

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

  if (vertical) {
    /* apply vertical shear first */
    offset = 1;
    for (col = 1; col < 256; col++) {
      // move this column down by 'offset'
      for (row = 255; row > offset; row--) {
        pic[row][col] = pic[row-offset][col]; pic[row-offset][col] = ' ';
      }
      offset += 1;
    }
  }

  if (horizontal) {
    /* apply horizontal shear next */
    row = 255;  // start at bottom of drawing
    offset = 0;
    for (;;) {
      static long temp[1024];
      for (col = 0; col < 256; col++) {
        temp[col] = ' ';
      }
      for (col = 0; col < 256; col++) {
        temp[col*2+offset] = pic[row][col];
        temp[col*2+offset+1] = ' ';
      }
      for (col = 0; col < 256; col++) {
        pic[row][col] = temp[col];
      }
      if (row == 0) break;
      offset += 1; /* more shear on next row up */
      row -= 1;
    }
  }

  if (trim) {
    trimmable = (0==0);
    for (;;) {
      for (row = 0; row < 256; row++) {
        if (pic[row][0] != ' ') {
          trimmable = (0!=0);
          break;
        }
      }
      if (!trimmable) break;
      for (row = 0; row < 256; row++) {
        for (col = 0; col+1 < 256; col++) {
          pic[row][col] = pic[row][col+1];
        }
        pic[row][255] = ' ';
      }
    }
  }

  if (wide) {
    /* apply widening last */
    row = 255;  // start at bottom of drawing
    offset = 0;
    for (;;) {
      static long temp[1024];
      for (col = 0; col < 256; col++) {
        temp[col] = ' ';
      }
      for (col = 0; col < 256; col++) {
        temp[col*2+offset] = pic[row][col];
        temp[col*2+offset+1] = ' ';
      }
      for (col = 0; col < 256; col++) {
        pic[row][col] = temp[col];
      }
      if (row == 0) break;
      row -= 1;
    }
  }

  /* display tree */
  for (row = 0; row < 256; row++) {
    trimmable = (0 == 0);
    for (col = 0; col < 256; col++) {
      if (pic[row][col] != ' ') {
        trimmable = (0!=0);
        break;
      }
    }
    if (!trimmable) {
      fprintf(stdout, "  ");  // INDENT
      for (col = 255; col >= 0; col--) {
        if (pic[row][col] != ' ') break;
        pic[row][col] = '\0';
      }
      for (col = 0; col < 256; col++) {
        if ((pic[row][col] < -128) || (pic[row][col] > 255)) {
          oldtextblit(row, col, (char *)pic[row][col]);
        } else if (pic[row][col] == '\0') break;
        putchar(pic[row][col]);
      }
      putchar('\n');
    }
  }

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

Short test produces:

          =
         / \
        /   +
       /   / \
      /   /   ->
     /   /   / \
    []  a   c   d
   / \
  b   5

   */

  fflush(stdout);
  return;
}