// Attaching nodes to the tree does so in ascending order. Therefore,
// operator < and operator == must be defined for the class being stored.

#ifndef _GENERALTREE_
#define _GENERALTREE_
#include <queue>
#include <string>
#include "TreeException.h"
#include "TreeNode.h" // contains definitions for TreeNode
           // and TreeItemType


template <class TreeItemType>
class GeneralTree
{
public:
// constructors and destructor:
  typedef void (*FunctionType)(TreeItemType& anItem);
  GeneralTree();
  GeneralTree(const TreeItemType& rootItem);
  GeneralTree(const TreeItemType& rootItem,
       GeneralTree& childTree,
       GeneralTree& siblingTree);
  GeneralTree(const GeneralTree& tree);
  virtual ~GeneralTree();

// general tree operations:
  virtual bool isEmpty() const;
  virtual TreeItemType rootData() const
   throw(TreeException);
  virtual void setRootData(const TreeItemType& newItem)
   throw (TreeException);
  virtual void attachChild(const TreeItemType& newItem)
   throw(TreeException); // attaches a child to the root
  virtual void attachChildSubtree(GeneralTree& childTree)
   throw(TreeException); // attaches a general tree to the root
  virtual void attachChild(TreeNode<TreeItemType>* subTree,const TreeItemType& newItem)
   throw(TreeException); // attaches a child to a subTree within the general tree
  virtual void attachChildSubtree(TreeNode<TreeItemType>* subTree,GeneralTree& childTree)
   throw(TreeException); // attaches a general tree to a subTree within general tree
  virtual bool retrieveChild(TreeNode<TreeItemType>* subTree, TreeItemType& item) const
   throw(TreeException); // returns item if found from the subtree's children
  virtual void deleteChild(const TreeItemType& searchKey)
   throw(TreeException); // deletes a child from the root, must be a leaf
  virtual void deleteChild(TreeNode<TreeItemType>* subTree,const TreeItemType& searchKey)
   throw(TreeException); // deletes a child from a subTree, must be a leaf
  virtual void detachChildSubTree(const TreeItemType& searchKey,GeneralTree& subTree)
   throw(TreeException); // child at searchKey detached and returned in subTree
  virtual GeneralTree childSubtree(const TreeItemType& searchKey) const;
   // return a copy of the subtree with searchKey at the root
  virtual void preorderTraverse(FunctionType visit);
  virtual void inorderTraverse(FunctionType visit);
  virtual void postorderTraverse(FunctionType visit);
  virtual void breadthFirstTraversal(FunctionType visit);

// overloaded operator:
  virtual GeneralTree& operator=(const GeneralTree& rhs);

protected:
  GeneralTree(TreeNode<TreeItemType> *nodePtr); // constructor
  void copyTree(TreeNode<TreeItemType> *treePtr,
     TreeNode<TreeItemType>* & newTreePtr) const throw (TreeException);
  // Copies the tree rooted at treePtr into a tree rooted
  // at newTreePtr. Throws TreeException if a copy of the
  // tree cannot be allocated.

  void destroyTree(TreeNode<TreeItemType> * &treePtr);
  // Deallocates memory for a tree.
  // The next two functions retrieve and set the value
  // of the private data member root.

  TreeNode<TreeItemType> *rootPtr() const;
  void setRootPtr(TreeNode<TreeItemType> *newRoot);

  // The next two functions retrieve and set the values
  // of the child and sibling child pointers of a tree node.
  void getChildPtrs(TreeNode<TreeItemType> *nodePtr,
           TreeNode<TreeItemType> * &ChildPtr,
           TreeNode<TreeItemType> * &SiblingPtr) const;
  void setChildPtrs(TreeNode<TreeItemType> *nodePtr,
           TreeNode<TreeItemType> *ChildPtr,
           TreeNode<TreeItemType> *SiblingPtr);

  void preorder(TreeNode<TreeItemType> *treePtr, FunctionType visit);
  void inorder(TreeNode<TreeItemType> *treePtr, FunctionType visit);
  void postorder(TreeNode<TreeItemType> *treePtr, FunctionType visit);

private:
  TreeNode<TreeItemType> *root; // pointer to root of tree
}; // end class
#include "GeneralTree.cpp"
// End of header file.

#endif

#include "GeneralTree.h" // header file
#include <string>
#include <cstddef> // definition of NULL
#include <cassert> // for assert()

