// WinTreeF2.cpp

// Holds WinTree2 functions

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

// ************************************************************************
// ++++++++++++++++++++ Class constructors and destructors. ++++++++++++++++ 


// TreeNode constructor initializes all pointers and data to NULL.
// 'new' is used in TreeNode contructor so 'delete' is needed when a node it removed from the tree.

TreeNode::TreeNode(const TCHAR *cData){
                     pLeftPoint = NULL; pRightPoint = NULL; pLeftThread = NULL; pParentNode = NULL;                   
                     //  TCHAR     *szData;
                     szData = new TCHAR[ strlen( cData ) + 1];
                     assert( szData != 0 );
                     strcpy( szData, cData);							
     } //End constructor...

// TreeNode destructor deallocates dynamically allocated memory if any...
TreeNode::~TreeNode()	{
	int stop ;
	stop = 1 ;	
	delete szData ;
	pLeftPoint = NULL; pRightPoint = NULL; pLeftThread = NULL; pParentNode = NULL;
	} //End TreeNode destructor...


// TreeData constructor initializes with pointer to Root of Data Tree.
TreeData::TreeData(TreeNode* pROOT)	{
		pRoot = pROOT;   // Now Tree Data Class has address of tree root.

		// NULL out all other pointers and data members so program starts with frish face.

		pLestSignificantNode		= NULL ; 
		pLastNodeViewed			= NULL ;
		szCurrentTreeMembers[0]	= NULL ;
		szNodeToRemove[0]			= NULL ;
		
		// Booleans set to false.
		fUpThread		  = false ;
		fLastNodeReached = false ;
		fLestSignificantNodeReached = false ;

	} // End TreeData constructor ...


// TreeData destructor deallocates dynamically allocated memory if any...
TreeData::~TreeData()	{
				                           
	} //End TreeNode destructor...

// ----------------- Class constructors and detructors. -------------------
// ************************************************************************


// *********************************************************
// +++++++++++++ BEGIN function Create Tree ++++++++++++++++

