// FILE: 02ab4.cpp 
// PURPOSE: 2002 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 02ab4S.cpp
//---------------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// 1. Print out 2002 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 Node {
   Node(char ch, Node *left2=NULL, Node *right2=NULL) :
            letter(ch), left(left2), right(right2) {}
   char letter;
   Node *left;
   Node *right;
};

class CodeTree {
  friend  
    void CharToBitsHelperTest(Node *T);
  public:
    CodeTree(Node *np = NULL) : myRoot(np) {}
    string BitsToWord(const string &code) const;
    string WordToBits(const string &word) const;
  private:
    string CharToBitsHelper(char ch, Node *T, const string &pathSoFar);    
    Node *myRoot;
};

/////////////////////////////////////////////
//             Part (a)
/////////////////////////////////////////////
string CodeTree::BitsToWord(const string &code) const {
  const int LEN = code.length();
  return "";  
}


/////////////////////////////////////////////
//            Part (b)
/////////////////////////////////////////////
string CodeTree::CharToBitsHelper(char ch, Node *T, const string &pathSoFar) {
    return "";          
}

void BitsToWordTest(Node *T);
void CharToBitsHelperTest(Node *T);
void buildTree(Node *&);
void clearMat(void);
void nodeMat(void);
void markXY(Node *T1, int x, int level);
void printTree(Node *);
void cls(void);
void pause(void);

int main() {
   Node *T;
   buildTree(T);
   cls();
   string title("2002 AB Exam: Question 4");
   cout << setw(39 + title.length()/2) << title.c_str() << "\n\n";
   BitsToWordTest(T);
   CharToBitsHelperTest(T);
   return 0;
} // main  ***************************************


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

void BitsToWordTest(Node *T) {
  CodeTree C(T);
  clearMat(); markXY(T, initX, 1); 
  printTree(T);             
  cout << "Testing CodeTree::BitsToWord:\n\n";
  cout << "C.BitsToWord(\"1110\") should = \"in\", = " 
       << C.BitsToWord("1110") << endl;
  cout << "C.BitsToWord(\"000101010011\") should = \"sunny\", = " 
       << C.BitsToWord("000101010011") << endl;       
  pause();
}


void CharToBitsHelperTest(Node *T) {
  cls();
  CodeTree C(T);
  clearMat(); markXY(T, initX, 1); 
  printTree(T);             
  cout << "Testing CodeTree::CharToBitsHelper:\n" << endl;
  cout << "C.CharToBitsHelper('y', myRoot, \"\") should = \"011\", = ";
  cout << '\"' << C.CharToBitsHelper('y', C.myRoot, "")  << '\"' << endl;
  cout << "C.CharToBitsHelper('n', myRoot, \"\") should = \"10\", = "; 
  cout << '\"' << C.CharToBitsHelper('n', C.myRoot, "") << '\"' << endl;
 pause();
}

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

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

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



void nodeMat(void) {
   // not needed for 2002 AB 4 code
   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(Node *T) {
  const string title(" C");
  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(Node *&root) {
  root = new Node('*', 
            new Node('*', 
              new Node('s', NULL, NULL), 
              new Node('*',
                new Node('u', NULL, NULL),
                new Node('y', NULL, NULL))),                     
            new Node('*', 
              new Node('n', NULL, NULL), 
              new Node('i', 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'); 
}