/******************************************************************
 * Memorial University of Newfoundland
 * Engineering 4892 Data Structures
 * Assignment 3
 *
 * $RCSfile$   $Revision$
 * $Date$
 * $State$ 
 *
 * A Doubly Linked list class template.
 *
 ******************************************************************/

/******************************************************************
 *                     REVISION HISTORY
 *
 * $Log$
 *
 ******************************************************************/

#ifndef DLIST_DEF
#define DLIST_DEF


template <class T>
class List 
{
  public:
  // A list of type T.
  // Modeled by: 
  //   L sequence of T
  // 
  // INV: none

  // Local types
    enum Status { Ok, NewFail, NoSuchElement };

  // Constructors 
    List();
    // Post: L = _

    List(const List<T>& r);
    // Post: L' = r.L

  // Destructor
    ~List();

  // Accessors
    T front() const;
    // Pre: |L| > 0
    // Post: Result = first element of L

    T back() const;
    // Pre: |L| > 0
    // Post: Result = last element of L

    const T& operator[] (int i) const;
    // Pre: 0 <= i < |L|
    // Post: Result = L[i] (i'th element of L)

    bool empty() const;
    // Post: Result = (|L| = 0)

    int size() const;
    // Post: Result = |L|

    Status getStatus() const { return err; }
    // Post: Result = status of last access

  // Mutators
    Status push_back(const T& x);
    // Post: Result = Ok -> L' = Lx 

    Status push_front(const T& x);
    // Post: Result = Ok -> L' = xL 

    Status insert(const T& x, int i);
    // Pre: 0 <= i <= |L|
    // Post: L' = L with x inserted at the ith position. If i == |L| then x
    //      is appended

    void pop_front();
    // Pre: |L| > 0
    // Post: L' = L with first element removed

    void pop_back();
    // Pre: |L| > 0
    // Post: L' = L with last element removed

    Status remove(int i);
    // Pre: 0 <= i < |L|
    // Post: L' = L with i'th element removed.

    List<T>& operator=(const List<T>& r);
    // Assignment operator
    // Post: this is a copy of r

  private:
    // Representation:
    // head != 0 -> L = { head->data, head->next->data, ...  } /\ 
    // head = 0 -> L = _
    
    class Node { 
      public:
        T data;
        Node* next;
        Node* prev;
        Node(T d = 0, Node *n = 0, Node* p = 0) 
          : data(d), next(n), prev(p) { }
          // Note this assumes that T has a copy constructor.
    };
    Node* head;
    Node* tail;

    mutable Status err;   // Status of the last call.

    // Private methods
    void copyList(const Node* src, Node** dest);
    void deleteList(Node* cur);
};

#include <cassert>
#include <new>


/******************************************************************
 * List -- constructor
 *
 * Post: err = Ok /\ head = 0 /\ tail = 0
 *******************************************************************/
template <class T>
List<T>::List<T>()
{
  head = 0;
  tail = 0;
  err = Ok;
}

/******************************************************************
 * List<T> -- copy constructor
 * 
 * Post: err = Ok -> head points to a linked list that is a copy of r
 *                   /\ tail points to the end of the list
 *       err = NewFail -> memory allocation failure
 *******************************************************************/
template <class T>
List<T>::List<T>(const List<T>& r)
{
  head = 0;
  tail = 0;
  copyList(r.head, &head);
}

/******************************************************************
 * ~List<T> -- destructor
 * 
 *******************************************************************/
template <class T>
List<T>::~List()
{
  deleteList(head);
}

/******************************************************************
 * front -- return the value of the front element
 * 
 * Pre: head != 0
 * Post: Result = head->data
 *******************************************************************/
template <class T>
T 
List<T>::front() const
{
  assert(head != 0);
  return head->data;
}

/******************************************************************
 * back -- return the value of the last element
 * 
 * Pre: tail != 0
 * Post: Result = tail->data
 *******************************************************************/
