#include "arrayList.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

// Write declarations of static helper functions below:
static void shiftArray(int index, arrayList *const pAL);

/**  Creates a new, empty arrayList object such that:
 * 
 *      - capacity equals dimension
 *      - elemSz equals the size (in bytes) of the data objects the user
 *        will store in the arrayList
 *      - data points to a block of memory large enough to hold capacity
 *        user data objects
 *      - usage is zero
 *      - the user's comparison function is correctly installed
 *      - the user's clean function is correctly installed, if provided

 *   Returns:  new arrayList object
 */
arrayList *AL_create(uint32_t dimension, uint32_t elemSz,
					 int32_t (*compareElems)(const void *const pLeft, const void *const pRight),
					 void (*cleanElem)(void *const pElem))
{
	arrayList *result = malloc(sizeof(arrayList));

	result->capacity = dimension;
	result->elemSz = elemSz;
	result->data = calloc(result->capacity, result->elemSz);
	result->usage = 0;

	result->compareElems = compareElems;
	result->cleanElem = cleanElem;

	return result;
}

/**  Inserts the user's data object into the arrayList.
 * 
 *   Pre:     *pAL is a proper arrayList object
 *            *pElem is a valid user data object
 *   Post:    a copy of the user's data object has been inserted, at the
 *            position defined by the user's compare function
 *   Returns: true unless the insertion fails (unlikely unless it's not
 *            possible to increase the size of the arrayList
 */
bool AL_insert(arrayList *const pAL, const void *const pElem)
{
	if (pAL->usage == pAL->capacity)
	{
		pAL->data = realloc(pAL->data, (2 * pAL->capacity) * pAL->elemSz);
		pAL->capacity += pAL->capacity;
	}

	// Checks for insertion into empty arrayList
	if (!pAL->usage)
		memcpy(pAL->data, pElem, pAL->elemSz);
	else
	{
		uint32_t i;
		// Finds correct index for object insertion
		for (i = 0; i < pAL->usage; i++)
			if (pAL->compareElems(pAL->data + (i * pAL->elemSz), pElem) > 0)
				break;
		// Call to static helper shiftArray()
		shiftArray(i, pAL);
		memcpy(pAL->data + (i * pAL->elemSz), pElem, pAL->elemSz);
	}

	pAL->usage++;

	return true;
}

/**  Returns pointer to the data object at the given index.
 * 
 *   Pre:      *pAL is a proper arrayList object
 *             indexis a valid index for *pAL
 *   Returns:  pointer to the data object at index in *pAL; NULL if no
 *             such data object exists
 */
void *AL_elemAt(const arrayList *const pAL, uint32_t index)
{
	return (void *)(pAL->data + (index * pAL->elemSz));
}

/**  Searches for a matching object in the arrayList.
 * 
 *   Pre:      *pAL is a proper arrayList object
 *             *pElem is a valid user data object
 *   Returns:  pointer to a matching data object in *pAL; NULL if no
 *             match can be found
 */
void *AL_find(const arrayList *const pAL, const void *const pElem)
{
	uint32_t i;
	for (i = 0; i < pAL->usage; i++)
		// Checks to see if pElem is equal to the element at the current index
		if (pAL->compareElems(pAL->data + (i * pAL->elemSz), pElem) == 0)
			return pAL->data + (i * pAL->elemSz);

	return NULL;
}

/**  Deallocates all dynamic content in the arrayList, including any
 *   dynamic content in the user data objects in the arrayList.
 * 
 *   Pre:   *pAL is a proper arrayList object
 *   Post:  the data array in *pAL has been freed, as has any dynamic
 *          memory associated with the user data objects that were in
 *          that array (via the user-supplied clean function); all the
 *          fields in *pAL are set to 0 or NULL, as appropriate.
 */
void AL_clean(arrayList *const pAL)
{
	uint32_t i = 0;
	while (i < pAL->usage)
		// Uses the user-specified clean function to free data within the data objects
		pAL->cleanElem(pAL->data + (i++ * pAL->elemSz));

	free(pAL->data);
	pAL->usage = 0;
}

// Write definitions of static helper functions below:
static void shiftArray(int index, arrayList *const pAL)
{
	for (int i = pAL->usage; i > index; i--)
		// Shifts all elements greater than the element at index to the right by 1
		memcpy(pAL->data + (i * pAL->elemSz), pAL->data + ((i - 1) * pAL->elemSz), pAL->elemSz);
}