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. 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:
This is how it looked afterwards...
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!