FiniteAutomaton.hh

Go to the documentation of this file.

#ifndef __DIADES__AUTOMATA__EXPERIMENTAL__FINITEAUTOMATON__HH__
#define __DIADES__AUTOMATA__EXPERIMENTAL__FINITEAUTOMATON__HH__

#include<unordered_set>
#include<diades/utils/Verbose.hh>
#include<diades/automata/experimental/StateMachine.hh>
#include<diades/automata/experimental/StateCreation.hh>

namespace Diades
{
   namespace Automata
   {
      namespace Experimental
      {
         using Diades::Utils::Msg;

         template<typename _StatePropertyId,
         typename _InputSymbolId,
         typename _NullStatePropertyId = NullValue<_StatePropertyId>,
         typename _NullInputSymbolId = NullValue< _InputSymbolId>>
         class FiniteAutomaton : public StateMachine<_StatePropertyId, _InputSymbolId, _NullStatePropertyId, _NullInputSymbolId>
         {
         public:
            using SM = StateMachine<_StatePropertyId, _InputSymbolId, _NullStatePropertyId>;
            using InputSymbolId = _InputSymbolId;
            using StatePropertyId = _StatePropertyId;
            using NullStatePropertyId = _NullStatePropertyId;
            using NullInputSymbolId = _NullInputSymbolId;
            using State = typename SM::State;
            using Transition = typename SM::Transition;
            using AcceptingStates = std::unordered_set<State>;
            using ConstAcceptingStateIterator = typename AcceptingStates::const_iterator;
            using AcceptingStateIterator = typename AcceptingStates::iterator;

            using InputSymbolIdIterator = typename SM::EventPropertyIdIterator;

         private:
            AcceptingStates _accepting;

         public:

            FiniteAutomaton() : SM(), _accepting()
            {
            }

            FiniteAutomaton(const FiniteAutomaton & automaton) : SM(automaton)
            {
               // each copied state has the id of the state in the given automaton
               std::for_each(automaton.acceptingStateBegin(),
                             automaton.acceptingStateEnd(),
                             [&](State s)
                             {
                                setAcceptingState(SM::behaviour().getNode(s.id()));
                             });
            }

            FiniteAutomaton & operator=(const FiniteAutomaton & automaton)
            {
               if(this != &automaton)
               {
                  clear();
                  SM::operator=(automaton);
                  // each copied state has the id of the state in the given automaton
                  std::for_each(automaton.acceptingStateBegin(),
                                automaton.acceptingStateEnd(),
                                [&](State s)
                                {
                                   setAcceptingState(SM::behaviour().getNode(s.id()));
                                });
               }
               return *this;
            }

            InputSymbolIdIterator
            inputSymbolIdBegin() const
            {
               return SM::eventBegin();
            }

            InputSymbolIdIterator
            inputSymbolIdEnd() const
            {
               return SM::eventEnd();
            }

            const vector<InputSymbolId> &
            inputSymbolIds() const
            {
               return SM::events();
            }

            State
            initialState() const
            {
               if(SM::initialStateBegin() == SM::initialStateEnd())
               {
                  return State();
               }
               if(SM::numberOfInitialStates() > 1)
               {
                  return State();
               }
               return *SM::initialStateBegin();
            }

            virtual
            bool
            isValid() const
            {
               return SM::isValid() && initialState().valid();
            }

            decltype(auto)
            numberOfInputSymbolIds() const
            {
               return SM::numberOfEvents();
            }

            ConstAcceptingStateIterator
            acceptingStateBegin() const
            {
               return _accepting.begin();
            }

            ConstAcceptingStateIterator
            acceptingStateEnd() const
            {
               return _accepting.end();
            }

            const AcceptingStates &
            acceptingStates() const
            {
               return _accepting;
            }

           void swapAcceptingState(State state)
           {
             if(isAcceptingState(state))
               {
                 unsetAcceptingState(state);
               }
                 else
               {
                 setAcceptingState(state);
               }
           }

           virtual
           void
           clear()
           {
             clearAllAcceptingStates();
             SM::clear();
           }

           virtual void
               deleteState(State state)
             {
               unsetAcceptingState(state);
               SM::deleteState(state);
             }
           
           std::pair<AcceptingStateIterator, bool>
           setAcceptingState(State state)
           {
             return _accepting.insert(state);
           }

           AcceptingStateIterator
           unsetAcceptingState(State state)
           {
             auto it = _accepting.find(state);
             if(it != _accepting.end())
               {
                 return _accepting.erase(_accepting.find(state));
               }
             return it;
           }

           void
           clearAllAcceptingStates()
           {
             _accepting.clear();
           }

