/*
 * Programmer:	Nicholas Williams
 * e-mail:     nwaussie@cats.ucsc.edu
 * Class:		CMP109
 * Instructor:	I. Pohl
 *
 * Date:			5/8/96
 * Compiler:	Borland Turbo C/C++ v4.5
 * System:		Compaq 486DX4-100MHz
 * Language:	C++
 *
 * This Program implements a doubley linked list form of a double
 * ended queue (deque). It first runs a test of the deques's
 * member functions using arditrary char "input". It then asks the
 * user to input a single word. It tests the word to see if it is a
 * palindrom and then sorts the letters of the word. It repeats these
 * steps for integer numbers (less than 32767) and for groups of words
 * (eg. the cat ate the dog).
 */

#include<iostream.h>
#include<assert.h>
#include<cstring.h>

// CLASS DEFINITIONS ==============================================
template <class T>
class deque	{
	public:
		deque()	{ reset(); }
		deque(const deque& old);
		~deque()	{ release(); }
		void	reset()	{ top = bottom = 0; }
		void	release();
		T	pop_top();
		T	pop_bot();
		void	push_top(T item);
		void	push_bot(T item);
		void	sort();
		void	print() const;
		T	top_of()	const	{ return(top->data); }
		T	bottom_of()	const	{ return(bottom->data);	}
		int	empty() const	{ return (top == 0 || bottom == 0); }
	private:
		struct listelem	{
			T	data;
			listelem*	next;
			listelem*	prev;
		};

		listelem*	top;
		listelem*	bottom;
};

// Member Function Declarations =======================================

// COPY CONSTRUCTOR: Performs a deep copy of deque old.
template <class T>
deque<T>::deque(const deque<T>& old)
{
	listelem*	oldtop = old.top;
	listelem*	oldbot = old.bottom;

	reset();
	while(oldtop != 0 && oldbot != 0)	{
		push_bot(oldtop->data);
		oldtop = oldtop->next;
	}
}

// Removes all items from the deque by popping them off
template <class T>
void deque<T>::release()
{
	while(!empty())
		pop_top();
}

// Pops the top item off the deque and deallocates that item's
// memory.
template <class T>
T	deque<T>::pop_top()
{
	T	item;
	listelem*	temp = top;

	if(!empty())	{
		item = top->data;
		if(top->next == 0)
			reset();
		else	{
			(top->next)->prev = 0;
			top = top->next;
		}
	}
	delete temp;
	return(item);
}

// Pops the bottom item off the deque and deallocates that item's
// memory.
template <class T>
T	deque<T>::pop_bot()
{
	T	item;
	listelem*	temp = bottom;

	if(!empty())	{
		item = bottom->data;
		if(bottom->prev == 0)
			reset();
		else	{
			(bottom->prev)->next = 0;
			bottom = bottom->prev;
		}
	}
	delete temp;
	return(item);
}

// Pushes an item on to the top of the deque by allocating
// memory.
template <class T>
void	deque<T>::push_top(T item)
{
	listelem* temp = new listelem;
	assert(temp != 0);

	temp->data = item;
	temp->next = top;
	temp->prev = 0;

	top = temp;
	if(bottom == 0)
		bottom = top;
	else
		(top->next)->prev = top;
}

// Pushes an item on to the bottom of the deque by allocating
// memory.
template <class T>
void	deque<T>::push_bot(T item)
{
	listelem* temp = new listelem;
	assert(temp != 0);

	temp->data = item;
	temp->next = 0;
	temp->prev = bottom;

	bottom = temp;
	if(top == 0)
		top = bottom;
	else
		(bottom->prev)->next = bottom;
}

// Sorts the elements of the deque, whether they be chars, ints
// or strings, into lexicographical order.
template <class T>
void	deque<T>::sort()
{
	listelem*	oldtop = top;
	listelem*	oldbot = bottom;
	listelem*	temp;
	T	item;

	reset();
	while(oldtop != 0 && oldbot != 0)	{
		item = oldtop->data;
		if(top == 0 && bottom == 0)
			push_top(item);
		else	{
			if(item <= top_of())	{
				push_top(item);
			} else	{
				if(item >= bottom_of())	{
					push_bot(item);
				}
				else	{
					temp = top;
					while(!(temp->data <= item && (temp->next)->data >= item))	{
						temp = temp->next;
					}
					listelem*	newitem = new listelem;
					assert(newitem != 0);
					newitem->data = item;
					newitem->next = temp->next;
					newitem->prev = temp;
					(temp->next)->prev = temp->next = newitem;
				}
			}
		}
		oldtop = oldtop->next;
	}
}

