// StringTreeUtility.h version 1.18 created March 15, 2000 by Rick Wagner.
//
// Provides a String Tree Utility Data Structure (STUDS).
//
// This file last modified April 10, 2000 by Rick Wagner.
// Copyright 2000 by Rick Wagner, all rights reserved.

#ifndef STRINGTREEUTILITY_H
#define STRINGTREEUTILITY_H

#include <iostream.h>                                // For console IO.
#include <iomanip.h>                                 // For console IO formatting.
#include <fstream.h>                                 // For file IO.
#include <stdlib.h>                                  // For NULL.
#include <string.h>                                  // For strlen().

// Global constants:
const int giAlphabetSize = 128;                      // 7-bit ascii alphabet.

// General utility function prototypes:
void intToString(int iIn, char*& sOut);              // Creates new C-string in heap memory by reference.

// Predefine a class:
template<class Item>
class Queue;                                         // Each StringTreeNode has a queue for object storage.


// Class to build a tree database of string keyed objects:
template<class Item>
class StringTreeNode
{
public:

  // Constructors:
  StringTreeNode(char n);
  StringTreeNode(char n, int flag);
  StringTreeNode(int minChar, int maxChar, char n);
  StringTreeNode(int minChar, int maxChar, char n, int flag);

  // Destructor:
  ~StringTreeNode();

  // Member functions:
  void insert(char* sKey, Item* obj);                // For building the string tree with string key.
  void insert(int iKey, Item* obj);                  // For building the string tree with integer key.
  void collectCharacters(char*& sString, int& i);    // Construct the key string from an object node.
  void printObjects();                               // Print the objects of a tree node to the screen.
  void preOrderPrintObjects();                       // Walk the tree preorder and print out objects.
  void preOrderStoreObjects(Item* array[], int& n);  // Walk the tree and store that objects in an array.
  void writeObject(ofstream outfile);                // Write a character of the tree to file.
  void saveObjectsPreorder(ofstream outfile);        // Walk the tree and save the objects to file.
  int existsP(char* sString);                        // Predicate for string search.
  int lastCharacter();                               // Return true if an object is stored at the node.
  StringTreeNode<Item>* getChild(int i);             // Return the ith child node.
  StringTreeNode<Item>* findNode(char* sKey);        // Find the node for a key string.
  StringTreeNode<Item>* findNode(int iKey);          // Find the node for a key string.
  StringTreeNode<Item>* nextNode(char* sKey);        // Return the next node in alphabetical order.
  StringTreeNode<Item>* nextNode(int iKey);          // Return the next node in numerical order.
  Queue<Item*>* getDataObjectQueue();                // Return the whole object queue at the node.
  int getMinChar();                                  // Get the minimal character for this tree.
  int getMaxChar();                                  // Get the maximal character for this tree.

  // Friend functions:
  friend void breadthFirstStore(Item* array[], StringTreeNode<Item>* stn);

private:

  int _iMinChar;                                     // Minimal character for this instance.
  int _iMaxChar;                                     // Maximal character for this instance.
  char _cDigit;                                      // Storage for a single digit of a string;
  int _lastCharacter;                                // Flag to indicate that the character is terminal.
  StringTreeNode<Item>** _childArray;                // Array of child node pointers.
  StringTreeNode<Item>* _parent;                     // The child must know its parent to recover key strings.
  Queue<Item*>* _dataObjectQueue;                    // Queue for storing data objects in the tree node.

  // Helper member functions:
  StringTreeNode<Item>* preOrderNextNode(char* sString, int& iFlag);
};

// Non-member functions:
template<class Item>
void breadthFirstPrint(Item stn);                    // Print objects to screen breadth first.

template<class Item>                                 // Save objects breadth first.
void saveObjectsBreadthFirst(ofstream outfile, Item stn);

// Class for a list node for queue and stack classes:
template <class Item>                                // Item can be a StringTreeNode pointer,
class ListNode                                       // data object, or anything else.
{
public:

  // Constructors:
  ListNode();
  ListNode(Item data, ListNode<Item>* next);

  // Accessor:
  Item getData();

  // Mutators:
  void setNext(ListNode* next);
  ListNode<Item>* getNext();
  ListNode<Item>* insertAfter(Item entry);

private:

