// FILE: 95ab4.cpp 
// PURPOSE: 1995 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 95ab4.cpp
//---------------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// 1. Print out 1995 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 {
   TreeNode(char ch, TreeNode *left2, TreeNode *right2) :
            info(ch), left(left2), right(right2) {}
   char info;
   TreeNode *left;
   TreeNode *right;
};

bool HasOneChild(TreeNode *);

bool IsChild(TreeNode * first, TreeNode * second)   {
  // precondition: second != NULL
  // postcondition: returns true if second is a child of first
  //                returns false otherwise
  return false; 
}

bool IsDescendant(TreeNode * first, TreeNode * second) {
  // precondition: second != NULL
  return false; 
}


void ChangeTree(TreeNode *&T)  {
  // postorder skips some candidates because T is updated prematurely


}

void isChildTest(TreeNode *);
void isDescendantTest(TreeNode *);
void ChangeTreeTest(TreeNode *&);
void buildTree(TreeNode *&);
void clearMat(void);
void nodeMat(void);
void markXY(TreeNode *T1, int x, int level);
void printTree(TreeNode *);
void cls(void);
void pause(void);

int main() {
   TreeNode *T;
   buildTree(T);
   cls();
   string title("1995 AB Exam: Question 4");
   cout << setw(39 + title.length()/2) << title.c_str() << "\n\n";
   isChildTest(T);
   isDescendantTest(T);   
   ChangeTreeTest(T);
   return 0;
} // main  ***************************************


bool HasOneChild(TreeNode *T) {
   return (T->left != NULL && T->right == NULL) || 
          (T->right != NULL && T->left == NULL);
}

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

void isChildTest(TreeNode *T) {
   TreeNode *NodeC = T->left, *NodeD = NodeC->left, *NodeA = T->right;
   clearMat(); markXY(T, initX, 1);  nodeMat();
   printTree(T);             
   cout << "Testing IsChild:\n";
   cout << "IsChild(NodeC, NodeD) = "  
        << (IsChild(NodeC, NodeD)? "true" : "false") << endl;     
   cout << "IsChild(NodeD, NodeC) = "  
        << (IsChild(NodeD, NodeC)? "true" : "false") << endl;     
   cout << "IsChild(T, NodeA) = "  
        << (IsChild(T, NodeA)? "true" : "false") << endl;     
   cout << "IsChild(NodeC, NodeA) = "  
        << (IsChild(NodeC, NodeA)? "true" : "false") << endl;     
   pause();
}


void isDescendantTest(TreeNode *T) {
   cls();
   printTree(T);
   cout << "Testing IsDescendant:\n";
   TreeNode *NodeA(T->right), *NodeB(NodeA->right->left);
   TreeNode *NodeC(T->left), *NodeD(NodeC->left);  
   cout << "IsDescendant(NodeC, NodeA) = " 
        << (IsDescendant(NodeC, NodeA)? "true" : "false") << endl;    
   cout << "IsDescendant(NodeA, NodeB) = " 
        << (IsDescendant(NodeA, NodeB)? "true" : "false") << endl;    
   cout << "IsDescendant(NodeB, NodeA) = " 
        << (IsDescendant(NodeB, NodeA)? "true" : "false") << endl;    
   cout << "IsDescendant(NodeC, NodeD) = " 
        << (IsDescendant(NodeC, NodeD)? "true" : "false") << endl;    
   cout << "IsDescendant(NodeA, NodeA) = " 
        << (IsDescendant(NodeA, NodeA)? "true" : "false") << endl;            
   pause();
}

void ChangeTreeTest(TreeNode *&T) {
   cls();
   clearMat(); markXY(T, initX, 1);
   printTree(T);
   cout << "Testing ChangeTree:\n\n";
   ChangeTree(T); 
   clearMat(); 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(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->info;
  if (T1->right !=  NULL) {
    markXY(T1->right, x + dx, level + 1);
    treeMat[newY+1].replace(x, dx+1, arcString);     
  }
}//*** markXY



void nodeMat(void) {
   int leftPos = treeMat[5].find('4') - 9;
   treeMat[3].replace(leftPos, 9, "NodeC--> "); 
   treeMat[5].replace(leftPos, 9, "NodeD--> ");   
   int rightPos = treeMat[7].find('8') + 5; 
   treeMat[3].replace(rightPos, 9, " <--NodeA"); 
   treeMat[7].replace(rightPos, 9, " <--NodeB");
}


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 buildTree(TreeNode *&root) {
  root = new TreeNode('1',
            new TreeNode('2', 
               new TreeNode('4', NULL,
                  new TreeNode('7', NULL, NULL)
               ), NULL), 
            new TreeNode('3', 
               new TreeNode('5', NULL, NULL), 
               new TreeNode('6', 
                  new TreeNode('8', NULL, NULL), 
               NULL)
            )); 
}//*** builtTree


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

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