18template <FieldArray Array,
typename Parent>
20 const Array& array, Parent&& parent, std::string& error,
21 uint64_t* error_row =
nullptr)
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);
30 error =
"row is unreadable";
33 const std::optional<uint64_t> link = std::invoke(parent, *element);
70template <FieldArray Array>
73 using Element = std::remove_cvref_t<decltype(*std::declval<const Array&>().at(
size_t {}))>;
102 using Slice =
decltype(
m_array->slice(
size_t {},
size_t {}));
103 const auto range =
m_index->subtree_range(row);
106 return m_array->slice(range->first, range->count);
110 template <
typename Fn>
113 for (
const uint64_t root :
m_index->roots()) {
114 if (!
visit(root, fn))
121 template <
typename Fn>
124 for (
const uint64_t child :
m_index->children(row)) {
125 if (!
visit(child, fn))
132 template <
typename Fn>
135 for (
auto parent =
m_index->parent(row); parent; parent =
m_index->parent(*parent)) {
136 if (!
visit(*parent, fn))
147 template <
typename Fn>
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))
158 std::vector<uint64_t> pending;
160 while (!pending.empty()) {
161 const uint64_t next = pending.back();
163 if (!
visit(next, fn))
176 template <
typename Acc,
typename Fn>
180 init = std::invoke(fn, std::move(init), row, *
element);
182 init = std::invoke(fn, std::move(init), next, value);
188 template <
typename Fn>
189 bool visit(
size_t row, Fn& fn)
const
194 if constexpr (std::same_as<std::invoke_result_t<Fn&, size_t, const Element&>,
bool>) {
195 return std::invoke(fn, row, *
element);
197 std::invoke(fn, row, *
element);
204 const auto children =
m_index->children(row);
205 pending.insert(pending.end(), children.rbegin(), children.rend());
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.
const ForestIndex * m_index
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.
bool visit(size_t row, Fn &fn) const
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.