Anna Becker
Software Engineer

Game Engine – PCS Tree

The first assignment this term was a parent/child/sibling tree. Each node had a pointers for a parent, child and sibling. That meant the siblings were a singly linked list which made things a bit tricky down the line. We were given a bare bones project with the PCS class and unit test. The point was to make all the functions actually do something (properly) so the tests would pass.

Setup:
While I knew the tests would fail, I honesty didn’t think it would blow up as it did:

The application has failed to start because its side-by-side configuration is incorrect.

That’s helpful! Thanks windows! Cheeky shit. So I go to the event log…

Activation context generation failed for “…PA1.exe”. Dependent Assembly Microsoft.VC90.DebugCRT, processorArchitecture=”x86″, publicKeyToken=”1fc8b3b9a1e18e3b”, type=”win32″, version=”9.0.21022.8″ could not be found.

My google-fu first tells me to install Microsoft Visual C++ 2005 Redistributable Package, which is odd since I already have it. Figured it couldn’t hurt so went ahead and tried that. Nope. Further digging, which isn’t a lot out there, I keep seeing references to Visual Studio 08. Odd I think since I’m using 10. Eventually come to an old posting that mentions installing 08. I grab a copy from MSDNAA, because I’m all out of ideas. The next day someone started a discussion and the best response was: You don’t need to install VS2008. Just open Project Properties and go to Linker > Manifest File, switch Generate Manifest to No.

Did I mention I’m too stubborn to ask (other than google) until I’ve tried everything? Something about proving that an old art nerd can in fact think with the other side of her brain again. Or maybe it’s a lady problem. I can do maths! Probably more likely though is that I remember more by fixing it myself.

Coding begins:
Most of it was pretty straight forward tree building stuff. It’d been a while since I’d dealt with trees and I’m pretty sure I’ve never actually written one.

Recursion and I have never been friendly. Spending most of my life in tangible ideas – photography and film – my brain gets stuck on the abstract concepts. For instance, it used to be that I wanted to punch whomever thought up pointers. That is until I took Computer Systems 2 where I figured out that sometimes you want to manipulate something while keeping the original in tact. All of a sudden, it clicked and I haven’t had a problem with them since.

I understand that recursion (if done on the right things) will speed up the run time. Divide and conquer and all that. But it takes me so long to see what it’s doing, tracing it out, and holy fuck the debugging nightmare it gives me.

Remove:
We were supposed to remove (not delete) the node and all of it’s children. This I spent quite a bit of my time on drawing, writing and rewriting.

//Remove a node and all of it's children. Remove the node.
 void PCSTree::remove(PCSNode * const inNode)
 {
    PCSNode *prevSibling = 0;
    PCSNode *child = inNode->getChild();
    PCSNode *sibling = inNode->getSibling();
 
    if(inNode != this->root)
    {
       PCSNode *parent = inNode->getParent();
 
       //find the previous sibling
       prevSibling = parent->getChild();
 
       if(prevSibling != inNode)
       {
          while(prevSibling->getSibling() != inNode)
          {
             prevSibling = prevSibling->getSibling();
          }
          prevSibling->setSibling(sibling);
       }
       else
       {
          //attach parent node to sibling
          parent->setChild(sibling);
       }
 
       //null pointers
       inNode->setParent(0);
       inNode->setSibling(0);
    }
 
    else
    {
       root = 0;
    }
 
    removeHelper(inNode);
    info.numLevels = this->getLevel(root);
 }
 
//remove all of the children.
 void PCSTree::removeHelper(PCSNode * const inNode)
 {  
    PCSNode *child = inNode->getChild();
    PCSNode *sibling = inNode->getSibling();
 
    while(child != 0)
    {
       remove(child);
       child = inNode->getChild();
    }
 
    while(sibling != 0)
    {
       remove(sibling);
       sibling = inNode->getSibling();
    }
 
    if(child == 0 && sibling == 0)
    {
       info.numNodes--;
    }
 
 }

Get Level:
The point here is to get the height of the tree – the amount of steps from root to the lowest node. It was another tricky one due to the singly linked list for siblings. Once I got it to not crash, I figured out that it wasn’t hitting all the siblings. Figuring it out really got me to learn how to debug a recursive function.

int PCSTree::getLevel(PCSNode * const inNode)
{
   int max = 0;
   int height = 0;
 
   if(inNode == NULL)
   {
      return 0;
   }
   else
   {
      PCSNode *child = inNode->getChild();
      PCSNode *sibling = inNode->getSibling();
      PCSNode *siblingChild;
 
      if(child == 0 && sibling == 0)
      {
         return 1;
      }   
      if(child != 0)
      {       
         height = this->getLevel(child);
         if (height > max)
         {
            max = height;
         }
      }
 
      while(sibling != 0)
      {
         siblingChild = sibling->getChild();
         if(siblingChild != 0)
         {
            height = this->getLevel(siblingChild);
            if (height > max)
            {
               max = height;
            }
         }
         sibling = sibling->getSibling();
      }
 
   }
      return max +1;
}

Leave a Reply

Your email address will not be published. Required fields are marked *