           decltype(auto)
           numberOfAcceptingStates() const
           {
             return _accepting.size();
           }

           void
           insertInputSymbolId(InputSymbolId symbol)
           {
             SM::insertEventPropertyId(symbol);
           }

           bool
           isAcceptingState(State s) const
           {
             return _accepting.find(s) != _accepting.end();
           }

         };

         template<typename FA, typename BS>
         struct
         MakeAcceptingState
         {
            using State = typename FA::State;

            MakeAcceptingState(const FA & source, FA & target, const BS & bs, State s)
            {
               auto it = std::find_if(bs.begin(), bs.end(),
                                      [&](State s) -> bool
                                      {
                                         return source.isAcceptingState(s);
                                      });
               if(it != bs.end())
               {
                  target.setAcceptingState(s);
               }
            };
         };

         template<typename S, typename I, typename NS, typename NI>
         class OnlySourceStateCreator<FiniteAutomaton<S, I, NS, NI>> :
         public StateCreation<FiniteAutomaton<S, I, NS, NI>>,
         public BeliefStateWithSourceStateCreator<FiniteAutomaton<S, I, NS, NI>>
         {
            public:
            using FA = FiniteAutomaton<S, I, NS, NI>;
            using SC = StateCreation<FA>;
            using BSSSC = BeliefStateWithSourceStateCreator<FA>;
            using State = typename SC::State;
            using FsmBs = typename BSSSC::FsmBs;
            public:

            OnlySourceStateCreator(const FA & source, FA & target) :
                    SC(source, target), BSSSC()
            {
            }

            virtual std::pair<State, bool>
                    newState(State source, const FsmBs & bs)
            {
               // why using StateCreation<StateMachine>::_target instead of _target? Does not compile
               // see https://gcc.gnu.org/onlinedocs/gcc/Name-lookup.html for explanation

               // here we do not take into account the belief state of source
               auto result = SC::_target.newState(SC::_source.getStatePropertyId(source));
               MakeAcceptingState<FA, FsmBs>(SC::_source, SC::_target, bs, std::get<0>(result));
               return result;
            }
         };

         template<typename S, typename I, typename NS, typename NI, typename StatePropertyCombination>
         class ManagedBeliefStateWithSourceStateCreator<FiniteAutomaton<S, I, NS, NI>, StatePropertyCombination> :
         public ManagedStateCreation< FiniteAutomaton<S, I, NS, NI>, typename StatePropertyCombination::StateProperty>,
         public BeliefStateWithSourceStateCreator<FiniteAutomaton<S, I, NS, NI>>
         {
            public:


            using FA = FiniteAutomaton<S, I, NS, NI>;
            using BSSSC = BeliefStateWithSourceStateCreator<FA>;
            using MSC = ManagedStateCreation< FA, typename StatePropertyCombination::StateProperty>;
            using State = typename MSC::State;
            using FsmBs = typename BSSSC::FsmBs;
            using StatePropertyId = typename MSC::StatePropertyId;
            using StateProperty = typename MSC::StateProperty;

            ManagedBeliefStateWithSourceStateCreator(const FA & source, FA & target,
                                                     const StatePropertyManager<StateProperty, StatePropertyId> & sourceStateManager,
                                                     StatePropertyManager<StateProperty, StatePropertyId> & targetStateManager) :
                    MSC(source, target, sourceStateManager, targetStateManager), BSSSC()
            {
            }

            virtual std::pair<State, bool>
                    newState(State source, const FsmBs & bs)
            {

               // get the iterator of the StatePropertyId associated with the state *bs.begin() in _source
               auto begin = MSC::sourceStateManager().infoIdRangeInfoIterator(MSC::_source.statePropertyIdRangeIterator(bs.begin()));
               // get the iterator of the StatePropertyId associated with the-after-the-last-state bs.end() in _source
               auto end = MSC::sourceStateManager().infoIdRangeInfoIterator(MSC::_source.statePropertyIdRangeIterator(bs.end()));
               // creation of the new StateProperty compatible with the projection as specified in StatePropertyProjection
               auto statePropertyId = MSC::targetStateManager().statePropertyId(
                                                                                StatePropertyCombination()(MSC::sourceStateManager().getStateProperty(MSC::_source.getStatePropertyId(source)),
                                                                                                           begin, end));
               // create the state in target with the statePropertyId created in the _projectionStateManager
               auto result = MSC::_target.newState(statePropertyId);
               MakeAcceptingState<FA, FsmBs>(MSC::_source, MSC::_target, bs, std::get<0>(result));
               return result;
            }

         };

