arraylist.h

/************************************************************************
*																		*
*	File:		arraylist.h												*
*																		*
*	Author:		Robb T. Koether											*
*																		*
*	Date:		Jul 3, 2000												*
*																		*
*	Abstract:	This file contains the definition of the ArrayList 		*
*				template class											*
*																		*
************************************************************************/

#ifndef ARRAYLIST_H
#define ARRAYLIST_H

//	Header files

#include <iostream>
#include <string>
#include <cassert>

using namespace std;

/************************************************************************
*																		*
*	The ArrayList class definition										*
*																		*
************************************************************************/

template <class T>
class ArrayList
{
//	Public member functions

	public:

	//	Constructors

		ArrayList(int sz = 0, const T& value = T());
		ArrayList(const ArrayList<T>& lst);
	
	//	Destructor
	
		~ArrayList() {delete [] element;}

	//	Inspectors

		T& GetElement(int pos) const
			{assert(1 <= pos && pos <= size); return element[pos - 1];}
		int Size() const {return size;}
		bool Empty() const {return size == 0;}

	//	Mutators

		void SetElement(int pos, const T& value) {GetElement(pos) = value;}
		void Insert(int pos, const T& value);
		void Delete(int pos);
		void PushFront(const T& value) {Insert(1, value);}
		void PushBack(const T& value) {Insert(size + 1, value);  }
		T PopFront() {T value = GetElement(1); Delete(1); return value;}
		T PopBack() {T value = GetElement(size); Delete(size); return value;}
		void MakeEmpty()
			{delete [] element; capacity = 0; size = 0; element = NULL;}

	//	Facilitators
	
		void Input(istream& in);
		void Output(ostream& out) const;
	
	//	Operators
	
		ArrayList<T>& operator=(const ArrayList<T>& lst);
		T& operator[](int pos) const {return GetElement(pos);}

	//	Other functions
	
		void Swap(ArrayList<T>& lst);
		int Search(const T& value) const;
		int Search(const T& value, bool sorted) const;
		void Sort() {Sort(0, size - 1);}
		void Validate() const;

//	Protected member functions

	protected:
		void SetSize(int newCap);
		void MakeCopy();
		
//	Private member functions

	private:
		void Sort(int left, int right);

//	Data members

	protected:
		int capacity;	// Allocated space
		int size;		// Number of items in list
		T* element;		// Pointer to first item
};

//	ArrayList operators

template <class T>
istream& operator>>(istream& in, ArrayList<T>& lst);
template <class T>
ostream& operator<<(ostream& out, const ArrayList<T>& lst);

/************************************************************************
*																		*
*	Function:	ArrayList(int = 0, T& = T())							*
*																		*
*	Purpose:	This function will construct a list of the specified 	*
*				size													*
*																		*
************************************************************************/

template <class T>
ArrayList<T>::ArrayList(int cap, const T& value)
{
	capacity = cap;
	size = cap;

	if (size == 0)
		element = NULL;
	else
		element = new T[capacity];

	for (int i = 0; i < size; i++)
		element[i] = value;
	return;
}

/************************************************************************
*																		*
*	Function:	ArrayList(ArrayList&)									*
*																		*
*	Purpose:	This function will construct a list that is a copy of 	*
*				the specified list										*
*																		*
************************************************************************/

template <class T>
ArrayList<T>::ArrayList(const ArrayList<T>& lst)
{
	capacity = lst.capacity;
	size = lst.size;

	if (size == 0)
		element = NULL;
	else
		element = new T[capacity];

	for (int i = 0; i < size; i++)
		element[i] = lst.element[i];
	return;
}

/************************************************************************
*																		*
*	Function:	Insert													*
*																		*
*	Purpose:	This function will insert an element into the list at 	*
*				the specified position									*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Insert(int pos, const T& value)
{
	assert(1 <= pos && pos <= size + 1);
	
	if (size == capacity)
		if (capacity == 0)
			SetSize(1);
		else
			SetSize(2 * capacity);
	
	for (int i = size; i >= pos; i--)
		element[i] = element[i - 1];
	
	element[pos - 1] = value;
	size++;
	return;
}

/************************************************************************
*																		*
*	Function:	Delete													*
*																		*
*	Purpose:	This function will delete the element in the specified 	*
*				position												*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Delete(int pos)
{
	assert(1 <= pos && pos <= size);

	for (int i = pos; i < size; i++)
		element[i - 1] = element[i];

	size--;
	if (size < capacity/4)
		SetSize(capacity/2);
	
	if (capacity == 0)
		element = NULL;
		
	return;
}

/************************************************************************
*																		*
*	Function:	Input													*
*																		*
*	Purpose:	This function will extract a list from the input stream	*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Input(istream& in)
{
	MakeEmpty();			// Clear out old values
	char c;
	T value;
	
	in >> c;				// Read the first character
	assert(c == '{');		// Verify it is open brace
	
	in >> c;				// Read next character
	if (c == '}')			// List is empty
		return;				// Nothing else to read
		
	else					// List is not empty
	{
		in.putback(c);		// Put char back in input stream
		while(c != '}')		// Read until '}' is found
		{
			in >> value;	// Read the element
		 	PushBack(value);// Append the element to the list
		 	in >> c;		// Read the comma or close brace
		}
	}
	return;
}

/************************************************************************
*																		*
*	Function:	Output													*
*																		*
*	Purpose:	This function will insert a list into the output stream	*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Output(ostream& out) const
{
	out << "{";							// Write open brace
	if (size > 0)
	{
		for (int i = 0; i < size; i++)
			out << element[i] << ", ";	// Write element and comma
		out << "\b\b";					// Erase last comma
	}
	out << "}";							// Write close brace
	return;
}

/************************************************************************
*																		*
*	Function:	operator=												*
*																		*
*	Purpose:	This function will assign one list to another			*
*																		*
************************************************************************/

