/* Lecture code 11.0
 *
 * Updated DebugVector, complete with bracket syntax and the
 * < relational operator.  Note that there are some minor changes
 * from lecture in the operator < function that you should consider
 * looking in to.
 */
 
#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();

	/* Constructor to set the size of the vector.  The constructor is marked
	 * explicit so that it can't be used in implicit conversions.
	 */
	explicit DebugVector(int startSize);

	DebugVector(const DebugVector &other); // Copy constructor
	DebugVector& operator =(const DebugVector& other); // Assignment operator
	~DebugVector();

	/* Accessors return references to the element, so we don't need getAt/setAt.
	 * Note that this function is const-overloaded.
	 */
	T& operator[] (int index);
	const T& operator[] (int index) const;

	/* Iterator support.  These two typedefs convert raw C++ pointers into
	 * DebugVector<T>::iterator and DebugVector<T>::const_iterator.
	 */
	typedef T* iterator;
	typedef const T* const_iterator;

	/* begin and end are const-overloaded and just return the corresponding
	 * parts of the array.
	 */
	iterator begin() { return array; }
	iterator end()   { return array + logicalLength; }
	const_iterator begin() const { return array; }
	const_iterator end()   const { return array + logicalLength; }

	/* Some utility functions to insert, remove, and append elements. */
	void removeAt(int index);
	void insertAt(const T& value, int index);
	void append(const T& value);

	/* Size functions. */
	int size() const;
	bool isEmpty() const;

	/* Used so that we can store DebugVector in map/set. */
	bool operator < (const DebugVector& other) const;
private:

	void copyOther(const DebugVector& other);
	void grow();
	void logCreation();
	void clear();

	T *array;
	int logicalLength;
	int allocatedLength;
	static const int START_SIZE = 8;
};

/* Constructor.  Note that most of the variables are set up in the initializer list. */
template<typename T> DebugVector<T>::DebugVector() :
	array(new T[START_SIZE]), logicalLength(0), allocatedLength(START_SIZE)
{
	logCreation();
}

/* copyOther just copies over the relevant fields, then does a deep copy. */
template<typename T> void DebugVector<T>::copyOther(const DebugVector& other)
{
	logicalLength = other.logicalLength;
	allocatedLength = other.allocatedLength;

	array = new T[allocatedLength];

	/* Use the STL to perform the deep copy. */
	copy(other.begin(), other.end(), begin());
}

/* Copy constructor - just copy the other object and log creation data! */
template<typename T> DebugVector<T>::DebugVector(const DebugVector& other)
{
	copyOther(other);
	logCreation();
}

/* Assignment operator is a bit trickier. */
template<typename T> DebugVector<T>& DebugVector<T>::operator =(const DebugVector& other)
{
	/* Avoid self-assignment by checking to see if we're coincident with the source. */
	if(this != &other)
	{
		clear();          // Deallocate old data
		copyOther(other); // Copy in new data
	}
	
	/* Return a reference to ourself. */
	return *this;
}

/* Extra constructor just creates us at a certain size. */
template<typename T> DebugVector<T>::DebugVector(int startSize) :
	array(new T[startSize]), logicalLength(startSize), allocatedLength(startSize)
{
	logCreation();
}

/* logCreation uses some functions from ctime to print debugging info. */
template<typename T> void DebugVector<T>::logCreation()
{
	time_t currTime;
	time(&currTime);

	clog << "DebugVector created at " << ctime(&currTime) << endl;
}

/* clear just wipes out existing data and zeros the relevant fields. */
template<typename T> void DebugVector<T>::clear()
{
	delete [] array;
	array = NULL;

	allocatedLength = logicalLength = 0;
}

/* Destructor clears out the vector and logs destruction information. */
template<typename T> DebugVector<T>::~DebugVector()
{
	time_t currTime;
	time(&currTime);

	clog << "DebugVector destroyed at " << ctime(&currTime) << endl;

	clear();
}

/* Returns the number of elements - note the const modifier here since this doesn't
 * actually change the state of the object.
 */
template<typename T> int DebugVector<T>::size() const
{
	return logicalLength;
}

template<typename T> bool DebugVector<T>::isEmpty() const
{
	return logicalLength == 0;
}

/* Both versions of the const-overloaded at function. */
template<typename T> T& DebugVector<T>::operator[] (int index)
{
	return array[index];
}

template<typename T> const T& DebugVector<T>::operator[] (int index) const
{
	return array[index];
}

/* removeAt deletes an element and shuffles things down. */
template<typename T> void DebugVector<T>::removeAt(int index)
{
	for(int i = index; i < logicalLength - 1; i++)
		array[i] = array[i + 1];
	
	logicalLength --;
}

/* Inserts a new element, growing if necessary, then shuffles things down. */
template<typename T> void DebugVector<T>::insertAt(const T& value, int index)
{
	if(logicalLength == allocatedLength)
		grow();

	for(int i = logicalLength; i > index; i--)
		array[i] = array[i - 1];
		
	array[index] = value;
	logicalLength ++;
}

/* Appends an element - effectively a glorified call to insertAt. */
template<typename T> void DebugVector<T>::append(const T& value)
{
	insertAt(value, logicalLength);
}

/* Grows the vector when we need more space. */
template<typename T> void DebugVector<T>::grow()
{
	/* In case we were cleared out, reset to the start size. */
	if(allocatedLength == 0)
		allocatedLength = START_SIZE;

	allocatedLength *= 2;
	T *newArray = new T[allocatedLength];

	for(int i = 0; i < logicalLength; i++)
		newArray[i] = array[i];

	delete [] array;
	array = newArray;
}

/* operator< compares two DebugVectors as follows:
 * 1. If one vector is shorter than another, the shorter vector
 *    is less than the longer vector.
 * 2. If the vectors have the same length, use a lexicographical
 *    comparison of the two vectors.
 *
 *
 * NOTE: After lecture, I remembered that (surprise!) there is an
 * STL algorithm that performs this very task.  The algorithm
 * is lexicographical_compare, which takes in two iterator
 * ranges and returns whether the first is lexicographically
 * less than the second.  Thus we can rewrite the entire
 * function below as
 *
 * return lexicographical_compare(begin(), end(), other.begin(), other.end());
 *
 * This performs a true lexicographical comparison, which means that it will not
 * compare the lengths of the two vectors against each other explicitly (e.g. if one
 * is shorter than another, the initial segments of both vectors will still be
 * compared against each other).  While this isn't exactly identical to the code
 * below, it is nonetheless a valid way of comparing two vectors.
 *
 * The code written in lecture is reproduced below:
 */
template <typename T>
bool DebugVector<T>::operator <(const DebugVector& other) const
{
	/* Check for length mismatch.  If there's a clear winner, return
	 * the appropriate value.
	 */
	if(logicalLength < other.logicalLength) return true;
	if(other.logicalLength < logicalLength) return false;

	/* Now, compare each element individually and return if there are
	 * any mismatches.
	 */
	for(int i = 0; i < logicalLength; ++i)
	{
		if(array[i] < other.array[i])
			return true;

		/* Note that we use the < operator here instead of >, because
		 * > might not be defined.
		 */
		if(other.array[i] < array[i])
			return false;
	}

	/* Must be equal!  Return false. */
	return false;
}

const int NUM_INTS = 10;

int main()
{
	/* Populate the vector. */
	DebugVector<int> myVector(NUM_INTS);
	for(int i = 0; i < NUM_INTS; ++i)
		myVector[i] = i;

	/* Print out the vector. */
	copy(myVector.begin(), myVector.end(), ostream_iterator<int>(cout, "\n"));
	return 0;
}