MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
MayaFlux::Kakshya::DataForestTraversal< Array > Class Template Reference

On-demand walks over the parent links of an indexed array. More...

#include <DataForestTraversal.hpp>

Collaboration diagram for MayaFlux::Kakshya::DataForestTraversal< Array >:

Public Types

using Element = std::remove_cvref_t<decltype(*std::declval<const Array&>().at(size_t {}))>

Public Member Functions

 DataForestTraversal (const Array &array, const ForestIndex &index) noexcept
 Borrow an array and the index built from it.
auto element (size_t row) const
 Borrow one element by row.
template<typename Fn>
bool for_each_ancestor (size_t row, Fn &&fn) const
 Visit the ancestors of row, nearest first.
template<typename Fn>
bool for_each_child (size_t row, Fn &&fn) const
 Visit the direct children of row, in row order.
template<typename Fn>
bool for_each_descendant (size_t row, Fn &&fn) const
 Visit every descendant of row in document order, excluding row.
template<typename Fn>
bool for_each_root (Fn &&fn) const
 Visit the rows without a parent, in row order.
const ForestIndex & index () const noexcept
 The borrowed index.
bool matches () const
 Whether the index and array have the same number of rows.
template<typename Acc, typename Fn>
Acc reduce_subtree (size_t row, Acc init, Fn &&fn) const
 Fold row and its descendants into an accumulator.
auto subtree (size_t row) const
 Borrow the rows of the subtree of row, including row itself.

Private Member Functions

void push_children (std::vector< uint64_t > &pending, size_t row) const
template<typename Fn>
bool visit (size_t row, Fn &fn) const

Private Attributes

const Array * m_array
const ForestIndex * m_index

Detailed Description

template<FieldArray Array>
class MayaFlux::Kakshya::DataForestTraversal< Array >

On-demand walks over the parent links of an indexed array.

The sibling of DataFieldTraversal for hierarchical rows. It borrows an array and a ForestIndex built from that array's parent links, and walks children, ancestors, descendants and subtrees without owning either. When the rows are preorder, subtree() is an ordinary slice of the array, so a DataFieldTraversal over it windows, projects and reduces one branch with no copy. The same walks work with any FieldArray; neither this class nor the array names a record format.

Usage:

auto index = build_forest_index(rows, [](const auto& row) {
return row.template get<uint64_t>("parent");
}, error);
forest.for_each_child(0, [](size_t row, const auto& child) { });
if (auto branch = forest.subtree(2)) {
DataFieldTraversal<std::remove_cvref_t<decltype(*branch)>> window(*branch, 64);
}
const ForestIndex & index() const noexcept
The borrowed index.
On-demand walks over the parent links of an indexed array.
std::optional< ForestIndex > build_forest_index(const Array &array, Parent &&parent, std::string &error, uint64_t *error_row=nullptr)
Build a ForestIndex from an array whose elements carry a parent row.

Visitors take the row index and a borrowed element. A visitor returning bool stops the walk by returning false, and the walk then returns false. A row whose element cannot be borrowed is skipped, as in DataFieldTraversal.

Template Parameters
ArrayIndexed array satisfying FieldArray.
Note
The array and index must outlive the traversal and stay matched.

Definition at line 71 of file DataForestTraversal.hpp.


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