From aa784eaece4425c6145419ea9d1baa5da51a3cc6 Mon Sep 17 00:00:00 2001 From: leiyu3 Date: Thu, 22 Sep 2022 13:47:34 -0400 Subject: add resizing --- libvector.c | 37 +++++++++++------- vector.c | 120 ---------------------------------------------------------- vector.h | 4 +- vector_test.c | 32 ++++++++++++++-- 4 files changed, 55 insertions(+), 138 deletions(-) delete mode 100644 vector.c diff --git a/libvector.c b/libvector.c index 69537ab..f099e34 100644 --- a/libvector.c +++ b/libvector.c @@ -42,24 +42,13 @@ int at(vector_t vec, int index){ } void push(vector_t *vec, int value){ - if (is_full(*vec)){ - printf("Array out of Size!!\n\ - Can't push!! \n\ - Not yet implemented resize!!\n"); - exit(-1); - } - + resize_vec_check(vec); vec->arr[vec->cur_size] = value; vec->cur_size++; } void insert(vector_t *vec, int index, int val){ - if (is_full(*vec)){ - printf("Array out of Size!!\n\ - Can't insert!\n\ - Not yet implemented resize!!\n"); - exit(1); - } + resize_vec_check(vec); int tmp; for (int i = index; i <= vec->cur_size; i++){ @@ -82,6 +71,7 @@ void delete_vec(vector_t *vec, int index){ } vec->cur_size = vec->cur_size - 1; + resize_vec_check(vec); } void remove_val(vector_t *vec, int value){ @@ -93,6 +83,7 @@ void remove_val(vector_t *vec, int value){ } i++; } + resize_vec_check(vec); } void prepend(vector_t *vec, int value){ @@ -103,6 +94,7 @@ int pop(vector_t *vec){ // remove item at the end, return value int ret = vec->arr[vec->cur_size-1]; vec->cur_size--; + resize_vec_check(vec); return ret; } @@ -119,7 +111,7 @@ void destroy_vec(vector_t *vec){ free(vec->arr); } -int find(vector_t vec, int value){ +int find_vec(vector_t vec, int value){ for (int i = 0; i < size(vec); i++){ if (at(vec, i) == value){ return i; @@ -128,3 +120,20 @@ int find(vector_t vec, int value){ return -1; } +void resize_vec_check(vector_t *vec){ + int capacity = vec->max_size; + int cur_size = vec->cur_size; + + if (cur_size == capacity){ + resize_vec(vec, capacity*2); + } + if (cur_size <= capacity/4){ + resize_vec(vec, capacity/2); + } +} + +void resize_vec(vector_t *vec, int new_capacity){ + vec->arr = (int*)realloc(vec->arr, sizeof(int)*new_capacity); + vec->max_size = new_capacity; +} + diff --git a/vector.c b/vector.c deleted file mode 100644 index 2c8f8d2..0000000 --- a/vector.c +++ /dev/null @@ -1,120 +0,0 @@ -#include -#include - -vector_t vector_init(int size){ - vector_t vec; - vec.max_size = size; - vec.arr = malloc(sizeof(int)*vec.max_size); - vec.cur_size = 0; - return vec; -} - -int size(vector_t vec){ - return vec.cur_size; -} - -int capacity(vector_t vec){ - return vec.max_size; -} - -int is_empty(vector_t vec){ - if (vec.cur_size == 0){ - return 1; - } - return 0; -} - -int is_full(vector_t vec){ - if (vec.cur_size >= vec.max_size){ - return 1; - } - return 0; -} - -int at(vector_t vec, int index){ - if (index >= vec.max_size){ - printf("Index out of bound!!\n"); - exit(1); - } - - return vec.arr[index]; -} - -void push(vector_t *vec, int value){ - if (is_full(*vec)){ - printf("Array out of Size!!\n\ - Can't push!! \n\ - Not yet implemented resize!!\n"); - exit(1); - } - - vec->arr[vec->cur_size] = value; - vec->cur_size++; -} - -void insert(vector_t *vec, int index, int val){ - if (is_full(*vec)){ - printf("Array out of Size!!\n\ - Can't insert!\n\ - Not yet implemented resize!!\n"); - exit(1); - } - - int tmp; - for (int i = index; i <= vec->cur_size; i++){ - tmp = val; - val = vec->arr[i]; - vec->arr[i] = tmp; - } - vec->cur_size += 1; -} - -void delete(vector_t *vec, int index){ - if (!(index < vec->cur_size)){ - printf("Invalid Index!\nFailed to Delete Element\n"); - exit(-1); - } - int len = vec->cur_size - 1; - - for (int i = index; i < len; i++){ - vec->arr[i] = vec->arr[i+1]; - } - - vec->cur_size = vec->cur_size - 1; -} - -void remove_val(vector_t *vec, int value){ - int i = 0; - while (i < vec->cur_size){ - if (vec->arr[i] == value){ - delete(vec, i); - continue; - } - i++; - } -} - -void prepend(vector_t *vec, int value){ - insert(vec, 0, value); -} - -int pop(vector_t *vec){ - // remove item at the end, return value - int ret = vec->arr[vec->cur_size-1]; - vec->cur_size--; - return ret; -} - -void print_vec(vector_t vec){ - printf("["); - for (int i = 0; i < vec.cur_size; i++){ - printf("%d ", vec.arr[i]); - - } - printf("]\n"); -} - -void destroy_vec(vector_t *vec){ - free(vec->arr); -} - diff --git a/vector.h b/vector.h index 2dec5ec..aa91c89 100644 --- a/vector.h +++ b/vector.h @@ -21,6 +21,8 @@ void prepend(vector_t *vec, int value); int pop(vector_t *vec); void print_vec(vector_t vec); void destroy_vec(vector_t *vec); -int find(vector_t vec, int value); +int find_vec(vector_t vec, int value); +void resize_vec_check(vector_t *vec); +void resize_vec(vector_t *vec, int new_capacity); #endif diff --git a/vector_test.c b/vector_test.c index dcab29b..3fcfd46 100644 --- a/vector_test.c +++ b/vector_test.c @@ -84,7 +84,7 @@ Test(vectortests, delete_check){ } Test(vectortests, remove_test){ - for (int i = 0; i < vec.max_size; i++){ + for (int i = 0; i < 16; i++){ if (i%2 == 0){ push(&vec, 5); continue; @@ -120,11 +120,37 @@ Test(vectortests, find_test){ push(&vec, 6); push(&vec, 9); - cr_assert(find(vec, 9)==2); + cr_assert(find_vec(vec, 9)==2); + cr_assert(find_vec(vec, 99)==-1); +} + +Test(vectortests, resize_test){ + cr_assert(capacity(vec)==n); + resize_vec(&vec, 8); + cr_assert(capacity(vec)==8, "new capacity is %d", capacity(vec)); + resize_vec(&vec, 32); + cr_assert(capacity(vec)==32, "new capacity is %d", capacity(vec)); +} + +Test(vectortests, resize_large_size_test){ + for (int i = 0; i < 65; i++){ + push(&vec, i); + } - cr_assert(find(vec, 99)==-1); + cr_assert(capacity(vec)==128); + for (int i = 0; i < 63; i++){ + pop(&vec); + } + + cr_assert(capacity(vec)==4, "capacity is %d", capacity(vec)); + + pop(&vec); + + cr_assert(capacity(vec)==2, "capacity is %d", capacity(vec)); } + + -- cgit v1.2.3