Add numerical sort for files

Signed-off-by: Andrew Opalach <andrew@akon.city>

6 files changed, 291 insertions, 0 deletions

diff --git a/include/nnwt/sort.h b/include/nnwt/sort.h
new file mode 100644
index 0000000..571eb5d
--- /dev/null
+++ b/include/nnwt/sort.h
@@ -0,0 +1,3 @@
+#pragma once
+
+#include "../../src/util/sort.h"
diff --git a/meson.build b/meson.build
index 14d2245..751f6f6 100644
--- a/meson.build
+++ b/meson.build
@@ -15,6 +15,7 @@ naunet_src = [
   'src/util/error.c',
   'src/util/buffer.c',
   'src/util/packet.c',
+  'src/util/sort.c',
   'src/util/file/util.c'
 ]
 naunet_inc = [include_directories('include')]
diff --git a/src/util/sort.c b/src/util/sort.c
new file mode 100644
index 0000000..8d306a8
--- /dev/null
+++ b/src/util/sort.c
@@ -0,0 +1,61 @@
+#include <al/str.h>
+
+static inline u32 find_number(str *s)
+{
+    u32 i = 0;
+    while (i < s->length && !al_isnumber(al_str_at(s, i))) { i++; }
+    return (i == s->length) ? AL_STR_NO_POS : i;
+}
+
+static inline u32 find_non_number(str *s)
+{
+    u32 i = 0;
+    while (i < s->length && al_isnumber(al_str_at(s, i))) { i++; }
+    return i;
+}
+
+s32 nn_numerical_compare(const void *a, const void *b)
+{
+    str s1 = *(str *)a, s2 = *(str *)b;
+    s32 ret;
+    str sub1, sub2;
+    bool error;
+    s64 n1, n2;
+    u32 nn1 = find_number(&s1);
+    u32 nn2 = find_number(&s2);
+    if (nn1 != nn2) {
+        goto compare_remainder;
+    }
+    s1 = al_str_substr(&s1, nn1, s1.length);
+    s2 = al_str_substr(&s2, nn2, s2.length);
+    do {
+        nn1 = find_non_number(&s1);
+        nn2 = find_non_number(&s2);
+        sub1 = al_str_substr(&s1, 0, nn1);
+        sub2 = al_str_substr(&s2, 0, nn2);
+        n1 = al_str_to_long(&sub1, 10, &error);
+        al_assert(!error);
+        n2 = al_str_to_long(&sub2, 10, &error);
+        al_assert(!error);
+        if (n1 > n2) return 1;
+        else if (n1 < n2) return -1;
+        s1 = al_str_substr(&s1, nn1, s1.length);
+        s2 = al_str_substr(&s2, nn2, s2.length);
+        nn1 = find_number(&s1);
+        nn2 = find_number(&s2);
+        if (nn1 == AL_STR_NO_POS || nn2 == AL_STR_NO_POS) {
+            goto compare_remainder;
+        }
+        sub1 = al_str_substr(&s1, 0, nn1);
+        sub2 = al_str_substr(&s2, 0, nn2);
+        if (!al_str_eq(&sub1, &sub2)) {
+            goto compare_remainder;
+        }
+        s1 = al_str_substr(&s1, nn1, s1.length);
+        s2 = al_str_substr(&s2, nn2, s2.length);
+    } while (1);
+compare_remainder:
+    ret = al_str_cmp(&s1, &s2, 0, MIN(s1.length, s2.length));
+    if (ret == 0) return s1.length - s2.length;
+    return ret;
+}
diff --git a/src/util/sort.h b/src/util/sort.h
new file mode 100644
index 0000000..6c0cfc7
--- /dev/null
+++ b/src/util/sort.h
@@ -0,0 +1 @@
+s32 nn_numerical_compare(const void *a, const void *b);
diff --git a/tests/meson.build b/tests/meson.build
index 1074e40..70b06ef 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -1,3 +1,4 @@
+executable('units', ['units.c'], dependencies: naunet)
 executable('misc_file', ['misc_file.c'], dependencies: naunet)
 executable('condition_variable', ['condition_variable.c'], dependencies: naunet)
 executable('timer_thread', ['timer_thread.c'], dependencies: naunet)
