///////////////////////////////////////////////////////////////////////////////
//	g++ -fhandle-exceptions Stack.C -o Stack
///////////////////////////////////////////////////////////////////////////////

//================================< Array.h >=================================

// WARNING: Requires exceptions  (use g++ -fhandle-exceptions)

#ifndef Array_First
#define Array_First

template <class ElementType>
class Array
{

	enum
	{
		log2BucketSize = 4,                  // LOG (BASE 2) OF HOW MANY ELEMENTS PER BUCKET
		bucketSize     = 1<<log2BucketSize,  // HOW MANY ELEMENTS PER BUCKET
		modBucketSize  = bucketSize-1,       // MASK FOR LOWER BITS OF INDICES
		divBucketSize  = log2BucketSize-1    // HOW FAR TO SHIFT UPPER BITS OF INDICES
	};

public:

// THIS CLASS CAN BE USED TO PRE-ALLOCATED A FIXED NUMBER OF ELEMENTS

	class Size
	{
		friend class Array<ElementType>;
	public:
		explicit Size(int s) : myElemCount(s) {}
	private:
		int myElemCount;
	};

// THIS CLASS IMPLEMENTS AN EXCEPTION ON BOUNDS ERROR

        struct BoundsError
        {
        	BoundsError(int i, int m) : index(i) , max(m) {}

        	int index;
        	int max;
        };

private:
	int		myBucketCount;	// NUMBER OF BUCKETS ALLOCATED
	int		myNextFree;	// INDEX OF NEXT FREE ELEMENT
	ElementType**	myElement;	// POINTER TO VECTOR OF BUCKETS


// 1. CONVERT AN INDEX INTO A BUCKET NUMBER AND INDEX WITHIN THAT BUCKET
//    RETURN A REFERENCE TO THE CORRESPONDING ELEMENT

	ElementType& access(int index) const
	{
		return myElement[index>>divBucketSize][index&modBucketSize];
	}


// 2. REALLOCATE THE REQUIRED NUMBER OF BUCKETS
//    IF THE REQUIRED NUMBER IS 0, ALLOCATE ENOUGH SPACE
//    FOR AT LEAST ONE EXTRA ELEMENT

	void reallocate(int reqBucketCount = 0)
	{
        	if (reqBucketCount>0 && reqBucketCount>myBucketCount)
        	{
		// ALLOCATE A VECTOR OF THE REQUIRED NUMBER OF BUCKETS

        		ElementType** newelement = new ElementType* [reqBucketCount];
        		int i;

		// MOVE EACH EXISTING BUCKET TO NEW BUCKET VECTOR

        		for (i=0;i<myBucketCount;i++)
			{
        			newelement[i] = myElement[i];
        		}

		// ADD NEW BUCKETS TO THE END OF THE VECTOR

        		for (;i<reqBucketCount;i++)
        		{
        			newelement[i] = new ElementType [bucketSize];
        		}

		// RECLAIM OLD VECTOR, REPLACE IT WITH THE NEW VECTOR,
		// AND REMEMBER THE NEW COUNT

        		delete [] myElement;
        		myElement = newelement;
        		myBucketCount = reqBucketCount;
        	}
        }


public:

// 3. CONSTRUCTORS AND DESTRUCTORS

	Array(void)
	: myBucketCount(0)
	, myNextFree(0)
	, myElement(0)
	{}

	Array(const ElementType & elem)
        : myBucketCount(0)
        , myNextFree(1)
        , myElement(0)
        { 
        	reallocate(1);
        	access(0) = elem;
        }

	Array(const Array<ElementType> & array)
        : myBucketCount(0)
        , myNextFree(array.myNextFree)
        , myElement(0)
        { 
	// ALLOCATE AS MANY BUCKETS AS REQUIRED TO STORE THE
	// NUMBER OF ELEMENTS IN THE EXISTING ARRAY array

		reallocate(array.myNextFree+modBucketSize >> divBucketSize);

	// COPY EACH ELEMENT ACROSS

        	for (int i=0; i<array.myNextFree; i++)
        	{
        		access(i) = array.access(i);
        	}
        }

	Array(Array<ElementType>::Size initsize)
	: myBucketCount(0)
	, myNextFree(0)
	, myElement(0)
	{
	// CONVERT ELEMENT COUNT TO BUCKET COUNT

		reallocate(initsize.myElemCount+modBucketSize >> divBucketSize);
	}

	Array(Size initsize, const ElementType& initval)
	: myBucketCount(0)
	, myNextFree(initsize.myElemCount)
	, myElement(0)
	{
	// CONVERT ELEMENT COUNT TO BUCKET COUNT

		reallocate(initsize.myElemCount+modBucketSize >> divBucketSize);

	// INITIALIZE EACH REQUESTED BUCKET

		for (int i=0;i<myNextFree;i++)
		{
			access(i) = initval;
		}
	}

	~Array(void)
	{
	// DELETE EACH BUCKET

		for (int i=0; i<myBucketCount; i++)
		{
			delete [] myElement[i];
		}

	// THEN DELETE THE BUCKET VECTOR

		delete [] myElement;
	}


// 4. ASSIGN A SINGLE ELEMENT

