A journey thro' India, I have never seen!

There are Millions of Ruskin Bond fans now I know why?.....I am the latest addition.

It all started with....

Room on the roof... a start that is so Indian, the way Rusty met Somi, it took me back to my childhood days where making friends was so easy,  no pretensions , no inhibitions just a care free attitude...I liked the intense friendship/concern he shared with Kishen a spoilt brat. 
Most important thing for me is the way I am acquainted to Dhera I have never seen it but I felt like I have lived there with Rusty visiting the Bazaar, the clock tower ... Kapoor's banglow and yes Rusty's room .

The book just gripped me, I felt an impatient urge to buy the next book "Vagrants of the Valley" I was curious about what happens next...I could not wait. Thanks to FlipKart I ended up buying Ruskin Bond - Complete and Unbridged which had six novels.


# The Room on the Roof
# Vagrants in the Valley
# Delhi Is Not Far
# A Flight of Pigeons
# The Sensualist
# A Handful of Nuts

let us say I went on a rampage I guess that is the effect of the first book.Since then I felt like Ruskin held my hand and took me on a journey thro' Uttarakhand/UP which I have never seen some of them intensely emotional, of all the stories I still feel "Vagrants of the valley" is very very good  the point where Rusty's late father helps him to get to England by leaving some very simple yet valuable possessions, getting to know about his father from Mr Pettigrow should have brought varied thoughts about a father of whom he had seen very little.His friendships with kishen, Hathi, lafunga, devinder  and who can forget the gooonga!!.

It has been truly a fascinating , evocative and enchanting journey through the small towns, far away mountains ,forests, the ghats on river ganga even thought it was done with all the comforts of my bedroom.


I will not be able to write more on all the other novels but enjoyed reading "Flight of the Pigeons"(thrilling account of Indian Sepoy Mutiny),"Sensualist", and in the "Handfull of nuts", I am still guessing who the bollywood actor is? the character's name is Sitaram in the novel :-).
 
That is it for now....!

Tree Traversals

I had  recently written a small basic program on various tree traversal methods and ways to build a tree give Pre-order,Post-order and In-order here is the complete code snippet for the same.

//----------------------------------------------------------------------------------------

int In[17]   = {75,24,27,39,73,43,91,14,8,70,87,99,9,25,0,45,13}; /* In   Order  */

int Pre[17]  = {8,14,39,24,75,27,43,73,91,45,9,87,70,99,25,0,13}; /* Pre  Order  */

int Post[17] = {75,27,24,73,91,43,39,14,70,99,87,0,25,9,13,45,8}; /* Post Order  */

//----------------------------------------------------------------------------------------

int iLastIndex = 16;

class TreeNode

{

public:

      TreeNode* pLeft;

      TreeNode* pRight;

      int data;

/*This variable(index) is used only while building a tree using iteration*/

      int index;

};

TreeNode* pRoot=NULL;

TreeNode* makeNode()

{

      TreeNode* pNode =  new TreeNode();

      pNode->pLeft=NULL;

      pNode->pRight=NULL;

      return pNode;

}

int findNewRtIndex(int data)

{

      for(int i=0;i<=iLastIndex;i++)

      {

            if(In[i] == data )

            {

                  return i;  

            }

      }

}

void AddToTree(TreeNode* pParent , TreeNode* pNode)

{

     

      if(pNode->index <= pParent->index)

      {

            if(pParent->pLeft!=NULL)

                  AddToTree(pParent->pLeft,pNode);

            else

                  pParent->pLeft=pNode;

      }

      if(pNode->index > pParent->index)

      {

            if(pParent->pRight!=NULL)

                  AddToTree(pParent->pRight,pNode);

            else

                  pParent->pRight = pNode;

      }

}

/*

This function tries build a tree using the Pre-order and In-Order   Traversals without Recursion.

This is a a nice function in the sense that it builds the tree based on the index instead of the actual Pre/In order traversals, It needs and additional member variable called index for the same purpose.

*/

void makeTreeWithPreAndInUsingIteration(int iEndIndex)

{

      TreeNode* pNode=NULL;

      pRoot = makeNode();

      pRoot->data = Pre[0];

      pRoot->index =  findNewRtIndex(Pre[0]);

      for(int i=0;i<=iEndIndex;i++)

      {

            int iInIndex =  findNewRtIndex(Pre[i]);

            pNode = makeNode();

            pNode->index = iInIndex;

            pNode->data = Pre[i];

            AddToTree(pRoot,pNode);

      }

}

