turingStyleMConfigurationTuringMachineTransition.h

#pragma once
 
#include <utils/compare.h>
#include <utils/printer.h>
#include <symbol/turingMachineSymbolPattern.h>
#include <transition/Turing/localTuringMachineTransition.h>
#include <transition/Turing/mConfigurationTuringMachineTransition.h>
 
namespace TuringSim::Transition::Turing {
 
    template<typename T, bool hasHalfTape>
    class TuringStyleMConfigurationTuringMachineTransition
            : public MConfigurationTuringMachineTransition<T, T, hasHalfTape>
    {
        typedef MConfigurationTuringMachineTransition<T, T, hasHalfTape> MConfigurationTuringMachineTransition_;
    public:
        using typename MConfigurationTuringMachineTransition_::Movement;
        using typename MConfigurationTuringMachineTransition_::StateType;
        using typename MConfigurationTuringMachineTransition_::SymbolType;
        using typename MConfigurationTuringMachineTransition_::HasHalfTape;
        using typename MConfigurationTuringMachineTransition_::StorageType;
        using typename MConfigurationTuringMachineTransition_::NodeStateType;
        using typename MConfigurationTuringMachineTransition_::ApplyHelperType;
        using typename MConfigurationTuringMachineTransition_::SubstitutionType;
 
        typedef Symbol::TuringStyleMixedSymbolPattern<T> SymbolPattern;
 
        typedef typename MConfigurationTuringMachineTransition_::Instruction ConstantInstruction;
 
        struct DynamicWrite {
            T symbol_key; 
            constexpr bool operator==(const DynamicWrite& other) const { return symbol_key == other.symbol_key; }
            constexpr bool operator!=(const DynamicWrite& other) const { return symbol_key != other.symbol_key; }
            constexpr bool operator<(const DynamicWrite& other) const { return symbol_key < other.symbol_key; }
        };
 
        typedef std::variant<ConstantInstruction, DynamicWrite> Instruction;
 
        static_assert(std::is_same_v<T, SymbolType>);
        static_assert(std::is_same_v<T, NodeStateType>);
        static_assert(std::is_same_v<StateType, std::shared_ptr<const State::MConfiguration::MConfiguration<T>>>);
        static_assert(std::is_same_v<ApplyHelperType, std::map<T, std::shared_ptr<const State::MConfiguration::MConfiguration<T>>>>);
        static_assert(std::is_same_v<StorageType, Memory::TapeLike<hasHalfTape, SymbolType>>);
 
        template <typename CharT = char, typename Traits = std::char_traits<CharT>>
        friend std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const DynamicWrite& i) {
            os << "dyn_write(" << i.symbol_key << ")";
            return os;
        }
 
