/******************************************
This is the file WinTreeCreateTree.cpp == Windows Last Left Threaded Data Tree Create Tree. 
It holds functions that create a Last Left Threaded Data Tree
this tree is to be used for training and testing of the overall functionality 
of the Data Base Application.
******************************************/

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

// *********************************************************
// +++++++++++++ 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 application's entree node to the data structure.

TreeNode*
CreateTree()	{
     
     int i; // for loop counter.	
	  int iNum; // Subscript for szAlph array.    
     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.
     
    // Don't put the 'randomize()' function in the
	//  'while' loop.  If you do you will be reinitalizing
  //   the seed every time...
	  
	  srand( (unsigned)time( NULL ));  // Now seed is set.

// 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) {  // Will stay in 'while' loop till the bool flag fFull is set to TRUE.
						// 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 ;  // This TRUE maks sure we only do one root.
         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 ---------------
// *********************************************************