MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
ForestIndex.cpp
Go to the documentation of this file.
1#include "ForestIndex.hpp"
2
3namespace MayaFlux::Kakshya {
4
5std::optional<ForestIndex> ForestIndex::build(
6 std::span<const uint64_t> parents, std::string& error, uint64_t* error_row)
7{
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) {
11 if (error_row)
12 *error_row = row;
13 error = "row parent must precede its child";
14 return std::nullopt;
15 }
16 }
17
18 ForestIndex index;
19 index.m_parent.assign(parents.begin(), parents.end());
20
21 index.m_subtree_size.assign(count, 1);
22 for (size_t row = count; row-- > 0;) {
23 if (parents[row] != no_parent)
24 index.m_subtree_size[parents[row]] += index.m_subtree_size[row];
25 }
26
27 index.m_depth.assign(count, 0);
28 index.m_child_offset.assign(count + 1, 0);
29 for (size_t row = 0; row < count; ++row) {
30 if (parents[row] == no_parent) {
31 index.m_roots.push_back(row);
32 } else {
33 index.m_depth[row] = index.m_depth[parents[row]] + 1;
34 ++index.m_child_offset[parents[row] + 1];
35 }
36 }
37 for (size_t row = 0; row < count; ++row)
38 index.m_child_offset[row + 1] += index.m_child_offset[row];
39
40 index.m_child_row.resize(index.m_child_offset[count]);
41 std::vector<uint64_t> fill(index.m_child_offset.begin(), index.m_child_offset.end() - 1);
42 for (size_t row = 0; row < count; ++row) {
43 if (parents[row] != no_parent)
44 index.m_child_row[fill[parents[row]]++] = row;
45 }
46
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]];
53 if (next != row) {
54 index.m_preorder = false;
55 break;
56 }
57 next += index.m_subtree_size[row];
58 }
59 return index;
60}
61
62std::optional<uint64_t> ForestIndex::parent(size_t row) const noexcept
63{
64 if (row >= m_parent.size() || m_parent[row] == no_parent)
65 return std::nullopt;
66 return m_parent[row];
67}
68
69std::span<const uint64_t> ForestIndex::children(size_t row) const noexcept
70{
71 if (row >= m_parent.size())
72 return {};
73 const uint64_t begin = m_child_offset[row];
74 return { m_child_row.data() + begin, static_cast<size_t>(m_child_offset[row + 1] - begin) };
75}
76
77size_t ForestIndex::subtree_size(size_t row) const noexcept
78{
79 return row < m_subtree_size.size() ? static_cast<size_t>(m_subtree_size[row]) : 0;
80}
81
82uint32_t ForestIndex::depth(size_t row) const noexcept
83{
84 return row < m_depth.size() ? m_depth[row] : 0;
85}
86
87std::optional<RowRange> ForestIndex::subtree_range(size_t row) const noexcept
88{
89 if (!m_preorder || row >= m_parent.size())
90 return std::nullopt;
91 return RowRange { .first = row, .count = static_cast<size_t>(m_subtree_size[row]) };
92}
93
94}
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.