# HG changeset patch
# User Franz Glasner <fzglas.hg@dom66.de>
# Date 1729975321 -7200
# Node ID b5b19c62da24454a5dcddc99f90317dd3846cf0c
# Parent  7d44112dfb817c91f065600d5f46968db909e2c8
fports: FIX: man page: Synopsis should document the "deptree" subcommand

diff -r 7d44112dfb81 -r b5b19c62da24 Makefile
--- a/Makefile	Sat Oct 26 18:38:05 2024 +0200
+++ b/Makefile	Sat Oct 26 22:42:01 2024 +0200
@@ -90,7 +90,7 @@
 	${SED} -i "" -e "s|@@SIMPLEVERSIONTAG@@|${SIMPLEVERSIONTAG}|" ${WRKSRC}/${_ef}
 .endfor
 	${MKDIR} ${WRKSRC}/share/${PORTNAME}
-.for _df in share/local-bsdtools/farray.sh share/local-bsdtools/common.subr share/local-bsdtools/ports.subr
+.for _df in share/local-bsdtools/farray.sh share/local-bsdtools/farray-ext.sh share/local-bsdtools/common.subr share/local-bsdtools/ports.subr
 	${CP} -v ${SRC}/${_df} ${WRKSRC}/${_df}
 	${SED} -i "" -e "s|@@SIMPLEVERSIONTAG@@|${SIMPLEVERSIONTAG}|" ${WRKSRC}/${_df}
 .endfor
@@ -126,7 +126,7 @@
 	${INSTALL_SCRIPT} ${WRKSRC}/etc/periodic/daily/${_ps} ${STAGEDIR}${PREFIX}/etc/periodic/daily
 .endfor
 	${MKDIR} ${STAGEDIR}${DATADIR}
-.for _df in farray.sh common.subr ports.subr
+.for _df in farray.sh farray-ext.sh common.subr ports.subr
 	${INSTALL_DATA} ${WRKSRC}/share/${PORTNAME}/${_df} ${STAGEDIR}${DATADIR}
 .endfor
 	${MKDIR} ${STAGEDIR}${EXAMPLESDIR}
diff -r 7d44112dfb81 -r b5b19c62da24 docs/man/man8/fports.rst
--- a/docs/man/man8/fports.rst	Sat Oct 26 18:38:05 2024 +0200
+++ b/docs/man/man8/fports.rst	Sat Oct 26 22:42:01 2024 +0200
@@ -13,7 +13,7 @@
 
 **fports -V**
 
-**fports subcommand**
+**fports deptree** [**-l** `maxlevel`] [**-r**] `package` ...
 
 
 Description
diff -r 7d44112dfb81 -r b5b19c62da24 pkg-plist
--- a/pkg-plist	Sat Oct 26 18:38:05 2024 +0200
+++ b/pkg-plist	Sat Oct 26 22:42:01 2024 +0200
@@ -11,6 +11,7 @@
 sbin/fzfs
 %%DATADIR%%/common.subr
 %%DATADIR%%/farray.sh
+%%DATADIR%%/farray-ext.sh
 %%DATADIR%%/ports.subr
 %%EXAMPLESDIR%%/freebsd-update-ftjail-template.sh
 %%EXAMPLESDIR%%/freebsd-update-ftjail.sh