         template<typename S, typename I, typename NS, typename NI>
         class OnlyStateCreator< FiniteAutomaton<S, I, NS, NI> > : public StateCreation<FiniteAutomaton<S, I, NS, NI>>,
         public BeliefStateBasedStateCreator<FiniteAutomaton<S, I, NS, NI>>
         {
            public:
            using FA = FiniteAutomaton<S, I, NS, NI>;
            using SC = StateCreation<FA>;
            using BSBSC = BeliefStateBasedStateCreator<FA>;
            using State = typename SC::State;
            using FsmBs = typename BSBSC::FsmBs;
            public:

            OnlyStateCreator(const FA & source, FA & target) :
                    SC(source, target), BSBSC()
            {
            }

            virtual std::pair<State, bool>
                    newState(const FsmBs & bs)
            {
               // why using StateCreation<StateMachine>::_target instead of _target? Does not compile
               // see https://gcc.gnu.org/onlinedocs/gcc/Name-lookup.html for explanation

               // here we do not take into account the belief state of source
               auto result = std::make_pair(SC::_target.newState(), true);
               MakeAcceptingState<FA, FsmBs>(SC::_source, SC::_target, bs, std::get<0>(result));
               return result;
            }


          

           
         };

         template<typename S, typename I, typename NS, typename NI, typename StatePropertyCombination>
         class ManagedBeliefStateBasedStateCreator <FiniteAutomaton<S, I, NS, NI>, StatePropertyCombination> :
         public ManagedStateCreation<FiniteAutomaton<S, I, NS, NI>, typename StatePropertyCombination::Property>,
         public BeliefStateBasedStateCreator<FiniteAutomaton<S, I, NS, NI>>
         {
            public:
            using FA = FiniteAutomaton<S, I, NS, NI>;
            using MSC = ManagedStateCreation<FA, typename StatePropertyCombination::Property>;
            using BSBSC = BeliefStateBasedStateCreator<FA>;
            using State = typename MSC::State;
            using FsmBs = typename BSBSC::FsmBs;
            using StatePropertyId = typename MSC::StatePropertyId;
            using StateProperty = typename MSC::StateProperty;

            public:

            ManagedBeliefStateBasedStateCreator(const FA & source, FA & target,
                                                const StatePropertyManager<StateProperty, StatePropertyId> & sourceStateManager,
                                                StatePropertyManager<StateProperty, StatePropertyId> & targetStateManager) :
                    MSC(source, target, sourceStateManager, targetStateManager), BSBSC()
            {
            }

            virtual std::pair<State, bool>
                    newState(const FsmBs & bs)
            {
               // get the iterator of the StatePropertyId associated with the state *bs.begin() in _source
               auto begin = MSC::sourceStateManager().infoIdRangeInfoIterator(MSC::_source.statePropertyIdRangeIterator(bs.begin()));
               // get the iterator of the StatePropertyId associated with the-after-the-last-state bs.end() in _source
               auto end = MSC::sourceStateManager().infoIdRangeInfoIterator(MSC::_source.statePropertyIdRangeIterator(bs.end()));
               // creation of the new StateProperty compatible with the projection as specified in StatePropertyProjection
               auto statePropertyId = MSC::targetStateManager().statePropertyId(
                                                                                StatePropertyCombination()(begin, end));
               // create the state in target with the statePropertyId created in the _projectionStateManager
               auto result = MSC::_target.newState(statePropertyId);
               MakeAcceptingState<FA, FsmBs>(MSC::_source, MSC::_target, bs, std::get<0>(result));
               return result;
            }



         };

         template <typename S, typename I, typename NS, typename NI,
         typename _StateProperty, typename StatePropertyCombination>
         class ManagedSynchronisedAcceptingStateCreation :
         public ManagedSynchronisedStateCreation<FiniteAutomaton<S, I, NS, NI>, _StateProperty, StatePropertyCombination>
         {
         public:
            using MSSC = ManagedSynchronisedStateCreation<FiniteAutomaton<S, I, NS, NI>, _StateProperty, StatePropertyCombination>;

         public:

            ManagedSynchronisedAcceptingStateCreation(const std::vector<typename Ptr<typename MSSC::StateMachine>::ConstP> & machines,
                                                      const std::vector<typename Ptr<typename MSSC::SManager>::ConstP> & managers,
                                                      typename MSSC::SManager & syncManager)
            : MSSC(machines, managers, syncManager)
            {
            }


         private:

            void
            setAcceptingState(const std::vector<typename MSSC::State> & states,
                              typename MSSC::State newState)
            {
               bool isNotAcceptor = false;
               size_t index = 0;
               while(!isNotAcceptor && (index != states.size()))
               {
                  isNotAcceptor = !MSSC::_machines->at(index)->isAcceptingState(states[index]);
                  ++index;
               }
               if(!isNotAcceptor)
               {
                  MSSC::_target->setAcceptingState(newState);
               }
            }

         public:

            virtual std::pair<typename MSSC::State, bool>
            newState(const std::vector<typename MSSC::State> & states)
            {

               auto result = MSSC::newState(states);
               if(std::get<1>(result))
               {
                  setAcceptingState(states, std::get<0>(result));
               }
               return result;
            }
         };