  Item _data;                                         // The stored object.
  ListNode<Item>* _next;                              // Pointer to next node.
};

// Nonmember functions:
template <class Item>
void insertBeforeHead(ListNode<Item>*& head, Item entry);

template <class Item>
void deleteHead(ListNode<Item>*& head);


// Class for a queue for storing objects at tree nodes and for breadth-first search:
template <class Item>
class Queue
{
public:

  // Constructors:
  Queue();

  // Mutators:
  Item  pop();                                         // Pop from front.
  void push(Item data);                                // Push from rear.

  // Accessors:
  Item peek(int n = 1);                                // Peek at the nth item (1 is front of queue).
  ListNode<Item>* getFront();
  int empty() {return _iNumInQueue == 0;}
  int size() {return _iNumInQueue;}

private:

  int _iNumInQueue;                                    // Size of the queue.
  ListNode<Item>* _front;                              // Pointer to the front.
  ListNode<Item>* _rear;                               // Pointer to the rear.
};

// Class for a stack for converting integer to string:
template <class Item>
class Stack
{
public:

  Stack();                                             // Constructor.
  Item pop();                                          // Remove and return the top item.
  void push(Item data);                                // Push item onto the stack.
  int empty() {return _iNumInStack == 0;}
  int size() {return _iNumInStack;}

private:

  int _iNumInStack;                                    // Size of the stack.
  ListNode<Item>* _top;                                // Pointer to stack top.
};

// Class for person objects for test of the STUD algorithms:
class Person
{
public:

  // Constructors:
  Person();
  Person(int age, float weight, char* firstName, char* lastName, char* SSN);

  // Destructor:
  ~Person();

  // Accessors:
  int getAge();
  float getWeight();
  char* getFirstName();
  char* getLastName();
  char* getSSN();
  void print();

private:

  int _iAge;
  float _sfWeight;
  char* _sFirstName;
  char* _sLastName;
  char* _sSSN;
};

// Class for rock objects for test of the STUD algorithms:
class Rock
{
public:

  Rock();
  Rock(int iID, char* sColor);
  ~Rock();
  int getID();
  char* getColor();
  void print();
  
private:

  int _iID;
  char* _sColor;
};

// * * Template class implementations * * * * * * * * * * * * * * * * * * * * * * * * * * 

// * * StringTreeNode class implementations * *

// Character constructor:
template <class Item>
StringTreeNode<Item>::StringTreeNode(char n)
{
  int i = 0;

  _iMinChar = 0;
  _iMaxChar = 127;

  _cDigit = n;
  _lastCharacter = 0;
  _childArray = new StringTreeNode<Item>*[giAlphabetSize];
  for (i = 0; i < giAlphabetSize; i++) _childArray[i] = NULL;
  _parent = NULL;
  _dataObjectQueue = new Queue<Item*>;
}

// Digit character and last character flag constructor:
template <class Item>
StringTreeNode<Item>::StringTreeNode(char n, int flag)
{
  int i = 0;

  _iMinChar = 0;
  _iMaxChar = 127;

  _cDigit = n;
  _lastCharacter = flag;                                   // 1 means last character of a string.
  _childArray = new StringTreeNode<Item>*[giAlphabetSize];
  for (i = 0; i < giAlphabetSize; i++) _childArray[i] = NULL;
  _parent = NULL;
  _dataObjectQueue = new Queue<Item*>;
}

// Constructor with specific alphabet range:
template <class Item>
StringTreeNode<Item>::StringTreeNode(int minChar, int maxChar, char n)
{
  int i = 0;

  _iMinChar = minChar;
  _iMaxChar = maxChar;

  _cDigit = n;
  _lastCharacter = 0;
  _childArray = new StringTreeNode<Item>*[maxChar + 1];
  for (i = 0; i <= maxChar; i++) _childArray[i] = NULL;
  _parent = NULL;
  _dataObjectQueue = new Queue<Item*>;
}

