# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1763900119 -3600
# Node ID dfc0ddd9571e5447689f202b681ef46178cb5ed0
# Parent  f4010cda9a2a19f2947a198855967ef7d7594001
optimize sorted insertion by using the infimum instead of the supremum

The reason is that the supremum returns the equal element with the smallest index, and we want the largest.
Therefore, we use the infimum, which already gives us the largest index when there are equal elements, and increase the index by one. The infimum is also guaranteed to exist in that case.

diff -r f4010cda9a2a -r dfc0ddd9571e src/array_list.c
--- a/src/array_list.c	Sun Nov 23 12:19:24 2025 +0100
+++ b/src/array_list.c	Sun Nov 23 13:15:19 2025 +0100
@@ -417,21 +417,23 @@
     // while there are both source and buffered elements left,
     // copy them interleaving
     while (si < elem_count && bi < new_size) {
-        // determine how many source elements can be inserted
+        // determine how many source elements can be inserted.
+        // the first element that shall not be inserted is the smallest element
+        // that is strictly larger than the first buffered element
+        // (located at the index of the infimum plus one).
+        // the infimum is guaranteed to exist:
+        // - if all src elements are larger,
+        //   there is no buffer, and this loop is skipped
+        // - if any src element is smaller or equal, the infimum exists
+        // - when all src elements that are smaller are copied, the second part
+        //   of this loop body will copy the remaining buffer (emptying it)
+        // Therefore, the buffer can never contain an element that is smaller
+        // than any element in the source and the infimum exists.
         size_t copy_len, bytes_copied;
-        copy_len = cx_array_binary_search_sup(
-                src,
-                elem_count - si,
-                elem_size,
-                bptr,
-                cmp_func
+        copy_len = cx_array_binary_search_inf(
+            src, elem_count - si, elem_size, bptr, cmp_func
         );
-        // binary search gives us the smallest index;
-        // we also want to include equal elements here
-        while (si + copy_len < elem_count
-                && cmp_func(bptr, src+copy_len*elem_size) == 0) {
-            copy_len++;
-        }
+        copy_len++;
 
         // copy the source elements
         if (copy_len > 0) {
diff -r f4010cda9a2a -r dfc0ddd9571e tests/test_list.c
--- a/tests/test_list.c	Sun Nov 23 12:19:24 2025 +0100
+++ b/tests/test_list.c	Sun Nov 23 13:15:19 2025 +0100
@@ -315,9 +315,11 @@
     int d8 = 90;
     int d9 = 56;
     int d10a[3] = {67, 75, 90};
-    int expected[22] = {
-            40, 50, 51, 52, 54, 56, 56, 57, 58, 60,
-            62, 64, 65, 67, 70, 75, 75, 77, 78, 80, 90, 90
+    int d11a[6] = {58, 59, 71, 71, 72, 75};
+    int d12a[3] = {10, 120, 130};
+    int expected[31] = {
+            10, 40, 50, 51, 52, 54, 56, 56, 57, 58, 58, 59, 60, 62, 64, 65, 67,
+            70, 71, 71, 72, 75, 75, 75, 77, 78, 80, 90, 90, 120, 130
     };
 
     CX_ARRAY_DECLARE(int, array);
@@ -354,8 +356,14 @@
         CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d10a, 3, cx_cmp_int));
         CX_TEST_ASSERT(array_size == 22);
         CX_TEST_ASSERT(array_capacity >= 22);
-
-        CX_TEST_ASSERT(0 == memcmp(array, expected, 22 * sizeof(int)));
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d11a, 6, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 28);
+        CX_TEST_ASSERT(array_capacity >= 28);
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d12a, 3, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 31);
+        CX_TEST_ASSERT(array_capacity >= 31);
+
+        CX_TEST_ASSERT(0 == memcmp(array, expected, 31 * sizeof(int)));
     }
     cxFreeDefault(array);
 }
@@ -371,9 +379,10 @@
     int d8 = 90;
     int d9 = 56;
     int d10a[3] = {67, 75, 90};
-    int expected[19] = {
-            40, 50, 51, 52, 54, 56, 57, 58, 60,
-            62, 64, 65, 67, 70, 75, 77, 78, 80, 90
+    int d11a[8] = {90, 90, 90, 95, 95, 100, 110, 110};
+    int expected[22] = {
+            40, 50, 51, 52, 54, 56, 57, 58, 60, 62, 64,
+            65, 67, 70, 75, 77, 78, 80, 90, 95, 100, 110
     };
 
     CX_ARRAY_DECLARE(int, array);
@@ -410,8 +419,11 @@
         CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d10a, 3, cx_cmp_int));
         CX_TEST_ASSERT(array_size == 19);
         CX_TEST_ASSERT(array_capacity >= 19);
-
-        CX_TEST_ASSERT(0 == memcmp(array, expected, 19 * sizeof(int)));
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d11a, 8, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 22);
+        CX_TEST_ASSERT(array_capacity >= 22);
+
+        CX_TEST_ASSERT(0 == memcmp(array, expected, 22 * sizeof(int)));
     }
     cxFreeDefault(array);
 }