Build the index from one parent per 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;) {
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) {
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) {
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}
static constexpr uint64_t no_parent
Parent value of a root row.
void error(Component component, Context context, std::source_location location, std::string_view message)
Log an error message and optionally throw an exception.
std::vector< double > count(std::span< const double > data, size_t n_windows, uint32_t hop_size, uint32_t window_size)
Sample count per window (as double for pipeline uniformity).