Starting a new programming course!

By: Anthon Fredriksson / November 14, 2014 /
Program: Programming
/ No Comments

So I have started this new course called Gameprogramming III. It feels good to start coding after a few months of game design.

We started of the week by creating a BMP compressor in C++ just to get into programming again. We had to compress a bitmap image file to the smallest possible size. I got down to ~10 KB. It was really fun to work with that. I got to work on the binary level which is pretty new for me. I´ve uploaded the code to my repository for anyone to look at.

I have also finished my first game programming assignment which was to create a linked list and a binary search tree. I will not explain what that is because other sources provides better explanation but I will explain other things amongst that.

For both the linked list and the binary search tree I used the new feature in C++11 called initializer_list. It is a way of initializing with an array of objects. Since the oh so famous std::vector uses it I wanted to give it a try and it was so much easier that I expected. I only had to create a different constructor with a parameter of a std::initializer_list reference and use that list to insert elements one by one in the linked list or the binary search tree.

template
LinkedList::LinkedList(const std::initializer_list &list)
{
        for (std::initializer_list::iterator it = list.begin(); it != list.end(); ++it)
        {
                push_back(*it);
        }
}
 
// and then use it like this
LinkedList list = { 1, 5, 3, 8 };
list.size(); // size = 4

I will use this method to intialize containers from now on.

I got one more thing that I like to brag about and it is a feature I added in the binary search tree.
Most binary search trees that deletes a node with two children is swapping the node to be deleted with its successor or predecessor I implemented a way of not swapping any values but instead swapping all of the references.
Take this image for example.

Say I want to delete node 3 and then I choose to replace it with its successor which is node 4. So as I said before, most implementations swap their values with each other and then delete the successor. What I do is to take the entire node 4 and change every connection from/to node 3 and put it on node 4 and then take all connections to/from node 4 and reroute them to appropriate places. Let go through this step by step.

In this example I have to:

  • Find node 3´s successor which is 4.
  • Point node 6 left reference to null.
  • Point node 8 left reference to node 4.
  • Point node 4 left reference to node 1.
  • Point node 4 right reference to node 6.

Now node 3 has no connection to any node or from any node, it it safe to deallocate its memory and remove the node. This implementation does however come with a few edgecases where the successor might have children. Then you have to route those children to whatevery node that is pointing to the successor. Here is my kickass delete function for anyone to inspect.

The advantages of this is method instead of swapping values is that it is more performance friendly when storing large values in nodes because then you don’t have to allocate a new variable when you perform the swap. But for when storing small things like integers or chars, there is nearly no difference. I do actually allocate a few bytes for some pointers here and there but it is like 4 temp pointers so it is not a big problem.

While I could just make the swap implementation I wanted to test myself and I had really fun doing this.

// Doodlemeat

About Anthon Fredriksson

2013 Programming
Tags: 2013