diff -r 7d44112dfb81 -r b5b19c62da24 share/local-bsdtools/farray-ext.sh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/share/local-bsdtools/farray-ext.sh	Sat Oct 26 22:42:01 2024 +0200
@@ -0,0 +1,406 @@
+#!/bin/sh
+# -*- indent-tabs-mode: nil; -*-
+#:
+#: This is a collection of mainly unused sorting algorithms because they
+#: are not as good as though in :command:`/bin/sh`.
+#:
+#: When using these extensions the :file:`farray.sh` **must** be sourced in
+#: first also.
+#:
+#: Currently these are Gnome Sort and Heap Sort (standard and bottom-up).
+#:
+#: :Author:    Franz Glasner
+#: :Copyright: (c) 2024 Franz Glasner.
+#:             All rights reserved.
+#: :License:   BSD 3-Clause "New" or "Revised" License.
+#:             See LICENSE for details.
+#:             If you cannot find LICENSE see
+#:             <https://opensource.org/licenses/BSD-3-Clause>
+#: :ID:        @(#)@@SIMPLEVERSIONTAG@@
+#:
+
+
+type farray_create 1>/dev/null 2>/dev/null || { echo "ERROR: source \`farray.sh' first"; exit 70; }
+
+
+#:
+#: Sort an array using Gnome Sort.
+#:
+#: Args:
+#:   $1: The array to sort to
+#:
+#: See Also:
+#:   `_farr_array_gnomesort`
+#:
+farray_gnomesort() {
+    local __farr_name
+
+    local __farr_token __farr_gvrname __farr_len \
+          __farr_pos __farr_val __farr_val_1
+
+    _farr_array_get_meta "$@"
+
+    _farr_array_gnomesort
+}
+
+
+#:
+#: Internal sort implementation using Gnome Sort.
+#:
+#: Stable: yes
+#:
+#: This is a very simple stable sort (a variant of insertion sort).
+#:
+#: See: https://en.wikipedia.org/wiki/Gnome_sort
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_gnomesort() {
+
+    local __farr_name __farr_token __farr_gvrname __farr_len \
+          __farr_pos __farr_val __farr_val_1
+
+    __farr_pos=1
+    while [ "${__farr_pos}" -le "${__farr_len}" ]; do
+        if [ "${__farr_pos}" -eq 1 ]; then
+            __farr_pos=$((__farr_pos + 1))
+        else
+            eval __farr_val=\"\$\{"${__farr_gvrname}"_"${__farr_pos}"\}\"
+            eval __farr_val_1=\"\$\{"${__farr_gvrname}"_$((__farr_pos - 1))\}\"
+            if [ "${__farr_val}" '>' "${__farr_val_1}" ] || [ "${__farr_val}" '=' "${__farr_val_1}" ] ; then
+                __farr_pos=$((__farr_pos + 1))
+            else
+                # swap
+                setvar "${__farr_gvrname}_${__farr_pos}" "${__farr_val_1}"
+                setvar "${__farr_gvrname}_$((__farr_pos - 1))" "${__farr_val}"
+                __farr_pos=$((__farr_pos - 1))
+            fi
+        fi
+    done
+}
+
+
+#:
+#: Sort an array using Heapsort.
+#:
+#: Args:
+#:   $1: The array to sort to
+#:
+#: See Also:
+#:   `_farr_array_heapsort`
+#:
+#: Note:
+#:   The heap is an implicit data structure which takes no space beyond the
+#:   array of objects to be sorted; the array is interpreted as a complete
+#:   binary tree where each array element is a node and each node's parent
+#:   and child links are defined by simple arithmetic on the array indexes.
+#:
+#:   The computation of these indexes is as follows:
+#:
+#:   - For 0-based indexes::
+#:
+#:       iLeftChild(i)  = 2⋅i + 1
+#:       iRightChild(i) = 2⋅i + 2
+#:       iParent(i)     = floor((i−1) / 2)
+#:
+#:   -  For 1 based indexes (in shell expession syntax and semantics)::
+#:
+#:       iLeftChild(i)  = 2 * i
+#:       iRightChild(i) = 2 * i + 1
+#:       iParent(i)     = i / 2
+#:
+#:   Variables:
+#:
+#:     Two variables (here, `start` and `end`) keep track of the bounds of the
+#:     heap area. The portion of the array before `start` is unsorted, while
+#:     the portion beginning at `end` is sorted. Heap construction decreases
+#:     `start` until it is one, after which heap extraction decreases `end`
+#:     until it is 2 and the array is entirely sorted.
+#:
+farray_heapsort() {
+    local __farr_name
+
+    local __farr_token __farr_gvrname __farr_len \
+          __farr_pos __farr_val __farr_val_1
+
+    _farr_array_get_meta "$@"
+
+    _farr_array_heapsort
+}
+
+
+#:
+#: Internal sort implementation using Heapsort.
+#:
+#: Stable: no
+#:
+#: See: https://en.wikipedia.org/wiki/Heapsort
+#:
+#: Here the "standard" implementation is used.
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_heapsort() {
+
+    local __farr_name __farr_token __farr_gvrname __farr_len \
+          __farr_start __farr_end __farr_root __farr_child __farr_childp1 \
+          __farr_tmpitem __farr_rootitem __farr_childitem __farr_childp1item
+
+    __farr_start=$(( (__farr_len / 2) + 1))    # aka: iParent(of the last element)
+    __farr_end=$((__farr_len + 1))
+    while [ "${__farr_end}" -gt 2 ]; do
+#        echo  "== WHILE: START: $__farr_start,   END: $__farr_end"
+        if [ "${__farr_start}" -gt 1 ]; then
+#            echo "==== HEAP CONSTRUCTION"
+            # Heap construction
+            __farr_start=$((__farr_start - 1))
+        else
+#            echo "==== HEAP EXTRACTION"
+            # Heap extraction
+            __farr_end=$((__farr_end - 1))
+            # swap(a[end], a[1])
+            eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_1\}\"
+            eval "${__farr_gvrname}"_1=\"\$\{"${__farr_gvrname}"_"${__farr_end}"\}\"
+            setvar "${__farr_gvrname}"_"${__farr_end}" "${__farr_tmpitem}"
+        fi
+#        echo "==== BEFORE: START: $__farr_start,   END: $__farr_end"
+        #farray_debug "$__farr_name"
+        # The following is siftDown(a, start, end)
+        __farr_root="${__farr_start}"
+        eval __farr_rootitem=\"\$\{"${__farr_gvrname}"_"${__farr_root}"\}\"
+#        echo "==== NEW ROOT: ${__farr_root},   a[root]: ${__farr_rootitem}"
+        while [ $((2 * __farr_root)) -lt "${__farr_end}" ]; do
+            __farr_child=$((2 * __farr_root))
+            eval __farr_childitem=\"\$\{"${__farr_gvrname}"_"${__farr_child}"\}\"
+#            echo "CHILD: ${__farr_child},   ROOT: ${__farr_root},   END: ${__farr_end},   a[child]: ${__farr_childitem}"
+            # If there is a right child and that child is greater
+            __farr_childp1=$((__farr_child + 1))
+            if [ "${__farr_childp1}" -lt "${__farr_end}" ]; then
+                eval __farr_childp1item=\"\$\{"${__farr_gvrname}"_"${__farr_childp1}"\}\"
+#                echo "===== a[child+1]: ${__farr_childp1item}"
+                if [ "${__farr_childitem}" '<' "${__farr_childp1item}" ]; then
+                    #child=$((child + 1))
+                    __farr_child="${__farr_childp1}"
+                    eval __farr_childitem=\"\$\{"${__farr_gvrname}"_"${__farr_child}"\}\"
+#                    echo "====== INCR CHILD TO: $__farr_child"
+                fi
+            fi
+#            echo "====== a[root]: ${__farr_rootitem},   a[child]: ${__farr_childitem}"
+            if [ "${__farr_rootitem}" '<' "${__farr_childitem}" ]; then
+#                echo "====== SWAPPING: root: ${__farr_root}, child: ${__farr_child}, a[root]: $__farr_rootitem, a[child]: $__farr_childitem"
+                # swap(a[root], a[child])
+                setvar "${__farr_gvrname}"_"${__farr_root}" "${__farr_childitem}"
+                setvar "${__farr_gvrname}"_"${__farr_child}" "${__farr_rootitem}"
+                # repeat to continue sifting down
+                __farr_root="${__farr_child}"
+
+                #
+                # XXX FIXME: Why are these lines not needed?
+                #
+                # This gives the *wrong* result
+                #__farr_rootitem="${__farr_childitem}"
+                # This does not harm but seems not needed
+                #eval __farr_rootitem=\"\$\{"${__farr_gvrname}"_"${__farr_root}"\}\"
+            else
+                # return to outer loop
+#                echo "====== BREAK"
+                break
+            fi
+#            echo "====== LOOPING ..."
+        done
+#        echo "==== AFTER: START: $__farr_start,   END: $__farr_end"
+        #farray_debug "$__farr_name"
+    done
+}
+
+
+#:
+#: Sort an array using Heapsort.
+#:
+#: Args:
+#:   $1: The array to sort to
+#:
+#: See Also:
+#:   `_farr_array_heapsort`
+#:
+farray_heapsort_bottomup() {
+    local __farr_name
+
+    local __farr_token __farr_gvrname __farr_len \
+          __farr_pos __farr_val __farr_val_1
+
+    _farr_array_get_meta "$@"
+
+    _farr_array_heapsort_bottomup
+}
+
+
+#:
+#: Internal sort implementation using Heapsort.
+#:
+#: Stable: no
+#:
+#: See: https://en.wikipedia.org/wiki/Heapsort
+#:
+#: Here the bottom-up implementation.
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_heapsort_bottomup() {
+    #
+
+    local __farr_end __farr_tmpitem
+
+    _farr_array_hsbu_heapify
+
+    #
+    # The following loop maintains the invariants that a[1:end−1] is a
+    # heap, and every element a[end:count] beyond end is greater
+    # than everything before it, i.e. a[end:count] is in sorted
+    # order.)
+
+    __farr_end=$((__farr_len + 1))
+    while [ "${__farr_end}" -gt 2 ]; do
+        # The heap size is reduced by one)
+        __farr_end=$((__farr_end - 1))
+        #
+        # a[1] is the root and largest value. The swap moves it in
+        # front of the sorted elements.)
+        #
+        #swap(a[end], a[1])
+        eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_1\}\"
+        eval "${__farr_gvrname}"_1=\"\$\{"${__farr_gvrname}"_"${__farr_end}"\}\"
+        setvar "${__farr_gvrname}"_"${__farr_end}" "${__farr_tmpitem}"
+        # the swap ruined the heap property, so restore it)
+        #siftDown(a, 1, end)
+        _farr_array_hsbu_sift_down 1 "${__farr_end}"
+    done
+}
+
+
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_hsbu_heapify() {
+    #
+
+    local __farr_start
+    #
+    # start is initialized to the first leaf node
+    #
+    # The last element in a 1-based array is at index count; find the
+    # parent of that element.
+    #
+    __farr_start=$(( (__farr_len / 2) + 1))
+    while [ "${__farr_start}" -gt 1 ]; do
+        # go to the last non-heap node
+        __farr_start=$((__farr_start - 1))
+        #
+        # Sift down the node at index 'start' to the proper place such
+        # that all nodes below the start index are in heap order.
+        #
+        _farr_array_hsbu_sift_down "${__farr_start}" $((__farr_len + 1))
+    done
+    # after sifting down the root all nodes/elements are in heap order
+}
+
+
+#:
+#: Args:
+#:   $1 (int): Index i
+#:   $2(int) : end
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_hsbu_sift_down() {
+    # $1 $2
+
+    local __farr_j __farr_item_i __farr_item_j __farr_tmpitem
+
+    _farr_array_hsbu_leaf_search __farr_j "$1" "$2"
+
+    eval __farr_item_i=\"\$\{"${__farr_gvrname}"_"${1}"\}\"
+    eval __farr_item_j=\"\$\{"${__farr_gvrname}"_"${__farr_j}"\}\"
+    while [ "${__farr_item_i}" '>' "${__farr_item_j}" ]; do
+        #j ← iParent(j)
+        __farr_j=$((__farr_j / 2))
+        eval __farr_item_j=\"\$\{"${__farr_gvrname}"_"${__farr_j}"\}\"
+    done
+    while [ "${__farr_j}" -gt "${1}" ]; do
+        #swap(a[i], a[j])
+        eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_"${1}"\}\"
+        eval "${__farr_gvrname}"_"${1}"=\"\$\{"${__farr_gvrname}"_"${__farr_j}"\}\"
+        setvar "${__farr_gvrname}"_"${__farr_j}" "${__farr_tmpitem}"
+        #j ← iParent(j)
+        __farr_j=$((__farr_j / 2))
+    done
+}
+
+
+#:
+#: Args:
+#:   $1 (str): The variable name where to store the return value into
+#:   $2 (int): Index i
+#:   $3 (int): end
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_hsbu_leaf_search() {
+    # $1 $2 $3
+
+    local __farr_ls_j __farr_ls_rightchild_j __farr_ls_leftchild_j \
+          __farr_ls_tmp_rightchild __farr_ls_tmp_leftchild
+
+    __farr_ls_j="${2}"
+
+    __farr_ls_rightchild_j=$((2 * __farr_ls_j + 1))
+    __farr_ls_leftchild_j=$((2 * __farr_ls_j))
+    while [ "${__farr_ls_rightchild_j}" -lt "${3}" ]; do
+        # Determine which of j's two children is the greater
+        eval __farr_ls_tmp_rightchild=\"\$\{"${__farr_gvrname}"_"${__farr_ls_rightchild_j}"\}\"
+        eval __farr_ls_tmp_leftchild=\"\$\{"${__farr_gvrname}"_"${__farr_ls_leftchild_j}"\}\"
+        if [ "${__farr_ls_tmp_rightchild}" '>' "${__farr_ls_tmp_leftchild}" ];  then
+            __farr_ls_j="${__farr_ls_rightchild_j}"
+        else
+            __farr_ls_j="${__farr_ls_leftchild_j}"
+        fi
+        __farr_ls_rightchild_j=$((2 * __farr_ls_j + 1))
+        __farr_ls_leftchild_j=$((2 * __farr_ls_j))
+    done
+    # At the last level, there might be only one child
+    if [ "${__farr_ls_leftchild_j}" -lt "${3}" ]; then
+        # j ← iLeftChild(j)
+        __farr_ls_j=$((2 * __farr_ls_j))
+    fi
+    setvar "${1}" "${__farr_ls_j}"
+}
diff -r 7d44112dfb81 -r b5b19c62da24 share/local-bsdtools/farray.sh
--- a/share/local-bsdtools/farray.sh	Sat Oct 26 18:38:05 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Sat Oct 26 22:42:01 2024 +0200
@@ -1637,68 +1637,6 @@
 
 
 #:
