MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
DataForestTraversal.hpp
Go to the documentation of this file.
1#pragma once
2
4#include "ForestIndex.hpp"
5
6namespace MayaFlux::Kakshya {
7
8/**
9 * @brief Build a ForestIndex from an array whose elements carry a parent row.
10 * @tparam Array Indexed array satisfying FieldArray.
11 * @tparam Parent Callable taking a borrowed element and returning
12 * std::optional<uint64_t>; an empty result marks a root.
13 * @param error Receives the reason when nullopt is returned.
14 * @param error_row Receives the failing row when given.
15 * @return The index, or nullopt for an unreadable row or a parent that does
16 * not precede its child.
17 */
18template <FieldArray Array, typename Parent>
19[[nodiscard]] std::optional<ForestIndex> build_forest_index(
20 const Array& array, Parent&& parent, std::string& error,
21 uint64_t* error_row = nullptr)
22{
23 std::vector<uint64_t> parents;
24 parents.reserve(array.size());
25 for (size_t row = 0; row < array.size(); ++row) {
26 const auto element = array.at(row);
27 if (!element) {
28 if (error_row)
29 *error_row = row;
30 error = "row is unreadable";
31 return std::nullopt;
32 }
33 const std::optional<uint64_t> link = std::invoke(parent, *element);
34 parents.push_back(link.value_or(ForestIndex::no_parent));
35 }
36 return ForestIndex::build(parents, error, error_row);
37}
38
39/**
40 * @class DataForestTraversal
41 * @brief On-demand walks over the parent links of an indexed array.
42 *
43 * The sibling of DataFieldTraversal for hierarchical rows. It borrows an
44 * array and a ForestIndex built from that array's parent links, and walks
45 * children, ancestors, descendants and subtrees without owning either. When
46 * the rows are preorder, subtree() is an ordinary slice of the array, so a
47 * DataFieldTraversal over it windows, projects and reduces one branch with
48 * no copy. The same walks work with any FieldArray; neither this class nor
49 * the array names a record format.
50 *
51 * Usage:
52 * @code
53 * auto index = build_forest_index(rows, [](const auto& row) {
54 * return row.template get<uint64_t>("parent");
55 * }, error);
56 * DataForestTraversal<CompositeArray> forest(rows, *index);
57 * forest.for_each_child(0, [](size_t row, const auto& child) { });
58 * if (auto branch = forest.subtree(2)) {
59 * DataFieldTraversal<std::remove_cvref_t<decltype(*branch)>> window(*branch, 64);
60 * }
61 * @endcode
62 *
63 * Visitors take the row index and a borrowed element. A visitor returning
64 * bool stops the walk by returning false, and the walk then returns false.
65 * A row whose element cannot be borrowed is skipped, as in DataFieldTraversal.
66 *
67 * @tparam Array Indexed array satisfying FieldArray.
68 * @note The array and index must outlive the traversal and stay matched.
69 */
70template <FieldArray Array>
72public:
73 using Element = std::remove_cvref_t<decltype(*std::declval<const Array&>().at(size_t {}))>;
74
75 /**
76 * @brief Borrow an array and the index built from it.
77 * @param array Array that must outlive this traversal.
78 * @param index Index built from array's parent links; it must outlive this traversal.
79 */
80 DataForestTraversal(const Array& array, const ForestIndex& index) noexcept
81 : m_array(&array)
82 , m_index(&index)
83 {
84 }
85
86 /** @brief The borrowed index. */
87 [[nodiscard]] const ForestIndex& index() const noexcept { return *m_index; }
88
89 /** @brief Whether the index and array have the same number of rows. */
90 [[nodiscard]] bool matches() const { return m_array->size() == m_index->size(); }
91
92 /** @brief Borrow one element by row. */
93 [[nodiscard]] auto element(size_t row) const { return m_array->at(row); }
94
95 /**
96 * @brief Borrow the rows of the subtree of row, including row itself.
97 * @return The array's slice, or an empty result when the rows are not
98 * preorder, row is out of range, or the index does not match the array.
99 */
100 [[nodiscard]] auto subtree(size_t row) const
101 {
102 using Slice = decltype(m_array->slice(size_t {}, size_t {}));
103 const auto range = m_index->subtree_range(row);
104 if (!range || !matches())
105 return Slice {};
106 return m_array->slice(range->first, range->count);
107 }
108
109 /** @brief Visit the rows without a parent, in row order. */
110 template <typename Fn>
111 bool for_each_root(Fn&& fn) const
112 {
113 for (const uint64_t root : m_index->roots()) {
114 if (!visit(root, fn))
115 return false;
116 }
117 return true;
118 }
119
120 /** @brief Visit the direct children of row, in row order. */
121 template <typename Fn>
122 bool for_each_child(size_t row, Fn&& fn) const
123 {
124 for (const uint64_t child : m_index->children(row)) {
125 if (!visit(child, fn))
126 return false;
127 }
128 return true;
129 }
130
131 /** @brief Visit the ancestors of row, nearest first. */
132 template <typename Fn>
133 bool for_each_ancestor(size_t row, Fn&& fn) const
134 {
135 for (auto parent = m_index->parent(row); parent; parent = m_index->parent(*parent)) {
136 if (!visit(*parent, fn))
137 return false;
138 }
139 return true;
140 }
141
142 /**
143 * @brief Visit every descendant of row in document order, excluding row.
144 * @note Preorder rows take a sequential pass; other forests walk the
145 * child links depth first.
146 */
147 template <typename Fn>
148 bool for_each_descendant(size_t row, Fn&& fn) const
149 {
150 if (const auto range = m_index->subtree_range(row)) {
151 for (size_t next = range->first + 1; next < range->first + range->count; ++next) {
152 if (!visit(next, fn))
153 return false;
154 }
155 return true;
156 }
157
158 std::vector<uint64_t> pending;
159 push_children(pending, row);
160 while (!pending.empty()) {
161 const uint64_t next = pending.back();
162 pending.pop_back();
163 if (!visit(next, fn))
164 return false;
165 push_children(pending, next);
166 }
167 return true;
168 }
169
170 /**
171 * @brief Fold row and its descendants into an accumulator.
172 * @tparam Fn Callable returning the next accumulator from the accumulator,
173 * a row index and a borrowed element.
174 * @return Final accumulator.
175 */
176 template <typename Acc, typename Fn>
177 [[nodiscard]] Acc reduce_subtree(size_t row, Acc init, Fn&& fn) const
178 {
179 if (const auto element = m_array->at(row))
180 init = std::invoke(fn, std::move(init), row, *element);
181 for_each_descendant(row, [&](size_t next, const Element& value) {
182 init = std::invoke(fn, std::move(init), next, value);
183 });
184 return init;
185 }
186
187private:
188 template <typename Fn>
189 bool visit(size_t row, Fn& fn) const
190 {
191 const auto element = m_array->at(row);
192 if (!element)
193 return true;
194 if constexpr (std::same_as<std::invoke_result_t<Fn&, size_t, const Element&>, bool>) {
195 return std::invoke(fn, row, *element);
196 } else {
197 std::invoke(fn, row, *element);
198 return true;
199 }
200 }
201
202 void push_children(std::vector<uint64_t>& pending, size_t row) const
203 {
204 const auto children = m_index->children(row);
205 pending.insert(pending.end(), children.rbegin(), children.rend());
206 }
207
208 const Array* m_array;
210};
211
212}
auto subtree(size_t row) const
Borrow the rows of the subtree of row, including row itself.
bool matches() const
Whether the index and array have the same number of rows.
bool for_each_child(size_t row, Fn &&fn) const
Visit the direct children of row, in row order.
auto element(size_t row) const
Borrow one element by row.
void push_children(std::vector< uint64_t > &pending, size_t row) const
DataForestTraversal(const Array &array, const ForestIndex &index) noexcept
Borrow an array and the index built from it.
bool for_each_descendant(size_t row, Fn &&fn) const
Visit every descendant of row in document order, excluding row.
bool for_each_root(Fn &&fn) const
Visit the rows without a parent, in row order.
const ForestIndex & index() const noexcept
The borrowed index.
std::remove_cvref_t< decltype(*std::declval< const Array & >().at(size_t {}))> Element
bool for_each_ancestor(size_t row, Fn &&fn) const
Visit the ancestors of row, nearest first.
Acc reduce_subtree(size_t row, Acc init, Fn &&fn) const
Fold row and its descendants into an accumulator.
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.
Parent, child, depth and subtree structure over rows linked by parent index.
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.