Adding upstream version 2.1.1.upstream/2.1.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 727 insertions, 0 deletions

diff --git a/doc/rtree.rst b/doc/rtree.rst
new file mode 100644
index 0000000..4f691e2
--- /dev/null
+++ b/doc/rtree.rst
@@ -0,0 +1,727 @@
+
+.. highlight:: cpp
+
+R-tree
+======
+
+Overview
+--------
+
+`R-tree <https://en.wikipedia.org/wiki/R-tree>`_ is a tree-based data
+structure designed for optimal query performance on multi-dimensional spatial
+objects with rectangular bounding shapes.  The R-tree implementation included
+in this library is a variant of R-tree known as `R*-tree
+<https://en.wikipedia.org/wiki/R*_tree>`_ which differs from the original
+R-tree in that it may re-insert an object if the insertion of that object
+would cause the original target directory to overflow.  Such re-insertions
+lead to more balanced tree which in turn lead to better query performance, at
+the expense of slightly more overhead at insertion time.
+
+Our implementation of R-tree theoretically supports any number of dimensions
+although certain functionalities, especially those related to visualization,
+are only supported for 2-dimensional instances.
+
+R-tree consists of three types of nodes.  Value nodes store the values
+inserted externally and always sit at the bottom of the tree.  Leaf directory
+nodes sit directly above the value nodes, and store only value nodes as their
+child nodes.  The rest are all non-leaf directory nodes which can either store
+leaf or non-leaf directory nodes.
+
+
+Quick start
+-----------
+
+Let's go through a very simple example to demonstrate how to use
+:cpp:class:`~mdds::rtree`.  First, you need to specify a concrete type by
+specifying the key type and value type to use::
+
+    #include <mdds/rtree.hpp>
+
+    #include <string>
+    #include <iostream>
+
+    // key values are of type double, and we are storing std::string as a
+    // value for each spatial object.  By default, tree becomes 2-dimensional
+    // object store unless otherwise specified.
+    using rt_type = mdds::rtree<double, std::string>;
+
+You'll only need to specify the types of key and value here unless you want to
+customize other properties of :cpp:class:`~mdds::rtree` including the number
+of dimensions.  By default, :cpp:class:`~mdds::rtree` sets the number of
+dimensions to 2.
+
+::
+
+    rt_type tree;
+
+Instantiating an rtree instance should be no brainer as it requires no input
+parameters.  Now, let's insert some data::
+
+    tree.insert({{0.0, 0.0}, {15.0, 20.0}}, "first rectangle data");
+
+This inserts a string value associated with a bounding rectangle of (0, 0) -
+(15, 20).  Note that in the above code we are passing the bounding rectangle
+parameter to rtree's :cpp:func:`~mdds::rtree::insert` method as a nested
+initializer list, which implicitly gets converted to
+:cpp:class:`~mdds::rtree::extent_type`.  You can also use the underlying type
+directly as follows::
+
+    rt_type::extent_type bounds({-2.0, -1.0}, {1.0, 2.0});
+    std::cout << "inserting value for " << bounds.to_string() << std::endl;
+    tree.insert(bounds, "second rectangle data");
+
+which inserts a string value associated with a bounding rectangle of (-2, -1)
+to (1, 2).  You may have noticed that this code also uses extent_type's
+:cpp:func:`~mdds::rtree::extent_type::to_string` method which returns a string
+representation of the bounding rectangle.  This may come in handy when
+debugging your code.  This method should work as long as the key type used in
+your rtree class overloads ``std::ostream``'s ``<<`` operator function.
+
+Running this code will generate the following output:
+
+.. code-block:: none
+
+    inserting value for (-2, -1) - (1, 2)
+
+As :cpp:class:`~mdds::rtree::extent_type` consists of two members called
+``start`` and ``end`` both of which are of type
+:cpp:class:`~mdds::rtree::point_type`, which in turn contains an array of keys
+called ``d`` whose size equals the number of dimensions, you can modify the
+extent directly::
+
+    bounds.start.d[0] = -1.0; // Change the first dimension value of the start rectangle point.
+    bounds.end.d[1] += 1.0; // Increment the second dimension value of the end rectangle point.
+    std::cout << "inserting value for " << bounds.to_string() << std::endl;
+    tree.insert(bounds, "third rectangle data");
+
+This code will insert a string value associated with a rectangle of (-1, -1)
+to (1, 3), and will generate the following output:
+
+.. code-block:: none
+
+    inserting value for (-1, -1) - (1, 3)
+
+So far we have only inserted data associated with rectangle shapes, but
+:cpp:class:`~mdds::rtree` also allows data associated with points to co-exist
+in the same tree.  The following code inserts a string value associated with a
+point (5, 6)::
+
+    tree.insert({5.0, 6.0}, "first point data");
+
+Like the verfy first rectangle data we've inserted, we are passing the point
+data as an initializer list of two elements (for 2-dimensional data storage),
+which will implicitly get converted to :cpp:class:`~mdds::rtree::point_type`
+before it enters into the call.
+
+Now that some data have been inserted, it's time to run some queries.  Let's
+query all objects that overlap with a certain rectangular region either
+partially or fully.  The following code will do just that::
+
+    // Search for all objects that overlap with a (4, 4) - (7, 7) rectangle.
+    auto results = tree.search({{4.0, 4.0}, {7.0, 7.0}}, rt_type::search_type::overlap);
+
+    for (const std::string& v : results)
+        std::cout << "value: " << v << std::endl;
+
+In this query, we are specifying the search region to be (4, 4) to (7, 7)
+which should overlap with the first rectangle data and the first point data.
+Indeed, when you execute this code, you will see the following output:
+
+.. code-block:: none
+
+    value: first rectangle data
+    value: first point data
+
+indicating that the query region does overlap with two of the stored values
+
+Note that the :cpp:func:`~mdds::rtree::search` method takes exactly two
+arguments; the first one specifies the search region while the second two
+specifies the type of search to be performed.  In the above call we passed
+:cpp:type:`~mdds::detail::rtree::search_type`'s ``overlap`` enum value which
+picks up all values whose bounding rectangles overlap with the search region
+either partially or fully.
+
+Sometimes, however, you may need to find a value whose bounding rectangle
+matches exactly the search region you specify in your query.  You can achieve
+that by setting the search type to ``match``.
+
+Here is an example::
+
+    // Search for all objects whose bounding rectangles are exactly (4, 4) - (7, 7).
+    auto results = tree.search({{4.0, 4.0}, {7.0, 7.0}}, rt_type::search_type::match);
+    std::cout << "number of results: " << std::distance(results.begin(), results.end()) << std::endl;
+
+The search region is identical to that of the previous example, but the search
+type is set to ``match`` instead.  Then the next line will count the number of
+results and print it out.  The output you will see is as follows:
+
+.. code-block:: none
+
+    number of results: 0
+
+indicating that the results are empty.  That is expected since none of the
+objects stored in the tree have an exact bounding rectangle of (4, 4) - (7,
+7).  When you change the search region to (0, 0) - (15, 20), however, you'll
+get one object back.  Here is the actual code::
+
+    // Search for all objects whose bounding rectangles are exactly (0, 0) - (15, 20).
+    auto results = tree.search({{0.0, 0.0}, {15.0, 20.0}}, rt_type::search_type::match);
+    std::cout << "number of results: " << std::distance(results.begin(), results.end()) << std::endl;
+
+which is identical to the previous one except for the search resion.  This is
+its output:
+
+.. code-block:: none
+
+    number of results: 1
+
+indicating that it has found exactly one object whose bounding rectangle
+exactly matches the search region.
+
+It's worth mentioning that :cpp:class:`~mdds::rtree` supports storage of
+multiple objects with identical bounding rectangle.  As such, searching with
+the search type of ``match`` can return more than one result.
+
+As you may have noticed in these example codes, the
+:cpp:class:`~mdds::rtree::search_results` object does provide
+:cpp:func:`~mdds::rtree::search_results::begin` and
+:cpp:func:`~mdds::rtree::search_results::end` methods that return standard
+iterators which you can plug into various iterator algorithms from the STL.
+Dereferencing the iterator will return a reference to the stored value i.e.
+this line::
+
+    std::cout << "value: " << *results.begin() << std::endl;
+
+which immediately comes after the previous search will output:
+
+.. code-block:: none
+
+    value: first rectangle data
+
+In addition to accessing the value that the iterator references, you can also
+query from the same iterator object the bounding rectangle associated with the
+value as well as its depth in the tree by calling its
+:cpp:func:`~mdds::rtree::iterator_base::extent` and
+:cpp:func:`~mdds::rtree::iterator_base::depth` methods, respectively, as in
+the following code::
+
+    auto it = results.begin();
+    std::cout << "value: " << *it << std::endl;
+    std::cout << "extent: " << it.extent().to_string() << std::endl;
+    std::cout << "depth: " << it.depth() << std::endl;
+
+Running this code will produce the following output:
+
+.. code-block:: none
+
+    value: first rectangle data
+    extent: (0, 0) - (15, 20)
+    depth: 1
+
+A depth value represents the distance of the node where the value is stored
+from the root node of the tree, and is technically 0-based.  However, you will
+never see a depth of 0 in the search results since the root node of a R-tree
+is always a directory node, and a directory node only stores other child nodes
+and never a value (hence never appears in the search results).
+
+
+Removing a value from tree
+--------------------------
+
+Removing an existing value from the tree first requires you to perform the
+search to obtian search results, then from the search results get the iterator
+and advance it to the position of the value you wish to remove.  Once you have
+your iterator set to the right position, pass it to the
+:cpp:func:`~mdds::rtree::erase` method to remove that value.
+
+Note that you can only remove one value at a time, and the iterator becomes
+invalid each time you call the :cpp:func:`~mdds::rtree::erase` method to
+remove a value.
+
+Here is a contrived example to demonstrate how erasing a value works::
+
+    #include <mdds/rtree.hpp>
+
+    #include <string>
+    #include <iostream>
+
+    int main()
+    {
+        using rt_type = mdds::rtree<int, std::string>;
+
+        rt_type tree;
+
+        // Insert multiple values at the same point.
+        tree.insert({1, 1}, "A");
+        tree.insert({1, 1}, "B");
+        tree.insert({1, 1}, "C");
+        tree.insert({1, 1}, "D");
+        tree.insert({1, 1}, "E");
+
+        // This should return all five values.
+        auto results = tree.search({1, 1}, rt_type::search_type::match);
+
+        for (const std::string& v : results)
+            std::cout << v << std::endl;
+
+        // Erase "C".
+        for (auto it = results.begin(); it != results.end(); ++it)
+        {
+            if (*it == "C")
+            {
+                tree.erase(it);
+                break; // This invalidates the iterator.  Bail out.
+            }
+        }
+
+        std::cout << "'C' has been erased." << std::endl;
+
+        // Now this should only return A, B, D and E.
+        results = tree.search({1, 1}, rt_type::search_type::match);
+
+        for (const std::string& v : results)
+            std::cout << v << std::endl;
+
+        return EXIT_SUCCESS;
+    }
+
+In this code, we are intentionally putting 5 values to the same 2-dimensional
+point (1, 1), then removing one of them based on matching criteria (of being
+equal to "C").
+
+Compiling and running this code will generate the following output:
+
+.. code-block:: none
+
+    A
+    B
+    C
+    D
+    E
+    'C' has been erased.
+    A
+    B
+    D
+    E
+
+which clearly shows that the 'C' has been successfully erased.
+
+
+Visualize R-tree structure
+--------------------------
+
+In this section we will illustrate a way to visualize an R-tree structure via
+:cpp:func:`~mdds::rtree::export_tree` method, which can be useful when you
+need to visually inspect the tree structure to see how well balanced it is (or
+not).
+
+We will be using the following set of 2-dimensional rectangles as the bounding
+rectangles for input values.
+
+.. figure:: _static/images/rtree_bounds_src.png
+   :align: center
+
+For input values, we'll simply use linearly increasing series of integer
+values, but the values themselves are not the focus of this section, and we'll
+not talk much about that.  We will also intentionally make the capacity of
+directory nodes smaller so that the tree will split more frequently during
+insertion even for smaller number of inputs.
+
+Now, let's take a look at the code::
+
+    #include <mdds/rtree.hpp>
+
+    #include <iostream>
+    #include <fstream>
+
+    // Make the node capacity intentionally small.
+    struct tiny_trait_2d
+    {
+        constexpr static size_t dimensions = 2;
+        constexpr static size_t min_node_size = 2;
+        constexpr static size_t max_node_size = 5;
+        constexpr static size_t max_tree_depth = 100;
+
+        constexpr static bool enable_forced_reinsertion = true;
+        constexpr static size_t reinsertion_size = 2;
+    };
+
+    using rt_type = mdds::rtree<int, int, tiny_trait_2d>;
+
+    int main()
+    {
+        // 2D rectangle with the top-left position (x, y), width and height.
+        struct rect
+        {
+            int x;
+            int y;
+            int w;
+            int h;
+        };
+
+        std::vector<rect> rects =
+        {
+            {  3731,  2433, 1356,  937 },
+            {  6003,  3172, 1066,  743 },
+            {  4119,  6403,  825, 1949 },
+            { 10305,  2315,  776,  548 },
+            { 13930,  5468, 1742,  626 },
+            {  8614,  4107, 2709, 1793 },
+            { 14606,  1887, 5368, 1326 },
+            { 17990,  5196, 1163, 1911 },
+            {  6728,  7881, 3676, 1210 },
+            { 14704,  9789, 5271, 1092 },
+            {  4071, 10723, 4739,  898 },
+            { 11755,  9010, 1357, 2806 },
+            { 13978,  4068,  776,  509 },
+            { 17507,  3717,  777,  471 },
+            { 20358,  6092,  824, 1093 },
+            {  6390,  4535, 1066, 1715 },
+            { 13978,  7182, 2516, 1365 },
+            { 17942, 11580, 2854,  665 },
+            {  9919, 10450,  873, 1716 },
+            {  5568, 13215, 7446,  509 },
+            {  7357, 15277, 3145, 3234 },
+            {  3539, 12592,  631,  509 },
+            {  4747, 14498,  825,  626 },
+            {  4554, 16913,  969, 1443 },
+            { 12771, 14693, 2323,  548 },
+            { 18714,  8193, 2372,  586 },
+            { 22292,  2743,  487, 1638 },
+            { 20987, 17535, 1163, 1249 },
+            { 19536, 18859,  632,  431 },
+            { 19778, 15394, 1356,  626 },
+            { 22969, 15394,  631, 2066 },
+        };
+
+        rt_type tree;
+
+        // Insert the rectangle objects into the tree.
+        int value = 0;
+        for (const auto& rect : rects)
+            tree.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
+
+        // Export the tree structure as a SVG for visualization.
+        std::string tree_svg = tree.export_tree(rt_type::export_tree_type::extent_as_svg);
+        std::ofstream fout("bounds.svg");
+        fout << tree_svg;
+
+        return EXIT_SUCCESS;
+    }
+
+First, we need to talk about how the concrete rtree type is instantiated::
+
+    // Make the node capacity intentionally small.
+    struct tiny_trait_2d
+    {
+        constexpr static size_t dimensions = 2;
+        constexpr static size_t min_node_size = 2;
+        constexpr static size_t max_node_size = 5;
+        constexpr static size_t max_tree_depth = 100;
+
+        constexpr static bool enable_forced_reinsertion = true;
+        constexpr static size_t reinsertion_size = 2;
+    };
+
+    using rt_type = mdds::rtree<int, int, tiny_trait_2d>;
+
+The first and second template arguments specify the key and value types to be
+both ``int``.  This time around, however, we are passing a third template
+argument which is a struct containing several static constant values.  These
+constant values define certain characteristics of your R-tree, and there are
+some restrictions you need to be aware of in case you need to use your own
+custom trait for your R-tree.  Refer to
+:cpp:class:`~mdds::detail::rtree::default_rtree_traits`, which is the default
+trait used when you don't specify your own, for the descriptions of the
+individual constants that your trait struct is expected to have as well as
+restrictions that you must be aware of.
+
+Also be aware that these constants must all be constant expressions with
+``constexpr`` specifiers, as some of them are used within ``static_assert``
+declarations, and even those that are currently not used within
+``static_assert`` may be used in ``static_assert`` in the future.
+
+As far as our current example goes, the only part of the custom trait we need
+to highlight is that we are setting the directory node size to 2-to-5 instead
+of the default size of 40-to-100, to trigger more node splits and make the
+tree artificially deeper.
+
+Let's move on to the next part of the code::
+
+    // 2D rectangle with the top-left position (x, y), width and height.
+    struct rect
+    {
+        int x;
+        int y;
+        int w;
+        int h;
+    };
+
+    std::vector<rect> rects =
+    {
+        {  3731,  2433, 1356,  937 },
+        {  6003,  3172, 1066,  743 },
+        {  4119,  6403,  825, 1949 },
+        { 10305,  2315,  776,  548 },
+        { 13930,  5468, 1742,  626 },
+        {  8614,  4107, 2709, 1793 },
+        { 14606,  1887, 5368, 1326 },
+        { 17990,  5196, 1163, 1911 },
+        {  6728,  7881, 3676, 1210 },
+        { 14704,  9789, 5271, 1092 },
+        {  4071, 10723, 4739,  898 },
+        { 11755,  9010, 1357, 2806 },
+        { 13978,  4068,  776,  509 },
+        { 17507,  3717,  777,  471 },
+        { 20358,  6092,  824, 1093 },
+        {  6390,  4535, 1066, 1715 },
+        { 13978,  7182, 2516, 1365 },
+        { 17942, 11580, 2854,  665 },
+        {  9919, 10450,  873, 1716 },
+        {  5568, 13215, 7446,  509 },
+        {  7357, 15277, 3145, 3234 },
+        {  3539, 12592,  631,  509 },
+        {  4747, 14498,  825,  626 },
+        {  4554, 16913,  969, 1443 },
+        { 12771, 14693, 2323,  548 },
+        { 18714,  8193, 2372,  586 },
+        { 22292,  2743,  487, 1638 },
+        { 20987, 17535, 1163, 1249 },
+        { 19536, 18859,  632,  431 },
+        { 19778, 15394, 1356,  626 },
+        { 22969, 15394,  631, 2066 },
+    };
+
+This ``rects`` variable holds an array of 2-dimensional rectangle data that
+represent the positions and sizes of rectangles shown earlier in this section.
+This will be used as bounding rectangles for the input values in the next part
+of the code::
+
+    rt_type tree;
+
+    // Insert the rectangle objects into the tree.
+    int value = 0;
+    for (const auto& rect : rects)
+        tree.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
+
+Here, the tree is instantiated, and the rectangles are inserted with their
+associated values one at a time.  Once the tree is populated, the code that
+follows will export the structure of the tree as an SVG string, which will
+then be saved to a file on disk::
+
+    // Export the tree structure as a SVG for visualization.
+    std::string tree_svg = tree.export_tree(rt_type::export_tree_type::extent_as_svg);
+    std::ofstream fout("bounds.svg");
+    fout << tree_svg;
+
+When you open the exported SVG file named **bounds.svg** in a SVG viewer,
+you'll see something similar to this:
+
+.. figure:: _static/images/rtree_bounds_tree.png
+   :align: center
+
+which depicts not only the bounding rectangles of the inserted values
+(the red rectangles), but also the bounding rectangles of the directory
+nodes as well (the light green rectangles).
+
+
+Bulk-loading data
+-----------------
+
+In this section we will explore on how to bulk-load data into an
+:cpp:class:`~mdds::rtree` instance via rtree's own
+:cpp:class:`~mdds::rtree::bulk_loader` class.  In this example, we'll be using
+the same custom trait we've used in the previous section in order to
+artificially promote the rate of node splits.  The first part of the code::
+
+    #include <mdds/rtree.hpp>
+
+    #include <iostream>
+    #include <fstream>
+
+    // Make the node capacity intentionally small.
+    struct tiny_trait_2d
+    {
+        constexpr static size_t dimensions = 2;
+        constexpr static size_t min_node_size = 2;
+        constexpr static size_t max_node_size = 5;
+        constexpr static size_t max_tree_depth = 100;
+
+        constexpr static bool enable_forced_reinsertion = true;
+        constexpr static size_t reinsertion_size = 2;
+    };
+
+    using rt_type = mdds::rtree<int, int, tiny_trait_2d>;
+
+is pretty much identical to the example in the last section.  The next part of
+the code defines what bounding rectangles to be inserted.  Here, we are using
+a different set of rectangles than the previous example to illustrate the
+difference between a series of normal insertions and bulk-loading::
+
+    // 2D rectangle with the top-left position (x, y), width and height.
+    struct rect
+    {
+        int x;
+        int y;
+        int w;
+        int h;
+    };
+
+    std::vector<rect> rects =
+    {
+        {  3538,  9126, 1908,  1908 },
+        { 34272, 52053, 2416,  2543 },
+        { 32113,  9761, 2416,   638 },
+        { 16493, 16747, 7369,  2289 },
+        { 29192, 23732, 3432,  2035 },
+        { 35797, 17000, 1781,   892 },
+        { 15857, 29319, 2162,  1654 },
+        {  5825, 24239, 3559,  8512 },
+        {  9127, 46846, 2543,  1019 },
+        {  7094, 54338, 5210,   892 },
+        { 18779, 39734, 3813, 10417 },
+        { 32749, 35923, 2289,  2924 },
+        { 26018, 31098,  257,  2797 },
+        {  6713, 37066, 2924,  1146 },
+        { 19541,  3157, 3305,  1146 },
+        { 21953, 10904, 4448,   892 },
+        { 15984, 24240, 5210,  1273 },
+        {  8237, 15350, 2670,  2797 },
+        { 17001, 13826, 4067,  1273 },
+        { 30970, 13826, 3940,   765 },
+        {  9634,  6587, 1654,  1781 },
+        { 38464, 47099,  511,  1400 },
+        { 20556, 54085, 1400,  1527 },
+        { 37575, 24113, 1019,   765 },
+        { 20429, 21064, 1146,  1400 },
+        { 31733,  4427, 2543,   638 },
+        {  2142, 27161, 1273,  7369 },
+        {  3920, 43289, 8131,  1146 },
+        { 14714, 34272, 1400,  4956 },
+        { 38464, 41258, 1273,  1273 },
+        { 35542, 45703,  892,  1273 },
+        { 25891, 50783, 1273,  5083 },
+        { 35415, 28431, 2924,  1781 },
+        { 15476,  7349, 1908,   765 },
+        { 12555, 11159, 1654,  2035 },
+        { 11158, 21445, 1908,  2416 },
+        { 23350, 28049, 3432,   892 },
+        { 28684, 15985, 2416,  4321 },
+        { 24620, 21953, 1654,   638 },
+        { 30208, 30716, 2670,  2162 },
+        { 26907, 44179, 2797,  4067 },
+        { 21191, 35416, 2162,  1019 },
+        { 27668, 38717,  638,  3178 },
+        {  3666, 50528, 2035,  1400 },
+        { 15349, 48750, 2670,  1654 },
+        { 28430,  7221, 2162,   892 },
+        {  4808,  3158, 2416,  1273 },
+        { 38464,  3666, 1527,  1781 },
+        {  2777, 20937, 2289,  1146 },
+        { 38209,  9254, 1908,  1781 },
+        {  2269, 56497, 2289,   892 },
+    };
+
+As with the previous example, each line contains the top-left position as well
+as the size of a rectangle.  We are now going to insert these rectangles in
+two different ways.
+
+First, we insert them via normal :cpp:func:`~mdds::rtree::insert` method::
+
+    void load_tree()
+    {
+        rt_type tree;
+
+        // Insert the rectangle objects into the tree.
+        int value = 0;
+        for (const auto& rect : rects)
+            tree.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
+
+        // Export the tree structure as a SVG for visualization.
+        std::string tree_svg = tree.export_tree(rt_type::export_tree_type::extent_as_svg);
+        std::ofstream fout("bounds2.svg");
+        fout << tree_svg;
+    }
+
+This code should look familiar since it's nearly identical to the code in the
+previous section.  After the insertion is done, we export the tree as an SVG
+to visualize its structure.
+
+Next, we insert the same set of rectangles via
+:cpp:class:`~mdds::rtree::bulk_loader`::
+
+    void bulkload_tree()
+    {
+        rt_type::bulk_loader loader;
+
+        // Insert the rectangle objects into the tree.
+        int value = 0;
+        for (const auto& rect : rects)
+            loader.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
+
+        // Start bulk-loading the tree.
+        rt_type tree = loader.pack();
+
+        // Export the tree structure as a SVG for visualization.
+        std::string tree_svg = tree.export_tree(rt_type::export_tree_type::extent_as_svg);
+        std::ofstream fout("bounds2-bulkload.svg");
+        fout << tree_svg;
+    }
+
+Inserting via :cpp:class:`~mdds::rtree::bulk_loader` shouldn't be too
+different than inserting via rtree's own insert methods.  The only
+difference is that you instantiate a
+:cpp:class:`~mdds::rtree::bulk_loader` instance to insert all your data
+to it, then call its :cpp:func:`~mdds::rtree::bulk_loader::pack` method
+at the end to construct the final :cpp:class:`~mdds::rtree` instance.
+
+When the insertion is done and the tree instance created, we are once again
+exporting its structure to an SVG file for visualization.
+
+There are primarily two advantages to using
+:cpp:class:`~mdds::rtree::bulk_loader` to load data.  First, unlike the
+normal insertion, bulk-loading does not trigger re-insertion nor node
+splits on the fly.  Second, a tree created from bulk loader is typically
+well balanced than if you insert the same data through normal insertion.
+That is because the bulk loader sorts the data with respect to their
+bounding rectangles ahead of time and partition them evenly.  The tree
+is then built from the bottom-up.  You can visually see the effect of
+this when comparing the two trees built in our current example.
+
+The first one is from the tree built via normal insertion:
+
+.. figure:: _static/images/rtree_bounds2_tree.png
+   :align: center
+
+The top part of the picture looks very "busy" indicated by a darker
+green area representative of more directory nodes overlaping with each
+other.  In general, the rectangles look bigger and show higher degree of
+overlaps.
+
+This one, on the other hand, is from the tree built with the same data
+set but through bulk-loading:
+
+.. figure:: _static/images/rtree_bounds2_tree_bulkload.png
+   :align: center
+
+The rectangles generally look smaller and show much less overlaps than the
+previous picture, which is considered to be a more balanced R-tree structure.
+
+
+API Reference
+-------------
+
+.. doxygenclass:: mdds::rtree
+   :members:
+
+.. doxygenstruct:: mdds::detail::rtree::default_rtree_traits
+   :members:
+
+.. doxygenstruct:: mdds::detail::rtree::integrity_check_properties
+   :members:
+
+.. doxygenenum:: mdds::detail::rtree::export_tree_type
+   :project: mdds
+
+.. doxygenenum:: mdds::detail::rtree::search_type
+   :project: mdds