/* Lecture code 13.0
 *
 * DebugVector Version 3 - Now with overloaded element access,
 * stream insertion, and comparison operators.
 *
 * Comments have been added to the relevant sections.
 */

#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& operator[](size_t index);
	const T& operator[](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);

	/* Less-than operator for storage in STL containers. */
	bool operator < (const DebugVector&) const;

	/* Stream insertion.  Note that this is defined as a friend function
	 * and is therefore not actually part of the class but still has
	 * access to the private data members.
	 */
	template <typename T>
	friend ostream& operator << (ostream& out, const DebugVector<T>& v);

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
};

/* Implementation of operator<< just uses copy and an ostream_iterator.
 * Note that the first parameter and return type are ostream&, a reference
 * to some sort of output stream.  Also note that this is a free function
 * so that we can write cout << myVector instead of myVector << cout.
 */
template <typename T>
ostream& operator << (ostream& out, const DebugVector<T>& v)
{
	out << "( ";
	copy(v.array, v.array + v.logicalLength, ostream_iterator<T>(out, " "));
	out << ")";
	return out;
}

/* 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>::operator[](size_t index) const
{
	return array[index];
}

/* const overload. */
template <typename T>
T& DebugVector<T>::operator[](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, 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();
}

/* The less-than operator uses a modified lexicographical comparison to
 * compare two DebugVectors.  We first compare sizes - if they aren't the
 * same, we use this to break ties.  Otherwise, we look for the first
 * mismatched element and use that.
 */
template <typename T>
bool DebugVector<T>::operator< (const DebugVector& other) const
{
	if(size() != other.size())
		return size < other.size();
	
	/* Note that this code is equivalent to the simpler code
	 *
	 * return lexicographical_compare(begin(), end(), other.begin(), other.end());
	 *
	 * This uses the STL algorithms to get the job done and is a bit simpler.
	 * We didn't cover this in lecture because it obscured the detail about
	 * using the < vs the > operator in the body of the loop.
	 */
	for(size_t i = 0; i < size(); ++i)
	{
		if((*this)[i] < other[i])
			return true;
		if(other[i] < (*this)[i])
			return false;
	}

	return false;
}

const int kNumInts = 10;

int main()
{
	DebugVector<int> myVector(kNumInts);

	for(size_t i = 0; i < myVector.size(); ++i)
		myVector[i] = i;

	cout << myVector << endl;
}