/* This file contains the implementation for class List.

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

#include "List.h"

#include <assert.h>
#include <stdlib.h>

/*-----------------------------------------------------------------
   This function constructs a List object.

   Precondition:  A List object has been declared.
   Receive:       NumValues, the size of the list (default 0)
   Postcondition: In the List object containing this function,
                     Length_ is equal to NumValues, and
                     the Array member is either a NULL pointer,
                     or points to an array of NumValues elements.
------------------------------------------------------------------*/

List::List(int NumValues)
{
   Length_ = NumValues;        // set List length indicator

   if (Length_ == 0)           // if default length
      Array = 0;               //   set ptr to NULL address
   else                        // otherwise, allocate anonymous array
   {                           //   having the specified length
      Array = new ListElement [NumValues];
      assert(Array != 0);
   }
}

/*-----------------------------------------------------------------
   This function is the copy constructor for class List.

   Precondition:   The compiler needs a copy of a List.
   Receive:        Original, the List object to be copied
   Postcondition:  The List containing this function is a complete
                      copy of the List named Original.
------------------------------------------------------------------*/

List::List(const List& Original)
{
   Length_ = Original.Length_;           // copy the scalar member
                                         // copy the array member
   if (Length_ > 0)                      // if Original has an array:
   {
      Array = new ListElement [Length_]; //   allocate a new array
      assert(Array != 0);                //   verify success

      for (int i = 0; i < Length_; i++)  //   copy the array member
         Array[i] = Original.Array[i];
   }
   else                                  // else
      Array = 0;                         //   set Array to null address
}

/*-----------------------------------------------------------------
   This function permits the assignment 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)
{
   if (this != &Original)
   {
      delete [] Array;                       // destroy previous array
      Length_ = Original.Length_;            // copy scalar member
      if (Length_ > 0)                       // copy  Array member
      {
         Array = new ListElement [Length_];  // allocate a new array
         assert(Array != 0);                 // verify success

         for (int i = 0; i < Length_; i++)   // copy the array member
            Array[i] = Original.Array[i];
      }
      else
         Array = 0;                          // set Array to NULL
   }
   return *this;                             // return this object
}

/*-----------------------------------------------------------------
   This function performs keyboard input for a List object,
   assuming that it has been constructed to hold the number of
   values in the input list.

   Receive: An istream (reference) object In containing n values
            A List (reference) object InList, with
               its Length_ member equal to n, and
               its Array member pointing to an array of n elements
   Input:   A sequence of n ListElement values, from In
   Return:  InList, with the input values stored in the array
              pointed to by Array
------------------------------------------------------------------*/

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

  return In;
}

/*-----------------------------------------------------------------
   This function performs keyboard input for a List object, assuming
   that a bound exists on the number of values in the input list.

   Receive: An istream (reference) object In
            A List (reference) object InList
   Input:   A sequence of n numbers, 0 < n <= MaxLength, from In
   Return:  InList, with the input values stored in the first n
               array elements, its Length_ member set to n
------------------------------------------------------------------*/

/*
istream& operator>>(istream& In, List& InList)
{
   ListElement
      Buffer[List::MaxLength];             // fixed-size array

   InList.Length_ = 0;                     // initialize counter
   In >> Buffer[InList.Length_];           // read a value into Buffer
   while (!In.eof() &&                     // while more data
      (InList.Length_ < List::MaxLength))  //   and Buffer not full:
   {
      InList.Length_++;                    //   update counter
      In >> Buffer[InList.Length_];        //   read next value
   }                                       //     into Buffer

   if (InList.Length_ == List::MaxLength)
      cerr << "\nWarning: List filled ! Values may be unread...\n";

   delete [] InList.Array;                 // deallocate old array

   InList.Array =
       new ListElement[InList.Length_];    // allocate new array
   assert(InList.Array != 0);              // verify success

   for (int i = 0; i < InList.Length_; i++)// copy values from Buffer
      InList.Array[i] = Buffer[i];         //   into the new array

  return In;
}
*/

/*-----------------------------------------------------------------
   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 whose index
              is i
------------------------------------------------------------------*/

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

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

/*-----------------------------------------------------------------
   This function fills a List object with data from a file,
   assuming that the first line of the file is the number of values
   in the list.

   Receive:      FileName, a Strings object containing the name of
                    an input file
   Input (File): The number of list values and the values
   Return:       The List object containing this function, its
                    Length_ member containing the number of input
                    values and its Array member containing the
                    input values
                 True if operation successful, false otherwise
------------------------------------------------------------------*/

Boolean List::Load(const Strings& FileName)
{
   fstream
      InStream(FileName, ios::in);    // open stream to input file

   if (InStream.fail())               // if not successful
   {
      cerr << "\n*** Load: Unable to open "
           << FileName << ".\n";
      return False;                   // ... indicate failure
   }

   InStream >> Length_;               // read the number of values

   delete [] Array;                   // deallocate old array

   Array = new ListElement[Length_];  // allocate right-sized array
   assert(Array != 0);                // verify success

   for (int i = 0; i < Length_; i++)  // fill it with input values
      InStream >> Array[i];

   InStream.close();                  // close the stream

   return True;                       // indicate success
}

/*-----------------------------------------------------------------
   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
}

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

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

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

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

void List::SSort(void)
{
   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)
{
   QuickSort(0, Length_ - 1);
}