dynamic_array.c

#include <stdlib.h>
#include <assert.h>


/*
 * DYNAMIC ARRAY
 */

 /*
  * Dynamic array structure.
  *
  * vt is the virtual method table
  * array is a pointer to the actual array
  * capacity is the size of the actual array
  * length is the number of elements in the array
  */
 typedef struct DynamicArrayVT DynamicArrayVT;
 typedef struct {
     DynamicArrayVT* vt;
     int* _array;
     int _capacity;
     int _length;
 } DynamicArray_Struct, *DynamicArray;

/*
 * Virtual table for the type DynamicArray.
 */
typedef struct DynamicArrayVT {
    int (*elemAtRank)(DynamicArray da, int i);
    void (*replaceAtRank)(DynamicArray da, int i, int elem);
    void (*addLast)(DynamicArray da, int elem);
    int (*removeLast)(DynamicArray da);
    void (*destroy)(DynamicArray da);
} DynamicArrayVT;

/*
 * Returns the element at the position `i`.
 */
int elemAtRank(DynamicArray da, int i) {
    assert(da->_length >= i);
    return da->_array[i];
}

/*
 * Replaces the element at the position `i` by the element `elem`.
 */
void replaceAtRank(DynamicArray da, int i, int elem) {
    assert(da->_length >= i);
    da->_array[i] = elem;
}

/*
 * Appends `elem` to the array.
 *
 * If the space allocated to `da->array` is already
 * full, then we allocate twice the space to a new array A, copy the contents
 * of `da->array` to A, and set `da->array` to A.
 */
void addLast(DynamicArray da, int elem) {
    if (da->_length == da->_capacity) {
        da->_capacity *= 2;
        da->_array = (int*) realloc(da->_array, sizeof(int) * da->_capacity);
    }

    da->_array[da->_length++] = elem;
}

/*
 * Pops and removes the last element of the array.
 *
 * If this caused the array occupation rate (defined as the ratio of `da->length`
 * and `da->capacity`) to drop below 1/2, then shrink `da->array` to 3/4
 * of the initial capacity.
 */
int removeLast(DynamicArray da) {
    int ret = da->_array[(da->_length--) - 1];

    float occupancyRate = da->_length / (float) da->_capacity;
    if (occupancyRate < 0.5) {
        size_t newSize = (size_t) (sizeof(int) * da->_capacity * 0.75);
        da->_array = (int*) realloc(da->_array, newSize);
    }

    return ret;
}

void destroy(DynamicArray da) {
    free(da->_array);
    free(da);
}

/*
 * Default dynamic array virtual table
 */
DynamicArrayVT dynamicArrayVT = {
    .elemAtRank = elemAtRank,
    .replaceAtRank = replaceAtRank,
    .addLast = addLast,
    .removeLast = removeLast,
    .destroy = destroy
};

/*
 * Constructs a dynamic array of specified `capacity`.
 */
DynamicArray newDynamicArray(int capacity) {
    DynamicArray self = (DynamicArray) malloc(sizeof(DynamicArray_Struct));
    self->vt = &dynamicArrayVT;
    self->_array = (int*) malloc(sizeof(int) * capacity);
    self->_capacity = capacity;
    self->_length = 0;
    return self;
}