// ***********************************************************
// *                                                         *
// *  singlist.C                                             *
// *                                                         *
// *  Implementation for a list class, implemented via       *
// *        singly-linked memory                             * 
// *                                                         *
// *  Written 5 May 1997 by Jason Zych                       *
// *                                                         *
// *********************************************************** 

// ******************************************************
// *                                                    *
// *  Access functions  Replace(), ToArray(), Reverse() *
// *              SortedInsert(), Splice()  written by: *
// *                                                    *
// *  Author: Zaczek, Mariusz                           *
// *  Date:   2/25/1999                                 *
// *  Class:  Tu 11-1 , Chad Piper                      *
// *                                                    *
// ******************************************************


#include "singlist.h"

// ***********************************************
// ** This is where your MP4 functions should go


// Replace
//    - parameters : oldVal - the value we want to replace in the list
//                 : newVal - the value we want to replace it with
//    - replaces all occurences of oldVal in the list with newVal,
//        and then sets current to be the first item in the list,
//        if there are items in the list
template <class Etype>
void List<Etype>::Replace(const Etype oldVal, const Etype newVal)
{
  Warn(size > 0, "Cannot update an element in an empty list.");

  // Test if list has elements...i.e. is not empty
  if (size > 0)
  {
    ListNode<Etype> *tempPtr;
      tempPtr = head;

    // Loop through the list, starting at _head_, and when the 
    //   element at a location matches the _oldVal_ then set
    //   this element equal to _newVal_  
    for(int i=0 ; i < size ; i++)
    {
      if (tempPtr -> element == oldVal)
        tempPtr -> element = newVal;
     
      // Move _tempPtr_ to next list node.
      tempPtr = tempPtr -> next;
    }
  }
  return;
}


// ToArray
//    - return type : an Array object whose size is equal to the size
//                       of the list
//    - returns an Array containing the elements of the list,   
//        appearing in the same order in the Array as they do in the list
//        Assumes list is non-empty
template <class Etype>
Array<Etype> List<Etype>::ToArray()
{
  ListNode<Etype> *tempPtr;
    tempPtr = head;   // Originate pointer at head.

  Array<Etype> myArray(1,size);

  // Loop through linked list and read each element and store it
  //   consecutively in the array.
  for (int i=1 ; i <=size ; i++)
  {
    myArray[i] = tempPtr -> element;
    tempPtr = tempPtr -> next;
  }  
  
  // Return array to function where call initiated.
  return myArray;
}


// SortedInsert
//    - parameters : insElem - the value we wish to insert
//    - inserts the parameter element in sorted order. This
//        function requires that operator< is defined for the
//        type in question, and assumes that the list is already
//        sorted from smallest to largest value as defined by
//        operator< on that type. The newly-inserted element
//        should become the current element.
template <class Etype>
void List<Etype>::SortedInsert(const Etype insElem)
{
  ListNode<Etype> *newElemPtr = new ListNode<Etype>;
  ListNode<Etype> *tempPtr;
    tempPtr = head;  // Originate pointer at head.

  // If the size of the linked list is zero - i.e. empty list - 
  //    then set the item to be inserted as the first node in 
  //    the list. Set head, current, and tail to point to this node.
  if (size == 0)
  {
    newElemPtr -> element = insElem;
    newElemPtr -> next = NULL;

    head = current = tail = newElemPtr;
  }
  else 
  {  
    // ELSE loop through all nodes, comparing the current element with 
    //   _insElem_. Only stop when _insElem_ less than  or equal to 
    //   the current element or you are at end of list. 
    while( (insElem >= tempPtr -> element) && (tempPtr -> next != NULL) )
      tempPtr = tempPtr -> next;


    // If _insElem_ is greater than the current element then insert it
    //   AFTER the current element.
    // Else insert it BEFORE.
    if( insElem >= tempPtr -> element )
    {
      // InsertAfter
  
      newElemPtr -> element = insElem;
      newElemPtr -> next = tempPtr -> next;
      tempPtr -> next = newElemPtr;
    }
    else
    {
      // InsertBefore
      
      newElemPtr -> next = tempPtr -> next;
      tempPtr -> next = newElemPtr;
      newElemPtr -> element = tempPtr -> element;
      tempPtr -> element = insElem;
    }

    current = newElemPtr;
  }

  // Update linked list size.
  size++;
  return;
}



// Reverse
//    - reverses the order of the elements in the list
template <class Etype>
void List<Etype>::Reverse()
{
  // Reverse the list only if the list is not empty.
  if (size > 0)
  {
     ListNode<Etype> *tempPtr;
       tempPtr = head;  // set pointer to point to head of list

    Array<Etype> myArray(1,size);

    // Loop through list and copy elements into an array.
    for (int i=1 ; i <= size ; i++)
    {
      myArray[i] = tempPtr -> element;
      
      tempPtr = tempPtr -> next;

    }
 
    tempPtr = head;  // set pointer to point to head of list
  
    // Loop through array and copy the elements from the array
    //   back into the linked list. Loop down, thus copying
    //   elements in reverse.
    for ( i=size ; i > 0 ; i--)
    {  
      tempPtr -> element = myArray[i];     

      tempPtr = tempPtr -> next;
    }

  }
  return;
}


