/* mp4.c -- a C solution to the H-tree problem */

/*
 * This code is written in order to get the logic of plotting H-trees right before
 * trying to do it in assembly language.  It plots into a 2-dimensional array and
 * then outputs that array after filling it with very close to the largest H-tree
 * that will fit in the array.
 *
 * It is much easier to debug the logic of plotting H-trees in a high level language
 * than to try to debug the code in assembly language!
 *
 * This program is not the simplest possible program to do this because the
 * assignment explicitly said that the calling sequence was haich(x,y,n)
 * where n is the order.  A simpler formulation would have haich(x,y,n,w,h)
 * where w and h are the width and height of the tree, respectively.
 */

#include <stdio.h>

/* the dimensions of the "screen" */
#define width 62
#define height 31

/* the working area we will plot on and then output when done */
char blackboard[width][height];

/****************************************
 * The actual code for plotting H-trees *
 ****************************************/

/* we need this because C requires definition before use */
void oddh( int x, int y, int o, int w, int h );
	/* in all of the following,
         *     x = x coordinate of the tree center
         *     y = y coordinate of the tree center
         *     o = order of the tree
         *     w = width of the tree, in characters
         *     h = height of the tree, in characters
         */

void evenh( int x, int y, int o, int w, int h ) {
        /* plot an even order H */
	if (o > 0) { /* side by side case */
		int neww = (w - 3)/2;
		int offset = (neww + 3)/2;
		int i;
		oddh( x - offset, y, o - 1, neww, h );
		oddh( x + offset, y, o - 1, neww, h );
		for (i = (x - offset) + 1; i < (x + offset); i++) {
			blackboard[i][y] = '_';
		}
	}
}

void oddh( int x, int y, int o, int w, int h ) {
        /* plot an odd order H */
	if (o > 0) { /* top to bottom case */
		int newh = (h - 2)/2;
		int offset = (newh + 2)/2;
		int i;
		evenh( x, y - offset, o - 1, w, newh );
		evenh( x, y + offset, o - 1, w, newh );
		for (i = (y - offset) + 1; i < (y + offset) + 1; i++) {
			blackboard[x][i] = '|';
		}
	}
}

/**************************
 * The required interface *
 **************************/

void haich( int x, int y, int o ) {
        /* compute what size H-tree and call either the even or odd case */
	if (o > 0) {
		int w = 1;
		int h = 0;
		int i;
		for (i = o; i > 0; i--) {
			if (i & 1) { /* i is odd */
				h = 2*h + 2;
			} else { /* i is even */
				w = 2*w + 3;
			}
		}

		if (o & 1) { /* o is odd */
			oddh( x, y, o, w, h );
		} else { /* o is even */
			evenh( x, y, o, w, h );
		}
	}
}

/****************
 * Main program *
 ****************/

main() {
        /* erase the blackboard, then
         * figure out what size H-tree to display, then
         * draw the H-tree centered on the blackboard, then
	 * output the blackboard to the screen
         */
           
	int x,y,o;

	/* erase the blackboard */
	for (y = 0; y < height; y++) {
		for (x = 0; x < width; x++) {
			blackboard[x][y] = ' ';
		}
	}

	/* figure out what size h-tree to display */
	x = 1;
	y = 0;
	o = 0;
	for (;;) {
		if (o & 1) { /* if o-1 is odd */
			x = 2*x + 3;
		} else { /* if o-1 is even */
			y = 2*y + 2;
		}
		if ((x >= width) || (y >= height)) break;
		o = o + 1;
	}

	/* draw the h-tree centered on the blackboard */
	haich( width/2, height/2, o );

	/* output the blackboard to the screen */
	for (y = 0; y < height; y++) {
		for (x = 0; x < width; x++) {
			putchar( blackboard[x][y] );
		}
		putchar( '\n' );
	}
}