// Constructor with specific alphabet range and last character flag:
template <class Item>
StringTreeNode<Item>::StringTreeNode(int minChar, int maxChar, char n, int flag)
{
  int i = 0;

  _iMinChar = minChar;
  _iMaxChar = maxChar;

  _cDigit = n;
  _lastCharacter = flag;                                   // 1 means last character of a string.
  _childArray = new StringTreeNode<Item>*[maxChar + 1];
  for (i = 0; i <= maxChar; i++) _childArray[i] = NULL;
  _parent = NULL;
  _dataObjectQueue = new Queue<Item*>;
}

// Destructor:
template <class Item>
StringTreeNode<Item>::~StringTreeNode()
{
  int i = 0;

  for (i = 0; i <= maxChar; i++)
  {
    if (_childArray[i] != NULL) delete _childArray[i];
  }
  delete [] _childArray;
  delete _dataObjectQueue;
}

// Add a string keyed object to the database (call from root StringTreeNode):
template <class Item>
void StringTreeNode<Item>::insert(char* sKey, Item* obj)
{
  int flag = 0;
  int iLength = (int) strlen(sKey);

  if (iLength > 0)
  {
    if (iLength == 1) flag = 1;                                  // A ones digit character.

    if (_childArray[sKey[0]] == NULL)                            // Create the child.
    {
      _childArray[sKey[0]] = new StringTreeNode<Item>(_iMinChar, _iMaxChar, sKey[0], flag);
      _childArray[sKey[0]]->_parent = this;

      // Push the data item into the rear of the queue:
      if (flag) _childArray[sKey[0]]->_dataObjectQueue->push(obj);
    }
    else
    {
      if (flag)
      {
        _childArray[sKey[0]]->_lastCharacter = 1;                // Mark the node;

        // Push the data item onto the rear of the queue:
        _childArray[sKey[0]]->_dataObjectQueue->push(obj);
      }
    }

    _childArray[sKey[0]]->insert(sKey + 1, obj);                 // Recursive call.
  }
}

// Add a string keyed object to the database (call from root StringTreeNode):
template <class Item>
void StringTreeNode<Item>::insert(int iKey, Item* obj)
{
  //int flag = 0;
  char* sKey = NULL;
  //int iLength = 0;

  intToString(iKey, sKey);
  insert(sKey, obj);
}

// Construct the string string for output:
template <class Item>
void StringTreeNode<Item>::collectCharacters(char*& sString, int& i)
{
  if (_parent != NULL)
  {
    _parent->collectCharacters(sString, i);                      // Recursive call.
    sString[i] = _cDigit;                                        // Post-order accumulation.
    sString[i + 1] = 0;                                          // Set the null character terminator.
    i++;
  }
}

// Print the objects from a ones digit node:
template <class Item>
void StringTreeNode<Item>::printObjects()
{
  int i = 0;
  int n = 0;
  Item* obj;

  n = _dataObjectQueue->size();

  for (i = 1; i <= n; i++)
  {
    obj = _dataObjectQueue->peek(i);
    obj->print();
  }
}

// Pre-order traverse the string tree and print all the objects:
template <class Item>
void StringTreeNode<Item>::preOrderPrintObjects()
{
  int i = 0;

  if (_lastCharacter) printObjects();                               // Pre-order print.

  for (i = _iMinChar; i <= _iMaxChar; i++)
  {
    if (_childArray[i] != NULL) _childArray[i]->preOrderPrintObjects();
  }
}

// Pre-order traverse the string tree and store all the objects in an array:
template <class Item>
void StringTreeNode<Item>::preOrderStoreObjects(Item* array[], int& n)
{
  int i = 0;

  if (_lastCharacter)
  {
    // Process the objects stored at the node:
    while (!_dataObjectQueue->empty())
    {
      array[n] = _dataObjectQueue->pop();
      n++;
    }
  }

  for (i = _iMinChar; i <= _iMaxChar; i++)
  {
    if (_childArray[i] != NULL) _childArray[i]->preOrderStoreObjects(array, n);
  }
}

// Write the string string to output file from the ones digit node:
template <class Item>
void StringTreeNode<Item>::writeObject(ofstream outfile)
{
  char* sString = new char[80];
  sString[0] = 0;
  int i = 0;

  collectCharacters(sString, i);
  outfile << sString << endl;

  delete [] sString;
}

