// StudsDemo.cpp version 1.18 created March 15, 2000 by Rick Wagner.
//
// String Tree Utility Data Structure (STUDS)demonstration program.
//
// Last modified April 9, 2000 by Rick Wagner.
// Copyright 2000 by Rick Wagner, all rights reserved.

#include <iostream.h>
#include <string.h>
#include <stdlib.h>                                      // For atoi() and NULL.
#include <ctype.h>
#include <time.h>
#include "StringTreeUtility.h"

// Function prototypes:
void main();
void loadPeople(StringTreeNode<Person>* root);
void savePeoplePreorder(StringTreeNode<Person>* root);
void savePeopleBreadthFirst(StringTreeNode<Person>* root);
void buildPeople(Person** array);
void UI();                                               // Text menu user interface.
void pause();
void menu();
void peopleBySSN();
void peopleByAge();
void peopleByName();
void buildRocks(Rock** array, int n, int iColor16Flag);
void rocksByID(int iNumRocks);
void rocksByColor(int iNumRocks);
void sortRandomIntegers(int n);


void main()
{
  int i = 0;
  int iFileMode = 0;                                     // False means use hard-coded array.
  int iSave = 0;                                         // True means save the tree to disk.
  int iAuto = 0;                                         // Flag for automatically testing
  int iByID = 0;                                         // large numbers of rocks.
  int iRocks = 0;
  int iRandomIntegers = 0;

  if (iAuto)
  {
    if (iByID)
    {
      cout << "Sorting " << iRocks << " rocks by ID." << endl << endl;
      rocksByID(iRocks);
      cout << iRocks << " rocks sorted by ID." << endl << endl;
    }
    else
    {
      if (iRandomIntegers)
      {
        cout << "Sorting " << iRocks << " random integers." << endl << endl;
        sortRandomIntegers(iRocks);
        cout << iRocks << " integers sorted." << endl << endl;
      }
      else
      {
        cout << "Sorting " << iRocks << " rocks by Color." << endl << endl;
        rocksByColor(iRocks);
        cout << iRocks << " rocks sorted by color." << endl << endl;
      }
    }
  }
  else
  {
    cout << "String Tree Utility Data Structure demonstration program version 1.11."
         << endl << endl;
    UI();
  }
}

void loadPeople(StringTreeNode<Person>* root)
{
  char* sString = new char[80];
  ifstream infile;

  infile.open("datain.txt");
  if (!infile)
  {
    cout << "Error opening input file." << endl;
  }
  else
  {
    // Build the string tree:
    while (infile >> sString)
    {
      // Add the string to the tree:
      // under construction.
    }
    infile.close();
  }
  delete [] sString;
}

void savePeopleBreadthFirst(StringTreeNode<Person>* root)
{
  ofstream outfile;

  outfile.open("dataout.txt");
  if (!outfile)
  {
    cout << "Error opening output file." << endl;
  }
  else
  {
    saveObjectsBreadthFirst(outfile, root);
    outfile.close();
  }
}

void savePeoplePreorder(StringTreeNode<Person>* root)
{
  ofstream outfile;

  outfile.open("dataout.txt");
  if (!outfile)
  {
    cout << "Error opening output file." << endl;
  }
  else
  {
    root->saveObjectsPreorder(outfile);
    outfile.close();
  }
}

void UI()
{
  char cIn = 'A';
  int iCount = 0;                                    // To tell if it's the first time through.

  while (cIn != 'Q')
  {
    menu();
    if (iCount > 0)
    {
      cout << endl << endl << endl << endl << endl << endl << endl << endl
           << endl << endl << endl << endl << endl << endl;
    }
    iCount++;
    cout << " Your choice? ";
    cin >> cIn;
    cIn = toupper(cIn);

    switch (cIn)
    {
      case 'A':
      {
        peopleBySSN();
        break;
      }
      case 'B':
      {
        peopleByAge();
        break;
      }
      case 'C':
      {
        peopleByName();
        break;
      }
      case 'D':
      {
        rocksByID(0);
        break;
      }
      case 'E':
      {
        rocksByColor(0);
        break;
      }
      case 'F':
      {
        sortRandomIntegers(0);
        break;
      }
    }
    if (cIn != 'Q')
    {
      pause();
    }
  }
}

void pause()
{
  char cX = 0;

  cin.ignore();
  cout << "Hit Enter to continue. ";
  cin.get(cX);
}

