What did I do this christmas?

Posted: 20091229

I mean.. come on ... This christmas ... There was NO rock show. NO party. NO girlfriend at present. Of course I hacked C++, what else?!?

I wrote an AVL tree implementation in C++. 360 lines of code. Here is the implementation. This is a complete project. Does balancing, single rotation, double rotation, implements the canonical put, get, contains, remove etc methods. Took me about a day. Some people wrote an article that is 30 pages long. Makes me wonder. Anyway.. Back using C++ is a good thing. Using Visual C++ is even better :-).

My AVL implementation performs a bit better as the Red-Black-Tree impl from the VC7.1 Standard libary. As expected. Not bad. My Implemenation is not a standard compliants container, I had my frustration with trying to create one during my HashMap project. I also do not store the balance as a character, but I store two ints for the maximum left and right child depth, which kind of sucks.

What is also really cool is dumping datastructures in the Graphviz dot file format and then displaying it with dotty. Like that DDD debugger from the linux world?. Very convenient.. Here is how my tree looked like before I deleted node 6:

DottyDeletion1.png

This is how it looked afterwards...

DottyDeletion2.png

FUNNY. Dumping into .dot format is quite practical if you are debugging tree-like data structures.

So what else was remarkable? First, CMake is cool. Its just the simplest solution for crossplatform C++ projects. I wanted to dig a bit into it, especially since I bought the Mastering CMake book. Anyway, It's my personal choice for cross-platform C++ projects from now on.. Why? Its simple enough and straightforward for normal use cases, has a simple language, albeit awkward filenames (come on CMakeLists.txt? We are not in JavaLand but in C++ where file names should be lower case.. even class names should be lower_case, such as: class boost_fanatic_impl). Anyway you get tight platform IDE integration, f.e. Visual C++ 6/7.1/8/9. Kind of high level Makefile.am usage, that works out of the box. Detects dependencies such as Qt, etc. KDE uses it. And .. out of source builds by default. Nice.

Hmm I also used the boost testing framework. What still freaks me out that the boost logging library isn't here yet. Anyway the sourceforge project Boost.Log shows a lot of activity and they (or rather him?) are progressing fast. I need blessed std::cout operations so please, please, please deliver :-)

Also iterative development with Visual C++ is amazingly fast. Still king in my world. No bugs in the IDE. No waiting, No slow GUI. Fast iterations. No constant interfering from the IDE (like eclipse) while your are typing.

So anyway, that's it.

...

...

HEY!!!! Don't leave yet.. I nearly forgot. I kicked hungarian notation. no more m_pRootNode or even m_pcrootnd. Just root_node.

Btw if you want to see some sensible, intelligent usage of hungarian style in an API (apart from Win32), check out the C API for the awesome tokyo cabinet key/value db. Here is the documentation. But its also incredibly funny to read. My personal favourites are:

tcstrsqzspc
tcstrcntutf

So, happy tcstrsqzspc, and enjoy it!