#ifndef ORDERED_ARRAY_LIST_TYPE_INCLUDED
#define ORDERED_ARRAY_LIST_TYPE_INCLUDED


//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <cassert>
using namespace std;



//-----------------------------------------------------------------------------
// orderedArrayListType - The array list data type from chapter 3 of our text
//-------------------------------------------------------------------------JMMH
template <class T>
class orderedArrayListType
{
public:
	//Overload the assignment operator to perform deep copy
    const orderedArrayListType<T>& operator=(const orderedArrayListType<T> & old);

	//Function to determine whether the list is empty
	//Postcondition: Returns true if the list is empty; 
 	//        	    otherwise, returns false.
    bool isEmpty() const;

	//Function to determine whether the list is full
	//Postcondition: Returns true if the list is full; 
 	//               otherwise, returns false.
    bool isFull() const;

	//Function to determine the number of elements in the list
	//Postcondition: Returns the value of length.
    int listSize() const;

	//Function to determine the size of the list
 	//Postcondition: Returns the value of maxSize.
    int maxListSize() const;

	//Function to output the elements of the list
	//Postcondition: Elements of the list are output on the 
 	//               standard output device.
    void print() const;

	//Function to determine whether the item is the same 
 	//as the item in the list at the position specified by location
	//Postcondition: Returns true if the list[location] 
	//               is the same as the item; otherwise, 
	//		     returns false.
    bool isItemAtEqual(int location, const T& item) const;

	//Function to remove the item from the list at the 
	//position specified by location 
	//Postcondition: The list element at list[location] is 
	//               removed and length is decremented by 1.
	//       If location is out of range, an appropriate message
	//       is displayed.
	void removeAt(int location);

	//Function to retrieve the element from the list at the  
	//position specified by location 
	//Postcondition: retItem = list[location] 
	//      If location is out of range, an appropriate 
	//      message is displayed.
    void retrieveAt(int location, T& retItem);

	//Function to remove all the elements from the list 
	//After this operation, the size of the list is zero.
 	//Postcondition: length = 0;
    void clearList();

	// inserts in an ordered fashion
 	void insertOrd(const T&);
	

	// searches for item in the ordered list
	// returns position if finds it, -1 if not
	int binarySearch(const T& item);


	//Postcondition: If the item is found, returns the location 
	//               in the array where the item is found; 
   	//               otherwise, returns -1.
    int seqSearch(const T& item);

	//Function to remove an item from the list. The parameter 
	//removeItem specifies the item to be removed.
	//Postcondition: If removeItem is found in the list,
	//      it is removed from the list and length is 
	//      decremented by one.
    void remove(const T& removeItem);

	//constructor
	//Creates an array of the size specified by the 
	//parameter size. The default array size is 100.
	//Postcondition: The list points to the array, length = 0, 
	//               and maxSize = size
    orderedArrayListType(int size = 100);

	//copy constructor - performs deep copy
    orderedArrayListType(const orderedArrayListType<T>& otherList); 

	//destructor
	//Deallocates the memory occupied by the array.
    ~orderedArrayListType();

private:
    T *list; 			//array to hold the list elements
    int length;		    //variable to store the length of the list
    int maxSize;		//variable to store the maximum size of the list

	//Private function to insert an item in the list at the 
	//position specified by location. The item to be inserted 
	//is passed as a parameter to the function.
	//Postcondition: Starting at location, the elements 
 	//               of the list are shifted down, 
 	//               list[location] = insertItem;, and
 	//               length++;    
 	//       If the list is full or location is out of
	//	   range, an appropriate message is displayed.    
    void insertAt(int location, const T& insertItem);

};



template <class T>
bool orderedArrayListType<T>::isEmpty() const
{
	return (length == 0);
}


template <class T>
bool orderedArrayListType<T>::isFull() const
{
	return (length == maxSize);
}


template <class T>
int orderedArrayListType<T>::listSize() const
{
	return length;
}


template <class T>
int orderedArrayListType<T>::maxListSize() const
{
	return maxSize;
}


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


template <class T>
bool orderedArrayListType<T>::isItemAtEqual(int location, const T& item) const
{
	return(list[location] == item);
}


template <class T>
void orderedArrayListType<T>::insertAt(int location, const T& insertItem)
{
	if(location < 0 || location >= maxSize)
		cerr<<"The position of the item to be inserted "
			<<"is out of range"<<endl;
	else
		if(length >= maxSize)  //list is full
			cerr<<"Cannot insert in a full list"<<endl;
		else
		{
			for(int i = length; i > location; i--)
				list[i] = list[i - 1];	//move the elements down

			list[location] = insertItem;	//insert the item at the 
 										//specified position

			length++;	//increment the length
		}
} //end insertAt


