// ******************************************************
// *                                                    *
// *  listfns.C (MP4)                                   *
// *                                                    *
// *  Implementation for the MP4 global functions       * 
// *                                                    *
// *  Author: Zaczek, Mariusz                           *
// *  Date:   2/25/1999                                 *
// *  Class:  Tu 11-1 , Chad Piper                      *
// *                                                    *
// ******************************************************

#include "listfns.h"
#include "singlist.h"

// Replace
//    - parameters : repList - the list to run the replacement on 
//                 : 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 Replace(List<Etype>& repList, const Etype oldVal, const Etype newVal)
{
   Warn(repList.Length() > 0, "Cannot update an element in an empty list.");

   // Test if list has elements ... i.e. is not empty.
   if (repList.Length() > 0)
   {
     repList.Head();      // Start at head

     // Loop throught the _repList_ list and if a value is found equal
     //   to _oldVal_ then set this nodes element equal to _newVal_
     for ( int i = 0 ; i < repList.Length() ; i++, repList++ )
     {
       if (repList.Retrieve() == oldVal)
         repList.Update(newVal);
     }
   }

  return;
}

  
// ToArray
//    - parameters : readList - a list to write into an Array
//    - 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> ToArray(const List<Etype>& readList)
{
  Array<Etype> myArray(1,readList.Length());

  readList.Head();  // Start at head of list

  // Loop through _readList_ list and copy each element to the array.
  for ( int i = 0 ; i <= readList.Length() ; i++, readList++ )
   myArray[i] = readList.Retrieve();

  return myArray;
}




// SortedInsert
//    - parameters : insList - the list to insert into
//                 : 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 SortedInsert(List<Etype>& insList, const Etype insElem)
{
  int length = insList.Length();

  // If _insList_ list is empty then insert the _insElem_ element 
  //   as the first element.
  if ( length == 0 )
  {
    insList.InsertAfter(insElem);
  }
  else
  {
    int position = 1;  // Counter to keep track of position in list.
    insList.Head();    // Start at head of list.

    // While the _insElem_ element to be inserted is bigger or equal
    //   to the current value and you are not yet at the end of the 
    //   list then keep increasing the list position and the counter.
    while ( insElem >= insList.Retrieve()  && position != length )
    {
      insList++;
      position++;
    }

   // If the _insElem_ element is greater than or equal to the current
   //   element then insert the _insElem_ element after the current.
   // Otherwise insert the _insElem_ before the current element.
   if ( insElem >= insList.Retrieve() )   
      insList.InsertAfter(insElem);
    else   
      insList.InsertBefore(insElem);

  }

  return;
}



// Reverse 
//    - parameters : revList - the list to reverse
//    - reverses the order of the elements in the list
template <class Etype>
void Reverse(List<Etype>& revList)
{
  int length = revList.Length();

  // Reverse only lists that have elements ... i.e. non-empty lists
  if ( length > 0 )
  {
    Array<Etype> myArray(1,length);
    
    revList.Head();   // Start at head of list.

    // Loop through the _revList_ list and assign the values to the array.
    for ( int i=1 ; i <= length ; i++, revList++ )
      myArray[i] = revList.Retrieve();
       
    revList.Head();   // Go back to the head of the list again.
 
    // Looping backwards through the array, set the values of the array
    //   equal to the elements in the linked list.
    for ( i=length ; i > 0 ; i--, revList++ )
      revList.Update(myArray[i]);
  }

  return;
} 




// Splice
//    - parameters : baseList - the list to be spliced into 
//                 : spliceList - a list to be spliced into the base list
//    - splices the values of spliceList into baselist starting at the 
//        position after the current value of baselist. When the
//        function has completed, the current location indicator of 
//        baselist should be set to be the first element of baselist, 
//        if any  elements are in baselist. 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 Splice(List<Etype>& baseList, List<Etype>& spliceList)
{

  // If the first list is not empty then continue.
  if (baseList.Length() > 0)
  {
    // If the second list is not empty then we can splice
    //   it to the first.
    if (spliceList.Length() > 0)
    {
      spliceList.Head();   // Start at head of list
  
      // Loop through the _spliceList_ list and insert it node by node
      //   into the _baseList_ list.
      for ( int i = 0 ; i < spliceList.Length() ; i++, spliceList++)
        baseList.InsertAfter(spliceList.Retrieve());

      // Clear the _spliceList_ list.
      spliceList.Clear();
    }
  }
  else
  {
    // Now, assuming the first _baseList_ list is empty then 
    //   copy the entire _spliceList_ list to the _baseList_ list.
    baseList = spliceList;

    // Clear the _spliceList_ list.
    spliceList.Clear();
  }

  return;
}