template <class TreeItemType>
GeneralTree<TreeItemType>::GeneralTree() : root(NULL)
{
} // end default constructor

template <class TreeItemType>
GeneralTree<TreeItemType>::GeneralTree(const TreeItemType& rootItem)
{
  root = new TreeNode<TreeItemType>(rootItem, NULL, NULL);
  assert(root != NULL);
} // end constructor

template <class TreeItemType>
GeneralTree<TreeItemType>::GeneralTree(const TreeItemType& rootItem,
            GeneralTree& childTree,
            GeneralTree& siblingTree)
{
  root = new TreeNode<TreeItemType>(rootItem, NULL, NULL);
  assert(root != NULL);

  attachChildSubtree(childTree);
  attachSiblingSubtree(siblingTree);
} // end constructor

template <class TreeItemType>
GeneralTree<TreeItemType>::GeneralTree(const GeneralTree& tree)
{
  copyTree(tree.root, root);
} // end copy constructor

template <class TreeItemType>
GeneralTree<TreeItemType>::GeneralTree(TreeNode<TreeItemType> *nodePtr)
           : root(nodePtr)
{
} // end protected constructor

template <class TreeItemType>
GeneralTree<TreeItemType>::~GeneralTree()
{
  destroyTree(root);
} // end destructor

template <class TreeItemType>
bool GeneralTree<TreeItemType>::isEmpty() const
{
  return (root == NULL);
} // end isEmpty

template <class TreeItemType>
TreeItemType GeneralTree<TreeItemType>::rootData() const
             throw (TreeException)
{
  if (isEmpty())
   throw TreeException("TreeException: Empty tree");
  return root->item;
} // end rootData

template <class TreeItemType>
void GeneralTree<TreeItemType>::setRootData(const TreeItemType& newItem)
             throw (TreeException)
{
  if (!isEmpty())
   root->item = newItem;
  else
  { root = new TreeNode<TreeItemType>(newItem, NULL, NULL);
   if (root == NULL)
     throw TreeException(
      "TreeException: Cannot allocate memory");
  } // end if
} // end setRootData

template <class TreeItemType>
void GeneralTree<TreeItemType>::attachChild(const TreeItemType& newItem)
             throw (TreeException)
{
  if (isEmpty())
    throw TreeException("TreeException: Empty tree");
  TreeNode<TreeItemType>* newNode = new TreeNode<TreeItemType>(newItem);
  TreeNode<TreeItemType>* p = root->ChildPtr;
  TreeNode<TreeItemType>* q = NULL;
  while (p!=NULL && p->item < newItem)
  {
    q=p;
    p=p->SiblingPtr;
  }
  if (p!=NULL && p->item == newItem)
    throw TreeException("TreeException: Duplicate entry");
  if (q==NULL)
  {
    root->ChildPtr=newNode;
  }
  else
  {
    q->SiblingPtr = newNode;
  }

  newNode->SiblingPtr = p;

} // end attachChild


template <class TreeItemType>
void GeneralTree<TreeItemType>::attachChildSubtree(GeneralTree& childTree)
             throw (TreeException)
{
  if (isEmpty())
    throw TreeException("TreeException: Empty tree");
  TreeNode<TreeItemType>* p = root->ChildPtr;
  TreeNode<TreeItemType>* q = NULL;
  while (p!=NULL && p->item < childTree.root->item)
  {
    q=p;
    p=p->SiblingPtr;
  }
  if (p!=NULL && p->item == childTree.rootPtr()->item)
    throw TreeException("TreeException: Duplicate entry");
  if (q==NULL)
  {
    root->ChildPtr = childTree.root;
  }
  else
  {
    q->SiblingPtr = childTree.root;
  }

  childTree.root->SiblingPtr = p;
} // end attachChildSubtree

template <class TreeItemType>
void GeneralTree<TreeItemType>::attachChild(TreeNode<TreeItemType>* subTreePtr,
                      const TreeItemType& newItem)
             throw (TreeException)
{
  if (subTreePtr == NULL)
    throw TreeException("TreeException: non-existant node in attachChild");
  TreeNode<TreeItemType>* newNode = new TreeNode<TreeItemType>(newItem);
  TreeNode<TreeItemType>* p = subTreePtr->ChildPtr;
  TreeNode<TreeItemType>* q = NULL;
  while (p!=NULL && p->item < newItem)
  {
    q=p;
    p=p->SiblingPtr;
  }
  if (p!=NULL && p->item == newItem)
    throw TreeException("TreeException: Duplicate entry");
  if (q==NULL)
  {
    subTreePtr->ChildPtr=newNode;
  }
  else
  {
    q->SiblingPtr = newNode;
  }

  newNode->SiblingPtr = p;

} // end attachChild