         template <typename S, typename I, typename NS, typename NI>
         class StateCopy<FiniteAutomaton<S, I, NS, NI>> : public StateCreation<FiniteAutomaton<S, I, NS, NI>>
         {
            public:
            using FA = FiniteAutomaton<S, I, NS, NI>;
            using SC = StateCreation<FiniteAutomaton<S, I, NS, NI>>;

            public:

            StateCopy(const FA & source, FA & target) :
                    SC(source, target)
            {
            }

            virtual std::pair<typename SC::State, bool>
                    newState(typename SC::State source)
            {


               auto result = SC::target().newState(SC::source().getStatePropertyId(source));
               if(SC::source().isInitial(source))
               {
                  SC::target().setInitial(result.first);
               }
               if(SC::source().isAcceptingState(source))
               {
                  SC::target().setAcceptingState(result.first);
               }
               return result;
            }

            virtual std::pair<typename SC::State, bool>
                    newState(typename SC::State source, const typename SC::StatePropertyId & statePropertyId)
            {
               auto result = SC::target().newState(statePropertyId);
               if(SC::source().isInitial(source))
               {
                  SC::target().setInitial(result.first);
               }
               if(SC::source().isAcceptingState(source))
               {
                  SC::target().setAcceptingState(result.first);
               }
               return result;
            }
         };

         template<typename S, typename I, typename NS, typename NI, typename StateProperty>
         class ManagedStateCopy<FiniteAutomaton<S, I, NS, NI>, StateProperty> :
         public ManagedStateCreation<FiniteAutomaton<S, I, NS, NI>, StateProperty>
         {
         public:
            using MSC = ManagedStateCreation<FiniteAutomaton<S, I, NS, NI>, StateProperty>;
            using Fsm = typename MSC::Fsm;
            using StManager = typename MSC::StManager;
            using State = typename MSC::State;
            using StatePropertyId = typename MSC::StatePropertyId;

            ManagedStateCopy(const Fsm & source,
                             Fsm & target,
                             const StManager & sourceStateManager,
                             StManager & targetStateManager) :
            MSC(source, target, sourceStateManager, targetStateManager)
            {
            }

            virtual std::pair<State, bool>
            newState(State source)
            {
               auto propId = MSC::source().getStatePropertyId(source);
               std::pair<State, bool> result;
               if(propId != MSC::source().nullStatePropertyId)
               {
                  if(MSC::sourceStateManager().hasStatePropertyId(propId))
                  {
                     result = MSC::target().newState(MSC::targetStateManager().statePropertyId(MSC::sourceStateManager().getStateProperty(propId)));
                  }
                  else
                  {
                     result = MSC::target().newState(propId);
                  }
               }
               else
               {
                  result = MSC::target().newState(MSC::source().nullStatePropertyId);
               }
               if(MSC::source().isInitial(source))
               {
                  MSC::target().setInitial(result.first);
               }
               if(MSC::source().isAcceptingState(source))
               {
                  MSC::target().setAcceptingState(result.first);
               }
               return result;
            }

            virtual std::pair<State, bool>
            newState(State source, const StatePropertyId & statePropertyId)
            {
               auto result = MSC::target().newState(statePropertyId);
               if(result.second)
               {
                  auto propId = MSC::source().getStatePropertyId(source);
                  if(propId != MSC::source().nullStatePropertyId)
                  {
                     if(MSC::sourceStateManager().hasStatePropertyId(propId))
                     {
                        MSC::targetStateManager().setStateProperty(MSC::sourceStateManager().getStateProperty(propId),
                                                                   statePropertyId);
                     }
                  }
               }

               if(MSC::source().isInitial(source))
               {
                  MSC::target().setInitial(result.first);
               }
               if(MSC::source().isAcceptingState(source))
               {
                  MSC::target().setAcceptingState(result.first);
               }
               return result;
            }
         };



      };
   };
};


#endif /* __DIADES__AUTOMATA__EXPERIMENTAL__FINITEAUTOMATON__HH__ */