/**************************************************************************************************/
/*                                                                                                */
/*  Name:  DarC KonQuesT                                                                          */
/*  Program:  #2                                                                                  */
/*  Date:  2005.2.8                                                                               */
/*  Purpose:                                                                                      */
/*  listType.h - provided by book author for creating, monitoring, and manipulating a list        */
/*                                                                                                */
/*                                                                                                */
/*                                                                                                */
/**************************************************************************************************/

#ifndef H_listType
#define H_listType

#include <iostream>
#include <cassert>
#include "stockType.h"


using namespace std;

template <class elemType>
class listType
{
public:
	
  bool search(elemType);
  bool remove(elemType);
    
    bool isEmpty();
	  //Returns true if the list is empty, false otherwise
    bool isFull();
	  //Returns true if the list is full, false otherwise
    int getLength();
	  //Returns the length of the list, the number of
	  //elements currently in the list
    int getMaxSize();
	  //Returns the maximum number of elements that can
	  //be stored in the list
    void sort();  
  	  //Sorts the list
   	  //Post: the list elements are in ascending order
    void print() const; 
  	  //Outputs the elements of the list
    void insertAt(const elemType& item, int position);
	  //Post: list[position] = item; length++;
	  //If the position is out of range, the program is aborted

    listType(int listSize = 50); 
 	  //constructor
  	  //Creates an array of the size specified by the
  	  //parameter listSize. The default array size is 50
  	  //Post: list contain the base address of the array,
  	  //      length = 0 and maxsize =listSize

    ~listType(); 
  	  //destructor
  	  //delete all elements of the list
  	  //Post: the array list is deleted
protected:
    int maxSize; //maximum number that can be 
    		     //stored in the list
    int length;  //number of elements in the list
    elemType *list; //pointer to the array that holds the
 					//list elements
};


/*  Name:  search                                                                                                     */
/*  Purpose:  return (true/false) whether or not a search_string is found in the array                                */
/*  Parameters:  elemType search_string                                                                               */
/*  Preconditions:  Array is set up and search_string is supplied                                                     */
/*  Postconditions:  User knows if the search_string was found by return true/false                                   */

template<class elemType>
bool listType<elemType>::search(elemType search_string) {
  bool found = false; 
  for(int i = 0; i < length; i++)
  {
    if(list[i] == search_string)
      return true;
  }
  return false;
}
  

/*  Name:  remove                                                                                                     */
/*  Purpose:  Remove a item from the array                                                                            */
/*  Parameters:  elemType remove_me                                                                                   */
/*  Preconditions:  Array is set up and remove_me is supplied                                                         */
/*  Postconditions:  remove_me is found and removed, and array is shifted, OR it returns false if record not found    */

template<class elemType>
bool listType<elemType>::remove(elemType remove_me) {

  elemType temp;
  
  if(search(remove_me) == false) {
        cout << endl << "Error:  Record not found!" << endl;
        return false;
  }
  else if(search(remove_me) == true) 
    for(int i = 0; i < length; i++)
        {
          if(list[i] == remove_me)
          {
            while(i < length)
            {
              temp = list[i + 1];
              list[i] = list[i + 1];
              i++;

            }

          }      
          return true;  
        }
  }


  
/*  Name:  isEmpty()                                                                                                  */
/*  Purpose:  Tell user if the list is empty                                                                          */
/*  Parameters:  None                                                                                                 */
/*  Preconditions:  list exists                                                                                       */
/*  Postconditions:  User knows if list is empty                                                                      */

template<class elemType>
bool listType<elemType>::isEmpty()
{
	return (length == 0);
}


/*  Name:  isFull()                                                                                                   */
/*  Purpose:  Tells user if list is full - can't hold anymore without overflow                                        */
/*  Parameters:  None                                                                                                 */
/*  Preconditions:  List exists                                                                                       */
/*  Postconditions:  User knows if list is full                                                                       */

template<class elemType>
bool listType<elemType>::isFull()
{
	return (length == maxSize);
}


/*  Name:  getLength()                                                                                                */
/*  Purpose:  Return the size of the list                                                                             */
/*  Parameters:  None                                                                                                 */
/*  Preconditions:  List exists                                                                                       */
/*  Postconditions:  User knows length of list                                                                        */

template<class elemType>
int listType<elemType>::getLength()
{
	return length;
}


/*  Name:  getMaxSize()                                                                                               */
/*  Purpose:  Return maximum size of list to user                                                                     */
/*  Parameters:  None                                                                                                 */
/*  Preconditions:  List exists and maxSize is set                                                                    */
/*  Postconditions:  User knows maxSize of list                                                                       */

template<class elemType>
int listType<elemType>::getMaxSize()
{
	return maxSize;
}


/*  Name:  listType - constructor                                                                                     */
/*  Purpose:  Initialize length, maxSize, and setup list pointer to array                                             */
/*  Parameters:  listSize                                                                                             */
/*  Preconditions:  listSize is supplied                                                                              */
/*  Postconditions:  Variables are initialized                                                                        */

template<class elemType>
listType<elemType>::listType(int listSize) 
{
	maxSize = listSize;
	length = 0;
	list = new elemType[maxSize];
}



/*  Name:  ~listType - destructor                                                                                     */
/*  Purpose:  Deallocate memory used by list                                                                          */
/*  Parameters:  None                                                                                                 */
/*  Preconditions:  list had been allocated                                                                           */
/*  Postconditions:  list is deallocated                                                                              */

template<class elemType>
listType<elemType>::~listType()  //destructor
{
	delete [] list;
}



/*  Name:  sort()                                                                                                     */
/*  Purpose:  Sort list in ascending order                                                                            */
/*  Parameters:   None                                                                                                */
/*  Preconditions:  List is created and filled with values                                                            */
/*  Postconditions: List is sorted in asending order                                                                  */

template<class elemType>
void listType<elemType>::sort()   //selection sort
{
	int i, j;
	int min;
	elemType  temp;

	for(i = 0; i <length; i++)
	{
		min = i;
		for(j = i+1; j < length; ++j)
		   if(list[j] < list[min])
			min = j;
		temp = list[i];
		list[i] = list[min];
		list[min] = temp;
	}//end for
}//end sort


/*  Name:  print()                                                                                                    */
/*  Purpose:  Print all items in list                                                                                 */
/*  Parameters:  None                                                                                                 */
/*  Preconditions:  List is created and filled with data                                                              */
/*  Postconditions:  List is printed on screen                                                                        */

template<class elemType>
void listType<elemType>::print() const
{
	int i;
	for(i = 0; i < length; ++i)
		cout<<list[i]<<"  ";
	cout<<endl;
}//end print


/*  Name:  insertAt                                                                                                   */
/*  Purpose:  Insert an item in the list at a certain position                                                        */
/*  Parameters: const elemType& item, int position                                                                    */
/*  Preconditions:  List is setup, item and position are supplied                                                     */
/*  Postconditions:  item is inserted in the list at [position]                                                       */

template<class elemType>
void listType<elemType>::insertAt(const elemType& item, int position)
{
	assert(position >= 0 && position < maxSize);
	list[position] = item;
	length++;
}

#endif