/* This file contains the implementation for class List.

-----------------------------------------------------------------*/

#include "List.h"

#include <stdlib.h>

/*----------------------------------------------------------------
   This function is one class constructor for class List.

   Precondition:  A List object has been declared.
   Receive:       Len, the number of elements (default 0)
   		    that will be used in the list
   Output:        An error message if Len > MaxLength
   Postcondition: Length_ = Len.
-----------------------------------------------------------------*/

List::List(int Len)
{
   if (Len < 0 || Len > MaxLength)
   {
      cerr << "\n*** List: Length value " << Len
           << " exceeds limit - using 0!\n";
      Length_ = 0;
   }

   Length_ = Len;
}

/*----------------------------------------------------------------
   This function is another class constructor for class List.

   Precondition:  A List object has been declared.
   Receive:       Len, the number of element
		  InitVal, the initial value of the array's
                    elements
   Output:        An error message if Len > MaxLength
   Postcondition: The List has been initialized as a list of
                    Len elements, each with the value InitVal.
-----------------------------------------------------------------*/
List::List(int Len, ListElement InitVal)
{
   if (Len < 0 || Len > MaxLength)
   {
      cerr << "\n*** List: Length value " << Len
           << " exceeds limit - using 0!\n";
      Length_ = 0;
   }

   Length_ = Len;

   for (int i = 0; i < Length_; i++)
      Array[i] = InitVal;
}

/*----------------------------------------------------------------
   This function performs interactive input of a List object.
   It assumes that the length of the List has been previously
   initialized.

   Receive: An istream (reference) object In
            A List (reference) object InList
   Input:   A sequence of InList.Length_ ListElement values
              from In
   Return:  InList, with the input values stored in its Array
              elements
            In
------------------------------------------------------------------*/

istream& operator>>(istream& In, List& InList)
{
   for (int i = 0; i < InList.Length_; i++)
      In >> InList.Array[i];

   return In;
}

/*----------------------------------------------------------------
   This function performs screen output for a List object.

   Receive: An ostream (reference) object Out
            A List (reference) object OutList, to Out
   Output:  The values stored within OutList, separated by spaces
   Return:  Out
------------------------------------------------------------------*/

ostream& operator<<(ostream& Out, const List& OutList)
{
   for (int i = 0; i < OutList.Length_; i++)
      Out << OutList.Array[i] << ' ';

   return Out;
}

/*----------------------------------------------------------------
   operator= makes a copy of a List object.

   Receive:  Original, a List object
   Return:   the object containing this function, with its members
               as copies of those of Original, and a reference to
               this List (for chained assignments)
------------------------------------------------------------------*/

List& List::operator=(const List& Original)
{
   Length_ = Original.Length_;       // copy scalar member

   for (int i = 0; i < Length_; i++) // copy array member
      Array[i] = Original.Array[i];

   return *this;                     // return this object
}

/*----------------------------------------------------------------
   This function provides access to the values stored within a List.

   Receive: i, an index for a List element
   Return:  The value of the element in member Array with index i
------------------------------------------------------------------*/

ListElement& List::operator[] (int i)
{
   if (i >= 0 && i < Length_)
      return Array[i];

   cerr << "\n***Subscript: invalid attempt to access element "
        << i << " !\n";
   exit (-1);
}

const ListElement& List::operator[] (int i) const
{
   if (i >= 0 && i < Length_)
      return Array[i];

   cerr << "\n***Subscript: invalid attempt to access element "
        << i << " !\n";
   exit (-1);
}

/*----------------------------------------------------------------
   LSearch finds the index of a value SearchVal in a List.

   Receive:  SearchVal, a (ListElement) value;
   Return:   the index of SearchVal, if it is present in member
               Array, and -1 otherwise
------------------------------------------------------------------*/

int List::LSearch (const ListElement& SearchVal) const
{
   for (int i = 0; i < Length_; i++) // for each element:
      if (Array[i] == SearchVal)     //   if SearchVal at location i
         return i;                   //     return its index

   return -1;                        // SearchVal not found
}

/*----------------------------------------------------------------
   IndexOfMin finds the index of the smallest value in a List.

   Receive: First, the index of the first element to be examined
            Last, the index of the last element to be examined
   Return:  The index of the smallest value in the examined elements
-------------------------------------------------------------------*/

