StateMachine.hh

Go to the documentation of this file.

/* 
 * @file   StateMachine.hh
 * @author Yannick Pencole, ypencole@laas.fr, LAAS-CNRS, Univ. Toulouse, FRANCE
 *
 * Created on 20 october 2017, 13:58
 */

#ifndef __DIADES__AUTOMATA__STATEMACHINE_HH__
#define __DIADES__AUTOMATA__STATEMACHINE_HH__
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <tuple>
#include <diades/utils/Pointer.hh>
#include <diades/utils/Exceptions.hh>
#include <diades/utils/Assertion.hh>
#include <diades/utils/VectorTools.hh>
#include <diades/utils/Iterator.hh>
#include <diades/utils/NullValue.hh>
#include <diades/graph/Graph.hh>
#include <diades/graph/NodeMap.hh>
#include <diades/graph/EdgeMap.hh>
#include <diades/graph/ConstNodeMap.hh>
#include <diades/graph/ConstEdgeMap.hh>


namespace Diades
{
   namespace Automata
   {
      namespace Experimental
      {
         using Diades::Utils::Msg;
         using Diades::Utils::NullValue;
         using std::unordered_set;
         using std::unordered_map;
         using std::set;


         using StatePropertyIdAsSizeT = size_t;

         template<typename StatePropertyId, typename EventPropertyId, typename NullStatePropertyId, typename NullEventPropertyId>
         class StateMachine;

         template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename NullStateProperty, typename NullEventProperty>
         inline void deleteTransition(StateMachine<StatePropertyId, EventPropertyId, NullStateProperty, NullEventProperty> & m, InputIterator first, InputIterator last);

         template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename NullStateProperty, typename NullEventProperty>
         inline void deleteState(StateMachine<StatePropertyId, EventPropertyId, NullStateProperty, NullEventProperty> & m, InputIterator first, InputIterator last);



         template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename Predicate, typename NullStatePropertyId = NullValue<StatePropertyId>, typename NullEventPropertyId>
         inline void
         deleteState(StateMachine<StatePropertyId, EventPropertyId, NullStatePropertyId, NullEventPropertyId> & m, InputIterator first, InputIterator last, Predicate pred);

         template<typename _StatePropertyId,
         typename _EventPropertyId,
         typename _NullStatePropertyId = NullValue<_StatePropertyId>,
         typename _NullEventPropertyId = NullValue<_EventPropertyId>>
         class StateMachine
         {
         public:
            using StatePropertyId = _StatePropertyId;
            using EventPropertyId = _EventPropertyId;
            using NullStatePropertyId = _NullStatePropertyId;
            using NullEventPropertyId = _NullEventPropertyId;
            using Id = size_t;

         private:
            using StatePropertyIdIndex = size_t;




            using EventPropertyIdIndex = size_t;

            const size_t _nullStatePropertyIdIndex = std::numeric_limits<StatePropertyIdIndex>::max();

         public:

            const StatePropertyId nullStatePropertyId = NullStatePropertyId().nullValue();
            const EventPropertyId nullEventPropertyId = NullEventPropertyId().nullValue();

            static string
            defaultStateMachineName()
            {
               return "noname"; 
            }

            static string
            typeName()
            {
               return "Automata::StateMachine";
            }
            using Exception = Diades::Utils::Exception<StateMachine>;


         public:
            typedef Diades::Graph::Node State;
            typedef Diades::Graph::Edge Transition;
            typedef Diades::Graph::NodeIterator StateIterator;
            typedef Diades::Graph::EdgeIterator TransitionIterator;
            typedef list<Transition>::const_iterator EventTransitionIterator;
            typedef unordered_set<State>::const_iterator InitialStateIterator;
            typedef Diades::Graph::InEdgeIterator InputTransitionIterator;
            typedef Diades::Graph::OutEdgeIterator OutputTransitionIterator;
            typedef typename vector<EventPropertyId>::const_iterator EventPropertyIdIterator;
            typedef unordered_set<Transition>::const_iterator OutputEventTransitionIterator;
            typedef unordered_set<Transition>::const_iterator InputEventTransitionIterator;
            typedef unordered_set<State>::const_iterator LabelledStateIterator;





         protected:
           Diades::Graph::Graph _behav; 
           unordered_set<State> _initial; 
           Diades::Graph::NodeMap<bool> _isInitial; 
         private:
           string _name; 
           Id _id; 
           vector<EventPropertyId> _eventPropertyIds; 
           unordered_map<EventPropertyId, EventPropertyIdIndex> _indexOfEventPropertyId;
           Diades::Graph::EdgeMap< EventPropertyIdIndex > _eventPropertyIdIndexOfTransition;

           vector<StatePropertyId> _statePropertyIds;
           vector<State> _stateOfStatePropertyIdIndex;
           unordered_map<StatePropertyId, StatePropertyIdIndex> _indexOfStatePropertyIdIndex;
           Diades::Graph::NodeMap< StatePropertyIdIndex > _statePropertyIdIndexOfState; 
           unordered_set<State> _nullStatePropertyIdStates; 
           vector< Diades::Graph::NodeMap< unordered_set<Transition> > > _transitionsWithTarget;
           vector< Diades::Graph::NodeMap< unordered_set<Transition> > > _transitionsWithSource;
           vector< unordered_set<State> > _sourceWithEventPropertyIdIndex;
           vector< unordered_set<State> > _targetWithEventPropertyIdIndex;
           vector< list<Transition> > _transitionsWithEventPropertyIdIndex;

           template<typename _Iterator>
            class GetStatePropertyId
            {
            public:
               using Data = StatePropertyId;
               using MapStructure = StateMachine;
               using Iterator = _Iterator;

               const Data & operator()(const MapStructure & m, Iterator it) const
               {
                  return m.getStatePropertyId(*it);
               }
            };


         protected:

            EventPropertyId
            getEventFromIndex(size_t index) const
            {
               return _eventPropertyIds[index];
            }

         public:

            template<typename StateIterator>
            using StatePropertyIdRangeIterator = Diades::Utils::RangeMapperIterator<GetStatePropertyId<StateIterator>>;


         public:


            /*********************************************************************/
            /* GENERAL MANAGEMENT */
            /*********************************************************************/

            StateMachine() : _behav(),
            _initial(),
            _isInitial(),
            _name(defaultStateMachineName()),
            _id(),
            _eventPropertyIds(),
            _indexOfEventPropertyId(),
            _eventPropertyIdIndexOfTransition(),
            _statePropertyIds(),
            _stateOfStatePropertyIdIndex(),
            _indexOfStatePropertyIdIndex(),
            _statePropertyIdIndexOfState(),
            _nullStatePropertyIdStates(),
            _transitionsWithTarget(),
            _transitionsWithSource(),
            _sourceWithEventPropertyIdIndex(),
            _targetWithEventPropertyIdIndex(),
            _transitionsWithEventPropertyIdIndex()
            {
               _eventPropertyIdIndexOfTransition.init(_behav);
               _statePropertyIdIndexOfState.init(_behav);
               _isInitial.init(_behav, 0);
            }

            StateMachine(const StateMachine & machine) :
            _behav(machine._behav),
            _initial(),
            _isInitial(),
            _name(machine.name()),
            _id(machine.id()),
            _eventPropertyIds(machine._eventPropertyIds),
            _indexOfEventPropertyId(machine._indexOfEventPropertyId),
            _eventPropertyIdIndexOfTransition(),
            _statePropertyIds(machine._statePropertyIds),
            _stateOfStatePropertyIdIndex(),
            _indexOfStatePropertyIdIndex(machine._indexOfStatePropertyIdIndex),
            _statePropertyIdIndexOfState(),
            _nullStatePropertyIdStates(),
            _transitionsWithTarget(),
            _transitionsWithSource(),
            _sourceWithEventPropertyIdIndex(),
            _targetWithEventPropertyIdIndex(),
            _transitionsWithEventPropertyIdIndex()
            {
               finaliseEventPropertyIds(machine);
               finaliseInitialStates(machine);
               finaliseStatePropertyIds(machine);
               finaliseTransitions(machine);
            }

            StateMachine & operator=(const StateMachine & machine)
            {
               if(this != &machine)
               {
                  clear();
                  _behav = machine._behav;
                  _name = machine.name();
                  _id = machine.id();
                  _eventPropertyIds = machine._eventPropertyIds;
                  _indexOfEventPropertyId = machine._indexOfEventPropertyId;
                  _statePropertyIds = machine._statePropertyIds;
                  _indexOfStatePropertyIdIndex = machine._indexOfStatePropertyIdIndex;
                  finaliseEventPropertyIds(machine);
                  finaliseInitialStates(machine);
                  finaliseStatePropertyIds(machine);
                  finaliseTransitions(machine);
               }
               return *this;
            }

            virtual
            ~StateMachine()
            {
               clear();
            }

            bool operator==(const StateMachine & machine) const
            {
               return this == &machine;
            }

            bool operator!=(const StateMachine & machine) const
            {
               return !(*this == machine);
            }

            virtual void
            clear()
            {
               _behav.clear();
               _initial.clear();
               _isInitial.clear();
               _name = defaultStateMachineName();
               _id = 0;
               _eventPropertyIds.clear();
               _indexOfEventPropertyId.clear();
               _eventPropertyIdIndexOfTransition.clear();
               _statePropertyIds.clear();
               _stateOfStatePropertyIdIndex.clear();
               _indexOfStatePropertyIdIndex.clear();
               _statePropertyIdIndexOfState.clear();
               _nullStatePropertyIdStates.clear();
               _transitionsWithTarget.clear();
               _transitionsWithSource.clear();
               _sourceWithEventPropertyIdIndex.clear();
               _targetWithEventPropertyIdIndex.clear();
               _transitionsWithEventPropertyIdIndex.clear();
               _eventPropertyIdIndexOfTransition.init(_behav);
               _statePropertyIdIndexOfState.init(_behav);
               _isInitial.init(_behav, 0);
            }

            Id
            id() const
            {
               return _id;
            }

            Id
            setId(Id identifier)
            {
               return _id = identifier;
            }

            Graph::Graph &
            behaviour()
            {
               return _behav;
            }

            const Graph::Graph &
            behaviour() const
            {
               return _behav;
            }

            bool
            isEmpty() const
            {
               return(_behav.empty());
            }

            bool
            isValid() const
            {
               return !isEmpty() && name() != defaultStateMachineName();
            }


            /*********************************************************************/
            /* NAME MANAGEMENT */
            /*********************************************************************/

            const string &
            setName(const string & name)
            {

               return _name = name;

            }

            const string &
            name() const
            {

               return _name;
            }
            /********************************************************************/


            /*********************************************************************/
            /* EVENT MANAGEMENT */
            /*********************************************************************/

            EventPropertyId
            nullEvent() const
            {
               return nullEventPropertyId;
            }

            bool
            isNullEvent(EventPropertyId evt) const
            {
               return evt == nullEventPropertyId;
            }

            void
            copyEventPropertyId(const StateMachine & m, const EventPropertyId & event)
            {
               insertEventPropertyId(event);
            }

            void
            copyEventPropertyIds(const StateMachine & m)
            {
               std::for_each(m.eventBegin(), m.eventEnd(),
                             [&](EventPropertyId event)
                             {
                                copyEventPropertyId(m, event);
                             }
                             );
            }

