/* This file contains the declaration of class List.

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

#ifndef LIST
#define LIST

#include <iostream.h>                // interactive I/O
#include <fstream.h>                 // file I/O

typedef double ListElement;          // array element type

/*
#include "Student.h"                 // alternate array element type
typedef Student ListElement;         //   (for Figure 12.17)
*/

class List
{

// -- the public section --

public:
   enum { MaxLength = 256 };         // number of array elements

   /***** Constructors *****/

   /* These functions are the class constructors for class List.

      Precondition:  A List object has been declared.
      Receive:       Len, the length of the array (default 0)
                     InitVal, the initial value of the array's
                       elements (optional)
      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(int Len = 0);
   List(int Len, ListElement InitVal);


   /***** Operations *****/
   /***---Input---***/
   /* 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
   ----------------------------------------------------------------*/
   friend istream& operator>>(istream& In, List& InList);


   /***---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);

   /*
      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& operator=(const List& Original);


   /***---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);              // nonconstant lists

   const ListElement& operator[](int i) const;  // constant lists



   /***---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);


// -- the private section --
private:

/********** data members **********/
   ListElement
      Array[MaxLength];               //    the array

   int
      Length_;                        //    array value counter

/******* private functions ********/
   int Split(                         //    quicksort utility
            int Low,                  //       sublist beginning
            int High);                //       sublist end
   void QuickSort(                    //    quick sort
            int Low,                  //       sublist beginning
            int High);                //       sublist end
};

#endif