aboutsummaryrefslogtreecommitdiff
path: root/arraylist.c
diff options
context:
space:
mode:
Diffstat (limited to 'arraylist.c')
-rw-r--r--arraylist.c368
1 files changed, 0 insertions, 368 deletions
diff --git a/arraylist.c b/arraylist.c
deleted file mode 100644
index f010d07..0000000
--- a/arraylist.c
+++ /dev/null
@@ -1,368 +0,0 @@
1/* arraylist */
2#include <assert.h>
3#include <stdbool.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7#include <time.h>
8
9#include "util.h"
10
11typedef int T;
12
13struct ArrayList {
14 T ** array;
15 size_t size;
16 size_t capacity;
17};
18
19static T **
20ArrayList_allocateArray(void *ptr, size_t nelem)
21{
22 T **new_ptr = reallocarray(ptr, nelem, sizeof *new_ptr);
23
24 if ( new_ptr == NULL ) {
25 ERROR("out of memory");
26 }
27
28 return new_ptr;
29}
30
31void
32ArrayList_init(struct ArrayList *arrayList)
33{
34 assert(arrayList);
35
36 arrayList->array = NULL;
37 arrayList->size = 0;
38 arrayList->capacity = 0;
39}
40
41struct ArrayList *
42ArrayList_new(void)
43{
44 struct ArrayList *arrayList = malloc(sizeof *arrayList);
45 if ( arrayList ) {
46 ArrayList_init(arrayList);
47 }
48 return arrayList;
49}
50
51void
52ArrayList_free(struct ArrayList *arrayList)
53{
54 assert(arrayList);
55
56 free(arrayList->array);
57 ArrayList_init(arrayList);
58}
59
60void
61ArrayList_delete(struct ArrayList *arrayList)
62{
63 assert(arrayList);
64
65 ArrayList_free(arrayList);
66 free(arrayList);
67}
68
69static void
70ArrayList_growIfNeeded(struct ArrayList *arrayList)
71{
72 assert(arrayList);
73
74 if ( arrayList->size == arrayList->capacity ) {
75 if ( arrayList->array == NULL ) { // leere Liste
76 assert(arrayList->size == 0);
77 assert(arrayList->capacity == 0);
78
79 static const size_t DEFAULT_CAPACITY = 10;
80
81 arrayList->capacity = DEFAULT_CAPACITY;
82 arrayList->array = ArrayList_allocateArray(NULL, DEFAULT_CAPACITY);
83 }
84 else {
85 size_t new_capacity = (arrayList->capacity * 3) / 2; // *= 1.5
86 T ** new_arrayList = ArrayList_allocateArray(arrayList->array, new_capacity);
87
88 arrayList->capacity = new_capacity;
89 arrayList->array = new_arrayList;
90 }
91
92 assert(arrayList->array);
93 }
94
95 assert(arrayList->capacity > arrayList->size);
96}
97
98void
99ArrayList_append(struct ArrayList *arrayList, T *ptr)
100{
101 assert(arrayList);
102
103 ArrayList_growIfNeeded(arrayList);
104
105 arrayList->array[arrayList->size++] = ptr;
106}
107
108void
109ArrayList_insertAt(struct ArrayList *arrayList, size_t idx, T *ptr)
110{
111 assert(arrayList);
112 assert(idx <= arrayList->size); // allow last position
113
114 ArrayList_growIfNeeded(arrayList);
115
116 memmove(&arrayList->array[idx + 1],
117 &arrayList->array[idx],
118 (arrayList->size - idx) * sizeof arrayList->array[0]);
119 arrayList->array[idx] = ptr;
120 ++arrayList->size;
121}
122
123T *
124ArrayList_getAt(struct ArrayList *arrayList, size_t idx)
125{
126 assert(arrayList);
127 assert(idx < arrayList->size);
128
129 return arrayList->array[idx];
130}
131
132size_t
133ArrayList_size(struct ArrayList *arrayList)
134{
135 assert(arrayList);
136
137 return arrayList->size;
138}
139
140bool
141ArrayList_empty(struct ArrayList *arrayList)
142{
143 assert(arrayList);
144
145 return arrayList->size == 0;
146}
147
148void
149ArrayList_removeAt(struct ArrayList *arrayList, size_t idx, void clear_func(T *, void *), void *args)
150{
151 assert(arrayList);
152 assert(idx < arrayList->size);
153
154 if ( clear_func ) {
155 clear_func(arrayList->array[idx], args);
156 }
157
158#if defined(ARRAYLIST_KEEP_ORDER)
159 memmove(&arrayList->arrayList[idx],
160 &arrayList->arrayList[idx + 1],
161 (arrayList->size - (idx + 1)) * sizeof arrayList->arrayList[0]);
162#else
163 arrayList->array[idx] = arrayList->array[arrayList->size - 1];
164#endif
165
166 --arrayList->size;
167}
168
169struct qsortHelper_context {
170 int (*cmp)(const T *, const T *, void *);
171 void *args;
172};
173
174typedef const T *const_T_ptr;
175
176static int
177ArrayList_qsortHelper(void *ctx, const void *a, const void *b)
178{
179 const const_T_ptr *aa = a;
180 const const_T_ptr *bb = b;
181
182 const struct qsortHelper_context *context = ctx;
183
184 return context->cmp(*aa, *bb, context->args);
185}
186
187void
188ArrayList_sort(struct ArrayList *arrayList, int cmp(const T *, const T *, void *), void *args)
189{
190 assert(arrayList);
191 assert(cmp);
192
193 struct qsortHelper_context context = {
194 .cmp = cmp,
195 .args = args
196 };
197
198 // Das vollständige qsort_x()-Drama: https://stackoverflow.com/a/46042467
199 qsort_r(arrayList->array, arrayList->size, sizeof arrayList->array[0], &context, ArrayList_qsortHelper);
200}
201
202bool
203ArrayList_linearSearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *, void *), void *args, size_t *loc)
204{
205 assert(arrayList);
206 assert(cmp);
207 assert(loc);
208
209 for ( size_t idx = 0; idx != arrayList->size; ++idx ) {
210 if ( cmp(key, arrayList->array[idx], args) == 0 ) {
211 *loc = idx;
212 return true;
213 }
214 }
215 return false;
216}
217
218struct bsearchHelper_context {
219 void *key;
220 int (*cmp)(void *, const T *, void *);
221 void *args;
222};
223
224static int
225ArrayList_bsearchHelper(const void *ctx, const void *el)
226{
227 const struct bsearchHelper_context *context = ctx;
228 const const_T_ptr * element = el;
229
230 return context->cmp(context->key, *element, context->args);
231}
232
233bool
234ArrayList_binarySearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *, void *), void *args, size_t *loc)
235{
236 assert(arrayList);
237 assert(cmp);
238 assert(loc);
239
240 struct bsearchHelper_context context = {
241 .key = key,
242 .cmp = cmp,
243 .args = args
244 };
245
246 T **pos = bsearch(&context, arrayList->array, arrayList->size, sizeof arrayList->array[0], ArrayList_bsearchHelper);
247 if ( pos ) {
248 *loc = (size_t)(pos - arrayList->array);
249 return true;
250 }
251 else {
252 return false;
253 }
254}
255
256void
257ArrayList_shuffle(struct ArrayList *arrayList, size_t rng(size_t, void *), void *args)
258{
259 assert(arrayList);
260 assert(rng);
261
262 if ( arrayList->size > 1 ) {
263 for ( size_t i = arrayList->size - 1; i > 0; --i ) {
264 size_t j = rng(i + 1, args);
265
266 // swap
267 T *t = arrayList->array[j];
268 arrayList->array[j] = arrayList->array[i];
269 arrayList->array[i] = t;
270 }
271 }
272}
273
274static void
275ArrayList_debugPrint(struct ArrayList *arrayList)
276{
277 for ( size_t idx = 0; idx != ArrayList_size(arrayList); ++idx ) {
278 T *ptr = ArrayList_getAt(arrayList, idx);
279 printf("%d, ", *ptr);
280 }
281 putchar('\n');
282}
283
284static int
285my_compare(const T *a, const T *b, void *args)
286{
287 (void) args;
288
289 if ( *a > *b )
290 return 1;
291 else if ( *a < *b )
292 return -1;
293 else
294 return 0;
295}
296
297static int
298my_search_compare(void *key, const T *element, void *args)
299{
300 (void) args;
301
302 int *a = key;
303
304 if ( *a < *element )
305 return -1;
306 else if ( *a > *element )
307 return 1;
308 else
309 return 0;
310}
311
312static size_t
313my_rng(size_t max, void *args)
314{
315 (void) args;
316 return (size_t) rand() % max;
317}
318
319static void
320ArrayList_testSort(struct ArrayList *arrayList)
321{
322 for ( size_t i = 1; i < arrayList->size; ++i ) {
323 if ( *arrayList->array[i - 1] > *arrayList->array[i] ) {
324 fprintf(stderr, "Fehler: %zu (%d, %d)\n", i, *arrayList->array[i - 1], *arrayList->array[i]);
325 exit(EXIT_FAILURE);
326 }
327 }
328}
329
330int
331main(void)
332{
333 srand(time(NULL));
334
335 int a = 11, b = 22, c = 33, d = 44;
336
337 struct ArrayList *arrayList = ArrayList_new();
338
339 ArrayList_append(arrayList, &a);
340 ArrayList_append(arrayList, &b);
341 ArrayList_append(arrayList, &c);
342 ArrayList_append(arrayList, &d);
343 ArrayList_debugPrint(arrayList); // 11, 22, 33, 44
344
345 ArrayList_removeAt(arrayList, 0, NULL, NULL);
346 ArrayList_debugPrint(arrayList); // 44, 22, 33
347
348 ArrayList_insertAt(arrayList, 3, &a);
349 ArrayList_debugPrint(arrayList); // 44, 22, 33, 11
350
351 ArrayList_sort(arrayList, my_compare, NULL);
352 ArrayList_testSort(arrayList);
353
354 ArrayList_debugPrint(arrayList); // 11, 22, 33, 44
355
356 size_t loc;
357 int dummy = 44;
358 if ( ArrayList_binarySearch(arrayList, &dummy, my_search_compare, NULL, &loc) ) {
359 printf("Gefunden: %zu\n", loc);
360 }
361
362 ArrayList_shuffle(arrayList, my_rng, NULL);
363 ArrayList_debugPrint(arrayList); // ??
364
365 ArrayList_delete(arrayList);
366
367 return EXIT_SUCCESS;
368}