List.h

#ifndef LIST_H
#define LIST_H
/* List.h
 *
 * doubly-linked, double-ended list with Iterator interface
 * Project UID c1f28c309e55405daf00c565d57ff9ad
 * EECS 280 Project 4
 */

#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;

  //EFFECTS: returns the number of elements in this List
  int size() const;

  //REQUIRES: list is not empty
  //EFFECTS: Returns the first element in the list by reference
  T & front();

  //REQUIRES: list is not empty
  //EFFECTS: Returns the last element in the list by reference
  T & back();

  //EFFECTS:  inserts datum into the front of the list
  void push_front(const T &datum);

  //EFFECTS:  inserts datum into the back of the list
  void push_back(const T &datum);

  //REQUIRES: list is not empty
  //MODIFIES: may invalidate list iterators
  //EFFECTS:  removes the item at the front of the list
  void pop_front();

  //REQUIRES: list is not empty
  //MODIFIES: may invalidate list iterators
  //EFFECTS:  removes the item at the back of the list
  void pop_back();

  //MODIFIES: may invalidate list iterators
  //EFFECTS:  removes all items from the list
  void clear();

    List(); //constructor

    ~List(); //destructor

    List(List &x);

    List& operator= (List &x);
  // 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

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);

  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

public:
  ////////////////////////////////////////

  class Iterator {

    //OVERVIEW: Iterator interface to List
      friend class List;
  public:
      Iterator();

      Iterator(Iterator &x) {
          node_ptr = x.node_ptr;
      }

      Iterator& operator= (Iterator &x) {
          node_ptr = x.node_ptr;
      }


    // 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.


      T& operator* ();

      Iterator &operator++();

      bool operator==(Iterator rhs) const;

      bool operator!=(Iterator rhs) const;

    // 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& operator--() {
      assert(node_ptr);
      node_ptr = node_ptr->prev;
      return *this;
    }

  private:
    Node *node_ptr; //current Iterator position is a List node
    // add any additional necessary member variables here
    // construct an Iterator at a specific position
    Iterator(Node *p);


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

  // return an Iterator pointing to the first element


  //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);

  //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);


    // return an Iterator pointing to "past the end"

    Iterator begin()  {
        return Iterator(first);
    }
    Iterator end() {
        return Iterator();
    }

};//List

template <typename T>
List<T>::Iterator::Iterator() {
    node_ptr = nullptr;
}

template <typename T>
void List<T>::erase(Iterator i) {
    assert(!empty());
    if(i.node_ptr == first) {
        pop_front();
    }
    else if(i.node_ptr == last) {
        pop_back();
    }
    else {
        ((*(i.node_ptr)).prev)->next =(*(i.node_ptr)).next;
        ((*(i.node_ptr)).next)->prev =(*(i.node_ptr)).prev;
        delete i.node_ptr;
    }
}

template <typename T>
void List<T>::insert(Iterator i, const T &datum) {
    if(i.node_ptr == first) {
        push_front(datum);
    }
    else {
        Node *added = new Node();
        added->next = i.node_ptr;
        added->prev =(*(i.node_ptr)).prev;
        added->datum = datum;
        (i.node_ptr)->prev = added;
        ((*(i.node_ptr)).prev)->next = added;
    }
}

template <typename T>
T & List<T>::Iterator::operator*()  {
    assert(node_ptr);  // check whether this is a past-the-end iterator
    return node_ptr->datum;
}

template <typename T>
typename List<T>::Iterator & List<T>::Iterator::operator++() {
    assert(node_ptr);  // check whether this is a past-the-end iterator
    node_ptr = node_ptr->next;
    return *this;
}

template <typename T>
bool List<T>::Iterator::operator==(Iterator rhs) const {
    return node_ptr == rhs.node_ptr;
}

template <typename T>
bool List<T>::Iterator::operator!=(Iterator rhs) const {
    return node_ptr != rhs.node_ptr;
}

template <class T>
List<T>::List(List &x): List<T>() {
    for(Node *ptr = x.first; ptr; ptr = ptr->next) {
        push_back(ptr->datum);
    }
}

template <class T>
List<T>& List<T>::operator= (List &x) {
    if(this == &x) {
        return *this;
    }
    while(!empty()) {
        pop_front();
    }
    for(Node *ptr = x.first; ptr; ptr = ptr->next) {
        push_back(ptr->datum);
    }
    return *this;
}

template <class T>
List<T>::~List() {
    while(!empty()) {
        pop_front();
    }
}

template <class T>
List<T>::List() {
    first = nullptr;
    last = nullptr;
}

template <class T>
bool List<T>::empty() const {
    return size() == 0;
}

template <class T>
void List<T>::copy_all(const List<T> &other) {
    assert(empty());
    for(Node *ptr = other.first; ptr; ptr = ptr->next) {
        push_back(ptr->datum);
    }
}

template <class T>
int List<T>::size() const {
    if(first == nullptr) {
        return 0;
    }
    int i = 0;
    for(Node *ptr = first; ptr != nullptr; ptr = ptr->next) {
        i++;
    }
    return i;
}

template <class T>
T & List<T>::front() {
    assert(!empty());
    return first->datum;
}

template <class T>
T & List<T>::back() {
    assert(!empty());
    return last->datum;
}

template <class T>
void List<T>::push_front(const T &datum) {
    Node *p = new Node;
    p->datum = datum;
    p->next = first;
    p->prev = nullptr;
    if(first != nullptr) {
        first->prev = p;
    }
    else { //empty list
        last = p;
    }
    first = p;
}

template <class T>
void List<T>::push_back(const T &datum) {
    Node *p = new Node;
    p->datum = datum;
    p->next = nullptr;
    p->prev = last;
    if(last) {
        last->next = p;
    }
    else {
        first = p;
    }
    last = p;
}

template <class T>
void List<T>::pop_front() {
    assert(!empty());
    if(size() == 1) {
        delete first;
        first = nullptr;
        last = nullptr;
    }
    else {
        Node *newFirst = first->next;
        delete first;
        first = newFirst;
        if(!empty()) {
            first->prev = nullptr;
        }
    }
}

template <class T>
void List<T>::pop_back() {
    assert(!empty());
    if(size() == 1) {
        delete last;
        first = nullptr;
        last = nullptr;
    }
    else {
        Node *newLast = last->prev;
        delete last;
        last = newLast;
        if(!empty()) {
            last->next = nullptr;
        }
    }
}

template <class T>
void List<T>::clear() {
    while(!empty()) {
        pop_front();
    }
}


////////////////////////////////////////////////////////////////////////////////
// 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.