// List.cpp - implementation file for linked list List ADT

#include <iostream>
using namespace std;

#include "List.h"

//-- Definition of the class constructor
List::List() : first(0), last(0), mySize(0)
{ }

//-- Definition of the copy constructor
List::List( const List & origList )
{
   mySize = origList.mySize;
   
   first = last = 0;
   if ( mySize == 0 )
      return;

   List::NodePointer origPtr;
   
   first = new Node(origList.first->data); // copy first node
   last = first;
   origPtr = origList.first->next;

   while ( origPtr != 0 )
   {
      last->next = new Node(origPtr->data);
      origPtr = origPtr->next;
      last = last->next;
   }
}

//-- Definition of the destructor
inline List::~List()
{
   List::NodePointer prev = first, ptr;
   
   while ( prev != 0 )
   {
      ptr = prev->next;
      delete prev;
      prev = ptr;
   }
}

//-- Definition of the assignment operator
const List & List::operator=( const List & rightSide )
{
   mySize = rightSide.mySize;

   first = last = 0;
   if ( mySize == 0 )
      return *this;

   if ( this != &rightSide )
   {
      this->~List();
      List::NodePointer origPtr;
      first = new Node(rightSide.first->data); // copy first node
      last = first;
      origPtr = rightSide.first->next;
      while ( origPtr != 0 )
      {
         last->next = new Node(origPtr->data);
         origPtr = origPtr->next;
         last = last->next;
      }
   }
   return *this;
}

// Definition of empty()
bool List::empty() const
{
   return mySize == 0;
}

//-- Definition of insert()
void List::insert( ElementType dataVal, int index )
{
   if ( index < 0 || index > mySize )
   {
      cerr << "Illegal location to insert -- " << index << endl;
      return;
   }
   List::NodePointer newPtr = new Node(dataVal), predPtr = first;
   if ( index == 0 )
   {
      newPtr->next = first;
      first = newPtr;
      if ( mySize == 0 )
         last = first;     // insert to empty list; first and last pt. to new node
   }
   else if ( index == mySize )
   {
      last = last->next = newPtr;  // insert new element at end of list
   }
   else
   {
      for( int i = 1;  i < index;  ++i )
         predPtr = predPtr->next;
      newPtr->next = predPtr->next;
      predPtr->next = newPtr;
   }
   ++mySize;
}

//-- Definition of erase()
void List::erase( int index )
{
   if ( index < 0 || index >= mySize )
   {
      cerr << "Illegal location to delete -- " << index << endl;
      return;
   }
   List::NodePointer ptr, predPtr = first;
   if ( index == 0 )
   {
      ptr = first;
      first = ptr->next;
      delete ptr;
      if ( first == 0 )
         last = 0;     // erased only node; first and last must be null
   }
   else
   {
      for( int i = 1;  i < index;  ++i )
         predPtr = predPtr->next;
      ptr = predPtr->next;
      predPtr->next = ptr->next;
      if ( ptr == last )
         last = predPtr;
      delete ptr;
   }
   --mySize;
 }

//-- Definition of at
ElementType List::at( int index ) const
{
   List::NodePointer p = first;

   if ( index < 0  ||  index >= mySize )
   {
      cerr << "*** Attempt to access non-existent element"
              " -- returning garbage ***\n";
      ElementType *temp = new(ElementType);  
      ElementType garbage = *temp;         // "garbage" value
      delete temp;
      return garbage;
   }

   for( int i = 0;  i < index;  ++i )
      p = p->next;
   
   return p->data;
}

//-- Definition of search()
int List::search( ElementType dataVal )
{
   int pos = 0;
   List::NodePointer p = first;

   while ( p != 0 )
   {
      if ( p->data == dataVal )
         return pos;
      p = p->next;
     ++pos;
   }
   return -1;
}

//-- Definition of display()
void List::display( ostream & out ) const
{
   List::NodePointer p = first;

   while (p != 0)
   {
      out << p->data << ' ';
      p = p->next;
   }
}

//-- Definition of the output operator
ostream & operator<<( ostream & out, const List & aList )
{
   aList.display(out);
   return out;
}

//-- Definition of nodeCount()
int List::nodeCount()
{
   return mySize;
}

//-- Definition of reverse()
void List::reverse()
{
   List::NodePointer pp = 0,      // prev pointer
                     p = first,   // current pointer
                     np;          // next pointer

   while ( p != 0 )
   {
      np = p->next;
      p->next = pp;
      pp = p;
      p = np;
   }
   last = first;
   first = pp; // new head of (reversed) linked list
}

//-- Definition of ascendingOrder()
bool List::ascendingOrder()
{
   // an empty or one-element list is always in ascending (and descending!) order
   if ( mySize <= 1 )
      return true;

   NodePointer p = first, np = first->next;

   while ( np != 0  &&  p->data <= np->data )
   {
      p = np;
      np = np->next;
   }

   // the list is in ascending order if and only if we've gone the whole list w/o 
   // finding a pair of adjacent elements that are out of (ascending) order
   return (np == 0) ? true : false;
}