// FILE: 99ab4.cpp 
// PURPOSE: 1999 AP AB Exam: Question 4 (Binary trees)
//---------------------------------------------------------------------
// COMPILATION INSTRUCTIONS: g++ and gxx 
// 1. FILES: No special files needed. Using C++ string instead of apstring
// 2. COMMAND LINE: g++ (or gxx) -Wall 99ab4.cpp
//---------------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// 1. Print out 1999 AB Exam  Question 4 and implement solutions as specified
// 2. After implementing solutions on paper, enter them below and run program
//    to verfify them
//---------------------------------------------------------------------
#include <iostream.h>
#include <iomanip.h>
#include <string>
#include <math.h>
#include <stdlib.h>

struct TreeNode {
  char name;
  TreeNode * left;
  TreeNode * right;
  TreeNode(int val, TreeNode * lchild = 0, TreeNode * rchild = 0)
    : name(val), left(lchild), right(rchild) { }
};
    
int Max(int x, int y);
    
int PathLength(TreeNode *T, char someChar, int level)  {
      return -77;                
}


int RootPath(TreeNode *T)  {      
  return -77;
}

void PathLengthTest(void);
void RootPathTest(void);
void buildTreeNode1(TreeNode *&);
void buildTreeNode2(TreeNode *&);
void nodeMat(char);
void clearMat(void);
void markXY(TreeNode *T1, int x, int level);
void printTree(TreeNode *);
void cls(void);
void pause(void);

int main() {
   cls();
   string title("1999 AB Exam: Question 4");
   cout << setw(39 + title.length()/2) << title.c_str() << "\n\n"; 
   PathLengthTest();
   RootPathTest();
  
   return 0;
} // main  ***************************************

int Max(int x, int y) {
   return (x >= y ? x : y);
}

const int initX = 39;
const int ROWS(12), COLS(78);                 
string treeMat[ROWS];

void PathLengthTest(void) {
   TreeNode *T;
   buildTreeNode1(T);
   clearMat(); markXY(T, initX, 1);
   printTree(T);
   cout << "Testing PathLength:\n";  
   cout << "PathLength(T, 'S', 1) = " << PathLength(T, 'S', 1) << endl;
   cout << "PathLength(T, 'K', 1) = " << PathLength(T, 'K', 1) << endl; 
   cout << "PathLength(T, 'C', 1) = " << PathLength(T, 'C', 1) << endl;
   cout << "PathLength(T, 'Q', 1) = " << PathLength(T, 'Q', 1) << endl; 
   cout << "PathLength(T->left, 'S', 1) = " << PathLength(T->left, 'T', 1) << endl;
   cout << "PathLength(T->right->left, 'D', 1) = " 
        << PathLength(T->right->left, 'D', 1) << endl;    
   pause();
}

void RootPathTest(void) {
   TreeNode *T;
   buildTreeNode1(T);
   clearMat(); markXY(T, initX, 1);
   cls(); printTree(T);
   cout << "Testing RootPath:\n";  
   cout << "RootPath(T)= " << RootPath(T) << endl;
   cout << "RootPath(T->left)= " << RootPath(T->left) << endl;
   cout << "RootPath(T->right)= " << RootPath(T->right) << endl;   
   cout << "RootPath(T->left->left->left)= " << RootPath(T->left->left->left) << endl;   
   pause();
}

//*****************************************************
//   tree build and print routines
//*****************************************************

void clearMat(void) {
  for (int r = 0; r < ROWS; r++)
     treeMat[r] = string(COLS, ' ');
}

void markXY(TreeNode *T1, int x, int level) {
  int dx = int(initX / floor(exp(level * log(2))));
  int newY = 2 * level - 1;
  string arcString;
  if ( dx > 1 )
     arcString = "+" + string(dx-1, '-') + "+";
  else  
     arcString = string(dx+1, '+');
  if (T1->left !=  NULL) {
    markXY(T1->left, x - dx, level + 1);
    treeMat[newY+1].replace(x - dx, dx + 1, arcString); 
  }
  if ( x >= 0 && x < COLS && newY >= 0 && newY < ROWS)
    treeMat[newY][x] = T1->name;
  if (T1->right !=  NULL) {
    markXY(T1->right, x + dx, level + 1);
    treeMat[newY+1].replace(x, dx+1, arcString);     
  }
}//*** markXY

void printTree(TreeNode *T) {
  const string title(" T");
  cout << setw(initX + title.length()/2) << title.c_str() << endl;
  if ( T == NULL )
    cout << "\n\nTree is empty...";
  else {
    treeMat[0][initX] = '|';
    for (int r = 0; r < ROWS; r++) {
       cout << treeMat[r] << endl;
    } // for
  } // else
}//*** printTree


void nodeMat(char dir) {
   if ( dir == 'R' ) {   
     int rightPos = treeMat[3].find('1') + 1; 
     treeMat[3].replace(rightPos, 5, " <--P");    
   }
   else { // dir == 'L'
     int leftPos = treeMat[3].find('4') - 5; 
     treeMat[3].replace(leftPos, 5, "P--> ");    
   }
}

void buildTreeNode1(TreeNode *&root) {
  root = new TreeNode('S',
            new TreeNode('T', 
               new TreeNode('F', NULL, NULL), 
               new TreeNode('S', new TreeNode('G', NULL, NULL), NULL)),
            new TreeNode('C', 
               new TreeNode('D', 
                   new TreeNode('S', new TreeNode('D', NULL, NULL), NULL), 
                   new TreeNode('F',
                       new TreeNode('M', NULL, NULL), 
                       new TreeNode('T', NULL, new TreeNode('C', NULL, NULL)))), 
               new TreeNode('K', NULL, NULL)
            )); 
}//*** buildTreeNode1

void cls(void) {
  for (int k = 0; k < 55; k++)
    cout << endl;
}

void pause(void) {
   cout << "\nPress <ENTER> to continue..."; 
   cin.ignore(10, '\n'); 
}