// Print deque
template <class T>
void	deque<T>::print() const
{
	listelem*	temp = top;

	while(temp != 0)	{
		cout << temp->data;
		temp = temp->next;
	}
}

// FUNCTION PROTOTYPES ==============================================
void	test_char();
void	getInput(deque<char>& q);
void	getInput(deque<int>& q);
void	getInput(deque<string>& q);
int	is_palin(deque<char> p);
int	is_palin(deque<int> p);
int	is_palin(deque<string> p);
void	run(deque<char>& q);
void	run(deque<int>& q);
void	run(deque<string>& q);

// ==================================================================
// Tests the member functions then runs three palindrome tests on
// three pieces of input - a word, some integers, and some words.
int main()
{
	deque<char>	qch;
	deque<int>	qint;
	deque<string> qstr;

	test_char();

	cout << "\n\nPALINDROME TEST (CHAR):\n\nEnter one word (end with #): ";
	run(qch);
	cout << "\n\nPALINDROME TEST (INT):\n\nEnter some integers (end with negative): ";
	run(qint);
	cout << "\n\nPALINDROME TEST (STRING):\n\nEnter some words (end with #): ";
	run(qstr);

	return(0);
}

// ================================================================
//	Gets the input word to be tested, tests to see if it is a
// palindrome and prints the result. It then sorts the input and
// prints the sorted order.
template <class T>
void	run(deque<T>& q)
{
	int	palin;

	getInput(q);

	cout << "\n";
	cout << "'";
	q.print();
	cout << "'";
	palin = is_palin(q);
	if (palin == TRUE)
		cout << " is a palindrome." << endl;
	else
		cout << " is NOT a palindrome." << endl;

	q.sort();
	cout << "The sorted input is: ";
	q.print();
	cout << endl;
}

// ====================================================================
// Gets the input whether it be char, int or string. The input must be
// ended by a # if it is word based, or a negative number if it is 
// number based. Then it ignores any following characters that may
// interfere with following input.
template <class T>
void getInput(deque<T>& q)
{
	T	new_item;

	cin >> new_item;
	while (new_item != '#' && new_item >= 0)	{
		q.push_bot(new_item);
		cin >> new_item;
	}
	cin.ignore(40,'\n');
}

// ====================================================================
// Determines if input is a palindrome by popping an item off
// each end and comparing them. Avoids the problem of an odd
// number of items in a word by checking to see if the deque
// is empty twice.
template <class T>
int	is_palin(deque<T> p)
{
	int	palin = 1;
	T	top_item, bot_item;

	while (!(p.empty()) && palin)	{
		top_item = p.pop_top();
		if (!p.empty())	{
			bot_item = p.pop_bot();
			if (top_item != bot_item)
				palin = FALSE;
		}
	}
	return(palin);
}

//===================================================================
// Tests the various member functions of deque with arbitrary
// character "input" to show that they work.
void	test_char()
{
	deque<char>	ch;
	deque<char> temp;

	cout << "TEST OF DEQUE'S FUNCTIONS (CHAR):\n";

	ch.push_top('a');
	cout << "\nTEST PUSH:\npush_top('a'): ";
	ch.print();
	ch.push_bot('b');
	cout << "\npush_bot('b'): ";
	ch.print();
	ch.push_top('c');
	cout << "\npush_top('c'): ";
	ch.print();

	temp = ch;
	cout << "\n\nTEST SORT:\nsort(), string is: ";
	temp.sort();
	temp.print();

	cout << "\n\nTEST LOOK & POP & EMPTY:\nString is:\t\t";
	ch.print();
	cout << "\ntop_of() is:\t\t";
	cout << ch.top_of() << "\npop_top(), string is:\t";
	ch.pop_top();
	ch.print();
	cout << "\nbottom_of() is:\t\t" << ch.bottom_of() << "\npop_bot(), string is:\t";
	ch.pop_bot();
	ch.print();
	cout << "\nempty():\t\t";
	cout << (ch.empty() ? "TRUE" : "FALSE") << endl;

	ch.reset();
	cout << "\nTEST RESET & EMPTY:\nreset string is:\t";
	ch.print();
	cout << "\nempty(): ";
	cout << (ch.empty() ? "TRUE" : "FALSE") << endl;
}