template <class T>
T 
List<T>::back() const
{
  assert(tail != 0);
  return tail->data;
}

/******************************************************************
 * empty -- return true if the List is empty, false otherwise
 * 
 * Post: Result = head == 0
 *******************************************************************/
template <class T>
bool 
List<T>::empty() const
{
  return (head == 0);
}

/******************************************************************
 * size -- return the length of the List 
 * 
 * Post: Result = len
 *******************************************************************/
template <class T>
int 
List<T>::size() const
{
  int len = 0;
  Node* cur = head;
  while (cur != 0) {
    cur = cur->next;
    len++;
  }
  return len;
}

/******************************************************************
 * push_back -- put an element on the rear of the List
 * 
 * Post: *tail' is a new node with data = x /\ tail'->prev = tail
 *******************************************************************/
template <class T>
List<T>::Status 
List<T>::push_back(const T& x)
{
  Node* toAdd = new(std::nothrow) Node(x, 0, tail);
  if (toAdd != 0) {
    if (tail != 0) {
      tail->next = toAdd;
    } else {
      head = toAdd;
    }
    tail = toAdd;
    err = Ok;
  } else {
    err = NewFail;
  }
  return err;
}

/******************************************************************
 * push_front -- put an element on the front of the List
 * 
 * Post: *head' is a new node with data = x /\ head'->next = head
 *******************************************************************/
template <class T>
List<T>::Status 
List<T>::push_front(const T& x)
{
  Node* toAdd = new(std::nothrow) Node(x, head, 0);
  if (toAdd != 0) {
    if (head != 0) {
      head->prev = toAdd;
    } else {
      tail = toAdd;
    }
    head = toAdd;
    err = Ok;
  } else {
    err = NewFail;
  }
  return err;
}

/******************************************************************
 * pop_front -- remove the element from the front of the List
 * 
 * Pre: head != 0
 * Post: head' = head->next /\ head is deleted
 *******************************************************************/
template <class T>
void 
List<T>::pop_front()
{
  assert(head != 0);
  Node* toDel = head;
  head = head->next;
  if (head == 0) {
    tail = 0;
  } else {
    head->prev = 0;
  }
  delete toDel;
  return;
}

/******************************************************************
 * pop_back -- remove the element from the end of the List
 * 
 * Pre: head != 0
 * Post: tail' = tail->prev /\ tail is deleted
 *******************************************************************/
template <class T>
void 
List<T>::pop_back()
{
  assert(head != 0);
  Node* toDel = tail;
  tail = tail->prev;
  if (tail == 0) {
    head = 0;
  } else {
    tail->next = 0;
  }
  delete toDel;
  return;
}

/******************************************************************
 * operator= -- assignment operator
 * 
 * Post: err = Ok -> (q points to size bytes of appropriately allocated memory 
 *                    this is a copy of r)
 *       err = Fail -> q = null (memory allocation failure)
 *******************************************************************/
template <class T>
List<T>& 
List<T>::operator=(const List<T>& r)
{
  if (&r != this) {
    deleteList(head);
    head = 0;
    copyList(r.head, &head);
  }
  return *this;
}

template <class T>
void
List<T>::copyList(const Node* src, Node** dest)
{
  err = Ok;
  Node *prev = 0;
  while (src != 0 && err == Ok) {
    // INV: dest is address of 'head' for remainder of destination list /\ 
    //      src points to the head of the list remaining to be copied.
    *dest = new(std::nothrow) Node<T>;
    if (*dest != 0) {
      (*dest)->data = src->data;
      (*dest)->prev = prev;
      prev = *dest;
      src = src->next;
      dest = &(*dest)->next;
    } else {
      err = NewFail;
    }
  }
  if (err == Ok) {
    tail = prev;
  }
}

template <class T>
void
List<T>::deleteList(List<T>::Node* cur)
{
  while (cur != 0) {
    // INV: cur points to the head of the list to be deleted
    Node* nxt = cur->next;
    delete cur;
    cur = nxt;
  }
}
#endif