template <typename Type>
class NeatArray
{
public:
	//constructor
	// if no values are passed the
	//  default size should be 200
	//  default length should be 0
	NeatArray(int size = 200, int length = 0)
	{
		if(size <= 0)
			_size = 200;
		else
			_size = size;

		_array       = new Type[_size];
		_length   = length;
	};
   // Destructor
   ~NeatArray()
   {
	   delete [] _array;
   };
   //###############################################
   // insert an element
   //
   void insert(Type element)
	{
		if(!full())
		{
			_array[_length] = element;
			_length++;
		}
		else
		{
			Type* _new_array;
			int   _new_size;
			_new_size = _size + 10000;
			_new_array = new Type[_new_size];
			for (int i = 0; i < _length; i++)
				_new_array[i] = _array[i];
			_size = _new_size;
			delete [] _array;
			_array = _new_array;
		}
	};
	//###############################################
	// return size of array
	//
	int size()
	{
		return(_length);
	}
	//###############################################
	// is this baby full ?
	//
	bool full()
	{
		return(_length == _size);
	}
	//###############################################
	// is this less
	//
	bool less(Type A, Type B)
	{
		return(A < B);
	}
	//###############################################
	// operator
	//
	//bool operator==(const Type &A, const Type &B)
	//{ return !less(A, B) && !less(B, A); }
	//###############################################
	// operator
	//
	Type& operator[](int idx)
	{ return _array[idx]; }
	const Type& operator[](int idx) const
	{ return _array[idx]; }
	//###############################################
	// swap
	//
	void swap(Type array[], int first, int second)
	{
		Type tmp;
		tmp = array[first];
		array[first] = array[second];
		array[second] = tmp;
	}// end swap
	//###############################################
	// partition
	//
	int partition( Type array[], int first, int last)
	{
		Type pivot;
		int ix;
		int sm_ix;
		swap( array, first, (first+last)/2 );
		pivot = array[first];
		sm_ix = first;

		for( ix = first+1; ix <= last; ix++ )
		if( array[ix] < pivot)
		{
			sm_ix++;
			swap( array,sm_ix,ix );
		}
		swap( array,first,sm_ix );
		return sm_ix;
	}// end partition
	//###############################################
	// recursive quick sort
	//
	void rec_quick_sort(Type array[], int first, int last)
	{
		int pivot;
		if(first < last)
		{
			pivot = partition(array, first, last);
			rec_quick_sort(array, first, pivot-1);
			rec_quick_sort(array, pivot+1, last);
		}
	}
	//###############################################
	// quick sort
	//
	void quick_sort()
	{
		rec_quick_sort( _array, 0 , _length-1);
	}
	//###############################################
	// sorting for the obese
	//
	void obese_sort()
	{
		NeatArray<pointer<Type> > p_array(_size,_length);
		int i;
		int j;
		int nx_j;
		//p_array._length = _length;
		// copy the contents of the calling array into a temp array of pointers to the objects.
		for( int i = 0; i < _length; i++ )
			p_array[i] = &_array[i];
		// sort the array of pointers
		//p_array.quick_sort();
		rec_quick_sort(*p_array._array,0,p_array._length-1);
		// now we will move around all of the pointers
		for( int i = 0; i < _length; i++ )
		{
			if( p_array[i] != &_array[i])
			{
				Type tmp = _array[i];
				for( int j = i; p_array[j] != &_array[i]; j = nx_j )
				{
					nx_j = p_array[j] - &_array[0];
					_array[j]  = *p_array[j];
					p_array[j] = &_array[j];
				}//end for j
				_array[j] = tmp;
				p_array[j]   = &_array[j];
			}//end if
		}// end for i
	}// end obese_sort
//private:
	Type *_array;
	int _length;
	int _size;
};