ndtree::v1::tree< nd > Struct Template Reference

Description

template<int nd>
struct ndtree::v1::tree< nd >

nd-octree data-structure

nd-tree

Spatial constants
static constexpr int_t	dimension () noexcept
	Number of spatial dimensions of the tree.
static constexpr auto	dimensions () noexcept
	Range of spatial dimensions of the tree: [0, nd)
static constexpr uint_t	no_children () noexcept
	Number of children per node.
static constexpr uint_t	position_in_parent (node_idx n) noexcept
	Position of node n within its parent. More...

Graph edges (parent/children)
using	child_pos = bounded< uint_t, 0, no_children(), struct child_pos_tag >
	Child position type is a uint_t bounded in [0, no_children)
static constexpr siblings_idx	sibling_group (node_idx n) noexcept
	Index of the sibling group of node n.
static constexpr auto	child_positions () noexcept
	Range of child positions: [0, no_children)
static constexpr auto	nodes (siblings_idx s) noexcept
	Nodes in sibling group s.
static constexpr bool	is_root (node_idx n) noexcept
	Is n the root node?
node_idx	parent (siblings_idx s) const noexcept
	Index of the parent node of the sibling group s.
node_idx	parent (node_idx n) const noexcept
	Index of the parent node of node n.
siblings_idx	children_group (node_idx n) const noexcept
	Index of the group of children of node n.
node_idx	child (node_idx n, child_pos p) const noexcept
	Child node at position p of node n.
auto	children (node_idx n) const noexcept
	Range of children nodes of node n.
void	set_first_free_sibling_group (siblings_idx s) noexcept
	Sets the first free sibling group to s.
auto	operator() () const noexcept
	All nodes in use within the tree (fast and safe) More...
auto	nodes () const noexcept
	All nodes in use within the tree (slow and safe) More...
auto	leaf () const noexcept
	Range filter that selects leaf nodes only.
auto	with_children () const noexcept
	Range filter that selects nodes with children only.
bool	is_leaf (node_idx n) const noexcept
	Is node n a leaf node? (That is, does it have zero children?)
uint_t	no_children (node_idx n) const noexcept
	Number of childrens of the node n.
bool	is_compact () const noexcept
	Does the tree have a compact representation? More...

Memory management
static constexpr siblings_idx	no_sibling_groups (node_idx no_nodes) noexcept
	Number of sibling groups required to hold no_nodes nodes.
static constexpr node_idx	no_nodes (siblings_idx no_sibling_groups) noexcept
	Number of nodes that can be holded by no_sibling_groups sibling groups.
siblings_idx	sibling_group_capacity () const noexcept
	Maximum number of sibling groups that the tree can hold.
node_idx	capacity () const noexcept
	Maximum number of nodes that the tree can hold.
node_idx	size () const noexcept
	Number of nodes in the tree.
bool	empty () const noexcept
	Is the tree empty?
siblings_idx	refine (node_idx p) noexcept
	Refine node p and returns children group idx. More...
void	coarsen (node_idx p) noexcept
	Coarsen node p. More...
void	swap (siblings_idx a, siblings_idx b) noexcept
	Swaps the memory location of the sibling groups a and b. More...

Public Member Functions
	tree (uint_t node_capacity)
	Creates a tree with capacity for at least cap nodes and initializes it with a root node.

Member Function Documentation

template<int nd>

static constexpr uint_t ndtree::v1::tree< nd >::position_in_parent ( node_idx  n )

staticnoexcept

Position of node n within its parent.

Postcondition

n == child(parent(n), position_in_parent(n))

References ndtree::v1::tree< nd >::no_children().

template<int nd>

auto ndtree::v1::tree< nd >::operator() ( ) const

noexcept

All nodes in use within the tree (fast and safe)

Precondition

the tree must be compact

References ndtree::v1::tree< nd >::is_compact().

template<int nd>

auto ndtree::v1::tree< nd >::nodes ( ) const

noexcept

All nodes in use within the tree (slow and safe)

Note

The tree does not need to be compact

Referenced by ndtree::v1::tree< nd >::swap().

template<int nd>

bool ndtree::v1::tree< nd >::is_compact ( ) const

noexcept

Does the tree have a compact representation?

That is, no free sibling groups before the last sibling group in use.

References ndtree::v1::tree< nd >::sibling_group(), and ndtree::v1::tree< nd >::size().

Referenced by ndtree::v1::tree< nd >::operator()().

template<int nd>

siblings_idx ndtree::v1::tree< nd >::refine ( node_idx  p )

noexcept

Refine node p and returns children group idx.

If refinement failed returns nothing.

Precondition

!is_free(p) && is_leaf(p)

Postcondition

!is_free(p) && !is_leaf(p)

References ndtree::v1::tree< nd >::capacity(), ndtree::v1::tree< nd >::children(), ndtree::v1::tree< nd >::is_leaf(), ndtree::v1::tree< nd >::no_children(), and ndtree::v1::tree< nd >::size().

template<int nd>

void ndtree::v1::tree< nd >::coarsen ( node_idx  p )

noexcept

Coarsen node p.

Precondition

!is_free(p) && !is_leaf(p) && is_leaf(children group of p)

Postcondition

!is_free(p) && is_leaf(p) && is_free(children group of p)

References ndtree::v1::tree< nd >::children_group(), ndtree::v1::tree< nd >::is_leaf(), and ndtree::v1::tree< nd >::no_children().

template<int nd>

void ndtree::v1::tree< nd >::swap ( siblings_idx  a, siblings_idx  b  )

noexcept

Swaps the memory location of the sibling groups a and b.

Precondition

no sibling group can be swapped with the root's node sibling group

no sibling group can be swapped with itself

Warning

not thread safe

1) swap siblings -> children edges, and children -> sibling edges:

2) swap parent -> sibling edges, and sibling -> parent edges:

3) update the first free sibling group flag:

• if one of the nodes is inactive:

References ndtree::v1::tree< nd >::children_group(), ndtree::v1::tree< nd >::nodes(), ndtree::v1::tree< nd >::parent(), and ndtree::v1::bit::swap().