/* vector.cpp, version 1.0
 *
 * A partial implementation of the Vector class defined in Vector.h.
 * This is an INCOMPLETE implementation and is missing several functions.
 * We will implement them next lecture.
 */

#include "vector.h"
#include <algorithm>

/* Vector constructor initializes the internal array to a reasonable
 * starting size.
 */
Vector::Vector()
{
	elems = new string[8];
	logicalLength = 0;
	allocatedLength = 8;
}

/* Destructor deallocates stored resources. */
Vector::~Vector()
{
	delete [] elems;
}

/* Returns the number of elements stored in the Vector. */
size_t Vector::size()
{
	return logicalLength;
}

/* Since Vector::iterators are really string*s, this function
 * will return the elems array.  Because of array/pointer
 * duality and the fact that STL iterators are modeled after
 * raw pointers, this function returns an iterator to the first
 * element of the Vector.
 */
Vector::iterator Vector::begin()
{
	return elems;
}

/* Returns an iterator to the position one past the end of the Vector. */
Vector::iterator Vector::end()
{
	/* Note that this implementation is defined entirely in terms of the
	 * public interface of the Vector class.  This is an extremely useful
	 * design trick.  If we were to change the representation of the Vector
	 * to use an entirely different setup, this function would still be
	 * correct.  As a general rule, try as hard as possible to implement
	 * classes using their own public interface.
	 */
	return begin() + size();
}

/* Returns the amount of space we've allocated. */
size_t Vector::capacity()
{
	return allocatedLength;
}

/* Ensures that a particular amount of space exists.  We actually will
 * keep doubling the space until at least howMuch has been reserved so
 * that consecutive calls to reserve are unlikely to cause multiple
 * reallocations.
 */
void Vector::reserve(size_t howMuch)
{
	/* If space already exists, do nothing. */
	if (capacity() >= howMuch) return;

	/* Keep doubling the new space allocation until we end up
	 * with a value at least as bit as howMuch.
	 */
	while (allocatedLength < howMuch)
		allocatedLength *= 2;

	/* Create a new array to hold the values, then use the
	 * copy algorithm to duplicate our elements there.  Notice
	 * that the call to copy uses this Vector's begin() and end()
	 * member functions as parameters.
	 */
	string* newElems = new string[allocatedLength];
	copy(begin(), end(), newElems);

	/* Clean up the old array, then reset the elems pointer to use
	 * the new buffer.
	 */
	delete [] elems;
	elems = newElems;
}

/* The insert function ensures space exists, shuffles elements down one
 * position, and increases the number of elements by one.
 */
Vector::iterator Vector::insert(iterator where, string value)
{
	/* The following trick ensures that space exists for the
	 * new element.  Notice that we have to cache the index the
	 * iterator refers to in case there is a reallocation
	 * involved.
	 */
	ptrdiff_t offset = where - begin();
	reserve(size() + 1);
	where = begin() + offset;

	/* Shuffle the elements from the insert point onward down
	 * one position.  Notice that we use copy_backward instead of
	 * regular copy because the two ranges overlap.
	 */
	copy_backward(where, end(), end() + 1);

	/* Actually store the value in the Vector. */
	*where = value;

	/* Record that a new element was inserted. */
	++logicalLength;

	/* Per interface contract, return an iterator to the
	 * newly-inserted element.
	 */
	return where;
}

/* Appends an element. */
void Vector::push_back(string str)
{
	/* Notice that this is written entirely in terms of the public
	 * interface!
	 */
	insert(end(), str);
}

/* TODO:
 * 1. Implement erase
 * 2. Implement pop_back
 * 3. Implement at
 * 4. Implement empty
 * 5. Implement indexOf
 */