/********************************
This is the file WinTreeFetch.cpp == Windows Last Left Threaded Data Tree Fetch data. 
It holds the functions:

"FetchAllTreeData", 
that the Windows Last Left Threaded Tree uses to fetch data from the nodes of the tree.

"FetchNodeData"
that WLLTT will use to find a specific node entered by the user.
********************************/

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


// *********************************************************
// ++++++++++ BEGIN function FetchAllTreeData +++++++++++++++

// Will walk through tree and return with all current node 
//		data in ascending order. 

/****
	This is were the code gets complex, and as functionality increases with more data member in each node and more pointers
	from each node the complexity will increases exponentially.  Complexity akin to np == number of pointers, 
	complexity == 2^(np).
	
	Think of the data tree like a family tree, descendents below, ancestors above.

	For this Last Left Thread Tree demonstrator we pickup the data in ascending value.
	'A' == lest value, 'z' == greatest value.
	We use the simple Last Left Thread Tree logic to find and collect the data in ascending order.
	
	current node = root node;
	Last Left Pointer flag = false;
	LLPf == Last Left Pointer flag;
   iCurrentTreeMemberCount is a tally of the number of current tree nodes.


	while(1){
	??? If ( current node has left child && !( LLPf ) )  
				move to left child; 
				continue;
			else
			??? If ( !( LLPf ) 
					fetch current node data;
					++iCurrentTreeMemberCount
			
	??? If ( current node has right child ) 
			move to right child ; 
			set LLPf to false ;	
				??? If( current node has no left child ) 
						fetch current node data; 
						++iCurrentTreeMemberCount
			continue; 

	??? If ( current node has; no left child, no right child )
			??? If ( Last Left Pointer not NULL) 				  
				set LLPf to true;
				move up Last Left Thread to last node left ture was made at ;  
				fetch current node data;
				++iCurrentTreeMemberCount
				continue;
			else
				break ;

  If this betoken code does not make sense you need to look through a Data Structure book
  Try Mark Allen Weiss's Data Structures and Algorithm Analysis in C++.
****/

