/* Lecture code 11.0
 *
 * DebugVector, Version 1.  The interface has been const-corrected so that
 * we can pass DebugVectors by reference-to-const and so that we minimize
 * the overhead from pass-by-value.
 */

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <string>
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.
	 * Note that we've const-overloaded this function so that if we have a 
	 * non-const DebugVector we can read and write elements, but with a const
	 * DebugVector we can only read elements.
	 */
	T& at(size_t index);
	const T& at(size_t index) const;

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

	/* The const_iterator type is used when working with const DebugVectors
	 * and can only read elements.  Note that the type
	 * const T* means "pointer to const T", not "a const pointer to a T;"
	 * see Chapter 15 of the course reader for more info.
	 */
	typedef const T* const_iterator;
	const_iterator begin() const;
	const_iterator end() const;

	/* Some utility functions to insert, remove, and append elements. */
	iterator erase(iterator where);
	iterator insert(iterator where, const T& what);
	void push_back(const 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() const;
	bool isEmpty() const;

	/* reserve and capacity are similar to what you'd find in std::vector. 
	 * Note that reserve() is NOT const because it might resize the vector
	 * behind-the-scenes, causing outstanding iterators to point to the
	 * wrong locations.
	 */
	size_t capacity() const;
	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() const
{
	return logicalLength;
}

/* Vector is empty if it has no elements in it. */
template <typename T>
bool DebugVector<T>::isEmpty() const
{
	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.  This version returns a const reference,
 * however, and so is safe even with a const DebugVector.
 */
template <typename T>
const T& DebugVector<T>::at(size_t index) const
{
	return array[index];
}

/* This const overload can be implemented in two ways.  First, we can just
 * duplicate the code from the above implementation of at (as shown here).
 * Alternatively, as we mentioned in class, we can use the const_cast/static_cast
 * trick as follows:
 *
 * 1. Use static_cast to typecast the this pointer to be const.
 * 2. Call at; this invokes the const version.
 * 3. Use const_cast to strip the constness off of the return value.
 *
 * This version is shown below, but commented out.
 */
template <typename T>
T& DebugVector<T>::at(size_t index)
{
	//return const_cast<T&>(static_cast<const DebugVector*>(this)->at(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, const 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(const 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() const
{
	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();
}
template <typename T>
typename DebugVector<T>::const_iterator DebugVector<T>::begin() const
{
	return array;
}
template <typename T>
typename DebugVector<T>::const_iterator DebugVector<T>::end() const
{
	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();

	copy(myVector.begin(), myVector.end(), ostream_iterator<int>(cout, "\n"));
	return 0;
}