core_algorithms.h

Go to the documentation of this file.

// Copyright (c) 2026 Tinverse LLC. All rights reserved.
// SPDX-License-Identifier: LicenseRef-Tinverse-Commercial
 
 
#pragma once
 
#include <array>
#include <cstddef>
#include <cstdint>
#include <type_traits>
 
#include "tsm/transition.h"
#include "tsm/type_list.h"
 
namespace tsm::core {
 
inline constexpr std::uint16_t npos = 0xFFFFU;
 
template<std::size_t Capacity>
struct static_path {
    std::array<std::uint16_t, Capacity> values{};
    std::size_t size{};
 
    constexpr void push_back(std::uint16_t value) {
        if (size < Capacity) {
            values[size++] = value;
        }
    }
 
    [[nodiscard]] constexpr std::uint16_t operator[](std::size_t index) const {
        return values[index];
    }
 
    [[nodiscard]] constexpr bool contains(std::uint16_t value) const {
        for (std::size_t i = 0; i < size; ++i) {
            if (values[i] == value) {
                return true;
            }
        }
        return false;
    }
 
    [[nodiscard]] constexpr static_path reversed() const {
        static_path result{};
        for (std::size_t i = 0; i < size; ++i) {
            result.push_back(values[size - 1U - i]);
        }
        return result;
    }
 
    [[nodiscard]] constexpr bool operator==(static_path const& other) const {
        if (size != other.size) {
            return false;
        }
        for (std::size_t i = 0; i < size; ++i) {
            if (values[i] != other.values[i]) {
                return false;
            }
        }
        return true;
    }
};
 
template<typename T, typename... Ts>
consteval std::size_t index_in_pack() {
    constexpr std::array<bool, sizeof...(Ts)> matches{
      std::is_same_v<T, Ts>...
    };
    for (std::size_t i = 0; i < matches.size(); ++i) {
        if (matches[i]) {
            return i;
        }
    }
    return static_cast<std::size_t>(-1);
}
 
template<typename T, typename... Ts>
consteval bool contains_type() {
    return (std::is_same_v<T, Ts> || ...);
}
 
template<typename List>
struct type_set;
 
template<typename... Ts>
struct type_set<tsm::detail::type_list<Ts...>> {
    static constexpr std::size_t size = sizeof...(Ts);
 
    template<typename T>
    static consteval std::uint16_t index() {
        constexpr auto value = index_in_pack<T, Ts...>();
        static_assert(value != static_cast<std::size_t>(-1),
                      "tsm: type is not in this type_set");
        return static_cast<std::uint16_t>(value);
    }
 
