Casting with Multiple Inheritance

(Reader Level : Intermediate)
(Knowledge assumptions : C++ casts, Multiple Inheritance)

The Question:
Given the classes:

struct A { int _aValue; };

struct B { float _bValue; };

class C : public A, public B { };

Consider the following statements:

C objC;

void *pC = &objC;

A *pA = reinterpret_cast<A*>( pC );

B *pB = reinterpret_cast<B*>( pC );

...

Are both pA and pB valid? Why or why not?

The Answer:
pA is valid. pB is invalid.

The Reason:
Many feel that the order in which base classes are inherited does not matter for multiple inheritance. However, in some cases, it does matter. This is one of those cases.

When creating an instance of C, its A subobject will be instantiated first and then its B subobject. This behaviour is due to the fact that C inherits from A first and then from B. The 'this' pointer of the A subobject will be at an offset of 0 bytes from the 'this' pointer of objC. On the other hand, the B subobject will be at an offset of 4 bytes from the 'this' address of objC. The displacement of 4 bytes is attributed to the integer member _aValue of class A.
The following diagrams should make things clear.



Now, what happens when you cast from a void* to A*? The compiler doesn't know that the actual type of pC is C*. So, it assumes that pA can point to the 'this' address of pC. That's fair because the A subobject of an instance of C will be at the starting address of objC. However, when making the cast from void* to B*, the compiler assumes that the B subobject is at the starting address of objC. That isn't true and hence, pB is invalid.

Corollary:
Now that we know why pB is invalid, let's see if we can correct it. Obviously, reinterpret_cast is ugly and unreliable.
Would a static_cast do any better?
Unfortunately, no. A static_cast works at compile time and as stated before the compiler doesn't know anything about the actual type of pC.
How about a dynamic_cast?
A dynamic_cast would nip our futile attempts in the bud by refusing to cast from void* to anything.

The take-home message:
reinterpret_cast is bad but void* is evil!

The three aspects of a successful Software Engineer

A wise person once told me that there are three aspects to a successful software engineer.

1. Attitude.
A person must have a good outlook and should always strive to do the best that he/she can. That defines attitude. A bad attitude could be attributed to the work environment (colleagues, work interest, monetary satisfaction, bosses etc.) but a good software engineer will try not to let such annoyances affect him.

2. Motivation.
Motivation means having a reason to do things. It gives a person a purpose and goal. If the odds are stacked against a person, then he/she must rise to the occasion.

3. Ability.
Ability involves the capability of a person. The ability of a software engineer is determined by the skills in his/her domain of expertise.

Now, here’s the interesting part. The aforementioned facets of a software engineer must go in that order of precedence. By having a good attitude and an “Up and at ‘em” disposition, one can discover motivation. Once a software engineer finds a reason to do something, then he/she will not quit until the job has been done and done well. A good attitude and proper motivation will naturally make a person pay attention to trivial details. It will make him or her push forward beyond normal limits and that’s what garners ability. An individual could be born with great skill but that could be put to little use unless he/she develops a good attitude.
Laugh in the most trying of times, never give up even if the chips are down and show others respect irrespective of whether you like them or not. That’s what a healthy attitude demands.

Eliminate duplicate elements from a container

(Reader Level : Intermediate)
(Knowledge assumptions : templates, STL)

One of the grandest things about STL is that it keeps us from re-inventing the wheel. In a practical world, it just doesn't make sense for a developer to create a doubly linked list or a queue from scratch. We have STL containers for that purpose. However, with great knowledge comes great responsibility. Its important to know what STL does under the hood, rather than just using it blindly. A lot of books out there have covered this topic but one of the most important ones that springs immediately to mind is The C++ Standard Library - A Tutorial and Reference by Nicolai M. Josuttis.

Enough of the prologue... Let's get down to a problem. There are times when one might have a container with duplicate element values. Whether such a scenario is justifiable or not may depend on a number of things. The first thing, we need to look into is the container itself and ask ourselves - "Is this the right container for the job? Why not use an std::set or an std::map instead?" If redesigning our code to use a more suitable container isn't a viable solution, then read on.

