#!/usr/bin/ksh93

########################################################################
#                                                                      #
#               This software is part of the ast package               #
#                 Copyright (c) 2006-2012 Roland Mainz                 #
#                      and is licensed under the                       #
#                 Eclipse Public License, Version 1.0                  #
#                    by AT&T Intellectual Property                     #
#                                                                      #
#                A copy of the License is available at                 #
#          http://www.eclipse.org/org/documents/epl-v10.html           #
#         (with md5 checksum b35adb5213ca9657e911e9befb180842)         #
#                                                                      #
#                                                                      #
#                 Roland Mainz <roland.mainz@nrubsig.org>              #
#                                                                      #
########################################################################

#
# Copyright (c) 2006, 2012, Roland Mainz. All rights reserved.
#

#
# Written by Roland Mainz <roland.mainz@nrubsig.org>
#

#
# numtree1 - basic compound variable tree demo+benchmark
#

# Solaris needs /usr/xpg6/bin:/usr/xpg4/bin because the tools in /usr/bin are not POSIX-conformant
export PATH='/usr/xpg6/bin:/usr/xpg4/bin:/bin:/usr/bin'

# Make sure all math stuff runs in the "C" locale to avoid problems
# with alternative # radix point representations (e.g. ',' instead of
# '.' in de_DE.*-locales). This needs to be set _before_ any
# floating-point constants are defined in this script).
if [[ "${LC_ALL-}" != '' ]] ; then
	export \
		LC_MONETARY="${LC_ALL}" \
		LC_MESSAGES="${LC_ALL}" \
		LC_COLLATE="${LC_ALL}" \
		LC_CTYPE="${LC_ALL}"
		unset LC_ALL
fi
export LC_NUMERIC='C'


function fatal_error
{
	print -u2 -n "${progname}: "
	print -u2 -f "$@"
	exit 1
}

# floating-point version of "seq"
function floatseq
{
	float i
	nameref ar=$1
	integer ar_i=0
	
	shift
	float arg1=$1
	float arg2=$2
	float arg3=$3

	case $# in
		1)
			for (( i=1. ; i <= arg1 ; i=i+1. )) ; do
				(( ar[ar_i++]=i ))
			done
			;;
		2)
			for (( i=arg1 ; i <= arg2 ; i=i+1. )) ; do
				(( ar[ar_i++]=i ))
			done
			;;
		3)
			for (( i=arg1 ; i <= arg3 ; i+=arg2 )) ; do
				(( ar[ar_i++]=i ))
			done
			;;
		*)
			print -u2 -f $"%s: Illegal number of arguments %d\n" "$0" "$#"
			return 1
			;;
	esac
	
	return 0
}

