/*****************************
This file WinTreePosi.cpp  == Windows Last Left Threaded Data Tree Position new node in data tree. 
Holds the Windows Last Left Threaded Tree application "position"
This function is responsible for positioning a new node in the data tree.
*****************************/

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



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