#!/bin/sh
# -*- indent-tabs-mode: nil; -*-
#:
#: A simple library to emulate simple array (one-dimensional) in a POSIX shell.
#:
#: :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@@
#:
#: This implementation is inspired by
#: https://unix.stackexchange.com/questions/137566/arrays-in-unix-bourne-shell
#:
#: Is implements one-dimensional array with one-base indexing.
#:
#: Hints and rules:
#:
#: - Every array has a NAME
#: - One-based indexing is used
#: - Array elements are stored in a global variable named
#:   ``_farr_array_<NAME>_<index-number>``
#: - The number of elements in the array ist stored in the global
#:   variable ``_farr_array_<NAME>__``
#: - An array name must conform to shell variable naming conventions
#: - Currently the number of of elements of an array must be >= 0
#: - An unset global variable ``_farr_array_<NAME>__`` variable is a severe
#:   error normally and forces an immediate error ``exit``.
#:   Exceptions to this rule are documented.
#:
#: This module also contains a very rough implementation of an alist
#: (aka dict, aka map).
#: This is implemented with two corresponding arrays: one for the keys
#: and one for the values.
#:
#: If the map has the name NAME then the array naming is as such:
#:
#: - The keys are held in an array with name alist_key_<NAME>
#: - The values are held in an array with name alist_val_<NAME>
#:
#: This makes _farr_array_alist_key_<NAME> and _farr_array_alist_val_<NAME>
#: as effective shell level variable name prefixes.
#:
#: An alist exists iff both of the underlying arrays exist.
#:
#: Important:
#:   All names that start with ``_farr_`` or ``__farr_`` are reserved
#:   for private use. Try to do not use such names in your scripts.
#:
#:   Public functions start with ``array_`` or ``alist_``.
#:


_farr_global_prefix=_farr_array_
_farr_unset=_farr__UNSET_d646c21167a611efa78174d435fd3892__
_farr_alist_key_infix=alist_key_
_farr_alist_value_infix=alist_val_


#:
#: Internal error for fatal errors.
#:
#: Args:
#:   $1 (str): The error message.
#:
_farr_fatal() {
    echo "ERROR: ${1}" 1>&2
    exit 70    # EX_SOFTWARE
}


#:
#: Quote the given input to be safely used in evals with "Dollar-Single Quotes"
#:
#: Args:
#:   $1: The value to be quoted.
#:
#:
#: From FreeBSD's :manpage:`sh(1)`:
#:
#:   Dollar-Single Quotes
#:
#:     Enclosing characters between ``$'`` and ``'`` preserves the literal
#:     meaning of all characters except backslashes and single quotes.
#:
#:     A backslash introduces a C-style escape sequence.
#:     Most important here:
#:
#:       ``\\``
#:                Literal backslash
#:
#:       ``\'``
#:                Literal single-quote
#:
_farr_quote_for_eval_dsq() {
    printf "%s" "${1}" \
        | LC_ALL=C /usr/bin/sed -e $'s/\\\\/\\\\\\\\/g' -e $'s/\'/\\\\\'/g'
    #                              escape a backslash      escape a single quote
    # '    # make Emacs happy for correct syntax highlighting
}


#:
#: Create a new array.
#:
#: It is assumed that the array does not exist already.
#:
#: Args:
#:   $1 (str): The name of the array.
#:             Must conform to shell variable naming conventions.
#:   $2... (optional): Optional initialization values
#:
#: Exit:
#:   Iff the array already exists.
#:
array_create() {
    local __farr_name

    local __farr_gvrname __farr_el __farr_l

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    shift

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}

    [ "${__farr_l}" != ${_farr_unset} ] && _farr_fatal "array \`${__farr_name}' already exists"
    # Really create
    eval ${__farr_gvrname}__=0

    for __farr_el in "$@"; do
	array_append ${__farr_name} "${__farr_el}"
    done
}


#:
#: Create or re-create a new array.
#:
#: Args:
#:   $1 (str): The name of the array.
#:             Must conform to shell variable naming conventions.
#:   $2... (optional): Optional initialization values.
#:
#: If the array exists already it will be reinitialized completely.
#: If the array does not exist already it is just like `array_create`.
#: It is just a convenience function for calling `array_destroy`, ignoring
#: errors eventually, and calling `array_create`.
#:
array_new() {
    array_destroy $1 || true
    array_create "$@"
}