# convert numberto an indexed array of path elements, one element per digit
function num_to_pathelements
{
	nameref pe=$1 # out: array of element names
	nameref num=$2 # in: number (passed as reference for performance)
	integer len

	typeset numstr=$num
	# We need to safeguard log10(num) with fmax() since log10() returns -inf for 0
	for (( len=round(log10(fmax(num, 1))+0.5) , i=len ; i > 0 ; i-- )) ; do
        	pe+=( ${numstr:len-i:1} )
	done
	
	(( ${#pe[@]} == ${#numstr} )) || fatal_error $"Assertion %d, %q == %q failed.\n" "${mode}" "${#pe[@]}" "${#numstr}"

	return 0
}

function add_number_to_tree
{
	nameref treename=$1 # in: tree where we insert the element
	nameref num=$2 # in: number to insert (passed as reference for performance)
	integer i
	typeset nodepath # full name of compound variable
	integer -a pe # path elements

	num_to_pathelements pe num

	# walk path described via the "pe" array and build nodes if
	# there aren't any nodes yet
	nodepath='treename'
	for (( i=0 ; i < ${#pe[@]} ; i++ )) ; do
		nameref x="${nodepath}"
		
		# [[ -v ]] does not work for arrays because [[ -v ar ]]
		# is equal to [[ -v ar[0] ]]. In this case we can
		# use the output of typeset +p x.nodes
		[[ "${ typeset +p x.nodes ; }" == '' ]] && compound -a x.nodes
		
		nodepath+=".nodes[${pe[i]}]"
	done
	
	# insert element (leaf)
	nameref node="${nodepath}"
	[[ "${ typeset +p node.elements ;}" == '' ]] && integer -a node.elements
	node.elements+=( num )

	# In theory this is DEBUG only, but we keep it because the statements
	# below are common for tree operations and make the benchmark more
	# behave like real world applications
	[[ "${!node.elements[*]}" != ''                                 ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	[[ "${ typeset +p node.elements ; }" == ~(Alr)(.*-a.*)&(.*-i.*) ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	[[ -v node                                                      ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	[[ -R node                                                      ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	[[ "${ typeset +p ${nodepath} ; }" == *-C*                      ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	[[ "${!x.nodes[*]}" != ''                                       ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	[[ "${ typeset +p x.nodes ; }" == ~(Alr)(.*-a.*)&(.*-C.*)       ]] || fatal_error $"assertion %d FAILED.\n" "${LINENO}"
	
	return 0
}

function usage
{
	OPTIND=0
	getopts -a "${progname}" "${numtree1_usage}" OPT '-?'
	exit 2
}

function main
{
	compound base
	compound bench=(
		float start
		float stop
	)
	integer i

	while getopts -a "${progname}" "${numtree1_usage}" OPT ; do 
		case "${OPT}" in
			*) usage ;;
		esac
	done
	shift $(( OPTIND-1 ))
	
	# prechecks
	(( $# > 0 )) || usage
	
	cmd="${1}"
	shift

	# Read numbers from stdin outside benchmark loop
	if [[ "${cmd}" == 'stdin' ]] ; then
		# we use "cat" and not "$( <'/dev/stdin' )" here to get correct error handling 
		integer -r -a in_numbers=( $( cat '/dev/stdin' ) ) || fatal_error $"stdin read error.\n"
	elif [[ "${cmd}" == 'seq' ]] ; then
		integer -a in_numbers
		floatseq in_numbers "$@" || fatal_error $"seq error.\n"
	fi
	
	[[ -v in_numbers[0] ]] && print -u2 -f '# numnodes=%d\n' ${#in_numbers[@]}
	
	(( bench.start=SECONDS ))
	
	case "${cmd}" in
		'stdin' | 'seq')
			for (( i=0 ; i < ${#in_numbers[@]} ; i++ )) do
				add_number_to_tree base in_numbers[$i]
			done
			;;
		'demo1')
			for i in 1 32 33 34 34 38 90 ; do
				add_number_to_tree base i
			done
			;;
		'demo2')
			for (( i=1000000000 ; i < 1000000000+10 ; i++ )) ; do
				add_number_to_tree base i
			done
			;;
		*)
			print -u2 -f $"%s: Invalid command %s.\n" "${progname}" "${cmd}"
			return 1
			;;
	esac
	
	(( bench.stop=SECONDS ))
	
	print -u2 -f $"# time used: %f\n" '(bench.stop - bench.start)'
	
	# print tree
	print -v base
	
	return 0
}

# main
builtin basename

set -o noglob
set -o errexit
set -o nounset

typeset progname="${ basename "${0}" ; }"

typeset -r numtree1_usage=$'+
[-?\n@(#)\$Id: numtree1 (Roland Mainz) 2010-09-04 \$\n]
[-author?Roland Mainz <roland.mainz@nrubsig.org>]
[+NAME?numtree1 - generate sorted variable tree containing numbers]
[+DESCRIPTION?\bnumtree1\b is a simple variable tree generator which
	sorts a given set of numbers into a ksh compound variable tree).
	the application supports two different modes: \'seq\' takes
	1-3 arguments to specify the set of numbers via seq(1) and
	\'stdin\' reads the numbers from stdin (one per line).]

method [ arguments ]

[+SEE ALSO?\bksh93\b(1), \bseq\b(1)]
'

main "$@"
exit $?

# EOF.