R-tree
Overview
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 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
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 rtree
including the number
of dimensions. By default, 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 insert()
method as a nested
initializer list, which implicitly gets converted to
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
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:
inserting value for (-2, -1) - (1, 2)
As extent_type
consists of two members called
start
and end
both of which are of type
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:
inserting value for (-1, -1) - (1, 3)
So far we have only inserted data associated with rectangle shapes, but
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 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:
value: first rectangle data
value: first point data
indicating that the query region does overlap with two of the stored values
Note that the 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
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:
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:
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 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
search_results
object does provide
begin()
and
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:
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
extent()
and
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:
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
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 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:
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
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.

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
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:

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
rtree
instance via rtree’s own
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 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
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 bulk_loader
shouldn’t be too
different than inserting via rtree’s own insert methods. The only
difference is that you instantiate a
bulk_loader
instance to insert all your data
to it, then call its pack()
method
at the end to construct the final 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
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:

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:

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
-
template<typename KeyT, typename ValueT, typename Traits = detail::rtree::default_rtree_traits>
class rtree Public Types
-
using node_type = detail::rtree::node_type
-
using export_tree_type = detail::rtree::export_tree_type
-
using search_type = detail::rtree::search_type
-
using integrity_check_properties = detail::rtree::integrity_check_properties
Public Functions
-
rtree()
-
~rtree()
-
void insert(const extent_type &extent, value_type &&value)
Insert a new value associated with a bounding box. The new value object will be moved into the container.
- Parameters:
extent – bounding box associated with the value.
value – value being inserted.
-
void insert(const extent_type &extent, const value_type &value)
Insert a new value associated with a bounding box. A copy of the new value object will be placed into the container.
- Parameters:
extent – bounding box associated with the value.
value – value being inserted.
-
void insert(const point_type &position, value_type &&value)
Insert a new value associated with a point. The new value object will be moved into the container.
- Parameters:
position – point associated with the value.
value – value being inserted.
-
void insert(const point_type &position, const value_type &value)
Insert a new value associated with a point. A copy of the new value object will be placed into the container.
- Parameters:
position – point associated with the value.
value – value being inserted.
-
const_search_results search(const point_type &pt, search_type st) const
Search the tree and collect all value objects whose extents either contain the specified point, or exactly match the specified point.
- Parameters:
pt – reference point to use for the search.
st – search type that determines the satisfying condition of the search with respect to the reference point.
- Returns:
collection of all value objects that satisfy the specified search condition. This collection is immutable.
-
search_results search(const point_type &pt, search_type st)
Search the tree and collect all value objects whose extents either contain the specified point, or exactly match the specified point.
- Parameters:
pt – reference point to use for the search.
st – search type that determines the satisfying condition of the search with respect to the reference point.
- Returns:
collection of all value objects that satisfy the specified search condition. This collection is mutable.
-
const_search_results search(const extent_type &extent, search_type st) const
Search the tree and collect all value objects whose extents either overlaps with the specified extent, or exactly match the specified extent.
- Parameters:
extent – reference extent to use for the search.
st – search type that determines the satisfying condition of the search with respect to the reference extent.
- Returns:
collection of all value objects that satisfy the specified search condition. This collection is immutable.
-
search_results search(const extent_type &extent, search_type st)
Search the tree and collect all value objects whose extents either overlaps with the specified extent, or exactly match the specified extent.
- Parameters:
extent – reference extent to use for the search.
st – search type that determines the satisfying condition of the search with respect to the reference extent.
- Returns:
collection of all value objects that satisfy the specified search condition. This collection is mutable.
-
void erase(const const_iterator &pos)
Erase the value object referenced by the iterator passed to this method.
The iterator object will become invalid if the call results in an erasure of a value.
- Parameters:
pos – iterator that refernces the value object to erase.
-
void erase(const iterator &pos)
Erase the value object referenced by the iterator passed to this method.
The iterator object will become invalid if the call results in an erasure of a value.
- Parameters:
pos – iterator that refernces the value object to erase.
-
const extent_type &extent() const
Get the minimum bounding extent of the root node of the tree. The extent returned from this method is the minimum extent that contains the extents of all objects stored in the tree.
- Returns:
immutable reference to the extent of the root node of the tree.
-
bool empty() const
Check whether or not the tree stores any objects.
- Returns:
true if the tree is empty, otherwise false.
-
size_t size() const
Return the number of value nodes currently stored in the tree.
- Returns:
number of value nodes currently in the tree.
-
void swap(rtree &other)
Swap the content of the tree with another instance.
- Parameters:
other – another instance to swap the content with.
-
void clear()
Empty the entire container.
-
template<typename FuncT>
void walk(FuncT func) const Walk down the entire tree depth first.
- Parameters:
func – function or function object that gets called at each node in the tree.
-
void check_integrity(const integrity_check_properties &props) const
Check the integrity of the entire tree structure.
- Parameters:
props – specify how the check is to be performed.
- Throws:
integrity_error – if the integrity check fails.
-
std::string export_tree(export_tree_type mode) const
Export the structure of a tree in textural format.
- Parameters:
mode – specify the format in which to represent the structure of a tree.
- Returns:
string representation of the tree structure.
-
class bulk_loader
Loader optimized for loading a large number of value objects. A resultant tree will have a higher chance of being well balanced than if the value objects were inserted individually into the tree.
Public Functions
-
bulk_loader()
-
void insert(const extent_type &extent, value_type &&value)
-
void insert(const extent_type &extent, const value_type &value)
-
void insert(const point_type &position, value_type &&value)
-
void insert(const point_type &position, const value_type &value)
-
bulk_loader()
-
class const_iterator : public mdds::rtree<KeyT, ValueT, Traits>::iterator_base<const_iterator, const_search_results::store_type::const_iterator, const rtree::value_type>
Public Types
-
using value_type = _ValueT
-
using value_type = _ValueT
-
class const_search_results : public mdds::rtree<KeyT, ValueT, Traits>::search_results_base<const node_store>
Public Functions
-
const_iterator cbegin() const
-
const_iterator cend() const
-
const_iterator begin() const
-
const_iterator end() const
-
const_iterator cbegin() const
-
struct extent_type
Public Functions
-
extent_type()
-
extent_type(const point_type &_start, const point_type &_end)
-
std::string to_string() const
-
bool is_point() const
-
bool operator==(const extent_type &other) const
-
bool operator!=(const extent_type &other) const
-
bool contains(const point_type &pt) const
Determine whether or not the specified point lies within this extent.
- Parameters:
pt – point to query with.
- Returns:
true if the point lies within this extent, or false otherwise.
-
bool contains(const extent_type &bb) const
Determine whether or not the specified extent lies entirely within this extent.
- Parameters:
bb – extent to query with.
- Returns:
true if the specified extent lies entirely within this extent, or otherwise false.
-
bool intersects(const extent_type &bb) const
Determine whether or not the specified extent overlaps with this extent either partially or fully.
- Parameters:
bb – extent to query with.
- Returns:
true if the specified extent overlaps with this extent, or otherwise false.
-
bool contains_at_boundary(const extent_type &other) const
Determine whether or not another bounding box is within this bounding box and shares a part of its boundaries.
-
extent_type()
-
class iterator : public mdds::rtree<KeyT, ValueT, Traits>::iterator_base<iterator, search_results::store_type::iterator, rtree::value_type>
Public Types
-
using value_type = _ValueT
-
using value_type = _ValueT
-
template<typename _SelfIter, typename _StoreIter, typename _ValueT>
class iterator_base Public Types
-
using store_iterator_type = _StoreIter
-
using pointer = value_type*
-
using reference = value_type&
-
using difference_type = std::ptrdiff_t
-
using iterator_category = std::bidirectional_iterator_tag
Public Functions
-
bool operator==(const self_iterator_type &other) const
-
bool operator!=(const self_iterator_type &other) const
-
self_iterator_type &operator++()
-
self_iterator_type operator++(int)
-
self_iterator_type &operator--()
-
self_iterator_type operator--(int)
-
const extent_type &extent() const
-
size_t depth() const
-
using store_iterator_type = _StoreIter
-
struct node_properties
-
struct point_type
Public Functions
-
point_type()
-
std::string to_string() const
-
bool operator==(const point_type &other) const
-
bool operator!=(const point_type &other) const
-
point_type()
-
template<typename NS>
class search_results_base
-
using node_type = detail::rtree::node_type
-
struct default_rtree_traits
Public Static Attributes
-
static constexpr size_t dimensions = 2
Number of dimensions in bounding rectangles.
-
static constexpr size_t min_node_size = 40
Minimum number of child nodes that must be present in each directory node. Exception is the root node, which is allowed to have less than the minimum number of nodes, but only when it’s a leaf directory node.
-
static constexpr size_t max_node_size = 100
Maximum number of child nodes that each directory node is allowed to have. There are no exceptions to this rule.
-
static constexpr size_t max_tree_depth = 100
Maximum depth a tree is allowed to have.
-
static constexpr bool enable_forced_reinsertion = true
A flag to determine whether or not to perform forced reinsertion when a directory node overflows, before attempting to split the node.
-
static constexpr size_t reinsertion_size = 30
Number of nodes to get re-inserted during forced reinsertion. This should be roughly 30% of max_node_size + 1, and should not be greater than max_node_size - min_node_size + 1.
-
static constexpr size_t dimensions = 2
-
struct integrity_check_properties
Public Members
-
bool throw_on_first_error = true
When true, the integrity check will throw an exception on the first validation failure. When false, it will run through the entire tree and report all encountered validation failures then throw an exception if there is at least one failure.
-
bool error_on_min_node_size = true
When true, a node containing children less than the minimum node size will be treated as an error.
-
bool throw_on_first_error = true
-
enum class mdds::detail::rtree::export_tree_type
Values:
-
enumerator formatted_node_properties
Textural representation of a tree structure. Indent levels represent depths, and each line represents a single node.
-
enumerator extent_as_obj
The extents of all directory and value nodes are exported as Wavefront .obj format. Only 2 dimensional trees are supported for now.
For a 2-dimensional tree, each depth is represented by a 2D plane filled with rectangles representing the extents of either value or directory nodes at that depth level. The depth planes are then stacked vertically.
-
enumerator extent_as_svg
The extents of all directory and value nodes are exported as a scalable vector graphics (SVG) format. Only 2 dimensional trees are supported.
-
enumerator formatted_node_properties