$include (..\lib\compStch.ext)

/*
 *============================================================================
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE
 *
 *  Permission to use for any purpose, modify, copy, and make enhancements
 *  and derivative works of the software is granted if attribution is given to
 *  R.M. Gillmore, dba the ACME Software Deli, as the author
 *
 *  While the ACME Software Deli does not work for money, there is nonetheless
 *  a significant amount of work involved.  The ACME Software Deli maintains the
 *  rights to all code written, though it may be used and distributed as long as
 *  the following conditions are maintained.
 *
 *  1.  The copyright statement at the top of each code block is maintained in
 *      your distribution.
 *  2.  You do not identify yourself as the ACME Software Deli
 *  3.  Any changes made to the software are sent to the ACME Software Deli
 *============================================================================
 */


sortModule:
do;
$if not noID
declare IDString	(*) byte data
	( '@(#)sort.p86      $Author: rmgillmore $ $Date:: 2025-05-04 19:35:39#$:', 0 );
$endif

/*
 *	there are 4 parameters required:
 *		basePtr     	- this is the address of the first element in the array
 *		numberElements	- this is the number of elements in the array
 *		elementSize		- how large is each element in the array (number of bytes)
 *		compareFuncPtr	- the address of the function that will be called when
 *						  a comparison is needed.
 *
 *	the signature for the comparison method is:
 *		compareFunc: procedure( left, right, compareResultsPtr );
 *			declare	( left, right )	<the appropriate size of each element>,
 *					compareResultsPtr	pointer,
 *					compareResults Based compareResultsPtr	Integer;
 *
 *			compareResults:  0 if the elements are identical, non-zero if not identical
 *
 */

/* NOT reentrant because it has nested procedures */

sort:
procedure( basePtr, numberElements, elementSize, compareFuncPtr ) public;
	declare basePtr						pointer,
			numberElements				word,
			elementSize					word,
			compareFuncPtr				word;

	declare results						integer,	/* returned status */
			iHole						integer,	/* secondary index */
			i							integer;	/* index */

	/*
	 *	Suppose A is an array of N values. We want to sort A in ascending order.
	 *
	 *	Insertion Sort is an algorithm to do this as follows:
	 *		We traverse the array and insert each element into the sorted
	 *		part of the list where it belongs. This usually involves pushing
	 *		down the larger elements in the sorted part.
	 */

	declare sortTemplate literally '
		sortTemplateLoop:
		do i = 1 to n-1;
			item = a(i);
			iHole = i;
			call compareFuncPtr( @a( iHole - 1 ), @item, @results );
			doWhile:
			do while ( iHole > 0 ) and ( results <> 0 );
				a( iHole ) = a( iHole - 1 );
				iHole = iHole - 1;
				if ( iHole > 0 ) then
					call compareFuncPtr( @a( iHole - 1 ), @item, @results );
			end doWhile;
			a( iHole ) = item;
		end sortTemplateLoop';		/* end sortTemplate literal */

	sortBytes:	procedure( basePtr, numberElements, compareFuncPtr );
		declare basePtr					pointer,
				numberElements			word,
				compareFuncPtr			word;

		declare	a 						based basePtr ( * )	byte,
				item					byte,	/* temporary variable */
				n						word;	/* numberElements */

		n = numberElements;
		sortTemplate;
	end sortBytes;

	sortWords:	procedure( basePtr, numberElements, compareFuncPtr );
		declare basePtr					pointer,
				numberElements			word,
				compareFuncPtr			word;

		declare	a 						based basePtr ( * )	word,
				item					word,	/* temporary variable */
				n						word;	/* numberElements */

		n = numberElements;
		sortTemplate;
	end sortWords;

	sortDwords:	procedure( basePtr, numberElements, compareFuncPtr );
		declare basePtr					pointer,
				numberElements			word,
				compareFuncPtr			word;

		declare	a 						based basePtr ( * )	dword,
				item					dword,	/* temporary variable */
				n						word;	/* numberElements */

		n = numberElements;
		sortTemplate;
	end sortDwords;

	do;
		declare	byteVar					byte,
				wordVar					word,
				dwordVar				dword;

		if ( elementSize = size( byteVar ) ) then
			call sortbytes( basePtr, numberElements, compareFuncPtr );
		else if ( elementSize = size( wordVar ) ) then
			call sortwords( basePtr, numberElements, compareFuncPtr );
		else if ( elementSize = size( dwordVar ) ) then
			call sortdwords( basePtr, numberElements, compareFuncPtr );
	end;
end sort;

end sortModule;