Alexandrescu to the rescue

(Reader Level : Intermediate)
(Knowledge assumptions : templates, std::vector, std::string)
I've recently taken a fancy to Andrei Alexandrescu's Modern C++ design. Its a fabulous book and anyone who is serious about becoming a good C++ programmer ought to read it. However, the book is not for the novice or the faint of heart. Someone on CodeGuru even suggested that the reader wear a helmet while reading this book so that his/her brain would not explode!

Now let me tell my story...
I was writing a string tokenizer in C++. The basic idea was to split a parse string into tokens using another string as the delimiter. The resultant token strings can be returned as a vector of strings.

std::vector<std::string> Tokenize( const std::string& str, const std::string& delimitStr )
{
 std::vector<std::string> result;
  //////Rest of the code goes here...//////////

  return result;
}

Seems pretty sensible, right? Now here's the problem. What if I wanted to give the user the power to specify what kind of STL container he/she wanted to use. Perhaps, a list would be more pertinent, or maybe a deque. In order to do that the Tokenize() function needs to be templated. So here was my first attempt..

template<class Container>
Container Tokenize( const std::string& str, const std::string& tokenStr )
{
 Container result;
  //////Rest of the code goes here...//////////

  return result;
}

Alright, that seems nice enough and the user would have to call this Tokenizer() routine as:

Tokenize<std::list<std::string> >( "breakmeintoathousandpieces", "e" );

Unfortunately, that's redundant because we know that the result is a container of string tokens. Furthermore, the user should not be given the opportunity to misuse the algorithm by specifying something other than std::string for the template argument. It should be fair to simply say:

Tokenize<std::list>( "breakmeintoathousandpieces", "e" );

That won't work however because then the container type would be incomplete. I was wondering how to resolve this problem when it hit me! The use of Template Template Parameters was illustrated for designing Policy classes in Modern C++ Design. It suited my purpose wonderfully!
This is what my revised Tokenizer() function looked like:

template< template<class> class Container >
Container<std::string> Tokenize( const std::string& str, const std::string& tokenStr )
{
 Container<std::string> result;
  //////Rest of the code goes here...//////////

  return result;
}

This example was just to illustrate the use of template template parameters. As Alexandrescu so beautifully put it - "It is as if WidgetManager (the class he templated) were a little code generation engine, and you configure the ways in which it generates code."

If you really have a solid reason to tokenize anything complex, of course, I would recommend using Boost::Tokenizer.

Sorting Stuff with Heap Sort - Part III

In part I and II of this series, we learnt about Heap Sort and how to construct a heap out of unsorted data. Now, let's move on. Once the heap is constructed, we need to sort it.

You might have noticed that the SIFT function takes a heap size as one of its arguments. If the SIFT function already knows what heap it is working on, why would it be necessary to pass in the heapSize separately? The reason is that SIFT doesn't have to sift a node through the entire heap. It can work with a smaller part of the heap. In the HEAPIFY routine, everytime we invoked SIFT, we passed a constant heap size to it but we would like to be able to specify a smaller heap size if we want. We'll see the reason for this soon.

We already know that the top-most node in any heap is the largest value. In order to sort the heap, what we do is swap the top node (or in other words the 0th element in the list) with the last node in the heap (the element whose index is inputDataList.length()-1). Now our largest value is at the bottom of the heap. Next, we reduce the size of the heap to be sorted and sift the top-most node using the reduced heap size as an argument. The top node, of course, has to be sifted so that we get a proper heap again. We keep swapping and sifting until the size of the heap to be sorted becomes zero.

The following algorithm performs sorting of a heap:

1. i = inputDataList.length()-1
2. while(i > 0)
{
3. SWAP(0, i)
4. SIFT(0, i)
5. i = i - 1
}

That's all there is to it. Here's some C++ code that I had written to augment this series. If the algorithms I've provided seem a bit vague, feel free to look at the code here. Also, check out this nice Heap Sort visualization here.

Firefox Download Day

This post is a slight digression but you could think of it as a news update... I've just been informed along with some 21,000 odd Indians out there that the download day for Firefox is June 17th. I see a lot of Internet Explorer users blissfully using the worst browser that exists for a single platform - Windows! Firefox is free of charge, more secure, well-featured and open-sourced. What can IE do that Firefox cannot? The answer is nothing. So, then why use something that is second-rate? It's not that you have to shell out a packet to use Firefox. It's absolutely free! I guess, the only reason IE still exists is because it comes for free with Microsoft Windows.

