1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
#include <stdio.h>
#include <stdlib.h>
#include "vector.h"
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;
}
void check_valid_index(vector_t vec, int index){
if (index > size(vec) || index < 0){
printf("Index out of bound!!\n");
exit(-1);
}
}
int at(vector_t vec, int index){
check_valid_index(vec, index);
return vec.arr[index];
}
void push(vector_t *vec, int value){
resize_vec_check(vec);
vec->arr[vec->cur_size] = value;
vec->cur_size++;
}
void insert(vector_t *vec, int index, int val){
check_valid_index(*vec, index);
resize_vec_check(vec);
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_vec(vector_t *vec, int index){
check_valid_index(*vec, index);
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;
resize_vec_check(vec);
}
void remove_val(vector_t *vec, int value){
int i = 0;
while (i < vec->cur_size){
if (vec->arr[i] == value){
delete_vec(vec, i);
continue;
}
i++;
}
resize_vec_check(vec);
}
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--;
resize_vec_check(vec);
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);
}
int find_vec(vector_t vec, int value){
for (int i = 0; i < size(vec); i++){
if (at(vec, i) == value){
return i;
}
}
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;
}
|