template<class ContainerType>
void RemoveDuplicates( ContainerType& input )
{
 ContainerType::iterator currentPosIter = input.begin();
 currentPosIter;

 for( ContainerType::iterator iter = input.begin(); iter != input.end(); ++iter )
 {
   if( std::find( input.begin(), currentPosIter, *iter ) == currentPosIter )
   { 
     *currentPosIter = *iter;
     ++currentPosIter;
   }
 }

 input.erase(currentPosIter, input.end() );
}

The above function removes duplicates from any STL container as long as that container supports an erase method. Let's take it for a test drive, shall we?

std::deque<int> myDeque;

//Add some values to the deque.
myDeque.push_back(0);
myDeque.push_back(1);
myDeque.push_back(1);
myDeque.push_back(0);
myDeque.push_back(2);
myDeque.push_back(2);
myDeque.push_back(3);
myDeque.push_back(1);

//Before erasing duplicates.
std::cout << "Before erasing duplicates." << "\n";
std::copy( myDeque.begin(), myDeque.end(), std::ostream_iterator<int>( std::cout, "\n" ) );
std::cout << "\n\n";

RemoveDuplicates<std::deque<int> >( myDeque );

//After erasing duplicates.
std::cout << "After erasing duplicates." << "\n";
std::copy( myDeque.begin(), myDeque.end(), std::ostream_iterator<int>( std::cout, "\n" ) );

Template Parameter friends

(Reader Level : Intermediate)
(Knowledge assumptions : templates, friend)

The problem:
Currently, the C++ standard does not allow you to write code like this:

template<class T1, class T2>

class MyClass
{
  friend class T1;
  friend class T2;
};

You can’t make the template parameter of a class be a friend of that particular class. This might seem a reasonable requirement but the language does not allow you to do this, at least not directly.

The workaround:
In order to accomplish what we require here’s a quick workaround.

For the GCC compiler:-

#define MAKE_FRIEND(T) friend class MakeFriend<T>::Result

template<class T>
class MakeFriend
{
public:
  typedef T Result;
};

template<class T1, class T2>
class MyClass
{
 MAKE_FRIEND(T1);
 MAKE_FRIEND(T2);
};

For Microsoft's compiler:-

#define MAKE_FRIEND(T) friend MakeFriend<T>::Result

template<class T>
class MakeFriend
{
public:
  typedef T Result;
};

template<class T1, class T2>
class MyClass
{
 MAKE_FRIEND(T1);
 MAKE_FRIEND(T2);
};

Note the use of the 'class' keyword in the MAKE_FRIEND macro for the GCC compiler but not for the Microsoft compiler. If either T1 or T2 is not a class, then your compiler will complain. For example, if you try to instantiate an object with:

MyClass<SomeClass, int> myClassObj;

then the GCC compiler will say error: invalid type ‘int’ declared ‘friend’. But that makes sense, doesn’t it?

The code above has been tested on GCC 3.4.5 and on Microsoft Visual Studio 2008 (using the Microsoft Compiler).

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.

Movie Review: Into The Wild

Normally I'm an action junkie when it comes to movies, so its funny that 'Into the Wild' was not an action flick. The basic plot is as follows: After graduating from Emory University, top student and athlete Christopher McCandless abandons his possessions, gives his entire $24,000 savings account to charity and hitchhikes to Alaska to live in the wilderness. Along the way, Christopher encounters a series of characters that shape his life.

Seems pretty boring, right? That's what I thought when I read the plot summary on IMDB but I watched the movie anyway. It turns out that I was wrong and the movie offers some great insights into the philosophy of life and the spirituality that one can gain through adventure. This film is based on a book by Jon Krakauer who wrote about the true exploits of an American wanderer named Chris McCandless. At the end of the movie, you may become a bit cynical (as I did) due to certain developments in the plot. Then I remembered that this is an actual true story and that I was entirely missing the take home message. At any rate, whether you like or dislike this film, you are sure to have several opinions about it. To give it credit, Into the Wild won the 2007 Golden Globe Awards and was also nominated for the Academy Awards. It has also received favourable reviews from most movie critics. The acting, in my humble opinion, was top notch. Emile Hirsch (of Alpha Dog fame) plays McCandless and does a pretty good job. The film was directed by Sean Penn who was also involved in production as well as screenplay. One of the biggest assets of the film is probably its great soundtrack. The music is truly beautiful and it keeps you in touch with each scene. Don't google anything about the film until you've actually watched it. Otherwise you're just ruining the whole experience!

