//****************************************************************************
//
// Program:      Homework 2 -- n-ary tree
//
// Author:       Travis Dillon
// Email:        tdillon@ace.cs.ohiou.edu
//
// Description:  This program takes input of a representation of an n-ary left
//               child right sibling, and puts it into a binary tree.
//
// Date:         September 22, 2003
//
//****************************************************************************


#include "prog1.h"
#include "tree.h"

void get_data(vector <Name>& holder);
size_t find_name(const Name& temp_name, vector <Name>& holder);

int main()
{
   Tree oak;
   vector <Name> holder;

   get_data(holder);
   oak.set_root(holder);
   oak.make_tree(oak.get_root_at_left(), holder);

   cout << endl << endl;
   oak.print(oak.get_root());
   cout << endl << "n-ary depth: ";
   cout << oak.get_nary_depth(oak.get_root(), 0);
   cout << endl << "binary depth: ";
   cout << oak.get_depth(oak.get_root(), 0) << endl;

   return EXIT_SUCCESS;
}


//****************************************************************************
//
// Function:   get_data
//
// Purpose:    get data from keyboard and store it in a vector for later use
//
// Parameters: holder - containter of the keyboard input
//
// Calls:      function push_back, find_name
//
//****************************************************************************


void get_data(vector <Name>& holder)
{
   size_t count(0);
   size_t num_node(0);
   char temp;
   string junk;
   Name temp_name;

   while(cin.peek() == '#')  //this will run however many comments there are
   {
      getline(cin, junk);
   }

   cin >> num_node;

   while(count < num_node)  //worst case runtime is number of nodes square + 10
   {			   //this while loop can run up to the number of nodes
      cin >> temp;	  //and find_name runs up to number of node times
      if(temp == '#')
      {
         getline(cin, junk);  //space complexity is a constant five for this 
      }			     //function, only five variables used

      else if(temp == '(')
      {
         cin >> temp_name.one;
         cin >> temp_name.two;
         cin >> temp_name.three;

         if(temp_name.three == ")")
         {
            temp_name.three = "";
         }

         count += find_name(temp_name, holder);
         holder.push_back(temp_name);

         if(temp_name.three == "")
         {
            temp_name.three = "";
            count -= 1;
         }
         else
         {
            cin >> temp;
         }
      }

      else
      {
         cout << "\nThe input tree is not in the correct format!\n\n";
         exit(0);
      }
   }
}


//****************************************************************************
//
// Function:   find_name
//
// Purpose:    checks the vector to see if a new entry is in it
//
// Parameters: temp_name - struct of three names from the keyboard
//             holder - vector that holds all the keyboard input
//
// Calls:      function begin, empty, end
//
//****************************************************************************


size_t find_name(const Name& temp_name, vector <Name>& holder)
{
   size_t counter(0);
   size_t temp_one(0);
   size_t temp_two(0);
   size_t temp_three(0);
   vector<Name>::iterator iter = holder.begin();
   if(holder.empty())
   {
      if(temp_name.one != "NULL") ++counter;
      if(temp_name.two != "NULL") ++counter;
      if(temp_name.three != "NULL") ++counter;
      return counter;
   }
   else  //worst case runtime is the number of nodes + 10
   {     //space complexity is number of nodes + 6
      while(iter != holder.end())
      {

         if(temp_name.one != "NULL")
         {
            if(temp_name.one == iter -> one) ++temp_one;
            if(temp_name.one == iter -> two) ++temp_one;
            if(temp_name.one == iter -> three) ++temp_one;
         }
         else
         {
            ++temp_one;
         }
         if(temp_name.two != "NULL")
         {
            if(temp_name.two == iter -> one) ++temp_two;
            if(temp_name.two == iter -> two) ++temp_two;
            if(temp_name.two == iter -> three) ++temp_two;
         }
         else
         {
            ++temp_two;
         }
         if(temp_name.three != "NULL")
         {
            if(temp_name.three == iter -> one) ++temp_three;
            if(temp_name.three == iter -> two) ++temp_three;
            if(temp_name.three == iter -> three) ++temp_three;
         }
         else
         {
            ++temp_three;
         }
         ++iter;
      }

      if(temp_one == 0) ++counter;
      if(temp_two == 0) ++counter;
      if(temp_three == 0) ++counter;
      return counter;
   }
}