mdds 0.6.0 released

I’m once again very happy to announce that version 0.6.0 of Multi-Dimensional Data Structure (mdds) is released and is available at the link below:

This release comes almost 9 months after the release of the last stable version 0.5.4, and contains:

  • MSVC project files to allow managing source files and compile test programs in Visual Studio on Windows,
  • improved performance of size() method of mixed_type_matrix (patch from Markus Mohrhard), and
  • two new data structures: multi_type_vector and multi_type_matrix.

Also, starting with this release, mixed_type_matrix is deprecated, and is subject to deletion in future releases.

Other than one change made to mixed_type_matrix, there are no changes made to any of the other existing data structures. So, if you still use 0.5.4 and don’t use mixed_type_matrix, and don’t need to use the new data structures added to 0.6.0, there is no reason to upgrade to 0.6.0.

mdds 0.5.4 released

I’m happy to announce that version 0.5.4 of Multi-Dimensional Data Structure (mdds) is available for download from the link below.

This release fixes several bugs in segment_tree and point_quad_tree, but other than that, no other changes are made since 0.5.3. If you use 0.5.3 and don’t use these data structures, then there is no reason to update to 0.5.4.

mdds 0.5.3 released

I’m happy to announce that version 0.5.3 of Multi-Dimensional Data Structure (mdds) is available for download from the link below.

This is a bug fix release. In fact, the only change since 0.5.2 is in mixed_type_matrix, and in particular in its filled storage implementation. I’ve completely re-worked the fill storage backend of mixed_type_matrix in order to boost its performance on instantiation, whose effect will be evident when creating and destroying a large number of filled matrix objects.

There is no API-incompatible change in this release.

mdds 0.5.2 released

I’m happy to announce that version 0.5.2 of Multi-Dimensional Data Structure (mdds) is available for download from the link below.

This is a bug fix release. I would like to thank David Tardon for fixing several important bugs as well as implementing some new API’s for flat_segment_tree. In fact, the majority of changes between 0.5.1 and 0.5.2 are from David.

Here is the run-down of the major changes since 0.5.1:

  • flat_segment_tree
    • fixed a crash on assignment by properly implementing assignment
    • fixed several bugs in shift_right():
    • shifting of all existing nodes was not handled properly.
    • leaf nodes were not properly linked under certain conditions.
    • shifting with skip node option was not properly skipping the
      node at insertion position when the insertion position was at
      the leftmost node.
    • implemented min_key(), max_key(), default_value(), clear() and
    • fixed a bug in operator==() where two different containers were
      incorrectly evaluated to be equal.
    • added quickcheck test code.

There is no API-incompatible changes since 0.5.1, so if you are currently using mdds 0.5.1, your code should compile with 0.5.2 without any modifications.

mdds 0.3.1

I’m happy to announce the release of version 0.3.1 of the Multi-Dimensional Data Structure (mdds). This is a bug fix release, and contains no major changes from the previous version (0.3.0). The highlights of this release are:

  • use of autoconf tool, to allow you to run ./configure && sudo make install to install the library, and
  • drop the requirement for C++0x support, by using equivalent features from the boost library which mdds already depends on.

When using this library without the C++0x support, however, you need to define the MDDS_HASH_CONTAINER_BOOST compiler macro in order for the mdds library to use boost’s hash_containers, instead of the ones from C++0x. Similarly, you can define the MDDS_HASH_CONTAINER_STLPORT to force mdds to use stlport’s hash containers instead.

I will briefly explain the incompatible support of hash containers various libraries. Originally, the stlport library supported two hash containers, hash_map and hash_set, in the std namespace which can be used as hashed replacements of std::map and std::set, respectively. In C++0x, however, these two containers have been renamed to unordered_map and unordered_set which are still in the std namespace. Boost also provides unordered_map and unordered_set, but they are in the boost namespace. The change that this release contains should hopefully be useful when dealing with this incompatible hash container situation in various libraries.

This release contains patches from David Tardon and Phillip Thomas, who fixed various bits of the Makefile script. Phillip also helped me fix the rpm spec file. Thanks a lot!

mdds 0.3.0 released!

I’m happy to announce the release of version 0.3.0 of Multi-Dimensional Data Structure, or mdds for short. This is a C++ library, and is a collection of various data structures designed to efficiently store and query multi-dimensional data for various filtering criteria. Different structures are optimized for different query needs.

This library is a source-code only library. It’s designed to be header-only meaning that the user program does not need to link to any additional shared library in order to use these data structures. The data structures are all available as C++ templates.

I have briefly touched on the motivation behind starting this project when I previously talked about my effort to increase Calc’s row limit, the effort of which eventually led to the creation of Flat segment tree, one of the structures included in this library.

What this release contains

This version contains the following four data structures:

  • Segment tree
  • Flat segment tree
  • Rectangle set
  • Point quad tree

I will not go into the details of each of these data structures in this post, but I will probably do a follow-up post explaining the strengths of each structure, and details of how they are structured internally, how the query works etc. The project home page provides a brief (yes, very brief!) overview of these data structures for the curious-minded.


I’ve created a package for the SUSE family of Linux distributions, via openSUSE Build Service (OBS). There is also a link to 1-Click Install from the project home page.

For non-SUSE users, please install it directly from the generic source package available from here, but first I must apologize for not providing the familiar configure, make, make install installation option yet. That’s one of the things I’d like to work on in future releases. For now, please install the library manually by

tar xvf mdds_0.3.0.tar.bz2
cd mdds_0.3.0
sudo cp -R inc/mdds /usr/local/include/

How to use these data structures

I’ve provided some example source code under the example directory which should serve as a quick tutorial on how to use these structures. For more details of the API, please refer to their respective header file. As time permits, I will work on providing documentation for this library.


Comments and feedback are very much appreciated! Thank you very much, ladies and gentlemen. :-)