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