layout.hpp

Go to the documentation of this file.

#pragma once
 
#include <array>
#include <cstddef>
 
namespace yorch::detail {
 
template <typename... Nodes>
[[nodiscard]] consteval auto make_level_array() {
    return std::array<std::size_t, sizeof...(Nodes)> {Nodes::level...};
}
 
template <std::size_t N>
[[nodiscard]] consteval auto make_slot_index_array() {
    std::array<std::size_t, N> indices {};
 
    for (std::size_t i = 0; i < N; ++i) {
        indices[i] = i;
    }
 
    return indices;
}
 
template <std::size_t N>
[[nodiscard]] consteval auto make_parent_index_array(const std::array<std::size_t, N>& levels) {
    std::array<std::size_t, N> parents {};
    parents.fill(N);
 
    if constexpr (N > 0) {
        parents[0] = N;
 
        for (std::size_t node = 1; node < N; ++node) {
            const auto target_level = levels[node] - 1;
 
            for (std::size_t cursor = node; cursor > 0; --cursor) {
                const auto candidate = cursor - 1;
 
                if (levels[candidate] == target_level) {
                    parents[node] = candidate;
                    break;
                }
            }
        }
    }
 
    return parents;
}
 
template <std::size_t N>
struct child_layout {
    std::array<std::size_t, N> counts {};
    std::array<std::size_t, N> offsets {};
    std::array<std::size_t, (N > 0 ? N - 1 : 0)> indices {};
};
 
template <std::size_t N>
[[nodiscard]] consteval auto make_child_layout(const std::array<std::size_t, N>& parents) {
    child_layout<N> layout {};
 
    if constexpr (N > 0) {
        for (std::size_t node = 1; node < N; ++node) {
            ++layout.counts[parents[node]];
        }
 
        std::size_t offset = 0;
        for (std::size_t node = 0; node < N; ++node) {
            layout.offsets[node] = offset;
            offset += layout.counts[node];
        }
 
        auto next_offsets = layout.offsets;
 
        for (std::size_t node = 1; node < N; ++node) {
            const auto parent = parents[node];
            layout.indices[next_offsets[parent]++] = node;
        }
    }
 
    return layout;
}
 
template <typename... Nodes>
inline constexpr auto compiled_levels_v = make_level_array<Nodes...>();
 
template <typename... Nodes>
inline constexpr auto compiled_parent_indices_v =
    make_parent_index_array(compiled_levels_v<Nodes...>);
 
template <typename... Nodes>
inline constexpr auto compiled_child_layout_v =
    make_child_layout(compiled_parent_indices_v<Nodes...>);
 
template <typename... Nodes>
inline constexpr auto compiled_slot_indices_v =
    make_slot_index_array<sizeof...(Nodes)>();
 
} // namespace yorch::detail