Skip to main content

class inner_node

Declaration

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

Template Parameters

ValueType
int Dims

Member Variables

size_t m_depth
bool m_contains_leaves
std::vector<box<Dims>> m_child_boxes
std::vector<typename types::inner_node_child_type> m_children

Member Aliases

  • using types = region_map_types<ValueType, Dims>;

Member Function Overview

  • template <typename Functor>
    apply_to_values(const Functor & f, std::vector<typename types::entry> & updated_nodes) → void
  • contains_leaves() const → bool
  • eject_only_child() → typename types::unique_inner_node_ptr
  • erase(const box<Dims> & box, std::vector<typename types::orphan> & orphans) → bool
  • template <typename Callback>
    for_each(const Callback & cb) const → void
  • format_to(fmt::format_context::iterator out, size_t level) const → auto
  • get_bounding_box() const → box<Dims>
  • get_depth() const → size_t
  • inner_node(inner_node<ValueType, Dims> &&) noexcept
  • inner_node(const inner_node<ValueType, Dims> &)
  • inner_node(bool contains_leaves, size_t depth)
  • insert(const box<Dims> & box, const ValueType & value) → std::optional<typename types::insert_result>
  • insert_child_node(const box<Dims> & box, std::unique_ptr<inner_node<ValueType, Dims>> && node) → void
  • insert_subtree(const box<Dims> & box, std::unique_ptr<inner_node<ValueType, Dims>> && subtree) → std::optional<typename types::insert_result>
  • num_children() const → size_t
  • operator=(inner_node<ValueType, Dims> &&) noexcept → inner_node<ValueType, Dims> &
  • operator=(const inner_node<ValueType, Dims> &) → inner_node<ValueType, Dims> &
  • point_query(const id<Dims> & point) const → std::optional<typename types::entry>
  • query(const box<Dims> & box, std::vector<typename types::entry> & intersecting) const → void
  • set_depth(size_t depth) → void
  • update_box(const box<Dims> & box, const ValueType & value, std::vector<typename types::update_action> & actions) → bool
  • ~inner_node()
  • erase_child(size_t index) → void
  • get_child_node(size_t index) → inner_node<ValueType, Dims> &
  • get_child_node(size_t index) const → const inner_node<ValueType, Dims> &
  • get_child_value(size_t index) → ValueType &
  • get_child_value(size_t index) const → const ValueType &
  • insert_child_value(const box<Dims> & box, const ValueType & value) → void
  • is_underfull() const → bool
  • pick_split_seeds() → std::pair<size_t, size_t>
  • sanity_check_bounding_boxes() const → box<Dims>

Member Functions

template <typename Functor>
void apply_to_values(
    const Functor& f,
    std::vector<typename types::entry>&
        updated_nodes)

Template Parameters

Functor

Parameters

const Functor& f
std::vector<typename types::entry>& updated_nodes

bool contains_leaves() const

Description

Whether this node contains leaves, i.e. ValueType entries, or more inner_nodes.

typename types::unique_inner_node_ptr
eject_only_child()

bool erase(
    const box<Dims>& box,
    std::vector<typename types::orphan>& orphans)

Description

Erases a box if it is contained in the subtree.

Parameters

const box<Dims>& box
std::vector<typename types::orphan>& orphans
A list of entries or subtrees that were orphaned due to dissolving a node.

Returns

True if the box was erased in this subtree.

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

Template Parameters

Callback

Parameters

const Callback& cb

auto format_to(fmt::format_context::iterator out,
               size_t level) const

Parameters

fmt::format_context::iterator out
size_t level

box<Dims> get_bounding_box() const

size_t get_depth() const

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

Parameters

inner_node<ValueType, Dims>&& 

inner_node(const inner_node<ValueType, Dims>&)

Parameters

const inner_node<ValueType, Dims>& 

inner_node(bool contains_leaves, size_t depth)

Parameters

bool contains_leaves
size_t depth

std::optional<typename types::insert_result>
insert(const box<Dims>& box,
       const ValueType& value)

Description

Inserts a the provided entry into the tree. It is assumed that the box fits into a currently existing hole and does not overlap with any other box in the subtree. TODO: Structurally very similar to insert_subtree - can we DRY up?

Parameters

const box<Dims>& box
const ValueType& value

Returns

If the insertion caused a node to be split, the spilled node is returned.

void insert_child_node(
    const box<Dims>& box,
    std::unique_ptr<inner_node<ValueType, Dims>>&&
        node)

Parameters

const box<Dims>& box
std::unique_ptr<inner_node<ValueType, Dims>>&& node

std::optional<typename types::insert_result>
insert_subtree(
    const box<Dims>& box,
    std::unique_ptr<inner_node<ValueType, Dims>>&&
        subtree)

Description

Inserts the given subtree as a child into this subtree, either directly or further down (depending on its depth). TODO: Structurally very similar to insert - can we DRY up?

Parameters

const box<Dims>& box
std::unique_ptr<inner_node<ValueType, Dims>>&& subtree

Returns

If the insertion caused a node to be split, the spilled node is returned.

size_t num_children() const

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

Parameters

inner_node<ValueType, Dims>&& 

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

Parameters

const inner_node<ValueType, Dims>& 

std::optional<typename types::entry> point_query(
    const id<Dims>& point) const

Description

Returns the entry containing a given point, if such an entry exists.

Parameters

const id<Dims>& point

void query(const box<Dims>& box,
           std::vector<typename types::entry>&
               intersecting) const

Description

Recursively finds all entries that intersect with box.

Parameters

const box<Dims>& box
std::vector<typename types::entry>& intersecting

void set_depth(size_t depth)

Description

Recursively sets depth on this node and all of its children.

Parameters

size_t depth

bool update_box(
    const box<Dims>& box,
    const ValueType& value,
    std::vector<typename types::update_action>&
        actions)

Description

Either updates the value of the given box directly, or prepares the subtree for insertion of said entry by creating a hole of the appropriate size. Inserting a new value usually means splitting up existing boxes within the tree (for example placing a smaller rectangle inside a larger one results in 5 total rectangles). This function calculates the set of actions required to perform such a split, which are then dispatched from the root. There are two special cases that can be handled more efficiently: - If the number of new boxes created due to a split is determined to fit inside this subtree without overflowing it, a localized update is performed, and no actions need to be dispatched from the root. - If the box to be updated matches an existing box inside this subtree exactly, an in-place update is performed and no further actions are required.

Parameters

const box<Dims>& box
const ValueType& value
std::vector<typename types::update_action>& actions
The list of erase and insert actions required to create a hole for the new entry.

Returns

True if a localized update operation was performed that may require a bounding box recomputation.

~inner_node()

void erase_child(size_t index)

Parameters

size_t index

inner_node<ValueType, Dims>& get_child_node(
    size_t index)

Parameters

size_t index

const inner_node<ValueType, Dims>& get_child_node(
    size_t index) const

Parameters

size_t index

ValueType& get_child_value(size_t index)

Parameters

size_t index

const ValueType& get_child_value(
    size_t index) const

Parameters

size_t index

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

Parameters

const box<Dims>& box
const ValueType& value

bool is_underfull() const

std::pair<size_t, size_t> pick_split_seeds()

box<Dims> sanity_check_bounding_boxes() const