Hopefully when Firefox 3 sets a world record for the most software downloaded in a 24-hour period, more web-users will sit up and take notice. We are a country with the second largest population in the world. Let's prove that we are also willing to embrace a future of free and open-source software by participating in this important event.

On a side-note, I wouldn't recommend any NIN fan opening http://remix.nin.com with IE6.

Sorting Stuff with Heap Sort - Part II

Why do we call it ‘Heap’ sort?
Heap sort begins by building a heap of the data. A heap can be visualized as a binary tree where each parent node is greater than its successors. In practice, the heap can easily be represented by a simple array where the left and right children of the i^th node in the array will be at positions 2*i+1 and 2*i+2 respectively. For example, the following is a heap:

This heap above can be represented using an array as follows:

Note that the i^th element has the (2i+1)^th and (2i+2)^th elements as its children. The fact that the heap can be represented like this means that we can do an in-place sort without having to construct an entirely new data structure for storage. There are a couple of interesting features of the heap which are to be noted:

1. Each node is greater than its successors (for sorting in ascending order).
2. By virtue of (1), the largest node will always be on top of the heap.

Now that we know what the heap is, let’s see how we can generate such a heap out of unsorted data.

Building the Heap.
Before we talk about building a heap, we must first discuss a sifting procedure. The sifting procedure basically sifts a given node downward through the tree until it reaches its rightful place in the tree. I may keep using the term ‘node’ simply because its easier to visualize things that way but remember that in practice, a node is nothing but an element in a list. The sifting algorithm is pretty straight-forward.

Procedure SIFT(int siftNode, int heapSize)
1. Start with the position of the node to be sifted.
2. If either of the sift node’s children are larger than it, then swap the sift node with the larger of its children.
3. If neither of the sift node’s children are larger than it or the end of the heap has been reached then exit.
4. Otherwise, go to step 2.

Using the sift procedure, we can easily build an initial heap out of seemingly unsorted data. We start with the last node in the tree or in other words, the last element in the input data list. We then invoke our earlier sift procedure on this element. Then we move onto the previous element in the list and the cycle continues until we have sifted all of the elements in the list. The result will be a nice heap. For grasping the idea better, the following algorithm should suffice. Note that the algorithm assumes a zero based input data list.

Procedure Heapify()
1. siftNode = inputDataList.length()-1
2. while siftNode >= 0
 {
3. Invoke SIFT( siftNode, inputDataList.length() )
4. siftNode = siftNode – 1
 }

Sometimes, building an initial heap out of the input data is known as “Heapifying” the data. We are not done yet. The heap has to now be sorted and we'll see how that can be done soon. Until then, have a nice week!

Sorting Stuff with Heap Sort - Part I

I’m starting a small series of blog posts that will explain the Heap Sort algorithm in depth. I’ve noticed that this is an academic topic that few are willing to touch but I am! I hope you find this short series informative.

The Basics.
First, lets get through the basics of any sorting algorithm. A sorting algorithm is an algorithm that seeks to arrange the elements of a data structure (think, a simple List) in a particular order. In most cases, we prefer the elements to be sorted in either ascending or descending order. The efficiency of an algorithm can be measured in terms of its Time Complexity or Space Complexity. The term Time Complexity refers to the amount of time that an algorithm takes to process the input and produce the desired output. The term Space Complexity refers to the amount of space or memory that an algorithm takes to produce the expected result. Generally, the complexity of an algorithm (time or space) is expressed as a function of the size of the problem, n. This is known as the Big-Oh Notation. So, if we were to say that a sorting algorithm has a time complexity of O(n), it means that the algorithm will take a factor of 10 units of time to sort 10 values. If the complexity of the algorithm were O(n²), then it would take a factor of 100 units of time to sort 10 values. Note that I have said that the algorithm will take "a factor of" time because this factor would depend on the particular problem. For example, if we were sorting simple integers, we could expect this factor to be a lot less than if we were sorting strings. Also, the complexity of an algorithm can be specified for Best, Worst or Average case scenarios. A best case scenario for a sorting algorithm would, of course, be if the data were already sorted in the first place. A worst case for a sorting algorithm would arise if the data were arranged in a manner that is contrary to the working of the algorithm. Generally, a good algorithm is measured for its worst-case scenario but in some cases, we also consider the average case.

