//MACRO     Avl.__balnc     Type,   Anchor,     PFld,   FieldDispl, WReg[7]
//--------------------------------------------------------------------------------------------------
//
//  @ 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.
//
//--------------------------------------------------------------------------------------------------
//
    //
    //  Get load/store MIs and word length
    //
    eval(DVASM.getEnv()[5]);
    var ld= "L" + abiWID;
    var st= "S" + abiWID;
    var wl= abiWLen;

    var leftField= FieldDispl;
    var parentField= wl + "+" + FieldDispl;
    var rightField= wl*2 + "+" + FieldDispl;
    var complRotLabel= DVASM.getNewLabel();

    //
    //  Validate Type and WReg parameters
    //
    Type= Type.toUpperCase();
    var typeNdx= ["INSERT", "REMOVE"].indexOf(Type);
    if (typeNdx < 0)
        return DVASM.putError("Positional parameter Type [%s] is invalid", Type.toUpperCase());

    var balAddSub= ["ADD", "SUB"][typeNdx];

    var pFld= PFld;

    var bNode= WReg[0];
    var aNode= WReg[1];
    var cNode= WReg[2];
    var tmp0= WReg[3];
    var tmp1= WReg[4];
    var tmp2= WReg[5];
    var tmp3= WReg[6];
    var balance= WReg[6];

