#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_RESIZABLE_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_RESIZABLE_ARRAY

/*
 *  This code assumes that the array capacity will be representable as
 *  an int.  Consequently, only values < 2^31 are calculated.
 */

int const CAPACITY_ARRAY[5][60] = {
	//                          _  k
	// The closest integer to \/2 2  for non-powers-of-two (every second).
	//   - 2.4 copies per insertion
	//   - 18% empty on average
	{
		4, 6,  // Initial capacity is 8; these are used for downsizing
		8, 11, 16, 23, 32, 45, 64, 91, 128, 181, 256, 362, 512, 724,
		1024, 1448, 2048, 2896, 4096, 5793, 8192, 11585, 16384, 23170,
		32768, 46341, 65536, 92682, 131072, 185364, 262144, 370728,
		524288, 741455, 1048576, 1482910, 2097152, 2965821, 4194304,
		5931642, 8388608, 11863283, 16777216, 23726566, 33554432,
		47453133, 67108864, 94906266, 134217728, 189812531, 268435456,
		379625062, 536870912, 759250125, 1073741824, 1518500250
	},

	// Using a factor of 1.5
	//   - 2 copies per insertion
	//   - 22% empty on average
	{
		3, 5,  // Initial capacity is 8; these are used for downsizing
		8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473, 710, 1065, 1598, 2397,
		3596, 5394, 8091, 12137, 18206, 27309, 40964, 61446, 92169, 138254,
		207381, 311072, 466608, 699912, 1049868, 1574802, 2362203, 3543305,
		5314958, 7972437, 11958656, 17937984, 26906976, 40360464, 60540696,
		90811044, 136216566, 204324849, 306487274, 459730911, 689596367,
		1034394551, 1551591827, 2327387741, 3491081612
	},

	//                         3_   2k + 1        3_  2k + 1
	// The closest integer to \/4  2       and 2 \/2 2       for non-odd-powers-of-two (every third).
	//   - 1.7 copies per insertion
	//   - 25% empty on average
	{
		5, 6,  // Initial capacity is 8; these are used for downsizing
		8, 13, 20, 32, 51, 81, 128, 203, 323, 512, 813, 1290, 2048,
		3251, 5161, 8192, 13004, 20643, 32768, 52016, 82570, 131072,
		208064, 330281, 524288, 832255, 1321123, 2097152, 3329021,
		5284492, 8388608, 13316085, 21137968, 33554432, 53264341,
		84551870, 134217728, 213057363, 338207482, 536870912,
		852229450, 1352829926
	},

	// Using a factor of 2
	//   - 1 copy per insertion
	//   - 39% empty on average
	{
		2, 4,  // Initial capacity is 8; these are used for downsizing
		8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
		65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
		16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
		1073741824
	},

	// Using a factor of infinity
	//    - 0 copies per insertion
	{
		0, 0,  // These two ensures that resizing never occurs
		1073741824
	}
};

template <typename T, int K>
class Array {
	private:
		int capacity_index;
		int array_capacity;
		T *array;
		int array_size;

	public:
		Array():
		capacity_index( 2 ),
		array_capacity( CAPACITY_ARRAY[K][capacity_index] ),
		array( new T[capacity()] ),
		array_size( 0 ) {
			// empty constructor
		}

		~Array() {
			delete []array;
		}

		// Increase the size of the array if it is full
		// and insert the new entry at the end.

		void insert( T x ) {
			if ( size() >= capacity() ) {
				update_capacity( 1 );
			}

			array[size()] = x;
			++array_size;
		}

		// Remove the last element and decrase the
		// size of the array if it is too empty.

		void remove() {
			--array_size;

			if ( capacity_index > 2 && size() == CAPACITY_ARRAY[K][capacity_index - 2] ) {
				update_capacity( -1 );
			}
		}

		// Increase or decrease the size of the array:
		//  - Update the capacity index and allocate memory
		//    for a new array,
		//  - Copy over the entries,
		//  - Update the capacity, and
		//  - Delete the old array.

		void update_capacity( int delta ) {
			T *array_tmp = array;

			capacity_index += delta;
			array = new T[ CAPACITY_ARRAY[K][capacity_index] ];

			for ( int i = 0; i < size(); ++i ) {
				array[i] = array_tmp[i];
			}

			array_capacity = CAPACITY_ARRAY[K][capacity_index];

			delete []array_tmp;
		}

		int capacity() const {
			return array_capacity;
		}

		int size() const {
			return array_size;
		}

		// Sum the entries of the array.

		T sum() const {
			T value = 0;

			for ( int i = 0; i < size(); ++i ) {
				value += array[i];
			}

			return value;
		}
};

#endif