Heap Sort is an O(nLogn) time complexity algorithm. This is in stark contrast with other sorting algorithms such as Bubble Sort (the unjustifiably most famous sort) which has an average or worst case complexity of O(n²). In my next post, we will dive into the Heap Sort algorithm and find out the reason as to why its called Heap Sort in the first place.

Setting up Code::Blocks on Windows

This blog post is a how-to manual on how to set up Code::Blocks for Windows along with some other libraries such SDL and GTK+.

What is Code::Blocks?
Code::Blocks is an Integrated Development Environment(IDE) for C++. This means that it provides a convenient means for programmers to type and execute their programs. You will need to provide a compiler for any IDE and there are several C/C++ compilers for the Windows environment. Since, this walk-through is newbie oriented, I will simply assume that you do not have any particular compiler in hand.

Setting up Code::Blocks on Windows.
In order to set up Code::Blocks for your Windows OS, go to http://www.codeblocks.org/downloads/5 . You will see two setup files for Windows 2000/XP/Vista. The first setup assumes that you already have a compiler to use with the IDE. The second setup, comes with the MinGW compiler for Windows. Download this setup from its Sourceforge link. Once you've downloaded the file codeblocks-8.02mingw-setup.exe, then do a full install of the IDE. I'm going to assume that the selected installation path for the IDE is C:\Program Files\CodeBlocks. The installation is pretty straight-forward and there should not be any problems. Try creating a new Console Application using the Project Wizard.

Setting up Simple DirectMedia Library for Code::Blocks on Windows.
Setting up SDL for Code::Blocks is pretty easy. Download the SDL 1.2 development bundle from the direct link here. Untar the contents of the file. You should get a folder named something like SDL-1.2.13 and within that folder you should find folders named include, lib, bin etc. Code::Blocks expects to see the file SDL.h within the include folder but as of now, if you look inside the include folder, you will find another folder named SDL. Copy all the header files from within the SDL folder one level up to the include folder and delete the folder SDL. Then, copy the entire SDL-1.2.13 folder to C:\Program Files\CodeBlocks. Now, fire up Code::Blocks and try creating a sample SDL project using the Project Wizard. When asked to specify SDL's location, just provide the path as C:\Program Files\CodeBlocks\SDL-1.2.13. Hopefully, everything should go as planned.

Setting up GTK+ for Code::Blocks on Windows.
Setting up GTK+ for Code::Blocks is even easier. Download the GTK+ development bundle from the direct link here. This zip file is a tarbomb, so neatly unzip the contents of this file to a folder named gtk+-bundle-2.12.9. Copy this entire folder to C:\Program Files\CodeBlocks. Now try creating a new GTK+ project using the Project Wizard. When asked to specify GTK's location, just provide the path as C:\Program Files\CodeBlocks\gtk+-bundle-2.12.9.

const_iterator : Safety or Necessity?

(Reader Level : Beginner)
(Knowledge assumptions : const-correctness, std::vector, iterators)
A while back I asked a senior programmer a very naive but valid doubt.
"Are const iterators used only to enforce safety or are there cases where they could be absolutely necessary?"
In reply, this is what I got and the answer was clear.

#include <iostream>
#include <vector>

class A
{
private:
std::vector<int> _vector;

public:
void Init()
{
   _vector.push_back( 1 );
   _vector.push_back( 2 );
   _vector.push_back( 3 );
}

void Display() const
{
   for(std::vector<int>::const_iterator itr = _vector.begin(); itr != _vector.end(); ++itr)    
      std::cout << (*itr) << std::endl;
}
};

int main(int argc, char *argv[])
{
A a;

a.Init();
a.Display();

std::cout<<"\n\n";
return 0;
}

If we were to try replacing the const_iterator in the Display() function with a normal iterator, the code would simply not compile. This is because the Display() routine is itself const and hence, we must guarantee that no member functions are altered within it. A normal iterator cannot give such a guarantee but a const_iterator can.