// Copyright 1999
// College of Computer Science
// Northeastern University Boston MA 02115

// This software may be used for educational purposes as long as this copyright
// notice is retained at the top of all files

// Should this software be modified, the words "Modified from Original" must be
// included as a comment below this notice

// All publication rights are retained.  This software or its documentation may
// not be published in any media either in whole or in part.

///////////////////////////////////////////////////////////////////////////////
//	StackT.h
///////////////////////////////////////////////////////////////////////////////

#ifndef STACK_TEMPLATE_H_
#define STACK_TEMPLATE_H_

#include "AllocT.h"

template <class DataType>
class Stack {
	DataType*	data;			// pointer to the stack
	int		totalsize;			// total stack space
	int		validsize;			// valid stack space = stack height
	
	// copy is the heart of the copy constructor and operator=
	// copy assumes data is invalid and does no extra delete[]
	
	void Copy(const Stack& Original) {
		// set important fields to zero in case allocate fails
		data = 0;
		totalsize = 0;
		validsize = 0;
		
		// allocate
		Allocate(data, Original.totalsize);
		
		// set new parameters
		totalsize	= Original.totalsize;
		validsize	= Original.validsize;
		
		// copy valid data
		// caller cannot assume invalid data is copied

		CopyData(data, Original.data, 0, 0, validsize);
	};
	
public:
	// provide means for caller to recover DataType

	typedef DataType datatype;


	// routines to return internal information
	
	int TotalSize() const		{ return totalsize; };
	
	int ValidSize() const		{ return validsize; };
	

	// standard constructor
	
	Stack(int size = 1) {
		// set important fields to zero in case allocate fails
		data = 0;
		totalsize = 0;
		validsize = 0;
		
		if (size < 1) size = 1;			// force size positive
		
		Allocate(data, size);			// allocate the memory
		
		totalsize = size;				// set totalsize
	};
	

	// destructor
	
	~Stack() {
		delete [] data;
	};
	

	// copy constructor
	
	Stack(const Stack& Original) {
		Copy(Original);
	};

	
	// assignment: operator=
	
	Stack& operator= (const Stack& Original) {
		// if this object is the same as original just return
		if (this == &Original)
			return *this;
		
		// delete allocated memory in object
		delete [] data;
		
		// copy
		Copy(Original);
		
		return *this;
	};
	

	// Expand: Double available stack size
	
	Stack& Expand() {
		// set new size
		int NewSize;
		
		if (totalsize > 0)
			NewSize = 2 * totalsize;
		else
			NewSize = 1;
		
		// save original
		DataType* original = data;
		
		// allocate and catch error
		try {
			Allocate(data, NewSize);
		}
		catch (string& s) {
			// print message
			cout << s << endl << endl;

			// on error restore original and return immediately
			data = original;
			return *this;
		}
		
		// reset totalsize
		totalsize = NewSize;

		// copy original data up to validsize
		CopyData(data, original, 0, 0, validsize);
		
		// delete original data
		delete [] original;
		
		return *this;
	};

	
	// Push: Insert value at top of stack. Expand if necessary.
	
	bool Push(const DataType& value) {
		// check if more space is needed
		if (validsize == totalsize) Expand();
		
		// append the value if there is enough space now
		if (validsize < totalsize) {
			data[validsize] = value;		// store value
			validsize++;					// increment count
			return true;
		}
		else
			return false;
	};
	

	// Pop: Return top stack value and decrease validsize
	
	bool Pop(DataType& value) {
		if (validsize > 0) {
			validsize--;					// decrement count
			value = data[validsize];		// deliver value
			return true;
		}
		else
			return false;
	};
	

	// Peek: Return top stack value without changing validsize
	
	bool Peek(DataType& value) {
		if (validsize > 0) {
			value = data[validsize - 1];	// deliver value
			return true;
		}
		else
			return false;
	};

	
	// IsEmpty: Check if stack is empty
	
	bool IsEmpty() {
		return (validsize == 0);
	};
	

	// IsFull: If stack is full then first attempt to expand. Then check
	// whether validsize < totalsize
	
	bool IsFull() {
		if (validsize == totalsize) Expand();
		
		return (validsize == totalsize);
	};
};

#endif // STACK_TEMPLATE_H_