#:
#: Get the length of an array and put it into a variable
#:
#: Args:
#:   $1 (str): The name of the variable to put the length into.
#:   $2 (str): The name of the array.
#:
#: Returns:
#:   0 (truthy) if the array exists,
#:   1 (falsy) if the array does not exist
#:
array_length() {
    local __farr_varname __farr_name

    local __farr_gvrname __farr_l

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_gvrname=${_farr_global_prefix}$2

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}

    if [ "${__farr_l}" = ${_farr_unset} ]; then
	return 1
    else
        eval ${__farr_varname}=${__farr_l}
        return 0
    fi
}


#:
#: Get the length of an array.
#:
#: Args:
#:   $1 (str): The name of the array.
#:
#: Output (stdout):
#:   The number of elements of the array.
#:   If the array does not exist the output is -1.
#:
#: Returns:
#:   0 (truthy)
#:
array_print_length() {
    local __farr_name

    local __farr_vn

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1

    if array_length __farr_vn ${__farr_name}; then
        printf "%s" "${__farr_vn}"
    else
        printf "%s" "-1"
    fi
    return 0
}


#:
#: Append a value to an existing array.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (optional): The value to append. If the value is not given the null
#:                  will be appended.
#:
array_append() {
    local __farr_name __farr_value

    local __farr_gvrname __farr_l __farr_l_1

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    __farr_value="${2-}"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_l_1=$((${__farr_l} + 1))

    #
    # Set value
    # Escape properly: use $' ' and escape any backslashes and single quotes.
    #
    eval ${__farr_gvrname}_${__farr_l_1}=\$\'"$(_farr_quote_for_eval_dsq "${__farr_value}")"\'
    # the implementation below line does not escape properly
    #   eval ${__farr_gvrname}_${__farr_l_1}="\"${__farr_value}\""

    # Set new array length
    eval ${__farr_gvrname}__=${__farr_l_1}
}


#:
#: Set an array at an index to a value.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (int): The index.
#:   $3 (optional): The value to set. If the value is not given the null
#:                  will be appended.
#:
#: No holes are allowed in an array: only values at existing indices are
#: allowed. As an exception a value can be appended if the given index
#: is exactly the current length + 1.
#:
array_set() {
    local __farr_name __farr_index __farr_value

    local __farr_gvrname __farr_l __farr_l_1

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    [ $# -lt 2 ] && _farr_fatal "missing array index"
    __farr_index=$2
    __farr_value="${3-}"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    # For proper quoting: see array_append
    if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_l} \) ]; then
        # replace a value at an existing index
        eval ${__farr_gvrname}_${__farr_l}=\$\'"$(_farr_quote_for_eval_dsq "${__farr_value}")"\'
    else
        __farr_l_1=$((${__farr_l} + 1))
        if [ ${__farr_index} -eq ${__farr_l_1} ]; then
            # append value
            eval ${__farr_gvrname}_${__farr_l_1}=\$\'"$(_farr_quote_for_eval_dsq "${__farr_value}")"\'
            # and set new length
            eval ${__farr_gvrname}__=${__farr_l_1}
        else
            _farr_fatal "array index out of bounds (cannot create holes)"
        fi
    fi
}


#:
#: Get an array value from a given index and put it into given variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of the existing array.
#:   $3 (int): The index.
#:
array_get() {
    local __farr_varname __farr_name __farr_index

    local __farr_gvrname __farr_l

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_gvrname=${_farr_global_prefix}$2
    [ $# -lt 3 ] && _farr_fatal "missing array index"
    __farr_index=$3

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt ${__farr_l} \) ]; then
	_farr_fatal "array index out of bounds"
    fi

    eval ${__farr_varname}=\"\${${__farr_gvrname}_${__farr_index}}\"
}


#:
#: Try to get an array value from a given index into a variable
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of the existing array.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds (i.e. EOD).
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
array_tryget() {
    local __farr_varname __farr_name __farr_index

    local __farr_gvrname __farr_l

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_gvrname=${_farr_global_prefix}$2
    [ $# -lt 3 ] && _farr_fatal "missing array index"
    __farr_index=$3

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt ${__farr_l} \) ]; then
	return 1
    fi

    eval ${__farr_varname}=\"\${${__farr_gvrname}_${__farr_index}}\"
    return 0
}


