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

changeset 749:e8eb5e7ceb37

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
farray.sh: Implement binary lexicographical search in "farray_binsearch()". While there disable SC3012 in shellcheck because FreeBSD's /bin/sh supports lexicographical comparisons in "test".
author Franz Glasner <fzglas.hg@dom66.de>
date Thu, 10 Oct 2024 13:27:50 +0200
parents 32580e25df78
children 464fc11180a0
files .shellcheckrc share/local-bsdtools/farray.sh tests/farray-array.t
diffstat 3 files changed, 260 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/.shellcheckrc	Wed Oct 09 22:56:11 2024 +0200
+++ b/.shellcheckrc	Thu Oct 10 13:27:50 2024 +0200
@@ -21,6 +21,8 @@
 disable=SC2166
 # In POSIX sh, $'..' is undefined
 disable=SC3003
+# In POSIX sh, lexicographical \< is undefined.
+disable=SC3012
 # In POSIX sh, local is undefined
 disable=SC3043
 
--- a/share/local-bsdtools/farray.sh	Wed Oct 09 22:56:11 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Thu Oct 10 13:27:50 2024 +0200
@@ -1183,7 +1183,6 @@
         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))
@@ -1436,7 +1435,6 @@
         else
             eval __farr_val=\"\$\{${__farr_gvrname}_${__farr_pos}\}\"
             eval __farr_val_1=\"\$\{${__farr_gvrname}_$((__farr_pos - 1))\}\"
-            # shellcheck disable=SC3012  # POSIX sh: lexicographical > undef
             if [ \( "${__farr_val}" '>' "${__farr_val_1}" \) -o \( "${__farr_val}" '=' "${__farr_val_1}" \) ] ; then
                 __farr_pos=$((__farr_pos + 1))
             else
@@ -1451,6 +1449,72 @@
 
 
 #:
+#: Try to find the index of a given value in an existing array.
+#:
+#: It assumes that the array is sorted and uses a binary search algorithm
+#: and uses lexicographical comparisons.
+#:
+#: Args:
+#:   $1 (str): The name of a variable where to put the found index into
+#:   $2 (str): The name of an existing array
+#:   $3: The value to search for
+#:   $4 (int, nuĺl, optional): The start index to search for (inclusive).
+#:                             If not given or `null` then `1` is used.
+#:   $5 (int, null, optional):  The index to stop (inclusive).
+#:                              If not given or `null` then the length of
+#:                              `$2` is used.
+#:
+#: Returns:
+#:   - 0 (truish) if the argument value is found within the given array
+#:     and index constraints
+#:   - 1 (falsy) otherwise
+#:
+farray_binsearch() {
+    local __farr_varname __farr_name __farr_searched_value
+    local __farr_start __farr_end    
+
+    local __farr_token __farr_gvrname __farr_len
+    local __farr_lo __farr_hi __farr_mid __farr_mid_value
+
+    __farr_varname="${1-}"
+    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
+    shift
+
+    _farr_array_get_meta "$@"
+    
+    __farr_searched_value="${2+SET}"
+    [ -z "${__farr_searched_value}" ] && _farr_fatal "no search value given"
+    __farr_searched_value="$2"
+
+    __farr_start="${3-}"
+    [ -z "${__farr_start}" ] && __farr_start=1
+    _farr_make_index __farr_start "${__farr_start}" "${__farr_len}"
+    [ ${__farr_start} -lt 1 ] && _farr_fatal "start index must be >= 1"
+    __farr_end="${4-}"
+    [ -z "${__farr_end}" ] && __farr_end="${__farr_len}"
+    _farr_make_index __farr_end "${__farr_end}" "${__farr_len}"
+    [ ${__farr_end} -lt 1 ] && [ ${__farr_len} -gt 0 ] && _farr_fatal "end index must be >= 1"
+    [ ${__farr_end} -gt "${__farr_len}" ] && _farr_fatal "end index exceeds array length"
+    __farr_lo="${__farr_start}"
+    __farr_hi="${__farr_end}"
+    while [ "${__farr_lo}" -le "${__farr_hi}" ]; do
+        __farr_mid=$((__farr_lo + ((__farr_hi-__farr_lo)/2) ))
+        eval __farr_mid_value=\"\$\{${__farr_gvrname}_${__farr_mid}\}\"
+        if [ "${__farr_searched_value}" '<' "${__farr_mid_value}" ]; then
+            __farr_hi=$((__farr_mid - 1))            
+        elif [ "${__farr_searched_value}" '>' "${__farr_mid_value}" ]; then
+            __farr_lo=$((__farr_mid + 1))
+        else
+            # found
+            eval eval "${__farr_varname}"=${__farr_mid}
+            return 0
+        fi
+    done
+    return 1    # not found
+}
+
+
+#:
 #: Join all the elements in given array with a separator and put the result
 #: into a variable.
 #:
@@ -2414,7 +2478,6 @@
         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
--- a/tests/farray-array.t	Wed Oct 09 22:56:11 2024 +0200
+++ b/tests/farray-array.t	Thu Oct 10 13:27:50 2024 +0200
@@ -1266,6 +1266,198 @@
   $ check_no_array_artifacts
 
 
+Binary Search
+=============
+
+  $ farray_create TEST
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_binsearch _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch _var TEST 5
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_binsearch _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch _var TEST 5
+  [1]
+  $ farray_binsearch _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch _var TEST 7
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_binsearch _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch _var TEST 5
+  [1]
+  $ farray_binsearch _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch _var TEST 7
+  [1]
+  $ farray_binsearch _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch _var TEST 9
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8 88
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_binsearch _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch _var TEST 5
+  [1]
+  $ farray_binsearch _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch _var TEST 7
+  [1]
+  $ farray_binsearch _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch _var TEST 87
+  [1]
+  $ farray_binsearch _var TEST 88
+  $ echo ${_var}
+  5
+  $ farray_binsearch _var TEST 888
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8 88 8888
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_binsearch _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch _var TEST 5
+  [1]
+  $ farray_binsearch _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch _var TEST 7
+  [1]
+  $ farray_binsearch _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch _var TEST 87
+  [1]
+  $ farray_binsearch _var TEST 88
+  $ echo ${_var}
+  5
+  $ farray_binsearch _var TEST 888
+  [1]
+  $ farray_binsearch _var TEST 8888
+  $ echo ${_var}
+  6
+  $ farray_binsearch _var TEST 88888
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8 88 8888 9
+  $ farray_binsearch _var TEST 1
+  [1]
+  $ farray_binsearch _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch _var TEST 3
+  [1]
+  $ farray_binsearch _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch _var TEST 5
+  [1]
+  $ farray_binsearch _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch _var TEST 7
+  [1]
+  $ farray_binsearch _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch _var TEST 87
+  [1]
+  $ farray_binsearch _var TEST 88
+  $ echo ${_var}
+  5
+  $ farray_binsearch _var TEST 888
+  [1]
+  $ farray_binsearch _var TEST 8888
+  $ echo ${_var}
+  6
+  $ farray_binsearch _var TEST 88888
+  [1]
+  $ farray_binsearch _var TEST 9
+  $ echo ${_var}
+  7
+  $ farray_binsearch _var TEST 99
+  [1]
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+
 Generic Destruction
 ===================