/*********************************
This is the file WinTreeRemove.cpp == Windows Last Left Threaded Data Tree Remove node from tree. 
It holds functions that are used to remove a node from the Last Left Threaded Tree 
and then percolate (reorder the tree with) a current tree node if percolation is needed.  
That candidate node (the node to be percolated up the tree) is first nominated by its original position in the 
tree, and by it's relationship with the node to be removed.    The node to be percolated is
always a descendant of the node that is to be removed.
*********************************/

#include "WinTree2.h"  // WinTree1.h is 'ifndef' so wont be multipled defind


// *********************************************************
// +++++++++ BEGIN function RemoveNode ++++++

//  Will remove the node pointed to in TreeData member as NodeToBeRemoved, 
//  and percolate best of the remaining nodes to 
//  take the place of the node that was removed. 

void
PreRemoveNode(TreeNode* pRoot, TreeData* pTD, TCHAR* szBuffer_1, TCHAR* szBuffer_2, 
				  TCHAR* szBuffer_3, TCHAR* szBuffer_5, TCHAR* szBuffer_6, TCHAR* szBuffer_7)	{

					/****************************************************************************** 
					Left arrow key will remove the lest significant node from the tree, while the
					Right arrow key will remove the most significant node from the tree.
					Then find and percolate the best candidate of the remaining nodes to take 
					the place of the removed node.
					The tree's node pointers must be reordered when a node is removed, to
					maintain the tree's pointer integrity. 

               iCurrentTreeMemberCount is a tally of the number of current tree nodes.
					*******************************************************************************/
	TCHAR* szBuffer;

		  		if( DoesTreeExist(pTD) ) // Must check if tree exist. 
					{
					pTD->VoidOutCurrentTreeMembers() ; 
					FetchAllTreeData(pTD) ;	

					szBuffer = pTD->FetchPointerNodeToBeRemoved()->FetchTreeNodeData() ;
				
					if(  szBuffer )
				     pTD->SetLastNodeRemoved( szBuffer ) ;					
										
					
					RemoveNode(pTD); // Only call to RemoveNode in application.					
					pTD->SetCurrentTreeMemberCount( -1 ) ;
					if( pTD->FetchPointerToRoot() != pRoot )	// If root node was removed/replaced reset WinProc's root pointer.
					pRoot = pTD->FetchPointerToRoot() ;		
					pTD->VoidOutCurrentTreeMembers() ; 
					if( DoesTreeExist(pTD) ) // If the tree still exist (root was not Node to Remove) then load szBuffer_* with data.
						{
						FetchAllTreeData(pTD) ;												
						strcpy( szBuffer_1, ( ( pTD->FetchPointerToRoot() )->FetchTreeNodeData() ) );	// root data
		 				strcpy( szBuffer_2, pTD->FetchCurrentTreeMembers() );									// current tree data
						strcpy( szBuffer_3, ( (pTD->FetchPointerLestSignificantNode())->FetchTreeNodeData() ) );	//  lest sig node	 
						strcpy( szBuffer_5, ( (pTD->FetchPointerMostSignificantNode())->FetchTreeNodeData() ) );	//  most sig node	 
						strcpy( szBuffer_6, ( (pTD->FetchPointerMedianNode())->FetchTreeNodeData() ) );	//  most sig node	 
						strcpy( szBuffer_7, ( (pTD->FetchLastNodeRemoved() ) ) );	//  most sig node	 
						}
					else // If last node was removed then ...
						{
						strcpy( szBuffer_1, "\0" ); // NULL out the Buffs..
						strcpy( szBuffer_2, "No Tree Exist!");  // Set the meassage. 
						strcpy( szBuffer_3, "\0" );					
						strcpy( szBuffer_5, "\0" );
                  strcpy( szBuffer_6, "\0" );
						strcpy( szBuffer_7, "\0" );
						}
					} // End of if on fDoesTreeExist ...		
} // End PreRemoveNode ...

// -------- END function RemoveNode ---------
// *********************************************************