Some links to check out AFTER you've watched 'Into The Wild':
Wiki on Chris McCandless
Official film site

Creating a custom GRUB bootsplash

Creating your own GRUB bootsplash image does not require you to be an artist or an image-editing wizard. It's very easy.
Every GRUB bootsplash image must have the following characteristics:
a) Image format must be of the xpm format. GRUB will load compressed images even faster.
b) Image resolution must be 640x480, irrespective of whether your monitor is widescreen or not.
c) Image can only have a maximum 14 colours. No more.

Armed with these facts, let's go ahead and try to create our own bootsplash image. The image editing software that I am going to use for this purpose is the GIMP (GNU Image Manipulation Program).
First, pick out an image that you really like. The format doesn't matter at this point. It can be jpg, bmp, png, anything you like.

Now open the image in GIMP. Resize the image to a 640x480 resolution. Go to Image->Scale Image and set Width to 640 and the Height to 480. You can tweak the other settings in the same dialog if you want. After that click on the Scale button.

Next we need to make our image only have a maximum of 14 colours. So, go to Image->Mode->Indexed. Click on the Generate optimum palette radio button and set the Maximum number of colors to 14. Now we probably have a pretty ugly looking image. :)

Finally, save the image with extension xpm. You could call it something like bootsplash.xpm. Alright, we've got our image. Let's compress it. Open up a terminal and navigate to the folder where you saved bootsplash.xpm using the cd command. Then type:

gzip bootsplash.xpm

The gzip utility will compress our image and its name gets changed to bootsplash.xpm.gz. That's it! We're done. You can now set it as your new GRUB bootsplash. Enjoy!

By the way, this is what my own GRUB bootsplash looks like.

Mess around with your GRUB menu

GRUB stands for GRand Unified Bootloader. I don't know why, but someone thought that it would be a funny play on the term "Grand Unification Theory" in physics. Essentially, GRUB is a bootloader program that loads when you boot into your PC. Using the GRUB menu, you can then pick your operating system of choice (if you happen to have more than one). I've been using Linux for a while now and today I'll show you how to tweak your GRUB menu settings so that it looks and behaves the way you might want it to. The Linux distribution that I currently use is Kubuntu 7.10. As such, many of the commands that I use may be Ubuntuish.

Let's get started. The options for your GRUB menu are stored in a file named menu.lst. Typically, this file will be located at /boot/grub. Before making any changes to menu.lst, let's first take a backup of the file. Open up a terminal and type the following:

sudo cp /boot/grub/menu.lst /boot/grub/menu.lst_backup

The shell should prompt you for your root password. Once you enter your password, the contents of the file menu.lst will be copied to another file named menu.lst_backup.
Now type:

sudo nano /boot/grub/menu.lst

to take a look at the menu.lst file. I'd imagine the file contents to be something like this.
Any line in this file that starts with a # symbol is a comment. This means that it will be safely ignored when GRUB reads this file.

1. Changing the default OS.
You can change the OS that loads by default in the GRUB menu. In order to do this, first count the entries in the menu starting from zero (not one). Now, locate the line in the menu.lst file that says default<space>n where n is literally a number. Change that number to the entry you want. For example, in order to make the first entry in the list as the default OS to be loaded, change the line in menu.lst to default 0
Save the file and exit the editor by pressing Ctrl+O and Ctrl+X (only for nano). A common mistake that many make is inadvertently change the commented line in the file. If there is a commented line leave it as is.

2. Changing the timeout.
Generally, the GRUB menu gives you about five seconds to decide which OS you want to boot. At the end of this time, GRUB automatically boots into the default OS. To change the timeout, simply find the line in menu.lst that says timeout and change it to timeout<space>n where n is the number of seconds you want to set. I usually set this value to 15. Save the file and exit the editor.

3. Changing the splash image.
Here's a fun customization that you can do. Most GRUB menu screens are purely black with white text. If you want to change the GRUB menu screen to that of a picture, you can easily do that. Get a nice GRUB splash image from the net. You can find plenty under the BootSplash section on http://www.kde-look.org
The grub splash image file should be something like filename.xpm.gz. If your splash image file is not in the xpm format, then it cannot be loaded by GRUB. Alright, now to set this picture as a grub splash, copy it to /boot/grub. Do the following:

sudo cp <PATH_TO_IMAGE> /boot/grub/bootsplash.xpm.gz