#:
#: Delete an array value at a given index.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (int): The index to delete to.
#:
array_del() {
    local __farr_name __farr_index

    local __farr_gvrname __farr_l __farr_new_l
    local __farr_idx __farr_idx_1 __farr_value

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    [ $# -lt 2 ] && _farr_fatal "missing array index"
    __farr_index=$2

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt ${__farr_l} \) ]; then
	_farr_fatal "array index out of bounds"
    fi

    __farr_new_l=$((${__farr_l} - 1))
    __farr_idx=${__farr_index}
    __farr_idx_1=$((${__farr_idx} + 1))
    while [ ${__farr_idx} -lt ${__farr_l} ]; do
        # copy the following value to the current index
        eval __farr_value=\"\${${__farr_gvrname}_${__farr_idx_1}}\"
        eval ${__farr_gvrname}_${__farr_idx}=\$\'"$(_farr_quote_for_eval_dsq "${__farr_value}")"\'
        __farr_idx=$((${__farr_idx} + 1))
        __farr_idx_1=$((${__farr_idx} + 1))
    done
    # Drop the last item
    eval unset unset ${__farr_gvrname}_${__farr_idx}
    # Set the new length
    eval ${__farr_gvrname}__=${__farr_new_l}
}


#:
#: Empty an existing array.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:
array_clear() {
    local __farr_name

    local __farr_gvrname __farr_l __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_l} ]; do
	eval unset ${__farr_gvrname}_${__farr_idx}
	__farr_idx=$((${__farr_idx} + 1))
    done

    # Length is now zero
    eval ${__farr_gvrname}__=0
}


#:
#: Destroy and unset an array and all its elements.
#:
#: Args:
#:   $1 (str): The name of an array. The array may exist or not.
#:
#: Returns:
#:   - A truthy value if the array existed and has been deleted.
#:   - A falsy value if the array does not exist.
#:
array_destroy() {
    local __farr_name

    local __farr_gvrname __farr_l __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1

    # Handle non-existing array names
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	return 1
    fi
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_l} ]; do
	eval unset ${__farr_gvrname}_${__farr_idx}
	__farr_idx=$((${__farr_idx} + 1))
    done

    # Remove
    eval unset ${__farr_gvrname}__
}


#:
#: Determine whether a value is found within the array
#:
#: Args:
#:   $1: The name of an existing array.
#:   $2: The value to search for.
#:
#: Returns:
#:   0 (truish) if the argument value is found within the given array,
#:   1 (falsy) otherwise
#:
array_contains() {
    local __farr_name __farr_searched_value

    local __farr_gvrname __farr_l __farr_idx __farr_existing_value

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    [ $# -ne 2 ] && _farr_fatal "missing value to search for"
    __farr_searched_value="$2"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_l} ]; do
        eval __farr_existing_value=\"\${${__farr_gvrname}_${__farr_idx}}\"
        [ "${__farr_existing_value}" = "${__farr_searched_value}" ] && return 0
	__farr_idx=$((${__farr_idx} + 1))
    done
    return 1
}


