/******************************************
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 "WinTree.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]={{L"A\0",L"N\0"},{L"B\0",L"N\0"},{L"C\0",L"N\0"},{L"D\0",L"N\0"},{L"E\0",L"N\0"},{L"F\0",L"N\0"},
		  {L"G\0",L"N\0"},{L"H\0",L"N\0"},{L"I\0",L"N\0"},{L"J\0",L"N\0"},{L"K\0",L"N\0"},{L"L\0",L"N\0"},{L"M\0",L"N\0"},{L"N\0",L"N\0"},
		  {L"O\0",L"N\0"},{L"P\0",L"N\0"},{L"Q\0",L"N\0"},{L"R\0",L"N\0"},{L"S\0",L"N\0"},{L"T\0",L"N\0"},{L"U\0",L"N\0"},{L"V\0",L"N\0"},
		  {L"W\0",L"N\0"},{L"X\0",L"N\0"},{L"Y\0",L"N\0"},{L"Z\0",L"N\0"},{L"a\0",L"N\0"},{L"b\0",L"N\0"},{L"c\0",L"N\0"},{L"d\0",L"N\0"},
		  {L"e\0",L"N\0"},{L"f\0",L"N\0"},{L"g\0",L"N\0"},{L"h\0",L"N\0"},{L"i\0",L"N\0"},{L"j\0",L"N\0"},{L"k\0",L"N\0"},{L"l\0",L"N\0"},
		  {L"m\0",L"N\0"},{L"n\0",L"N\0"},{L"o\0",L"N\0"},{L"p\0",L"N\0"},{L"q\0",L"N\0"},{L"r\0",L"N\0"},{L"s\0",L"N\0"},{L"t\0",L"N\0"},
		  {L"u\0",L"N\0"},{L"v\0",L"N\0"},{L"w\0",L"N\0"},{L"x\0",L"N\0"},{L"y\0",L"N\0"},{L"z\0",L"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]=L"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( wcscmp( szAlph[iNum][0], szAlph[i][0] ) == 0 ) {		
			if( wcscmp( szAlph[iNum][1], L"N\0" ) == 0 ) {  // *szAlph[iNum][i] by de-referencing the pointer, conversion 
				szAlph[iNum][1]=L"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( wcscmp(szAlph[i][1], L"N\0") == 0  )		{ // wcscmp (a1, a2) if a1==a2 wcscmp 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 ---------------
// *********************************************************