where PATH_TO_IMAGE is the logical path to the GRUB bootsplash image file that you intend to use. Now reopen menu.lst with root previleges.
sudo nano /boot/grub/menu.lst

Add a new line to this file (preferably after the initial comments):
splashimage /boot/grub/bootsplash.xpm.gz
Save and exit the editor.
Now everytime you boot your system, you should see the pretty new GRUB splash image instead of that boring dark one!

NOTE: If at any point, you realise that you've messed up your menu.lst file, then just retrieve it from the backup that we had first created.
Type:

sudo cp menu.lst_backup menu.lst

Kubuntu 7.10 CD request

I feel quite happy today because the Kubuntu Gutsy CD that I requested from Canonical has arrived. I requested for the 32-bit version of the CD on the 7th of March and today is April Fool's. So, it totally took little more than three weeks to deliver the CD. I figured that since I lived in India which is quite some distance from the US, I'd at least have to pay for the shipping charges. The truth is that I didn't have to pay a dime, no shipping charges - nothing! A friend of mine told me that he had also got some free Ubuntu stickers along with his CD request. I didn't but that's okay because now I can make my own stickers. :D

https://shipit.ubuntu.com/

What is FLOSS?

FLOSS stands for Free 'Libre' Open Source Software. It is a term that is used to represent software that has very limited restrictions on its license. Users of FLOSS are given the right to read and alter its source code. It is important to remember that free software does not mean that the software is free of charge. It means that the software is free from restrictions. Think of it in terms of "free speech" rather than "free food". Of course, there's lots of software out there that can be both. Just imagine a world where you don't have to simply file a bug report on the software that you use and then wait for the manufacturers to get back to you (which could be a very long wait!). Perhaps, if you have the technical knowledge, you could add to the software or call upon others to try and improve it. This would benefit not just you but all other users of that piece of software. Folks used to call such software that is free of restrictions as FOSS without the 'L'. However, this caused some level of ambiguity since it led to the assumption that one did not have to pay for the software. Such a notion would have spelt doom for any business prospects that such software might have. Once the word 'Libre' (meaning Liberty in Spanish or French) was brought in, the meaning became clear. So what FLOSS can you get? Well, apart from your dentist, here's an extensive list compiled by Wikipedia. I'm not too much of an activist. So, I wouldn't tell you to get rid of your proprietary (possibly pirated?) software. You probably use free software anyway. If you use Firefox, VLC or Gimp, then you are already a part of the solution. There are other useful applications that you could use. All it takes is an open mind to make a difference.

Other important links:-
Free Software Foundation
Info on Free and Non-free Software Licenses
Making the Move

An introduction to the STL : Priority Queues

(Reader Level : Beginner)
(Knowledge assumptions : classes, std::vector, std::string, queues)
Hello all! This time we're going to look at another STL container - the Priority Queue. You probably know what a queue is but just in case you don't or your memory could use some jogging, here goes... A queue is a First In First Out data structure. It means that the first element you put into the queue is the first one to leave the queue. Think of it as one of those long queues at the supermarket. The sooner you enter the queue, the sooner you can leave. So what is a priority queue? A priority queue is a queue where elements are entered based on their priority. If the wife of the supermarket's Manager had to do some shopping, she might not have to wait in line(hypothetically speaking ;)). She could immediately walk to the front of the queue and check out her purchases. If the Manager's daughter were also present, then she would stand behind the wife because she doesn't get as much importance as the mother but is still more important than the rest of the frustrated patrons. I know, I know. Silly example but hopefully you get the idea. In order to illustrate the beauty of a priority queue let me describe a rather contrived problem. This question was presented to me for a programming competition held at my college university.

The Problem: Write a C++ program to accept a list of words from the user. The user must also enter a weight associated with each word. Finally, display the words in decreasing order of their weights.

Solution Attempt #1 : Using a vector:
The user having to enter words and associated weights is pretty basic stuff. So, I'm not going to write any of that code in order to keep this blog post as short as possible. Here's one possible way to do it with vectors.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

//This class encapsulates a word that can be prioritized based on a number.
class PrioritizedWord
{
private:
 std::string m_word;
 int m_priority;

public:
 explicit PrioritizedWord()
 {}

 explicit PrioritizedWord(const std::string& word, const int priority = 0) : m_word(word), m_priority(priority)
 {}
           
