# HG changeset patch
# User Franz Glasner <fzglas.hg@dom66.de>
# Date 1728395550 -7200
# Node ID 6fcf7da879810ab87fe3a39259dd98a732547df1
# Parent  5ba94d373199640880c6ac14b9200f3059bd7388
farray.sh: implement "falist_merge()" to merge two "sorted" alists and add the result to a resulting alist

diff -r 5ba94d373199 -r 6fcf7da87981 share/local-bsdtools/farray.sh
--- a/share/local-bsdtools/farray.sh	Tue Oct 08 09:52:29 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Tue Oct 08 15:52:30 2024 +0200
@@ -2322,6 +2322,94 @@
 
 
 #:
+#: Merge two *sorted* alists using the mergesort algorithm.
+#:
+#: A "sorted" alist is an alist where all the key-value pairs are added
+#: in a sorted fashion: `falist_keys()` yields a lexicographcally sorted
+#: array.
+#:
+#: Sources: - https://de.wikipedia.org/wiki/Mergesort
+#:          - https://en.wikipedia.org/wiki/Merge_sort
+#:
+#: Args:
+#:   $1 (str): The result alist where all the sorted items will be added to
+#:             using `falist_add`
+#:   $2 (str): The first sorted input alist
+#:   $3 (str): The second sorted input alist
+#:
+falist_merge() {
+    local __farr_result __farr_input_1 __farr_input_2
+
+    local __farr_name __farr_token __farr_objname __farr_valname __farr_keyname __farr_len
+    local __farr_name_1 __farr_token_1 __farr_objname_1 __farr_valname_1 __farr_keyname_1 __farr_len_1
+    local __farr_name_2 __farr_token_2 __farr_objname_2 __farr_valname_2 __farr_keyname_2 __farr_len_2
+    local __farr_idx_1 __farr_key_1 __farr_val_2
+    local __farr_idx_2 __farr_key_2 __farr_val_2
+
+    _farr_alist_get_meta "$2"
+    __farr_input_1="$2"
+    __farr_name_1="${__farr_name}"
+    __farr_token_1="${__farr_token}"
+    __farr_objname_1="${__farr_objname}"
+    __farr_keyname_1="${__farr_keyname}"
+    __farr_valname_1="${__farr_valname}"
+    __farr_len_1="${__farr_len}"
+    _farr_alist_get_meta "$3"
+    __farr_input_2="$3"
+    __farr_name_2="${__farr_name}"
+    __farr_token_2="${__farr_token}"
+    __farr_objname_2="${__farr_objname}"
+    __farr_keyname_2="${__farr_keyname}"
+    __farr_valname_2="${__farr_valname}"
+    __farr_len_2="${__farr_len}"
+    _farr_alist_get_meta "$1"
+    __farr_result="$1"
+
+    __farr_idx_1=1
+    if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
+        eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\"
+    fi
+    __farr_idx_2=1
+    if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
+        eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\"
+    fi
+    while [ \( "${__farr_idx_1}" -le "${__farr_len_1}" \) -a \( "${__farr_idx_2}" -le "${__farr_len_2}" \) ]; do
+        # shellcheck disable=SC3012 # lexicographical '<' is undefined in POSIX
+        if [ \( "${__farr_key_1}" '<' "${__farr_key_2}" \) -o \( "${__farr_key_1}" '=' "${__farr_key_2}" \) ] ; then
+            eval __farr_val_1=\"\$\{${__farr_valname_1}_${__farr_idx_1}\}\"
+            # shellcheck disable=SC2154  # bogus __farr_val_1 is ref but not set
+            falist_add "${__farr_result}" "${__farr_key_1}" "${__farr_val_1}"
+            __farr_idx_1=$((__farr_idx_1 + 1))
+            if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
+                eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\"
+            fi
+        else
+            eval __farr_val_2=\"\$\{${__farr_valname_2}_${__farr_idx_2}\}\"
+            falist_add "${__farr_result}" "${__farr_key_2}" "${__farr_val_2}"
+            __farr_idx_2=$((__farr_idx_2 + 1))
+            if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
+                eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\"
+            fi
+        fi
+    done
+    # Only one of the two while-loops below will be entered
+    while [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; do
+        eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\"
+        eval __farr_val_1=\"\$\{${__farr_valname_1}_${__farr_idx_1}\}\"
+        falist_add "${__farr_result}" "${__farr_key_1}" "${__farr_val_1}"
+        __farr_idx_1=$((__farr_idx_1 + 1))
+    done
+    while [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; do
+        eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\"
+        eval __farr_val_2=\"\$\{${__farr_valname_2}_${__farr_idx_2}\}\"
+        falist_add "${__farr_result}" "${__farr_key_2}" "${__farr_val_2}"
+        __farr_idx_2=$((__farr_idx_2 + 1))
+    done
+    return 0
+}
+
+
+#:
 #: Get the value that is associated with a key and put it into a variable.
 #:
 #: Args:
diff -r 5ba94d373199 -r 6fcf7da87981 tests/farray-alist.t
--- a/tests/farray-alist.t	Tue Oct 08 09:52:29 2024 +0200
+++ b/tests/farray-alist.t	Tue Oct 08 15:52:30 2024 +0200
@@ -381,6 +381,116 @@
   $ check_no_alist_artifacts
 
 
+Merging
+=======
+
+  $ falist_create RES
+  $ falist_create INPUT1 "K1" "V1" "K2" "V2" "K3" "V3"
+  $ falist_create INPUT2
+  $ falist_merge "$RES" "$INPUT1" "$INPUT2"
+  $ falist_release INPUT1
+  $ falist_release INPUT2
+  $ falist_debug RES
+  DEBUG: alist `RES' has length 3
+  DEBUG:   the items:
+  DEBUG:     `K1' -> `V1'
+  DEBUG:     `K2' -> `V2'
+  DEBUG:     `K3' -> `V3'
+  $ falist_release RES
+  $ check_no_alist_artifacts
+
+  $ falist_create RES
+  $ falist_create INPUT1
+  $ falist_create INPUT2 "k1" "v1" "k2" "v2" "k3" "v3"
+  $ falist_merge "$RES" "$INPUT1" "$INPUT2"
+  $ falist_release INPUT1
+  $ falist_release INPUT2
+  $ falist_debug RES
+  DEBUG: alist `RES' has length 3
+  DEBUG:   the items:
+  DEBUG:     `k1' -> `v1'
+  DEBUG:     `k2' -> `v2'
+  DEBUG:     `k3' -> `v3'
+  $ falist_release RES
+  $ check_no_alist_artifacts
+
+  $ falist_create RES
+  $ falist_create INPUT1 "K1" "V1" "K2" "V2" "K3" "V3"
+  $ falist_create INPUT2 "k1" "v1" "k2" "v2" "k3" "v3" "k4" "v4"
+  $ falist_merge "$RES" "$INPUT1" "$INPUT2"
+  $ falist_release INPUT1
+  $ falist_release INPUT2
+  $ falist_debug RES
+  DEBUG: alist `RES' has length 7
+  DEBUG:   the items:
+  DEBUG:     `K1' -> `V1'
+  DEBUG:     `K2' -> `V2'
+  DEBUG:     `K3' -> `V3'
+  DEBUG:     `k1' -> `v1'
+  DEBUG:     `k2' -> `v2'
+  DEBUG:     `k3' -> `v3'
+  DEBUG:     `k4' -> `v4'
+  $ falist_release RES
+  $ check_no_alist_artifacts
+
+  $ falist_create RES
+  $ falist_create INPUT1 "k1" "v1" "k2" "v2" "k3" "v3" "k4" "v4"
+  $ falist_create INPUT2 "K1" "V1" "K2" "V2" "K3" "V3"
+  $ falist_merge "$RES" "$INPUT1" "$INPUT2"
+  $ falist_release INPUT1
+  $ falist_release INPUT2
+  $ falist_debug RES
+  DEBUG: alist `RES' has length 7
+  DEBUG:   the items:
+  DEBUG:     `K1' -> `V1'
+  DEBUG:     `K2' -> `V2'
+  DEBUG:     `K3' -> `V3'
+  DEBUG:     `k1' -> `v1'
+  DEBUG:     `k2' -> `v2'
+  DEBUG:     `k3' -> `v3'
+  DEBUG:     `k4' -> `v4'
+  $ falist_release RES
+  $ check_no_alist_artifacts
+
+  $ falist_create RES
+  $ falist_create INPUT1 "K1" "V1" "K3" "V3" "k1" "v1" "k4" "v4"
+  $ falist_create INPUT2 "K2" "V2" "k2" "v2" "k3" "v3"
+  $ falist_merge "$RES" "$INPUT1" "$INPUT2"
+  $ falist_release INPUT1
+  $ falist_release INPUT2
+  $ falist_debug RES
+  DEBUG: alist `RES' has length 7
+  DEBUG:   the items:
+  DEBUG:     `K1' -> `V1'
+  DEBUG:     `K2' -> `V2'
+  DEBUG:     `K3' -> `V3'
+  DEBUG:     `k1' -> `v1'
+  DEBUG:     `k2' -> `v2'
+  DEBUG:     `k3' -> `v3'
+  DEBUG:     `k4' -> `v4'
+  $ falist_release RES
+  $ check_no_alist_artifacts
+
+  $ falist_create RES
+  $ falist_create INPUT1 "K1" "V1" "K3" "V3" "k1" "v1" "k4" "v4"
+  $ falist_create INPUT2 "K2" "V2" "k2" "v2" "k3" "v3"
+  $ falist_merge "$RES" INPUT2 INPUT1
+  $ falist_release INPUT1
+  $ falist_release INPUT2
+  $ falist_debug RES
+  DEBUG: alist `RES' has length 7
+  DEBUG:   the items:
+  DEBUG:     `K1' -> `V1'
+  DEBUG:     `K2' -> `V2'
+  DEBUG:     `K3' -> `V3'
+  DEBUG:     `k1' -> `v1'
+  DEBUG:     `k2' -> `v2'
+  DEBUG:     `k3' -> `v3'
+  DEBUG:     `k4' -> `v4'
+  $ falist_release RES
+  $ check_no_alist_artifacts
+
+
 Items / Keys / Values
 =====================