Mercurial > hgrepos > FreeBSD > ports > sysutils > local-bsdtools

changeset 740:bcfd8383a918

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
farray.sh: implement "farray_merge()" to merge two sorted arrays
author Franz Glasner <fzglas.hg@dom66.de>
date Tue, 08 Oct 2024 09:04:42 +0200
parents dae85cddc47b
children 446c175cfb48
files share/local-bsdtools/farray.sh tests/farray-array.t
diffstat 2 files changed, 188 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/share/local-bsdtools/farray.sh	Mon Oct 07 23:39:01 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Tue Oct 08 09:04:42 2024 +0200
@@ -1138,6 +1138,79 @@
 
 
 #:
+#: Merge two *sorted* arrays using the mergesort algorithm.
+#:
+#: Sources: - https://de.wikipedia.org/wiki/Mergesort
+#:          - https://en.wikipedia.org/wiki/Merge_sort
+#:
+#: Args:
+#:   $1 (str): The result array where all the sorted items will be appended to
+#:   $2 (str): The first sorted input array
+#:   $3 (str): The second sorted input array
+#:
+farray_merge() {
+    local __farr_result __farr_input_1 __farr_input_2
+
+    local __farr_name __farr_token __farr_gvrname __farr_len
+    local __farr_name_1 __farr_token_1 __farr_gvrname_1 __farr_len_1
+    local __farr_name_2 __farr_token_2 __farr_gvrname_2 __farr_len_2
+    local __farr_idx_1 __farr_idx_2 __farr_item_1 __farr_item_2
+
+    _farr_array_get_meta "$2"
+    __farr_input_1="$2"
+    __farr_name_1="${__farr_name}"
+    __farr_token_1="${__farr_token}"
+    __farr_gvrname_1="${__farr_gvrname}"
+    __farr_len_1="${__farr_len}"
+    _farr_array_get_meta "$3"
+    __farr_input_2="$3"    
+    __farr_name_2="${__farr_name}"
+    __farr_token_2="${__farr_token}"
+    __farr_gvrname_2="${__farr_gvrname}"
+    __farr_len_2="${__farr_len}"
+    _farr_array_get_meta "$1"
+    __farr_result="$1"    
+
+    __farr_idx_1=1
+    if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
+        eval __farr_item_1=\"\$\{${__farr_gvrname_1}_${__farr_idx_1}\}\"
+    fi
+    __farr_idx_2=1
+    if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
+        eval __farr_item_2=\"\$\{${__farr_gvrname_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_item_1}" '<' "${__farr_item_2}" \) -o \( "${__farr_item_1}" '=' "${__farr_item_2}" \) ] ; then
+            farray_append "${__farr_result}" "${__farr_item_1}"
+            __farr_idx_1=$((__farr_idx_1 + 1))
+            if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
+                eval __farr_item_1=\"\$\{${__farr_gvrname_1}_${__farr_idx_1}\}\"
+            fi
+        else
+            farray_append "${__farr_result}" "${__farr_item_2}"
+            __farr_idx_2=$((__farr_idx_2 + 1))
+            if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
+                eval __farr_item_2=\"\$\{${__farr_gvrname_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_item_1=\"\$\{${__farr_gvrname_1}_${__farr_idx_1}\}\"
+        farray_append "${__farr_result}" "${__farr_item_1}"
+        __farr_idx_1=$((__farr_idx_1 + 1))
+    done
+    while [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; do
+        eval __farr_item_2=\"\$\{${__farr_gvrname_2}_${__farr_idx_2}\}\"
+        farray_append "${__farr_result}" "${__farr_item_2}"
+        __farr_idx_2=$((__farr_idx_2 + 1))
+    done
+    return 0
+}
+
+
+#:
 #: Empty an existing array.
 #:
 #: Args:
--- a/tests/farray-array.t	Mon Oct 07 23:39:01 2024 +0200
+++ b/tests/farray-array.t	Tue Oct 08 09:04:42 2024 +0200
@@ -1135,6 +1135,121 @@
   $ check_no_array_artifacts
 
 