    template<typename T>
    static consteval bool contains() {
        return contains_type<T, Ts...>();
    }
};
 
template<typename TransitionList>
concept transition_list_like =
  tsm::detail::type_list_like<TransitionList> &&
  tsm::detail::type_list_traits::all_satisfy<
    tsm::detail::is_transition,
    TransitionList>::value;
 
template<transition_list_like TransitionList>
struct transition_table;
 
 
template<typename Transition>
struct transition_states {
    using type =
      tsm::detail::type_list<typename Transition::from, typename Transition::to>;
};
 
template<typename TransitionList>
struct get_states;
 
template<tsm::detail::transition_edge_like... TransitionEntries>
struct get_states<tsm::detail::type_list<TransitionEntries...>> {
    using type = typename tsm::detail::unique_tuple<
      tsm::detail::concat_type_lists_t<
        typename transition_states<TransitionEntries>::type...>,
      tsm::detail::type_list<>>::type;
};
 
template<typename TransitionList>
using get_states_t = typename get_states<TransitionList>::type;
 
template<typename TransitionList>
struct get_events;
 
template<tsm::detail::transition_edge_like... TransitionEntries>
struct get_events<tsm::detail::type_list<TransitionEntries...>> {
    using type = typename tsm::detail::unique_tuple<
      tsm::detail::type_list<typename TransitionEntries::event...>,
      tsm::detail::type_list<>>::type;
};
 
template<typename TransitionList>
using get_events_t = typename get_events<TransitionList>::type;
 
template<typename From, typename Event, typename Transition>
inline constexpr bool same_trigger_v =
  std::is_same_v<typename Transition::from, From> &&
  std::is_same_v<typename Transition::event, Event>;
 
template<typename From, typename Event, typename... TransitionEntries>
consteval std::size_t trigger_count() {
    return (std::size_t{ 0 } + ... +
            (same_trigger_v<From, Event, TransitionEntries>
               ? std::size_t{ 1 }
               : std::size_t{ 0 }));
}
 
template<typename From, typename Event, typename... TransitionEntries>
consteval bool duplicate_group_is_guarded() {
    return ((same_trigger_v<From, Event, TransitionEntries>
               ? tsm::detail::transition_has_guard<TransitionEntries>
               : true) &&
            ...);
}
 
template<typename From, typename Event, typename... TransitionEntries>
consteval std::size_t duplicate_group_unguarded_count() {
    return (std::size_t{ 0 } + ... +
            (same_trigger_v<From, Event, TransitionEntries> &&
                 !tsm::detail::transition_has_guard<TransitionEntries>
               ? std::size_t{ 1 }
               : std::size_t{ 0 }));
}
 
template<typename From, typename Event, typename... TransitionEntries>
consteval bool trigger_group_is_valid() {
    constexpr auto count = trigger_count<From, Event, TransitionEntries...>();
    if constexpr (count <= 1U) {
        return true;
    } else if constexpr (tsm::detail::decision_pseudostate_like<From> &&
                         std::is_same_v<Event, tsm::detail::automatic_event>) {
        return duplicate_group_unguarded_count<From,
                                               Event,
                                               TransitionEntries...>() <= 1U;
    } else {
        return duplicate_group_is_guarded<From, Event, TransitionEntries...>();
    }
}
 
template<typename... TransitionEntries>
consteval bool transition_triggers_are_valid() {
    return (trigger_group_is_valid<typename TransitionEntries::from,
                                   typename TransitionEntries::event,
                                   TransitionEntries...>() &&
            ...);
}
 
template<tsm::detail::transition_like... TransitionEntries>
struct transition_table<tsm::detail::type_list<TransitionEntries...>> {
    using list = tsm::detail::type_list<TransitionEntries...>;
    using states = get_states_t<list>;
    using events = get_events_t<list>;
    using state_set = type_set<states>;
    using event_set = type_set<events>;
 
    static constexpr std::size_t transition_count = sizeof...(TransitionEntries);
    static constexpr std::size_t state_count = state_set::size;
    static constexpr bool valid_triggers =
      transition_triggers_are_valid<TransitionEntries...>();
 
    template<typename State>
    static consteval std::uint16_t state_index() {
        return state_set::template index<State>();
    }
 
    template<typename Event>
    static consteval std::uint16_t event_index() {
        if constexpr (event_set::template contains<Event>()) {
            return event_set::template index<Event>();
        } else {
            return npos;
        }
    }
 
    template<typename Transition>
    static consteval std::uint16_t transition_type_index() {
        constexpr std::array<bool, sizeof...(TransitionEntries)> matches{
          std::is_same_v<Transition, TransitionEntries>...
        };
        for (std::size_t i = 0; i < matches.size(); ++i) {
            if (matches[i]) {
                return static_cast<std::uint16_t>(i);
            }
        }
        return npos;
    }
 
    template<typename From, typename Event>
    static consteval bool has_transition() {
        return ((std::is_same_v<typename TransitionEntries::from, From> &&
                 std::is_same_v<typename TransitionEntries::event, Event>) ||
                ...);
    }
 
    template<typename From, typename Event>
    static consteval std::uint16_t transition_index() {
        constexpr std::array<bool, sizeof...(TransitionEntries)> matches{
          (std::is_same_v<typename TransitionEntries::from, From> &&
           std::is_same_v<typename TransitionEntries::event, Event>)...
        };
        for (std::size_t i = 0; i < matches.size(); ++i) {
            if (matches[i]) {
                return static_cast<std::uint16_t>(i);
            }
        }
        return npos;
    }
};
 
template<typename Child, typename Parent>
struct parent {
    using child = Child;
    using parent_state = Parent;
};
 
template<typename Composite, typename Initial>
struct initial_child {
    using composite = Composite;
    using initial = Initial;
};
 
template<typename ParentList>
struct parent_map_from_list;
 
template<typename... Parents>
struct parent_map_from_list<tsm::detail::type_list<Parents...>> {
    using type = tsm::detail::type_map<
      tsm::detail::type_map_entry<typename Parents::child,
                                  typename Parents::parent_state>...>;
};
 
template<typename ParentList>
using parent_map_from_list_t = typename parent_map_from_list<ParentList>::type;
 
template<typename InitialChildList>
struct initial_child_map_from_list;
 
template<typename... InitialChildren>
struct initial_child_map_from_list<tsm::detail::type_list<InitialChildren...>> {
    using type = tsm::detail::type_map<
      tsm::detail::type_map_entry<typename InitialChildren::composite,
                                  typename InitialChildren::initial>...>;
};
 
template<typename InitialChildList>
using initial_child_map_from_list_t =
  typename initial_child_map_from_list<InitialChildList>::type;
 
template<typename Root, typename States, typename Parents, typename InitialChildren>
struct hierarchy;
 
template<typename Context, typename Root = Context>
struct infer_hierarchy;
 
namespace detail {
 
template<typename Context>
struct inferred_root {};
 
} // namespace detail
 
template<typename Context, typename Root = detail::inferred_root<Context>>
using infer_hierarchy_t = typename infer_hierarchy<Context, Root>::type;
 
template<typename Root,
         typename... States,
         typename... Parents,
         typename... InitialChildren>
struct hierarchy<Root,
                 tsm::detail::type_list<States...>,
                 tsm::detail::type_list<Parents...>,
                 tsm::detail::type_list<InitialChildren...>> {
    using states = tsm::detail::type_list<States...>;
    using state_set = type_set<tsm::detail::type_list<States...>>;
    static constexpr std::size_t state_count = sizeof...(States);
    static constexpr std::size_t max_depth = state_count;
 
    template<typename State>
    static consteval std::uint16_t state_index() {
        return state_set::template index<State>();
    }
 
    template<typename State>
    static consteval std::uint16_t parent_index() {
        constexpr std::array<bool, sizeof...(Parents)> matches{
          std::is_same_v<State, typename Parents::child>...
        };
        constexpr std::array<std::uint16_t, sizeof...(Parents)> parent_ids{
          state_index<typename Parents::parent_state>()...
        };
        for (std::size_t i = 0; i < matches.size(); ++i) {
            if (matches[i]) {
                return parent_ids[i];
            }
        }
        return npos;
    }
 
    template<typename State>
    static consteval std::uint16_t initial_child_index() {
        constexpr std::array<bool, sizeof...(InitialChildren)> matches{
          std::is_same_v<State, typename InitialChildren::composite>...
        };
        constexpr std::array<std::uint16_t, sizeof...(InitialChildren)> child_ids{
          state_index<typename InitialChildren::initial>()...
        };
        for (std::size_t i = 0; i < matches.size(); ++i) {
            if (matches[i]) {
                return child_ids[i];
            }
        }
        return npos;
    }
 
    [[nodiscard]] static constexpr std::uint16_t parent_index(
      std::uint16_t state) {
        constexpr std::array<std::uint16_t, state_count> parents{
          parent_index<States>()...
        };
        return state < parents.size() ? parents[state] : npos;
    }
 
    [[nodiscard]] static constexpr std::uint16_t initial_child_index(
      std::uint16_t state) {
        constexpr std::array<std::uint16_t, state_count> initial_children{
          initial_child_index<States>()...
        };
        return state < initial_children.size() ? initial_children[state] : npos;
    }
 
    [[nodiscard]] static constexpr static_path<max_depth> ancestors(
      std::uint16_t state) {
        static_path<max_depth> result{};
        auto current = parent_index(state);
        while (current != npos) {
            result.push_back(current);
            current = parent_index(current);
        }
        return result;
    }
 
    [[nodiscard]] static constexpr static_path<max_depth> path_from_root(
      std::uint16_t state) {
        static_path<max_depth> leaf_to_root{};
        leaf_to_root.push_back(state);
        auto parent = parent_index(state);
        while (parent != npos) {
            leaf_to_root.push_back(parent);
            parent = parent_index(parent);
        }
        return leaf_to_root.reversed();
    }
 
    [[nodiscard]] static constexpr std::uint16_t least_common_ancestor(
      std::uint16_t a,
      std::uint16_t b) {
        static_path<max_depth> a_path{};
        a_path.push_back(a);
        auto parent = parent_index(a);
        while (parent != npos) {
            a_path.push_back(parent);
            parent = parent_index(parent);
        }
 
        auto current = b;
        while (current != npos) {
            if (a_path.contains(current)) {
                return current;
            }
            current = parent_index(current);
        }
        return npos;
    }
 
    [[nodiscard]] static constexpr static_path<max_depth> states_from_leaf_up_to(
      std::uint16_t source,
      std::uint16_t stop) {
        static_path<max_depth> result{};
        auto current = source;
        while (current != npos && current != stop) {
            result.push_back(current);
            current = parent_index(current);
        }
        return result;
    }
 
    [[nodiscard]] static constexpr static_path<max_depth> states_from_lca_down_to(
      std::uint16_t lca,
      std::uint16_t destination) {
        return states_from_leaf_up_to(destination, lca).reversed();
    }
 
    [[nodiscard]] static constexpr static_path<max_depth> enter_initial_children(
      std::uint16_t state) {
        static_path<max_depth> result{};
        auto current = initial_child_index(state);
        while (current != npos) {
            result.push_back(current);
            current = initial_child_index(current);
        }
        return result;
    }
};
 
template<std::size_t Capacity>
struct transition_sequence {
    std::uint16_t destination{ npos };
    std::uint16_t lca{ npos };
    static_path<Capacity> exits{};
    static_path<Capacity> entries{};
    static_path<Capacity> final_path{};
};
 
template<typename Hierarchy>
[[nodiscard]] constexpr auto compute_transition_sequence(
  std::uint16_t source,
  std::uint16_t destination) {
    transition_sequence<Hierarchy::max_depth> sequence{};
    sequence.destination = destination;
    sequence.lca = Hierarchy::least_common_ancestor(source, destination);
    if (sequence.lca == npos) {
        return sequence;
    }
 
    sequence.exits = Hierarchy::states_from_leaf_up_to(source, sequence.lca);
    auto direct_entries =
      Hierarchy::states_from_lca_down_to(sequence.lca, destination);
    for (std::size_t i = 0; i < direct_entries.size; ++i) {
        sequence.entries.push_back(direct_entries[i]);
    }
 
    auto initial_entries = Hierarchy::enter_initial_children(destination);
    for (std::size_t i = 0; i < initial_entries.size; ++i) {
        sequence.entries.push_back(initial_entries[i]);
    }
 
    auto prefix = Hierarchy::path_from_root(sequence.lca);
    for (std::size_t i = 0; i < prefix.size; ++i) {
        sequence.final_path.push_back(prefix[i]);
    }
    for (std::size_t i = 0; i < sequence.entries.size; ++i) {
        sequence.final_path.push_back(sequence.entries[i]);
    }
    return sequence;
}
 
template<typename Hierarchy>
[[nodiscard]] constexpr auto compute_local_transition_sequence(
  std::uint16_t active_leaf,
  std::uint16_t selected_source,
  std::uint16_t destination) {
    transition_sequence<Hierarchy::max_depth> sequence{};
    sequence.destination = destination;
    sequence.lca = selected_source;
 
    if (Hierarchy::least_common_ancestor(active_leaf, selected_source) !=
        selected_source) {
        sequence.lca = npos;
        return sequence;
    }
    if (Hierarchy::least_common_ancestor(selected_source, destination) !=
        selected_source) {
        sequence.lca = npos;
        return sequence;
    }
 
    sequence.exits =
      Hierarchy::states_from_leaf_up_to(active_leaf, selected_source);
 
    auto direct_entries =
      Hierarchy::states_from_lca_down_to(selected_source, destination);
    for (std::size_t i = 0; i < direct_entries.size; ++i) {
        sequence.entries.push_back(direct_entries[i]);
    }
 
    auto initial_entries = Hierarchy::enter_initial_children(destination);
    for (std::size_t i = 0; i < initial_entries.size; ++i) {
        sequence.entries.push_back(initial_entries[i]);
    }
 
    auto prefix = Hierarchy::path_from_root(selected_source);
    for (std::size_t i = 0; i < prefix.size; ++i) {
        sequence.final_path.push_back(prefix[i]);
    }
    for (std::size_t i = 0; i < sequence.entries.size; ++i) {
        sequence.final_path.push_back(sequence.entries[i]);
    }
    return sequence;
}
 
template<typename Hierarchy>
[[nodiscard]] constexpr auto compute_reentering_transition_sequence(
  std::uint16_t active_leaf,
  std::uint16_t selected_source,
  std::uint16_t destination) {
    transition_sequence<Hierarchy::max_depth> sequence{};
    sequence.destination = destination;
 
    if (Hierarchy::least_common_ancestor(active_leaf, selected_source) !=
        selected_source) {
        return sequence;
    }
 
    const auto parent = Hierarchy::parent_index(selected_source);
    sequence.lca = parent == npos ? selected_source : parent;
 
    if (Hierarchy::least_common_ancestor(sequence.lca, destination) !=
        sequence.lca) {
        sequence.lca = npos;
        return sequence;
    }
 
    sequence.exits = Hierarchy::states_from_leaf_up_to(active_leaf, sequence.lca);
 
    auto direct_entries =
      Hierarchy::states_from_lca_down_to(sequence.lca, destination);
    for (std::size_t i = 0; i < direct_entries.size; ++i) {
        sequence.entries.push_back(direct_entries[i]);
    }
 
    auto initial_entries = Hierarchy::enter_initial_children(destination);
    for (std::size_t i = 0; i < initial_entries.size; ++i) {
        sequence.entries.push_back(initial_entries[i]);
    }
 
    auto prefix = Hierarchy::path_from_root(sequence.lca);
    for (std::size_t i = 0; i < prefix.size; ++i) {
        sequence.final_path.push_back(prefix[i]);
    }
    for (std::size_t i = 0; i < sequence.entries.size; ++i) {
        sequence.final_path.push_back(sequence.entries[i]);
    }
    return sequence;
}
 
namespace detail {
 
template<typename Context>
struct context_transition_list {
    using type = tsm::detail::as_type_list_t<
      tsm::detail::transitions_of_t<Context>>;
};
 
template<typename Context>
using context_transition_list_t =
  typename context_transition_list<Context>::type;
 
template<typename Context>
using direct_states_t = get_states_t<context_transition_list_t<Context>>;
 
template<typename Context>
using direct_state_set_t = tsm::detail::type_set<direct_states_t<Context>>;
 
template<typename State, typename Parent, bool IsComposite>
struct nested_states_for_state {
    using type = tsm::detail::type_list<>;
};
 
template<typename State, typename Parent>
struct nested_states_for_state<State, Parent, true> {
    using type = typename infer_hierarchy<State, State>::states;
};
 
template<typename DirectStates, typename Parent>
struct nested_states_for_list;
 
template<typename Parent, typename... States>
struct nested_states_for_list<tsm::detail::type_list<States...>, Parent> {
    using type = tsm::detail::concat_type_lists_t<
      typename nested_states_for_state<States,
                                       Parent,
                                       tsm::detail::has_transitions_c<States>>::type...>;
};
 
template<typename State, bool IsComposite>
struct nested_transitions_for_state {
    using type = tsm::detail::type_list<>;
};
 
template<typename State>
struct nested_transitions_for_state<State, true> {
    using type = typename infer_hierarchy<State, State>::transitions;
};
 
template<typename DirectStates>
struct nested_transitions_for_list;
 
template<typename... States>
struct nested_transitions_for_list<tsm::detail::type_list<States...>> {
    using type = tsm::detail::concat_type_lists_t<
      typename nested_transitions_for_state<States,
                                            tsm::detail::has_transitions_c<States>>::type...>;
};
 
template<typename State, typename Parent, bool IsFinal, bool IsHistory>
struct inferred_parent_for_state {
    using type = Parent;
};
 
template<typename State, typename Parent>
struct inferred_parent_for_state<State, Parent, true, false> {
    using type = typename State::final_parent;
};
 
template<typename State, typename Parent>
struct inferred_parent_for_state<State, Parent, false, true> {
    using type = typename State::history_parent;
};
 
template<typename State, typename Parent, bool IsComposite>
struct parent_edges_for_state {
    using inferred_parent =
      typename inferred_parent_for_state<
        State,
        Parent,
        tsm::detail::final_state_like<State>,
        tsm::detail::history_state_like<State>>::type;
    using type = tsm::detail::type_list<parent<State, inferred_parent>>;
};
 
template<typename State, typename Parent>
struct parent_edges_for_state<State, Parent, true> {
    using nested = typename infer_hierarchy<State, State>::parents;
    using type =
      tsm::detail::concat_type_lists_t<tsm::detail::type_list<parent<State, Parent>>,
                                       nested>;
};
 
template<typename DirectStates, typename Parent>
struct parent_edges_for_list;
 
template<typename Parent, typename... States>
struct parent_edges_for_list<tsm::detail::type_list<States...>, Parent> {
    using type = tsm::detail::concat_type_lists_t<
      typename parent_edges_for_state<States,
                                      Parent,
                                      tsm::detail::has_transitions_c<States>>::type...>;
};
 
template<typename State, bool IsComposite>
struct initial_edges_for_state {
    using type = tsm::detail::type_list<>;
};
 
template<typename State>
struct initial_edges_for_state<State, true> {
    using nested = infer_hierarchy<State, State>;
    using type =
      tsm::detail::concat_type_lists_t<tsm::detail::type_list<
                                         initial_child<State,
                                                       typename nested::initial>>,
                                       typename nested::initial_children>;
};
 
template<typename DirectStates>
struct initial_edges_for_list;
 
template<typename... States>
struct initial_edges_for_list<tsm::detail::type_list<States...>> {
    using type = tsm::detail::concat_type_lists_t<
      typename initial_edges_for_state<States,
                                       tsm::detail::has_transitions_c<States>>::type...>;
};
 
template<typename State, bool IsComposite>
struct local_leaf_states_for_state {
    using type = tsm::detail::type_list<State>;
};
 
template<typename State>
struct local_leaf_states_for_state<State, true> {
    using type = typename infer_hierarchy<State, State>::leaf_states;
};
 
template<typename DirectStates>
struct local_leaf_states_for_list;
 
template<typename... States>
struct local_leaf_states_for_list<tsm::detail::type_list<States...>> {
    using type = tsm::detail::concat_type_lists_t<
      typename local_leaf_states_for_state<States,
                                           tsm::detail::has_transitions_c<States>>::type...>;
};
 
} // namespace detail
 
template<typename Context, typename Root>
struct infer_hierarchy {
    using direct_transitions = detail::context_transition_list_t<Context>;
    using direct_states = detail::direct_states_t<Context>;
    using direct_state_set = detail::direct_state_set_t<Context>;
 
    using nested_states =
      typename detail::nested_states_for_list<direct_states, Root>::type;
 
    using states =
      typename tsm::detail::unique_tuple<
        tsm::detail::concat_type_lists_t<tsm::detail::type_list<Root>,
                                         direct_states,
                                         nested_states>,
        tsm::detail::type_list<>>::type;
 
    using parents =
      typename detail::parent_edges_for_list<direct_states, Root>::type;
    using initial_children =
      typename detail::initial_edges_for_list<direct_states>::type;
 
    using local_leaf_states =
      typename detail::local_leaf_states_for_list<direct_states>::type;
    using leaf_states = local_leaf_states;
    using initial = tsm::detail::front_type_t<direct_states>;
 
    using transitions =
      tsm::detail::concat_type_lists_t<
        direct_transitions,
        typename detail::nested_transitions_for_list<direct_states>::type>;
    struct type : hierarchy<Root, states, parents, initial_children> {
        using transitions = infer_hierarchy::transitions;
    };
};
 
} // namespace tsm::core