 //Compares two words. This overloaded operator prioritizes words according to their weight.
 const bool operator <(const PrioritizedWord& pW) const
 {
     return (m_priority < pW.m_priority);
 }

 //Overloaded "put to" operator for streaming output.
 friend std::ostream& operator <<(std::ostream& out, const PrioritizedWord& pW)
 {
     out<<pW.m_word;
     return out;
 }
};

int main()
{
std::vector<PrioritizedWord>    vWords;

vWords.push_back(PrioritizedWord("Angelo", 23));
vWords.push_back(PrioritizedWord("This", -1));
vWords.push_back(PrioritizedWord("Here", 51));
vWords.push_back(PrioritizedWord("Was", -1));

std::sort(vWords.begin(), vWords.end());

for(std::vector<PrioritizedWord>::size_type i = 0; i < vWords.size(); ++i)
{
 std::cout<<vWords[i];
}

return 0;
}

We are sorting the vector contents using a function named sort that is available in the pre-compiled header <algorithm>. The working of the sort function is beyond the scope of this post but I'll provide a link at the end. Also, note the use of the overloaded less-than operator. We need to overload this operator because the sort() function will compare two PrioritizedWord's using it. Don't forget the const at the end of the operator definition. sort() expects that our overloaded operator routine will not alter any class member variables. If you forget to be const-correct in this case, the compiler will bite your head off!

Solution Attempt #2 : Using a priority queue:
We'll use the same class PrioritizedWord from above. That way my lazy self won't have to do much typing. :D

#include <iostream>
#include <string>
#include <queue>  //Instead of vectors, we now use a queue.

//PrioritizedWord Class definition goes here.

int main()
{
std::priority_queue<PrioritizedWord>    wordQueue;

wordQueue.push(PrioritizedWord("Angelo", 23));
wordQueue.push(PrioritizedWord("Here", 51));
wordQueue.push(PrioritizedWord("Was", -1));

//Peek and pop until the priority queue is empty.
while(!wordQueue.empty())
{
  std::cout<<wordQueue.top()<<" ";
  wordQueue.pop();
}

return 0;
}

Note that this time we didn't have to sort anything because the words were pushed into the queue based on their priority. This means that at the end of our input, the words in the priority queue are already sorted based on their weights. Pretty neat, huh? I'd say that in this case a priority queue leads to more elegant code when compared to using a vector. The stuff that I said earlier about being const-correct with regard to the overloaded less-than operator applies here too. The push() function is the one who actually prioritizes the words. Here are some good links to read up on.

SGI Documentation on Priority Queues
Member functions of STL Priority Queue
SGI Documentation on sort algorithm
Enjoy!

More Free Stuff: Open Stickers

Recently, a friend of mine pointed me to a site that gave free sticker books. You can download them for free, print and use them wherever you like. The theme of the stickers was Open Source. I'm a big supporter of the Open Source philosophy (more on that later). I decided to give my laptop a makeover. Here's what I ended up with:

You can get these cool stickers too!

Free Stuff - Code::Blocks new release

I've been waiting for this for a long time (nearly two years actually). Code::Blocks 8.02 is here! I mentioned this free C++ IDE in a previous post of mine. At that time, it was called Code::Blocks 1.0 RC2. Now, the developers of Code::Blocks have decided to go with the Ubuntu style of versioning ie; "Year.Month". I must say that this IDE has begun to show much promise. I find it very intuitive and pretty feature-rich (code profiling, code statistics, code-completion and all that jazz) for something that's completely free. The best part, IMHO, is that Code::Blocks is cross-platform. Earlier, it was easy to download and install this IDE for Windows but when it came to Linux you had to configure it from source. They did have some packages targeting specific distributions but many of the links were broken. Now, the Linux packages have been given a face-lift. They even have a Mac OS X binary on the download page. Spiffy!
Interested? Hop on over and give it a try.
Code::Blocks 8.02 Free C++ IDE

Screenshot1: Building and executing a simple SDL application with Code::Blocks 8.02

Screenshot2: An amazing number of project templates for developers from all walks of life.

Screenshot3: Programming doesn't have to be stressful with the BYO Games tetris plugin. There's one for snake as well.

An introduction to the STL : Maps