// *********************************************************
// +++++++++ BEGIN function RemoveLestSignificantNode ++++++

// Will remove the lest significant node, and percolate best of the remaining nodes to 
// take the place of the node that was removed. 
void
RemoveNode(TreeData* pTD)	{

	/**************************************************************
  	The best candidate to replace the "Node to be Removed" will be...
	a) the left child if that child has no right children, 
	b) the furthest right descendant of the left child, 
	c) the first right child as long as their are no left children.

	Once the node to be percolated is found all pointer information involving both 
	the node to be removed and the node to be percolated (if any) must be saved for pointer reassignment. 
   ***************************************************************/

// Nomenclature;  use these in function calls to pointer reassignment
// functions.

// NR   = Node to be removed.
// PI   = Parent of node to be removed.
// NP   = Node to be percolated.
// PII  = Parent of node to be percolated.
// pC   = Current node used as place holder in search for percolation node.
// pR	  = Root node.

int stop ;
stop = 1;   // Debug stop.

TreeNode* pNR  = NULL ;  // 'p' prefix == pointer to
TreeNode* pPI  = NULL ;
TreeNode* pNP  = NULL ;
TreeNode* pPII = NULL ;
TreeNode* pC   = NULL ;
TreeNode* pR	= NULL ;

int type = 0 ;	// In notes this is called 'case', but "case"
					// is C++ reserve word, so call it type hear.
					// ‘type’ will represent the type of relationship between
					// nodes.

// Node to be removed.
pNR = pTD->FetchPointerNodeToBeRemoved()  ;	

// Parent of node to be removed.  If pPI == NULL then pNR == Root.
pPI = ( pTD->FetchPointerNodeToBeRemoved()  )->FetchParentNodePointer() ; 

	// Now need to find node to percolate into position of node to be removed. 
	// That node will be below the NR node if any nodes below NR exist.  
	
pC		= pNR ;	// Start looking for the NP at the NR.
pPII	= pPI ;	// PII will follow pC so when pC == NP then PII will point to the node 
					//	above NP and by that it will be pointing to the parent of NP.  Note pPII == pNR == pR.
pR = ( pTD->FetchPointerToRoot() ) ; // Now have current tree's root.



if( pC->FetchLeftPointer() != NULL ) 	{  // If there is a LC move pC to it.
   	pPII = pC ;
		pC   = pC->FetchLeftPointer();
	
	while(1)	{
	if(  pC->FetchRightPointer() !=NULL) 	{
	   pPII = pC ;
		pC = pC->FetchRightPointer() ;
	   continue ;
	   }
	   break ;
	}// End 'while(1)' loop.  Have now found the Node to percolate up.
	// Now pC (the pointer to Current node) is pointing to the to the Percolation 
	//		candidate hand that candidate's address off to pNR (pointer to Node to be Removed) .
   pNP = pC ;
	}else{  // 'else' with top 'if'
		if( pC->FetchRightPointer() != NULL ) // If you can't go left see if you can go right.
			{
			pPII = pC ;
			pC = pC->FetchRightPointer() ;
			} // End 'if'
		pNP = pC ;
		}// End 'if else' ...
		
if(pNP != pNR && pNP != NULL) pPII = pNP->FetchParentNodePointer() ;

stop = 1;

// Next find the relationship between the nodes so that
// proper percolation can be done.
// Whether or not a node to be removed is to have it's place fill by a descendants node totally relies on that 
// node's relationship with it parents, siblings, and descendants.

// If you look at the 'if' 'else' cascade below you will see that the last five Percolations
// look like the first five with the only deference being that perco 1- 5 deal with the root.
// You may seem to think that this duplicate the work load, and you are right.  Now it makes for twice
// the calls and twice the testing, but in the future there will be a much more complex node to node relationship and
// what seem over do now will be needed then.

   // Perco 1 Only Root in tree.
if( pNR == pC && pC == pR && pR == pNP && pNR != NULL && pPI == pPII && pPII == NULL )
	type = 1 ;
   else	{
   // Perco 2 Remove Root.  Root has only LCs, R has no RCs.  With R not having  RCs do not need a full percolation. 
if( pNR == pR && pR == pPII && pPII != pC && pC == pNP && pNP != pNR && pNR != pPI &&
	 pNP == pNR->FetchLeftPointer() && pNR->FetchRightPointer()== NULL  )
	type = 2 ;
   else	{
   // Perco 3 Remove Root.  Root has only RCs,  With only RCs do not need a full percolation. 
if( pNR == pR && pR == pPII && pPII != pC && pC == pNP && pNP != pNR && pNR != pPI &&
	 pNP == pNR->FetchRightPointer() && pNR->FetchLeftPointer()== NULL  )
	type = 3 ;
   else	{
	// Perco 4 Remove Root. If NR has LCs and RCs, but LC has no RC.
if( pNR == pR && pR == pPII && pPII != pC && pC == pNP && pNP != pNR && pNR != pPI && 
	 pNR->FetchLeftPointer() == pNP  )
	type = 4 ;
   else	{
   // Perco 5 Remove Root. NR has LC and and may have RC. LC has RCs (must full percolate.)
if( pNR == pR && pR != pPII && pPII != pC && pC == pNP && pNP != pNR && pNR != pPI && 
	 pNR->FetchLeftPointer() != pNP  )
	type = 5 ;
   else	{
   // Perco 6 Node to remove has no children.
if( pNR != pR && pNR == pNP && pNP == pC && pC != pPI && pPI == pPII &&
	 pNR->FetchLeftPointer() == NULL && pNR->FetchRightPointer() == NULL  )
	type = 6 ;
   else	{
   // Perco 7 NR has no RCs LC has no RCs (will not have to full percolate)
if( pNR != pR && pNR == pPII && pPII != pNP && pNP == pC && pC != pPI &&  
	 pNR->FetchLeftPointer() != NULL && pNR->FetchRightPointer() == NULL   )
	type = 7 ;
   else	{
   // Perco 8 NR may, or may not have RCs, NP has RCs  (must full percolate)
if( pNR != pR && pNR != pPII && pPII != pNP && pNP == pC && pC != pPI &&  
	 pNR->FetchLeftPointer() != NULL )
	type = 8 ;
   else	{
   // Perco 9 NR only has RCs (will not have to full percolate)
if( pNR != pR && pNR == pPII && pPII != pNP && pNP == pC && pC != pPI &&  
	 pNR->FetchLeftPointer() == NULL && pNR->FetchRightPointer() == pNP )
	type = 9 ;
   else  {
   // Perco 10 NR has LCs and RCs, LC has no RCs
if( pNR != pR && pR != pPII && pPII != pC && pC == pNP && pNP != pNR && pNR != pPI && 
	 pNR->FetchLeftPointer() == pNP  )
	type = 10 ;
		}}}}}}}}} ;  // Closes all the ‘else   {‘ of the above cascade.

// "switch" statement to make the calls to the pointer
// reassignment functions.
   
	stop = 1 ;	
//	return ;

	switch(type)	{

   case 1:	Perco_one(pNR);
				pTD->SetPointerToRoot( NULL ) ; // First five will have new root or no root (Perco_one).
   	break ;

   case 2:	Perco_two(pNR, pNP);
				pTD->SetPointerToRoot( pNP ) ; 
   	break ;

	case 3:	Perco_three(pNR, pNP);
            pTD->SetPointerToRoot( pNP ) ; 
   	break ;

   case 4:	Perco_four(pNR,pPI,pNP,pPII);
		      pTD->SetPointerToRoot( pNP ) ;
   	break ;

	case 5:	Perco_five(pNR,pPI,pNP,pPII);
		      pTD->SetPointerToRoot( pNP ) ;
   	break ;

	case 6:	Perco_six(pNR,pPI,pNP,pPII);   // Last five do not change root. 
   	break ;

	case 7:	Perco_seven(pNR,pPI,pNP,pPII ) ;
   	break ;

	case 8:	Perco_eight(pNR,pPI,pNP,pPII)  ;						
   	break ;

	case 9:	Perco_nine(pNR, pPI, pNP,pPII) ;
   	break ;

	case 10:	Perco_ten(pNR, pPI, pNP,pPII) ;
   	break ;

	default :
		stop = 1 ;  // Debug stop; 
   } ;  // End "switch(type)"

	return ;
	} // End of function RemoveLestSignificantNode...

