MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches
ForestIndex.hpp
Go to the documentation of this file.
1#pragma once
2
3namespace MayaFlux::Kakshya {
4
5/**
6 * @struct RowRange
7 * @brief Consecutive rows starting at first.
8 */
9struct RowRange {
10 size_t first {};
11 size_t count {};
12};
13
14/**
15 * @class ForestIndex
16 * @brief Parent, child, depth and subtree structure over rows linked by parent index.
17 *
18 * Built once from one parent per row. A row with no parent is a root. Every
19 * parent precedes its children, so the links form a forest and cannot loop.
20 * When each subtree also occupies consecutive rows (document preorder) the
21 * index reports preorder() and a subtree is the row range
22 * [row, row + subtree_size(row)). Such a range is an ordinary slice or
23 * one-axis Region of the source, so existing windows, traversals and
24 * projections apply to a subtree without any copy.
25 *
26 * The index stores no row data and does not refer to its source; the caller
27 * keeps it matched to the array it was built from.
28 *
29 * Usage:
30 * @code
31 * std::vector<uint64_t> parents { ForestIndex::no_parent, 0, 0, 2 };
32 * std::string error;
33 * auto index = ForestIndex::build(parents, error);
34 * auto kids = index->children(0);
35 * auto range = index->subtree_range(2);
36 * @endcode
37 */
38class MAYAFLUX_API ForestIndex {
39public:
40 /** @brief Parent value of a root row. */
41 static constexpr uint64_t no_parent = std::numeric_limits<uint64_t>::max();
42
43 /**
44 * @brief Build the index from one parent per row.
45 * @param parents Parent row of each row, or no_parent for a root.
46 * @param error Receives the reason when nullopt is returned.
47 * @param error_row Receives the failing row when given.
48 * @return The index, or nullopt when a parent does not precede its child.
49 */
50 [[nodiscard]] static std::optional<ForestIndex> build(
51 std::span<const uint64_t> parents, std::string& error,
52 uint64_t* error_row = nullptr);
53
54 /** @brief Number of rows. */
55 [[nodiscard]] size_t size() const noexcept { return m_parent.size(); }
56
57 /** @brief Parent row, or nullopt for a root or an out of range row. */
58 [[nodiscard]] std::optional<uint64_t> parent(size_t row) const noexcept;
59
60 /** @brief Direct children in row order; empty for a leaf or an out of range row. */
61 [[nodiscard]] std::span<const uint64_t> children(size_t row) const noexcept;
62
63 /** @brief Rows without a parent, in row order. */
64 [[nodiscard]] std::span<const uint64_t> roots() const noexcept { return m_roots; }
65
66 /** @brief Rows in the subtree of row, including row itself; zero when out of range. */
67 [[nodiscard]] size_t subtree_size(size_t row) const noexcept;
68
69 /** @brief Distance from the root of row; zero when out of range. */
70 [[nodiscard]] uint32_t depth(size_t row) const noexcept;
71
72 /** @brief Whether every subtree occupies consecutive rows. */
73 [[nodiscard]] bool preorder() const noexcept { return m_preorder; }
74
75 /**
76 * @brief Consecutive rows of the subtree of row.
77 * @return The range, or nullopt when the rows are not preorder or row is out of range.
78 */
79 [[nodiscard]] std::optional<RowRange> subtree_range(size_t row) const noexcept;
80
81private:
82 std::vector<uint64_t> m_parent;
83 std::vector<uint64_t> m_subtree_size;
84 std::vector<uint32_t> m_depth;
85 std::vector<uint64_t> m_child_offset;
86 std::vector<uint64_t> m_child_row;
87 std::vector<uint64_t> m_roots;
88 bool m_preorder { true };
89};
90
91}
std::vector< uint64_t > m_child_row
std::span< const uint64_t > roots() const noexcept
Rows without a parent, in row order.
size_t size() const noexcept
Number of rows.
std::vector< uint64_t > m_parent
bool preorder() const noexcept
Whether every subtree occupies consecutive rows.
static constexpr uint64_t no_parent
Parent value of a root row.
std::vector< uint64_t > m_subtree_size
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
Parent, child, depth and subtree structure over rows linked by parent index.
Consecutive rows starting at first.