void menu()
{
  cout << endl << endl;
  cout << "             STUD Menu" << endl << endl;
  cout << " A. Sort and display people by SSN." << endl;
  cout << " B. Sort and display people by age." << endl;
  cout << " C. Sort and display people by name." << endl;
  cout << " D. Sort rocks by ID number." << endl;
  cout << " E. Sort rocks by color." << endl;
  cout << " F. Sort n random integers." << endl << endl;
  cout << " Q. Quit." << endl << endl;
}

void buildPeople(Person** array)
{
  array[0] = new Person(33, (float) 125.7, "John", "Hancock", "634-36-6115");
  array[1] = new Person(25, (float) 132.3, "George", "Washington", "617-03-2572");
  array[2] = new Person(98, (float) 141.1, "Thomas", "Jefferson", "582-77-8235");
  array[3] = new Person(101, (float) 122.3, "Thomas", "Paine", "567-85-4031");
  array[4] = new Person(45, (float) 146.9, "John", "Adams", "032-72-6527");
  array[5] = new Person(50, (float) 155.3, "Betsy", "Ross", "624-20-6034");
  array[6] = new Person(11, (float) 148.8, "Paul", "Revere", "622-07-8954");
  array[7] = new Person(14, (float) 115.3, "Benedict", "Arnold", "620-28-0546");
  array[8] = new Person(17, (float) 167.3, "John F.", "Kennedy", "267-77-5124");
  array[9] = new Person(19, (float) 149.5, "Richard", "Nixon", "564-65-1392");
  array[10] = new Person(25, (float) 174.3, "Lyndon", "Johnson", "530-06-2870");
  array[11] = new Person(18, (float) 155.3, "Gary", "Cooper", "575-53-1323");
  array[12] = new Person(19, (float) 123.3, "Theodore", "Roosevelt", "630-82-7306");
  array[13] = new Person(24, (float) 135.6, "Herbert", "Hoover", "623-09-0921");
  array[14] = new Person(14, (float) 126.3, "John D.", "Rockefeller", "627-26-5686");
  array[15] = new Person(13, (float) 152.2, "Calvin", "Cooledge", "497-84-1694");
  array[16] = new Person(11, (float) 127.1, "Cary", "Grant", "572-83-9039");
  array[17] = new Person(12, (float) 175.3, "Marilyn", "Monroe", "569-93-9321");
  array[18] = new Person(19, (float) 188.6, "William Jefferson", "Clinton", "285-80-7783");
  array[19] = new Person(25, (float) 159.3, "Kevin", "Costner", "582-47-7680");
}

void peopleBySSN()
{
  int i = 0;
  StringTreeNode<Person>* personRoot = NULL;

  personRoot = new StringTreeNode<Person>('.');  // The root of the tree.

  Person** array = new Person*[20];
  buildPeople(array);

  for (i = 0; i < 20; i++)
  {
    personRoot->insert(array[i]->getSSN(), array[i]);
  }

  cout << endl << "People sorted by SSN:" << endl <<endl;
  cout << setw(11) << "SSN:" << " "
       << setw(17) << "First name:" << " "
       << setw(11) << "Last name:" << " "
       << setw(10) << "Age:"  << " "
       << setw(10) << "Weight:" << endl;

  personRoot->preOrderPrintObjects();
  cout << endl;

  for (i = 0; i < 20; i++)               // Delete the people.
  {
    delete array[i];
  }
  delete [] array;
}

void peopleByAge()
{
  int i = 0;
  StringTreeNode<Person>* personRoot = NULL;
  StringTreeNode<Person>* ageNode = NULL;
  StringTreeNode<Person>* nextAgeNode = NULL;

  personRoot = new StringTreeNode<Person>('.');  // The root of the tree.


  Person** array = new Person*[20];
  buildPeople(array);

  for (i = 0; i < 20; i++)
  {
    personRoot->insert(array[i]->getAge(), array[i]);
  }

  cout << endl << "People sorted by Age:" << endl <<endl;
  cout << setw(11) << "SSN:" << " "
       << setw(17) << "First name:" << " "
       << setw(11) << "Last name:" << " "
       << setw(10) << "Age:"  << " "
       << setw(10) << "Weight:" << endl;

  breadthFirstPrint(personRoot);
  cout << endl;

  ageNode = personRoot->findNode("98");
  if (ageNode != NULL)
  {
    ageNode->getDataObjectQueue()->peek(1)->print();
    cout << "calling nextNode()" << endl;
    nextAgeNode = personRoot->nextNode(98);
  }
  if (nextAgeNode != NULL)
  {
    nextAgeNode->getDataObjectQueue()->peek(1)->print();
  }
  else
  {
    cout << "No next age." << endl;
  }

  for (i = 0; i < 20; i++)               // Delete the people.
  {
    delete array[i];
  }
  delete [] array;
}

