// Symmetrically linked list implementation
// By: Nick Cash
// Coded for Computer Science III

// Standard includes
#include <cstdlib>
#include <iostream>

// Custom includes
#include "list.h"

// cList class implementation

// Constructor
template<class T>
cList<T>::cList()
{
  start = end = NULL;
}

// Destructor
template<class T>
cList<T>::~cList()
{
}

// Add item to the front of the list
template<class T>
inline void cList<T>::PushFront( const T& x )
{
  Element* elem = new Element;

  elem->data = x;

  Link( elem, true );
}

// Add item to the back of the list
template<class T>
inline void cList<T>::PushBack( const T& x )
{
  Element* elem = new Element;

  elem->data = x;

  Link( elem, false );
}

// Private member function
// Link element into the list, to the front or back
template<class T>
inline void cList<T>::Link(Element* i, bool front)
{
  if ( !i ) // Make sure we have data
   return;

  if ( !start ) // first element is a special case
  {
    start = end = i;
    i->SetNext(NULL);
    i->SetPrev(NULL);
  }
  else if ( front )
  {
    i->SetPrev(NULL);  // Front of list has no previous element
    i->SetNext(start); // The next in the list is the previous start node

    // Add i as the previous element to the soon to be second element
    start->SetPrev(i);

    // Set our start pointer to our new element
    start = i;
  }
  else
  {
    i->SetPrev(end);  // The current end becomes second to last
    i->SetNext(NULL); // Back of list has no next element

    // Add i as the next element to the soon to be second to last element
    end->SetNext(i);

    // Set our end pointer to our new element
    end = i;
  }
}

// Private member function
// Unlink an element from the list
template<class T>
inline void cList<T>::Unlink(Element* x)
{
  if ( !x ) // Make sure our x is good
   return;

  // Take care of start special case
  if ( x == start )
  {
    start = x->GetNext();

    if ( start )
     start->SetPrev(NULL);
  }
  else
    (x->GetPrev())->SetNext(x->GetNext());

  // End special case
  if ( x == end )
  {
    end = x->GetPrev();

    if ( end )
     end->SetNext(NULL);
  }
  else
   (x->GetNext())->SetPrev(x->GetPrev());

}

// Return the number of elements in the list
// Gathered by traversal instead of general upkeep in linking functions
template<class T>
inline unsigned int cList<T>::Size()
{
 unsigned int size = 0;

 for ( Element* iter = start; iter != NULL; iter = iter->GetNext() )
  size++;

 return size;
}

// Return true if our list is empty, false if it contains anything
template<class T>
inline bool cList<T>::Empty()
{
  return (start == NULL);
}

// Delete every element in our list
template<class T>
inline void cList<T>::Clear()
{
  while ( start )
  {
    Element* temp = start;

    Unlink(start);

    delete temp;
  }
}

// Print out our list, element by element.
//
//  Note: This function may need to be modified, even removed depending
//        what your element is. For example, classes and structures will
//        not print correctly without modification.
template<class T>
inline void cList<T>::Print()
{
  std::cout << "\n[ ";

  for ( Element* iter = start; iter != NULL; iter = iter->GetNext() )
   std::cout << iter->data << ' ';

  std::cout << "]\n";
}

// Delete -ONE- element from the list containing data "x"
//   Note: If you have an Element pointer and wish to remove it from the
//         list, simply call delete on its "data" field
template<class T>
inline void cList<T>::Delete(const T& x)
{
 for ( Element* iter = start; iter != NULL; iter = iter->GetNext() )
 {
   if ( iter->data == x )
   {
     Unlink(iter);
     delete iter;
     break;
   }
 }
}

// Erase -ALL- elements from the list containing data "x"
template<class T>
inline void cList<T>::Erase(const T& x)
{
 Element* next;

 for ( Element* iter = start; iter != NULL; iter = next )
 {
   next = iter->GetNext();

   if ( iter->data == x )
   {
     Unlink(iter);
     delete iter;
   }
 }
}

// Remove the first element from the list
template<class T>
inline void cList<T>::PopFront()
{
  Element* temp = start;

  Unlink(start);
  delete temp;
}

// Remove the last element from the list
template<class T>
inline void cList<T>::PopBack()
{
  Element* temp = end;

  Unlink(end);
  delete temp;
}

// Insert "link" -BEFORE- element "insert"
template<class T>
inline void cList<T>::Insert(Element* link, Element* insert)
{
  if ( !link || !insert )
   return;

  link->SetPrev(insert->GetPrev());

  if ( !insert->GetPrev() )
   start = link;
  else
   (insert->GetPrev())->SetNext(link);

  insert->SetPrev(link);
  link->SetNext(insert);
}

// Reverse the direction of the list
template<class T>
inline void cList<T>::Reverse()
{
  Element* iter = start;
  Element* prev = NULL;
  Element* next = NULL;

  // our start node will now be our ending node
  end = iter;

  while ( iter )
  {
     next = iter->GetNext(); // save to advance iter
     prev = iter->GetPrev();

     iter->SetPrev(next);
     iter->SetNext(prev);

     // if we have no next, this was our end element previously
     // and needs to be set to our new start
     if ( !next )
      start = iter;

     iter = next;
  }
}