#:
#: Try to find the index of a given value in an existing array.
#:
#: 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, optional): The start index to search for (inclusive)
#:   $5 (int, optional):  The index to stop (inclusive)
#:
#: Output (stdout):
#:   The index number where the value is found -- if any
#:
#: Returns:
#:   - 0 (truish) if the argument value is found within the given array
#:     and index constraints
#:   - 1 (falsy) otherwise
#:
array_find() {
    local __farr_varname __farr_name __farr_searched_value __farr_start __farr_end

    local __farr_gvrname __farr_l __farr_cur_idx __farr_existing_value

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_gvrname=${_farr_global_prefix}$2
    [ $# -lt 3 ] && _farr_fatal "missing value to search for"
    __farr_searched_value="$3"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_start=${4-1}
    __farr_end=${5-${__farr_l}}

    __farr_cur_idx=${__farr_start}
    while [ ${__farr_cur_idx} -le ${__farr_end} ]; do
        eval __farr_existing_value=\"\${${__farr_gvrname}_${__farr_cur_idx}}\"
        if [ "${__farr_existing_value}" = "${__farr_searched_value}" ]; then
            #printf "%d" ${__farr_cur_idx}
            eval ${__farr_varname}=${__farr_cur_idx}
            return 0
        fi
	__farr_cur_idx=$((${__farr_cur_idx} + 1))
    done
    return 1
}


#:
#: Join all the elements in given array with a separator and put the result
#: into a variable.
#:
#: Args:
#:   $1 (str): The name of a variable where to put joined string value into.
#:   $2 (str): The name of an existing array.
#:   $3 (str, optional): The separator (default: a space `` ``).
#:
array_join() {
    local __farr_varname __farr_name __farr_separator

    local __farr_gvrname __farr_l __farr_join_idx
    local __farr_command __farr_real_separator __farr_current_value

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_gvrname=${_farr_global_prefix}$2

    __farr_separator="${3-" "}"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_real_separator=""
    __farr_command=""

    __farr_join_idx=1
    while [ ${__farr_join_idx} -le ${__farr_l} ]; do
	eval __farr_current_value=\"\${${__farr_gvrname}_${__farr_join_idx}}\"
	__farr_command="${__farr_command}${__farr_real_separator}${__farr_current_value}"
	__farr_real_separator="${__farr_separator}"
	__farr_join_idx=$((${__farr_join_idx} + 1))
    done
    eval ${__farr_varname}=\"\${__farr_command}\"
}


#:
#: Join all the elements in given array with a space `` `` character while
#: escaping properly for feeding into shell's ``eval`` and put it into a
#: variable.
#:
#: It is meant that ``eval "$(array_join_for_eval ARRAY)"`` is safe:
#: every item of the array becomes a word when the eval evaluates the
#: joined string.
#:
#: Args:
#:   $1 (str): The name of a variable where to put joined and properly encoded
#:             string value into.
#:   $2 (str): The name of an existing array.
#:
#: Output (stdout):
#:   The result string.
#:
array_join_for_eval() {
    local __farr_varname  __farr_name

    local __farr_gvrname __farr_l __farr_join_idx
    local __farr_command __farr_real_separator __farr_current_value

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_gvrname=${_farr_global_prefix}$2

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_real_separator=""
    __farr_command=""

    __farr_join_idx=1
    while [ ${__farr_join_idx} -le ${__farr_l} ]; do
	eval __farr_current_value=\"\${${__farr_gvrname}_${__farr_join_idx}}\"
	__farr_command="${__farr_command}${__farr_real_separator}\$'$(_farr_quote_for_eval_dsq "${__farr_current_value}")'"
	__farr_real_separator=' '
	__farr_join_idx=$((${__farr_join_idx} + 1))
    done
    eval ${__farr_varname}=\"\${__farr_command}\"
}


#:
#: Join all the elements in given array with a space `` `` character while
#: escaping properly for feeding into shell's ``eval``.
#:
#: ``eval "$(array_join_for_eval ARRAY)"`` is safe:
#: every item of the array becomes a word when the eval evaluates the
#: joined string.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:
#: Output (stdout):
#:   The joined and properly encoded string.
#:
array_print_join_for_eval() {
    local __farr_name

    local __farr_gvrname __farr_l __farr_join_idx __farr_current_value

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_join_idx=1
    while [ ${__farr_join_idx} -le ${__farr_l} ]; do
	eval __farr_current_value=\"\${${__farr_gvrname}_${__farr_join_idx}}\"
        if [ ${__farr_join_idx} -gt 1 ]; then
            printf "%s" " "
        fi
        printf "%s" "\$'$(_farr_quote_for_eval_dsq "${__farr_current_value}")'"
	__farr_join_idx=$((${__farr_join_idx} + 1))
    done
}


#:
#: Call a function for every element in an array starting at the first index.
#:
#: The function to be called must accept three arguments:
#: - the array name
#: - the current index
#: - the element value at the current index
#:
#: The iteration stops if the called function returns a falsy value.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2 (str): The name of a function to be called with three arguments.
#:
#: Warning:
#:   If the number of elements changes while being in `array_for_each` then
#:   the behaviour is undefined.
#:   The current implementation determines the length of the array once
#:   at the start of execution.
#:
array_for_each() {
    local __farr_name __farr_callback

    local __farr_gvrname __farr_l __farr_idx __farr_rv

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    [ $# -lt 2 ] && _farr_fatal "missing callback function name"
    __farr_callback="$2"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_l} ]; do
	eval "${__farr_callback} ${__farr_name} ${__farr_idx} \"\${${__farr_gvrname}_${__farr_idx}}\""
	__farr_rv=$?
	[ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
	__farr_idx=$((${__farr_idx} + 1))
    done
    return 0
}


#:
#: Like `array_for_each`, but the function is called in reversed order --
#: beginning with the last index.
#:
array_reversed_for_each() {
    local __farr_name __farr_callback

    local __farr_gvrname __farr_l __farr_idx __farr_rv

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1
    [ $# -lt 2 ] && _farr_fatal "missing callback function name"
    __farr_callback="$2"

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	_farr_fatal "array \`${__farr_name}' does not exist"
    fi

    __farr_idx=${__farr_l}
    while [ ${__farr_idx} -gt 0 ]; do
	eval "${__farr_callback} ${__farr_name} ${__farr_idx} \"\${${__farr_gvrname}_${__farr_idx}}\""
	__farr_rv=$?
	[ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
	__farr_idx=$((${__farr_idx} - 1))
    done
    return 0
}


#:
#: Print the contents of an array to stderr.
#:
#: Args:
#:   $1 (str): The name of an array. The array may exist or not.
#:
#: Returns:
#:   0
#:
array_debug() {
    local __farr_name

    local __farr_gvrname __farr_l

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_gvrname=${_farr_global_prefix}$1

    # Check whether the variable already exists
    eval __farr_l=\${${__farr_gvrname}__:-${_farr_unset}}
    if [ "${__farr_l}" = ${_farr_unset} ]; then
	echo "DEBUG: array \`${__farr_name}' does not exist" 1>&2
        return 0
    fi
    echo "DEBUG: array \`${__farr_name}' has length ${__farr_l}" 1>&2
    if [ ${__farr_l} -gt 0 ]; then
        echo "DEBUG:   its contents:" 1>&2
        array_for_each ${__farr_name} _array_debug_print_value
    fi
    return 0
}


#:
#: Debug output helper for `array_debug`.
#:
_array_debug_print_value() {
    printf "DEBUG:     %s: \`%s'\\n" "$2" "$3" 1>&2
    return 0
}


#:
#: Create a new alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:             Must conform to shell variable naming conventions.
#:
#: Exit:
#:   Iff the alist already exists.
#:
alist_create() {
    local __farr_name

    local __farr_key_array __farr_val_array

    [ $# -lt 1 ] && _farr_fatal "missing alist name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}

    if array_create ${__farr_key_array}; then
        if ! array_create ${__farr_val_array}; then
            array_destroy ${__farr_key_array} || true
        fi
    fi
}


#:
#: Get the length of an alist and put it into a variable.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:
#: Returns:
#:   0 (truthy) if the array exists,
#:   1 (falsy) if the array does not exist.
#:
alist_length() {
    local __farr_varname __farr_name

    local __farr_key_array

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}

    array_length ${__farr_varname} ${__farr_key_array}
    return $?
}


#:
#: Get the length of an alist.
#:
#: Args:
#:   $1 (str): The name of the variable to put the length into.
#:   $2 (str): The name of the alist.
#:
#: Output (stdout):
#:   The number of elements in the alist.
#:   If the array does not exist the output is -1.
#:
#: Returns:
#:   0 (truthy)
#:
alist_print_length() {
    local __farr_name

    local __farr_pl_l __farr_key_array

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}

    array_print_length ${__farr_key_array}
    return 0
}


#:
#: Empty an existing alist.
#:
#: Args:
#:   $1 (str): The name of the existing alist.
#:
alist_clear() {
    local __farr_name

    local __farr_key_array __farr_val_array

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}

    array_clear ${__farr_val_array}
    array_clear ${__farr_key_array}
}


#:
#: Create or re-create a new alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:             Must conform to shell variable naming conventions.
#:
#: If the alist exists already it will be reinitialized completely.
#: If the alist does not exist already it is just like `alist_create`.
#: It is just a convenience function for calling `alist_destroy`, ignoring
#: errors eventually, and calling `alist_create`.
#:
alist_new() {
    alist_destroy $1 || true
    alist_create "$@"
}


#:
#: Destroy and unset an alist
#:
#: Args:
#:   $1 (str): The name of an alist. The alist may exist or not.
#:
#: Returns:
#:   - A truthy value if the alist existed and has been deleted.
#:   - A falsy value if the alist does not exist.
#:
alist_destroy() {
    local __farr_name

    local __farr_key_array __farr_val_array __farr_rc_key __farr_rc_val

    [ $# -lt 1 ] && _farr_fatal "missing alist name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}

    __farr_rc_key=0
    __farr_rc_val=0
    array_destroy ${__farr_val_array} || __farr_rc_val=$?
    array_destroy ${__farr_key_array} || __farr_rc_key=$?

    [ ${__farr_rc_key} -gt 0 ] && return ${__farr_rc_key}
    [ ${__farr_rc_val} -gt 0 ] && return ${__farr_rc_val}
    return 0
}


#:
#: Map a key to a value.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2: The key.
#:   $3: The value.
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
alist_set() {
    local __farr_name __farr_key __farr_value

    local __farr_key_array __farr_val_array __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_key="$2"
    [ $# -lt 3 ] && _farr_fatal "missing value"
    __farr_value="$3"

    if array_find __farr_idx ${__farr_key_array} "${__farr_key}"; then
        # Replace existing
        array_set ${__farr_key_array} ${__farr_idx} "${__farr_key}"
        array_set ${__farr_val_array} ${__farr_idx} "${__farr_value}"
    else
        # append new
        array_append ${__farr_key_array} "${__farr_key}"
        array_append ${__farr_val_array} "${__farr_value}"
        if [ "$(array_print_length ${__farr_key_array})" -ne "$(array_print_length ${__farr_val_array})" ]; then
            _farr_fatal "alist \`${__farr_name}': could not set (append error)"
        fi
    fi
}


#:
#: Get the value that is associated with a key and put it into a variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3: The key.
#:
#: Exit:
#:   - If the key is not found.
#:   - If one of the underlying arrays that implement the alist does not exist.
#:     or if an internal inconsistency will be detected.
#:
alist_get() {
    local __farr_varname __farr_name __farr_key

    local __farr_key_array __farr_val_array __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}
    [ $# -lt 3 ] && _farr_fatal "missing key"
    __farr_key="$3"

    if array_find __farr_idx ${__farr_key_array} "${__farr_key}"; then
        # Yes, we found an index
        #printf "%s" "$(array_get ${__farr_val_array} ${__farr_idx})"
        array_get ${__farr_varname} ${__farr_val_array} ${__farr_idx}
    else
        _farr_fatal "alist \`${__farr_name}': key not found"
    fi
}


#:
#: Try to get the value that is associated with a key and store it in a
#: variable.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3: The key.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given key is not found.
#:
alist_tryget() {
    local __farr_varname __farr_name __farr_key

    local __farr_key_array __farr_val_array __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}
    [ $# -lt 3 ] && _farr_fatal "missing key"
    __farr_key="$3"

    if array_find __farr_idx ${__farr_key_array} "${__farr_key}"; then
        # Yes, we found an index
        #printf "%s" "$(array_get ${__farr_val_array} ${__farr_idx})"
        array_get ${__farr_varname} ${__farr_val_array} ${__farr_idx}
        return 0
    else
        return 1
    fi
}


#:
#: Try to get the key that is associated with a storage index and store it in a variable.
#:
#: Use this for iteration over values.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the key into.
#:   $2 (str): The name of an existing alist.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
alist_tryget_key_at_index() {
    local __farr_varname __farr_name __farr_index

    local __farr_key_array __farr_val_array __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    [ $# -lt 3 ] && _farr_fatal "missing index"
    __farr_index=$3

    array_tryget ${__farr_varname} ${__farr_key_array} ${__farr_index}
}


#:
#: Try to get the value that is associated with a storage index and store it in a variable.
#:
#: Use this for iteration over keys.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
alist_tryget_value_at_index() {
    local __farr_varname __farr_name __farr_index

    local __farr_key_array __farr_val_array __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing variable name"
    __farr_varname=$1
    [ $# -lt 2 ] && _farr_fatal "missing array name"
    __farr_name=$2
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}
    [ $# -lt 3 ] && _farr_fatal "missing index"
    __farr_index=$3

    array_tryget ${__farr_varname} ${__farr_val_array} ${__farr_index}
}


#:
#: Determine whether a key is found within the alist.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2: The key.
#:
#: Returns:
#:   0 (truthy) on success if the key is found,
#:   1 (falsy) if the given key is not found.
#:
alist_contains() {
    local __farr_name __farr_key

    local __farr_key_array __farr_idx

    [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_key="$2"

    if array_find __farr_idx ${__farr_key_array} "${__farr_key}"; then
        return 0
    else
        return 1
    fi
}


#:
#: Call a function for every key-value pair in an alist starting in index order.
#:
#: The function to be called must accept three or four arguments:
#: - the alist name
#: - the element key at the current index
#: - the element value at the current index
#: - the current index
#:
#: The iteration stops if the called function returns a falsy value.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2 (str): The name of a function to be called with four arguments.
#:
#: Warning:
#:   If the number of elements changes while being in `alist_for_each` then
#:   the behaviour is undefined.
#:   The current implementation determines the length of the alist once
#:   at the start of execution.
#:
alist_for_each() {
    local __farr_name __farr_callback

    local __farr_key_array __farr_val_array __farr_idx __farr_length
    local __farr_feidx __farr_fekey __farr_feval __farr_rv

    [ $# -lt 1 ] && _farr_fatal "missing alist name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}
    [ $# -lt 2 ] && _farr_fatal "missing callback function name"
    __farr_callback="$2"

    if ! alist_length __farr_length ${__farr_name}; then
        _farr_fatal "alist \`${__farr_name}' does not exist"
    fi
    __farr_feidx=1
    while [ ${__farr_feidx} -le ${__farr_length} ]; do
        if alist_tryget_key_at_index __farr_fekey ${__farr_name} ${__farr_feidx}; then
            if alist_tryget_value_at_index __farr_feval ${__farr_name} ${__farr_feidx}; then
                eval "${__farr_callback} ${__farr_name} \"\${__farr_fekey}\" \"\${__farr_feval}\" ${__farr_feidx}"
                __farr_rv=$?
                [ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
            else
                _farr_fatal "alist \`${__farr_name}': missing value index"
            fi
        else
            _farr_fatal "alist \`${__farr_name}': missing key index"
        fi
        __farr_feidx=$((${__farr_feidx} + 1))
    done
}


#:
#: Print the contents of an alist to stderr.
#:
#: Args:
#:   $1 (str): The name of an alist. The array may exist or not.
#:
#: Returns:
#:   0
#:
#: This function must know some of the basics of the array implementation
#: also.
#:
alist_debug() {
    local __farr_name

    local __farr_key_array __farr_val_array
    local __farr_key_gvrname __farr_val_gvrname
    local __farr_key_l __farr_val_l __farr_idx __farr_i_k __farr_i_v

     [ $# -lt 1 ] && _farr_fatal "missing array name"
    __farr_name=$1
    __farr_key_array=${_farr_alist_key_infix}${__farr_name}
    __farr_val_array=${_farr_alist_value_infix}${__farr_name}

    __farr_key_gvrname=${_farr_global_prefix}${__farr_key_array}
    __farr_val_gvrname=${_farr_global_prefix}${__farr_val_array}

    # Check whether the variables alread exist
    eval __farr_key_l=\${${__farr_key_gvrname}__:-${_farr_unset}}
    if [ "${__farr_key_l}" = ${_farr_unset} ]; then
	echo "DEBUG: alist \`${__farr_name}' does not exist (key list)" 1>&2
        return 0
    fi
    eval __farr_val_l=\${${__farr_val_gvrname}__:-${_farr_unset}}
    if [ "${__farr_val_l}" = ${_farr_unset} ]; then
	echo "DEBUG: alist \`${__farr_name}' does not exist (value list)" 1>&2
        return 0
    fi
    if [ ${__farr_key_l} -ne ${__farr_val_l} ]; then
        echo "DEBUG: length mismatch between keys and values in alist \`${__farr_name}' encountered" 1>&2
        return 0
    fi
    echo "DEBUG: alist \`${__farr_name}' has length ${__farr_key_l}" 1>&2
    if [ "${__farr_key_l}" -gt 0 ]; then
        echo "DEBUG:   its contents:" 1>&2
        __farr_idx=1
        while [ ${__farr_idx} -le ${__farr_key_l} ]; do
            eval __farr_i_k=\"\${${__farr_key_gvrname}_${__farr_idx}}\"
            eval __farr_i_v=\"\${${__farr_val_gvrname}_${__farr_idx}}\"
            printf "DEBUG:     \`%s' -> \`%s'\\n" "${__farr_i_k}" "${__farr_i_v}" 1>&2
            __farr_idx=$((${__farr_idx} + 1))
        done
    fi
    return 0
}


_array_test() {
    local _i _var _k _v

    set -
    set -eu

    array_create TEST 1 2 3 '4  5   6' $'" 123" \\\'45 '    # '
    array_debug TEST
    if array_contains TEST 7; then
        echo "CONTAINS (ERROR)"
    fi
    if ! array_contains TEST '4  5   6'; then
        echo "NO CONTAINS (ERROR)"
    fi
    if array_contains TEST '4 5 6'; then
        echo "CONTAINS (ERROR)"
    fi
    if ! array_contains TEST 1; then
        echo "NOT CONTAINS (ERROR)"
    fi
    if ! array_contains TEST 2; then
        echo "NOT CONTAINS (ERROR)"
    fi

    if ! array_contains TEST $'" 123" \\\'45 ' ; then      # '
       echo "NOT CONTAINS (ERROR)"
    fi
    if ! array_find _i TEST $'" 123" \\\'45 ' ; then       # '
       echo "NOT CONTAINS (ERROR)"
    fi

    array_get _var TEST 1
    printf "VAR 1: %s\n" "$_var"
    array_get _var TEST 5
    printf "VAR 2: %s\n" "$_var"
    [ "$_var" = $'" 123" \\\'45 ' ] || echo "COMPARE ERROR"

    array_new TEST 11 22 33 '44  55   66' $'" 112233" \\\'4455 '    # '
    array_debug TEST

    array_get _i TEST 1
    echo $_i
    array_get _i TEST 2
    array_del TEST 4
    array_get _i TEST 4
    echo $_i
    array_tryget _i TEST 1 || echo "NOT FOUND (ERROR)"
    array_tryget _i TEST 4 || echo "NOT FOUND (ERROR)"
    ! array_tryget _i TEST 5 || echo "FOUND (ERROR)"
    array_get _var TEST 4
    [ "$_var" = $'" 112233" \\\'4455 ' ] || echo "COMPARE ERROR"  # '

    if ! array_destroy TEST; then
        echo "DESTROY FAILED (ERROR)"
    fi
    if array_destroy TEST; then
        echo "DESTROY succeeded (ERROR)"
    fi
    array_destroy TEST || true

    alist_create LIST
    alist_debug LIST
    alist_set LIST K1 V1
    alist_set LIST K2 V2
    alist_debug LIST
    alist_set LIST K2 V2-2
    alist_set LIST K3 $'" 111222333" \\\'444555 '    # '
    if ! alist_contains LIST K1; then
        echo "NOT CONTAINS (ERROR)"
    fi
    if alist_contains LIST K; then
        echo "CONTAINS (ERROR)"
    fi
    alist_debug LIST
    if ! alist_tryget _var LIST K1; then
        echo "NOT FOUND (ERROR)"
    fi
    if alist_tryget _i LIST K; then
        echo "FOUND (ERROR)"
    fi
    alist_length _i LIST
    echo "LENGTH: $_i"
    printf "%s" "PRINT LENGTH: "
    alist_print_length LIST
    echo
    _var="$(alist_print_length NON_EXISTING_LIST)"
    if [ "${_var}" != "-1" ]; then
        echo "VALID LENGTH (ERROR)"
    fi

    # Iteration by indexing
    echo "ITERATE:"
    _i=1
    while alist_tryget_key_at_index _k LIST ${_i}; do
        # cannot fail
        alist_tryget_value_at_index _v LIST ${_i}
        printf "  KEY: \`%s', VAL: \`%s'\\n" "${_k}" "${_v}"
        _i=$((${_i} + 1))
    done

    # Iteration with for each
    echo "ITERATE (for each):"
    alist_for_each LIST $'printf "EACH: %s key \\`%s\\\', value \\`%s\\\' at idx %d\\n"'   # `

    alist_clear LIST
    if ! alist_destroy LIST ; then
        echo "DESTROY FAILED (ERROR)"
    fi
    if alist_destroy LIST ; then
        echo "DESTROY SUCCEEDED (ERROR)"
    fi
    alist_destroy LIST || true
    #set
}


#_array_test