// Pre-order traverse the tree and write the objects to output file:
template <class Item>
void StringTreeNode<Item>::saveObjectsPreorder(ofstream outfile)
{
  int i = 0;

  if (_lastCharacter) writeObject(outfile);

  for (i = 0; i < 10; i++)
  {
    if (_childArray[i] != NULL) _childArray[i]->saveObjectsPreorder(outfile);
  }
}

// Is the string a key in the tree structure (call from root)?
template <class Item>
int StringTreeNode<Item>::existsP(char* sString)
{
  int r = 0;
  int iLength = (int) strlen(sString);
  
  if (iLength > 0 && _childArray[sString[0]] != NULL)
  {
    if (iLength == 1)
    {
      if (_childArray[sString[0]]->_lastCharacter) r = 1;
    }
    else
    {
      r = _childArray[sString[0]]->existsP(sString + 1);   // Recursive call.
    }
  }
  return r;
}

// Return the node of the given string key:
template <class Item>
StringTreeNode<Item>* StringTreeNode<Item>::findNode(char* sString)
{
  StringTreeNode<Item>* r = NULL;

  int iLength = (int) strlen(sString);
  
  if (iLength > 0 && _childArray[sString[0]] != NULL)
  {
    if (iLength == 1)
    {
      if (_childArray[sString[0]]->_lastCharacter) r = _childArray[sString[0]];
    }
    else
    {
      r = _childArray[sString[0]]->findNode(sString + 1);
    }
  }
  return r;
}

// Return the node of the given integer key:
template <class Item>
StringTreeNode<Item>* StringTreeNode<Item>::findNode(int iKey)
{
  StringTreeNode<Item>* r = NULL;
  char* sString = NULL;
  
  intToString(iKey, sString);
  int iLength = (int) strlen(sString);

  if (iLength > 0 && _childArray[sString[0]] != NULL)
  {
    if (iLength == 1)
    {
      if (_childArray[sString[0]]->_lastCharacter) r = _childArray[sString[0]];
    }
    else
    {
      r = _childArray[sString[0]]->findNode(sString + 1);
    }
  }
  return r;
}

// Recursively search the tree to find the next (preorder depth first) string keyed object in the tree:
template <class Item>
StringTreeNode<Item>* StringTreeNode<Item>::nextNode(char* sString)    // Call this function from the root.
{
  StringTreeNode<Item>* nextNode = NULL;
  StringTreeNode<Item>* stn = NULL;
  int iFlag = 0;
    
  stn = findNode(sString);                                             // There can't be a "next" if the
                                                                       // item before it doesn't exist.
  if (stn != NULL)
  {
    cout << "Found string " << sString << endl;
    nextNode = preOrderNextNode(sString, iFlag);
  }
  return nextNode;
}

// Helper function for nextNode(char* sString):
template <class Item>
StringTreeNode<Item>* StringTreeNode<Item>::preOrderNextNode(char* sString, int& iFlag)
{
  StringTreeNode<Item>* nextNode = NULL;
  int i = 0;
  char* sNode = new char[80];                                // For collectCharacters().

  // Find the next node in alphabetical order:
  if (_lastCharacter)
  {
    if (iFlag == 1)                                          // Signal that this one is it.
    {
      nextNode = this;
      iFlag = 2;                                             // Signals we have found the next node.
    }
    else
    {
      i = 0;
      sNode[0] = 0;
      collectCharacters(sNode, i);
      if (strcmp(sString, sNode) == 0)
      {
        // We can begin to find next:
        iFlag = 1;                                           // Signal that the next one is it.
        for (i = _iMinChar; i <= _iMaxChar; i++)
        {
          if (_childArray[i] != NULL)
          {
            if (iFlag != 2)
            {
              nextNode = _childArray[i]->preOrderNextNode(sString, iFlag);
            }
          }
        }
      }
      else
      {
        // We continue preorder traversal:
        for (i = _iMinChar; i <= _iMaxChar; i++)
        {
          if (_childArray[i] != NULL)
          {
            if (iFlag != 2)
            {
              nextNode = _childArray[i]->preOrderNextNode(sString, iFlag);
            }
          }
        }
      }
    }
  }
  else
  {
    // We continue preorder traversal:
    for (i = _iMinChar; i <= _iMaxChar; i++)
    {
      if (_childArray[i] != NULL)
      {
        if (iFlag != 2)
        {
          nextNode = _childArray[i]->preOrderNextNode(sString, iFlag);
        }
      }
    }
  }
  return nextNode;
}