/*This function tries build a tree using the Pre-order and In-Order Traversals using Recursion*/

void makeTreeWithPreAndIn(TreeNode* pNode,int iStIndex,int iEndIndex)

{

     

      static int iCurIndex = -1;

      int iNewRtIndex =-1;

      if(iStIndex>iEndIndex)

            return;

      if(iCurIndex==-1)

      {

            iNewRtIndex =  findNewRtIndex(Pre[0]);

            iCurIndex =0;

            pRoot = makeNode();

            pRoot->data = Pre[0];

            pNode =  pRoot;

            pNode->pLeft  =  makeNode();

            pNode->pRight =  makeNode();

      }

      else

      {

            iNewRtIndex = findNewRtIndex(Pre[++iCurIndex]);

           

            pNode->data   = In[iNewRtIndex];

            pNode->pLeft  =  makeNode();

            pNode->pRight =  makeNode();

           

      }

      if(iStIndex==iEndIndex)

            return;

      makeTreeWithPreAndIn(pNode->pLeft,iStIndex,iNewRtIndex-1);

      makeTreeWithPreAndIn(pNode->pRight,iNewRtIndex+1,iEndIndex);

}

/* This function tries build a tree using the Post-order and In-Order Traversals using Recursion*/

TreeNode* makeTreeWithPostAndIn(int iStIndex,int iEndIndex)

{

      static int iCurIndex = -1;

      TreeNode* pNode=NULL;

      int iNewRtIndex =-1;

      if(iStIndex>iEndIndex)

            return pNode;

      if(iCurIndex==-1)

      {

            iNewRtIndex =  findNewRtIndex(Post[iLastIndex]);

            iCurIndex = iLastIndex;

            pRoot = makeNode();

            pRoot->data = Post[iLastIndex];

            pNode =  pRoot;

           

      }

      else

      {

            iNewRtIndex = findNewRtIndex(Post[--iCurIndex]);

            pNode = makeNode();

            pNode->data   = In[iNewRtIndex];

           

      }

      if(iStIndex==iEndIndex)

            return pNode;

     

      pNode->pRight = makeTreeWithPostAndIn(iNewRtIndex+1,iEndIndex);

     

      pNode->pLeft = makeTreeWithPostAndIn(iStIndex,iNewRtIndex-1);

      return pNode;

}

/* This function does Pre-order traversal of the tree using iteration.*/

void IterativePreOrderTraversal()

{

      std::stack<TreeNode*>   stck;

      stck.push(pRoot);

      while(!stck.empty())

      {

            TreeNode* pNode  =(TreeNode*)  stck.top();

            stck.pop();

            if(pNode->pRight!=NULL)

            {

                  stck.push(pNode->pRight);

            }

            if(pNode->pLeft!=NULL)

            {

                  stck.push(pNode->pLeft);

            }

            cout<<pNode->data<<endl;

      }

}

/* This function does Post-order traversal of the tree using iteration.*/

void IterativePostOrderTraversal()

{

      std::stack<TreeNode*>   stck;

      stck.push(pRoot);

      while(!stck.empty())

      {

            TreeNode* pNode  =(TreeNode*)  stck.top();

            stck.pop();

           

            if(pNode->pLeft!=NULL)

            {

                  stck.push(pNode->pLeft);

            }

            if(pNode->pRight!=NULL)

            {

                  stck.push(pNode->pRight);

            }

            cout<<pNode->data<<endl;

      }

}

/* This function does In-order traversal of the tree using iteration.*/

void IterativeInOrderTraversal()

{

      std::stack<TreeNode*>stck;

      stck.push(pRoot);

      TreeNode* pNode = pRoot;

      while(!stck.empty())

      {

            if(pNode!=NULL)

            {

                             

                  stck.push(pNode);

                  pNode = pNode->pLeft;

                  continue;

            }

            else

            {

                  if(!stck.empty())

                  {

                        pNode = (TreeNode*) stck.top();

                        stck.pop();

                        if(!stck.empty())

                        {

                              cout<<pNode->data<<endl;

                              pNode = (TreeNode*)pNode->pRight;

                        }

                        else

                              break;

                 

                  }

                  else

                        break;

            }

           

      }

}