template <class TreeItemType>
void GeneralTree<TreeItemType>::attachChildSubtree(TreeNode<TreeItemType>* subTreePtr,
                          GeneralTree& childTree)
             throw (TreeException)
{
  if (subTreePtr == NULL)
    throw TreeException("TreeException: non-existant node in attachChildSubtree");
  TreeNode<TreeItemType>* p = subTreePtr->ChildPtr;
  TreeNode<TreeItemType>* q = NULL;
  while (p!=NULL && childTree.root->item > p->item)
  while (p!=NULL && p->item < childTree.root->item)
  {
    q=p;
    p=p->SiblingPtr;
  }
  if (p!=NULL && p->item == childTree.rootPtr()->item)
    throw TreeException("TreeException: Duplicate entry");
  if (q==NULL)
  {
    subTreePtr->ChildPtr = childTree.root;
  }
  else
  {
    q->SiblingPtr = childTree.root;
  }

  childTree.root->SiblingPtr = p;
} // end attachChildSubtree

template <class TreeItemType>
bool GeneralTree<TreeItemType>::retrieveChild(TreeNode<TreeItemType>* subTree,
                       TreeItemType& item) const
   throw(TreeException)
{
  if (subTree == NULL)
    throw TreeException("TreeException: Empty tree");
  TreeNode<TreeItemType>* p = subTree->ChildPtr;
  bool found=false;
  while (p!=NULL && !found)
    if (p->item == item)
      found=true;
    else
      p = p->SiblingPtr;
  if (found)
    item = p->item;
  return found;
}

template <class TreeItemType>
void GeneralTree<TreeItemType>::deleteChild(const TreeItemType& searchKey)
             throw (TreeException)
{

  if (isEmpty())
    throw TreeException("TreeException: Empty tree");
  else
  {
    TreeNode<TreeItemType>* p = root->ChildPtr;
    TreeNode<TreeItemType>* q = NULL;
    bool found=false;
    while (!found && p!=NULL && p->item <= searchKey)
    {
      if (p->item == searchKey)
        found = true;
      else
      {
        q=p;
        p=p->SiblingPtr;
      }
    }
    if (found)
    {
      if (p->ChildPtr)
        throw TreeException("TreeException: child to delete has children");
      if (q==NULL)
        root->ChildPtr = p->SiblingPtr;
      else
        q->SiblingPtr = p->SiblingPtr;
      delete p;
    }
    else
      throw TreeException("TreeException: child does not exist in deleteChild");
  } // end if
} // end detachChildSubtree

template <class TreeItemType>
void GeneralTree<TreeItemType>::deleteChild(TreeNode<TreeItemType>* subTreePtr,
                      const TreeItemType& searchKey)
             throw (TreeException)
{

  if (isEmpty())
    throw TreeException("TreeException: Empty tree");
  else
  {
    TreeNode<TreeItemType>* p = subTreePtr->ChildPtr;
    TreeNode<TreeItemType>* q = NULL;
    bool found=false;
    while (!found && p!=NULL && p->item <= searchKey)
    {
      if (p->item == searchKey)
        found = true;
      else
      {
        q=p;
        p=p->SiblingPtr;
      }
    }
    if (found)
    {
      if (p->ChildPtr)
        throw TreeException("child to delete has children");
      if (q==NULL)
        subTreePtr->ChildPtr = p->SiblingPtr;
      else
        q->SiblingPtr = p->SiblingPtr;
      delete p;
    }
    else
      throw TreeException("TreeException: child does not exist in deleteChild");
  } // end if
} // end detachChildSubtree