(Reader Level : Beginner)
(Knowledge assumptions : std::string, std::vector)
Hello! Today we're going to discuss another popular data structure in the STL - Maps. Maps are basically associative arrays or hash tables where each element consists of a unique key that identifies a particular value. Once a key is stored in the map, then it cannot be changed. Only the value it identifies can be changed. If we want to associate a new key with a value, then the entire element(key + value) must be removed from the map and the new element inserted. To actually see the beauty of maps, let us attempt to solve a simple problem.

The Problem: Write a C++ program to find the character with most number of occurrences in a string.

Solution attempt #1 : Using Vectors

#include <iostream>
#include <string>
#include <vector>

const char VectorMethodOfCounting(const std::string& str)
{
std::vector<unsigned int> vCharCount(26);
char mostUsedChar = '\0';
unsigned int count = 0, currentIndex;

for(std::string::size_type i = 0; i < str.length(); ++i)
{
   //Calculate the index of this character in the vector.
   currentIndex = str[i] - 'a';
   ++vCharCount[currentIndex];

   if(vCharCount[currentIndex] > count)
   {
       mostUsedChar = str[i];
       count = vCharCount[currentIndex];
   }
}

return mostUsedChar;
}

int main()
{
std::string myString = "thebrowncowjumpedoverthemoon";
std::cout<<VectorMethodOfCounting(myString);

return 0;
}

Basically, what we've done here is create a vector for all twenty-six characters in the english alphabet. This vector will maintain a count of the occurrences of each alphabet in our string. Then, we loop through the characters of the string. As we encounter, each character in the string, we determine its index in the vector by subtracting its ASCII value from that of 'a'. We also maintain a record of the character with the most occurrences till date. When we finish iterating through the string, we return this character.
This solution, of course, works but it has some pretty serious drawbacks. The first shortcoming is that it only works with lowercase strings. If the string were to contain uppercase characters or other special characters like spaces, then the solution fails. We could resize the vector to account for all 256 ASCII characters (or maybe all UNICODE characters) but then that would be wasted space if only a handful of characters were actually present in the string. Also, as we will soon see, this problem could have been solved more elegantly. I especially hate that part where we determined the index of the character in the vector.

Now, on to maps. If we analyse the problem more closely, we will come to the conclusion that what we really want to do is maintain a count of the number of occurrences for each character in the string. In other words, each unique character in the string is associated with a count. This concept could best be represented with a map where each element consists of a character as the key and an integer as the value. Let's try doing that.

Solution attempt #2 : Using Maps

#include <iostream>
#include <string>
#include <map>

const char MapMethodOfCounting(const std::string& str)
{
   std::map<char, unsigned int> mapCharCount;
   char mostUsedChar = '\0';
   unsigned int count = 0;

   for(std::string::size_type i = 0; i < str.length(); ++i)
   {
       ++mapCharCount[str[i]];

       if(mapCharCount[str[i]] > count)
       {
           mostUsedChar = str[i];
           count = mapCharCount[str[i]];
       }
   }

   return mostUsedChar;
}

int main()
{
   std::string myString = "thebrowncowjumpedoverthemoon";
   std::cout<<MapMethodOfCounting(myString);

   return 0;
}

A little explanation is in order. In order to use maps, we need to include the pre-compiled header "map". The next thing we do is create a map named mapCharCount. The first char in the syntax is the data type of the keys and the unsigned int is the data type of the values. Everything else is pretty much the same with the exception of the indexing. Unlike our vector method, indexing into the map based on the key is easy. Our key is the character str[i], so we retrieve the value (the count) by mapCharCount[str[i]]. Pure elegance!

There's more to maps than meets the eye. For more information on maps, feel free to read up on the following links:

SGI Documentation on Maps
Member functions of STL Map

In my next post, I'll talk about another STL container - The Priority Queue.

An introduction to the STL : Vectors

(Reader Level : Beginner)
(Knowledge assumptions : Arrays)
Today I'm going to cover a pretty basic standard library provision that I feel every C++ programmer should know about - Standard Template Library Vectors. Vectors (don't mind the wierd sounding name) are similar to C-style arrays but with more safety. Whenever I explain a concept, I prefer to illustrate what I mean with some code. Let's first try to create a one-dimensional C-style array of type int:

#include <iostream>

