/* Lecture Code 12.0
 *
 * DebugVector, Version 2.  This one now has deep-copy support,
 * so we can pass it to functions by value and correctly assign it
 * around.
 */
#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:
	/* Default constructor.  If we just create a DebugVector, it starts at
	 * size zero.  If we want to specify a size for it, we can do so by
	 * passing it as a parameter to the constructor.  Note that the explicit
	 * keyword here indicates that we can't write code like
	 *
	 * DebugVector<string> myVector = 137;
	 *
	 * In case you're confused by the syntax (size_t = 0), this means that the
	 * function takes in a size_t that has default value 0.  It's probably
	 * more readable if we write it as (size_t size = 0), but naming parameters
	 * is optional in function prototypes and you do tend to see this format
	 * from time to time.
	 */
	explicit DebugVector(size_t = 0);

	/* Copy constructor and assignment operator are responsible for performing
	 * deep copies.  The copy constructor is used to create new DebugVectors
	 * that are copies of existing DebugVectors, while the assignment operator
	 * is used to set existing DebugVectors to be copies of other DebugVectors.
	 * See Chapter 20 for more information.
	 */
	DebugVector(const DebugVector&);
	DebugVector& operator= (const 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

	void logCreation() const; // Prints creationg information
	void copyOther(const DebugVector& other); // Copies another DebugVector
	void clear(); // Clears out the DebugVector
};

/* Constructor sets aside some space for elements, then sets the size
 * to the user-specified parameter.  Note that although it doesn't show
 * here, the size_t parameter defaults to 0.
 */
const int kStartSize = 8;

template <typename T>
DebugVector<T>::DebugVector(size_t startSize)
{
	/* Figure out how much space we need - if we have fewer than kStartSize
	 * elements, we'll use kStartSize elements of storage space; else we use
	 * the storage space that exactly holds the amount of space the user
	 * requests.  Note the user of the ?: operator.
	 */
	const size_t initialCapacity = (startSize < kStartSize? kStartSize : startSize);
	array = new T[initialCapacity];
	logicalLength = startSize;
	allocatedLength = initialCapacity;

	logCreation(); // Mention that we were created.
}

/* Copy constructor creates this DebugVector as a copy of another DebugVector. */
template <typename T>
DebugVector<T>::DebugVector(const DebugVector& other)
{
	copyOther(other); // Perform deep-copy
	logCreation();    // Mention that we were created.
}

/* The assignment operator is tricky.  We need to check for self-assignment,
 * clear our old data members, do the deep copy, and return a reference to
 * ourself.
 */
template <typename T>
DebugVector<T>& DebugVector<T>::operator= (const DebugVector& other)
{
	if(this != &other) // Check for self-assignment
	{
		clear();			// Release resources
		copyOther(other);	// Perform the copy
	}
	return *this;			// Return a reference to ourself.
}

/* Prints out the current time. */
template <typename T>
void DebugVector<T>::logCreation() const
{
	time_t currTime = time(NULL);
	clog << "DebugVector created at " << ctime(&currTime);
}

/* Deallocates all resources. */
template <typename T>
void DebugVector<T>::clear()
{
	/* Free memory. */
	delete [] array;
}

/* Deep-copies data from another DebugVector. */
template <typename T>
void DebugVector<T>::copyOther(const DebugVector& other)
{
	/* Copy over length and capacity fields.  Note that this
	 * uses sibling access to read other's fields.  And no,
	 * this is not cousin access. :-)
	 */
	logicalLength = other.logicalLength;
	allocatedLength = other.allocatedLength;

	/* Deep-copy the elements from the other DebugVector. */
	array = new T[allocatedLength];
	copy(other.begin(), other.end(), array);
}

/* 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);

	clear();
}

/* 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;

void PrintVector(DebugVector<int> myVector)
{
	copy(myVector.begin(), myVector.end(), ostream_iterator<int>(cout, "\n"));
}

/* A sample class that cannot be copied because its copy
 * functions are marked private.  Note that the copy functions
 * aren't implemented since they aren't supposed to be called.
 */
class Uncopyable
{
public:

private:
	Uncopyable(const Uncopyable&);
	Uncopyable& operator= (const Uncopyable&);
};

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

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

	PrintVector(myVector);
	return 0;
}