#!/bin/bash
# qsort - Pure Bash QSort Support

set -e

######
# Library Configuration

core_qsort_config_init() {
	# $qsort_compare_func - Name of function to use for comparing
	# two items.  See the `Comparison Functions`_ section for
	# more information and built-in options.
	lib_setting_vars qsort_compare_func
	qsort_compare_func=compare_str_asc
}

######
# Internal functions

qsort_stack_push() { qsort_stack+=( "$@" ); }
qsort_stack_pop() { qsort_stack=( "${qsort_stack[@]:2}" ); }


######
# Public interface

# qsort() - Sorts items ($@) into the named array ($1) using
# the original qsort algorithm.
# $1 - Array to receive sorted items
# $@ - Items to sort
qsort() {
	min_args 1 "$@"
	local result=$1
	shift

	[ $# -gt 0 ] || return 0

	local -a sorted=( "$@" )

	local -a qsort_stack
	local last=$(($# - 1))
	qsort_stack_push 0 $last

	local -a smaller larger
	while (( ${#qsort_stack[@]} )); do
		local a=${qsort_stack[0]}
		local b=${qsort_stack[1]}
		qsort_stack_pop

		local pivot=${sorted[$a]}

		local i
		smaller=()
		larger=()
		for ((i = a + 1; i <= b; i++)); do
			local value="${sorted[i]}"
			local name
			$qsort_compare_func "$value" "$pivot" \
				&& smaller+=( $value ) \
				|| larger+=( $value )
		done

		sorted=( \
			"${sorted[@]:0:a}" \
			"${smaller[@]}" "$pivot" "${larger[@]}" \
			"${sorted[@]:b + 1:last - b}" \
			)

		if ((${#smaller[@]} >= 2)); then
			qsort_stack_push $a $((a + ${#smaller[@]} - 1))
		fi
		if ((${#larger[@]} >= 2)); then
			qsort_stack_push $((b - ${#larger[@]} + 1)) $b
		fi
	done
	eval "$result=( \"\${sorted[@]}\" )"
}

# qsort_list() - Sorts the named list ($1) in place using ``qsort()``.
qsort_list() {
	has_args 1 "$@"
	eval "qsort $1 \"\${$1[@]}\""
}


######
# Comparison Functions
#
# The functions in this section are meant to be used as
# ``$qsort_compare_func``.  They each take two arguments:
#   $1 - First item to compare
#   $2 - Second item to compare
# Returns: Success if the two items are in the correct order.

# compare_str_asc() - Sorts strings in ascending order
compare_str_asc() { [[ "$1" < "$2" ]]; }

# compare_str_asc() - Sorts strings in descending order
compare_str_dsc() { [[ "$1" > "$2" ]]; }

# compare_int_asc() - Sorts integers in ascending order
compare_int_asc() { (("$1" < "$2")); }

# compare_int_dsc() - Sorts integers in descending order
compare_int_dsc() { (("$1" > "$2")); }

# compare_int_asc() - Sorts files by modification time in chronological order.
compare_mtime_asc() { [[ $1 -ot $2 ]]; }

# compare_int_dsc() - Sorts files by modification timein reverse
# chronological order .
compare_mtime_dsc() { [[ $1 -nt $2 ]]; }