        template <typename CharT = char, typename Traits = std::char_traits<CharT>>
        friend std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const Instruction& instruction) {
            using Utils::Visitor;
            std::visit(
                    Visitor{
                            [&os](const ConstantInstruction& i) { os << i; },
                            [&os](const DynamicWrite& i) { os << i; },
                    },
                    instruction);
            return os;
        }
 
        template <typename CharT = char, typename Traits = std::char_traits<CharT>>
        std::function<std::basic_ostream<CharT, Traits>&(std::basic_ostream<CharT, Traits>&)> debug() const {
            return [this](std::basic_ostream<CharT, Traits>& os) -> std::basic_ostream<CharT, Traits>& {
                using Utils::Debug::operator<<;
                os << "(" << preStatePattern.debug() << ", " << preSymbolPattern << ", " << symbolPlaceHolder << ") -> "
                   << "(" << Utils::Debug::debug(instructions) << ", " << postStatePattern.debug() << ")";
                return os;
            };
        }
 
        template <typename U, bool hT, typename CharT, typename Traits>
        friend std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>&, const TuringStyleMConfigurationTuringMachineTransition<U, hT>&);
 
 
        TuringStyleMConfigurationTuringMachineTransition() = delete;
 
        TuringStyleMConfigurationTuringMachineTransition(
                const std::shared_ptr<const State::MConfiguration::MConfiguration<NodeStateType>>& preStatePattern,
                const SymbolPattern& preSymbolPattern,
                const std::vector<Instruction>& instructions,
                const NodeStateType& symbolPlaceHolder,
                const std::shared_ptr<const State::MConfiguration::MConfiguration<NodeStateType>>& postStatePattern);
 
        TuringStyleMConfigurationTuringMachineTransition(const TuringStyleMConfigurationTuringMachineTransition&) = default;
 
        TuringStyleMConfigurationTuringMachineTransition(TuringStyleMConfigurationTuringMachineTransition&&) = default;
 
        TuringStyleMConfigurationTuringMachineTransition& operator=(const TuringStyleMConfigurationTuringMachineTransition&) = default;
 
        TuringStyleMConfigurationTuringMachineTransition& operator=(TuringStyleMConfigurationTuringMachineTransition&&) = default;
 
        virtual ~TuringStyleMConfigurationTuringMachineTransition() override = default;
 
        virtual std::optional<ApplyHelperType> matchFromCurrentCell(const StateType& state, const SymbolType& symbol) const override;
 
        virtual StateType apply(const StateType& state, StorageType& storage, ApplyHelperType&& helper, bool& running) const override;
 
        bool isAlphaEquivalent(const TuringStyleMConfigurationTuringMachineTransition& other) const;
 
        const StateType getPreStatePattern() const {
            return preStatePattern;
        }
 
        int compare(const TuringStyleMConfigurationTuringMachineTransition& other) const;
 
        bool operator<(const TuringStyleMConfigurationTuringMachineTransition& other) const {
            return compare(other) < 0;
        }
        bool operator==(const TuringStyleMConfigurationTuringMachineTransition& other) const {
            return compare(other) == 0;
        }
    private:
        static constexpr bool matchSymbolPattern(const SymbolPattern&, const SubstitutionType&, const SymbolType&);
        static constexpr ConstantInstruction generateConstantInstruction(const Instruction&, const SubstitutionType&);
        static constexpr std::vector<ConstantInstruction> generateConstantInstructions(const std::vector<Instruction>&, const SubstitutionType&);
 
        std::shared_ptr<const State::MConfiguration::MConfiguration<NodeStateType>> preStatePattern;
        SymbolPattern preSymbolPattern;
        std::vector<Instruction> instructions;
        std::shared_ptr<const State::MConfiguration::MConfiguration<NodeStateType>> postStatePattern;
        NodeStateType symbolPlaceHolder;
    };
 
    template <typename U, bool hT, typename CharT = char, typename Traits = std::char_traits<CharT>>
    std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const TuringStyleMConfigurationTuringMachineTransition<U, hT>& transition) {
        using Utils::Debug::operator<<;
        os
                << "(" << transition.preStatePattern << ", " << transition.preSymbolPattern << ", " << transition.symbolPlaceHolder << ") -> "
                << "(" << Utils::Debug::debug(transition.instructions) << ", " << transition.postStatePattern << ")";
        return os;
    }
 
    template<typename T, bool hT>
    constexpr bool TuringStyleMConfigurationTuringMachineTransition<T, hT>::matchSymbolPattern(
            const SymbolPattern& pattern,
            const SubstitutionType& substitution,
            const SymbolType& symbol) {
        bool matched = pattern.match(symbol, substitution);
        return matched;
    }
 
    template<typename T, bool hT>
    constexpr std::vector<typename TuringStyleMConfigurationTuringMachineTransition<T, hT>::ConstantInstruction>
    TuringStyleMConfigurationTuringMachineTransition<T, hT>::generateConstantInstructions(
            const std::vector<Instruction>& instructions,
            const SubstitutionType& substitution) {
        std::vector<ConstantInstruction> is;
        std::transform(
                instructions.begin(),
                instructions.end(),
                std::back_inserter(is),
                [&substitution](const Instruction& i) { return generateConstantInstruction(i, substitution); }
        );
        return is;
    }
 
    template<typename T, bool hT>
    constexpr typename TuringStyleMConfigurationTuringMachineTransition<T, hT>::ConstantInstruction
    TuringStyleMConfigurationTuringMachineTransition<T, hT>::generateConstantInstruction(
            const Instruction& instruction,
            const SubstitutionType& substitution) {
        using Utils::Visitor;
        ConstantInstruction i =
                std::visit(
                        Visitor{
                                [](const ConstantInstruction& i) { return i; },
                                [&substitution](const DynamicWrite& i) -> ConstantInstruction {
                                    typename SubstitutionType::const_iterator it = substitution.find(i.symbol_key);
                                    if(it == substitution.end()) {
                                        using Utils::Debug::operator<<;
                                        std::ostringstream ss;
                                        ss << "Unable to transform dynamic write into constant write" << std::endl;
                                        ss << "  Symbol key: " << Utils::Debug::debug(i.symbol_key) << std::endl;
                                        ss << "  Substitution: " << Utils::Debug::debug(substitution);
                                        throw std::runtime_error(ss.str());
                                    }
                                    std::shared_ptr<const State::MConfiguration::MConfiguration<T>> symbol = it->second;
                                    typename MConfigurationTuringMachineTransition_::WriteInstruction wi {symbol->getNode()};
                                    return wi;
                                },
                        },
                        instruction
                );
        return i;
    }
 
    template<typename T, bool hT>
    std::optional<typename TuringStyleMConfigurationTuringMachineTransition<T, hT>::ApplyHelperType>
    TuringStyleMConfigurationTuringMachineTransition<T, hT>::matchFromCurrentCell(const StateType& m_conf,
                                                                                  const SymbolType& symbol) const {
        SubstitutionType substitution;
        try {
            std::shared_ptr<const State::MConfiguration::MConfiguration<T>> symbolAsState = std::make_shared<const State::MConfiguration::MConfiguration<T>>(symbol);
            std::shared_ptr<const State::MConfiguration::MConfiguration<T>> preStatePatternWithoutPlaceholder =
                    State::MConfiguration::MConfiguration<T>::applySubstitution(preStatePattern, {{symbolPlaceHolder, symbolAsState}});
            substitution = preStatePatternWithoutPlaceholder->unifyWithMConf(m_conf);
        }
        catch(State::MConfiguration::NoUnificationException<T>) {
            return std::optional<ApplyHelperType>(std::nullopt);
        }
 
        if(matchSymbolPattern(preSymbolPattern, substitution, symbol)) {
            return std::optional<ApplyHelperType>(substitution);
        }
        return std::optional<ApplyHelperType>(std::nullopt);
    }
 
    template<typename T, bool hT>
    typename TuringStyleMConfigurationTuringMachineTransition<T, hT>::StateType
    TuringStyleMConfigurationTuringMachineTransition<T, hT>::apply(
            const StateType&,
            StorageType& tape,
            ApplyHelperType&& substitution,
            bool& running) const {
        SymbolType preSymbol = tape.read();
        typename ApplyHelperType::const_iterator it = substitution.find(symbolPlaceHolder);
        StateType preSymbolAsMConf = std::make_shared<const State::MConfiguration::MConfiguration<T>>(preSymbol);
        if (it == substitution.end()) {
            substitution.insert({symbolPlaceHolder, preSymbolAsMConf});
        }
        StateType postState = State::MConfiguration::MConfiguration<SymbolType>::applySubstitution(postStatePattern, substitution);
 
        std::vector<ConstantInstruction> constant_instructions = generateConstantInstructions(instructions, substitution);
        MConfigurationTuringMachineTransition_::run_instructions(tape, running, constant_instructions);
        return postState;
    }
 
    template<typename T, bool hT>
    TuringStyleMConfigurationTuringMachineTransition<T, hT>::TuringStyleMConfigurationTuringMachineTransition(
            const std::shared_ptr<const State::MConfiguration::MConfiguration<NodeStateType>>& preStatePattern,
            const SymbolPattern& preSymbolPattern,
            const std::vector<Instruction>& instructions,
            const NodeStateType& symbolPlaceHolder,
            const std::shared_ptr<const State::MConfiguration::MConfiguration<NodeStateType>>& postStatePattern
    ) :
            preStatePattern(preStatePattern), preSymbolPattern(preSymbolPattern), instructions(instructions),
            postStatePattern(postStatePattern), symbolPlaceHolder(symbolPlaceHolder) {
    }
 
    template<typename T, bool hT>
    bool TuringStyleMConfigurationTuringMachineTransition<T, hT>::isAlphaEquivalent(
            const TuringStyleMConfigurationTuringMachineTransition<T, hT>& other) const {
        typedef typename State::MConfiguration::MConfiguration<NodeStateType>::AlphaRewriting AlphaRewriting;
        typedef typename State::MConfiguration::MConfiguration<NodeStateType>::AlphaRelation AlphaRelation;
        using Utils::Visitor;
        std::optional<AlphaRelation> preStateRelation_o = preStatePattern->isAlphaEquivalent(other.preStatePattern);
        std::optional<AlphaRelation> postStateRelation_o = postStatePattern->isAlphaEquivalent(other.postStatePattern);
 
        if(!preStateRelation_o || !postStateRelation_o) {
            return false;
        }
 
        AlphaRelation preStateRelation = *preStateRelation_o;
        AlphaRelation postStateRelation = *postStateRelation_o;
 
        for(const std::pair<T, T>& binding : preStateRelation.first) {
            typename AlphaRewriting::iterator it = postStateRelation.first.find(binding.first);
            if(it != postStateRelation.first.end()) {
                if(it->second != binding.second) {
                    return false;
                }
            }
        }
 
        if(typename AlphaRewriting::iterator it = postStateRelation.first.find(symbolPlaceHolder);
                it != postStateRelation.first.end()) {
            if (it->second != other.symbolPlaceHolder) {
                return false;
            }
        }
 
        if(!preSymbolPattern.isAlphaEquivalent(preSymbolPattern, preStateRelation.first)) {
            return false;
        }
 
        if(instructions.size() != other.instructions.size()) {
            return false;
        }
 
        for(typename std::vector<Instruction>::const_iterator it = instructions.begin(),
                    it2 = other.instructions.begin(); it != instructions.end(); ++it, ++it2) {
            Instruction instruction = *it;
            Instruction otherInstruction = *it2;
 
            if(instruction.index() != otherInstruction.index()) {
                return false;
            }
            else if(std::holds_alternative<DynamicWrite>(instruction)) {
                DynamicWrite dynamicWrite = std::get<DynamicWrite>(instruction);
                DynamicWrite otherDynamicWrite = std::get<DynamicWrite>(otherInstruction);
                if(preStateRelation.first[dynamicWrite.symbol_key] != otherDynamicWrite.symbol_key) {
                    return false;
                }
            }
            else if(instruction != otherInstruction) {
                return false;
            }
        }
 
        return true;
    }
 
    template<typename T, bool hT>
    int TuringStyleMConfigurationTuringMachineTransition<T, hT>::compare(const TuringStyleMConfigurationTuringMachineTransition<T, hT>& other) const {
        int cmp;
        cmp = preStatePattern->compare(*other.preStatePattern);
        if(cmp != 0) {
            return cmp;
        }
        cmp = Utils::compare(preSymbolPattern, other.preSymbolPattern);
        if(cmp != 0) {
            return cmp;
        }
        cmp = Utils::compare(instructions, other.instructions);
        if(cmp != 0) {
            return cmp;
        }
        cmp = postStatePattern->compare(*other.postStatePattern);
        if(cmp != 0) {
            return cmp;
        }
        cmp = Utils::compare(symbolPlaceHolder, other.symbolPlaceHolder);
        return cmp;
    }
}