/*
 * Prints out a tree structure for use in a future TreeBall game.
 *
 * Author:  Zach Tomaszewski 
 * Created: 16 Feb 2012
 * Version: 17 Apr 2012
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


// HEADER details

/* The number of levels in new trees.  Includes the root node as level 1. */
#define TREE_LEVELS 4

/* The data value for an empty tree node. */
#define EMPTY '*'

/* The character to represent destroyed nodes in the tree. */
#define DESTROYED 'X'

/*
 * A single node at the root of a Tree.  The complete structure will
 * actually be stored as an array of these elements.
 */
typedef char Tree;


//function declarations.
Tree* newTree(void);
void printTree(Tree *root, int depth);


// FUNCTION definitions

/*
 * Returns a new empty binary Tree of TREE_LEVELS depth.
 *
 * Depth is 1-based.  That is, 1 returns a single root node; 2 returns a
 * root node and two children nodes; etc. The binary tree is stored in a
 * Tree[], where each the children of node i can be found at (2i + 1) and
 * (2i + 2).
 *
 * Returns the dynamically constructed array.
 */
Tree* newTree(void) {
  int nodes = pow(2, TREE_LEVELS) - 1;
  Tree* root = malloc(nodes);
  //initialize all nodes to special EMPTY value
  memset(root, EMPTY, nodes);
  return root;
}


/*
 * Prints to stdout the given number of levels of the given tree.
 *
 * Assumes a perfect tree that is completely full of nodes.  In other words,
 * all of tree's leaves must be at the same level.
 *
 * A printed tree looks something like this, where each # is a node's contents:
 *
 *         #
 *        / \
 *       /   \
 *      /     \
 *     /       \
 *     #       #
 *    / \     / \
 *   /   \   /   \
 *   #   #   #   #
 *  / \ / \ / \ / \
 *  # # # # # # # #
 *
 * Note that the distance between the levels grows geometrically.
 *
 */
void printTree(Tree *root, int levels) {
  int lvl;

  //print tree from root down
  for (lvl = 1; lvl <= levels; lvl++) {
    int n, nodes;

    //calculate indent spacing for this level, which depends on full tree size
    // (example: lvl 2 of 4-level tree -> 7 spaces between any two nodes)
    int indent = pow(2, levels - lvl + 1) - 1;
    int halfIndent = indent / 2;

    putchar(' '); //extra left margin padding on start of each level

    //print each node on this level
    nodes = pow(2, lvl - 1);
    for (n = 0; n < nodes; n++) {
      int s;
      //print indent before each node (with only halfIndent before first node)
      for (s = 0; s < ((n == 0) ? halfIndent : indent); s++) {
        putchar(' ');
      }
      //print node itself
      putchar(*root);
      root++;
    }
    putchar('\n');  //end lvl line

    //now print the lines that contain connectors to the next level below
    if (lvl < levels) {
      //not on last level of tree yet yet, so...
      int lines = pow(2, levels - lvl - 1);
      int line;

      //print the lines of connectors
      for (line = 1; line <= lines; line++) {
        int spaces = halfIndent - line;  // spaces before / and after \.

        putchar(' ');  //left margin padding

        for (n = 0; n < nodes; n++) {
          int c;
          for (c = 0; c < spaces; c++) {  //spaces before the /
            putchar(' ');
          }
          putchar('/');
          for (c = 0; c < line * 2 - 1; c++) { //under node, between lines
            putchar(' ');
          }
          putchar('\\');
          for (c = 0; c < spaces; c++) {  //after the \ to next mid-node point
            putchar(' ');
          }
          putchar(' '); //midpoint space
        }
        putchar('\n');
      }
    }
  }
}

  
/*
 * Prints a sample tree to the screen for testing purposes.
 */
int main() {
  Tree* tree = newTree();
  //fill in a couple points in the tree for testing purposes
  tree[0] = 't';  
  tree[1] = 'l';
  tree[2] = 'r';
  printTree(tree, TREE_LEVELS);
  free(tree);
}