// This is the Create Tree function it will Create a last left threaded Tree
// with 52 Nodes.   The data TreeNodes of that Tree will be the letters A..Za...z
// when done CreateTree will return a TreeNode pointer to the root of the tree.
// The root is the programs entree node to the data structure.
TreeNode*
CreateTree()	{
     
     int i; // for loop counter.	
	  int iNum; // Subscript for szAlph array.
     TCHAR *cTemp;
     bool fRootLoaded = false ; // To tell if Root node has been created.
     bool fFull = false ;  // To tell if tree has all 52 TreeNodes loaded A...Za...z
     TreeNode* TN;  // Used in building the tree.    
     TreeNode* pRoot; // The root of the data tree.

     srand( (unsigned)time( NULL ));  

     
          // Don't put the 'randomize()' function in the
		// 'while' loop.  If you do you will be reinitalizing
          // the seed every time...

// caAlph is an array [n][0] will hold the TCHAR, [n][1] will be used as a marker
// to tell if a particular letter has been added to the Tree or not, if [n][N] then no 
// not in tree yet, if [n][Y] then this letter is in tree and rando an other Tree TreeNode.


	  TCHAR *szAlph[ciNodeCount][2]={{"A\0","N\0"},{"B\0","N\0"},{"C\0","N\0"},{"D\0","N\0"}, {"E\0","N\0"}, {"F\0","N\0"},
		  {"G\0","N\0"},{"H\0","N\0"},{"I\0","N\0"},{"J\0","N\0"},{"K\0","N\0"},{"L\0","N\0"},{"M\0","N\0"},{"N\0","N\0"},
	{"O\0","N\0"},{"P\0","N\0"},{"Q\0","N\0"},{"R\0","N\0"},{"S\0","N\0"},{"T\0","N\0"},{"U\0","N\0"},{"V\0","N\0"},
	{"W\0","N\0"},{"X\0","N\0"},{"Y\0","N\0"},{"Z\0","N\0"},{"a\0","N\0"},{"b\0","N\0"},{"c\0","N\0"},{"d\0","N\0"},
	{"e\0","N\0"},{"f\0","N\0"},{"g\0","N\0"},{"h\0","N\0"},{"i\0","N\0"},{"j\0","N\0"},{"k\0","N\0"},{"l\0","N\0"},
	{"m\0","N\0"},{"n\0","N\0"},{"o\0","N\0"},{"p\0","N\0"},{"q\0","N\0"},{"r\0","N\0"},{"s\0","N\0"},{"t\0","N\0"},
	{"u\0","N\0"},{"v\0","N\0"},{"w\0","N\0"},{"x\0","N\0"},{"y\0","N\0"},{"z\0","N\0"}};   


  while(!fFull) {       // ciNodeCount is globle const...
	
	iNum = rand() % (ciNodeCount)  ; 	// iNum [0...52] as szAlph[n][m] has {{"A","?"}...{"z","?"}}
if(iNum < 0 || iNum > ciNodeCount ) continue ;
	if(!fRootLoaded)	{  // The 'root' is the first node to be created.
          pRoot = new TreeNode(szAlph[iNum][0]);  
			 szAlph[iNum][1]="Y" ; // Mark the Root data on the list of data already in tree !!!
          fRootLoaded = true ;
         continue ; // back up to 'while'
          }
          else
          {
              
      // Once ‘root’ is loaded then tree can be built.

	for(i=0; i<ciNodeCount; ++i)	{
		if( strcmp( szAlph[iNum][0], szAlph[i][0] ) == 0 ) {		
			if( strcmp( szAlph[iNum][1], "N\0" ) == 0 ) {  // *szAlph[iNum][i] by de-referencing the pointer, conversion 
				szAlph[iNum][1]="Y\0" ;  //   from 'char *' to 'int'  occurs.   Note 'N' is a char while "N" is a char string! 						
				TN = new TreeNode(szAlph[iNum][0]);   // Creat the new Tree Node...
				fFull = Position(TN, pRoot) ; // position new node in tree.  If return value from Position function is TRUE
														// then an other node with this new nodes data value already existed.
														// Function position deleted the new node TN when it found this inconsistency.
				break ;			   //  back up to 'while'... 
			} // End if...
		} // End outer if...
   } // end for loop.

	// Test if all A...Za...z data TreeNodes are in tree.
	for(i=0; i<ciNodeCount; ++i)	{
				fFull = true ;
		if( strcmp(szAlph[i][1], "N\0") == 0  )		{ // strcmp (a1, a2) if a1==a2 strcmp return 0
			fFull = false ;
			break ;
			} // End if...
		} // End for...

				 } // End 'else' on if(!fRootLoaded)....
	} // end 'while' on while(!fFull)...

	return pRoot;
     } // End function Create Tree...

// ---------------- END function Create Tree ---------------
// *********************************************************