int main()
{
    int myArray[3];

    myArray[0] = 10;
    myArray[1] = 20;
    myArray[2] = 30;
    //myArray[3] = 40;    //Can't add any more.

    for(int i = 0; i < 4; ++i)  //Out of bounds!
    {
        std::cout<<myArray[i]<<std::endl;
    }
   
    return 0;
}

One of the biggest drawbacks of C-style arrays is that the dimension(s) of an array must be known at the time of declaration. This generally leads to wastage of allocated space. In our example, we can't add more than 3 integers to the array because we've already decided on its maximum size at compile time.
Another shortcoming of arrays is that its very easy to trip up and access beyond the bounds of an array. In our example, we inadvertently tried to print the value of myArray[3] simply because its quite hard to remember a hard-coded dimension. Of course, there's lots of other ways by which an out-of-bounds access can happen but we'll just stick to the basics for the time being.

Alright then, let's rewrite the exact same code as above, only this time we'll use Vectors.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> myVector;

    myVector.push_back(10);
    myVector.push_back(20);
    myVector.push_back(30);  //Add some more if you like. :)

    for(std::vector<int>::size_type i = 0; i < myVector.size(); ++i)  //Safer...
    {
        std::cout<<myVector[i];
    }
    return 0;
}

At the top we include the pre-compiled header file for using vectors. In main(), we declare a vector of integers called myVector. By default, the initial size of myVector will be zero which means that there is no memory allocated for it. Note that, vectors are also named within the std namespace just as cout is. After we declare the vector, we then add data to this vector using a function named push_back(). Since this is an integer vector, we push integers into the vector. This means that at the end of the three pushes, our vector will be as follows:
myVector[0] = 10;
myVector[1] = 20;
myVector[2] = 30;

However, we couldn't just substitute these statements in place of the three push_back() function calls. Why? Remember that the size of myVector was zero when we declared it. So, trying to access an element of the vector through an index will lead to an out-of-bounds access. Finally, we iterate through all the elements in the vector and display the value of each element. The function size() gives us the number of elements in the vector. So, there's no way we could iterate beyond the bounds of the vector. Now you may ask, what's with that wierd data type with which the variable 'i' was declared? It's nothing but a defined type that is implementation specific for vectors. Since we are iterating over the elements of the vector based on its size, the maximum value of the variable i can be the maximum size for any vector.

There are lots of other cool things one could easily do with vectors. For example, you could resize a vector(doing that with an array would be a major headache) or clear the contents of the vector in one go. Unfortunately, all those cool things are beyond the scope of this measly blog post. The following links should help you get started on STL Vectors:
A Beginner's Tutorial For std::vector, Part 1
Member functions of STL Vector
In my next post, I hope to introduce you to another useful STL container.

const pointers and typedef

(Reader Level : Beginner)
(Knowledge assumptions : Pointers, typedef, std::vector...)
Sometimes we create our own types using the typedef keyword in C++. For eg;
typedef std::vector<int> INTVECTOR;

If we write : const INTVECTOR myVector;
It is the same as : const std::vector<int> myVector;
This means that the type (in this case, a vector of ints) itself is constant and we can't do stuff like this:
myVector.push_back(10);

Let's look at a typedef for a pointer.
typedef int* INTPTR

If we write : const INTPTR pInt;
Is it equivalent to writing? : const int* pInt;
To answer that we need to think about what these two statements syntactically mean.

In the former statement, we are saying that the type (in this case, the integer pointer) itself is constant and that we can't change it in anyway. That statement prevents us from doing stuff like this: pInt++;

In the second statement, we are informing the compiler that the value that the pointer "points" to is constant.
That means we CAN do : pInt++;
But we can't do : *pInt = 20;

In other words,
const INTPTR pInt; is equivalent to int* const pInt;

Defining a user-defined type within a templated class definition

(Reader Level : Intermediate)
(Knowledge assumptions : Classes, Templates, Structures...)
Ever tried declaring a class, structure, array or an enum within a templated class? Perhaps, the code could be something like this:

template<class T>
class MyClass
{
public:
    struct MyStruct
    {
        T m_d1, m_d2, m_d3;
    };

    const MyStruct& GetStructure() const;

private:
    MyStruct m_struct;
};

template<class T>
const MyClass<T>::MyStruct& MyClass<T>::GetStructure() const
{
    return m_struct;
}

