/* This file contains the declaration of class List.

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

#include <iostream.h>                     // interactive i/o
#include <fstream.h>                      // file i/o

#include "Boolean.h"
#include "Strings.h"

typedef double ListElement;               // array element type

class List
{
protected:

/********** data members **********/
   ListElement                            // a pointer to a run-time
      *Array;                             //  allocated array

   int
      Length_;                            // # values in List

   enum
     {MaxLength = 1024};                  // maximum list length

/******* private functions ********/
   int Split(int Low, int High);

   void QuickSort(int First, int Last);

 public:

   /****** Constructors and Destructor ******/
   /*----- Class -----
      Precondition:  A List object has been declared.
      Receive:       NumValues, the size of the List being defined
                        (default 0)
      Postcondition: The List has been appropriately initialized
                        as a list that can hold NumValues values.
   ------------------------------------------------------------------*/
   List(int NumValues = 0);

   /*----- Copy -----
      Precondition:  The compiler needs a copy of a List.
      Receive:       Original, the List being copied
      Postcondition: The scalar and array members of this List are
                        distinct copies of the data members of
                        Original.
   ------------------------------------------------------------------*/
   List(const List& Original);

   /*----- Destructor -----
      Precondition:  A List object's lifetime is over.
      Postcondition: The storage allocated to that List is
                        deallocated; and its data members are
                        reset as an empty List.
   ------------------------------------------------------------------*/
   ~List(void)
    {
        delete [] Array;
        Array = 0;
        Length_ = 0;
    }


   /****** Operations and Members *****/
    /*----- Assignment -----

      Receive: A List object Original
      Return:  The List containing this function, its members
                  as distinct copies of those of Original
   ------------------------------------------------------------------*/
   List& operator=(const List& Original);

   /*--- Interactive Input ---
      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
                  In
      Assumption: The number of values in the input list
                     is <= MaxLength.
   ------------------------------------------------------------------*/
   friend istream& operator>>(istream& In, List& InList);

   /*--- File Input -----

      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
                       inputvalues and its Array member containing
                       the input values
                    True if operation successful, false otherwise
      Assumption:   The first line of the file has the number of
                       values in the list.
   ------------------------------------------------------------------*/
   Boolean Load(const Strings& FName);

   /*--- File Output -----

      Receive:      FileName, a Strings object containing the name
                       of an output file
      Output(File): The number of list values and the values
      Return:       The List object containing this function
                    True if operation successful, false otherwise
      Assumption:   The first line of the file now has the number of
                       values in the list.
   ------------------------------------------------------------------*/
   Boolean Write(const Strings& FName) const;

   /***---Output---***/
   /* Receive: An ostream (reference) object Out
               A List (reference) object OutList
      Output:  The values stored within OutList to Out, separated
                 by spaces
      Return:  Out
   ----------------------------------------------------------------*/
   friend ostream& operator<<(ostream& Out, const List& L);

   /***---Subscript---
      Receive: i, an index for a List element
      Return:  The value of the element in member Array with index i
      Note: Two forms are provided, the first for nonconstant
            arrays and the second for constant arrays.
   ----------------------------------------------------------------*/
   ListElement& operator[] (int i);

   /***---Length---
      Return:  The length of the list (the value stored in field
                  Length_).
   ----------------------------------------------------------------*/
   int Length(void) const { return Length_; }

   /***---Searches---***/
   /***---Linear search ---
      Receive:  SearchVal, a (ListElement) value
      Return:   The index of SearchVal, if it is present in
                   member Array, and -1 otherwise
   ----------------------------------------------------------------*/
   int LSearch(const ListElement & SearchVal) const;

   /***---Binary search ---
      Receive:  SearchVal, a ListElement value
      Return:   The index of SearchVal, if it is present in
                   member Array, and -1 otherwise
   ----------------------------------------------------------------*/
   int BSearch(const ListElement & SearchVal) const;

   /***---Find smallest value in a sublist ---
      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 IndexOfMin(int First, int Last) const;

   /***---Sorts---***/
   /***---Simple Selection Sort ---

      Return:   The List containing this function, its Array
                   member sorted into ascending order by simple
                   selection sort
   ----------------------------------------------------------------*/
   void SSort(void);

   /***---Quicksort ---

      Return:   The List containing this function, its Array
                   member sorted into ascending order by
                   quicksort
   ----------------------------------------------------------------*/
   void QSort(void);

};