//MACRO     Avl.remove  Anchor,    Node,    WReg[8],	FieldDispl= 0
//--------------------------------------------------------------------------------------------------
//
//  @ 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 balanceLbl= DVASM.getNewLabel();
    var leftField= FieldDispl;
    var parentField= wl + "+" + FieldDispl;
    var rightField= wl*2 + "+" + FieldDispl;

    //
    //  Set up registers and addresses
    //
    var lockTmp= WReg[0];
    var pFld = WReg[0];
    var left= WReg[1];
    var pAddr= WReg[2];
    var right= WReg[3];
    var tmp0= WReg[4];
    var tmp1= WReg[5];
    var tmp2= WReg[6];
    var rNode= WReg[7];

    var balWReg= "[" + WReg.slice(1, 8) + "]";

    //
    //  Generate code
    //
\#Label     DO                                              // Start main DO loop
\               #ld         #left, #leftField[#Node]            // Load left child addr
\               #ld         #pFld, #parentField[#Node]          // Load parent field
\               AVL.__EXTPA #pAddr, #pFld                       // Get parent addr
\               AVL.__EXTLT #tmp0, #pFld                        // Get parent link type
\               #ld         #right, #rightField[#Node]          // Load left child addr
\
\               //
\               // Node is leaf
\               //
\               IF          ( #left == 0 && #right == 0 ), THEN // Handle leaf node
\
\                   IF          ( #pAddr == 0 ), THEN               // Node is root and leaf
\                       #st         0, #Anchor                          // Mark tree as empy
\                       BREAK                                           // Done - tree is empy
\                       ENDIF
\
\                   IF          ( #tmp0 != 0 ), THEN                // Check if node is left child
\                       #st     0, #leftField[#pAddr]                   // Clear left child addr in parent
\                       GOTO    #balanceLbl                             // Process balancing
\                       ENDIF
\
\                   #st         0, #rightField[#pAddr]              // Clear right child addr in parent
\                   GOTO        #balanceLbl                         // Process balancing
\                   ENDIF
\
\               //
\               // Node does not have left child
\               //
\               IF          ( #left == 0 ), THEN                // Node does not have left child
\                   #ld         #pFld, #parentField[#right]         // Load right child parent field
\
\                   IF          ( #pAddr == 0 ), THEN               // Check if node is root
\                       #st         #right, #Anchor                     // Update header
\                       AVL.__EXTBB #pFld, #pFld                        // Keep only balance bits
\                       #st         #pFld, #parentField[#right]         // Store it back
\                       BREAK                                           // Done - right child is new root
\                       ENDIF
\
\                   IF          ( #tmp0 == 0 ), THEN              	// Check if right child
\                       #st         #right, #rightField[#pAddr]         // Node right child is new parent right child
\                       AVL.__SETPA #right, #pFld, #pFld, #pAddr,, RIGHT, CLEAR, #parentField // Link from new parent is to right child
\                       GOTO        #balanceLbl                         // Process balancing
\                       ENDIF
\
\                   #st         #right, #leftField[#pAddr]          // Node right child is new parent left child
\                   AVL.__SETPA #right, #pFld, #pFld, #pAddr,, LEFT, CLEAR, #parentField // Link from new parent is to left child
\                   GOTO        #balanceLbl                         // Process balancing
\                   ENDIF
\
\               //
\               // Node does not have right child
\               //
\               IF          ( #right == 0 ), THEN               // Node does not have right child
\                   #ld         #pFld, #parentField[#left]          // Load left child parent field
\
\                   IF          ( #pAddr == 0 ), THEN               // Check if node is root
\                       #st         #left, #Anchor                      // Update header
\                       AVL.__EXTBB #pFld, #pFld                        // Keep only balance bits
\                       #st         #pFld, #parentField[#left]          // Store it back
\                       BREAK                                           // Done - left child is new root
\                       ENDIF
\
\                   IF          ( #tmp0 != 0 ), THEN                // Check if node is left child
\                       #st         #left, #leftField[#pAddr]           // Node left child is new parent left child
\                       AVL.__SETPA #left, #pFld, #pFld, #pAddr,, LEFT, CLEAR, #parentField // Link from new parent is to left child
\                       GOTO            #balanceLbl                     // Process balancing
\                       ENDIF
\
\                   #st         #left, #rightField[#pAddr]          // Node left child is new parent right child
\                   AVL.__SETPA #left, #pFld, #pFld, #pAddr,, RIGHT, CLEAR, #parentField // Link from new parent is to right child
\                   GOTO            #balanceLbl                     // Process balancing
\                   ENDIF
\
\               //
\               // Node has both left and right child
\               //
\               AVL.__EXTBB #tmp1, #pFld                        // Get balance bits
\
\               //
\               // Use left subtree
\               //
\               IF          ( #tmp1 != 0 ), THEN                // Use left subtree since it is deeper or even
\                   MV          #rNode, #left                       // Copy left child to prime the loop
\                   WHILE                                           // Start loop to find right most node in subtree
\                       #ld         #tmp1, #rightField[#rNode]          // Load right child addr
\                       IF          ( #tmp1 == 0 ), BREAK               // Most right node in left subtree found
\                       MV          #rNode, #tmp1                       // Copy node addr
\                       ENDWHILE
\
\                   IF          ( #pAddr == 0 ), THEN               // Check if node is root
\                       #st         #rNode, #Anchor                 // Update header addr of root node
\                   <ELSE
\                       IF          ( #tmp0 == 0 ), THEN            // Check if parent link type is right
\                           #st         #rNode, #rightField[#pAddr]     // Update parent right child addr
\                       <ELSE
\                           #st         #rNode, #leftField[#pAddr]      // Update parent left child addr
\                           ENDIF
\                       ENDIF
\
\                   #ld         #tmp1, #parentField[#rNode]         // Get replace node parent field
\                   #ld         #tmp2, #leftField[#rNode]           // Get left child addr if any
\                   #st         #pFld, #parentField[#rNode]         // Store parent field in replace node
\                   #st         #right, #rightField[#rNode]         // Store right child addr in replace node
\                   #ld         #tmp0, #parentField[#right]         // Get parent field of right node
\                   AVL.__SETPA     #right, #tmp0, #tmp0, #rNode,,, CLEAR, #parentField // Replace parent addr in right child parent field
\
\                   IF          ( #left != #rNode ), THEN           // Check if replace node is not left child of node
\                       #st         #left, #leftField[#rNode]           // Set left child for replacement node
\                       #ld         #tmp0, #parentField[#left]          // Get parent field of left node
\                       AVL.__SETPA #left, #tmp0, #tmp0, #rNode,,, CLEAR, #parentField // Replace parent addr in parent field of left child
\                       AVL.__EXTPA #pAddr, #tmp1                       // Get parent addr of replace node
\                       #st         #tmp2, #rightField[#pAddr]          // Store right child addr of replace node parent
\                       AVL.__SETPA , #pFld, #pAddr,,, RIGHT, NOCLEAR, #parentField // Set parent link to right
\                       IF          ( #tmp2 == 0 ), GOTO, ID= #balanceLbl   // Process balancing
\                       #ld         #pFld, #parentField[#tmp2]          // Get parent field of replace node left child
\                       AVL.__SETPA #tmp2, #pFld, #pFld, #pAddr,, RIGHT, CLEAR, #parentField // Replace parent addr in replace node left child
\                       GOTO        #balanceLbl                         // Process balancing
\                       ENDIF
\
\                   AVL.__SETPA , #pFld, #rNode,,, LEFT, NOCLEAR, #parentField // Set parent link to replace node to left
\                   IF          ( #tmp2 == 0 ), GOTO, ID= #balanceLbl   // Process balancing
\                   #ld         #pFld, #parentField[#tmp2]          // Get parent field of replace node left child
\                   GOTO        #balanceLbl                         // Process balancing
\                   ENDIF
\
\               //
\               // Use right subtree
\               //
\               MV          #rNode, #right                      // Copy right child to prime the loop
\               WHILE                                           // Start loop to find right most node in subtree
\                   #ld         #tmp1, #leftField[#rNode]           // Load left child addr
\                   IF          ( #tmp1 == 0 ), BREAK               // Most left node in right subtree found
\                   MV          #rNode, #tmp1                       // Copy node addr
\                   ENDWHILE
\
\               IF          ( #pAddr == 0 ), THEN               // Check if node is root
\                   #st         #rNode, #Anchor                     // Update header addr of root node
\               <ELSE
\                   IF          ( #tmp0 != 0 ), THEN                // Check if parent link type is left
\                   #st         #rNode, #leftField[#pAddr]          // Update parent left child addr
\                   <ELSE
\                   #st         #rNode, #rightField[#pAddr]         // Update parent right child addr
\                   ENDIF
\               ENDIF
\
\               #ld         #tmp1, #parentField[#rNode]             // Get replace node parent field
\               #ld         #tmp2, #rightField[#rNode]              // Get right child addr if any
\               #st         #pFld, #parentField[#rNode]             // Store parent field in replace node
\               #st         #left, #leftField[#rNode]               // Store left child addr in replace node
\               #ld         #tmp0, #parentField[#left]              // Get parent field of left node
\               AVL.__SETPA #left, #tmp0, #tmp0, #rNode,,, CLEAR, #parentField    // Replace parent addr in left child parent field
\
\               IF          ( #right != #rNode ), THEN              // Check if replace node is not right child of node
\                   #st         #right, #rightField[#rNode]         // Set right child for replacement node
\                   #ld         #tmp0, #parentField[#right]         // Get parent field of right node
\                   AVL.__SETPA #right, #tmp0, #tmp0, #rNode,,, CLEAR, #parentField   // Replace parent addr in parent field of right child
\                   AVL.__EXTPA #pAddr, #tmp1                       //Get parent addr of replace node
\
\                   #st         #tmp2, #leftField[#pAddr]           // Store left child addr of replace node parent
\                   AVL.__SETPA , #pFld, #pAddr,,, LEFT, NOCLEAR, #parentField // Set parent link to left
\                   IF          ( #tmp2 == 0 ), GOTO, ID= #balanceLbl   // Process balancing
\                   #ld         #pFld, #parentField[#tmp2]          // Get parent field of replace node right child
\                   AVL.__SETPA #tmp2, #pFld, #pFld, #pAddr,, LEFT, CLEAR, #parentField // Replace parent addr in replace node right child
\                   GOTO        #balanceLbl                         // Process balancing
\                   ENDIF
\
\               AVL.__SETPA , #pFld, #rNode,,, RIGHT, NOCLEAR, #parentField // Set parent link to replace node to right
\               IF          ( #tmp2 == 0 ), GOTO, ID= #balanceLbl   // Process balancing
\               #ld         #pFld, #parentField[#tmp2]              // Get parent field of replace node left child
\
\               //
\               //  Balance the tree
\               //
\#balanceLbl    AVL.__BALNC REMOVE, #Anchor, #pFld, #FieldDispl, #balWReg
\               ENDDO