Tag Archives: mdds

mdds 0.5.4 released

Share Button

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

http://multidimalgorithm.googlecode.com/files/mdds_0.5.4.tar.bz2

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 moves to git

Share Button

Following the announcement that Google Code finally gets git support, I’ve migrated my mdds source code repository from the old mercurial one to a new git one. For anyone who has the old mercurial repository of mdds checked out, please switch to the new git repo. Refer to this page on how to check out the new git-based mdds repository.

As for doing the actual migration, this blog post was very helpful.

mdds 0.5.3 released

Share Button

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

http://multidimalgorithm.googlecode.com/files/mdds_0.5.3.tar.bz2

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

Share Button

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

http://multidimalgorithm.googlecode.com/files/mdds_0.5.2.tar.bz2

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
      operator().
    • 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
      swap().
    • 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

Share Button

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!

Share Button

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.

Installation

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.

Lastly…

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