namespace darray

{ 

	template<class T>

	class DArray

	{

		bool init;

	

		unsigned long long arraySize;

		unsigned long long mostRecentAssign;

		unsigned long long highestAssign;

		struct InternalArray

		{

			T element;

			bool isAssigned;

			void operator=(const InternalArray& other)

			{

				element = other.element;

				isAssigned = other.isAssigned;

			}

			void Assign(const T& in)

			{

				element = in;

				isAssigned = true;

			}

			InternalArray()

			{

				isAssigned = false;

			}

		};

		InternalArray* internalArray;



	public:

		unsigned long long Size()

		{

			return arraySize;

		}

		unsigned long long WrittenSize()

		{

			return highestAssign+1;

		}

		void Resize(unsigned long long newSize)

		{

			if (arraySize > 0)

			{

				InternalArray* copyArray = new InternalArray[arraySize];

				for (unsigned long long i = 0; i < arraySize; i++)

				{

					copyArray[i] = internalArray[i];

				}

				delete[] internalArray;

				internalArray = new InternalArray[newSize];

				unsigned long long smaller = (arraySize > newSize) ? newSize : arraySize;

				for (unsigned long long i = 0; i < smaller; i++)

				{

					internalArray[i] = copyArray[i];

				}

				delete[] copyArray;

			} else

			{

				delete[] internalArray;

				internalArray = new InternalArray[newSize];

			}

			arraySize = newSize;

		}



		void PlaceBack(const T& newElement)

		{

			unsigned long long temp = arraySize;

			if (arraySize == 0) Resize(1);

			else Resize(arraySize * 2);

			Assign(temp, newElement);

		}



		void PushBackSoft(const T& newElement)

		{

			if (arraySize == 0) PlaceBack(newElement);

			else

			{

				if (init)

				{ 

					if (mostRecentAssign + 1 == arraySize) PlaceBack(newElement);

					else Assign(mostRecentAssign + 1, newElement);

				} else Assign(0, newElement);

			}

		

		}



		void PushBackHard(const T& newElement)

		{

			if (arraySize > 0)

			{

				unsigned long long lastAssigned = 0;

				for (unsigned long long i = 0; i < arraySize; i++)

				{

					if (internalArray[i].isAssigned == true)

					{

						lastAssigned = i;

					}

				}

				if (lastAssigned == arraySize - 1)

				{

					PlaceBack(newElement);

				}else

				{

					if(init) Assign(lastAssigned+1, newElement);

					else Assign(lastAssigned, newElement);

				}

			} else

			{

				PlaceBack(newElement);

			}

		

		}



		void operator=(const DArray& other)

		{

			delete[] internalArray;

			if (other.arraySize > 0)

			{ 

				internalArray = new InternalArray[other.arraySize];

				for (unsigned long long i = 0; i < other.arraySize; i++)

				{

					internalArray[i] = other.internalArray[i];

				}

			}

		}



		void ShrinkToWidth()

		{

			Resize(highestAssign + 1);

		}



		void ShrinkToSmallest()

		{

			unsigned long long assignedNo = 0;

			for (unsigned long long i = 0; i < arraySize; i++)

			{

				if (internalArray[i].isAssigned == true) assignedNo++;

			}

			InternalArray* copyArray = new InternalArray[assignedNo];

			unsigned long long j = 0;

			for (unsigned long long i = 0; i < arraySize; i++)

			{

				if (internalArray[i].isAssigned == true)

				{

					copyArray[j] = internalArray[i];

					j++;

				}

			}

			delete[] internalArray;

			internalArray = new InternalArray[assignedNo];

			for (unsigned long long i = 0; i < assignedNo; i++)

			{

				internalArray[i] = copyArray[i];

			}

			highestAssign = assignedNo - 1;

			delete[] copyArray;

			arraySize = assignedNo;

		}



		void Assign(unsigned long long index, const T& value)

		{

			init = true;

			internalArray[index].Assign(value);

			mostRecentAssign = index;

			if (index >= highestAssign) highestAssign = index;

		}



		void Insert(unsigned long long index, const T& value)

		{

			if (index <= arraySize - 1)

			{

				InternalArray* copyArray = new InternalArray[arraySize + 1];

				unsigned long long j = 0;

				for (unsigned long long i = 0; i < arraySize +1; i++)

				{

					if (i == index)

					{

						copyArray[i].element = value;

						copyArray[i].isAssigned = true;

						continue;

					}

					copyArray[i] = internalArray[j];

					j++;

				}

				delete[] internalArray;

				internalArray = new InternalArray[arraySize + 1];

				for (unsigned long long i = 0; i < arraySize + 1; i++)

				{

					internalArray[i] = copyArray[i];

				}

				delete[] copyArray;

				arraySize++;

			}

		}



		const T& operator[](unsigned index)

		{

			return internalArray[index].element;

		}



		const T& Front()

		{

			return internalArray[0].element;

		}



		const T& Back()

		{

			return internalArray[(arraySize == 0)?0:arraySize-1].element;

		}



		size_t MaxSize()

		{

			return numeric_limits<std::size_t>::max() / sizeof(T);

		}



		DArray()

		{

			arraySize = 0;

			init = false;

			highestAssign = 0;

		}

		DArray(unsigned long long size)

		{

			Resize(size);

			init = false;

			highestAssign = 0;

		}

	};

}