// BstIterator.h
//      iterator traverses a ModifiedBst in alphabetical order, low to high
//	it can move in either direction so if it is on a ModNode containing
//	"we" it could walk to the next smallest node "wax" or the next
//	largest node "wee"

#ifndef BSTITERATOR_CLASS
#define BSTITERATOR_CLASS

#include <iostream>
#include <string>
#include "Bst.h"
#include "ModNode.h"

template <class T>
class BstIterator {
  private:
    ModNode<T> * curr;   // points to current Modnode

  public:
    // constructor for the iterator
    BstIterator(ModNode<T> * currIn = NULL);

    // returns the current object
    const ModNode<T> * operator->() const;

    // returns curr's data (a Pair)
    const Pair operator*() const;

    // pre-increment operator
    BstIterator & operator++();

    // post-increment operator
    BstIterator operator++(int);

    // pre-decrement operator
    BstIterator & operator--();

    // post-decrement operator
    BstIterator operator--(int);

    // equality operator
    bool operator==(const BstIterator & other);

    // inequality operator
    bool operator!=(const BstIterator & other);

    // like begin()
    void setToFirstNode();

    // link end()
    void setToLastNode();

  private:

    // YOU MAY PLACE ANY FUNCTIONS HERE THAT YOU WISH
    // helper functions

    // you may ignore or change this function
    // it finds the node immediately succeeding curr called succ
    void findNext(std::string word,ModNode<T> * curr,ModNode<T> *& succ);

    // you may ignore or change this function
    // it finds the node immediately preceding curr called prev
    void findPrev(std::string word,ModNode<T> * curr,ModNode<T> *& prev);
};

#endif //BSTITERATOR_CLASS