6 std::span<const uint64_t> parents, std::string& error, uint64_t* error_row)
8 const size_t count = parents.size();
9 for (
size_t row = 0; row < count; ++row) {
10 if (parents[row] !=
no_parent && parents[row] >= row) {
13 error =
"row parent must precede its child";
19 index.
m_parent.assign(parents.begin(), parents.end());
22 for (
size_t row = count; row-- > 0;) {
29 for (
size_t row = 0; row < count; ++row) {
37 for (
size_t row = 0; row < count; ++row)
42 for (
size_t row = 0; row < count; ++row) {
47 std::vector<uint64_t> expected(count);
48 for (
size_t row = 0; row < count; ++row)
49 expected[row] = row + 1;
50 uint64_t expected_root = 0;
51 for (
size_t row = 0; row < count; ++row) {
52 uint64_t& next = parents[row] ==
no_parent ? expected_root : expected[parents[row]];
std::vector< uint64_t > m_child_row
std::optional< RowRange > subtree_range(size_t row) const noexcept
Consecutive rows of the subtree of row.
std::vector< uint64_t > m_parent
std::optional< uint64_t > parent(size_t row) const noexcept
Parent row, or nullopt for a root or an out of range row.
static constexpr uint64_t no_parent
Parent value of a root row.
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.
std::vector< uint64_t > m_subtree_size
uint32_t depth(size_t row) const noexcept
Distance from the root of row; zero when out of range.
std::vector< uint64_t > m_roots
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.
std::vector< uint64_t > m_child_offset
std::vector< uint32_t > m_depth
size_t subtree_size(size_t row) const noexcept
Rows in the subtree of row, including row itself; zero when out of range.
Parent, child, depth and subtree structure over rows linked by parent index.
Consecutive rows starting at first.