// *********************************************************
// +++++++++++++++++++ BEGIN function position +++++++++++++
bool
Position(TreeNode *TN, TreeNode *pRoot ) 	{

	TreeNode *pCurrent ;
	TreeNode *pLastLeft ;// Last place turned left, if every.

	//TreeNode *last ;

	bool fLeftTurn ;   // Ask if we every turned left.
	pCurrent = pRoot ;
	fLeftTurn = false ;

TCHAR *szCurrentData;
TCHAR *szTNData;

szCurrentData = pCurrent->FetchTreeNodeData();
szTNData      = TN->FetchTreeNodeData();

/**** 
	 The 'root' is setup in 'create tree'.   To position a new 'node'
	 in the tree start at the 'root' compare 'root' value to new 'node'
	 value.	Each node in the tree has many pointer. At present there are only two child pointers,
	 more will be added later.  For any node in the tree including root, it's left child pointer
	 points a node that has a data member (the key member) that is less in value than it's data members 
	 value.   node m data > node n data : so node m will be parent of node n, node n will be left child of 
	 node m.   
	 If node n's data member (the key member) is greater in value than node m's data member then node n will
	 become the right child of node m.   
    The easy recipe for the code that follows is this;  to find your new nodes place in the tree 
	 
	 One: if your new node is less in value than the current node see if there is a left child of the current node
			if not then new node becomes that child.
			Same if new node value is grater than current node.
	 Two: if current node has a child on that side (left or right) then follow the pointer to that sides child
			and repeat above. 

    To handle a twin a new twin pointer will be added later.
****/
// int j = 	strcmp(pCurrent->FetchTreeNodeData(), TN->FetchTreeNodeData());
// int t = j ;

while(1)	{

  if( strcmp(pCurrent->FetchTreeNodeData(), TN->FetchTreeNodeData() ) == 1 ){
   
	  fLeftTurn = true ;  // Turned left.

   pLastLeft = pCurrent ;  // Lasted place turned left.

	if(pCurrent->FetchLeftPointer() == NULL) { // If no one less then put
   	pCurrent->SetLeftPointer( TN ) ;			 //	new member here.

      TN->SetLeftThreadPointer( pLastLeft ) ; // Lasted place left turn was made.
		TN->SetParentNodePointer( pCurrent ) ;	 // pCurrent is parent of new member.
		
      break ;
      }
		// To get here there was a left child.
   if(pCurrent->FetchLeftPointer() != NULL)  { // If some one less move
      pCurrent = pCurrent->FetchLeftPointer() ;  // down the tree.
   	continue ;
      }

} // ----- end first 'if' on strcmp...

// Same as above but moving to the right.
// If you only move to the right then no "last left"

  if( strcmp(pCurrent->FetchTreeNodeData(), TN->FetchTreeNodeData()) == -1 ) {
	if(pCurrent->FetchRightPointer() == NULL) {

   	pCurrent->SetRightPointer( TN ) ;
      TN->SetParentNodePointer( pCurrent ) ; // pCurrent is parent of new member.
      // Test to see if ever moved left.   If so set last left.

      if(fLeftTurn)	{
			TN->SetLeftThreadPointer( pLastLeft ) ;
			fLeftTurn = false ;  // Reset .
			break;
			}
		break;
      }  // If someone below to right move on down.

   if(pCurrent->FetchRightPointer() !=NULL ) {
      pCurrent = pCurrent->FetchRightPointer();
   	continue ;
      }

} // ----- end second 'if'

  // For now no twins.  That will come lator.
 if( strcmp(pCurrent->FetchTreeNodeData(), TN->FetchTreeNodeData()) == 0  ){
   delete TN ;
   return true ;
   }

} // ----- end 'while' -----

return false ;

}  // End function position...
// ---------------- END function position ------------------
// *********************************************************


// *********************************************************
// ++++++++++++ BEGIN function DoesTreeExist +++++++++++++++

/****
	One; test if tree exist,  Two; test if new tree node data is valid for this tree.
****/

bool
DoesTreeExist(TreeData* pTD)	{

	if( pTD->FetchPointerToRoot() == NULL )	{
		return false;
		}
		else
		{
		TCHAR *szTreeNodeData = (pTD->FetchPointerToRoot())->FetchTreeNodeData() ;  
		if( (int)*szTreeNodeData <= 64  ||  (int)*szTreeNodeData >= 123 )	
			return false;
		}
return true;
	} // End FetchTreeData...
// ------------ END function DoesTreeExist -----------------
// *********************************************************


// *********************************************************
// ++++++++++ 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;

	while(1){
	??? If ( current node has left child && !( LLPf ) )  
				move to left child; 
				continue;
			else
			??? If ( !( LLPf ) 
					fetch current node data;
			
	??? 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; 
			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;
				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->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 );

// 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() ) ;		
		//	if( (pTD->FetchPointerLastNodeViewed())->FetchRightPointer() != NULL )
			//	pTD->SetPointerLastNodeViewed( ( pTD->FetchPointerLastNodeViewed() )->FetchRightPointer() ) ;
		}   // 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() ) ;
				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->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() ) ;		
		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. 
/*	if( pTD->FetchPointerLastNodeViewed() != pTD->FetchPointerToRoot() &&
			   pTD->FetchPointerLastNodeViewed()->FetchLeftPointer() == NULL &&
				  pTD->FetchPointerLastNodeViewed()->FetchRightPointer() == NULL &&
					 pTD->FetchPointerLastNodeViewed()->FetchLeftThreadPointer() == NULL && 
						!( pTD->FetchFlagUpThread() ) )	{	
			pTD->CatTNDtoCurrentTreeMembers( (pTD->FetchPointerLastNodeViewed())->FetchTreeNodeData() ) ;				
		} */   // End 'if' above... 
	break ;
		} // End of while... One Node to go... maybe..if last node is not root.
		   		
	int stop ;
  	stop = 1 ;

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

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