algorithm toolbox

A toolbox of algorithms written in C++. Details of different algorithms are described below. Note that this toolbox will not compile out of the box. Most noticeably, there is no makefile or configuration, or instructions on how to build. You're on your own, and you'll probably need to make slight adjustments. The source is here.

van Emde-Boas tree

This is an efficient priority queue that supports operations over integers i O(lg lg n) time, where n is the maximum integer stored in the set. This implementation uses bit-arrays for efficiency, and has hardcoded n=20. The data structure is implemented in the vebtree.h file, and benchmark and example is given in veb.cc file. The arguments on the command line are the fill factor of the tree (max. 2^20-1) and the number of repetitions (for more precise time measurement).

Caveats: the intrinsics.h file declares several functions that correspond to x86 machine instructions. The _bsf function has shown to be crucial for efficient implementation of the "find minimum" operation. It should be coded in inline assembly, in the way that it returns -1 if the input is 0, otherwise it returns the usual result. The intrinsics32.il file contains an implementation suitable for use with the Sun C++ compiler.

The original article where this data structure has been first described can be found here (local copy). However, this paper was almost incomprehensible for me. My implementation is based on the wikipedia article, and following papers, which I found much more easier to read: this, this, this, and this.

Intrusive AVL tree

This is an AVL tree implemented according to this excellent tutorial. It has been rewritten in C++ and slightly redesigned so that it can be used in an intrusive way. This has the advantage that no memory allocation or deallocation takes place. However, the nodes must already contain links for the tree, and the implementation must define traits for each node types. How this is done is best shown in the h-avl.cc file which must be compiled to a which must be compiled to a .so (shared object) file. This is also a plug-in for the exhaustive testing of correctness of the tree code. The code has been tested to work correctly on all permutations of up to 10 elements.

Exhaustive permutation tester

You need to compile and link against the Boost program_options library. This program has several modes of operation, which you can see by running it without any arguments. For more information, read the introduction in the code. The code has large portions delimited with #ifdef USE_THREADS. This is broken and should not be used. Maybe I fix it once in the future, but don't hold your breath. The --part option supersedes the need for threads. Examples:

perm-driver --N 4 --part 2/8 will divide the job in (roughly) 8 equal chunks, and run the specified action (by default, print the permutations), on each permutation. Without the --part option, the program processes all permutations. The format must be I/K with 1 <= I <= K and 1 <= K <= N!.
perm-driver --N 4 --printk K where K is number 0 <= K < N! prints just the K'th permutation in lexicographic order.
perm-driver --N 7 --solib ./h-avl.so executes the do_perm function in the specified shared library, with the current permutation as an argument. Read the source and example for the specific interface.