// FILE: 97ab3.cpp  
// PURPOSE: 1997 AP AB Exam: Question 3 (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 97ab3.cpp
//---------------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// 1. Print out 1997 AB Exam  Question 3 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 Tree {
  char info;
  Tree * left;
  Tree * right;
  // provide constructor
  Tree(int val, Tree * lchild = 0, Tree * rchild = 0)
    : info(val), left(lchild), right(rchild) { }
};
    
    
int CountNum(Tree * T, char key)  {
// precondition: returns the number of nodes in Tree T  with the value key.  
//     Returns 0 if no nodes contain key or if the tree is empty   

  return -77;
}


void Insert(Tree * p, char key, char direction) {
// precondition: P is not NULL/0.  If direction is 'R', P has a right child; 
//               if direction is 'L', P has a left child.
// postcondition: If direction is 'R', a node containing the value key is 
//   created and inserted between P and P's right child. If direction is 'L', 
//   a node containing the value key is created and inserted between P and
//   P's left child.

  
}


void Separate(Tree * T) {

  
}

void CountNumTest(void);
void InsertTest(void);
void SeparateTest(void);
void buildTree1(Tree *&);
void buildTree2(Tree *&);
void nodeMat(char);
void clearMat(void);
void markXY(Tree *T1, int x, int level);
void printTree(Tree *);
void cls(void);
void pause(void);

int main() {
   cls();
   string title("1997 AB Exam: Question 3");
   cout << setw(39 + title.length()/2) << title.c_str() << "\n\n"; 
   CountNumTest();
   InsertTest();
   SeparateTest();
  
   return 0;
} // main  ***************************************

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

void CountNumTest(void) {
   Tree *T;
   buildTree1(T);
   clearMat(); markXY(T, initX, 1);
   printTree(T);
   cout << "Testing CountNum:\n";  
   cout << "CountNum(T, 0) = " << CountNum(T, '0') << endl;
   cout << "CountNum(T, 1) = " << CountNum(T, '1') << endl;
   cout << "CountNum(T, 2) = " << CountNum(T, '2') << endl;   
   pause();
}

void InsertTest(void) {
   Tree *T, *P;
   buildTree1(T);
   clearMat(); markXY(T, initX, 1);
   nodeMat('R'); cls(); printTree(T);
   cout << "After Insert(P, 3, 'R'):\n\n"; 
   P = T->right;
   Insert(P, '3','R');
   markXY(T, initX, 1); printTree(T);   
   pause();

   buildTree1(T);
   clearMat(); markXY(T, initX, 1);
   nodeMat('L'); cls(); printTree(T);
   cout << "After Insert(P, 3, 'L'):\n\n"; 
   P = T->left;
   Insert(P, '3','L');
   markXY(T, initX, 1); printTree(T);          
   pause();
}

void SeparateTest(void) {
   Tree *T;
   buildTree2(T);
   clearMat(); markXY(T, initX, 1);
   cls(); printTree(T);
   cout << "After Separate(T):\n"; 
   Separate(T);
   markXY(T, initX, 1); printTree(T);   
   pause();
}

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

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

void markXY(Tree *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->info;
  if (T1->right !=  NULL) {
    markXY(T1->right, x + dx, level + 1);
    treeMat[newY+1].replace(x, dx+1, arcString);     
  }
}//*** markXY


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 printTree(Tree *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 buildTree1(Tree *&root) {
  root = new Tree('0',
            new Tree('4', 
               new Tree('1', NULL, NULL), 
               NULL),
            new Tree('1', 
               new Tree('0', NULL, NULL), 
               new Tree('1', NULL, NULL)
            )); 
}//*** buildTree1

void buildTree2(Tree *&root) {
  root = new Tree('3',
            new Tree('1', 
               new Tree('1', NULL, NULL), 
               new Tree('1', NULL, NULL)),
            new Tree('3', 
               new Tree('3', NULL, NULL), 
               new Tree('1', NULL, NULL)
            )); 
}//*** buildTree2

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

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