MyStruct is not a general-purpose structure. It's used primarily for MyClass. So, it makes sense to scope it within MyClass itself. However, this code will not compile. The following errors were reported by the Microsoft Visual Studio 2005 compiler.
warning: 'MyClass::MyStruct' : dependent name is not a type
error: syntax error : missing ';' before '&'
error: missing type specifier - int assumed. Note: C++ does not support default-int
fatal error: unable to recover from previous error(s); stopping compilation

Clearly the cause of this lies in the fact that the compiler can't discern the type of MyStruct in the GetStructure() definition. A look at the standards provides the solution. The relevant citation is from Section 14.6:
"When a qualified-id is intended to refer to a type that is not a member of the current instantiation (14.6.2.1) and its nested-name-specifier depends on a template-parameter (14.6.2), it shall be prefixed by the keyword typename, forming a typename-specifier."

The revised GetStructure() definition for MyClass should be as follows:

template<class T>
const typename MyClass<T>::MyStruct& MyClass<T>::GetStructure() const
{
           return m_struct;
}

The Pimpl pattern

(Reader Level : Beginner)
(Knowledge assumptions : Classes, Pointers...)
The Private Implementation (Pimpl) pattern allows the implementation of a whole interface without the need to recompile the modules which use it. As with most design patterns, this pattern can best be explained with an example. Let's say that we have a class named Student. Our Student class is very popular in our project because many other classes use it. The header file of the Student class, "Student.h" may be as follows:

#ifndef STUDENT_HEADER
#define STUDENT_HEADER

#include <string>

class Student
{
private:
    std::string m_name;
};

#endif

We may have many classes that contain instances of Student. For example, a Subject class may have an aggregation of Students. So, each of the classes that contain Student(s) would probably have to include "Student.h". Now let's say that at some point in time, colleges allow students to carry mobile phones freely (I know that's not likely. :D). Now, our Student will have a contact number that we might want to record. Professors already had mobiles all along. So, let's say that we already have a class named ContactNo that stores all types of numbers, be they Landline, Mobile or Pagers. "Student.h" becomes...

#ifndef STUDENT_HEADER
#define STUDENT_HEADER

#include <string>
#include "ContactNo.h"

class Student
{
private:
    std::string m_name;
    ContactNo m_contactNo;
};

#endif

After making the relevant changes, we need to do a full re-compile of the source. To our dismay, we might find that the compile time has become unbearably long. Why? It's because we included "Contact.h" in our popular "Student.h". With that one simple change, the header files of all the classes that used to just include "Student.h" will now also include "Contact.h". If our Student was that popular, then this might mean a lot of unnecessary inclusions. To add insult to injury, the contact number of the Student might never even be used by many classes. For example, our Subject class would have no reason to know the contact number of the Students who take that subject. That's why m_contactNo is a private member of Student. You might think that the entire situation is a bit contrived but I assure you its not and there can be situations where you might desperately be seeking a way to reduce compile times, especially in the case of large projects. This is where the Pimpl pattern comes in. Basically, what we need to somehow achieve is the removal of "ContactNo.h" from "Student.h". What we do is take the private implementation of the class (in our case, m_contactNo of Student) and pack it into a simple internal structure. A pointer to this structure, called an opaque pointer or d-pointer is then made a private member of the class. We also need to take care of dynamically creating and destroying the implementation structure for every object of the wrapping class.

This is then our "Student.h" file with the Pimpl pattern.

#ifndef STUDENT_HEADER
#define STUDENT_HEADER

#include <string>

class Student
{
private:
    std::string m_name;
    struct PIMPL; //Forward declaration.
    PIMPL* pimpl; //The opaque pointer.

public:
    Student();
    ~Student();
};

#endif

Our "Student.cpp" file could be:

#include "Student.h"
#include "ContactNo.h"

//Private Implementation structure.
struct Student::PIMPL
{
    ContactNo m_contactNo;
};

Student::Student()
{
    pimpl = new PIMPL;
}

Student::~Student()
{
    if(pimpl)
        delete pimpl;
}

If we want to access the contact number of the student internally we do it as pimpl->m_contactNo. Now that we've seen how useful the Pimpl pattern can be, let's talk about its downside. By using the Pimpl pattern, our code has become a little more complex (less readable anyway) and we've also got to do a dynamic allocation for every instance of Student that is created. For large objects with relatively fewer instances, this probably won't be an issue but for small objects with several instances, Pimpl may not fit the bill.