-#: Sort an array using Gnome Sort.
-#:
-#: Args:
-#:   $1: The array to sort to
-#:
-#: See Also:
-#:   `_farr_array_gnomesort`
-#:
-farray_gnomesort() {
-    local __farr_name
-
-    local __farr_token __farr_gvrname __farr_len \
-          __farr_pos __farr_val __farr_val_1
-
-    _farr_array_get_meta "$@"
-
-    _farr_array_gnomesort
-}
-
-
-#:
-#: Internal sort implementation using Gnome Sort.
-#:
-#: Stable: yes
-#:
-#: This is a very simple stable sort (a variant of insertion sort).
-#:
-#: See: https://en.wikipedia.org/wiki/Gnome_sort
-#:
-#: Input (Globals):
-#:   All the "Output (Globals)" from `farr_array_get_meta`:
-#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
-#:   These variables are declared local in this function but the shell
-#:   initializes them from the same variables in the nearest dynamic scope.
-#:   So they are really input variables and not also output variables.
-#:
-_farr_array_gnomesort() {
-
-    local __farr_name __farr_token __farr_gvrname __farr_len \
-          __farr_pos __farr_val __farr_val_1
-
-    __farr_pos=1
-    while [ "${__farr_pos}" -le "${__farr_len}" ]; do
-        if [ "${__farr_pos}" -eq 1 ]; then
-            __farr_pos=$((__farr_pos + 1))
-        else
-            eval __farr_val=\"\$\{"${__farr_gvrname}"_"${__farr_pos}"\}\"
-            eval __farr_val_1=\"\$\{"${__farr_gvrname}"_$((__farr_pos - 1))\}\"
-            if [ "${__farr_val}" '>' "${__farr_val_1}" ] || [ "${__farr_val}" '=' "${__farr_val_1}" ] ; then
-                __farr_pos=$((__farr_pos + 1))
-            else
-                # swap
-                setvar "${__farr_gvrname}_${__farr_pos}" "${__farr_val_1}"
-                setvar "${__farr_gvrname}_$((__farr_pos - 1))" "${__farr_val}"
-                __farr_pos=$((__farr_pos - 1))
-            fi
-        fi
-    done
-}
-
-
-#:
 #: Sort an array using Insertion Sort.
 #:
 #: Args:
