#ifndef LIST_H

#define LIST_H

#include

#include

#include

template

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

}

//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(){

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 *p = new Node;

p->datum = datum;

p->next = first;

first = p;

}

//EFFECTS: inserts datum into the back of the list

void push_back(const T &datum){

Node *p = new Node;

p->datum = datum;

p->next = nullptr;

if (empty())

first = last = p;

else{

last = last->next = p;

}

}

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

//constructor

List() : first(0), last(0){}

//copy constructor

List(const List &other):first(0),last(0){

copy_all(other);

}

//destructor

~List(){pop_all();}

//overloading constuctor

List &operator = (const List &rhs){

if (this == &rhs) return *this;

pop_all();

copy_all(rhs);

return *this;

}

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

//MODIFIES: may invalidate list iterators

//EFFECTS: removes all nodes

void pop_all();

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

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

// 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(last->next);

}

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

};

#endif