Finding an element in a list

Often you need to search through an array or list to find a specific element and of course you need this search to be as fast and efficient as possible. One of the best ways to do this is using a binary predicate function.

A binary function is a function object (which are also called Functors) and is any object which can be called as if it was a function. Depending on your language and platform of choice, Function objects are also known as callback functions, function pointers and delegates (.NET). Generally, there are three types of function objects:

  1. Generators – function with no arguments
  2. Unary Functions – function with one argument
  3. Binary Functions – functions with two arguments

A function object which takes one parameter (i.e. unary function) and returns a bool are treated as a special case and are  called Predicate functions.

How do we use it? Say we have a simple data structure called ContactData to represent a Contact in an Address book as shown in the code snippet below. We also define a predicate function called FindAContact. Now we need to use this predicate function and define another function called  findContact. The findContact function in turn uses find_if.  find_if takes three parameters, the start of the iterator, the last element and the predicate to use. It returns the first iterator it finds in a given range for which the predicate holds. If no matches are found then  the last element in the iterator is returned.

We also need to ensure we have the relevant includes for this to compile and link properly hence include’s below.

The code snippet below shows all that we have discussed.

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

//Simple data structure
struct ContactData {
	string name;
	string addr1;
	string addr2;
	string addr3;
	string city;
	string postcode;
	string country;
	int workPhone;
	int homePhone;
	int mobilePhone;
	string workEmail;
	string homeEmail;
};

//I am lazy, create a typedef for the vector
typedef vector<ContactData> ContactDataArray;

// predicate function for rapidly searching the Contact data array
struct FindAContact: public std::binary_function<ContactData, std::string, bool>
{
	bool operator() (const ContactData &contact, const string &name) const
	{
		return (contact.name == name);
	}
};

//If a contact is find it returns that; else returns the iterator's last element
ContactData Contact::findContact(string name)
{
	ContactDataArray::iterator it = find_if(addressBook.begin(),
						addressBook.end(),
						std::bind2nd(FindAContact(), name)
					);

	return *it;
}

Printing code and making it look pretty

If you are on Linux and want to print some code and also make it look pretty then check out a2ps (Any to postscript filter). Of course if you can avoid printing in the first place and saving paper and trees and make it greener that is ideal – however there are times that is not possible. I tried printing from CDT, but the printing options from CDT just looks plain ugly and big fonts and can spread over 10 pages for a simple code file (spanning 293 lines). Sure I can tweak the font in CDT, but that is the only option available – enter a2ps. It seems to have more options, but I have not had a chance to play with those.

For example if I wanted a C++ code file called MOOSSniffer.cpp and “print it” out as PDF then use the command shown below. Here “-E” is the option to make the code look pretty and the “-P pdf” is the option for printing to PDF. Next comes the source file (you can also provide multiple files such as *.cpp) and finally the -o option is for the output filename. Of course you will need to install a2ps, which you can do via System -> Admin -> Synaptic Package Manager

a2ps -E -P pdf MOOSSniffer.cpp -o MOOSSniffer.pdf

Now, for some reason the resulting PDF could not be opened in Acrobat Reader, but on my Ubuntu machine, I could open it using the “Document Viewer” and print it using that. And in case you were curious, the pretty page option came to 3 pages instead of the original 10.

Also no trees were harmed in the making of this post – my printouts were all to PDF and not real paper – but in the end I did print out the 3 page version. 🙂

Ten commandments of Programming

I came across the Ten commandments of Programming while looking at a question on StackOverflow and I can’t believe I have not seen these before. I think every developer, lead, architect, dba, pm, whoever should print this out! 😎

  1. Understand and accept that you will make mistakes. The point is to find them early, before they make it into production. Fortunately, except for the few of us developing rocket guidance software at JPL, mistakes are rarely fatal in our industry, so we can, and should, learn, laugh, and move on.
  2. You are not your code. Remember that the entire point of a review is to find problems, and problems will be found. Don’t take it personally when one is uncovered.
  3. No matter how much “karate” you know, someone else will always know more. Such an individual can teach you some new moves if you ask. Seek and accept input from others, especially when you think it’s not needed.
  4. Don’t rewrite code without consultation. There’s a fine line between “fixing code” and “rewriting code.” Know the difference, and pursue stylistic changes within the framework of a code review, not as a lone enforcer.
  5. Treat people who know less than you with respect, deference, and patience. Nontechnical people who deal with developers on a regular basis almost universally hold the opinion that we are prima donnas at best and crybabies at worst. Don’t reinforce this stereotype with anger and impatience.
  6. The only constant in the world is change. Be open to it and accept it with a smile. Look at each change to your requirements, platform, or tool as a new challenge, not as some serious inconvenience to be fought.
  7. The only true authority stems from knowledge, not from position. Knowledge engenders authority, and authority engenders respect—so if you want respect in an egoless environment, cultivate knowledge.
  8. Fight for what you believe, but gracefully accept defeat. Understand that sometimes your ideas will be overruled. Even if you do turn out to be right, don’t take revenge or say, “I told you so” more than a few times at most, and don’t make your dearly departed idea a martyr or rallying cry.
  9. Don’t be “the guy in the room.” Don’t be the guy coding in the dark office emerging only to buy cola. The guy in the room is out of touch, out of sight, and out of control and has no place in an open, collaborative environment.
  10. Critique code instead of people—be kind to the coder, not to the code.As much as possible, make all of your comments positive and oriented to improving the code. Relate comments to local standards, program specs, increased performance, etc.

