//MACRO     HeapSort    BaseAddr,   Size,   RecSize{integer}, CompMacro,  WReg[9-32]
//--------------------------------------------------------------------------------------------------
//
//  @ CopyRight Roberti & Parau Enterprises, Inc.  2021-2023
//
//  This work is licensed under the Creative Commons Attribution-NoDerivatives 4.0 International License.
//  To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/4.0/
//   or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.
//
//--------------------------------------------------------------------------------------------------
// 
    //
    //  Check Record Size - it can only be 32 or 64
    //
    if (RecSize !== 32 && RecSize !== 64)
        DVASM.putError("Third parameter [RecSize] for macro HEAPSORT must be " +
            "either [32] or [64]\nIt is [" + RecSize + "]");
    
    //
    //  Set up control variables
    //
    var recShift
    var load;
    var store;
    RecSize/= 8;
    if (RecSize == 4) {
        recShift= 2;
        load= "LW";
        store= "SW";
    }
    else {
        recShift= 3;
        load= "LD";
        store= "SD";
    }
    
    //
    //  Set up register variables
    //
    var endAddr= WReg[0];
    var recAddr= WReg[1];
    var rec= WReg[2];
    var recOff= WReg[3]
    var parentAddr= WReg[4]
    var childOff= WReg[5]
    var childAddr= WReg[6];
    var child= WReg[7];
    var childNext= WReg[8];

    var compareWReg= "[" + WReg.slice(9) + "]";
    
\//
\//  Registers used by macro by default or as specified by user
\//
\//  #BaseAddr  -  address of buffer
\//  #Size  -  number of records in buffer
\//
\//  #endAddr  -  end address of buffer
\//  #recAddr  -  end address of record being sorted
\//  #rec  -  content of record being sorted
\//  #recOff  -  end offset of record being sorted
\//  #parentAddr  -  end address of parent record when adjusting heap
\//  #childOff  -  end offset of parent left child
\//  #childAddr  -  end address of parent left child
\//  #child  -  content of parent left child
\//  #childNext  -  content of parent right child
    
    //
    //  Generate code to create heap
    //
    var oneChild= DVASM.getNewLabel();
    var done= DVASM.getNewLabel();
    
\//
\//  Code to create the heap
\//
\#Label		SLLI    	#recOff, #recShift[#Size]			// Get buffer Size
\			ADD     	#endAddr, #recOff, #BaseAddr		// Get last record end addr
\			SRLI    	#recOff, 1							// Get mid-record end offset
\			ADD     	#recAddr, #recOff, #BaseAddr		// Get mid-record end addr
\			WHILE   	Condition= ( #recAddr > #BaseAddr ),	/> Start heap build main loop
\			        		RepeatCode= [!"ADDI        #recAddr, -#RecSize",	/>
\			        		            !"ADDI        #recOff, -#RecSize"]
\				#load    	#rec, -#RecSize[#recAddr]		// Load record
\				MV      	#parentAddr, #recAddr           // Copy rec addr as parent addr
\				SLLI    	#childOff, 1[#recOff]           // Get child end offset
\				ADD     	#childAddr, #childOff, #BaseAddr		// Get child end addr
\				WHILE   	Condition= ( #childAddr <= #endAddr ),	/> Get child end addr
\				        		RepeatCode= [!"SLLI        #childOff, 1",						/> Get new child offset
\				        		            !"ADD         #childAddr, #childOff, #BaseAddr"]	// Get new child addr
\					#load      	#child, -#RecSize[#childAddr]	// Load child
\					IF      	( #childAddr >= #endAddr ), GOTO, Id= #oneChild		// Check if next child
\					#load      	#childNext, 0[#childAddr]	// Load child next
\					#CompMacro 	#childNext, #child, false, #oneChild, #compareWReg	// Check which child is max
\					
\					#CompMacro 	#childNext, #rec, true, #done, #compareWReg	// Check if rec is max
\					#store     	#childNext, -#RecSize[#parentAddr]	// Move next child up
\					ADDI    	#parentAddr, #RecSize[#childAddr]	// Next child become parent
\					ADDI    	#childOff, #RecSize         // Get next child offset
\					CONTINUE
\#oneChild			#CompMacro  #child, #rec, true, #done, #compareWReg	// Check child with rec
\					#store    	#child, -#RecSize[#parentAddr]	// Move next child up
\					MV      	#parentAddr, #childAddr		// Child become parent
\					ENDWHILE
\#done			#store    #rec, -#RecSize[#parentAddr]
\				ENDWHILE
    
    //
    //  Generate the code to sort
    //
    oneChild= DVASM.getNewLabel();
    done= DVASM.getNewLabel();
    
\//
\//  Code to sort
\// 
\			ADDI    	#endAddr, -#RecSize               	// Reduce heap Size by one
\			WHILE 		Condition= ( #endAddr > #BaseAddr  ), 	/> Start sort main loop
\							RepeatCode= [!"ADDI        #endAddr,-#RecSize"]
\				ADDI    	#recOff, #RecSize[0]            	// Get starting record end offset
\				ADDI    	#recAddr, #RecSize[#BaseAddr]       // Get starting record end addr
\				#load      	#rec, 0[#endAddr]               	// Load record
\				#load      	#child, 0[#BaseAddr]            	// Get firt record in heap - last in sort order
\				#store     	#child, 0[#endAddr]             	// Store at the end of the heap
\				MV      	#parentAddr, #recAddr             	// Copy rec addr as parent addr
\				SLLI    	#childOff, 1[#recOff]           	// Get child end offset
\				ADD     	#childAddr, #childOff, #BaseAddr	// Get child end addr
\				WHILE		Condition= ( #childAddr <= #endAddr ),							/> Get child end addr
\							RepeatCode= [!"SLLI        #childOff, 1",						/> Get new child offset
\						            	!"ADD         #childAddr, #childOff, #BaseAddr"]	// Get new child addr
\					#load      	#child, -#RecSize[#childAddr]		// Load child
\					IF			( #childAddr >= #endAddr ), GOTO, Id= #oneChild		// Check if next child
\					#load      	#childNext, 0[#childAddr]			// Load child next
\					#CompMacro 	#childNext, #child, false, #oneChild, #compareWReg	// Check which child is max
\					#CompMacro 	#childNext, #rec, true, #done, #compareWReg	// Check if rec is max
\					#store      #childNext, -#RecSize[#parentAddr]	// Move next child up
\					ADDI      	#parentAddr, #RecSize[#childAddr]	// Next child become parent
\					ADDI      	#childOff, #RecSize					// Get next child offset
\					CONTINUE
\#oneChild  		#CompMacro  #child, #rec, true, #done, #compareWReg	// Check child with rec
\					#store      #child, -#RecSize[#parentAddr]		// Move next child up
\					MV         	#parentAddr, #childAddr				// Child become parent
\					ENDWHILE
\#done  		#store     	#rec, -#RecSize[#parentAddr]			// Save record in current child
\				ENDWHILE