Project.hh

Go to the documentation of this file.

#ifndef __DIADES__AUTOMATA__EXPERIMENTAL__PROJECT__HH
#define __DIADES__AUTOMATA__EXPERIMENTAL__PROJECT__HH

#include<unordered_map>
#include<unordered_set>
#include<diades/utils/Verbose.hh>
#include<diades/graph/ConstNodeMap.hh>
#include<diades/automata/experimental/StateMachine.hh>
#include<diades/automata/experimental/BeliefState.hh>
#include<diades/automata/experimental/StatePropertyManager.hh>
#include<diades/automata/experimental/StateCreation.hh>

namespace Diades {
  namespace Automata {
    namespace Experimental {
      namespace Projection {
        
        template<typename Fsm>
        void
        aggregateElementaryBeliefStates(const Fsm & machine,
                                        CstBsMap<Fsm> & bsFromState)
        {
          bool fixpoint = false;
          while (!fixpoint) {
            fixpoint = true;
            std::for_each(machine.stateBegin(), machine.stateEnd(),
                          [&](typename Fsm::State state) {
                            auto previousSize = bsFromState[state]->size();
                            std::vector<typename Fsm::State> states;
                            states.reserve(bsFromState[state]->size());
                            std::copy(bsFromState[state]->begin(),
                                      bsFromState[state]->end(),
                                      std::back_inserter(states)); // can we do it better ?? without copy ?
                            std::for_each(states.begin(), states.end(),
                                          [&](typename Fsm::State visited) {
                                            if (visited != state) {
                                              bsFromState[state]->insertStates(bsFromState[visited]->begin(),
                                                                               bsFromState[visited]->end());
                                            }
                                          });
                            fixpoint &= previousSize == bsFromState[state]->size();
                          });
          }
        }

        
                

        template<typename Fsm, typename IsGoal>
        void
        computeElementaryBeliefStates(const Fsm & machine,
                                      IsGoal isGoal,
                                      CstBsMap<Fsm> & bsFromState) {
          using FsmBs = BeliefState<Fsm>;
          std::for_each(machine.stateBegin(), machine.stateEnd(),
                        [&](typename Fsm::State state) {
                          bsFromState[state] = std::make_shared<FsmBs>(machine);
                          bsFromState[state]->insertState(state);
                        });
          std::for_each(machine.transitionBegin(), machine.transitionEnd(),
                        [&](typename Fsm::Transition transition)
                        {
                          if(isGoal(transition))
                            {
                              bsFromState[transition.source()]->insertState(transition.target());
                            }
                        });
        }



        template<typename Fsm, typename IsGoal>
        void
        makeBeliefStates(const Fsm & machine,
                         IsGoal isGoal,
                         CstBsMap<Fsm> & bsFromState) {
          computeElementaryBeliefStates(machine, isGoal, bsFromState);
          aggregateElementaryBeliefStates(machine,bsFromState);
        }

        

        template<typename Fsm, typename EventPropertyIdIterator>
        void
        computeElementaryBeliefStates(const Fsm & machine,
                                      EventPropertyIdIterator begin,
                                      EventPropertyIdIterator end,
                                      CstBsMap<Fsm> & bsFromState) {
          using FsmBs = BeliefState<Fsm>;
          std::for_each(machine.stateBegin(), machine.stateEnd(),
                        [&](typename Fsm::State state) {
                          bsFromState[state] = std::make_shared<FsmBs>(machine);
                          bsFromState[state]->insertState(state);
                        });
          std::for_each(begin, end,
                        [&](typename Fsm::EventPropertyId evt) {
                          std::for_each(machine.eventTransitionBegin(evt), machine.eventTransitionEnd(evt),
                                        [&](typename Fsm::Transition t) {
                                          bsFromState[t.source()]->insertState(t.target());
                                        });
                        });
        }



        
        template<typename Fsm, typename EventPropertyIdIterator>
        void
        makeBeliefStates(const Fsm & machine,
                         EventPropertyIdIterator begin,
                         EventPropertyIdIterator end,
                         CstBsMap<Fsm> & bsFromState) {
          computeElementaryBeliefStates(machine, begin, end, bsFromState);
          aggregateElementaryBeliefStates(machine, bsFromState);
        }



        template<typename Fsm, typename EventPropertyIdIterator>
        bool
        projectRange(const Fsm & machine,
                     Fsm & abstractMachine,
                     EventPropertyIdIterator projectedBegin,
                     EventPropertyIdIterator projectedEnd,
                     EventPropertyIdIterator abstractedBegin,
                     EventPropertyIdIterator abstractedEnd,
                     BeliefStateWithSourceStateCreator<Fsm> &stateCreation,
                     BsMap<Fsm> & bsMap,
                     CstStMap<typename Fsm::State> & stMap) {
          bool result = (machine.initialStateBegin() != machine.initialStateEnd())
            && (machine != abstractMachine);
          if (result) {
            CstBsMap<Fsm> localBsMap(machine.behaviour());
            makeBeliefStates(machine, abstractedBegin, abstractedEnd, localBsMap);
            abstractMachine.clear();
            std::vector<typename Fsm::State> toVisit;
            toVisit.reserve(machine.numberOfStates());

            // the projected machine has the same number of initial states
            std::for_each(machine.initialStateBegin(), machine.initialStateEnd(),
                          [&](typename Fsm::State state) {
                            typename Fsm::State newState;
                            // For each state  i we associate the projected state  i -> i1 i2 .. that 
                            // in the belief state
                            std::tie(newState, result) = stateCreation.newState(state, *localBsMap[state]);
                            if (result) {
                              abstractMachine.setInitial(newState);
                              stMap[state] = newState;
                              bsMap[newState] = localBsMap[state];
                              toVisit.push_back(state);
                            }
                          });
            std::for_each(projectedBegin, projectedEnd,
                          [&](typename Fsm::EventPropertyId event) {
                            abstractMachine.copyEventPropertyId(machine, event);
                          });

            while (result && !toVisit.empty()) {
              // current visited state
              auto currentState = toVisit.back();
              toVisit.pop_back();
              // for any event that is projected
              std::for_each(projectedBegin, projectedEnd,
                            [&](typename Fsm::EventPropertyId evt) {
                              // we compute the set of states that can be reached from the belief state
                              // of the visited state by the trigger of the event evt
                              auto nextBs = localBsMap[currentState]->nextBeliefState(evt);

                              // each state of nextBs is a potential target 
                              // for the tigger of evt, so each target must have
                              // its corresponding beliefstates mapped into abstractMachine
                              std::for_each(nextBs->begin(), nextBs->end(),
                                            [&](typename Fsm::State target) {
                                              if (!stMap[target].valid()) {
                                                // the corresponding beliefstate of target is not yet
                                                // in abstractmachine, we put it
                                                typename Fsm::State newTarget;
                                                std::tie(newTarget, result) = stateCreation.newState(target, *localBsMap[target]);
                                                if (result) {
                                                  stMap[target] = newTarget;
                                                  toVisit.push_back(target);
                                                }
                                              }
                                              abstractMachine.newTransition(stMap[currentState], stMap[target], evt);
                                            });
                            });
            }
          }
          return result;
        }

        template<typename Fsm, typename IsGoal>
        bool
        projectRange(const Fsm & machine,
                     Fsm & abstractMachine,
                     IsGoal isGoal,
                     BeliefStateWithSourceStateCreator<Fsm> &stateCreation,
                     BsMap<Fsm> & bsMap,
                     CstStMap<typename Fsm::State> & stMap) {
          bool result = (machine.initialStateBegin() != machine.initialStateEnd())
            && (machine != abstractMachine);
          if (result) {
            using FsmBs = BeliefState<Fsm>;
            using Transition = typename Fsm::Transition;
            using State = typename Fsm::State;
            CstBsMap<Fsm> localBsMap(machine.behaviour());
            makeBeliefStates(machine,[&](Transition t){ return !isGoal(t); }, localBsMap);
            //abstractMachine.clear();
            std::vector<typename Fsm::State> toVisit;
            toVisit.reserve(machine.numberOfStates());

            // the projected machine has the same number of initial states
            std::for_each(machine.initialStateBegin(), machine.initialStateEnd(),
                          [&](typename Fsm::State state) {
                            typename Fsm::State newState;
                            // For each state  i we associate the projected state  i -> i1 i2 .. that 
                            // in the belief state
                            std::tie(newState, result) = stateCreation.newState(state, *localBsMap[state]);
                            if (result) {
                              abstractMachine.setInitial(newState);
                              stMap[state] = newState;
                              bsMap[newState] = localBsMap[state];
                              toVisit.push_back(state);
                            }
                          });
           
            while (result && !toVisit.empty()) {
              // current visited state
              auto currentState = toVisit.back();
              toVisit.pop_back();
              // we compute the set of states that can be reached from the belief state 
              // of the visited state by a goal transition from the current belief state
              auto nextBs = std::make_shared<FsmBs>(machine);
              std::for_each(localBsMap[currentState]->begin(),
                            localBsMap[currentState]->end(),
                            [&](State s)
                                      {
                                        for(auto it = machine.outputTransitionBegin(s);
                                            it != machine.outputTransitionEnd(s);
                                            ++it)
                                          {
                                            if(isGoal(*it))
                                              {
                                                nextBs->insertState(it->target());
                                                if (!stMap[it->target()].valid()) {
                                                  // the corresponding beliefstate of target is not yet
                                                  // in abstractmachine, we put it
                                                  State newTarget;
                                                  std::tie(newTarget, result) = stateCreation.newState(it->target(),
                                                                                                       *localBsMap[it->target()]);
                                                  if (result)
                                                    {
                                                      stMap[it->target()] = newTarget;
                                                      bsMap[newTarget] = localBsMap[it->target()];
                                                      toVisit.push_back(it->target());
                                                    }
                                                }
                                                abstractMachine.newTransition(stMap[currentState],
                                                                              stMap[it->target()],
                                                                              machine.getEvent(*it));
                                              }
                                          }
                                      });
            }
          }
          return result;
        }

      };

      template<typename Fsm, typename IsGoal>
      bool
      project(const Fsm & machine,
              Fsm & abstractMachine,
              IsGoal isGoal,
              BsMap<Fsm> & bsMap,
              CstStMap<typename Fsm::State> & stMap)
      {
        OnlySourceStateCreator<Fsm> creator(machine, abstractMachine);
        bsMap.init(abstractMachine.behaviour());
        stMap.init(machine.behaviour());
        return Projection::projectRange(machine, abstractMachine,
                                        [&](typename Fsm::Transition transition)
                                        { return isGoal(transition); }, creator,
                                        bsMap,stMap);
      }



      template<typename Fsm, typename IsGoal>
      bool
      project(const Fsm & machine,
              Fsm & abstractMachine,
              IsGoal isGoal) {
        BsMap<Fsm> bsMap;
        CstStMap<typename Fsm::State> stMap;
        return project(machine,abstractMachine,isGoal,bsMap,stMap);
      }
      
      
    