template <class T>
ArrayList<T>& ArrayList<T>::operator=(const ArrayList<T>& lst)
{
	if (this != &lst)						// Lists are distinct
	{
		delete [] element;					// Clear out old elements
		capacity = lst.capacity;
		size = lst.size;

	// 	Allocate memory
	
		if (size == 0)
			element = NULL;
		else
			element = new T[capacity];

	// Copy elements
	
		for (int i = 0; i < size; i++)
			element[i] = lst.element[i];
	}
	return *this;
}

/************************************************************************
*																		*
*	Function:	Swap													*
*																		*
*	Purpose:	This function will swap this list with the specified 	*
*				list													*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Swap(ArrayList<T>& lst)
{

//	Perform a swap of the three data members, not the allocated memory

	int tempMaxSize = lst.capacity;
	int tempSize = lst.size;
	T* tempElement = lst.element;

	lst.capacity = capacity;
	lst.size = size;
	lst.element = element;

	capacity = tempMaxSize;
	size = tempSize;
	element = tempElement;
	return;
}

/************************************************************************
*																		*
*	Function:	Search(T)												*
*																		*
*	Purpose:	This function will use a sequential search to search 	*
*				the unsorted list for the specified element and report 	*
*				its location											*
*																		*
*	Note:		If the element was not found, the function returns 0	*
*																		*
************************************************************************/

template <class T>
int ArrayList<T>::Search(const T& value) const 
{
	int pos;
	for (pos = 0; pos < size; pos++)
		if (element[pos] == value)
			break;

	if (pos == size)
		return 0;
	else
		return pos + 1; 
}

/************************************************************************
*																		*
*	Function:	Search(T, bool)											*
*																		*
*	Purpose:	This function will search the list for the specified 	*
*				element and report its location							*
*																		*
*	Note 1:		If the bool parameter is true, a binary search will be	*
*				used.  If it is false, a sequential search will be used.*
*																		*
*	Note 2:		The operator < must be defined on class T in order to 	*
*				use the binary search									*
*																		*
*	Note 3:		If the element was not found, the function returns 0	*
*																		*
************************************************************************/

template <class T>
int ArrayList<T>::Search(const T& value, bool sorted) const 
{
	if (!sorted)							// List is not sorted
		return Search(value);				// Do sequential search

//	Do a binary search 

	int left = 0;
	int right = size - 1;
	while (left <= right)
	{
		int middle = (left + right)/2;
		if (value < element[middle])		// Value is in left half
			right = middle - 1;
		else if (element[middle] < value)	// Value is in right half
			left = middle + 1;
		else								// Value was found
			return middle + 1;
	}
	return 0;								// Value was not found
}

/************************************************************************
*																		*
*	Function:	Sort(int, int)											*
*																		*
*	Purpose:	This function will use the quicksort algorithm to sort 	*
*				the list recursively									*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Sort(int left, int right)
{
	if (left < right)
	{
		T temp;		// Used to swap list elements
		
	//	Pivot
	
		if (element[right] < element[left])
		{
			temp = element[right];
			element[right] = element[left];
			element[left] = temp;
		}
	
	//	Partition the list
	
		T pivot = element[left];
		int i = left;
		int j = right + 1;
		do
		{
			do ++i; while (element[i] < pivot);
			do --j; while (pivot < element[j]);
			if (i < j)
			{
				temp = element[i];
				element[i] = element[j];
				element[j] = temp;
			}
		} while (i < j);
		temp = element[j];
		element[j] = element[left];
		element[left] = temp;
		
	//	Sort the sublists recursively
	
		Sort(left, j - 1);
		Sort(j + 1, right);
	}
	return;
}

/************************************************************************
*																		*
*	Function:	Validate												*
*																		*
*	Purpose:	To validate that the arraylist has a valid structure	*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::Validate() const
{
	assert(capacity >= 0);
	assert(0 <= size && size <= capacity);
	
	if (size == 0)
		assert(element == NULL);
	else
		assert(element != NULL);
	
	return;
}

/************************************************************************
*																		*
*	Function:	SetSize													*
*																		*
*	Purpose:	This function will reset the maximum size of the list 	*
*				to the specified size									*
*																		*
************************************************************************/

template <class T>
void ArrayList<T>::SetSize(int newCap)
{
//	Verify that new capacity is valid

	assert(newCap >= 0);

	capacity = newCap;
	T* new_array;
	
//	Allocate memory and copy elements

	if (capacity == 0)
	{
		size = 0;
		new_array = NULL;
	}
	else
	{
	//	Allocate memory
	
		new_array = new T[capacity];
	
	//	Get new size
	
		if (capacity < size)
			size = capacity;
		
	//	Copy elements
	
		for (int i = 0; i < size; i++)
			new_array[i] = element[i];
	}

//	Delete old memory

	delete [] element;
	element = new_array;
	return;
}

/************************************************************************
*																		*
*	Function:	operator>>												*
*																		*
*	Purpose:	This function will extract a list from the input stream	*
*																		*
************************************************************************/

template <class T>
istream& operator>>(istream& in, ArrayList<T>& lst)
{
	lst.Input(in);
	return in;
}

/************************************************************************
*																		*
*	Function:	operator<<												*
*																		*
*	Purpose:	This function will insert a list into the output stream	*
*																		*
************************************************************************/

template <class T>
ostream& operator<<(ostream& out, const ArrayList<T>& lst)
{
	lst.Output(out);
	return out;
}

#endif