// -------- END function RemoveLestSignificantNode ---------
// *********************************************************


// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++ BEGIN Percolation functions one through eleven +++++

// All of these functions do pointer reassignment.

// Nomenclature:

// pNR   = Node to be removed.
// pPI   = Parent of node to be removed.
// pNP   = Node to be percolated.
// pPII  = Parent of node to be percolated.
// xxLC = xx’s left child.
// xxRC = xx’s right child.
// xxLT = xx’s left Thread.
// TEMP = temporary member for loops.



void
Perco_one(TreeNode* pNR ) // Only root and del it out.
{
   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ; 
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return  ;
}


void
Perco_two  (TreeNode* pNR, TreeNode* pNP )  // Remove root, root had only LC
{
   pNP->SetParentNodePointer( NULL ) ;
	pNP->SetLeftThreadPointer( NULL ) ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;	 
return ;
}

void
Perco_three(TreeNode* pNR, TreeNode* pNP )  // Remove root, root had only RC
{
   pNP->SetParentNodePointer( NULL ) ;
	pNP->SetLeftThreadPointer( NULL ) ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return ;
}

void
Perco_four ( TreeNode* pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII ) // Remove root, root had right descendents.
{
	pNP->SetParentNodePointer( NULL ) ;
	pNP->SetLeftThreadPointer( NULL ) ;
	pNP->SetRightPointer( pNR->FetchRightPointer( ) ) ;
	( pNR->FetchRightPointer() )->SetParentNodePointer( pNP ) ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return ;
}