template <class TreeItemType>
void GeneralTree<TreeItemType>::detachChildSubTree(const TreeItemType& searchKey,GeneralTree& tree)
   throw(TreeException) // child at searchKey detached and returned in tree
{
  if (isEmpty())
    throw TreeException("TreeException: Empty tree");
  else
  {
    TreeNode<TreeItemType>* p = root->ChildPtr;
    TreeNode<TreeItemType>* q = NULL;
    bool found=false;
    while (!found && p!=NULL && p->item <= searchKey)
    {
      if (p->item == searchKey)
        found = true;
      else
      {
        q=p;
        p=p->SiblingPtr;
      }
    }
    if (found)
    {
      tree.root = p;
      if (q==NULL)
        root->ChildPtr = p->SiblingPtr;
      else
        q->SiblingPtr = p->SiblingPtr;
    }
    else
      throw TreeException("TreeException: ChildSubTree does not exist");
  } // end if
}

template <class TreeItemType>
GeneralTree<TreeItemType> GeneralTree<TreeItemType>::childSubtree(const TreeItemType& searchKey) const
{
  TreeNode<TreeItemType> *subTreePtr = root->ChildPtr;
  while (subTreePtr != NULL && subTreePtr->item != searchKey)
   subTreePtr = subTreePtr->SiblingPtr;
  if (subTreePtr == NULL)
   return GeneralTree();
  else
  {
    TreeNode<TreeItemType> *p = new TreeNode<TreeItemType>(subTreePtr->item,NULL,NULL);
   copyTree(subTreePtr->ChildPtr, p->ChildPtr);
   return GeneralTree(p);
  } // end if
} // end childSubtree

template <class TreeItemType>
void GeneralTree<TreeItemType>::preorderTraverse(FunctionType visit)
{
  preorder(root, visit);
} // end preorderTraverse

template <class TreeItemType>
void GeneralTree<TreeItemType>::inorderTraverse(FunctionType visit)
{
  inorder(root, visit);
} // end inorderTraverse

template <class TreeItemType>
void GeneralTree<TreeItemType>::postorderTraverse(FunctionType visit)
{
  postorder(root, visit);
} // end postorderTraverse

template <class TreeItemType>
GeneralTree<TreeItemType>& GeneralTree<TreeItemType>::operator=(const GeneralTree& rhs)
{
  if (this != &rhs)
  { destroyTree(root); // deallocate child-hand side
   copyTree(rhs.root, root); // copy sibling-hand side
  } // end if
  return *this;
} // end operator=

template <class TreeItemType>
void GeneralTree<TreeItemType>::copyTree(TreeNode<TreeItemType> *treePtr,
             TreeNode<TreeItemType> *& newTreePtr) const
             throw (TreeException)
{
  // preorder traversal
  if (treePtr != NULL)
  { // copy node
   newTreePtr = new TreeNode<TreeItemType>(treePtr->item, NULL, NULL);
   if (newTreePtr == NULL)
     throw TreeException(
      "TreeException: Cannot allocate memory");

   copyTree(treePtr->ChildPtr, newTreePtr->ChildPtr);
   copyTree(treePtr->SiblingPtr, newTreePtr->SiblingPtr);
  }
  else
   newTreePtr = NULL; // copy empty tree
} // end copyTree

template <class TreeItemType>
void GeneralTree<TreeItemType>::destroyTree(TreeNode<TreeItemType> *& treePtr)
{
  // postorder traversal
  if (treePtr != NULL)
  { destroyTree(treePtr->ChildPtr);
   destroyTree(treePtr->SiblingPtr);
   delete treePtr;
   treePtr = NULL;
  } // end if
} // end destroyTree

template <class TreeItemType>
TreeNode<TreeItemType> *GeneralTree<TreeItemType>::rootPtr() const
{
 return root;
} // end rootPtr

template <class TreeItemType>
void GeneralTree<TreeItemType>::setRootPtr(TreeNode<TreeItemType> *newRoot)
{
  root = newRoot;
} // end setRoot

template <class TreeItemType>
void GeneralTree<TreeItemType>::getChildPtrs(TreeNode<TreeItemType> *nodePtr,
               TreeNode<TreeItemType> *& childPtr,
               TreeNode<TreeItemType> *& siblingPtr) const
{
  childPtr = nodePtr->ChildPtr;
  siblingPtr = nodePtr->SiblingPtr;
} // end getChildPtrs

template <class TreeItemType>
void GeneralTree<TreeItemType>::setChildPtrs(TreeNode<TreeItemType> *nodePtr,
               TreeNode<TreeItemType> *childPtr,
               TreeNode<TreeItemType> *siblingPtr)
{
  nodePtr->ChildPtr = childPtr;
  nodePtr->SiblingPtr = siblingPtr;
} // end setChildPtrs

