// Vector.h
//	a non-circular, singly linked list of Nodes
// 	mimics the STL vector class
//	includes random access into the data structure
//	dynamically resizes
// 	uses iterators to move through the data structure

#ifndef VECTOR_CLASS
#define VECTOR_CLASS

#include "Node.h"
#include "Iterator.h"

class Vector {
  private:
    unsigned count;	// the number of actual items in the sll
    Node * head;	// points to the first node
    Node * tail;	// points to the last node (ie the
			// one before the dummy node

  public:
    // default constructor
    // creates empty linked list of count = 0
    Vector();

    // copy constructor for vector
    // creates a deep copy, of the ll,
    // and stores it in other
    // calls copy()
    Vector(const Vector & other);

    // destructor 
    // calls clear();
    ~Vector();

    // overloaded assignment operator
    // calls copy()
    Vector & operator=(const Vector & original);

    // accessor
    // returns the head
    Node * getHead();

    // mutator 
    // sets head to hd;
    void setHead(Node * hd);

    // mutator
    // sets tail to tl;
    void setTail(Node * tl);

    // mutator
    // increments or decrements count by n
    void setCount(unsigned n);

    // reads a redirected file of strings
    // pushes each string onto the vector
    void reader();

    // returns the string in the first node of the ll
    // this operation is not valid for an empty vector
    std::string front();

    // returns the string in the last non-dummy node of the ll
    // this operation is not valid for an empty vector
    std::string back();

    // creates a node containing str
    // adds the string to the end of the ll
    // if the ll is empty, this node becomes the head and tail
    // and a dummy node containing "END" and NULL will
    // be the node "one past the end of the list"
    // if list is not empty, insert between tail and last node.
    // count is incremented 
    void pushback(const std::string str);

    // pre-condition: vector must not be empty before calling this
    // post-condition: deletes the last element of the vector
    // post-condition: decreases the count by 1
    // post-condition: tail points to new last element
    void popback();

    // "it" is pointing to the element to be removed 
    // count is decreased by 1
    // all iterators and references to elements past the erasure
    // point are invalid and must be reset or avoided
    void erase(Iterator it);

    // erases all nodes in the range [s,t)
    // s is erased and all nodes up to but not
    // including t are erased
    // count is decreased by the number or nodes erased
    // all iterators and references to elements past the erasure
    // point are invalid and must be reset or avoided
    void erase(Iterator s, Iterator t);

    // inserts Node containing "str" into the ll in front of "pos"
    // any iterators after pos are considered invalid
    Iterator insert(Iterator pos, const std::string str);

    // returns the number of elements in the ll
    unsigned size() const;

    // returns true if the ll is empty, otherwise it returns false
    bool isEmpty();

    // brackets operator allows indexing into the ll
    // "fakes" random access to the ith element of the ll
    // returns contents of ith element of the ll
    // if ll looks like: 
    // we -> are -> family ->
    // then element 2 would be "family"
    // remember the first element is the 0th element
    std::string & operator[](int i) const;

    // returns the iterator pointing to the first node in the ll
    Iterator begin();

    // returns an iterator pointing a dummy node
    // which is the node AFTER tail
    Iterator end();

    // rearranges the nodes so that they are in alphabetical order
    // if ll looks like this:  we -> are -> all -> here
    // after sort, the ll looks like: all -> are -> here -> we
    void sort();

    // prints out the ll like the following
    // contents of node, followed by a space, 
    // followed by -> followed by a space
    // see sort above for an example
    // after list is printed, it skips a line 
    // ie has 2 endls
    // if list is empty, it prints "->" followed by
    // 2 endls
    void print();

  private:

    // makes a deep copy of the ll for copy constructor
    // and assignment operator
    // "other" is copied
    void copy(const Vector & other);

    // determines smallest word/expression in nodes in ll
    std::string smallest();

    // determines largest word/expression in nodes in ll
    std::string largest();

    // clears the ll by deleting all nodes
    // calls the recursive function deleteVector()
    void clear();

    // recursively deletes the ll p
    // THIS FUNCTION MUST BE RECURSIVE
    void deleteVector(Node * p);

    // YOU MAY ADD ANY OTHER PRIVATE FUNCTIONS HERE
};

#endif // VECTOR_CLASS

    // non-member function
    // locates "str" in the range [first,last)
    // if "str" is found in the range, an iterator pointing to
    // the node containing "str" is returned
    // if "str" is not found, END is returned
    // ie. you got to the "dummy node" at the end of the ll
    Iterator find(Iterator first, Iterator last, std::string str);