void peopleByName()
{
  int i = 0;
  StringTreeNode<Person>* personRoot = NULL;
  char* sName;
  int iNameLength;
  StringTreeNode<Person>* nextPerson = NULL;

  personRoot = new StringTreeNode<Person>('.');  // The root of the tree.

  Person** array = new Person*[20];
  buildPeople(array);

  for (i = 0; i < 20; i++)
  {
    iNameLength = strlen(array[i]->getLastName()) + strlen(array[i]->getFirstName());
    sName = new char[iNameLength + 1];
    strcpy(sName, array[i]->getLastName());
    strcat(sName, array[i]->getFirstName());
    personRoot->insert(sName, array[i]);
    delete [] sName;
  }

  nextPerson = personRoot->nextNode("GrantCary");

  cout << endl << "People sorted by name:" << endl;
  cout << setw(11) << "SSN:" << " "
       << setw(17) << "First name:" << " "
       << setw(11) << "Last name:" << " "
       << setw(10) << "Age:"  << " "
       << setw(10) << "Weight:" << endl;

  personRoot->preOrderPrintObjects();

  if (nextPerson != NULL)
  {
    cout << "Next after Cary Grant: " << endl;
    nextPerson->getDataObjectQueue()->peek(1)->print();
  }

  for (i = 0; i < 20; i++)               // Delete the people.
  {
    delete array[i];
  }
  delete [] array;
}

void buildRocks(Rock** array, int n, int iColor16Flag)
{
  int i = 0;
  int j = 0;
  char* sColor = NULL;
  int iRandIndex = NULL;                         // Rock pointer index for swapping.
  Rock* temp = NULL;                             // Temporary rock for swapping.
  int iLen = 0;
  int iChar = 0;

  for (i = 0; i < n; i++)
  {
    if (iColor16Flag)
    {
      switch(rand() % 16)
      {
        case 0:
          sColor = "black";
          break;
        case 1:
          sColor = "brown";
          break;
        case 2:
          sColor = "red";
          break;
        case 3:
          sColor = "orange";
          break;
        case 4:
          sColor = "yellow";
          break;
        case 5:
          sColor = "green";
          break;
        case 6:
          sColor = "blue";
          break;
        case 7:
          sColor = "violet";
          break;
        case 8:
          sColor = "white";
          break;
        case 9:
          sColor = "gray";
          break;
        case 10:
          sColor = "purple";
          break;
        case 11:
          sColor = "mauve";
          break;
        case 12:
          sColor = "scarlet";
          break;
        case 13:
          sColor = "pink";
          break;
        case 14:
          sColor = "rose";
          break;
        case 15:
          sColor = "lake";
          break;
      }
    }
    else
    {
      // Assign colors as random strings:
      iLen = 3 + (rand() % 4);
      sColor = new char[iLen + 1];
      for (j = 0; j < iLen; j++)
      {
        sColor[j] = 97 + rand() % 26;
      }
      sColor[iLen] = '\0';
    }
    array[i] = new Rock(i, sColor);
    if (!iColor16Flag) delete [] sColor;
  }
  // Randomize (permute) the array:
  for (i = 0; i < n; i++)
  {
    iRandIndex = rand() % n;
    temp = array[i];
    array[i] = array[iRandIndex];
    array[iRandIndex] = temp;
  }
}

