MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
MayaFlux::Kakshya::ForestIndex Class Reference

Parent, child, depth and subtree structure over rows linked by parent index. More...

#include <ForestIndex.hpp>

Collaboration diagram for MayaFlux::Kakshya::ForestIndex:

Public Member Functions

std::span< const uint64_t > children (size_t row) const noexcept
 Direct children in row order; empty for a leaf or an out of range row.
uint32_t depth (size_t row) const noexcept
 Distance from the root of row; zero when out of range.
std::optional< uint64_t > parent (size_t row) const noexcept
 Parent row, or nullopt for a root or an out of range row.
bool preorder () const noexcept
 Whether every subtree occupies consecutive rows.
std::span< const uint64_t > roots () const noexcept
 Rows without a parent, in row order.
size_t size () const noexcept
 Number of rows.
std::optional< RowRange > subtree_range (size_t row) const noexcept
 Consecutive rows of the subtree of row.
size_t subtree_size (size_t row) const noexcept
 Rows in the subtree of row, including row itself; zero when out of range.

Static Public Member Functions

static std::optional< ForestIndex > build (std::span< const uint64_t > parents, std::string &error, uint64_t *error_row=nullptr)
 Build the index from one parent per row.

Static Public Attributes

static constexpr uint64_t no_parent = std::numeric_limits<uint64_t>::max()
 Parent value of a root row.

Private Attributes

std::vector< uint64_t > m_child_offset
std::vector< uint64_t > m_child_row
std::vector< uint32_t > m_depth
std::vector< uint64_t > m_parent
bool m_preorder { true }
std::vector< uint64_t > m_roots
std::vector< uint64_t > m_subtree_size

Detailed Description

Parent, child, depth and subtree structure over rows linked by parent index.

Built once from one parent per row. A row with no parent is a root. Every parent precedes its children, so the links form a forest and cannot loop. When each subtree also occupies consecutive rows (document preorder) the index reports preorder() and a subtree is the row range [row, row + subtree_size(row)). Such a range is an ordinary slice or one-axis Region of the source, so existing windows, traversals and projections apply to a subtree without any copy.

The index stores no row data and does not refer to its source; the caller keeps it matched to the array it was built from.

Usage:

std::vector<uint64_t> parents { ForestIndex::no_parent, 0, 0, 2 };
std::string error;
auto index = ForestIndex::build(parents, error);
auto kids = index->children(0);
auto range = index->subtree_range(2);
static constexpr uint64_t no_parent
Parent value of a root row.
static std::optional< ForestIndex > build(std::span< const uint64_t > parents, std::string &error, uint64_t *error_row=nullptr)
Build the index from one parent per row.

Definition at line 38 of file ForestIndex.hpp.


The documentation for this class was generated from the following files: