Last active
February 10, 2016 23:20
-
-
Save PiotrJander/af95d25a72f6b00f4623 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment