.. SPDX-FileCopyrightText: 2025 Kohei Yoshida .. .. SPDX-License-Identifier: MIT 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: type :end-before: //!code-end: type 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. .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: instantiate :end-before: //!code-end: instantiate :dedent: 4 Instantiating an rtree instance should be no brainer as it requires no input parameters. Now, let's insert some data: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: insert-1 :end-before: //!code-end: insert-1 :dedent: 4 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: insert-2 :end-before: //!code-end: insert-2 :dedent: 4 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: insert-3 :end-before: //!code-end: insert-3 :dedent: 4 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): .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: insert-pt-1 :end-before: //!code-end: insert-pt-1 :dedent: 4 Like the very first rectangle data we 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: search-overlap :end-before: //!code-end: search-overlap :dedent: 8 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: search-match-1 :end-before: //!code-end: search-match-1 :dedent: 8 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: search-match-2 :end-before: //!code-end: search-match-2 :dedent: 8 which is identical to the previous one except for the search region. 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: iterator-deref :end-before: //!code-end: iterator-deref :dedent: 8 which immediately follows the previous code block 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: .. literalinclude:: ../../example/rtree_simple.cpp :language: C++ :start-after: //!code-start: iterator-attrs :end-before: //!code-end: iterator-attrs :dedent: 8 Running this code will produce the following output: .. code-block:: none value: first rectangle data extent: (0, 0) - (15, 20) depth: 1 This depth value represents the distance of the node that stores the value 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 stores a value, hence it never appears in the search results.