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
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
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
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
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
perm-driver --N 4 --part 2/8will divide the job in (roughly) 8 equal chunks, and run the specified action (by default, print the permutations), on each permutation. Without the
--partoption, the program processes all permutations. The format must be
1 <= I <= Kand
1 <= K <= N!.
perm-driver --N 4 --printk Kwhere
0 <= K < N!prints just the
K'th permutation in lexicographic order.
perm-driver --N 7 --solib ./h-avl.soexecutes the
do_permfunction in the specified shared library, with the current permutation as an argument. Read the source and example for the specific interface.