\           //
\           // Balance the tree
\           //
\#Label     AVL.__EXTPA #aNode, #pFld                       // Set up parent addr for WHILE loop
\
\           DO                                              // Start balance loop
\               AVL.__EXTLT #tmp0, #pFld                        // Extract link type from parent
\               SRLI        #tmp0, 1                            // Convert link type
\               ADDI        #tmp0, -1                           // ... to +/- 1 to be subtracted from balance
\               #ld         #pFld, #parentField[#aNode]         // Get parent field
\               AVL.__EXTBL #balance, #pFld                     // Get balance of parent of deleted node
\               #balAddSub      #balance, #tmp0                 // Add (insert) Subtract (remove) link for new balance
\
\               //
\               //  Check if left rotation
\               //
\               LI          #tmp0, 1                            // Load compare constant
\           	IF          ( #balance > #tmp0 ), THEN          // Handle left substree too high
\               	#ld         #bNode, #leftField[#aNode]          // Load B node addr
\               	#ld         #cNode, #rightField[#bNode]         // Get C node addr
\               	#ld         #tmp3, #parentField[#bNode]         // get B node parent field
\               	AVL.__EXTBL #tmp3, #tmp3                        // Get B node balance
\
\                   //
\                   //  LL rotation - Top node is A, left child is B, right child of B node is C node if any
\                   //
\               	IF          ( #tmp3 >= 0 ), THEN                // LL rotation if >= 0
\               		#st         #cNode, #leftField[#aNode]           // Make C node right child  of A node
\               		IF          ( #cNode != 0 ), THEN               // Check if C node exists
\               			#ld         #tmp0, #parentField[#cNode]          // Get parent field of C node
\               			AVL.__SETPA #cNode, #tmp0, #tmp0, #aNode,, LEFT, CLEAR, #parentField // Set C node parent to A node - left link
\               			ENDIF

    //
    //  Code is slightly different between insert and remove - when insert balance for B cannot be zero
    //
    if (Type === "INSERT") {
\               		AVL.__SETPA #aNode, #tmp0, #bNode,, EVEN, RIGHT, NOCLEAR, #parentField // Set balance even - right link for A node
\               		AVL.__SETPA #bNode, #pFld, #pFld,, EVEN,, CLEAR, #parentField // Set balance even - A node parent for B node
    }
    else {
\               		IF          ( #tmp3 != 0 ), THEN                // Check if B node balance is not even
\                   		AVL.__SETPA #aNode, #tmp0,  #bNode,, EVEN, RIGHT, NOCLEAR, #parentField // Set balance even - right link for A node
\                   		AVL.__SETPA #bNode, #pFld,  #pFld,, EVEN,, CLEAR, #parentField // Set balance even - A node parent for B node
\               		<ELSE
\                   		AVL.__SETPA #aNode, #tmp0,  #bNode,, PLUS, RIGHT, NOCLEAR, #parentField // Set balance plus - right link for A node
\                   		AVL.__SETPA #bNode, #pFld,  #pFld,, MINUS,, CLEAR, #parentField // Set balance minus for A node
\                   		ENDIF
    }

\               		#st         #aNode, #rightField[#bNode]         // Set A node as right child of B node
\               		MV          #aNode, #bNode                      // Copy B node addr for rotation completion code
\               		GOTO        #complRotLabel                      // Execute rotation completion code
\               		ENDIF
\
\               	//
\               	//  LR Rotation - Top node is A, left child is B, its right child is C
\               	//
\               	#ld         #tmp0, #parentField[#cNode]         // Get parent field from C node
\
\	             	AVL.__EXTBL #tmp0, #tmp0                        // Get balance of C node
\
\	             	IF          ( #tmp0 == 0 ), THEN                // Check if C node balance is even
\	                 	AVL.__SETPA , #tmp1, #cNode,, EVEN, LEFT, NOCLEAR, #parentField // Set B node parent even/left
\                   	AVL.__SETPA , #tmp2, #cNode,, EVEN, RIGHT, NOCLEAR, #parentField // Set A node parent even/right
\               	<ELSEIF     ( #tmp0 > 0 )                       // Check if C node balance is high on left
\                   	AVL.__SETPA , #tmp1, #cNode,, EVEN, LEFT, NOCLEAR, #parentField // Set B node parent even/left
\                   	AVL.__SETPA , #tmp2, #cNode,, MINUS, RIGHT, NOCLEAR, #parentField // Set A node parent minus/right
\               	<ELSE                                           // Balance is high on right
\                   	AVL.__SETPA , #tmp1, #cNode,, PLUS, LEFT, NOCLEAR, #parentField // Set B node parent plus/left
\                   	AVL.__SETPA , #tmp2, #cNode,, EVEN, RIGHT, NOCLEAR, #parentField // Set A node parent even/right
\                   	ENDIF
\
\               	#st         #tmp1, #parentField[#bNode]         // Store B node parent field
\               	#st         #tmp2, #parentField[#aNode]         // Store A node parent field
\
\               	#ld         #tmp0, #leftField[#cNode]           // Get left child of C node
\               	#st         #tmp0, #rightField[#bNode]          // Store it as right child of B node
\               	IF          ( #tmp0 != 0 ), THEN                // Check if C node left child exists
\                   	#ld         #tmp1, #parentField[#tmp0]           // Get C node left child parent field
\                   	AVL.__SETPA #tmp0, #tmp1, #tmp1, #bNode,, RIGHT, CLEAR, #parentField // Set C node child parent to B node - right link
\                   	ENDIF
\
\               	#ld         #tmp0, #rightField[#cNode]          // get right child of C node
\               	#st         #tmp0, #leftField[#aNode]           // Store it as left child of A node
\               	IF          ( #tmp0 != 0 ), THEN                // Check if node exists
\                   	#ld         #tmp1, #parentField[#tmp0]           // Get C node right child parent field
\                   	AVL.__SETPA #tmp0, #tmp1, #tmp1, #aNode,, LEFT, CLEAR, #parentField // Set C node child parent to B node - right link
\                   	ENDIF
\               	#st         #bNode, #leftField[#cNode]          // Set B node as left child of C node
\               	#st         #aNode, #rightField[#cNode]         // Set A node as right child of C node
\
\               	AVL.__SETPA #cNode, #pFld, #pFld,, EVEN,, CLEAR, #parentField // Store A node parent in C node parnent field - even balance
\               	MV          #aNode, #cNode                      // Copy C node addr
\               	GOTO        #complRotLabel                      // Execute rotation completion code
\
\           	//
\           	//  Check if right rotation
\           	//
\				<ELSEIF		( #balance < #tmp0 ), Precode= [!"LI			#tmp0, -1"]
\																// Handle right substree too high
\               	#ld         #bNode, #rightField[#aNode]         // Load B node addr
\               	#ld         #cNode, #leftField[#bNode]         	// Get C node addr
\               	#ld         #tmp3, #parentField[#bNode]         // get B node parent field
\               	AVL.__EXTBL #tmp3, #tmp3                        // Get B node balance
\
\               	//
\               	// RR Rotation - Top node is A, left child is B, its right child is C if it exists
\               	//
\               	IF       ( #tmp3 <= 0 ), THEN                   // Check if RR rotation
\                   	#st         #cNode, #rightField[#aNode]         // Make B node left child new right child A node
\                   	IF          ( #cNode != 0 ), THEN
\                       	#ld         #tmp0, #parentField[#cNode]         // Get parent field of C node
\                       	AVL.__SETPA #cNode, #tmp0, #tmp0, #aNode,, RIGHT, CLEAR, #parentField // Set C node parent to A node - right link
\                       	ENDIF

    //
    //  Code is slightly different between insert and remove - when insert balance for B node cannot be zero
    //
    if (Type === "INSERT") {
\                   	AVL.__SETPA #aNode, #tmp0, #bNode,, EVEN, LEFT, NOCLEAR, #parentField // Set balance even - right link for A node
\                   	AVL.__SETPA #bNode, #pFld, #pFld,, EVEN,, CLEAR, #parentField // Set balance even - A node parent for B node
    }
    else {
\                   	IF          ( #tmp3 != 0 ), THEN                // Check if B node balance is not even
\                       	AVL.__SETPA #aNode, #tmp0,  #bNode,, EVEN, LEFT, NOCLEAR, #parentField // Set balance even - right link for A node
\                       	AVL.__SETPA #bNode, #pFld,  #pFld,, EVEN,, CLEAR, #parentField // Set balance even - A node parent for B node
\                   	<ELSE
\                       	AVL.__SETPA #aNode, #tmp0,  #bNode,, MINUS, LEFT, NOCLEAR, #parentField // Set balance plus - right link for A node
\                       	AVL.__SETPA #bNode, #pFld,  #pFld,, PLUS,, CLEAR, #parentField // Set balance minus for A node
\                       	ENDIF
    }

\                   	#st         #aNode, #leftField[#bNode]          // Set left child of B node
\    
\                   	MV       #aNode, #bNode                         // Copy B node addr
\                   	GOTO     #complRotLabel                         // Execute rotation completion code
\                   	ENDIF
\    
\               	//
\               	// RL Rotation - Top node is A, right child is B, its left child is C
\               	//
\               	#ld         #tmp0, #parentField[#cNode]         // Get parent field from C node
\               	AVL.__EXTBL #tmp0, #tmp0                        // Get balance of C node
\    
\               	IF          ( #tmp0 == 0 ), THEN                // Check if C node balance is even
\                   	AVL.__SETPA , #tmp1, #cNode,, EVEN, RIGHT, NOCLEAR, #parentField // Set B node parent even/right
\                   	AVL.__SETPA , #tmp2, #cNode,, EVEN, LEFT, NOCLEAR, #parentField // Set A node parent even/left
\               	<ELSEIF     ( #tmp0 < 0 )                       // Check if C node balance is high on right
\                   	AVL.__SETPA , #tmp1, #cNode,, EVEN, RIGHT, NOCLEAR, #parentField // Set B node parent even/right
\                   	AVL.__SETPA , #tmp2, #cNode,, PLUS, LEFT, NOCLEAR, #parentField // Set A node parent plus/left
\               	<ELSE                                           // Balance is high on left
\                   	AVL.__SETPA , #tmp1, #cNode,, MINUS, RIGHT, NOCLEAR, #parentField // Set B node parent minus/right
\                   	AVL.__SETPA , #tmp2, #cNode,, EVEN, LEFT, NOCLEAR, #parentField // Set A node parent even/left
\                   	ENDIF
\               	#st             #tmp1, #parentField[#bNode]     // Store B node parent field
\               	#st             #tmp2, #parentField[#aNode]     // Store A node parent field
\    
\               	#ld             #tmp0, #rightField[#cNode]      // Get right child of C node
\               	#st             #tmp0, #leftField[#bNode]       // Store it as left child of B node
\               	IF       ( #tmp0 != 0 ), THEN                   // Check if node exists
\                   	#ld             #tmp1, #parentField[#tmp0]      // Get its parent field
\                   	AVL.__SETPA #tmp0, #tmp1, #tmp1, #bNode,, LEFT, CLEAR, #parentField  // Set C node child parent to B node - left link
\                   	ENDIF
\    
\               	#ld                 #tmp0, #leftField[#cNode]    // Get left child of C node
\               	#st                 #tmp0, #rightField[#aNode]   // Store it as right child of A node
\               	IF       ( #tmp0 != 0 ), THEN                   // Check if node exists
\                   	#ld             #tmp1, #parentField[#tmp0]      // Get its parent field
\                   	AVL.__SETPA #tmp0, #tmp1, #tmp1, #aNode,, RIGHT, CLEAR, #parentField // Set C node child parent to B node - right link
\                   	ENDIF
\               	#st             #bNode, #rightField[#cNode]         // Set B node as right child of C node
\               	#st             #aNode, #leftField[#cNode]          // Set A node as left child of C node
\    
\               	AVL.__SETPA #cNode, #pFld, #pFld,, EVEN,, CLEAR, #parentField    // Store A node parent in C node parnent field - even balance
\               	MV              #aNode, #cNode                  // Copy C node addr
\               	GOTO     #complRotLabel                         // Execute rotation completion code
\					ENDIF
\    
\    			//
\    			//	No rotation
\    			//
\			 	ADDI		#tmp1, 1[#balance] 					// Encode balance
\    			ANDI		#tmp1, 0b011						// Keep low bits
\    			AVL.__EXTPA	#tmp0, #pFld						// Extract addr of next node up
\    
\    			IF			( #tmp0 == 0 ), THEN 				// Check if root node
\                   #st         #aNode, #Anchor                     // Update header
\    				#st			#tmp1, #parentField[#aNode]			// Store balance only in parent field
\    				BREAK											// Done
\    				ENDIF
\
\				ANDI		#pFld, ~ 0b011						// Clear balance bits in parent field
\				OR			#pFld, #tmp1						// Insert new balance
\    			#st			#pFld,#parentField[#aNode]			// Store parent field in node
\    			MV			#aNode, #tmp0						// Copy next node up addr

	if (Type === "INSERT") {
\				IF			(#balance != 0), CONTINUE			// Continue since balance is not zero
\				BREAK											// Done otherwise	
	}
	else {
\				ANDI		#balance, 0b001						// Extract low bit of balance
\				IF			( #balance != 0 ), BREAK			// Done if low bit is on (balance is +/- 1)
\				CONTINUE										// Continue otherwise							
	}
	
\    
\               //
\               //  Rotation completion common code
\               //
\#complRotLabel AVL.__EXTPA #tmp1, #pFld                    	// Get A node parent addr
\               IF          ( #tmp1 == 0 ), THEN                // Check if root node
\                   #st         #aNode, #Anchor                     // Update header
\                   AVL.__EXTBB #pFld, #pFld                        // Keep only balance bits
\                   #st         #pFld, #parentField[#aNode]         // Store it back
\                   BREAK                                           // Done - root node
\                   ENDIF
\    
\    			#st			#pFld,#parentField[#aNode]			// Store parent field in node
\               AVL.__EXTLT #tmp2, #pFld                        // Get parent link type of A node
\               IF       ( #tmp2 > 0 ), THEN                    // Check if left link
\                   #st         #aNode, #leftField[#tmp1]       // Set new top node as left child of parent
\               <ELSE
\                   #st         #aNode, #rightField[#tmp1]      // Set new top node as right child of parent
\                   ENDIF

	if (Type === "REMOVE") {
\               MV  		#aNode, #tmp1                       // Get addr of parent node
\				ANDI		#tmp1, 0b001[#pFld]					// Extract low bit of balance
\				IF			( #tmp1 != 0 && #aNode != 0 ), CONTINUE // Done if low bit is on (balance is zero) or not root node
	}
	
\    			ENDDO											// ENd of balance block