// Recursively search the tree to find the next (breadth first) integer keyed object in the tree:
template <class Item>
StringTreeNode<Item>* StringTreeNode<Item>::nextNode(int iKey)         // Call this function from the root.
{
  StringTreeNode<Item>* nextNode = NULL;
  StringTreeNode<Item>* stn = NULL;
  int i = 0;
  Queue<StringTreeNode<Item>*> q;
  char* sString = new char[80];                                        // For collectCharacters().
  int iTempKey = 0;
    
  stn = findNode(iKey);

  if (stn != NULL)
  {
    // See if the next node is in my parent's array (my sibling to my right):
    if (stn->_parent != NULL)
    {
      for (i = (int) stn->_cDigit + 1; i <= stn->_iMaxChar; i++)
      {
        if (stn->_parent->_childArray[i] != NULL)
        {
          // We have found the next object in the tree.
          nextNode = stn->_parent->_childArray[i];
          break;                                                       // Break out of for().
        }
      }
    }

    // If not, search the whole tree breadth first for it:
    if (nextNode == NULL)
    {
      // Fill a queue with nodes breadth first up until iKey:
      q.push(this);

      //Visit the next in the queue:
      while (!q.empty())
      {
        stn = q.pop();

        // Push the children into the queue:
        for (i = stn->getMinChar(); i <= stn->getMaxChar(); i++)
        {
          if (stn->getChild(i) != NULL)
          {
            q.push(stn->getChild(i));
          }
        }

        i = 0;
        sString[0] = 0;
        stn->collectCharacters(sString, i);
        iTempKey = atoi(sString);
        if (iTempKey == iKey)
        {
          // We have found the next.
          break;                                                       // Break out of while.
        }
      }

      // Then continue the search until the next key node is found:
      while (!q.empty())
      {
        stn = q.pop();

        // Push the children into the queue:
        for (i = stn->getMinChar(); i <= stn->getMaxChar(); i++)
        {
          if (stn->getChild(i) != NULL)
          {
            q.push(stn->getChild(i));
          }
        }

        if (stn->_lastCharacter)
        {
          // We have found the next key node.
          nextNode = stn;
          break;                                                       // Break out of while.
        }
      }
    }
  }

  delete [] sString;
  return nextNode;
}

template <class Item>
StringTreeNode<Item>* StringTreeNode<Item>::getChild(int i)            // Accessor.
{
  return _childArray[i];
}

template <class Item>
int StringTreeNode<Item>::lastCharacter()                              // Accessor.
{
  return _lastCharacter;
}

template <class Item>
Queue<Item*>* StringTreeNode<Item>::getDataObjectQueue()               // Accessor.
{
  return _dataObjectQueue;
}

template <class Item>
int StringTreeNode<Item>::getMinChar()                                 // Accessor.
{
  return _iMinChar;
}

template <class Item>
int StringTreeNode<Item>::getMaxChar()                                 // Accessor.
{
  return _iMaxChar;
}

// * * * StringTreeNode non-member functions: * * *

// Print all the objects breadth-first:
template <class Item>
void breadthFirstPrint(Item stn)                                       // Start at STN root.
{
  int i = 0;
  Queue<Item> q;

  q.push(stn);

  //Visit the next in the queue:
  while (!q.empty())
  {
    stn = q.pop();

    // Print the objects stored at the node;
    if (stn->lastCharacter()) stn->printObjects();

    // Push the children into the queue:
    for (i = stn->getMinChar(); i <= stn->getMaxChar(); i++)
    {
      if (stn->getChild(i) != NULL)
      {
        q.push(stn->getChild(i));
      }
    }
  }
}

