#!/bin/bash 
# copyright 2007 Gilbert Ashley <amigo@ibiblio.org>
# BashTrix sort is an implementation of the 'sort' command
# written in pure shell. Very few sort options are supported.
# It's based on the combsort algorithm and was originally
# written in BASH by Carl McNealy as a numerical sorter.
VERSION=0.2

ERROR=0
# show program usage
show_usage() {
echo "Usage: ${0##/*} [OPTION]... [FILE]..."
echo "Try '${0##/*} --help' for more information."
exit $ERROR
}

# show program help
show_help() {
echo
echo "Usage: ${0##/*} [OPTION]... [FILE]..."
echo "  or: (cat|echo) | ${0##/*} [OPTION]..."
echo "Sort lines of each FILE and print the result to standard output."
echo "With no FILE, read standard input."
echo "  -r  --reverse  	reverse the final output order"
echo "  -n  --numeric-sort	use numeric sort"
echo "  -u  --unique	output only the first of two equal lines."
echo "      --help     	display this help and exit"
echo "      --version  	output version information and exit"
exit $ERROR
}

show_version() {
echo ${0##/*}" (BashTrix) $VERSION"
echo "Copyright 2007 Gilbert Ashley <amigo@ibiblio.org>"
echo "This is free software written in pure shell."
exit $ERROR
}

# get the - options DUMMY
for WORD in "$@" ; do
	case $WORD in
		-*)  true ;
			case $WORD in
				-r|--reverse) REVERSE_RESULTS=1 ; shift ;;
				-n) NUMERIC_SORT=1 ; shift ;;
				-u) UNIQUE_LINES=1 ; shift ;;
				--help) show_help ;;
				--version) show_version ;;
				-) READ_STDIN=1 ; shift ;;
			esac
		;;
	esac
done

# sorting functions
function  newGap() {
typeset -i newgap
newgap=($1*10)
newgap=$newgap/13
if [[ $newgap -eq 9 || $newgap -eq 10 ]] ; then
	newgap=11
elif [[ $newgap -lt 1 ]] ; then 
	newgap=1
fi
return $newgap
}

function swap_lines() {
temp=${LINE[$1]}
LINE[$1]=${LINE[$2]}
LINE[$2]=$temp
}

function sort_alpha() {
let aSize=$FILE_LINE_COUNT
let gap=$aSize

while(true) ; do    
	newGap $gap
	gap=$?
	let swapped=0
	let i=0
	let diff=$aSize-$gap
	while(true) ; do
		if [[ $i -ge $diff ]] ; then
		break
		fi
		let j=$i+$gap
		if [[ "${LINE[$i]}" > "${LINE[$j]}" ]] ; then
			swap_lines $i $j
			let swapped=1
		fi
		let i=i+1
	done
	#echo "gap=$gap"
	if [[ $gap -eq 1 && $swapped -eq 0 ]] ; then
		break 1
	fi
done

}


function sort_numeric() {
# resort to a pure bubble sort for this with a gap of 1
# we have presorted using alpha sorting so we know
# that the numbers are at the top. Non-numeric lines are ignored this time
let aSize=$FILE_LINE_COUNT
let gap=$aSize

while(true) ; do    
	gap=1
	let swapped=0
	let i=0
	let diff=$aSize-$gap
	while(true) ; do
		if [[ $i -ge $diff ]] ; then
		break
		fi
		let j=$i+1
		if IsNumeric "${LINE[$i]}" && IsNumeric "${LINE[$j]}" ; then
			#echo 1:${LINE[$i]}
			#echo 2:${LINE[$j]}
			#exit
			if [ ${LINE[$i]} -gt ${LINE[$j]} ] ; then
				swap_lines $i $j
				let swapped=1
			fi
		fi
		let i=i+1
	done
	#echo "gap=$gap"
	if [[ $gap -eq 1 && $swapped -eq 0 ]] ; then
		break 1
	fi
done
}

IsNumeric() {
     if [ $# -ne 1 ]; then
          return 1
     fi
     expr "$1" + 1 >/dev/null 2>&1
     if [ $? -ge 2 ]; then
          return 1
     fi
     return 0
}

# output function takes care of reverse and unique switches
function output_results() {
# print the lines in reverse order
if [[ $REVERSE_RESULTS ]] ; then
	while [[ ${FILE_LINE_COUNT} -gt 0 ]] ; do
		# this is a spot where line numbers or or other data could be inserted (paste, join, fold)
		if [[ $UNIQUE_LINES ]] ; then
			NEXT_LINE=$(( $FILE_LINE_COUNT - 1 ))
			if [[ "${LINE[$FILE_LINE_COUNT]}" = "${LINE[$NEXT_LINE]}" ]] ; then
				echo ${LINE[$FILE_LINE_COUNT]}
				unset LINE[$NEXT_LINE]
				FILE_LINE_COUNT=$(( $FILE_LINE_COUNT - 2 ))
			else
				echo ${LINE[$FILE_LINE_COUNT]}
				(( FILE_LINE_COUNT-- ))
			fi
		else
		echo ${LINE[$FILE_LINE_COUNT]}
			(( FILE_LINE_COUNT-- ))
		fi
	done
else
	# print the lines in foward order
	FILE_LINE_COUNT=0
	while [[ ${FILE_LINE_COUNT} -lt ${aSize} ]] ; do
		if [[ $UNIQUE_LINES ]] ; then
			NEXT_LINE=$(( $FILE_LINE_COUNT + 1 ))
			if [[ "${LINE[$FILE_LINE_COUNT]}" = "${LINE[$NEXT_LINE]}" ]] ; then
				echo ${LINE[$FILE_LINE_COUNT]}
				unset LINE[$NEXT_LINE]
				FILE_LINE_COUNT=$(( $FILE_LINE_COUNT + 2 ))
			else
				echo ${LINE[$FILE_LINE_COUNT]}
				(( FILE_LINE_COUNT++ ))
			fi
		else
			echo ${LINE[$FILE_LINE_COUNT]}
			(( FILE_LINE_COUNT++ ))
		fi
	done
fi
}


if [[ $# -gt 0 ]] ; then
	while [[ $# -gt 0 ]] ; do
		FILE_NAME="$1"
		if [ ! -r "$1" ] ; then
			echo "Cannot find file $1" 1>&2
			exit 1
		else
			# read the lines of the file into an array LINE[$FILE_LINE_COUNT]
			FILE_LINE_COUNT=1
			LINE=
			IFS=$'\n'
			while read LINE ; do
				#(( FILE_LINE_COUNT++ ))
				declare -a LINE[$FILE_LINE_COUNT]=$LINE
				(( FILE_LINE_COUNT++ ))
			done <"$1"
		fi
		# do the sorting
		sort_alpha
		if [[ $NUMERIC_SORT ]] ; then
			sort_numeric
		fi
		# process and show the ouput from this file
		output_results
		# go to next FILE in $@
		shift
	done
else
	# piped input is presumed to be separated into lines already
	FILE_NAME="STDIN"
	# read the lines from stdin into an array LINE[$FILE_LINE_COUNT]
	FILE_LINE_COUNT=0
	LINE=
	IFS=
	while read LINE ; do
		# add the curent line to the line counter
		(( FILE_LINE_COUNT++ ))
		declare LINE[$FILE_LINE_COUNT]=$LINE
	done
	# do the sorting
	sort_alpha
	# process and show the output
	output_results
fi