Copying strings in C++

Here is a good example on why either you love C++ or hate it with such terse expression oriented code; I think its pretty cool.

If you want to copy one string to another, one option can be something like this.

void mycopy(char *p, char *q) {
	int len = strlen(q);

	for(int i=0; i&lt;=len; i++)
		p[i] = q[i];
}

However this achieves the same thing as above and is more efficient:

void mycopy(char *p, char *q) {
	while(*p++ = *q++);
}

Of course why would you write your own version when you have standard string copy fundtion strcpy in <string.h>

‘QPainter painter’ has initialiser but incomplete type

If you ever got an error something like [some-class] has initialiser but incomplete type, it basically means the compiler cannot understand the type and you need to add the include for it.

QPixmap pixmap(20,10);
pixmap.fill(Qt::white);

QPainter painter(&pixmap);
QPen pen(Qt::blue);

Take the code snipped above when you compile it you might get an error something along the lines of the following for line 4.

‘QPainter painter’ has initialiser but incomplete type

To fix this you need to include the header file where QPainter is defined. The updated code looks like:

#include <qpainter.h>

QPixmap pixmap(20,10);
pixmap.fill(Qt::white);

QPainter painter(&pixmap);
QPen pen(Qt::blue);

Making sense of primary-expression error

If you are new to C++ then some of the compiler errors can be a bit confusing and daunting at first. For example if the compiler given you an expected primary-expression error (e.g. expected primary-expression before ‘.’ token), at face value it does not make sense.

void RGBViewer::accept() {
	QMessageBox::information(this, "Button Clicked", "You clicked OK", QMessageBox::Ok);

	QColor color = QColor(Ui_RGBViewerClass.spinBoxRed->value(),
			Ui_RGBViewerClass.spinBoxGreen->value(),
			Ui_RGBViewerClass.spinBoxBlue->value(),
			255);

	qDebug() << color;

	QBrush brush(color);
	brush.setStyle(Qt::SolidPattern);
	ui.graphicsView->setBackgroundBrush(brush);
	ui.graphicsView->backgroundBrush();
}

When I compile the above code snippet, I get the following error from the compiler:

rgbviewer.cpp: In member function ‘virtual void RGBViewer::accept()’:
rgbviewer.cpp:19: error: expected primary-expression before ‘(’ token
rgbviewer.cpp:19: error: expected primary-expression before ‘.’ token
rgbviewer.cpp:20: error: expected primary-expression before ‘.’ token
rgbviewer.cpp:21: error: expected primary-expression before ‘.’ token

All this means is that I need to initialize the type ‘Ui_RGBViewerClass’ as the compiler does not understand it. In other words, I need to use a new.

Here is the ‘fixed’ version below of the same code snippet.

Ui::RGBViewerClass ui; //Defined in the header; shown here for completness

void RGBViewer::accept() {
	QMessageBox::information(this, "Button Clicked", "You clicked OK", QMessageBox::Ok);

	QColor color = QColor(ui.spinBoxRed->value(),
			ui.spinBoxGreen->value(),
			ui.spinBoxBlue->value(),
			255);

	qDebug() << color;

	QBrush brush(color);
	brush.setStyle(Qt::SolidPattern);
	ui.graphicsView->setBackgroundBrush(brush);
	ui.graphicsView->backgroundBrush();
}

Sandbox is Up!

As promised earlier, the Sanbox is up – go give it a whirl and let me know your thoughts. Also the code and release build of the World Clock are up there. Check it out and let me know what you think of it and also any bugs and feature enhancements you would like to see.