/* Lecture code 10.0
 *
 * Basic implementation of the DebugVector class.  As we continue further
 * into the heart of C++ we will see numerous revisions to this class.
 * This particular version has the basic class template structure and
 * demonstrates basic use of iterators.
 */

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;

/* A vector class that has some extra logging information.  Creating a
 * DebugVector prints out the time of creation to clog, and destroying
 * a DebugVector prints out the time of destruction to clog.
 */
template <typename T> class DebugVector
{
public:
	DebugVector();
	~DebugVector();

	/* Accessors return references to the element, so we don't need getAt/setAt. */
	T& at(size_t index);

	/* Iterator functions.  Since pointers act like STL iterators, we'll
	 * typedef regular pointers to be iterators.
	 */
	typedef T* iterator;
	iterator begin();
	iterator end();

	/* Some utility functions to insert, remove, and append elements. */
	iterator erase(iterator where);
	iterator insert(iterator where, T what);
	void push_back(T value);
	void pop_back();

	/* Size functions.  Note that we're using the type size_t instead of int
	 * because size_t is always nonnegative and sizes can't be negative.
	 */
	size_t size();
	bool isEmpty();

	/* reserve and capacity are similar to what you'd find in std::vector. */
	size_t capacity();
	void reserve(size_t space);

private:
	T* array;					// Actual elements
	size_t logicalLength;		// Number of elements used
	size_t allocatedLength;		// Available space
};

/* Constructor allocates eight elements of storage space. */
const int kStartSize = 8;

template <typename T>
DebugVector<T>::DebugVector()
{
	array = new T[kStartSize];
	logicalLength = 0;
	allocatedLength = kStartSize;

	/* Prints out the current time. */
	time_t currTime = time(NULL);
	clog << "DebugVector created at " << ctime(&currTime);
}

/* Destructor clears out the vector and logs destruction information. */
template <typename T>
DebugVector<T>::~DebugVector()
{
	/* Print out the current time. */
	time_t currTime = time(NULL);
	clog << "DebugVector destroyed at " << ctime(&currTime);

	/* Free memory. */
	delete [] array;
	array = NULL;
	allocatedLength = logicalLength = 0;
}

/* Returns the number of elements in the DebugVector. */
template <typename T>
size_t DebugVector<T>::size()
{
	return logicalLength;
}

/* Vector is empty if it has no elements in it. */
template <typename T>
bool DebugVector<T>::isEmpty()
{
	return logicalLength == 0;
}

/* Returns a reference to an element in the DebugVector.  Return-by-reference
 * is like pass-by-reference; it means that any changes you make to the return
 * value will modify the DebugVector.
 */
template <typename T>
T& DebugVector<T>::at(size_t index)
{
	return array[index];
}

/* Removes an element from the DebugVector and returns an iterator to
 * the element right after the one that was erased.  Note that the return
 * value is typename DebugVector<T>::iterator because iterator is nested
 * inside DebugVector<T>, which is a dependent type (a type that depends on
 * a template argument).
 */
template <typename T>
typename DebugVector<T>::iterator DebugVector<T>::erase(iterator where)
{
	/* Shuffle all elements down one position. */
	copy(where + 1, end(), where);
	logicalLength --;
	return where;
}

/* pop_back is just a wrapped call to erase. */
template <typename T>
void DebugVector<T>::pop_back()
{
	erase(end() - 1);
}

/* Inserts a new element, growing if necessary, then shuffles things down. */
template <typename T>
typename DebugVector<T>::iterator DebugVector<T>::insert(iterator where, T what)
{
	/* This is a bit tricky - we need to remember where to insert the element,
	 * but calling reserve() might cause us to reallocate the buffer and consequently
	 * to have the iterator pointing in the wrong place.  We'll get around this by
	 * caching the offset from the beginning of the DebugVector to the iterator,
	 * reserving space, and then finally restoring the iterator.
	 */
	ptrdiff_t offset = where - begin();
	reserve(size() + 1);
	where = begin() + offset;

	/* Shuffle all elements down one position to make room for the elements. */
	copy_backward(where, end(), end() + 1);
	
	/* Copy the element in. */
	*where = what;	
	
	/* Update size. */
	logicalLength ++;

	/* Return an iterator to the element. */
	return where;
}

/* Appends an element - effectively a glorified call to insert. */
template <typename T>
void DebugVector<T>::push_back(T what)
{
	insert(end(), what);
}

/* Ensures that we have at least as much space as is specified.  We do this by
 * doubling our size until we have as much space as was expected.
 */
template <typename T>
void DebugVector<T>::reserve(size_t space)
{
	/* If we don't need to grow, don't! */
	if(capacity() >= space) return;

	/* Compute our new size. */
	size_t newSize = capacity();
	while(newSize < space)
		newSize *= 2;

	/* Create a new array of elements and copy data over. */
	T* newArray = new T[newSize];
	copy(begin(), end(), newArray);

	/* Free existing array. */
	delete [] array;

	/* Update internals. */
	array = newArray;
	allocatedLength = newSize;
}

/* Our capacity is the allocatedLength. */
template <typename T>
size_t DebugVector<T>::capacity()
{
	return allocatedLength;
}

/* begin and end just return pointers to the first and past-the-end elements,
 * respectively.
 */
template <typename T>
typename DebugVector<T>::iterator DebugVector<T>::begin()
{
	return array;
}
template <typename T>
typename DebugVector<T>::iterator DebugVector<T>::end()
{
	return array + size();
}

const int kNumInts = 10;

/* Demonstrates how to use the DebugVector. */
int main()
{
	/* Populate the vector. */
	DebugVector<int> myVector;
	for(int i = 0; i < kNumInts; ++i)
		myVector.push_back(i);

	myVector.insert(myVector.begin() + 5, 137);
	myVector.erase(myVector.begin());
	myVector.pop_back();
	return 0;
}