template <class TreeItemType>
void GeneralTree<TreeItemType>::preorder(TreeNode<TreeItemType> *treePtr,
             FunctionType visit)
{
  if (treePtr != NULL)
  {
   visit(treePtr->item);
   preorder(treePtr->ChildPtr, visit);
   preorder(treePtr->SiblingPtr, visit);
  } // end if
} // end preorder

template <class TreeItemType>
void GeneralTree<TreeItemType>::inorder(TreeNode<TreeItemType> *treePtr,
             FunctionType visit)
{
  if (treePtr != NULL)
  { inorder(treePtr->ChildPtr, visit);
   visit(treePtr->item);
   inorder(treePtr->SiblingPtr, visit);
  } // end if
} // end inorder

template <class TreeItemType>
void GeneralTree<TreeItemType>::postorder(TreeNode<TreeItemType> *treePtr,
              FunctionType visit)
{
  if (treePtr != NULL)
  {
   postorder(treePtr->ChildPtr, visit);
   postorder(treePtr->SiblingPtr, visit);
   visit(treePtr->item);
  } // end if
} // end postorder
// End of implementation file.

template <class T>
void GeneralTree<T>::breadthFirstTraversal(FunctionType visit)
{
  queue<TreeNode<T>*> q;
  TreeNode<T>* p = root;
  while ( !(p==NULL && q.empty()) )
  {
    while (p!=NULL)
    {
      visit(p->item);
      q.push(p);
      p = p->SiblingPtr;
    }
    p=q.front();
    q.pop();
    p=p->ChildPtr;
  }
}

#ifndef _TREENODE_
#define _TREENODE_
#include <string>
template <class TreeItemType>
class GeneralTree;

template <class TreeItemType>
class TreeNode // node in the tree
{
  private:
    TreeNode() {};
    TreeNode(const TreeItemType& nodeItem,
        TreeNode *child = NULL,
        TreeNode *sibling = NULL)
        : item(nodeItem),ChildPtr(child),
         SiblingPtr(sibling) {}

    TreeItemType item;    // data portion
    TreeNode *ChildPtr; // pointer to child child
    TreeNode *SiblingPtr; // pointer to sibling child
    friend class GeneralTree<TreeItemType>;
    friend class DirectoryTree;
}; // end TreeNode class
#endif

// ********************************************************
// Header file TreeException.h for the ADT binary tree.
// ********************************************************
#include <stdexcept>
#include <string>
using namespace std;

class TreeException: public logic_error
{
public:
  TreeException(const string & message = "")
            : logic_error(message.c_str())
  { }
}; // end TreeException

#include "GeneralTree.h"
#include <iostream>
#include <string>

using namespace std;

int main()
{
    DirectoryTree<string> dir;
    dir.setRootData("kjorsvik");
    cout << dir.rootData() << " > "
    string input;
    while (input != "exit")
    {
        switch(input)
        {
            case ls:
                // List First Child of current dir and all siblings of first child

                break;

            case cd:
                // move cur directory pointer to specified dir. if dir doesnt exist throw exception
                // if .. move to parent dir if at root throw exception

                break;

            case mkdir:
                // make child node of dir type if already exists throw exception

                break;

            case rmdir:
                // delete specified dir node that has no children nodes. if had children nodes throw exception
                // if doesnt exist throw exception

                break;

            case pico:
                // Create node of file type. if already exists as a directory or file throw excpetion

                break;

            case rm:
                // remove file type node unless it doesnt exist then throw exception

                break;

            default:
                // throw exception of "Unknown command!"
                cout << "invalid command" << endl;
                break;
        }
        // cout << directory currently in with parents behind << " > "
        cin >> input;
    }
    return 0;
}

#include <string>
#include <stack> // STL stack

// note, DirectoryTree is not a template
// GeneralTree is templated and stores Entry (a file or directory)
// private inheritance is used, DirectoryTree As-A GeneralTree
class DirectoryTree : private GeneralTree<Entry>
{
  public:

  protected:

  private:
    TreeNode<Entry>* curDir; // pointer to current directory
    stack<TreeNode<Entry>*> DirPointers; // save curDir pointers when
                       // changing directories
    string prompt; // current prompt to be displayed
};