int _tmain(int argc, _TCHAR* argv[])

{

      //makeTreeWithPreAndIn(NULL,0,16);

      cout<<"-------------------------------------------"<<endl;

      //makeTreeWithPostAndIn(NULL,0,16);

      pRoot = makeTreeWithPostAndIn(0,16);

      cout<<"-------------------------------------------"<<endl;

      //makeTreeWithPreAndInUsingIteration(16);

      cout<<"-------------------------------------------"<<endl;

      IterativePreOrderTraversal();

      cout<<"-------------------------------------------"<<endl;

      IterativePostOrderTraversal();

      cout<<"-------------------------------------------"<<endl;

      IterativeInOrderTraversal();

      cout<<"-------------------------------------------"<<endl;

      return 0;

}

Perils of using W2A

Ever wondered why W2A leaks a lot of memory when used in a loop?

for(int i=0;i<count;i++)

{

      str= W2A(bstr);

      cout<<str<<endl;

           

}

When we try and step in at W2A we end up with following ASM code.

*********************************************************************************

_alloca_probe_16 proc                   ; 16 byte aligned alloca

        push    ecx

        lea     ecx, [esp] + 8          ; TOS before entering this function

        sub     ecx, eax                ; New TOS

        and     ecx, (16 - 1)           ; Distance from 16 bit align (align down)

        add     eax, ecx                ; Increase allocation size

        sbb     ecx, ecx                ; ecx = 0xFFFFFFFF if size wrapped around

        or      eax, ecx                ; cap allocation size on wraparound

        pop     ecx                     ; Restore ecx

        jmp     _chkstk

***********************************************************************************

What we see here is the stack is resized as in, W2A does an allocation on the stack
      so what would happen when this goes in a loop? obvious answer would be, the stack
      grows, and ends up with Stack Overflow problem.

So we end up with a couple of questions..

1.What is the best way takle this problem.

2.Are there any alternatives.
      3.Why USES_CONVERSION MACRO when we use W2A.

1.One way is to manually convert it CString like this function MyW2A
  does.

CString MyW2A(BSTR bstr)

{

      CString s;

      If(bstr!=NULL)

{

      LPSTR p = s.GetBuffer(SysStringLen(bstr) + 1);

      ::WideCharToMultiByte(CP_ACP,           

                                      0,                

                                      bstr,                 

                                      -1,                // assume NUL-terminated

                                      p,                

                                      SysStringLen(bstr)+1,

                                      NULL,             

                                      NULL);            

      s.ReleaseBuffer();

      }

      return s;

}//MyW2A
     

JNM(Joseph NewComer) has a very good article on String management here

http://www.flounder.com/cstring.htm

      2. CW2A which has been provided as part of ATL 7.0 can be used instead of W2A,
                another cool thing about this is, USES_CONVERSION is not required for CW2A.

3. Why do we need, USES_CONVERSION MACRO when we use W2A?

   The answer lies in Atlconv.h file and the way these macros have been defined.

  

/*
*where is the _lpw defined?
*where is _convert defined?
*where is _acp defined?
*/

   #define W2A(lpw) (\

      ((_lpw = lpw) == NULL) ? NULL : (\

            (_convert = (lstrlenW(_lpw)+1), \

            (_convert>INT_MAX/2) ? NULL : \

            ATLW2AHELPER((LPSTR) alloca(_convert*sizeof(WCHAR)), _lpw, 
   _convert*sizeof(WCHAR), _acp))))

/*

* U guessed it right? Look at the definition of USES_CONVERSION
* Simple right!!!
*/

#define USES_CONVERSION int _convert = 0; (_convert);\
UINT _acp = ATL::_AtlGetConversionACP() /*CP_THREAD_ACP*/;\
(_acp); LPCWSTR _lpw = NULL; (_lpw); \
LPCSTR _lpa = NULL; (_lpa)

Another clue would be when we compile without the USES_CONVERSION macro, we end up with the following errors.

1>c:\..\vc days\.....\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_lpw' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_convert' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_lpw' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_convert' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_convert' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_lpw' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_convert' : undeclared identifier

1>c:\..\vc days\......\w2atest\w2atest\w2atest.cpp(45) : error C2065: '_acp' : undeclared identifier