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

//================================< 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      // HOW FAR TO SHIFT UPPER BITS OF INDICES
	};

public:

// THIS CLASS CAN BE USED TO PRE-ALLOCATE 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 */


//===============================< testrig.h >================================

#include <iostream.h>

int lastshow = 0;

#define  TESTING(text)						\
	cout << "\nTesting " << #text << "..." << endl;

#define  REQUEST(var, okaycond)					\
	cout << "Enter " << #var << " (" << #okaycond << "): ";	\
	cin >> var;						\
	if (!(var okaycond)) break;

#define  SHOW(expr)						\
	if (lastshow<__LINE__-1) cout << endl;			\
	cout << "\t" << #expr << ": " << (expr) << endl;	\
	lastshow = __LINE__;

//================================< test.C >=================================

#include <string>

template <class ElementType>
ostream& operator<<(ostream& os, const Array<ElementType>& array)
{
	os << "[";
	for (int i=0; i<array.Count(); i++)
	{
		if (i>0)  { os << ","; }
		os << array[i];
	}
	os << "]";
	return os;
}

int main(void)
{
TESTING(Array ctors);

	Array<int> ai1;
	Array<int> ai2 (2);
	Array<int> ai3 (Array<int>::Size(10));
	Array<int> ai4 (Array<int>::Size(10),7);
	Array<int> ai5 (ai4);

	SHOW(ai1);
	SHOW(ai2);
	SHOW(ai3);
	SHOW(ai4);
	SHOW(ai5);

TESTING(Array::Count);

	SHOW(ai1.Count());
	SHOW(ai2.Count());
	SHOW(ai3.Count());
	SHOW(ai4.Count());
	SHOW(ai5.Count());

TESTING(Array::Append);

	SHOW(ai3.Append(1));
	SHOW(ai3.Append(2));
	SHOW(ai3.Append(3));
	SHOW(ai3.Append(4));
	SHOW(ai3.Append(5));
	SHOW(ai3.Append(6));
	SHOW(ai3.Append(7));
	SHOW(ai3.Append(8));
	SHOW(ai3.Append(9));
	SHOW(ai3.Append(10));

	SHOW(ai3.Append(ai5));
	SHOW(ai5.Append(ai5));

TESTING(Array::operator=)

	SHOW((ai5 = ai3));
	SHOW((ai5 = 99));

TESTING(Array::Contains)

	while (1)
	{
		int index;
		REQUEST( index, >0 );
		try
		{
			int val = ai3[index];
			SHOW(ai3[index]);
		}
		catch (Array<int>::BoundsError be)
		{
			cout << ">>> Invalid index: " << be.index << endl;
		}
	}

TESTING(Array::RemoveLast)

	SHOW(ai3.RemoveLast(1));
	SHOW(ai3.RemoveLast(4));
	SHOW(ai3.RemoveLast(-4));

TESTING(Array::RemoveLast)

	SHOW(ai3.Reset());

TESTING(Other ElementTypes)

	Array<string> as1 ("as1");
	Array<string> as2 (Array<string>::Size(5),"as2");
	Array<string> as3 (as2);

	SHOW(as1);
	SHOW(as2);
	SHOW(as3);

	SHOW((as3[2] = as1[0]));

	Array< Array<string> > aas (Array< Array<string> >::Size(3),as3);

	SHOW(aas);
	SHOW(aas[1]);
	SHOW(aas[1][1]);

TESTING(Equality test);

	SHOW((as1==as3));
	SHOW((as3==as3));
	SHOW((aas[1]==as3));
}