            virtual
            void
            insertEventPropertyId(const EventPropertyId & event)
            {
               if(!containsEvent(event))
               {
                  _eventPropertyIds.push_back(event);
                  //_normalEventPropertyIds.insert(event);
                  _indexOfEventPropertyId[event] = numberOfEvents() - 1;

                  if(numberOfEvents() > _transitionsWithTarget.size())
                  {
                     if(_transitionsWithTarget.size() == _transitionsWithTarget.capacity())
                     {
                        require(Exception, numberOfEvents() < _transitionsWithTarget.max_size(),
                                "insertEvent: too many events, memory allocation will fail");
                        size_t capacity = _transitionsWithTarget.max_size();
                        if(_transitionsWithTarget.max_size() / 2 > numberOfEvents())
                        {
                           capacity = 2 * numberOfEvents();
                        }
                        _transitionsWithTarget.reserve(capacity);
                        _transitionsWithSource.reserve(capacity);
                        _sourceWithEventPropertyIdIndex.reserve(capacity);
                        _targetWithEventPropertyIdIndex.reserve(capacity);
                        _transitionsWithEventPropertyIdIndex.reserve(capacity);
                     }
                     _transitionsWithTarget.resize(numberOfEvents());
                     _transitionsWithSource.resize(numberOfEvents());
                     _sourceWithEventPropertyIdIndex.resize(numberOfEvents());
                     _targetWithEventPropertyIdIndex.resize(numberOfEvents());
                     _transitionsWithEventPropertyIdIndex.resize(numberOfEvents());
                  }

                  _transitionsWithSource[numberOfEvents() - 1].init(_behav);
                  _transitionsWithTarget[numberOfEvents() - 1].init(_behav);
               }
               ensure(Exception, containsEvent(event), "insertEvent:  the event is not properly recorded");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() > numberOfEvents() - 1, "insertEvent: size problem in internal structures");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _transitionsWithTarget.size(), "insertEvent: size problem in internal structures (_sourceWithEvent.size() !=  _transitionsWithTarget.size()");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _transitionsWithSource.size(), "insertEvent: size problem in internal structures (_sourceWithEvent.size() != _transitionsWithSource.size() ");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _targetWithEventPropertyIdIndex.size(), "insertEvent: size problem in internal structures (_sourceWithEvent.size() !=  _targetWithEvent.size()");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _transitionsWithEventPropertyIdIndex.size(), "insertEvent: size problem in internal structures (_sourceWithEvent.size() !=  _transitionsWithEvent.size()");
            }

            unsigned
            numberOfEvents() const
            {
               return _eventPropertyIds.size();
            }

            template<typename EventIter>
            void
            insertEvent(EventIter start, EventIter end)
            {
               EventIter it = start;
               while(it != end)
               {
                  insertEventPropertyId(*it);
                  ++it;
               }



            }

            const EventPropertyId &
            getEvent(Transition t) const
            {
               require(Exception, t.valid(), "getEvent: invalid transition");
               require(Exception, &t.owner() == &_behav, "getEvent: the transition does not belong to this machine");
               return _eventPropertyIds[_eventPropertyIdIndexOfTransition[t]];
            }

            const vector<EventPropertyId> &
            events() const
            {
               return _eventPropertyIds;
            }

            EventPropertyIdIterator
            eventBegin() const
            {
               return _eventPropertyIds.begin();
            }

            EventPropertyIdIterator
            eventEnd() const
            {
               return _eventPropertyIds.end();
            }

            bool
            containsEvent(const EventPropertyId & e) const
            {
               return std::find(_eventPropertyIds.begin(), _eventPropertyIds.end(), e)
                       != _eventPropertyIds.end();
            }

            void
            replaceEvent(const EventPropertyId & e1, const EventPropertyId & e2)
            {
               if(containsEvent(e1))
               {
                  if(e1 != e2)
                  {
                     if(!containsEvent(e2))
                     {
                        insertEventPropertyId(e2);
                     }
                     auto e1Id = _indexOfEventPropertyId.at(e1);
                     auto e2Id = _indexOfEventPropertyId.at(e2);

                     for(list<Transition>::const_iterator transIt = _transitionsWithEventPropertyIdIndex[e1Id].begin();
                         transIt != _transitionsWithEventPropertyIdIndex[e1Id].end();
                         ++transIt)
                     {
                        _sourceWithEventPropertyIdIndex[e2Id].insert(transIt->source());
                        _targetWithEventPropertyIdIndex[e2Id].insert(transIt->target());
                        _transitionsWithEventPropertyIdIndex[e2Id].push_back(*transIt);
                        _eventPropertyIdIndexOfTransition[*transIt] = e2Id;
                        _transitionsWithSource[e2Id][transIt->source()].insert(*transIt);
                        _transitionsWithTarget[e2Id][transIt->target()].insert(*transIt);
                     }
                     finaliseEventPropertyIdRemoval(e1);
                  }
               }
            }


            /********************************************************************/

            void
            removeEvent(const EventPropertyId & e)
            {
               deleteTransition(eventTransitionBegin(e), eventTransitionEnd(e));
               eraseEventPropertyId(_indexOfEventPropertyId.at(e));
            }


            /*******************************************************************/
            /* STATE MANAGEMENT */
            /*********************************************************************/

            State
            newState()
            {
               State result = _behav.newNode();
               _nullStatePropertyIdStates.insert(result);
               _statePropertyIdIndexOfState[result] = _nullStatePropertyIdIndex;
               return result;
            }

            std::pair<State, bool>
            newState(const StatePropertyId & sProperty)
            {
               State result;
               bool present = false;
               if(NullStatePropertyId()(sProperty))
               {
                  return std::make_pair(newState(), true);
               }


               auto it = _indexOfStatePropertyIdIndex.find(sProperty);
               if(it != _indexOfStatePropertyIdIndex.end())
               {
                  result = _stateOfStatePropertyIdIndex[it->second];
                  assertion(Exception, result.valid(), "newState: _stateOfProperty is incorrectly initialised");
               }
               else
               {
                  present = true;
                  result = _behav.newNode();


                  _indexOfStatePropertyIdIndex[sProperty] = _statePropertyIds.size();
                  _statePropertyIdIndexOfState[result] = _statePropertyIds.size();
                  _statePropertyIds.push_back(sProperty);
                  _stateOfStatePropertyIdIndex.push_back(result);

               }

               ensure(Exception, result.valid() && (_statePropertyIdIndexOfState[result] == _indexOfStatePropertyIdIndex[sProperty]), "newState");
               ensure(Exception, getStateFromIndex(getIndexOfState(result)) == result,
                      "newState: inconsistency between getStateFromIndex/getIndexOfState");
               return std::make_pair(result, present);
            }

            const StatePropertyId &
            getStatePropertyId(State state) const
            {
               require(Exception, state.valid(), "getProperty: invalid state");
               require(Exception, &state.owner() == &_behav, "getProperty: the state does not belong to this machine");
               if(isNullState(state))
               {
                  return nullStatePropertyId;
               }
               return _statePropertyIds[_statePropertyIdIndexOfState[state]];
            }

            bool
            setStatePropertyId(State state, const StatePropertyId & sProperty)
            {
               require(Exception, state.valid(), "setProperty: invalid state");
               require(Exception, &state.owner() == &_behav, "setProperty: the state does not belong to this machine");
               auto it = _indexOfStatePropertyIdIndex.find(sProperty);
               bool isNullProperty = (sProperty == nullStatePropertyId);
               bool success = true;
               if(!isNullProperty)
               {
                  success = it == _indexOfStatePropertyIdIndex.end();
                  if(!success)
                  {
                     success = _statePropertyIdIndexOfState[state] == it->second;
                     return success;
                  }
               }
               // state will certainly assigned to sProperty
               if(isNullState(state) && isNullProperty)
               {
                  return success;
               }

               if(isNullState(state))
               {
                  _nullStatePropertyIdStates.erase(state);
                  _indexOfStatePropertyIdIndex[sProperty] = _statePropertyIds.size();
                  _statePropertyIdIndexOfState[state] = _statePropertyIds.size();
                  _statePropertyIds.push_back(sProperty);
                  _stateOfStatePropertyIdIndex.push_back(state);
                  return success;
               }

               eraseStatePropertyId(state);

               // and we add the new one
               if(isNullProperty)
               {
                  _statePropertyIdIndexOfState[state] = _nullStatePropertyIdIndex;
                  _nullStatePropertyIdStates.insert(state);
               }
               else
               {
                  _indexOfStatePropertyIdIndex[sProperty] = _statePropertyIds.size();
                  _statePropertyIdIndexOfState[state] = _statePropertyIds.size();
                  _statePropertyIds.push_back(sProperty);
                  _stateOfStatePropertyIdIndex.push_back(state);
               }
               if(!isNullProperty)
               {
                  ensure(Exception, getStateFromIndex(getIndexOfState(state)) == state,
                         "setStatePropertyId: inconsistency between getStateFromIndex/getIndexOfState");
               }
               return success;
            }

            State
            getState(const StatePropertyId & sProperty) const
            {
               auto it = _indexOfStatePropertyIdIndex.find(sProperty);
               //require(Exception, it != _stateOfProperty.end(), "getState: no such a state");
               if(it == _indexOfStatePropertyIdIndex.end())
               {
                  return State();
               }
               return _stateOfStatePropertyIdIndex[it->second];
            }

           virtual void
           deleteState(State state)
           {
             require(Exception, state.valid(), "deleteState: invalid state");
             require(Exception, &state.owner() == &_behav, "deleteState: the state does not belong to this state machine");
unsetInitial(state);

               if(isNullState(state))
               {
                  _nullStatePropertyIdStates.erase(state);
               }
               else
               {

                  // here we need to erase the  state property
                  if(_statePropertyIdIndexOfState[state] == _statePropertyIds.size() - 1)
                  {
                     //cool it is the last recorded property
                     _indexOfStatePropertyIdIndex.erase(_statePropertyIds.back());
                     _stateOfStatePropertyIdIndex.pop_back();
                     _statePropertyIds.pop_back();
                     _statePropertyIdIndexOfState[state] = _nullStatePropertyIdIndex;
                  }
                  else
                  {
                     // not cool we need to swap to have a tidy vector
                     auto stateWhosePropertyIsSwapped = _stateOfStatePropertyIdIndex[_statePropertyIds.size() - 1];



                     auto & keptProperty = _statePropertyIds[_statePropertyIdIndexOfState[state]];
                     auto & erasedProperty = _statePropertyIds[_statePropertyIds.size() - 1];
                     std::swap(keptProperty, erasedProperty);
                     size_t keptPropertyIndex = _statePropertyIdIndexOfState[state];
                     _statePropertyIdIndexOfState[stateWhosePropertyIsSwapped] = keptPropertyIndex;
                     _stateOfStatePropertyIdIndex[keptPropertyIndex] = stateWhosePropertyIsSwapped;
                     _indexOfStatePropertyIdIndex[keptProperty] = keptPropertyIndex;

                     _indexOfStatePropertyIdIndex.erase(_statePropertyIds.back());
                     _stateOfStatePropertyIdIndex.pop_back();
                     _statePropertyIds.pop_back();
                     _statePropertyIdIndexOfState[state] = _nullStatePropertyIdIndex;

                  }
               }
               deleteTransition(outputTransitionBegin(state), outputTransitionEnd(state));
               deleteTransition(inputTransitionBegin(state), inputTransitionEnd(state));
               _behav.deleteNode(state);


            }

            void
            deleteState(StateIterator start, StateIterator end)
            {
              //list<State> tmp;
              //tmp.insert(tmp.end(), start, end);
              //              Automata::Experimental::deleteState(*this, tmp.begin(), tmp.end());
              Automata::Experimental::deleteState(*this, start, end);
            }

            unsigned
            numberOfStates() const
            {
               return _behav.numberOfNodes();
            }

            StateIterator
            stateBegin() const
            {
               return _behav.nodeBegin();
            }

            StateIterator
            stateEnd() const
            {
               return _behav.nodeEnd();
            }

            typedef typename std::vector<StatePropertyId>::const_iterator StatePropertyIdIterator;

            StatePropertyIdIterator
            statePropertyIdBegin() const
            {
               return _statePropertyIds.begin();
            }

            StatePropertyIdIterator
            statePropertyIdEnd() const
            {
               return _statePropertyIds.end();
            }

            template<typename StateIterator>
            StatePropertyIdRangeIterator<StateIterator>
            statePropertyIdRangeIterator(StateIterator iterator) const
            {
               return StatePropertyIdRangeIterator<StateIterator>(*this, iterator);
            }

            void
            setInitial(State state)
            {
               if(state.valid() && (&state.owner() == &_behav))
               {
                  _initial.insert(state);
                  _isInitial[state] = 1;
               }
            }

            void
            unsetInitial(State state)
            {
               if(state.valid() && (&state.owner() == &_behav))
               {
                  _initial.erase(state);
                  _isInitial[state] = 0;
               }
            }

            void
            setAllInitialStates()
            {
               _initial.insert(stateBegin(), stateEnd());
               _isInitial.initValue(stateBegin(), stateEnd(), 1);
            }

            void
            clearAllInitialStates()
            {
               _isInitial.initValue(stateBegin(), stateEnd(), 0);
               _initial.clear();
            }


           void swapInitialState(State state)
           {
             if(isInitial(state))
               {
                 unsetInitial(state);
               }
             else
               {
                 setInitial(state);
               }
           }

           InitialStateIterator
                   initialStateBegin() const
             {
               return _initial.begin();
             }

           InitialStateIterator
            initialStateEnd() const
            {
               return _initial.end();
            }

            unsigned
            numberOfInitialStates() const
            {
               return _initial.size();
            }

            bool
            isInitial(State state) const
            {
               return(state.valid()) && (&state.owner() == &_behav) && (_isInitial[state] == 1);
            }

            bool
            isNullState(State state) const
            {
               return _statePropertyIdIndexOfState[state] == _nullStatePropertyIdIndex;
            }









            /*******************************************************************/
            /*  TRANSITION MANAGEMENT   */
            /*********************************************************************/

         public:

            Transition
            newTransition(State source, State target, const EventPropertyId & event)
            {
               require(Exception, source.valid(), "newTransition: invalid source state");
               require(Exception, &source.owner() == &_behav, "newTransition: the source state does not belong to this component");
               require(Exception, target.valid(), "newTransition: invalid target state");
               require(Exception, &target.owner() == &_behav, "newTransition: the target state does not belong to this component");

               Transition result;
               insertEventPropertyId(event);
               bool found = false;
               OutputEventTransitionIterator it = outputEventTransitionBegin(source, event);
               OutputEventTransitionIterator itEnd = outputEventTransitionEnd(source, event);

               while(!found && (it != itEnd))
               {
                  found = (target == it->target());
                  if(!found)
                  {
                     ++it;
                  }
               }
               if(found)
               {
                  result = *it;
               }
               else
               {

                  result = _behav.newEdge(source, target);
                  assertion(Exception, result.valid(), "the result is not valid");
                  assertion(Exception, &result.owner() == &_behav, "the result has not the right owner");
                  _eventPropertyIdIndexOfTransition[result] = _indexOfEventPropertyId[event];
                  assertion(Exception, _eventPropertyIdIndexOfTransition[result] == _indexOfEventPropertyId[event], "the event of result is not correctly set");
                  size_t eventIndex = _indexOfEventPropertyId[event];

                  _transitionsWithTarget[eventIndex][target].insert(result);
                  _transitionsWithSource[eventIndex][source].insert(result);
                  _sourceWithEventPropertyIdIndex[eventIndex].insert(source);
                  _targetWithEventPropertyIdIndex[eventIndex].insert(target);
                  _transitionsWithEventPropertyIdIndex[eventIndex].push_back(result);
               }
               ensure(Exception, result.valid(), "newTransition: the returned transition is invalid!");
               ensure(Exception, result.source() == source, "newTransition:  the returned transition has an incorrect source");
               ensure(Exception, result.target() == target, "newTransition:  the returned transition has an incorrect target");
               ensure(Exception, getEvent(result) == event, "newTransition:  the returned transition has an incorrect event");
               return result;
            }

            Transition
            newTransition(const StatePropertyId & source,
                          const StatePropertyId & target,
                          const EventPropertyId & event)
            {
               return newTransition(std::get<0>(newState(source)), std::get<0>(newState(target)), event);
            }

            void
            deleteTransition(Transition t)
            {
               require(Exception, t.valid(), "deleteTransition: invalid transition");
               require(Exception, &t.owner() == &_behav, "deleteTransition: the transition does not belong to the component");
               const auto & e = getEvent(t);
               const auto & target = t.target();
               const auto & source = t.source();
               size_t eventIndex = _indexOfEventPropertyId.at(e);
               _transitionsWithTarget[eventIndex][target].erase(t);
               if(_transitionsWithTarget[eventIndex][target].empty())
               {
                  _targetWithEventPropertyIdIndex[eventIndex].erase(target);
               }

               _transitionsWithSource[eventIndex][source].erase(t);
               if(_transitionsWithSource[eventIndex][source].empty())
               {
                  _sourceWithEventPropertyIdIndex[eventIndex].erase(source);
               }


               _transitionsWithEventPropertyIdIndex[eventIndex].remove(t);
               _behav.deleteEdge(t);


            }

            void
            deleteTransition(TransitionIterator start, TransitionIterator end)
            {
               list<Transition> tmp;
               tmp.insert(tmp.end(), start, end);
               Automata::Experimental::deleteTransition(*this, tmp.begin(), tmp.end());



            }

            void
            deleteTransition(EventTransitionIterator start, EventTransitionIterator end)
            {
               list<Transition> tmp;
               tmp.insert(tmp.end(), start, end);
               Automata::Experimental::deleteTransition(*this, tmp.begin(), tmp.end());

            }

            LabelledStateIterator
            beginOfSourceStateOfEvent(const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       "beginOfSourceStateOfEvent: the event does not belong to the component");
               return _sourceWithEventPropertyIdIndex[_indexOfEventPropertyId.at(e)].begin();
            }

            LabelledStateIterator
            endOfSourceStateOfEvent(const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       "endOfSourceStateOfEvent: the event does not belong to the component");
               return _sourceWithEventPropertyIdIndex[_indexOfEventPropertyId.at(e)].end();
            }

            LabelledStateIterator
            beginOfTargetStateOfEvent(const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       "beginOfTargetStateOfEvent: the event does not belong to the component");
               return _targetWithEventPropertyIdIndex[_indexOfEventPropertyId.at(e)].begin();
            }

            LabelledStateIterator
            endOfTargetStateOfEvent(const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       "endOfTargetStateOfEvent: the event does not belong to the component");
               return _targetWithEventPropertyIdIndex[_indexOfEventPropertyId.at(e)].end();
            }

            EventTransitionIterator
            eventTransitionBegin(const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       "eventTransitionBegin: the event does not belong to the component");
               return _transitionsWithEventPropertyIdIndex[_indexOfEventPropertyId.at(e)].begin();
            }

            EventTransitionIterator
            eventTransitionEnd(const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       "eventTransitionEnd: the event does not belong to the component");
               return _transitionsWithEventPropertyIdIndex[_indexOfEventPropertyId.at(e)].end();
            }

            OutputEventTransitionIterator
            outputEventTransitionBegin(State s, const EventPropertyId & e) const
            {

               require(Exception, containsEvent(e),
                       Msg("outputEventTransitionBegin: the event '%1%' does not belong to the component") % e);
               require(Exception, s.valid(), "outputEventTransitionBegin: invalid state");
               require(Exception, &s.owner() == &_behav, "outputEventTransitionBegin: the state does not belong to this component");
               return _transitionsWithSource[_indexOfEventPropertyId.at(e)][s].begin();
            }

            OutputEventTransitionIterator
            outputEventTransitionEnd(State s, const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       Msg("outputEventTransitionEnd: the event '%1%' does not belong to the component") % e);
               require(Exception, s.valid(), "outputEventTransitionEnd: invalid state");
               require(Exception, &s.owner() == &_behav, "outputEventTransitionEnd: the state does not belong to this component");
               return _transitionsWithSource[_indexOfEventPropertyId.at(e)][s].end();
            }

            InputEventTransitionIterator
            inputEventTransitionBegin(State s, const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       Msg("inputEventTransitionBegin: the event '%1%' does not belong to the component") % e);
               require(Exception, s.valid(), "inputEventTransitionBegin: invalid state");
               require(Exception, &s.owner() == &_behav, "inputEventTransitionBegin: the state does not belong to this component");
               return _transitionsWithTarget[_indexOfEventPropertyId.at(e)][s].begin();
            }

            InputEventTransitionIterator
            inputEventTransitionEnd(State s, const EventPropertyId & e) const
            {
               require(Exception, containsEvent(e),
                       Msg("inputEventTransitionEnd: the event '%1%' does not belong to the component") % e);
               require(Exception, s.valid(), "inputEventTransitionEnd: invalid state");
               require(Exception, &s.owner() == &_behav, "inputEventTransitionEnd: the state does not belong to this component");
               return _transitionsWithTarget[_indexOfEventPropertyId.at(e)][s].end();
            }

            TransitionIterator
            transitionBegin() const
            {
               return _behav.edgeBegin();
            }

            TransitionIterator
            transitionEnd() const
            {
               return _behav.edgeEnd();
            }

            OutputTransitionIterator
            outputTransitionBegin(State s) const
            {
               require(Exception, s.valid(), "outputTransitionBegin: the state is not valid");
               require(Exception, &s.owner() == &_behav, "outputTransitionBegin: the state does not belong to the component");
               return s.outEdgeBegin();
            }

            OutputTransitionIterator
            outputTransitionEnd(State s) const
            {
               require(Exception, s.valid(), "outputTransitionEnd: the state is not valid");
               require(Exception, &s.owner() == &_behav, "outputTransitionEnd: the state does not belong to the component");
               return s.outEdgeEnd();
            }

            InputTransitionIterator
            inputTransitionBegin(State s) const
            {
               require(Exception, s.valid(), "inputTransitionBegin: the state is not valid");
               require(Exception, &s.owner() == &_behav, "inputTransitionBegin: the state does not belong to the component");
               return s.inEdgeBegin();
            }

            InputTransitionIterator
            inputTransitionEnd(State s) const
            {
               require(Exception, s.valid(), "inputTransitionEnd: the state is not valid");
               require(Exception, &s.owner() == &_behav, "inputTransitionEnd: the state does not belong to the component");
               return s.inEdgeEnd();
            }

            unsigned
            numberOfTransitions() const
            {
               return _behav.numberOfEdges();
            }


         private:

            void
            finaliseTransitions(const StateMachine & machine)
            {

               _sourceWithEventPropertyIdIndex.resize(machine._sourceWithEventPropertyIdIndex.size());
               _targetWithEventPropertyIdIndex.resize(machine._targetWithEventPropertyIdIndex.size());
               for(TransitionIterator it = machine.transitionBegin();
                   it != machine.transitionEnd(); ++it)
               {

                  _transitionsWithEventPropertyIdIndex.resize(machine._transitionsWithEventPropertyIdIndex.size());
                  Transition transition = _behav.getEdge(it->id());
                  auto eventId = _indexOfEventPropertyId[machine.getEvent(*it)];
                  _eventPropertyIdIndexOfTransition[transition] = eventId;
                  _transitionsWithTarget[eventId][transition.target()].insert(transition);
                  _transitionsWithSource[eventId][transition.source()].insert(transition);
                  _sourceWithEventPropertyIdIndex[eventId].insert(transition.source());
                  _targetWithEventPropertyIdIndex[eventId].insert(transition.target());
                  _transitionsWithEventPropertyIdIndex[eventId].push_back(transition);
               }

            }

            void
            finaliseInitialStates(const StateMachine & machine)
            {
               _isInitial.init(_behav, 0);
               for(InitialStateIterator it = machine.initialStateBegin();
                   it != machine.initialStateEnd();
                   ++it)
               {
                  setInitial(_behav.getNode(it->id()));
               }
            }

            void
            finaliseStatePropertyIds(const StateMachine & machine)
            {
               _statePropertyIdIndexOfState.init(_behav);
               _nullStatePropertyIdStates.clear();
               _stateOfStatePropertyIdIndex.resize(_statePropertyIds.size() + 1);
               for(StateIterator it = machine.stateBegin();
                   it != machine.stateEnd(); ++it)
               {
                  State copiedState = _behav.getNode(it->id()); // copiedState is the copy of *it
                  if(machine.isNullState(*it))
                  {
                     _nullStatePropertyIdStates.insert(copiedState);
                     _statePropertyIdIndexOfState[copiedState] = _nullStatePropertyIdIndex;
                  }
                  else
                  {
                     _statePropertyIdIndexOfState[copiedState] = machine._statePropertyIdIndexOfState[*it];
                     _stateOfStatePropertyIdIndex[machine._statePropertyIdIndexOfState[*it]] = copiedState;
                     ensure(Exception, getStateFromIndex(getIndexOfState(copiedState)) == copiedState,
                            "finaliseStatePropertyIds: inconsistency between getStateFromIndex/getIndexOfState (non-null)");
                  }

               }
            }

            void
            finaliseEventPropertyIds(const StateMachine & machine)
            {
               _transitionsWithTarget.resize(machine._transitionsWithTarget.size());
               _transitionsWithSource.resize(machine._transitionsWithSource.size());
               _eventPropertyIdIndexOfTransition.init(_behav);
               for(const auto & event : _eventPropertyIds)
               {
                  _transitionsWithTarget[_indexOfEventPropertyId[event]].init(_behav);
                  _transitionsWithSource[_indexOfEventPropertyId[event]].init(_behav);
               }
            }

            void
            finaliseEventPropertyIdRemoval(const EventPropertyId & e)
            {
               eraseEventPropertyId(_indexOfEventPropertyId.at(e));
            }

            void
            eraseStatePropertyId(State state)
            {
               if(_statePropertyIdIndexOfState[state] == _statePropertyIds.size() - 1)
               {
                  //cool it is the last recorded property
                  _indexOfStatePropertyIdIndex.erase(_statePropertyIds.back());
                  _stateOfStatePropertyIdIndex.pop_back();
                  _statePropertyIds.pop_back();
                  _statePropertyIdIndexOfState[state] = 0;
               }
               else
               {
                  // not cool we need to swap to have a tidy vector
                  auto stateWhosePropertyIsSwapped = _stateOfStatePropertyIdIndex[_statePropertyIds.size() - 1];
                  auto & keptProperty = _statePropertyIds[_statePropertyIdIndexOfState[state]];
                  auto & erasedProperty = _statePropertyIds[_statePropertyIds.size() - 1];
                  std::swap(keptProperty, erasedProperty);
                  size_t keptPropertyIndex = _statePropertyIdIndexOfState[state];
                  _statePropertyIdIndexOfState[stateWhosePropertyIsSwapped] = keptPropertyIndex;
                  _stateOfStatePropertyIdIndex[keptPropertyIndex] = stateWhosePropertyIsSwapped;
                  _indexOfStatePropertyIdIndex[keptProperty] = keptPropertyIndex;
                  _indexOfStatePropertyIdIndex.erase(_statePropertyIds.back());
                  _stateOfStatePropertyIdIndex.pop_back();
                  _statePropertyIds.pop_back();
                  _statePropertyIdIndexOfState[state] = 0;
               }
            }
         protected:

            virtual
            void
            eraseEventPropertyId(size_t eventIndex)
            {
               //                                       _normalEventPropertyIds.erase(_eventPropertyIds[eventIndex]);
               //                                       _faultyEventPropertyIds.erase(_eventPropertyIds[eventIndex]);


               if(eventIndex == _eventPropertyIds.size() - 1)
               {
                  //cool it is the last recorded EventProperty
                  _indexOfEventPropertyId.erase(_eventPropertyIds.back());
                  _eventPropertyIds.pop_back();
                  _transitionsWithEventPropertyIdIndex.pop_back();
                  _sourceWithEventPropertyIdIndex.pop_back();
                  _targetWithEventPropertyIdIndex.pop_back();
                  _transitionsWithSource.pop_back();
                  _transitionsWithTarget.pop_back();
               }
               else
               {
                  // not cool we need to swap to have a tidy vector
                  size_t keptEventPropertyIndexBeforeSwap = _eventPropertyIds.size() - 1;
                  _indexOfEventPropertyId.erase(_eventPropertyIds.at(eventIndex));
                  auto keptEventPropertyIndexAfterSwap = Diades::Utils::swapRemove(_eventPropertyIds, eventIndex);
                  _indexOfEventPropertyId[_eventPropertyIds[keptEventPropertyIndexAfterSwap]] = keptEventPropertyIndexAfterSwap;
                  _transitionsWithEventPropertyIdIndex[keptEventPropertyIndexAfterSwap] = _transitionsWithEventPropertyIdIndex[keptEventPropertyIndexBeforeSwap];
                  _transitionsWithEventPropertyIdIndex.pop_back();
                  _sourceWithEventPropertyIdIndex[keptEventPropertyIndexAfterSwap] = _sourceWithEventPropertyIdIndex[keptEventPropertyIndexBeforeSwap];
                  _sourceWithEventPropertyIdIndex.pop_back();
                  _targetWithEventPropertyIdIndex[keptEventPropertyIndexAfterSwap] = _targetWithEventPropertyIdIndex[keptEventPropertyIndexBeforeSwap];
                  _targetWithEventPropertyIdIndex.pop_back();
                  _transitionsWithSource[keptEventPropertyIndexAfterSwap] = _transitionsWithSource[keptEventPropertyIndexBeforeSwap];
                  _transitionsWithSource.pop_back();
                  _transitionsWithTarget[keptEventPropertyIndexAfterSwap] = _transitionsWithTarget[keptEventPropertyIndexBeforeSwap];
                  _transitionsWithTarget.pop_back();


                  for(auto it = transitionBegin(); it != transitionEnd(); ++it)
                  {
                     if(_eventPropertyIdIndexOfTransition[*it] == keptEventPropertyIndexBeforeSwap)
                     {
                        _eventPropertyIdIndexOfTransition[*it] = keptEventPropertyIndexAfterSwap;
                     }
                  }

               }


               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _eventPropertyIds.size(), "eraseEventProperty: size problem in internal structures");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _transitionsWithTarget.size(), "eraseEventProperty: size problem in internal structures (_sourceWithEvent.size() !=  _transitionsWithTarget.size()");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _transitionsWithSource.size(), "eraseEventProperty: size problem in internal structures (_sourceWithEvent.size() != _transitionsWithSource.size() ");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _targetWithEventPropertyIdIndex.size(), "eraseEventProperty: size problem in internal structures (_sourceWithEvent.size() !=  _targetWithEvent.size()");
               ensure(Exception, _sourceWithEventPropertyIdIndex.size() == _transitionsWithEventPropertyIdIndex.size(), "eraseEventProperty: size problem in internal structures (_sourceWithEvent.size() !=  _transitionsWithEvent.size()");


            }

            State
            getStateFromIndex(StatePropertyIdIndex index) const
            {
               if(index == _nullStatePropertyIdIndex)
               {
                  return State();
               }
               return _stateOfStatePropertyIdIndex.at(index);
            }

            StatePropertyIdIndex
            getIndexOfState(State s) const
            {
               if(isNullState(s))
               {
                  return _nullStatePropertyIdIndex;
               }
               return _statePropertyIdIndexOfState[s];
            }

         };

         template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename IsNullStatePropertyId, typename IsNullEventProperty>
         inline void
         deleteTransition(StateMachine<StatePropertyId, EventPropertyId, IsNullStatePropertyId, IsNullEventProperty> & m, InputIterator first, InputIterator last)
         {
           while(first!=last)
             {
               auto t = *first;
               ++first; // i do that way to avoid any issue if first is a EdgeIterator.
               m.deleteTransition(t);
             }
         }

        template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename IsNullStateProperty, typename IsNullEventProperty>
        inline void
        deleteState(StateMachine<StatePropertyId, EventPropertyId, IsNullStateProperty, IsNullEventProperty> & m, InputIterator first, InputIterator last)
        {
          while(first!=last)
            {
              auto s = *first;
              ++first; // i do that way to avoid any issue if first is a NodeIterator.
              m.deleteState(s);
            }
        }

        template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename Predicate, typename IsNullStateProperty, typename IsNullEventProperty>
        inline void
        deleteState(StateMachine<StatePropertyId, EventPropertyId, IsNullStateProperty, IsNullEventProperty> & m, InputIterator first, InputIterator last, Predicate pred)
        {

          while(first!=last)
            {
              auto s = *first;
              ++first; // i do that way to avoid any issue if first is a NodeIterator.
              if(pred(s))
                {
                  m.deleteState(s);
                }
            }
        }
        template<typename StatePropertyId, typename EventPropertyId, typename InputIterator, typename Predicate, typename IsNullStateProperty, typename IsNullEventProperty, typename StatePropertyIdInsertIterator >
        inline void
        deleteState(StateMachine<StatePropertyId, EventPropertyId, IsNullStateProperty, IsNullEventProperty> & m, InputIterator first, InputIterator last, Predicate pred, StatePropertyIdInsertIterator insertIt)
        {

          while(first!=last)
            {
              auto s = *first;
              ++first; // i do that way to avoid any issue if first is a NodeIterator.
              if(pred(s))
                {
                  *insertIt++=m.getStatePropertyId(s);
                  m.deleteState(s);
                }
            }
        }


        template<typename Type>
        using CstStMap = Diades::Graph::ConstNodeMap<Type>;


        template<typename Type>
        using StMap = Diades::Graph::NodeMap<Type>;


        template<typename Type>
        using CstTrMap = Diades::Graph::ConstEdgeMap<Type>;


        template<typename Type>
        using TrMap = Diades::Graph::EdgeMap<Type>;



        
      }
   }

}


//
//
//namespace std
//{
//
//      template <typename StateProperty, typename EventProperty>
//      struct iterator_traits<Diades::Automata::Experimental::StateMachine<StateProperty, EventProperty>>
//      {
//              using iterator_category = std::forward_iterator_tag;
//              using value_type = StateProperty;
//      };
//
//}
//

#endif /* STATEMACHINE_HH */