// Splice
//    - parameters : spliceList - a list to be spliced into this list
//    - splices the values of spliceList into this list starting at the
//        position after the current value of this list. When the
//        function has completed, the current location indicator
//        should be set to be the first element of this list, if any
//        elements are in this list. The parameter list spliceList
//        should be empty when you are done, as you are not splicing
//        copies of the values of spliceList, but rather, you are
//        splicing the values themselves.
template <class Etype>
void List<Etype>::Splice(List& spliceList)
{
  // If the size of the original list is greater than 0 then 
  //   test the _spliceList_ list to determine if can be spliced
  //   with the original
  if ( size > 0 )
  {
    if ( spliceList.size > 0 )
    {
      ListNode<Etype> *tempPtr;
 
      // Loop through the _spliceList_ and take each node
      //   and move it to the original list by changing the 
      //   addresses it points to.
      for( int i = 0 ; i < spliceList.size ; i++ )
      {
        tempPtr = spliceList.current = spliceList.head;
        spliceList.current = spliceList.current -> next;        

        tempPtr -> next = current -> next;
        current -> next = tempPtr;
        current = tempPtr;
	spliceList.head = spliceList.current;
      }

      // Update the size of the newly formed larger list by adding
      //   the _spliceList_'s size to the original size.
      size += spliceList.size;
 
      // Clear the _spliceList_ list.
      spliceList.head = spliceList.current = spliceList.tail = NULL;
      spliceList.size = 0;     
    }
  }  
  else
  {
    // If the original list is empty then make the _spliceList_ list
    //   the new combined list.
    current = head = spliceList.head;
    tail = spliceList.tail;
    size = spliceList.size;

    // Clear the _spliceList_ list. 
    spliceList.head = spliceList.current = spliceList.tail = NULL;
    spliceList.size = 0;
  }
  return;
}


// ***********************************************



// List
//    - default constructor
template <class Etype>
List<Etype>::List()
{
   head = current = tail = NULL; 
   size=0; 
}


// List
//    - copy constructor
//    - parameters : origList - a previously allocated List object
//    - initializes the list to be a copy of origList
template <class Etype>
List<Etype>::List(const List<Etype>& origList)
{
   ListNode<Etype> *origListPtr = origList.head,
        *newListPtr; 

   if (origListPtr == NULL)  // then origList is empty
   {
      current = head = tail = NULL; 
      size=0; 
   }
   else   // origList is not empty; copy it node for node
   {
      // at least one node in origList; create that node
      newListPtr = new ListNode<Etype>; 
      newListPtr->element = origListPtr->element; 
      if (origListPtr == origList.current)  // place current pointer at 
         current = newListPtr;            // same spot in new list
      head = newListPtr; 
      origListPtr = origListPtr->next; 

      while (origListPtr !=NULL) // keep creating nodes as long as there
      {                         //  are nodes in origList
         newListPtr->next = new ListNode<Etype>; 
         newListPtr = newListPtr->next; 
         if (origListPtr == origList.current)
            current = newListPtr; 
         newListPtr->element = origListPtr->element; 
         origListPtr = origListPtr->next; 
      }
      newListPtr->next = NULL;   // last node points to NULL 
      tail = newListPtr; 
      size = origList.size;       
   }
}




// ~List
//    - destructor
//    - deallocates all dynamically allocated memory inside the list
template <class Etype>
List<Etype>::~List()
{
   Clear(); 
}



// Clear
//    - deletes all values from list, resulting in an empty list
template <class Etype>
void List<Etype>::Clear()
{

   ListNode<Etype> *deletionPtr = head; 
   current = head; 
   
   while (current != NULL)
   {
      current = current->next; 
      delete deletionPtr; 
      deletionPtr = current; 
   }

   head = current = tail = NULL; 
   size=0; 
}




// operator=
//    - parameters: origList - a previously allocated List object
//    - sets the the list to be a copy of origList
template <class Etype>
const List<Etype>& List<Etype>::operator=(const List<Etype>& origList)
{

   if (this!=&origList)
   {
      Clear(); 
     
      ListNode<Etype> *origListPtr = origList.head,
           *newListPtr;
 
      if (origListPtr == NULL)  // then origList is empty
      {
         current = head = tail = NULL;
         size=0;
      }
      else
      {
         newListPtr = new ListNode<Etype>;
         newListPtr->element = origListPtr->element;
         if (origListPtr == origList.current)
            current = newListPtr;
         head = newListPtr;
         origListPtr = origListPtr->next;
 
         while (origListPtr !=NULL)
         {
            newListPtr->next = new ListNode<Etype>; 
            newListPtr = newListPtr->next; 
            if (origListPtr == origList.current)
               current = newListPtr; 
            newListPtr->element = origListPtr->element; 
            origListPtr = origListPtr->next; 
         }
         newListPtr->next = NULL; 
         tail = newListPtr; 
         size = origList.size; 
      }
   }  // end if

   return *this;

} 