@@ -1856,328 +1794,6 @@
 
 
 #:
-#: Sort an array using Heapsort.
-#:
-#: Args:
-#:   $1: The array to sort to
-#:
-#: See Also:
-#:   `_farr_array_heapsort`
-#:
-#: Note:
-#:   The heap is an implicit data structure which takes no space beyond the
-#:   array of objects to be sorted; the array is interpreted as a complete
-#:   binary tree where each array element is a node and each node's parent
-#:   and child links are defined by simple arithmetic on the array indexes.
-#:
-#:   The computation of these indexes is as follows:
-#:
-#:   - For 0-based indexes::
-#:
-#:       iLeftChild(i)  = 2⋅i + 1
-#:       iRightChild(i) = 2⋅i + 2
-#:       iParent(i)     = floor((i−1) / 2)
-#:
-#:   -  For 1 based indexes (in shell expession syntax and semantics)::
-#:
-#:       iLeftChild(i)  = 2 * i
-#:       iRightChild(i) = 2 * i + 1
-#:       iParent(i)     = i / 2
-#:
-#:   Variables:
-#:
-#:     Two variables (here, `start` and `end`) keep track of the bounds of the
-#:     heap area. The portion of the array before `start` is unsorted, while
-#:     the portion beginning at `end` is sorted. Heap construction decreases
-#:     `start` until it is one, after which heap extraction decreases `end`
-#:     until it is 2 and the array is entirely sorted.
-#:
-farray_heapsort() {
-    local __farr_name
-
-    local __farr_token __farr_gvrname __farr_len \
-          __farr_pos __farr_val __farr_val_1
-
-    _farr_array_get_meta "$@"
-
-    _farr_array_heapsort
-}
-
-
-#:
-#: Internal sort implementation using Heapsort.
-#:
-#: Stable: no
-#:
-#: See: https://en.wikipedia.org/wiki/Heapsort
-#:
-#: Here the "standard" implementation is used.
-#:
-#: Input (Globals):
-#:   All the "Output (Globals)" from `farr_array_get_meta`:
-#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
-#:   These variables are declared local in this function but the shell
-#:   initializes them from the same variables in the nearest dynamic scope.
-#:   So they are really input variables and not also output variables.
-#:
-_farr_array_heapsort() {
-
-    local __farr_name __farr_token __farr_gvrname __farr_len \
-          __farr_start __farr_end __farr_root __farr_child __farr_childp1 \
-          __farr_tmpitem __farr_rootitem __farr_childitem __farr_childp1item
-
-    __farr_start=$(( (__farr_len / 2) + 1))    # aka: iParent(of the last element)
-    __farr_end=$((__farr_len + 1))
-    while [ "${__farr_end}" -gt 2 ]; do
-#        echo  "== WHILE: START: $__farr_start,   END: $__farr_end"
-        if [ "${__farr_start}" -gt 1 ]; then
-#            echo "==== HEAP CONSTRUCTION"
-            # Heap construction
-            __farr_start=$((__farr_start - 1))
-        else
-#            echo "==== HEAP EXTRACTION"
-            # Heap extraction
-            __farr_end=$((__farr_end - 1))
-            # swap(a[end], a[1])
-            eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_1\}\"
-            eval "${__farr_gvrname}"_1=\"\$\{"${__farr_gvrname}"_"${__farr_end}"\}\"
-            setvar "${__farr_gvrname}"_"${__farr_end}" "${__farr_tmpitem}"
-        fi
-#        echo "==== BEFORE: START: $__farr_start,   END: $__farr_end"
-        #farray_debug "$__farr_name"
-        # The following is siftDown(a, start, end)
-        __farr_root="${__farr_start}"
-        eval __farr_rootitem=\"\$\{"${__farr_gvrname}"_"${__farr_root}"\}\"
-#        echo "==== NEW ROOT: ${__farr_root},   a[root]: ${__farr_rootitem}"
-        while [ $((2 * __farr_root)) -lt "${__farr_end}" ]; do
-            __farr_child=$((2 * __farr_root))
-            eval __farr_childitem=\"\$\{"${__farr_gvrname}"_"${__farr_child}"\}\"
-#            echo "CHILD: ${__farr_child},   ROOT: ${__farr_root},   END: ${__farr_end},   a[child]: ${__farr_childitem}"
-            # If there is a right child and that child is greater
-            __farr_childp1=$((__farr_child + 1))
-            if [ "${__farr_childp1}" -lt "${__farr_end}" ]; then
-                eval __farr_childp1item=\"\$\{"${__farr_gvrname}"_"${__farr_childp1}"\}\"
-#                echo "===== a[child+1]: ${__farr_childp1item}"
-                if [ "${__farr_childitem}" '<' "${__farr_childp1item}" ]; then
-                    #child=$((child + 1))
-                    __farr_child="${__farr_childp1}"
-                    eval __farr_childitem=\"\$\{"${__farr_gvrname}"_"${__farr_child}"\}\"
-#                    echo "====== INCR CHILD TO: $__farr_child"
-                fi
-            fi
-#            echo "====== a[root]: ${__farr_rootitem},   a[child]: ${__farr_childitem}"
-            if [ "${__farr_rootitem}" '<' "${__farr_childitem}" ]; then
-#                echo "====== SWAPPING: root: ${__farr_root}, child: ${__farr_child}, a[root]: $__farr_rootitem, a[child]: $__farr_childitem"
-                # swap(a[root], a[child])
-                setvar "${__farr_gvrname}"_"${__farr_root}" "${__farr_childitem}"
-                setvar "${__farr_gvrname}"_"${__farr_child}" "${__farr_rootitem}"
-                # repeat to continue sifting down
-                __farr_root="${__farr_child}"
-
-                #
-                # XXX FIXME: Why are these lines not needed?
-                #
-                # This gives the *wrong* result
-                #__farr_rootitem="${__farr_childitem}"
-                # This does not harm but seems not needed
-                #eval __farr_rootitem=\"\$\{"${__farr_gvrname}"_"${__farr_root}"\}\"
-            else
-                # return to outer loop
-#                echo "====== BREAK"
-                break
-            fi
-#            echo "====== LOOPING ..."
-        done
-#        echo "==== AFTER: START: $__farr_start,   END: $__farr_end"
-        #farray_debug "$__farr_name"
-    done
-}
-
-
-#:
-#: Sort an array using Heapsort.
-#:
-#: Args:
-#:   $1: The array to sort to
-#:
-#: See Also:
-#:   `_farr_array_heapsort`
-#:
-farray_heapsort_bottomup() {
-    local __farr_name
-
-    local __farr_token __farr_gvrname __farr_len \
-          __farr_pos __farr_val __farr_val_1
-
-    _farr_array_get_meta "$@"
-
-    _farr_array_heapsort_bottomup
-}
-
-
-#:
-#: Internal sort implementation using Heapsort.
-#:
-#: Stable: no
-#:
-#: See: https://en.wikipedia.org/wiki/Heapsort
-#:
-#: Here the bottom-up implementation.
-#:
-#: Input (Globals):
-#:   All the "Output (Globals)" from `farr_array_get_meta`:
-#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
-#:   These variables are declared local in this function but the shell
-#:   initializes them from the same variables in the nearest dynamic scope.
-#:   So they are really input variables and not also output variables.
-#:
-_farr_array_heapsort_bottomup() {
-    #
-
-    local __farr_end __farr_tmpitem
-
-    _farr_array_hsbu_heapify
-
-    #
-    # The following loop maintains the invariants that a[1:end−1] is a
-    # heap, and every element a[end:count] beyond end is greater
-    # than everything before it, i.e. a[end:count] is in sorted
-    # order.)
-
-    __farr_end=$((__farr_len + 1))
-    while [ "${__farr_end}" -gt 2 ]; do
-        # The heap size is reduced by one)
-        __farr_end=$((__farr_end - 1))
-        #
-        # a[1] is the root and largest value. The swap moves it in
-        # front of the sorted elements.)
-        #
-        #swap(a[end], a[1])
-        eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_1\}\"
-        eval "${__farr_gvrname}"_1=\"\$\{"${__farr_gvrname}"_"${__farr_end}"\}\"
-        setvar "${__farr_gvrname}"_"${__farr_end}" "${__farr_tmpitem}"
-        # the swap ruined the heap property, so restore it)
-        #siftDown(a, 1, end)
-        _farr_array_hsbu_sift_down 1 "${__farr_end}"
-    done
-}
-
-
-#:
-#: Input (Globals):
-#:   All the "Output (Globals)" from `farr_array_get_meta`:
-#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
-#:   These variables are declared local in this function but the shell
-#:   initializes them from the same variables in the nearest dynamic scope.
-#:   So they are really input variables and not also output variables.
-#:
-_farr_array_hsbu_heapify() {
-    #
-
-    local __farr_start
-    #
-    # start is initialized to the first leaf node
-    #
-    # The last element in a 1-based array is at index count; find the
-    # parent of that element.
-    #
-    __farr_start=$(( (__farr_len / 2) + 1))
-    while [ "${__farr_start}" -gt 1 ]; do
-        # go to the last non-heap node
-        __farr_start=$((__farr_start - 1))
-        #
-        # Sift down the node at index 'start' to the proper place such
-        # that all nodes below the start index are in heap order.
-        #
-        _farr_array_hsbu_sift_down "${__farr_start}" $((__farr_len + 1))
-    done
-    # after sifting down the root all nodes/elements are in heap order
-}
-
-
-#:
-#: Args:
-#:   $1 (int): Index i
-#:   $2(int) : end
-#:
-#: Input (Globals):
-#:   All the "Output (Globals)" from `farr_array_get_meta`:
-#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
-#:   These variables are declared local in this function but the shell
-#:   initializes them from the same variables in the nearest dynamic scope.
-#:   So they are really input variables and not also output variables.
-#:
-_farr_array_hsbu_sift_down() {
-    # $1 $2
-
-    local __farr_j __farr_item_i __farr_item_j __farr_tmpitem
-
-    _farr_array_hsbu_leaf_search __farr_j "$1" "$2"
-
-    eval __farr_item_i=\"\$\{"${__farr_gvrname}"_"${1}"\}\"
-    eval __farr_item_j=\"\$\{"${__farr_gvrname}"_"${__farr_j}"\}\"
-    while [ "${__farr_item_i}" '>' "${__farr_item_j}" ]; do
-        #j ← iParent(j)
-        __farr_j=$((__farr_j / 2))
-        eval __farr_item_j=\"\$\{"${__farr_gvrname}"_"${__farr_j}"\}\"
-    done
-    while [ "${__farr_j}" -gt "${1}" ]; do
-        #swap(a[i], a[j])
-        eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_"${1}"\}\"
-        eval "${__farr_gvrname}"_"${1}"=\"\$\{"${__farr_gvrname}"_"${__farr_j}"\}\"
-        setvar "${__farr_gvrname}"_"${__farr_j}" "${__farr_tmpitem}"
-        #j ← iParent(j)
-        __farr_j=$((__farr_j / 2))
-    done
-}
-
-
-#:
-#: Args:
-#:   $1 (str): The variable name where to store the return value into
-#:   $2 (int): Index i
-#:   $3 (int): end
-#:
-#: Input (Globals):
-#:   All the "Output (Globals)" from `farr_array_get_meta`:
-#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
-#:   These variables are declared local in this function but the shell
-#:   initializes them from the same variables in the nearest dynamic scope.
-#:   So they are really input variables and not also output variables.
-#:
-_farr_array_hsbu_leaf_search() {
-    # $1 $2 $3
-
-    local __farr_ls_j __farr_ls_rightchild_j __farr_ls_leftchild_j \
-          __farr_ls_tmp_rightchild __farr_ls_tmp_leftchild
-
-    __farr_ls_j="${2}"
-
-    __farr_ls_rightchild_j=$((2 * __farr_ls_j + 1))
-    __farr_ls_leftchild_j=$((2 * __farr_ls_j))
-    while [ "${__farr_ls_rightchild_j}" -lt "${3}" ]; do
-        # Determine which of j's two children is the greater
-        eval __farr_ls_tmp_rightchild=\"\$\{"${__farr_gvrname}"_"${__farr_ls_rightchild_j}"\}\"
-        eval __farr_ls_tmp_leftchild=\"\$\{"${__farr_gvrname}"_"${__farr_ls_leftchild_j}"\}\"
-        if [ "${__farr_ls_tmp_rightchild}" '>' "${__farr_ls_tmp_leftchild}" ];  then
-            __farr_ls_j="${__farr_ls_rightchild_j}"
-        else
-            __farr_ls_j="${__farr_ls_leftchild_j}"
-        fi
-        __farr_ls_rightchild_j=$((2 * __farr_ls_j + 1))
-        __farr_ls_leftchild_j=$((2 * __farr_ls_j))
-    done
-    # At the last level, there might be only one child
-    if [ "${__farr_ls_leftchild_j}" -lt "${3}" ]; then
-        # j ← iLeftChild(j)
-        __farr_ls_j=$((2 * __farr_ls_j))
-    fi
-    setvar "${1}" "${__farr_ls_j}"
-}
-
-
-
-#:
 #: 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
diff -r 7d44112dfb81 -r b5b19c62da24 tests/farray-array.t
--- a/tests/farray-array.t	Sat Oct 26 18:38:05 2024 +0200
+++ b/tests/farray-array.t	Sat Oct 26 22:42:01 2024 +0200
@@ -10,6 +10,7 @@
   $ . "${TESTDIR}/testsetup.sh"
   $ _p_datadir="${TESTDIR}/../share/local-bsdtools"
   $ . "${_p_datadir}/farray.sh"
+  $ . "${_p_datadir}/farray-ext.sh"  
 
 
 Basic Creation and Destruction
diff -r 7d44112dfb81 -r b5b19c62da24 tests/sort-perf/sort-perf.sh
--- a/tests/sort-perf/sort-perf.sh	Sat Oct 26 18:38:05 2024 +0200
+++ b/tests/sort-perf/sort-perf.sh	Sat Oct 26 22:42:01 2024 +0200
@@ -10,6 +10,7 @@
 . "${TESTDIR}/testsetup.sh"
 _p_datadir="${TESTDIR}/../share/local-bsdtools"
 . "${_p_datadir}/farray.sh"
+. "${_p_datadir}/farray-ext.sh"
 
 
 fatal() {