1/* copyright (c) 2022 - 2026 grunfink et al. / MIT license */
  2
  3#ifndef _XS_LIST_TOOLS_H
  4
  5#define _XS_LIST_TOOLS_H
  6
  7#include "xs.h"
  8
  9 xs_list *xs_list_insert_sorted(xs_list *list, const xs_val *nv);
 10 xs_val **xs_list_to_array(const xs_list *l, int *len);
 11 int xs_list_sort_cmp(const void *p1, const void *p2);
 12 int xs_list_sort_inv_cmp(const void *p1, const void *p2);
 13 int xs_list_sort_dict_cmp(const char *field, const void *p1, const void *p2);
 14 xs_list *xs_list_sort(const xs_list *l, int (*cmp)(const void *, const void *));
 15 xs_list *xs_list_shuffle(const xs_list *l);
 16
 17#ifdef XS_IMPLEMENTATION
 18
 19#include "xs_random.h"
 20
 21xs_list *xs_list_insert_sorted(xs_list *list, const xs_val *nv)
 22/* inserts a string in the list in its ordered position */
 23{
 24    XS_ASSERT_TYPE(list, XSTYPE_LIST);
 25
 26    int offset = xs_size(list);
 27
 28    const xs_val *v;
 29    xs_list_foreach(list, v) {
 30        /* if this element is greater or equal, insert here */
 31        if (xs_cmp(v, nv) >= 0) {
 32            offset = v - list;
 33            break;
 34        }
 35    }
 36
 37    return _xs_list_write_litem(list, offset - 1, nv, xs_size(nv));
 38}
 39
 40
 41xs_val **xs_list_to_array(const xs_list *l, int *len)
 42/* converts a list to an array of values */
 43/* must be freed after use */
 44{
 45    *len = xs_list_len(l);
 46    xs_val **a = xs_realloc(NULL, *len * sizeof(xs_val *));
 47    const xs_val *v;
 48    int n = 0;
 49
 50    xs_list_foreach(l, v)
 51        a[n++] = (xs_val *)v;
 52
 53    return a;
 54}
 55
 56
 57int xs_list_sort_cmp(const void *p1, const void *p2)
 58/* default list sorting function */
 59{
 60    const xs_val *v1 = *(xs_val **)p1;
 61    const xs_val *v2 = *(xs_val **)p2;
 62
 63    return xs_cmp(v1, v2);
 64}
 65
 66
 67int xs_list_sort_inv_cmp(const void *p1, const void *p2)
 68/* default list inverse sorting function */
 69{
 70    const xs_val *v1 = *(xs_val **)p1;
 71    const xs_val *v2 = *(xs_val **)p2;
 72
 73    return xs_cmp(v2, v1);
 74}
 75
 76
 77int xs_list_sort_dict_cmp(const char *field, const void *p1, const void *p2)
 78/* compare sorting function for a field an array of dicts */
 79{
 80    const xs_dict *d1 = *(xs_val **)p1;
 81    const xs_dict *d2 = *(xs_val **)p2;
 82
 83    if (xs_type(d1) != XSTYPE_DICT || xs_type(d2) != XSTYPE_DICT)
 84        return 0;
 85
 86    return xs_cmp(xs_dict_get_def(d1, field, ""),
 87                  xs_dict_get_def(d2, field, ""));
 88}
 89
 90
 91xs_list *xs_list_sort(const xs_list *l, int (*cmp)(const void *, const void *))
 92/* returns a sorted copy of l. cmp can be null for standard sorting */
 93{
 94    int sz;
 95    xs_val **a = xs_list_to_array(l, &sz);
 96    xs_list *nl = xs_dup(l);
 97    char *p = nl + 1 + _XS_TYPE_SIZE;
 98
 99    /* sort the array */
100    qsort(a, sz, sizeof(xs_val *), cmp ? cmp : xs_list_sort_cmp);
101
102    /* transfer the sorted list over the copy */
103    for (int n = 0; n < sz; n++) {
104        /* get the litem */
105        const char *e = a[n] - 1;
106        int z = xs_size(e);
107
108        memcpy(p, e, z);
109        p += z;
110    }
111
112    xs_free(a);
113
114    return nl;
115}
116
117
118xs_list *xs_list_shuffle(const xs_list *l)
119/* returns a shuffled list */
120{
121    int sz;
122    xs_val **a = xs_list_to_array(l, &sz);
123    xs_list *nl = xs_list_new();
124    unsigned int seed = 0;
125
126    xs_rnd_buf(&seed, sizeof(seed));
127
128    /* shuffle */
129    for (int n = sz - 1; n > 0; n--) {
130        int m = xs_rnd_int32_d(&seed) % n;
131        void *p = a[n];
132        a[n] = a[m];
133        a[m] = p;
134    }
135
136    for (int n = 0; n < sz; n++)
137        nl = xs_list_append(nl, a[n]);
138
139    xs_free(a);
140
141    return nl;
142}
143
144
145#endif /* XS_IMPLEMENTATION */
146
147#endif /* XS_LIST_TOOLS_H */