void
FetchAllTreeData(TreeData* pTD)	{
	pTD->VoidOutCurrentTreeMembers() ;	
	pTD->SetPointerLastNodeViewed( pTD->FetchPointerToRoot() ) ; // Now at root of tree.
	pTD->SetPointerLestSignificantNode( pTD->FetchPointerToRoot() ) ;  // Start with LEst node pointer set to Root..               

	// Set to false for next time program comes in tree.
	pTD->SetFlagUpThread( FALSE ) ;		
	pTD->SetFlagLestSignificantNodeReached( FALSE );
	// To set node counter to 0.
	pTD->SetCurrentTreeMemberCount( -( pTD->FetchCurrentTreeMemberCount() ) ) ;

// This will get Tree Node Data and Cat it to TreeData  TCHAR szCurrentTreeMembers[60];
// pTD->CatTNDtoCurrentTreeMembers( (pTD->FetchPointerLastNodeViewed())->FetchTreeNodeData() ) ;

// Special case: This 'if' will get data from root node if root node is Lest Significant Node.
//		That is…  if( Root Has No Children ) do this...

	if( (pTD->FetchPointerLastNodeViewed()->FetchLeftPointer()) == NULL )	{
			pTD->SetFlagLestSignificantNodeReached( TRUE ) ;
			pTD->CatTNDtoCurrentTreeMembers( (pTD->FetchPointerLastNodeViewed())->FetchTreeNodeData() ) ;				
         pTD->SetCurrentTreeMemberCount( 1 ) ;
		}   // End if...

	// 1. Move all the way down the left side of the tree if any.	
	while(1)	{
		if( pTD->FetchPointerLastNodeViewed() != NULL && (pTD->FetchPointerLastNodeViewed())->FetchLeftPointer() != NULL &&
					!( pTD->FetchFlagUpThread() ) )	{	
			pTD->SetPointerLastNodeViewed( ( pTD->FetchPointerLastNodeViewed() )->FetchLeftPointer() ) ;
		
		// Once at end of left side of tree branch (or if no left side) get data. 
			if( (pTD->FetchPointerLastNodeViewed())->FetchLeftPointer() == NULL )	{				
				pTD->CatTNDtoCurrentTreeMembers( (pTD->FetchPointerLastNodeViewed())->FetchTreeNodeData() ) ;
				pTD->SetCurrentTreeMemberCount( 1 ) ;
				if( (pTD->FetchPointerLastNodeViewed() != NULL ) && !( pTD->FetchFlagLestSignificantNodeReached()) )
					pTD->SetPointerLestSignificantNode( (pTD->FetchPointerLastNodeViewed()) ) ;
					pTD->SetFlagLestSignificantNodeReached( TRUE );
				}// End second if above 
			continue ; // Now at end of left branch...
		} // End of if right under while(1) 
		
		// If you can't move left, see if you can move Right.
		if( (pTD->FetchPointerLastNodeViewed())->FetchRightPointer() != NULL )	{			 
		pTD->SetPointerLastNodeViewed( ( pTD->FetchPointerLastNodeViewed() )->FetchRightPointer() ) ;
		if( (pTD->FetchPointerLastNodeViewed())->FetchLeftPointer() == NULL )   { 
				pTD->CatTNDtoCurrentTreeMembers( (pTD->FetchPointerLastNodeViewed())->FetchTreeNodeData() ) ;
				pTD->SetCurrentTreeMemberCount( 1 ) ;
			}
		pTD->SetFlagUpThread( FALSE ) ;
		continue ;
		} // End of if...

		// If both the left and right pointers are NULL test is the Last Left Thread pointer is not NULL.
		// If there is an address then up and set the FlagUpThread flag to true.
		if( (pTD->FetchPointerLastNodeViewed())->FetchLeftThreadPointer() != NULL )	{
		pTD->SetPointerLastNodeViewed( ( pTD->FetchPointerLastNodeViewed() )->FetchLeftThreadPointer() ) ;
		pTD->SetFlagUpThread( TRUE ) ;
		pTD->CatTNDtoCurrentTreeMembers( (pTD->FetchPointerLastNodeViewed())->FetchTreeNodeData() ) ;	
		pTD->SetCurrentTreeMemberCount( 1 ) ;
		continue ;
		} // End of if...
				
		// To get here all pointers out of the node are NULL, so you are at the last node in the tree
		//		or Root is the only tree member. 

	break ;
		} // End of while... One Node to go... maybe..if last node is not root.
	
	pTD->SetPointerMostSignificantNode( pTD->FetchPointerLastNodeViewed() ) ;
	pTD->SetFlagMostSignificantNodeReached( TRUE ) ;	
	MedianOfDataTree( pTD ) ;	
	int stop ;
  	stop = 1 ;

return ; // return void.
	} // End function FetchAllTreeData

// ----------- END function FetchAllTreeData ---------------
// *********************************************************


// *********************************************************
// +++++++ BEGIN function FetchNodeData +++++++++

// Basically a cut down version of the code above.
// This function only has to find the node the user enters the key value of.
// If the node is found it's address in loaded into TD as the next node to be removed and TRUE is returned,
// If the node is not found in the data tree then FALSE is returned.
bool
FetchNodeData(TreeData* pTD ) {

TreeNode* pC ;   // pointer to Current node.

pC = ( pTD->FetchPointerToRoot() ) ; // Now have current tree's root.

TCHAR* szNodeValue = pTD->FetchNodeToBeRemoved() ;  // Node to be removed's key value.

	// To get pointer to median node must walk through the tree to find it.
	while( 1 )	{
		
		if( pC == NULL ) return FALSE ;  // If "pC" == "NULL" then have go through whole tree and not found node,
                                       // so node is not a current member of the tree.

		if( strncmp( szNodeValue, pC->FetchTreeNodeData(), 1 ) == 0 )	// See Def. of strncmp() function.
			{
			pTD->SetPointerNodeToBeRemoved( pC ) ;
			break ;
			} ;

		if( strcmp(pC->FetchTreeNodeData(), szNodeValue ) == 1 )	// A > B then 1, go left, else go right
			{
			pC = pC->FetchLeftPointer() ;
			}
		else
			{
			pC = pC->FetchRightPointer() ;
			}
	continue ; // Back to top of 'while' to test if this is median.
	} // End of while(1)...



return TRUE; 
	}

// -------- END function FetchNodeData ----------
// *********************************************************