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