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

changeset 752:c1f6efbb8580

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
farray.sh: Implement a variant of the exact binary search: "leftmost search" in "farray_binsearch_leftmost()"
author Franz Glasner <fzglas.hg@dom66.de>
date Thu, 10 Oct 2024 16:43:52 +0200
parents 4101e755b3e7
children d75979fdf67d
files share/local-bsdtools/farray.sh tests/farray-array.t
diffstat 2 files changed, 283 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/share/local-bsdtools/farray.sh	Thu Oct 10 14:04:16 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Thu Oct 10 16:43:52 2024 +0200
@@ -1471,7 +1471,7 @@
 #:
 farray_binsearch() {
     local __farr_varname __farr_name __farr_searched_value
-    local __farr_start __farr_end    
+    local __farr_start __farr_end
 
     local __farr_token __farr_gvrname __farr_len
     local __farr_lo __farr_hi __farr_mid __farr_mid_value
@@ -1481,7 +1481,7 @@
     shift
 
     _farr_array_get_meta "$@"
-    
+
     __farr_searched_value="${2+SET}"
     [ -z "${__farr_searched_value}" ] && _farr_fatal "no search value given"
     __farr_searched_value="$2"
@@ -1501,7 +1501,7 @@
         __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))            
+            __farr_hi=$((__farr_mid - 1))
         elif [ "${__farr_searched_value}" '>' "${__farr_mid_value}" ]; then
             __farr_lo=$((__farr_mid + 1))
         else
@@ -1515,6 +1515,58 @@
 
 
 #:
+#: Try to find the index of a given value in an existing array.
+#:
+#: It assumes that the array is sorted and uses an approximate binary search
+#: algorithm: it finds the leftmost match:
+#:
+#:    On duplicate keys it is the left mode one that is found.
+#:    On missing keys it is the index position at which the given key
+#:    would need to be inserted.
+#:
+#: Comparisons are lexicographic.
+#:
+#: 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
+#:
+#: Returns:
+#:   int: 0
+#:
+farray_binsearch_leftmost() {
+    local __farr_varname __farr_name __farr_searched_value
+
+    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_lo=1
+    __farr_hi=$((__farr_len + 1))
+    while [ "${__farr_lo}" -lt "${__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_lo=$((__farr_mid + 1))
+        else
+            __farr_hi=${__farr_mid}
+        fi
+    done
+    eval eval "${__farr_varname}"=${__farr_lo}
+    return 0
+}
+
+
+#:
 #: Join all the elements in given array with a separator and put the result
 #: into a variable.
 #:
--- a/tests/farray-array.t	Thu Oct 10 14:04:16 2024 +0200
+++ b/tests/farray-array.t	Thu Oct 10 16:43:52 2024 +0200
@@ -1467,6 +1467,234 @@
   $ check_no_array_artifacts
 
 
+Binary Search Leftmost
+======================
+
+  $ farray_create TEST
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 5
+  $ echo ${_var}
+  3
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 5
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 7
+  $ echo ${_var}
+  4
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 5
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 7
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 9
+  $ echo ${_var}
+  5
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8 88
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 5
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 7
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 87
+  $ echo ${_var}
+  5
+  $ farray_binsearch_leftmost _var TEST 88
+  $ echo ${_var}
+  5
+  $ farray_binsearch_leftmost _var TEST 888
+  $ echo ${_var}
+  6
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8 88 8888
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 5
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 7
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 87
+  $ echo ${_var}
+  5
+  $ farray_binsearch_leftmost _var TEST 88
+  $ echo ${_var}
+  5
+  $ farray_binsearch_leftmost _var TEST 888
+  $ echo ${_var}
+  6
+  $ farray_binsearch_leftmost _var TEST 8888
+  $ echo ${_var}
+  6
+  $ farray_binsearch_leftmost _var TEST 88888
+  $ echo ${_var}
+  7
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+  $ farray_create TEST 2 4 6 8 88 8888 9
+  $ farray_binsearch_leftmost _var TEST 1
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 2
+  $ echo ${_var}
+  1
+  $ farray_binsearch_leftmost _var TEST 3
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 4
+  $ echo ${_var}
+  2
+  $ farray_binsearch_leftmost _var TEST 5
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 6
+  $ echo ${_var}
+  3
+  $ farray_binsearch_leftmost _var TEST 7
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 8
+  $ echo ${_var}
+  4
+  $ farray_binsearch_leftmost _var TEST 87
+  $ echo ${_var}
+  5
+  $ farray_binsearch_leftmost _var TEST 88
+  $ echo ${_var}
+  5
+  $ farray_binsearch_leftmost _var TEST 888
+  $ echo ${_var}
+  6
+  $ farray_binsearch_leftmost _var TEST 8888
+  $ echo ${_var}
+  6
+  $ farray_binsearch_leftmost _var TEST 88888
+  $ echo ${_var}
+  7
+  $ farray_binsearch_leftmost _var TEST 9
+  $ echo ${_var}
+  7
+  $ farray_binsearch_leftmost _var TEST 99
+  $ echo ${_var}
+  8
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+
 Generic Destruction
 ===================