+Merge
+=====
+
+  $ farray_create MERGED
+  $ farray_create INPUT1 s1 s2 s3
+  $ farray_create INPUT2
+  $ farray_merge MERGED INPUT1 INPUT2
+  $ farray_release INPUT1
+  $ farray_release INPUT2
+  $ farray_debug MERGED
+  DEBUG: array `MERGED' has length 3
+  DEBUG:   the items:
+  DEBUG:     1: `s1'
+  DEBUG:     2: `s2'
+  DEBUG:     3: `s3'
+  $ farray_release MERGED
+  $ check_no_array_artifacts
+
+  $ farray_create MERGED
+  $ farray_create INPUT1
+  $ farray_create INPUT2 S1 S2 S3 S4
+  $ farray_merge MERGED INPUT1 INPUT2
+  $ farray_release INPUT1
+  $ farray_release INPUT2
+  $ farray_debug MERGED
+  DEBUG: array `MERGED' has length 4
+  DEBUG:   the items:
+  DEBUG:     1: `S1'
+  DEBUG:     2: `S2'
+  DEBUG:     3: `S3'
+  DEBUG:     4: `S4'
+  $ farray_release MERGED
+  $ check_no_array_artifacts
+
+  $ farray_create MERGED
+  $ farray_create INPUT1 s1 s2 s3 s4
+  $ farray_create INPUT2 S1 S2 S3 S4
+  $ farray_merge MERGED INPUT1 INPUT2
+  $ farray_release INPUT1
+  $ farray_release INPUT2
+  $ farray_debug MERGED
+  DEBUG: array `MERGED' has length 8
+  DEBUG:   the items:
+  DEBUG:     1: `S1'
+  DEBUG:     2: `S2'
+  DEBUG:     3: `S3'
+  DEBUG:     4: `S4'
+  DEBUG:     5: `s1'
+  DEBUG:     6: `s2'
+  DEBUG:     7: `s3'
+  DEBUG:     8: `s4'
+  $ farray_release MERGED
+  $ check_no_array_artifacts
+
+  $ farray_create MERGED
+  $ farray_create INPUT1 s1 s2 s3 s4
+  $ farray_create INPUT2 S1 S2 S3 S4
+  $ farray_merge MERGED INPUT2 INPUT1
+  $ farray_release INPUT1
+  $ farray_release INPUT2
+  $ farray_debug MERGED
+  DEBUG: array `MERGED' has length 8
+  DEBUG:   the items:
+  DEBUG:     1: `S1'
+  DEBUG:     2: `S2'
+  DEBUG:     3: `S3'
+  DEBUG:     4: `S4'
+  DEBUG:     5: `s1'
+  DEBUG:     6: `s2'
+  DEBUG:     7: `s3'
+  DEBUG:     8: `s4'
+  $ farray_release MERGED
+  $ check_no_array_artifacts
+
+  $ farray_create MERGED
+  $ farray_create INPUT1 S1 S2 S3 S4
+  $ farray_create INPUT2 s1 s2 s3 s4
+  $ farray_merge "$MERGED" "$INPUT1" "$INPUT2"
+  $ farray_release INPUT1
+  $ farray_release INPUT2
+  $ farray_debug MERGED
+  DEBUG: array `MERGED' has length 8
+  DEBUG:   the items:
+  DEBUG:     1: `S1'
+  DEBUG:     2: `S2'
+  DEBUG:     3: `S3'
+  DEBUG:     4: `S4'
+  DEBUG:     5: `s1'
+  DEBUG:     6: `s2'
+  DEBUG:     7: `s3'
+  DEBUG:     8: `s4'
+  $ farray_release MERGED
+  $ check_no_array_artifacts
+
+  $ farray_create MERGED
+  $ farray_create INPUT1 S1 S2 S3 S4
+  $ farray_create INPUT2 s1 s2 s3 s4
+  $ farray_merge "$MERGED" "$INPUT2" "$INPUT1"
+  $ farray_release INPUT1
+  $ farray_release INPUT2
+  $ farray_debug MERGED
+  DEBUG: array `MERGED' has length 8
+  DEBUG:   the items:
+  DEBUG:     1: `S1'
+  DEBUG:     2: `S2'
+  DEBUG:     3: `S3'
+  DEBUG:     4: `S4'
+  DEBUG:     5: `s1'
+  DEBUG:     6: `s2'
+  DEBUG:     7: `s3'
+  DEBUG:     8: `s4'
+  $ farray_release MERGED
+  $ check_no_array_artifacts
+
+
 Generic Destruction
 ===================