// Bst.h
// 	A binary search tree that will contain
// 	all dictionary Pairs
//	These will be ordered on plaintext strings
//	but each word or expression will be associated
//	with its 4-digit code translation

#ifndef BST_CLASS
#define BST_CLASS

#include <string>
#include "ModNode.h"
#include "myExceptions.h"

template <class T>
class Bst {
  protected:
    ModNode<T> * root;

  public:
    // default constructor
    // initializes root to NULL
    Bst();

    // constructor with Pair and pointers left and right
    Bst(T p, ModNode<T> * par, ModNode<T> * lt, ModNode<T> * rt);

    // copy constructor
    // makes a copy of "other"
    // calls copy()
    Bst(const Bst & other);

    // destructor
    // calls makeEmpty()
    virtual ~Bst();

    // explicitly defined assignment operator
    Bst & operator=(const Bst &);

    // returns a pointer to the root 
    ModNode<T> * getRootPointer();

    // returns true if target is a plaintext word in Bst
    bool exists(std::string target);

    // reads the text file, "codebook.txt"
    // creates a Pair for each text and code
    // creates a ModNode pointer to the pair
    // the argument is the name of the text file
    // throws an ReadEmptyFile() exception if the file 
    // does not exist or is empty
    // reads until EOF
    void reader(const char *);

    // searches for ModNode Pair containing X,
    // curr points to ModNode Pair containing plaintext X
    // parent points to the curr's parent
    // can be used to add a Pair to the tree
    // returns true if found, otherwise, returns false
    // this is non-recursive
    bool search(std::string X,ModNode<T> *& curr);

    // searches for ModNode Pair containing X,
    // child points to ModNode Pair containing plaintext X
    // parent points to the child's parent
    // returns true if found, otherwise, returns false
    // THIS FUNCTION IS RECURSIVE
    bool locate(std::string word,ModNode<T> *& child);

    // adds the Pair if it is not already in the tree
    // this is the same as a function that inserts
    // a pair into the tree
    // returns true if ModNode containing Pair is inserted
    // otherwise it returns false
    bool add(T);

    // deletes the MODNODE containing 'target' from the tree
    // you must use one of the methods we have 
    // provided in class : right subtree successor,
    // left subtree predecessor, easy right pullup or
    // easy left pullup
    // this does NOT remove data from codebook.txt,
    // it only deletes a ModNode in the tree
    // returns true if ModNode containing target is erased
    bool erase(std::string target);

    // finds the parent of the ModNode child
    // returns true if parent is found
    // otherwise returns false
    bool findParent(ModNode<T> *& parent, ModNode<T> * child);

    // takes a string containing plaintext and code
    // and creates a pair, putting plaintext in
    // the first portion of the pair and
    // putting the 4-digit code in the 2nd
    // portion of the pair
    T makePair(std::string str);

    // prints the nodes as they are visited in
    // a preorder traversal of the tree
    // may call helper function
    void preorder();

    // prints the nodes as they are visited in
    // an inorder traversal of the tree
    // may call helper function
    void inorder();

    // prints the nodes as they are visited in
    // a postorder traversal of the tree
    // may call helper function
    void postorder();

    // prints the BST in alphabetical order
    // SAME AS AN INORDER TRAVERSAL
    // MUST BE RECURSIVE
    void print();

    // deletes all nodes in the tree
    // function calling this sets root to NULL
    // MUST BE RECURSIVE
    // called from destructor
    void makeEmpty(ModNode<T> *& curr);

    // for testing findMax() and findMin()
    // prints the pair that p points to
    // prints word/expression followed by 
    // a single space followed by 4-digit code
    // followed by a newline
    void printPair(ModNode<T> * p);

    // finds ModNode with largest word in the tree/subtree 
    // t initially points to a tree or subtree
    // t will be pointing to the biggest node
    // in that tree or subtree when it is finished executing
    void findMax(ModNode<T> *& t);

    // finds ModNode with smallest word in the tree/subtree 
    // t initially points to a tree or subtree
    // t will be pointing to the smallest node
    // in that tree or subtree when it is finished executing
    void findMin(ModNode<T> *&);

  private:
    // makes a copy of "other" (a bst)
    // the copy will be in "curr"
    // this is a deep copy so when you 
    // have copied the bst pointed to by other
    // then you delete "other", "curr" should still
    // look like the original "other" bst
    void copy(ModNode<T> *& curr,ModNode<T> * other);

    // YOU MAY WRITE ANY OTHER PRIVATE METHODS THAT YOU NEED

};

#endif // BST_CLASS