// 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 "Node.h"
#include "myExceptions.h"

class Bst {
  private:
    Node * root;

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

    // constructor with Pair and pointers left and right
    Bst(Pair, Node *, Node *);

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

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

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

    // returns a pointer to the root 
    Node * 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 Node 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 Node Pair containing X,
    // curr points to Node 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, Node *& parent, Node *& curr);

    // searches for Node Pair containing X,
    // child points to Node 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, Node *& parent, Node *& 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 node containing Pair was inserted
    // otherwise it returns false
    bool add(Pair);

    // deletes the NODE 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
    // returns true if node containing target is erased
    bool erase(std::string target);

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

    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 BST in alphabetical order
    // SAME AS AN INORDER TRAVERSAL
    // 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(Node * curr);

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

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

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

  private:
    // makes a copy of "other" (an existing 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(Node *& curr,Node * other);

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

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

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

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

};

#endif // BST_CLASS