      template<typename Fsm, typename EventPropertyIdIterator>
      bool
      project(const Fsm & machine,
              Fsm & abstractMachine,
              EventPropertyIdIterator begin,
              EventPropertyIdIterator end,
              BsMap<Fsm> & bsMap,
              CstStMap<typename Fsm::State> & stMap) {
        std::vector<typename Fsm::EventPropertyId> abstractedEvents;
        abstractedEvents.reserve(machine.numberOfEvents());
        std::copy_if(machine.eventBegin(), machine.eventEnd(), std::back_inserter(abstractedEvents),
                     [&](typename Fsm::EventPropertyId evt) {
                       return std::find(begin, end, evt) == end;
                     });

        OnlySourceStateCreator<Fsm> creator(machine, abstractMachine);
        bsMap.init(abstractMachine.behaviour());
        stMap.init(machine.behaviour());
        return Projection::projectRange(machine, abstractMachine,
                                        begin, end,
                                        abstractedEvents.begin(), abstractedEvents.end(), creator,
                                        bsMap,stMap);
      }



      template<typename Fsm, typename EventPropertyIdIterator>
      bool
      project(const Fsm & machine,
              Fsm & abstractMachine,
              EventPropertyIdIterator begin,
              EventPropertyIdIterator end) {
        BsMap<Fsm> bsMap;
        CstStMap<typename Fsm::State> stMap;
        return project(machine,abstractMachine,begin,end,bsMap,stMap);
      }


      template<typename Fsm,
               typename IsGoal,
               typename StateProperty,
               typename StateLabelProjection>
      bool
      project(const Fsm & fsm,
              Fsm & projectedFsm,
              const StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & stateManager,
              StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & projectionStateManager,
              const StateLabelProjection & projection,
              IsGoal isGoal,
              BsMap<Fsm> & bsMap,
              CstStMap<typename Fsm::State> & stMap) {
        ManagedBeliefStateWithSourceStateCreator<Fsm, StateLabelProjection> creator(fsm, projectedFsm, stateManager, projectionStateManager);
        bsMap.init(projectedFsm.behaviour());
        stMap.init(fsm.behaviour());
        return Projection::projectRange(fsm, projectedFsm,
                                        isGoal, creator,
                                        bsMap,stMap);
      }

      template<typename Fsm,
               typename IsGoal,
               typename StateProperty,
               typename StateLabelProjection>
      bool
      project(const Fsm & fsm,
              Fsm & projectedFsm,
              const StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & stateManager,
              StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & projectionStateManager,
              const StateLabelProjection & projection,
              IsGoal isGoal) {
        BsMap<Fsm> bsMap;
        CstStMap<typename Fsm::State> stMap;
        return project(fsm,projectedFsm,stateManager,projectionStateManager,projection,isGoal,bsMap,stMap);
      }


     

      
      
      template<typename Fsm,
               typename EventPropertyIdIterator,
               typename StateProperty,
               typename StateLabelProjection>
      bool
      project(const Fsm & fsm,
              Fsm & projectedFsm,
              const StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & stateManager,
              StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & projectionStateManager,
              const StateLabelProjection & projection,
              EventPropertyIdIterator begin,
              EventPropertyIdIterator end,
              BsMap<Fsm> & bsMap,
              CstStMap<typename Fsm::State> & stMap) {
        std::vector<typename Fsm::EventPropertyId> abstractedEvents;
        abstractedEvents.reserve(fsm.numberOfEvents());
        std::copy_if(fsm.eventBegin(), fsm.eventEnd(), std::back_inserter(abstractedEvents),
                     [&](typename Fsm::EventPropertyId evt) {
                       return std::find(begin, end, evt) == end;
                     });
        ManagedBeliefStateWithSourceStateCreator<Fsm, StateLabelProjection> creator(fsm, projectedFsm, stateManager, projectionStateManager);
        bsMap.init(projectedFsm.behaviour());
        stMap.init(fsm.behaviour());
        return Projection::projectRange(fsm, projectedFsm,
                                        begin, end,
                                        abstractedEvents.begin(), abstractedEvents.end(), creator,
                                        bsMap, stMap);
      }
      template<typename Fsm,
               typename EventPropertyIdIterator,
               typename StateProperty,
               typename StateLabelProjection>
      bool
      project(const Fsm & fsm,
              Fsm & projectedFsm,
              const StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & stateManager,
              StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & projectionStateManager,
              const StateLabelProjection & projection,
              EventPropertyIdIterator begin,
              EventPropertyIdIterator end) {
        BsMap<Fsm> bsMap;
        CstStMap<typename Fsm::State> stMap;
        return project(fsm,projectedFsm,stateManager,projectionStateManager,projection,begin,end,bsMap,stMap);
      }

