/******************************************************************************
File: ___________ <name of this file, .h or .cpp>
Name: ___________ <your name>
Course/Section: SI221/1121
Project | HW | Lab: ___________ <name of the assignment>
Date: ___________ <dd mmm yyyy>
Description: Class List - a templated list implementation
Resources used: List all resources used except the course website.  If none,
state so.
Help received: List all help received, include the name of the individual and
topic.  If none, state so.
Help given: List all help given, include the name of the individual and
topic.  If none, state so.
******************************************************************************/

#pragma once
#include <cstdlib>

template <class DataType>
class List {
  // forward declare Node which is a private nested class
  class Node;

public:

  /** CLASS FOR ITERATING OVER LISTS **/
  class Iterator {
    friend class List;
  public:
    DataType& get() const; // returns the item pointed to by Iterator
    void next(); // advances Iterator to the next list item
    bool equal(const Iterator &A) const; // returns true if caller and
                                         // 'A' point to same object
    Iterator(); // creates an Iterator with curr set to NULL
    
    // the two friend functions below allow List to access private
    friend void List<DataType>::insertBefore(DataType val, Iterator &I);
    friend void List<DataType>::remove(Iterator &I);
  private:
    Node *curr;
    Iterator(Node *p); // creates an Iterator with curr set to 'p'

  };

/***********************************************************
 ** INTERFACE: PUBLIC MEMBERS OF CLASS LIST
 ***********************************************************/
  List();
  ~List();

  // add2front creates a new node with val, points it to the
  // first node of the list and points head to that new node
  void add2front(const DataType &val);

  // add2back creates a new node with val and points the last
  // node and tail to that new node
  void add2back(const DataType &val);

  Iterator begin() const; // returns an Iterator to the item
                          // pointed to by the head of the list

  Iterator end() const; // returns an Iterator to NULL which is
                        // what the tail of the list links to


  // PROTOTYPES FOR ALL THE FUNCTIONS YOU WILL DEFINE BELOW
  int length() const;                           /** PART 1 **/
  void copyList(List<DataType> &L) const;       /** PART 2 **/
  void insertBefore(DataType val, Iterator &I); /** PART 3 **/
  void remove(Iterator &I);                     /** PART 4 **/


/***********************************************************
 ** INTERFACE: PRIVATE MEMBERS OF CLASS LIST
 ***********************************************************/
private:
  //disable copy construtor and assignment operator
  List(const List<DataType> &L) { }
  List<DataType>& operator=(const List<DataType> &L) { }

  class Node {
  public:
    DataType data;
    Node *next;
    Node(const DataType &val = DataType(), Node *p = NULL) {
      data = val; next = p;
    }
  };//end class Node

  Node *head, *tail;
};


/***********************************************************
 ** DEFINITIONS OF LIST'S MEMBER FUNCTIONS
 ***********************************************************/
template <class DataType>
List<DataType>::List() {
  head = NULL; tail = NULL;
}

template <class DataType>
List<DataType>::~List() {
  if (head != NULL) {
    for(Node *curr = head, *after; curr != NULL; curr = after) {
      after = curr->next;
      delete curr;
    }
  }
}

template <class DataType>
void List<DataType>::add2front(const DataType &val) {
  head = new Node(val,head);
  if (tail == NULL)
    tail = head;
}

template <class DataType>
void List<DataType>::add2back(const DataType &val){
  if (head != NULL) {
    tail->next = new Node(val,NULL);
    tail = tail->next;
  }
  else {
    tail = new Node(val,NULL);
    head = tail;
  }
}

template <class DataType>
typename List<DataType>::Iterator List<DataType>::begin() const {
  return Iterator(head);
}

template <class DataType>
typename List<DataType>::Iterator List<DataType>::end() const {
  return Iterator();
}


/***********************************************************
 ** DEFINITIONS OF ITERATORS MEMBER FUNCTIONS
 ***********************************************************/
template <class DataType>
List<DataType>::Iterator::Iterator(): curr(NULL) { }

template <class DataType>
List<DataType>::Iterator::Iterator(Node *p): curr(p) { }

template <class DataType>
DataType& List<DataType>::Iterator::get() const {
  return curr->data;
}

template <class DataType>
void List<DataType>::Iterator::next() {
  curr = curr->next;
}

template <class DataType>
bool List<DataType>::Iterator::equal(const Iterator &A) const {
  return curr == A.curr;
}


/***********************************************************
 ** DEFINITIONS OF YOUR NEW LIST MEMBER FUNCTIONS
 ***********************************************************/

// NEW STUFF BELOW
/**
Function: length()
Purpose:  ????? -- fill me in!
**/
template <class DataType>
int List<DataType>::length() const {
  // PART 1 - fill me in!
}

/**
Function: copyList(List<DataType> &L) const
Purpose:  ????? -- fill me in!
**/
template <class DataType>
void List<DataType>::copyList(List<DataType> &L) const {
  // PART 2 - fill me in!
}

/**
Function: insertBefore(DataType val, Iterator &I)
Purpose:  ????? -- fill me in!
**/
template <class DataType>
void List<DataType>::insertBefore(DataType val, Iterator &I) {
  // PART 3 - fill me in!
}

/**
Function: remove(Iterator &I)
Purpose:  ????? -- fill me in!
**/
template <class DataType>
void List<DataType>::remove(Iterator &I) {
  // PART 4 - fill me in!
}
// END NEW STUFF