void rocksByID(int iNumRocks)
{
  int i = 0;
  int iManual = 0;
  Rock** array;
  char* sID = NULL;
  StringTreeNode<Rock>* rockRoot = NULL;
  StringTreeNode<Rock>* cursor = NULL;
  double dfProc = 0;
  int iPrint = 0;
  
  if (iNumRocks == 0)
  {
    iManual = 1;
    cout << endl;
    cout << "Sort rocks by ID:" << endl << endl;
    cout << "How many rocks do you want to sort? ";
    cin >> iNumRocks;
  }

  array = new Rock*[iNumRocks];
  buildRocks(array, iNumRocks, 1);

  rockRoot = new StringTreeNode<Rock>((int) '0', (int) '9', '.');  // The root of the tree.

  for (i = 0; i < iNumRocks; i++)
  {
    rockRoot->insert(array[i]->getID(), array[i]);
  }
  breadthFirstStore(array, rockRoot);

  dfProc = ((double) clock()) / CLOCKS_PER_SEC;  // 1000 clocks per second.

  if (iManual)
  {
    cout << endl;
    cursor = rockRoot->findNode(0);
    while (cursor != NULL)
    {
      iPrint = cursor->getDataObjectQueue()->peek(1)->getID();
      cout << iPrint << endl;
      cursor = rockRoot->nextNode(iPrint);
    }
    //for (i = 0; i < iNumRocks; i++)
    //{
    //  array[i]->print();
    //}
    cout << endl;
  }
  else
  {
    cout << endl << "Processor time = " << dfProc << endl;
  }

  delete [] sID;
  for (i = 0; i < iNumRocks; i++)               // Delete the rocks.
  {
    delete array[i];
  }
  delete [] array;
}

// Sort rocks by color:
void rocksByColor(int iNumRocks)
{
  int i = 0;                                    // Loop index.
  int iManual = 0;                              // Flag for manual entry.
  Rock** array;                                 // Array of rock pointers.
  StringTreeNode<Rock>* rockRoot = NULL;        // Root of the tree of rocks.
  double dfProc = 0;                            // Statistical information variable.
  
  if (iNumRocks == 0)                           // Get the number from the user.
  {
    iManual = 1;
    cout << endl;
    cout << "Sort rocks by color:" << endl << endl;
    cout << "How many rocks do you want to sort? ";
    cin >> iNumRocks;
  }

  array = new Rock*[iNumRocks];                 // Create the array of pointers.                 
  buildRocks(array, iNumRocks, 0);              // Create rocks randomly.
  dfProc = ((double) clock()) / CLOCKS_PER_SEC; // 1000 clocks per second.
  cout << endl << "Build rocks processor time = " << dfProc << endl;

  rockRoot = new StringTreeNode<Rock>((int) 'a', (int) 'z', '.'); // The root of the tree.

  for (i = 0; i < iNumRocks; i++)               // Insert the rocks into the tree.
  {
    rockRoot->insert(array[i]->getColor(), array[i]);
  }
  i = 0;
  rockRoot->preOrderStoreObjects(array, i);     // Traverse the tree in preorder and
                                                // store the rocks back in the array.
  dfProc = ((double) clock()) / CLOCKS_PER_SEC; // 1000 clocks per second.

  if (iManual)
  {
    cout << endl;
    for (i = 0; i < iNumRocks; i++)
    {
      array[i]->print();
    }
  }
  else
  {
    cout << endl << "Processor time = " << dfProc << endl;
  }

  for (i = 0; i < iNumRocks; i++)               // Delete the rocks.
  {
    delete array[i];
  }
  delete [] array;
}

void sortRandomIntegers(int n)
{
  int i = 0;                                    // Loop index.
  int iManual = 0;                              // Flag for manual entry.
  int** array;                                  // Array of integers.
  int iKey;
  StringTreeNode<int>* intRoot = NULL;          // Root of the tree of ints.
  double dfProc = 0;                            // Statistical information variable.
  
  if (n == 0)                                   // Get the number from the user.
  {
    iManual = 1;
    cout << endl;
    cout << "Sort random integers:" << endl << endl;
    cout << "How many integers do you want to sort? ";
    cin >> n;
  }
  array = new int*[n];                           // Create the array of int pointers.                 

  intRoot = new StringTreeNode<int>((int) '0', (int) '9', '.'); // The root of the tree.

  for (i = 0; i < n; i++)               // Insert the ints into the tree.
  {
    iKey = rand();
    array[i] = new int(iKey);
    intRoot->insert(iKey, array[i]);
  }

  breadthFirstStore(array, intRoot);

  dfProc = ((double) clock()) / CLOCKS_PER_SEC; // 1000 clocks per second.

  if (iManual)
  {
    cout << endl;
    for (i = 0; i < n; i++)
    {
      cout << *array[i] << endl;
    }
    cout << endl;
  }
  else
  {
    cout << endl << "Processor time = " << dfProc << endl;
  }
  delete [] array;
}