      template<typename Fsm, typename EventPropertyIdIterator>
      bool
      abstractEvents(const Fsm & machine,
                     Fsm & abstractMachine,
                     EventPropertyIdIterator begin,
                     EventPropertyIdIterator end,
                     BsMap<Fsm> & bsMap,
                     CstStMap<typename Fsm::State> & stMap) {
        std::vector<typename Fsm::EventPropertyId> projectedEvents;
        projectedEvents.reserve(machine.numberOfEvents());
        std::copy_if(machine.eventBegin(), machine.eventEnd(), std::back_inserter(projectedEvents),
                     [&](typename Fsm::EventPropertyId evt) {
                       return std::find(begin, end, evt) == end;
                     });
        bsMap.init(abstractMachine.behaviour());
        stMap.init(machine.behaviour());
        return Projection::projectRange(machine, abstractMachine,
                                        projectedEvents.begin(), projectedEvents.end(),
                                        begin, end,
                                        bsMap,stMap);
      }


      template<typename Fsm, typename EventPropertyIdIterator>
      bool
      abstractEvents(const Fsm & machine,
                     Fsm & abstractMachine,
                     EventPropertyIdIterator begin,
                     EventPropertyIdIterator end) {
        BsMap<Fsm> bsMap;
        CstStMap<typename Fsm::State> stMap;
        return abstractEvents(machine, abstractMachine, begin, end, bsMap, stMap);
      }

  
      template<typename Fsm,  typename EventPropertyIdIterator, typename StateProperty,
               typename StateLabelProjection>
      bool
      abstractEvents(const Fsm & fsm,
                     Fsm & projectedFsm,
                     const StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & stateManager,
                     StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & projectionStateManager,
                     const StateLabelProjection & projection,
                     EventPropertyIdIterator begin,
                     EventPropertyIdIterator end,
                     BsMap<Fsm> & bsMap,
                     CstStMap<typename Fsm::State> & stMap) {
        std::vector<typename Fsm::EventPropertyId> projectedEvents;
        projectedEvents.reserve(fsm.numberOfEvents());
        std::copy_if(fsm.eventBegin(), fsm.eventEnd(), std::back_inserter(projectedEvents),
                     [&](typename Fsm::EventPropertyId evt) {
                       return std::find(begin, end, evt) == end;
                     });

        ManagedBeliefStateWithSourceStateCreator<Fsm, StateLabelProjection> creator(fsm, projectedFsm, stateManager, projectionStateManager);

        bsMap.init(projectedFsm.behaviour());
        stMap.init(fsm.behaviour());
        return Projection::projectRange(fsm, projectedFsm,
                                        projectedEvents.begin(),
                                        projectedEvents.end(),
                                        begin, end, creator,
                                        bsMap,stMap);
      }
    


      
      template<typename Fsm,  typename EventPropertyIdIterator, typename StateProperty,
               typename StateLabelProjection>
      bool
      abstractEvents(const Fsm & fsm,
                     Fsm & projectedFsm,
                     const StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & stateManager,
                     StatePropertyManager<StateProperty, typename Fsm::StatePropertyId> & projectionStateManager,
                     const StateLabelProjection & projection,
                     EventPropertyIdIterator begin,
                     EventPropertyIdIterator end) {
        BsMap<Fsm> bsMap;
        CstStMap<typename Fsm::State> stMap;
        return abstractEvents(fsm,projectedFsm,stateManager,projectionStateManager,projection, begin,end, bsMap, stMap);
      }
    
    }
  }
}

#endif /* PROJECT_HH */