// InsertAfter
//    - parameters : newElem - an element of the list's type, to be inserted
//    - inserts newElem after current position in list
template <class Etype>
void List<Etype>::InsertAfter(Etype newElem)
{
   ListNode<Etype> *tempPtr = new ListNode<Etype>; 
   tempPtr->element = newElem; 
    
   if (size==0)
   {
      tempPtr->next=NULL; 
      current = head = tail = tempPtr;  
   }
   else
   {
      tempPtr->next = current->next; 
      current->next = tempPtr; 
      if (current == tail)
         tail = tempPtr; 
      current = tempPtr;
   }
   size++; 
}



// InsertBefore
//    - parameters : newElem - an element of the list's type, to be inserted
//    - inserts newElem before current position in list
template <class Etype>
void List<Etype>::InsertBefore(Etype newElem)
{
   ListNode<Etype> *tempPtr = new ListNode<Etype>;

   if (size==0)
   {
      tempPtr->element = newElem;
      tempPtr->next = NULL;
      current = head = tail = tempPtr;
   }
   else
   {
      tempPtr->element = current->element;
      tempPtr->next = current->next;
      current->element = newElem;
      current->next = tempPtr; 
      if (current == tail)
         tail = tempPtr; 
   }
   size++;
}



// Remove
//    - removes the element at the current postition of the list
template <class Etype> 
void List<Etype>::Remove()
{
   ListNode<Etype> *removePtr; 
   
   if (size==0)
   {
      Warn(size > 0, "Attempt to remove an element from an empty list."); 
      return; 
   }   
   else if (size==1)
   {
      delete current; 
      head = current = tail = NULL;
   }
   else if (current->next == NULL)   // deleting last element
   {
      removePtr = head; 
      while (removePtr->next != current)
         removePtr = removePtr->next; 
      removePtr->next = NULL; 
      delete current; 
      current = removePtr;
      tail = removePtr;  
   }
   else   // this is the case you would expect to reach most often
   {
      removePtr = current->next; 
      current->element = removePtr->element; 
      current->next = removePtr->next; 
      if (tail==removePtr)
         tail = current; 
      delete removePtr; 
   }
   size--; 
}




// Update
//    - parameters : updateElem - an element of the list's type
//    - replaces the value at the current position with updateElem
template <class Etype>
void List<Etype>::Update(Etype updateElem)
{  
   Warn(size > 0, "Cannot update an element in an empty list."); 
   if (size > 0)
      current->element = updateElem; 
}





// Head
//    - makes the first position in the list the current position
template <class Etype>
void List<Etype>::Head()
{
   current = head; 
}




// Tail
//    - makes the last position in the list the current position
template <class Etype>
void List<Etype>::Tail()
{
   current = tail; 
}





// operator++
//    - moves the current position one forward in the list
template <class Etype>
List<Etype>& List<Etype>::operator++(int)
{
   if (size > 0)   // if there are nodes in the list
      if (current->next != NULL)  // and we are not on the last one
         current =  current->next;   // increment the current pointer 
   return *this; 
}





// operator--
//    - moves the current position one backward in the list
template <class Etype>
List<Etype>& List<Etype>::operator--(int)
{
   if (current!=head)
   {
      ListNode<Etype> *beforePtr = head; 
      while (beforePtr->next != current)
         beforePtr = beforePtr->next; 
      current = beforePtr; 
   }
   return *this; 
}




// Retrieve
//    - returns the element at the current list position
template <class Etype>
Etype List<Etype>::Retrieve() const
{
   Assert(size > 0, "Cannot Retrieve an element from an empty list."); 
   return current->element;    
}




// Find 
//    - parameters : queryElem - an element of the list's type, to be searched for
//    - return value : a boolean yes or no
//    - searches list for queryElem...if found, make that position the current
//         position and return 1; otherwise, return 0
template <class Etype>
int List<Etype>::Find(Etype queryElem)
{
   ListNode<Etype> *searchPtr = head;
   while ((searchPtr !=NULL) && (searchPtr->element != queryElem))
      searchPtr = searchPtr->next; 
   if (searchPtr == NULL)
      return 0; 
   else
   {
      current = searchPtr; 
      return 1; 
   }
}




// Length
//    - return value : an integer representing the list's length
//    - returns the length of the list
template <class Etype>
int List<Etype>::Length() const
{
   return size; 
}



// Print
//    - writes the individual elements of the list to the output
//         stream object, and then returns that output stream object
template <class Etype>
void List<Etype>::Print() const
{
   ListNode<Etype>* outPtr = head; 

   if (size==0)
      cout << "< empty list >";  
   else
   { 
      cout << "< "; 
      while (outPtr!=NULL)  
      {
         cout << outPtr->element << " ";
         outPtr = outPtr->next; 
      } 
      cout << ">";
   } 
}