	Array& operator = (const ElementType & elem)
	{ 
        	reallocate(1);		// WILL NEED EXACTLY 1 BUCKET
        	access(0) = elem;	// elem GOES IN THE FIRST SLOT
        	myNextFree = 1;		// THERE IS NOW EXACTLY 1 ELEMENT
        	return *this;
        }


// 5. ASSIGN AN ARRAY OF ELEMENTS

	Array& operator = (const Array & array)
	{ 
	// SHORT CIRCUIT ON SELF-ASSIGNMENT

		if (&array == this) { return *this; }
	
	// ENSURE ENOUGH SPACE TO STORE ALL THE ELEMENTS IN array

		reallocate(array.myNextFree+modBucketSize >> divBucketSize);

	// COPY EACH ELEMENT

		for (int i=0; i<array.myNextFree; i++)
		{
			access(i) = array.access(i);
		}

	// ADJUST THE COUNT AND RETURN

		myNextFree = array.myNextFree;
        	return *this;
        }


// 6. LOGICALLY DELETE ALL THE ELEMENTS IN THE ARRAY

	Array& Reset(void)
	{
		myNextFree = 0;
		return *this;
	}


// 7. HOW MANY ELEMENTS ACTUALLY IN THE ARRAY
//    (NOTE: _NOT_ HOW MANY ELEMENTS SPACE HAS BEEN ALLOCATED FOR)

	int Count(void) const
	{
		return myNextFree;
	}


// 8. CHECKED PUBLIC ACCESS TO ARRAY

        ElementType& operator[] (int i)
        {
        	if (i>=0 && i<myNextFree) { return access(i); }
		throw BoundsError(i,myNextFree);
        }

        ElementType operator[] (int i) const
        {
        	if (i>=0 && i<myNextFree) { return access(i); }
		throw BoundsError(i,myNextFree);
        }


// 9. APPEND TO ARRAY

        Array& Append(const ElementType& elem)
        {
        	reallocate(myNextFree+1+modBucketSize >> divBucketSize);
        	access(myNextFree) = elem;
        	myNextFree++;
        	return *this;
        }

        Array& Append(const Array& array) 
        {
	// ENSURE ENOUGH SPACE FOR THE EXTRA ELEMENTS

        	reallocate(myNextFree+array.myNextFree+modBucketSize>>divBucketSize);

	// COPY EACH EXTRA ELEMENT TO THE NEXT EMPTY SLOT

        	for (int i=0; i<array.myNextFree; i++)
        	{
        		access(myNextFree+i) = array.access(i);
        	}

	// ADJUST THE COUNTER AND RETURN

		myNextFree += array.myNextFree;
        	return *this;
        }


// 10. REMOVE LAST n ELEMENT(S)

	Array& RemoveLast(int n = 1)
        {
		if (myNextFree<=n) { myNextFree = 0; }
		else if (n>=0)     { myNextFree -= n; }
        	return *this;
        }


// 11. CHECK FOR AN ELEMENT VALUE IN THE ARRAY
//     RETURNS: 0 ON FAILURE OR
//              (index+1) WHERE index IS THE INDEX OF THE FIRST
//                        ELEMENT WITH A MATCHING VALUE

	int Contains(const ElementType& elem) const
	{
        	for (int i=0;i<myNextFree;i++)
        	{
        		if (elem == access(i)) { return i+1; }
        	}
        	return 0;
        }

// 12. ARRAYS ARE EQUAL IF THEY ARE THE SAME LENGTH AND EACH ELEMENT IS EQUAL

	friend bool operator==(const Array& a1, const Array& a2)
	{
	// ARRAYS ALWAYS EQUAL THEMSELVES

		if (&a1==&a2) { return true; }

	// IF DIFFERENT LENGTHS, CAN'T BE EQUAL...

		if (a1.myNextFree!=a2.myNextFree) { return false; }

	// IF ANY CORRESPONDING ELEMENTS DIFFER, NOT EQUAL...

		for (int i=0; i<a1.myNextFree; i++)
		{
			if (!(a1.access(i) == a2.access(i))) { return false; }
		}

	// OTHERWISE...
		return true;
	}

};

#endif /* Array_First */


//================================< Stack.h >=================================

// #include "Array.h"


template <class ElementType>
class Stack : private Array<ElementType>
{
public:
	/*using*/ Array<ElementType>::Count;	// "using" not yet supported

	void Push(const ElementType& elem)
		{ Append(elem); }

	const ElementType& Top(void)
		{ return operator[]( Count()-1 ); }

	ElementType Pop(void)
		{ ElementType top = Top(); RemoveLast(); return top; }
};


//==============================< StackTest.C >===============================

#include <iostream.h>

int main(void)
{
	Stack<int> stack;

	stack.Push(1);
	cout << stack.Count() << endl;

	stack.Push(2);
	cout << stack.Count() << endl;

	stack.Push(3);
	cout << stack.Count() << endl;

	stack.Push(4);
	cout << stack.Count() << endl;

	cout << stack.Top() << endl;


	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
	cout << stack.Pop() << endl;
}