// Friend of StringTreeNode to put all the objects in an array (call passign the root):
template<class Item>
void breadthFirstStore(Item* array[], StringTreeNode<Item>* stn)
{                                                    // Converting this to a friend function gave
  int i = 0;                                         // only a 10% speedup.
  int n = 0;
  Queue<StringTreeNode<Item>*> q;                    // Queue for breadth-first traversal.

  q.push(stn);                                       // Initialize search with the root.

  //Visit the next in the queue:
  while (!q.empty())
  {
    stn = q.pop();

    // Process the objects stored at the node:
    if (stn->lastCharacter())
    {
      for (i = 1; i <= stn->_dataObjectQueue->size(); i++)
      //while (!stn->_dataObjectQueue->empty())
      {
        array[n] = stn->_dataObjectQueue->peek(i);
        n++;
      }
    }

    // Push the children into the queue:
    for (i = stn->_iMinChar; i <= stn->_iMaxChar; i++)
    {
      if (stn->_childArray[i] != NULL)
      {
        q.push(stn->_childArray[i]);
      }
    }
  }
}

template <class Item>
void saveObjectsBreadthFirst(ofstream outfile, Item stn)
{
  int i = 0;
  Queue<Item> q;

  q.push(stn);

  //Visit the next in the queue:
  while (!q.empty())
  {
    stn = q.pop();

    // Print the string;
    if (stn->lastCharacter()) stn->writeObject(outfile);

    // Push the children into the queue:
    for (i = stn->getMinChar(); i <= stn->getMaxChar(); i++)
    {
      if (stn->getChild(i) != NULL)
      {
        q.push(stn->getChild(i));
      }
    }
  }
}

// * * ListNode class implementations * *

// Default constructor:
template <class Item>
ListNode<Item>::ListNode()
{
  _data = NULL;
  _next = NULL;
}

// Parameter constructor:
template <class Item>
ListNode<Item>::ListNode(Item data, ListNode<Item>* next)
{
  _data = data;
  _next = next;
}

// Accessors:
template <class Item>
ListNode<Item>* ListNode<Item>::getNext()
{
  return _next;
}

template <class Item>
Item ListNode<Item>::getData()
{
  return _data;
}

template <class Item>
ListNode<Item>* ListNode<Item>::insertAfter(Item entry)
{
  _next = new ListNode<Item>(entry, _next);
  return _next;
}

template <class Item>
void ListNode<Item>::setNext(ListNode<Item>* next)
{
  _next = next;
}

// Nonmember functions:
template <class Item>
void insertBeforeHead(ListNode<Item>*& head, Item entry)
{
  head = new ListNode<Item>(entry, head);
}

template <class Item>
void deleteHead(ListNode<Item>*& head)
{
  ListNode<Item>* temp = head;
  head = head->getNext();
  delete temp;
}

// * * Queue implementation: * * 

// Constructor:
template <class Item>
Queue<Item>::Queue()
{
  _iNumInQueue = 0;
  _front = NULL;
  _rear = NULL;
}

template <class Item>
Item Queue<Item>::pop()                          // Pop from front.
{
  Item data = NULL;

  if (!empty())
  {
    data = _front->getData();
    deleteHead(_front);
    _iNumInQueue--;
  }
  return data;
}

template <class Item>
void Queue<Item>::push(Item data)                // Push from rear.
{
  if (empty())
  {
    insertBeforeHead(_front, data);
    _rear = _front;
  }
  else
  {
    _rear = _rear->insertAfter(data);
  }
  _iNumInQueue++;
}

template <class Item>
Item Queue<Item>::peek(int n)                    // Peek at the nth item.
{                                                // Front item is 1.
  Item data = NULL;
  int i = 0;
  ListNode<Item>* cursor = _front;

  if (_iNumInQueue > 0)
  {
    if (_iNumInQueue >= n)
    {
      for (i = 1; i < n; i++)
      {
        cursor = cursor->getNext();
      }
    }
  }
  data = cursor->getData();

  return data;
}

template <class Item>
ListNode<Item>* Queue<Item>::getFront()
{
  return _front;
}

// * * Stack implementation: * * 

// Constructor:
template <class Item>
Stack<Item>::Stack()
{
  _iNumInStack = 0;
  _top = NULL;
}

// Remove and return the top item.
template <class Item>
Item Stack<Item>::pop()
{
  Item data = NULL;
  if (!empty())
  {
    data = _top->getData();
    deleteHead(_top);
    _iNumInStack--;
  }
  return data;
}

// Push item onto the stack.
template <class Item>
void Stack<Item>::push(Item data)
{
    insertBeforeHead(_top, data);
    _iNumInStack++;
}

#endif