template <class T>
void orderedArrayListType<T>::removeAt(int location)
{
	if(location < 0 || location >= length)
    	cerr<<"The location of the item to be removed "
			<<"is out of range"<<endl;
	else
	{
   		for(int i = location; i < length - 1; i++)
	 		list[i] = list[i+1];

		length--;
	}
} //end removeAt


template <class T>
void orderedArrayListType<T>::retrieveAt(int location, T& retItem)
{
	if(location < 0 || location >= length)
    	cerr<<"The location of the item to be retrieved is "
			<<"out of range"<<endl;
	else
		retItem = list[location];
} // retrieveAt


template <class T>
void orderedArrayListType<T>::clearList()
{
	length = 0;
} // end clearList


template <class T>
int orderedArrayListType<T>::seqSearch(const T& item)
{
	int loc;
	bool found = false;

	for(loc = 0; loc < length; loc++)
	   if(list[loc] == item)
	   {
		found = true;
		break;
	   }

	if(found)
		return loc;
	else
		return -1;
} //end seqSearch


template <class T>
void orderedArrayListType<T>::remove(const T& removeItem)
{
	int loc;

	if(length == 0)
		cerr<<"Cannot delete from an empty list."<<endl;
	else
	{
		loc = seqSearch(removeItem);

		if(loc != -1)
			removeAt(loc);
		else
			cout<<"The tem to be deleted is not in the list."
				<<endl;
	}

} //end remove


template <class T>
orderedArrayListType<T>::orderedArrayListType(int size)
{
	if(size < 0)
	{
		cerr<<"The array size must be positive. Creating "
 			<<"an array of size 100. "<<endl;

 	   maxSize = 100;
 	}
 	else
 	   maxSize = size;

	length = 0;

	list = new T[maxSize];
	assert(list != NULL);
}



template <class T>
orderedArrayListType<T>::~orderedArrayListType()
{
	delete [] list;
}


	//copy constructor
template <class T>
orderedArrayListType<T>::orderedArrayListType
                   (const orderedArrayListType<T>& otherList)
{
   maxSize = otherList.maxSize;
   length = otherList.length;
   list = new T[maxSize]; 	//create the array
   assert(list != NULL);	//terminate if unable to allocate
 							//memory space

   for(int j = 0; j < length; j++)  //copy otherList
 	   list [j] = otherList.list[j];
}//end copy constructor


template <class T>
const orderedArrayListType<T>& orderedArrayListType<T>::operator=
			(const orderedArrayListType<T>& otherList)
{
	if(this != &otherList)	//avoid self-assignment
	{				   
	   delete [] list;				   
	   maxSize = otherList.maxSize;		   
       length = otherList.length;			   
	  
       list = new T[maxSize];		   
	   assert(list != NULL);			   

       for(int i = 0; i < length; i++)	   
	   	    list[i] = otherList.list[i];	   
	}

    return *this;					   	   
}


template<class T>
void orderedArrayListType<T>::insertOrd(const T& item)
{
	int first = 0;
	int last = length - 1;
	int mid;

	bool found = false;

	if(length == 0)   //list is empty
    {
        list[0] = item;
        length++;
    }
	else
		if(length == maxSize)
			cerr<<"Cannot insert into a full list."<<endl;
		else
		{
			while(first <= last && !found)
			{
				mid = (first + last) / 2;

				if(list[mid] == item)
					found = true;
				else
					if(list[mid] > item)
						last = mid - 1;
					else
						first = mid + 1;
			}//end while

			if(found)
	   			cerr<<"The insert item is already in the list. "
					<<"Duplicates are not allowed.";
			else
			{
				if(list[mid] < item)
					mid++;

				insertAt(mid, item);
			}
		}
}//end insertOrd

template<class T> 
int orderedArrayListType<T>::binarySearch(const T& item)
{
	int first = 0;
	int last = length - 1;
	int mid;

	bool found = false;

	while(first <= last && !found)
	{
		mid = (first + last) / 2;

		if(list[mid] == item)
		   found = true;
		else
		   if(list[mid] > item)
			last = mid - 1;
		   else
			first = mid + 1;
	}

	if(found) 
   	   return mid;
	else
		return -1;
}//end binarySearch


#endif