// ModBst.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
// 	ADDITIONALLY, this BST has an extra pointer 
// 	to the Node's parent

#ifndef MODIFIEDBST_CLASS
#define MODIFIEDBST_CLASS

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

class ModBst {
  private:
    ModNode * root;

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

    // constructor with Pair q and pointers parent, left and right
    ModBst(Pair q, ModNode *p, ModNode *l, ModNode *r);

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

    // destructor
    // calls makeEmpty()
    ~ModBst();

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

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

    // returns true if target is a plaintext word in ModifiedBst
    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
    // 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 *& curr);

    // searches for ModNode Pair containing X,
    // curr points to ModNode Pair containing plaintext X
    // returns true if found, otherwise, returns false
    // THIS FUNCTION IS RECURSIVE
    bool locate(std::string word,ModNode *& curr);

    // 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
    bool add(Pair);

    // 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 node in the tree
    bool erase(std::string target);

    Pair makePair(std::string str);

    // does a preorder traversal of the tree
    // may call helper function
    void preorder();

    // does an inorder traversal of the tree
    // may call helper function
    void inorder();

    // does a postorder traversal of the tree
    // may call helper function
    void postorder();

    // prints the ModifiedBST in alphabetical order
    // MUST BE RECURSIVE
    void print();

    // deletes all nodes in the tree
    // function that calls this sets root to NULL
    // MUST BE RECURSIVE
    // called from destructor
    void makeEmpty(ModNode * curr);

    // for testing findMax() and findMin()
    void printPair(ModNode *);

    // finds ModNode with largest word in the tree/subtree 
    void findMax(ModNode *&);

    // finds Node with smallest word in the tree/subtree 
    void findMin(ModNode *&);

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

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

    // my recursive print helper
    void printHelper(ModNode *);

    // helper for inorder()
    void helpInorder(ModNode *); 

    // helper for preorder()
    void helpPreorder(ModNode *);
 
    // helper for postorder()
    void helpPostorder(ModNode *); 

};

#endif // MODIFIEDBST_CLASS