int List::IndexOfMin(int First, int Last) const
{
   if ((First > Last) || (Last >= Length_))
   {
      cerr << "\n*** IndexOfMin: invalid index(s) received: "
           << First << ':' << Last << "!\n";
      exit (-1);
   }

   int
      MinPos = First;

   for (int j = First+1; j <= Last; j++) // for each j > First:
      if (Array[j] < Array[MinPos])      //   if j-th elem. is smaller
         MinPos = j;                     //     save value of j

   return MinPos;                        // return index of smallest
}

/*---Swap---*/

static void Swap(ListElement& A, ListElement& B)
{
   ListElement
      Temp;

   Temp = A; A = B; B = Temp;
}

/*----------------------------------------------------------------
   SSort sorts a List into ascending order.

   Return:   The List containing this function,
               its Array member sorted into ascending order
------------------------------------------------------------------*/

void List::SSort(void)
{
//   if (Length_ <= 1)
//      return;

   int
      MinPos;

   for (int i = 0; i < Length_ - 1; i++)
   {
      MinPos = IndexOfMin(i, Length_ - 1);
      Swap(Array[i], Array[MinPos]);
   }
}

/*----------------------------------------------------------------
   BSearch finds the index of a value SearchVal in a List.

   Receive: SearchVal, a (ListElement) value
   Return:  The index of SearchVal, if it is present in this List,
              and -1 otherwise.
------------------------------------------------------------------*/

int List::BSearch(const ListElement& SearchVal) const
{
   int
      First = 0,                         // index of first value
      Last = Length_ - 1,                // index of last value
      Middle;                            // index of middle value

   while (First <= Last)                 // while sublist is not empty
   {
      Middle = (First + Last) / 2;       //   find middle element

      if (SearchVal == Array[Middle])    //   if it's the value sought
         return Middle;                  //     return its index
      else if (SearchVal < Array[Middle])//   else if it's in 1st half
         Last = Middle - 1;              //     adjust value of Last
      else                               //   else (it's in 2nd half)
         First = Middle + 1;             //     adjust value of First
   }
                                         // if we reach this point,
   return -1;                            //   SearchVal is not in
                                         //   the Array
}

/*----------------------------------------------------------------
   This function splits a List into two subLists, using the first
   element as pivot, and returns the index of the element about
   which the List was divided.

   Receive:  Low, the index of the first element
             High, the index of the last element
   Return:   The List containing this function,
               with all elements < the pivot to the left of the pivot
               and all elements > the pivot to the right of the pivot
             The index of the element about which L was split
---------------------------------------------------------------------*/

int List::Split(int Low, int High)
{
   int
      Left = Low,                        // index of first element
      Right = High;                      // index of last element
   ListElement
      Pivot = Array[Low];                // pivot element

   while (Left < Right)                  // while indices haven't met
   {
      while (Array[Right] > Pivot)       // scan right to left to find
         Right--;                        //   elem smaller than pivot

      while ((Left < Right) &&           // scan left to right to find
       (Array[Left] <= Pivot))           //   elem larger than pivot
         Left++;

      if (Left < Right)                  // if indices haven't met
         Swap(Array[Left], Array[Right]);//   exchange the two elems
   }

   Array[Low] = Array[Right];            // switch element in split
   Array[Right] = Pivot;                 // position with pivot

   return Right;                         // return split position
}

/*----------------------------------------------------------------
   This function sorts a list using the quicksort method.

   Receive:  Low, the index of the first element
             High, the index of the last element
   Return:   The List containing this function, in ascending order
------------------------------------------------------------------*/

void List::QuickSort(int Low, int High)
{
   int
      Mid;                          // index of split point

   if (Low < High)                  // if list has 2 or more items
   {
      Mid = Split(Low, High);       //   split the list
      QuickSort(Low, Mid-1);        //   recursively sort left half
      QuickSort(Mid+1, High);       //   recursively sort right half
   }
}

/*----------------------------------------------------------------
   This function is the interface to QuickSort(), so that programs
   using the function need not pass the indices of the first and
   last elements.

   Return: The List containing this function, in ascending order
------------------------------------------------------------------*/

void List::QSort(void)
{
//   if (Length_ <= 1)
//      return;

   QuickSort(0, Length_ - 1);
}