#ifndef LIST_H
#define LIST_H
/* List.h
 *
 * doubly-linked, double-ended list with Iterator interface
 */

#include <iostream>
#include <cassert> //assert
#include <cstddef> //NULL

using namespace std;

template <typename T>
class List {
  //OVERVIEW: a doubly-linked, double-ended list with Iterator interface
public:
  //EFFECTS:  returns true if the list is empty
    bool empty() const    {
        return !first;
    }

  //EFFECTS: returns the number of elements in this List
  //HINT:    Traversing a list is really slow.  Instead, keep track of the size
  //         with a private member variable.  That's how std::list does it.
    int size() const  {
        return num;
    }

  //REQUIRES: list is not empty
  //EFFECTS: Returns the first element in the list by reference
    T & front()   {
        assert(!empty());
        return first->datum;
    }

  //REQUIRES: list is not empty
  //EFFECTS: Returns the last element in the list by reference
    T & back()    {
        assert(!empty());
        return last->datum;
    }

  //EFFECTS:  inserts datum into the front of the list
    void push_front(const T &datum)   {
        Node *temp = new Node{};
        temp->datum = datum;
        temp->next = first;
        temp->prev = nullptr;
        if (num == 0)   {
            last = temp;
            first = temp;
        }
        else    {
            first->prev = temp;
            first = temp;
        }
        if (num == 1)   {
            last->prev = temp;
        }
        num += 1;
    }

  //EFFECTS:  inserts datum into the back of the list
    void push_back(const T &datum)    {
        Node *temp = new Node{};
        temp->datum = datum;
        temp->prev = last;
        temp->next = nullptr;
        if (num == 0)   {
            first = temp;
            last = temp;
        }
        else    {
            last->next = temp;
            last = temp;
        }
        if (num == 1)   {
            first->next = temp;
        }
        num += 1;
    }

  //REQUIRES: list is not empty
  //MODIFIES: may invalidate list iterators
  //EFFECTS:  removes the item at the front of the list
    void pop_front()  {
        assert(!empty());
        Node *temp = first;
        first = first->next;
        if (first) {
            first->prev = nullptr;
        } else  {
            last = nullptr;
        }
        delete temp;
        num -= 1;
    }

  //REQUIRES: list is not empty
  //MODIFIES: may invalidate list iterators
  //EFFECTS:  removes the item at the back of the list
    void pop_back()   {
        assert(!empty());
        Node *temp = last;
        last = last->prev;
        if (last) {
            last->next = nullptr;
        } else  {
            first = nullptr;
        }
        delete temp;
        num -= 1;
    }

  //MODIFIES: may invalidate list iterators
  //EFFECTS:  removes all items from the list
    void clear()  {
        while (!empty()) {
            pop_back();
        }
        num = 0;
    }

    // You should add in a default constructor, destructor, copy constructor,
    // and overloaded assignment operator, if appropriate. If these operations
    // will work correctly without defining these, you can omit them. A user
    // of the class must be able to create, copy, assign, and destroy Lists

    
    List(): first(nullptr), last(nullptr), num(0)  {}
    
    List(const List &other): first(nullptr), last(nullptr), num(0)   {
        copy_all(other);
    }
    
    List & operator=(const List &rhs) {
      if (this != &rhs) {
        clear();
        copy_all(rhs);
      }
      return *this;
    }
    
    ~List() {
      clear();
    }
    
private:
  //a private type
  struct Node {
    Node *next;
    Node *prev;
    T datum;
  };

  //REQUIRES: list is empty
  //EFFECTS:  copies all nodes from other to this
    void copy_all(const List<T> &other)   {
      for (Node *ptr = other.first; ptr; ptr = ptr->next) {
        push_back(ptr->datum);
      }
    }

  Node *first;   // points to first Node in list, or nullptr if list is empty
  Node *last;    // points to last Node in list, or nullptr if list is empty
  int num;

public:
  ////////////////////////////////////////
  class Iterator {
    //OVERVIEW: Iterator interface to List

    // You should add in a default constructor, destructor, copy constructor,
    // and overloaded assignment operator, if appropriate. If these operations
    // will work correctly without defining these, you can omit them. A user
    // of the class must be able to create, copy, assign, and destroy Iterators.

    // Your iterator should implement the following public operators: *,
    // ++ (prefix), default constructor, == and !=.
    

  public:
    // This operator will be used to test your code. Do not modify it.
    // Requires that the current element is dereferenceable.
      Iterator(): node_ptr(nullptr)    {}
      
      Iterator(const Iterator &other): node_ptr(other.node_ptr) {}
      
      Iterator& operator--() {
      assert(node_ptr);
      node_ptr = node_ptr->prev;
      return *this;
    }
      
      T & operator*() const   {
          assert(node_ptr);
          return node_ptr->datum;
      }
      
      Iterator &operator++()  {
          assert(node_ptr);
          node_ptr = node_ptr->next;
          return *this;
      }

      bool operator==(Iterator rhs) const {
          return node_ptr == rhs.node_ptr;
      }

      bool operator!=(Iterator rhs) const {
          return node_ptr != rhs.node_ptr;
      }

  private:
    Node *node_ptr; //current Iterator position is a List node
    // add any additional necessary member variables here

    // add any friend declarations here
    friend class List;
    // construct an Iterator at a specific position
      
      Iterator(Node *p)   {
          node_ptr = p;
      }

  };//List::Iterator
  ////////////////////////////////////////

  // return an Iterator pointing to the first element
    Iterator begin() const {
        return Iterator(first);
    }

  // return an Iterator pointing to "past the end"
    Iterator end() const  {
        return Iterator();
    }

  //REQUIRES: i is a valid, dereferenceable iterator associated with this list
  //MODIFIES: may invalidate other list iterators
  //EFFECTS: Removes a single element from the list container
    void erase(Iterator i)    {
        if (i.node_ptr == first) {
            pop_front();
        } else if (i.node_ptr == last)  {
            pop_back();
        } else  {
            Node *temp = i.node_ptr;
            i.node_ptr->prev->next = i.node_ptr->next;
            i.node_ptr->next->prev = i.node_ptr->prev;
            delete temp;
        }
        num -= 1;
    }

  //REQUIRES: i is a valid iterator associated with this list
  //EFFECTS: inserts datum before the element at the specified position.
    void insert(Iterator i, const T &datum)   {
        if (i.node_ptr == first) {
            push_front(datum);
        } else if (i.node_ptr == nullptr)  {
            push_back(datum);
        } else  {
            Node *temp = new Node{};
            temp->datum = datum;
            temp->next = i.node_ptr;
            temp->prev = i.node_ptr->prev;
            i.node_ptr->prev->next = temp;
            i.node_ptr->prev = temp;
            num += 1;
        }
    }

};//List


////////////////////////////////////////////////////////////////////////////////
// Add your member function implementations below or in the class above
// (your choice). Do not change the public interface of List, although you
// may add the Big Three if needed.  Do add the public member functions for
// Iterator.


#endif // Do not remove this. Write all your code above this line.