Find file
Fetching contributors…
Cannot retrieve contributors at this time
232 lines (194 sloc) 5.57 KB
/* dynArray.c: Dynamic Array implementation. */
#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"
/* ************************************************************************
Dynamic Array Functions
************************************************************************ */
/* Initialize (including allocation of data array) dynamic array.
param: v pointer to the dynamic array
param: cap capacity of the dynamic array
pre: v is not null
post: internal data array can hold cap elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
v->data = (int *) malloc(sizeof(int) * capacity);
assert(v->data != 0);
v->lock = 0;
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap capacity
and 0 elements in it.
*/
DynArr* newDynArr(int cap)
{
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /* free the space on the heap */
v->data = 0; /* make it point to null */
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v pointer to the dynamic array
pre: none
post: the memory used by v->data is freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v pointer to the dynamic array
param: cap the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
int i;
/* Create a new underlying array */
int *newData = (int*)malloc(sizeof(int)*newCap);
assert(newData != 0);
/* copy elements to new data array */
for(i = 0; i < v->size; i++)
newData[i] = v->data[i];
/* Delete the old underlying array */
freeDynArr(v);
/* update capacity and size and data */
v->data = newData;
v->capacity = newCap;
v->size = i;
}
/* Get the size of the dynamic array
param: v pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic array
param: v pointer to the dynamic array
param: val the value to add to the end of the dynamic array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is doubled
post: val is in the last utilized position in the array
*/
void addDynArr(DynArr *v, int val)
{
/* Check to see if a resize is necessary */
if(v->size >= v->capacity)
_dynArrSetCapacity(v, 2 * v->capacity);
v->data[v->size] = val;
v->size++;
}
/* Get an element from the dynamic array from a specified position
param: v pointer to the dynamic array
param: pos integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and >= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
int getDynArr(DynArr *v, int pos)
{
assert(pos < v->size);
assert(pos >= 0);
return v->data[pos];
}
/* Put an item into the dynamic array at the specified location,
overwriting the element that was there
param: v pointer to the dynamic array
param: pos the index to put the value into
param: val the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the array
post: index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, int val)
{
assert(pos < v->size);
v->data[pos] = val;
}
/* Swap two specified elements in the dynamic array
param: v pointer to the dynamic array
param: i,j the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the dynamic array
post: index i now holds the value at j and index j now holds the value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
int temp;
assert(i < v->size);
assert(j < v->size);
temp = v->data[i];
v->data[i] = v->data[j];
v->data[j] = temp;
}
/* Remove the element at the specified location from the array,
shifts other elements back one to fill the gap
param: v pointer to the dynamic array
param: idx location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back one
*/
void removeAtDynArr(DynArr *v, int idx)
{
int i;
for(i = idx; i < v->size-1; ++i)
v->data[i] = v->data[i+1];
if(idx >= 0 && idx < v->size)
--v->size;
}
/* Copy elements from a dynamic array to another dynamic array
param: source pointer to the source dynamic array
param: destination pointer to the destination dynamic array
pre: s is not null and s is not empty
post: destination is initialized
post: the elements from source are copied to destination
*/
void copyDynArr(DynArr *source, DynArr *destination)
{
int i;
assert(source->size > 0);
initDynArr(destination, source->capacity);
/* copy elements to destination array */
for(i = 0; i < source->size; i++)
destination->data[i] = source->data[i];
destination->size = source->size;
}