void
Perco_five (TreeNode* pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII ) 
{  // Remove Root.  Root == NR
	// The NP will have no RC but may have LC.
   // If NP has LC must first reset pointers at NP and it's relations.
	// NR may have right children.
   
   if( pNP->FetchLeftPointer() != NULL )
		{
      pPII->SetRightPointer( pNP->FetchLeftPointer() ) ;
		( pNP->FetchLeftPointer() )->SetParentNodePointer( pPII ) ;
		// NPLC LLP is OK as NP will be moved to last left turn possition.
		}else{
		pPII->SetRightPointer( NULL ) ;
			}

	pNP->SetParentNodePointer( NULL ) ;
	pNP->SetLeftThreadPointer( NULL ) ;
   pNP->SetLeftPointer( pNR->FetchLeftPointer() ) ;
	( pNP->FetchLeftPointer() )->SetParentNodePointer( pNP ) ;
   if( pNR->FetchRightPointer() )
		{
	   pNP->SetRightPointer( pNR->FetchRightPointer( ) ) ;
	   ( pNR->FetchRightPointer() )->SetParentNodePointer( pNP ) ;
		}
	else
		pNP->SetRightPointer( NULL ) ;

	TreeNode* TEMP ;
   TEMP = pNR->FetchLeftPointer() ;
 while(TEMP != pPII->FetchRightPointer() )
   {
   TEMP->SetLeftThreadPointer( pNP ) ;
   TEMP = TEMP->FetchRightPointer() ;
   } ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return ;
}

// NR != Root, NR has no children.
void
Perco_six  (TreeNode* pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII )
{
 if( pPI->FetchLeftPointer() == pNR )
	 pPI->SetLeftPointer( NULL ) ;
 else
    pPI->SetRightPointer( NULL ) ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;	 
return ;
}


   // NR != Root.  NR has no RCs LC has no RCs (will not have to full percolate)
