Skip to main content

class region_map_impl

Declaration

template <typename ValueType, int Dims>
class region_map_impl { /* full declaration omitted */ };

Description

The region map is implemented as a customized R-Tree [Guttman 1984]. In order to maintain performance over time, entries with compatible boxes and equal values will be merged. The implementation logic is split between this class, which acts as a wrapper around the root node, as well as inner_node, which implements the recursive tree operations. This class is responsible for dispatching the recursive calls as well as handling the merging of entries and reinsertion of orphaned entries/nodes after update operations. It is also responsible for merging the final list of query results. TODO PERF: Try to minimize the number of value copies we do during intermediate steps (e.g. when merging) TODO PERF: Look into bulk-loading algorithms for updating multiple boxes at once

Template Parameters

ValueType
int Dims

Member Variables

static const size_t dimensions = Dims
box<Dims> m_extent
std::unique_ptr<typename types::inner_node_type> m_root
std::vector<typename types::update_action> m_update_actions
std::vector<typename types::entry> m_merge_candidates
std::vector<typename types::entry> m_updated_nodes
std::vector<typename types::orphan> m_erase_orphans
std::vector<typename types::entry> m_query_results_raw
std::vector<typename types::entry> m_query_results_clamped

Member Aliases

  • using value_type = ValueType;
  • using types = region_map_types<ValueType, Dims>;

Member Function Overview

  • template <typename Functor>
    apply_to_values(const Functor & f) → void
  • format_to(fmt::format_context::iterator out) const → auto
  • get_extent() const → range<Dims>
  • get_region_values(const box<Dims> & request) const → std::vector<typename types::entry>
  • operator=(const region_map_impl<ValueType, Dims> &) → region_map_impl<ValueType, Dims> &
  • operator=(region_map_impl<ValueType, Dims> &&) noexcept → region_map_impl<ValueType, Dims> &
  • region_map_impl(const box<Dims> & extent, const ValueType & default_value = ValueType{})
  • region_map_impl(const region_map_impl<ValueType, Dims> &)
  • region_map_impl(region_map_impl<ValueType, Dims> &&) noexcept
  • update_box(const box<Dims> & box, const ValueType & value) → void
  • ~region_map_impl()
  • can_merge(const box<Dims> & box_a, const box<Dims> & box_b) const → bool
  • erase(const box<Dims> & box) → void
  • template <typename Callback>
    for_each(const Callback & cb) const → void
  • insert(const box<Dims> & box, const ValueType & value) → void
  • insert_subtree(const box<Dims> & box, typename types::unique_inner_node_ptr && subtree) → void
  • reroot(typename types::insert_result new_sibling) → void
  • try_merge(std::vector<typename types::entry> && merge_candidates) → void

Member Functions

template <typename Functor>
void apply_to_values(const Functor& f)

Description

Applies the provided functor to all values and attempts to merge all entries that had their values changed.

Template Parameters

Functor

Parameters

const Functor& f

auto format_to(
    fmt::format_context::iterator out) const

Parameters

fmt::format_context::iterator out

range<Dims> get_extent() const

std::vector<typename types::entry>
get_region_values(const box<Dims>& request) const

Description

Finds all entries intersecting with request, clamps them to the extent and merges them. TODO PERF: In most cases we are unlikely to store the returned values, and the copy is unnecessary. Return const reference instead?

Parameters

const box<Dims>& request

region_map_impl<ValueType, Dims>& operator=(
    const region_map_impl<ValueType, Dims>&)

Parameters

const region_map_impl<ValueType, Dims>& 

region_map_impl<ValueType, Dims>& operator=(
    region_map_impl<ValueType, Dims>&&) noexcept

Parameters

region_map_impl<ValueType, Dims>&& 

region_map_impl(
    const box<Dims>& extent,
    const ValueType& default_value = ValueType{})

Parameters

const box<Dims>& extent
const ValueType& default_value = ValueType{}

region_map_impl(
    const region_map_impl<ValueType, Dims>&)

Parameters

const region_map_impl<ValueType, Dims>& 

region_map_impl(
    region_map_impl<ValueType, Dims>&&) noexcept

Parameters

region_map_impl<ValueType, Dims>&& 

void update_box(const box<Dims>& box,
                const ValueType& value)

Description

Updates the value for the provided box within the tree. This operation consists of roughly three steps: 1) Prepare the tree by creating a "hole" for the new box. This usually means splitting existing boxes within the tree. The required set of operations is propagated back up the tree. In some situations an in-place or localized update can be performed, in this case step 2 is skipped (see inner_node::update_box). 2) Perform all erase and insert operations calculated in step 1. 3) Attempt to merge the box as well as any other newly created boxes with their surrounding entries.

Parameters

const box<Dims>& box
const ValueType& value

~region_map_impl()

bool can_merge(const box<Dims>& box_a,
               const box<Dims>& box_b) const

Description

Calculates whether two boxes can be merged. In order to be mergeable, the two boxes have to touch in one dimension and match exactly in all remaining dimensions.

Parameters

const box<Dims>& box_a
const box<Dims>& box_b

void erase(const box<Dims>& box)

Description

Erases a box from the tree. If the parent box becomes underfull it is dissolved and its children are reinserted.

Parameters

const box<Dims>& box

template <typename Callback>
void for_each(const Callback& cb) const

Description

Invokes the provided callback for every entry (box/value pair) within the region map, for debugging / testing / instrumentation.

Template Parameters

Callback

Parameters

const Callback& cb

void insert(const box<Dims>& box,
            const ValueType& value)

Description

Inserts a new entry into the tree. Precondition: The insert location must be empty.

Parameters

const box<Dims>& box
const ValueType& value

void insert_subtree(
    const box<Dims>& box,
    typename types::unique_inner_node_ptr&&
        subtree)

Description

Inserts a subtree (either from a dissolved parent or after a split) into the tree.

Parameters

const box<Dims>& box
typename types::unique_inner_node_ptr&& subtree

void reroot(
    typename types::insert_result new_sibling)

Description

Creates a new root node that is parent to the current root node and new_sibling, increasing the tree's height by 1.

Parameters

typename types::insert_result new_sibling

void try_merge(
    std::vector<typename types::entry>&&
        merge_candidates)

Description

Try to merge a list of candidate entries with their neighbors within the tree.

Parameters

std::vector<typename types::entry>&& merge_candidates