#!/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}"
}