#include<iostream>
#include<cstdlib>
#include<type_traits>
using namespace std;

template<typename T> // template class from the beginning
class dynamic_array {
	/* storage here */
	/* Options:
	 *		new [] /delete [] 
	 *			- calls a constructor and destructor
	 *			- No resize feature
	 *		mmap
	 *			- does it work on Windows?
	 *			+ Makes it easy to save a data structure to disk
	 *		malloc / realloc / free
	 *			+ Doesn't call a constructor when moving things
	 *			+ Can reallocate
	 *			- Doesn't call a destructor with free!
	 */
	
	T* data;
	size_t _items = 0;
	size_t allocated_space;

public:
	dynamic_array(){
		data = (T*)malloc(10 * sizeof(T));
		allocated_space = 10;
	}
	dynamic_array(size_t initial_size){
		data = (T*)malloc(initial_size * sizeof(T));
		allocated_space = initial_size;
	}
	// Runs in O(n) time, not O(1)
	dynamic_array(const dynamic_array<T>& other){
		cout << "This ran\n";
		data = (T*)malloc(other._items * sizeof(T));
		// Call a copy constructor if T has one
		for(int i = 0; i < other._items; i++)
			data[i] = other.data[i];
		_items = other._items;
		allocated_space = other._items;
	}
	void reserve(size_t new_capacity){
		if(_items > new_capacity)
			_items = new_capacity;
		allocated_space = new_capacity;
		data = (T*)realloc(data, allocated_space * sizeof(T));
	}
	void trim(){
		allocated_space = _items;
		data = (T*)realloc(data, allocated_space * sizeof(T));
	}
	void push_back(const T& new_item){
		/* Do we have enough space? */
		if(allocated_space <= _items) {
			/* We don't have enough space! */
			allocated_space *= 2;
			data = (T*)realloc(data, allocated_space * sizeof(T));
		}
		/* Call a constructor without allocating memory for our new T */
		new (&data[_items]) T(new_item);
		_items++;
	}
	inline void operator+=(const T& new_item){
		push_back(new_item);
	}
	T& operator[](size_t index){
		return data[index];	
	}
	T pop_back(){
		_items--;
		return data[_items];
	}
	dynamic_array<T> operator+(const dynamic_array& other){
		dynamic_array<T> toreturn(_items + other._items);
		for(int i = 0; i < _items; i++)
			toreturn.data[i] = data[i];
		for(int i = 0; i < other._items; i++)
			toreturn.data[i + _items] = other.data[i];
		toreturn._items = toreturn.allocated_space;
		return toreturn;
	}
	size_t items(){
		return _items;
	}
	~dynamic_array(){
		/* If we didn't have a destructor, we don't need this loop.  It would be O(1) then! */
		if(!is_trivially_destructible<T>::value) 
			for(int i = 0; i < _items; i++)
				data[i].~T();
		free(data);
	}
};