void
Perco_seven(TreeNode*pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII )
{
 if( pPI->FetchLeftPointer() == pNR )
	 {
	 pPI->SetLeftPointer( pNR->FetchLeftPointer() ) ;
	 pNP->SetLeftThreadPointer( pPI ) ;
	 pNP->SetParentNodePointer( pPI ) ;
	 }
 else
	 {
    pPI->SetRightPointer( pNR->FetchLeftPointer() ) ;
	 pNP->SetLeftThreadPointer(  pNR->FetchLeftThreadPointer( )  ) ;
	 pNP->SetParentNodePointer( pPI ) ;
	 } ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return ;

}

   // NR may have RCs, NP has RCs  (must full percolate)
void
Perco_eight(TreeNode*pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII  )
{
	// The NP will have no RC but may have LC.
   // If NP has LC must first reset pointers at NP and it's relations.
  
 if( pNP->FetchLeftPointer() != NULL )
		{
      pPII->SetRightPointer( pNP->FetchLeftPointer() ) ;
		( pNP->FetchLeftPointer() )->SetParentNodePointer( pPII ) ;
		// NPLC LLP is OK as NP will be moved to last left turn possition.
		}else{
		pPII->SetRightPointer( NULL ) ;
			}
 
	pNP->SetParentNodePointer( pNR->FetchParentNodePointer() ) ;
	pNP->SetLeftThreadPointer( pNR->FetchLeftThreadPointer() ) ;
   pNP->SetLeftPointer( pNR->FetchLeftPointer() ) ;
	( pNP->FetchLeftPointer() )->SetParentNodePointer( pNP ) ;

	
	if( (pNR->FetchParentNodePointer())->FetchLeftPointer() == pNR )
		 (pNR->FetchParentNodePointer())->SetLeftPointer( pNP ) ;
	else
		 (pNR->FetchParentNodePointer())->SetRightPointer( pNP ) ;

	if( pNR->FetchRightPointer() != NULL )
		{
		 pNP->SetRightPointer( pNR->FetchRightPointer() );
   	 pNR->FetchRightPointer()->SetParentNodePointer( pNP ) ;
		}

	TreeNode* TEMP ;
   TEMP = pNR->FetchLeftPointer() ;
 while(TEMP != pPII->FetchRightPointer() )
   {
   TEMP->SetLeftThreadPointer( pNP ) ;
   TEMP = TEMP->FetchRightPointer() ;
   } ;

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;
	

    delete pNR ;
return ;
}

// NR only has RCs (will not have to full percolate)
void
Perco_nine (TreeNode* pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII )
{
   pNP->SetParentNodePointer( pNR->FetchParentNodePointer() ) ;
	
	if( pPI->FetchLeftPointer() == pNR )
		pPI->SetLeftPointer( pNP ) ;
	else
		pPI->SetRightPointer( pNP ) ;
		
	// NP LLP is OK as NP is a RC of NR and LLP of NP is already pointing to what NR pointed to.

   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return ;
}

// NR != Root. NR has LC and RC, but LC has no RC (will not have to full percolate)  
void
Perco_ten ( TreeNode* pNR, TreeNode* pPI, TreeNode* pNP, TreeNode* pPII )
{
	pNP->SetParentNodePointer( pNR->FetchParentNodePointer() ) ;
	pNP->SetLeftThreadPointer( pNR->FetchLeftThreadPointer() ) ;	

	if( (pNR->FetchParentNodePointer())->FetchLeftPointer() == pNR )
		 (pNR->FetchParentNodePointer())->SetLeftPointer( pNP ) ;
	else
		 (pNR->FetchParentNodePointer())->SetRightPointer( pNP ) ;

	if( pNR->FetchRightPointer() != NULL )
		{
		 pNP->SetRightPointer( pNR->FetchRightPointer() );
   	 pNR->FetchRightPointer()->SetParentNodePointer( pNP ) ;
		}	
	
   pNR->SetLeftPointer( NULL ) ;
   pNR->SetRightPointer( NULL ) ;
   pNR->SetLeftThreadPointer( NULL ) ;
	pNR->SetParentNodePointer( NULL ) ;

    delete pNR ;
return ;
}

// ----- End of Percolation functions ---------------------


// ------ END Percolation functions one through eleven ------
// ----------------------------------------------------------