diff --git a/tests/units.c b/tests/units.c
new file mode 100644
index 0000000..5cbd4a0
--- /dev/null
+++ b/tests/units.c
@@ -0,0 +1,224 @@
+#include <al/test.h>
+#include <al/str.h>
+#include <al/array.h>
+#include <al/random.h>
+#include <nnwt/common.h>
+#include <nnwt/sort.h>
+
+#define SHUFFLE_ARRAY(arr) do { \
+    al_assert((arr).count > 2); \
+    for (u32 i = 0; i < (arr).count - 2; i++) { \
+        u32 j = al_random_int(i, (arr).count - 1); \
+        SWAP(al_array_at(arr, i), al_array_at(arr, j)); \
+    } \
+} while (0)
+
+static bool sort_test_numerical_compare(void)
+{
+    AL_TEST_START("sort_numerical_compare");
+
+    array(str) strings;
+    al_array_init(strings);
+
+    str files1[] = {
+        al_str_c("631475239_1.jpg"),
+        al_str_c("631475239_2.jpg"),
+        al_str_c("631475239_3.jpg"),
+        al_str_c("631475239_4.jpg"),
+        al_str_c("631475239_5.jpg"),
+        al_str_c("631475239_6.jpg"),
+        al_str_c("631475239_7.jpg"),
+        al_str_c("631475239_8.jpg"),
+        al_str_c("631475239_9.jpg"),
+        al_str_c("631475239_10.jpg"),
+        al_str_c("631475239_11.jpg"),
+        al_str_c("631475239_12.jpg"),
+        al_str_c("631475239_13.jpg"),
+        al_str_c("631475239_14.jpg"),
+        al_str_c("631475239_15.jpg"),
+        al_str_c("631475239_15.jpg"),
+        al_str_c("631475239_16.jpg"),
+        al_str_c("631475239_17.jpg"),
+        al_str_c("631475239_18.jpg"),
+        al_str_c("631475239_19.jpg"),
+        al_str_c("631475239_20.m4v"),
+        al_str_c("631475239_21.mp4")
+    };
+
+    al_array_push(strings, files1[7]);
+    al_array_push(strings, files1[16]);
+    al_array_push(strings, files1[2]);
+    al_array_push(strings, files1[10]);
+    al_array_push(strings, files1[3]);
+    al_array_push(strings, files1[13]);
+    al_array_push(strings, files1[4]);
+    al_array_push(strings, files1[6]);
+    al_array_push(strings, files1[17]);
+    al_array_push(strings, files1[18]);
+    al_array_push(strings, files1[8]);
+    al_array_push(strings, files1[19]);
+    al_array_push(strings, files1[9]);
+    al_array_push(strings, files1[11]);
+    al_array_push(strings, files1[5]);
+    al_array_push(strings, files1[12]);
+    al_array_push(strings, files1[21]);
+    al_array_push(strings, files1[0]);
+    al_array_push(strings, files1[14]);
+    al_array_push(strings, files1[15]);
+    al_array_push(strings, files1[1]);
+    al_array_push(strings, files1[20]);
+    SHUFFLE_ARRAY(strings);
+
+    al_array_sort(strings, str, nn_numerical_compare);
+
+    for (u32 i = 0; i < strings.count; i++) {
+        AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files1[i]));
+    }
+
+    al_array_free(strings);
+
+    al_array_init(strings);
+
+    str files2[] = {
+        al_str_c("220.1png"),
+        al_str_c("220.jpg"),
+        al_str_c("220.png"),
+        al_str_c("35910.jpg"),
+        al_str_c("35910a.jpg"),
+        al_str_c("35910b.jpg"),
+        al_str_c("35910zzz.jpg"),
+    };
+
+    al_array_push(strings, files2[1]);
+    al_array_push(strings, files2[4]);
+    al_array_push(strings, files2[0]);
+    al_array_push(strings, files2[3]);
+    al_array_push(strings, files2[6]);
+    al_array_push(strings, files2[2]);
+    al_array_push(strings, files2[5]);
+    SHUFFLE_ARRAY(strings);
+
+    al_array_sort(strings, str, nn_numerical_compare);
+
+    for (u32 i = 0; i < strings.count; i++) {
+        AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files2[i]));
+    }
+
+    al_array_free(strings);
+
+    al_array_init(strings);
+
+    str files3[] = {
+        al_str_c("214124_a.jpeg"),
+        al_str_c("625315_a.jpeg"),
+        al_str_c("1412310_b_2.png"),
+        al_str_c("1412311_b.png"),
+        al_str_c("1412311_b_2.png"),
+        al_str_c("1412311_b_b.png")
+    };
+
+    al_array_push(strings, files3[1]);
+    al_array_push(strings, files3[4]);
+    al_array_push(strings, files3[0]);
+    al_array_push(strings, files3[3]);
+    al_array_push(strings, files3[2]);
+    al_array_push(strings, files3[5]);
+    SHUFFLE_ARRAY(strings);
+
+    al_array_sort(strings, str, nn_numerical_compare);
+    for (u32 i = 0; i < strings.count; i++) {
+        AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files3[i]));
+    }
+
+    al_array_free(strings);
+
+    al_array_init(strings);
+
+    str files4[] = {
+        al_str_c("pixiv_i_75528824_media0.png"),
+        al_str_c("pixiv_i_76697911_media0.png"),
+        al_str_c("pixiv_i_80864793_media0.png"),
+        al_str_c("pixiv_i_80864793_media0.png"),
+        al_str_c("pixiv_i_80864793_media0.png"),
+        al_str_c("pixiv_i_80864793_media1.png"),
+        al_str_c("pixiv_i_122898592_media0.jpg"),
+        al_str_c("pixiv_i_122898592_media1.jfif")
+    };
+
+    al_array_push(strings, files4[3]);
+    al_array_push(strings, files4[4]);
+    al_array_push(strings, files4[6]);
+    al_array_push(strings, files4[2]);
+    al_array_push(strings, files4[5]);
+    al_array_push(strings, files4[7]);
+    al_array_push(strings, files4[1]);
+    al_array_push(strings, files4[0]);
+    SHUFFLE_ARRAY(strings);
+
+    al_array_sort(strings, str, nn_numerical_compare);
+
+    for (u32 i = 0; i < strings.count; i++) {
+        AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files4[i]));
+    }
+
+    al_array_free(strings);
+
+    al_array_init(strings);
+
+    str files5[] = {
+        al_str_c("pixiv_i_24610911_media0.png"),
+        al_str_c("pixiv_i_27025514_media0.png"),
+        al_str_c("pixiv_i_33659689_media0.png"),
+        al_str_c("pixiv_i_42610626_media0.png"),
+        al_str_c("pixiv_i_49089079_media0.png"),
+        al_str_c("pixiv_i_49089079_media1.png"),
+        al_str_c("pixiv_i_49089079_media2.png"),
+        al_str_c("pixiv_i_49089079_media3.png"),
+        al_str_c("pixiv_i_49089079_media4.png"),
+        al_str_c("pixiv_i_49089079_media5.png"),
+        al_str_c("pixiv_i_49089079_media6.png"),
+        al_str_c("pixiv_i_49089079_media7.png"),
+        al_str_c("pixiv_i_49089079_media8.png"),
+        al_str_c("pixiv_i_49089079_media9.png"),
+        al_str_c("pixiv_i_49089079_media10.png"),
+        al_str_c("pixiv_i_49089079_media11.png"),
+        al_str_c("pixiv_i_49089079_media12.png"),
+        al_str_c("pixiv_i_49089079_media13.png"),
+        al_str_c("pixiv_i_49089079_media14.png"),
+        al_str_c("pixiv_i_49089079_media15.png"),
+        al_str_c("pixiv_i_49089079_media16.png"),
+        al_str_c("pixiv_i_49089079_media17.png"),
+        al_str_c("pixiv_i_49089079_media18.png"),
+        al_str_c("pixiv_i_49089079_media19.png"),
+        al_str_c("pixiv_i_49089079_media20.png"),
+        al_str_c("pixiv_i_49089079_media21.png"),
+        al_str_c("pixiv_i_114990114_media0.png")
+    };
+    for (u32 i = 0; i < ARRAY_SIZE(files5); i++) {
+        al_array_push(strings, files5[i]);
+    }
+    SHUFFLE_ARRAY(strings);
+
+    al_array_sort(strings, str, nn_numerical_compare);
+
+    for (u32 i = 0; i < strings.count; i++) {
+        AL_TEST_TRUE(al_str_eq(&al_array_at(strings, i), &files5[i]));
+    }
+
+    al_array_free(strings);
+
+    AL_TEST_END();
+}
+
+s32 main(void)
+{
+    if (!nn_common_init(NULL)) return EXIT_FAILURE;
+
+    AL_TEST_START_GROUP("units");
+
+    AL_TEST_RUN(sort_test_numerical_compare);
+
+    AL_TEST_END_GROUP();
+
+    return EXIT_SUCCESS;
+}