API Reference¶

template<typename KeyT, typename ValueT, typename Traits = detail::rtree::default_rtree_traits> class rtree¶

Public Types

using key_type = KeyT ¶

using value_type = ValueT ¶

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(rtree &&other)¶

rtree(const rtree &other)¶

~rtree()¶

rtree &operator=(const rtree &other)¶

rtree &operator=(rtree &&other)¶

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_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(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)¶

rtree pack()¶

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¶

Public Functions

inline value_type &operator*() const¶

inline value_type *operator->() const¶

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¶

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.

Public Members

point_type start¶

point_type end¶

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¶

Public Functions

inline value_type &operator*()¶

inline value_type *operator->()¶

template<typename _SelfIter, typename _StoreIter, typename _ValueT> class iterator_base¶

Public Types

using store_iterator_type = _StoreIter ¶

using self_iterator_type = _SelfIter ¶

using value_type = _ValueT ¶

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¶

struct node_properties¶

Public Members

node_type type¶

extent_type extent¶

struct point_type¶

Public Functions

point_type()¶

point_type(std::initializer_list<key_type> vs)¶

std::string to_string() const¶

bool operator==(const point_type &other) const¶

bool operator!=(const point_type &other) const¶

Public Members

key_type d[traits_type::dimensions]¶

class search_results : public mdds::rtree<KeyT, ValueT, Traits>::search_results_base<node_store>¶

Public Functions

iterator begin()¶

iterator end()¶

template<typename NS> class search_results_base¶

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.

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.

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.

enum class mdds::detail::rtree::search_type¶

Values:

enumerator overlap¶: Pick up all objects whose extents overlap with the specified search extent.

enumerator match¶: Pick up all objects whose extents exactly match the specified search extent.