---

streamable_dfa.hh

/*
*  Name:      streamable_dfa.hh
*  Author:    Rafael Jesus Alcantara Perez
*  Summary:   Streamable Deterministic Finite Automaton
*  Date:      $Date: 2003/04/14 00:18:31 $
*  Revision:  $Revision: 1.1 $
*
*  Copyright (C) 1999-2002  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
*  MA 02111-1307, USA.
*/

#ifndef _MPCL_AUTOMATON_STREAMABLE_DFA__
#define _MPCL_AUTOMATON_STREAMABLE_DFA__

#include <iostream>
#include <iterator>
#include "../event/event_handler.hh"
#include "../io/streamable.hh"
#include "../text/regex/matcher.hh"
#include "../text/string.hh"
#include "../util/collection/map.hh"
#include "defs.hh"
#include "deterministic_finite_automaton.hh"


namespace mpcl
{

  namespace automaton
  {

    using event::TEventHandler;
    using io::IStreamable;
    using text::TString;
    using text::regex::TMatcher;

    template <typename TState, typename TEvent>
    class TStreamableDfa                                   :
      public IStreamable<>                                 ,
      public TDeterministicFiniteAutomaton<TState, TEvent>
    {

      public:

        typedef
          IStreamable<>::char_type
          char_type;

        typedef
          IStreamable<>::traits_type
          traits_type;


      protected:

        typedef
          typename TDeterministicFiniteAutomaton<TState, TEvent>::TPair
          TPair;

        typedef
          typename TDeterministicFiniteAutomaton<TState, TEvent>::TTransitionMap
          TTransitionMap;

        typedef
          typename TDeterministicFiniteAutomaton<TState, TEvent>::TStateSet
          TStateSet;

        TEventHandler<TEvent>&   rtEventHandler;


      protected:

        typedef
          TMap<TString, TEvent>
          TStringToEventMap;

        typedef
          TMap<TString, TState>
          TStringToStateMap;

        TStringToEventMap   tStringToEventMap;

        TStringToStateMap   tStringToStateMap;

        TString   yDescription;

        TString   yName;

        TString   yPublic;

        TString   ySystem;


      protected:

        //
        //  C O N S T R U C T O R S
        //

        void read (std::basic_istream<char_type, traits_type>& rtSOURCE_ISTREAM);

        void readFooter (TMatcher& rtSOURCE_REM);

        void readHeader (TMatcher& rtSOURCE_REM);

        void readTransitionTable (TMatcher& rtSOURCE_REM);


      public:

        //
        //  C O N S T R U C T O R S
        //

        TStreamableDfa (TEventHandler<TEvent>& rtSOURCE_EVENT_HANDLER)           :
          IStreamable<>                                 ()                       ,
          TDeterministicFiniteAutomaton<TState, TEvent> ()                       ,
          rtEventHandler                                (rtSOURCE_EVENT_HANDLER) ,
          tStringToEventMap                             ()                       ,
          tStringToStateMap                             ()                       ,
          yDescription                                  ()                       ,
          yName                                         ()                       ,
          yPublic                                       ()                       ,
          ySystem                                       ()                       {}

        void start (void);


      protected:

        //
        //  S E L E C T O R S
        //

        virtual void check (void) const;

        TString eventToString (const TEvent& krtSOURCE_EVENT) const
          throw (TNotFoundException);

        TString stateToString (const TState& krtSOURCE_STATE) const
          throw (TNotFoundException);

        void write (std::basic_ostream<char_type, traits_type>& rtTARGET_OSTREAM) const
        {
          writeHeader          (rtTARGET_OSTREAM);
          writeTransitionTable (rtTARGET_OSTREAM);
          writeFooter          (rtTARGET_OSTREAM);
        }

        void writeFooter (std::basic_ostream<char_type, traits_type>& rtTARGET_OSTREAM) const
        {
          rtTARGET_OSTREAM << "</dfaml>\n";
        }

        void writeHeader (std::basic_ostream<char_type, traits_type>& rtTARGET_OSTREAM) const;

        void writeTransitionTable (std::basic_ostream<char_type, traits_type>& rtTARGET_OSTREAM) const;


      public:

        //
        //  S E L E C T O R S
        //

        using TDeterministicFiniteAutomaton<TState, TEvent>::isFinal;

        bool isFinal (const TString& rkySOURCE_STATE) const
        {
          return TDeterministicFiniteAutomaton<TState, TEvent>::isFinal (tStringToStateMap [rkySOURCE_STATE]);
        }

        bool isFinal (const char* pkcSOURCE_STATE) const
        {
          return TDeterministicFiniteAutomaton<TState, TEvent>::isFinal (tStringToStateMap [pkcSOURCE_STATE]);
        }

    };  // class TStreamableDfa
    
  }  // namespace automaton

}  // namespace mpcl


//
//  C O N S T R U C T O R S
//

template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
read (std::basic_istream<char_type, traits_type>& rtSOURCE_ISTREAM)
{
  
  //
  //  DFAML document must be validated, so parsing
  //  doesn't have to worry about syntax errors.
  //  First it musts find DFAML tag, and then skip
  //  it.
  //
  TMatcher   tMatcher (rtSOURCE_ISTREAM);

  tTransitionMap.clear();  
  tMatcher.setCaseSensitiveness (false);

  readHeader (tMatcher);
  if ( !yPublic.empty() )
  {
    if ( yPublic != pkcDOCTYPE_VERSION_1_0 )
    {
      throw TNotDfamlFileException ("this isn't a DFAML doctype");
    }
  }
  readTransitionTable (tMatcher);
  readFooter (tMatcher);
  check();

}  // read()


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
readFooter (TMatcher& rtSOURCE_REM)
{

  //
  //  DFAML end-tag.
  //
  while ( rtSOURCE_REM.scan (pkcCommentTagPattern, NULL) );
  rtSOURCE_REM.scan (pkcDFAML_EndTagPattern, NULL);
  while ( rtSOURCE_REM.scan (pkcCommentTagPattern, NULL) );

}  // readFooter()


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
readHeader (TMatcher& rtSOURCE_REM)
{

# define DFA_REMOVE_COMMENTS(rtREM)                           \
         {                                                    \
           while ( rtREM.scan (pkcCommentTagPattern, NULL) ); \
         }

  //
  //  !DOCTYPE tag.
  //
  DFA_REMOVE_COMMENTS (rtSOURCE_REM);
  if ( !rtSOURCE_REM.scan (pkcDOCTYPE_TagPattern_1, NULL) )
  {
    if ( !rtSOURCE_REM.scan (pkcDOCTYPE_TagPattern_2, NULL) )
    {
      if ( !rtSOURCE_REM.scan (pkcDOCTYPE_TagPattern_3, &ySystem, NULL) )
      {
        rtSOURCE_REM.scan (pkcDOCTYPE_TagPattern_4, &yPublic, NULL);
        yPublic.lowercase();
      }
    }
  }
  DFA_REMOVE_COMMENTS (rtSOURCE_REM);
  
  //
  //  DFAML tag.
  //
  if ( !rtSOURCE_REM.scan (pkcDFAML_TagPattern, &yName, NULL) )
  {
    throw TNotDfamlFileException ("file doesn't conform DFAML", __FILE__, __LINE__);
  }
  DFA_REMOVE_COMMENTS (rtSOURCE_REM);
  
  //
  //  Reads DESC tag/DESC body/DESC end-tag.
  //
  rtSOURCE_REM.scan (pkcDESC_ElementPattern, &yDescription, NULL);
  DFA_REMOVE_COMMENTS (rtSOURCE_REM);
  
# undef DFA_REMOVE_COMMENTS

}  // readHeader()


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
readTransitionTable (TMatcher& rtSOURCE_REM)
{

# define DFA_REMOVE_COMMENTS(rtREM)                           \
         {                                                    \
           while ( rtREM.scan (pkcCommentTagPattern, NULL) ); \
         }

  typedef
    TMap<TPair, TString>
    TUnresolvedTransitionMap;

  TUnresolvedTransitionMap                            tUnresolvedTransitionMap;
  typename TUnresolvedTransitionMap::const_iterator   I;
  TState                                              tStateIterator;
  TString                                             yInitialState;
  TString                                             yStateEvent;
  TString                                             yStateName;
  TString                                             yStateNext;
  TString                                             yStateType;

  //
  //  Reads TRANSTBL tag/DECLARE end-tag.
  //  The existence and syntax of this tag is verified by external
  //  SGML checking tools.
  //
  tInitialState = 0;
  rtSOURCE_REM.scan (pkcTRANSTBL_TagPattern, &yInitialState, NULL);
  
  //
  //  Dynamicly binds each new state.
  //
  yInitialState.lowercase();
  tStringToStateMap.bind (yInitialState, tInitialState);
  DFA_REMOVE_COMMENTS (rtSOURCE_REM);
  for (tStateIterator = tInitialState;;++tStateIterator)
  {
    yStateType.erase();
    if ( !rtSOURCE_REM.scan (pkcSTATE_TagPattern_1, &yStateName, NULL) )
    {
      if ( !rtSOURCE_REM.scan (pkcSTATE_TagPattern_2, &yStateName, &yStateType, NULL) )
      {
        if ( !rtSOURCE_REM.scan (pkcSTATE_TagPattern_3, &yStateType, &yStateName, NULL) )
        {
          break;
        }
      }
    }

    //
    //  Normalizes name and type, and binds in string to state map.
    //
    yStateName.lowercase();
    yStateType.lowercase();
    tStringToStateMap.bind (yStateName, tStateIterator);
    
    //
    //  If this state is a final state, then insert in final
    //  states set.
    //
    if ( yStateType == "final" )
    {
      tFinalStateSet.insert (tStateIterator);
    }
    
    //
    //  Reads transitions.
    //
    for (;;)
    {
      DFA_REMOVE_COMMENTS (rtSOURCE_REM);
      if ( !rtSOURCE_REM.scan (pkcTRANSIT_ElementPattern_1, &yStateEvent, &yStateNext, NULL) )
      {
        if ( !rtSOURCE_REM.scan (pkcTRANSIT_ElementPattern_2, &yStateNext, &yStateEvent, NULL) )
        {
          break;
        }
      }
      
      //
      //  Inserts the transitions (from state (yStateName) with event
      //  (yStateEvent) to state (yStateNext)) into a temporary map.
      //  This is due to the fact, that the references to next states
      //  can be made before those states were defined.
      //
      yStateEvent.lowercase();
      yStateNext.lowercase();
      tUnresolvedTransitionMap.bind
      (
        std::make_pair (tStateIterator, tStringToEventMap [yStateEvent]) ,
        yStateNext
      );
    }
    rtSOURCE_REM.scan (pkcSTATE_EndTagPattern, NULL);
    DFA_REMOVE_COMMENTS (rtSOURCE_REM);
  }
  rtSOURCE_REM.scan (pkcTRANSTBL_EndTagPattern, NULL);
  DFA_REMOVE_COMMENTS (rtSOURCE_REM);

  //
  //  Resolves next-states names to states.
  // 
  for (I = tUnresolvedTransitionMap.begin(); ( I != tUnresolvedTransitionMap.end() ) ;++I)
  {
    tTransitionMap.bind (I->first, tStringToStateMap [I->second]);
  }

# undef DFA_REMOVE_COMMENTS

}  // readTransitionTable()


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
start (void)
{

  move (tInitialState);
  while (true)
  {
    if ( !rtEventHandler.isEmpty() )
    {
      move (next (rtEventHandler.pop()));
    }
    else
    {
      if ( !TDeterministicFiniteAutomaton<TState, TEvent>::isFinal (current()) )
      {
        throw TIntegrityException ("state is not final", __FILE__, __LINE__);
      }
      break;
    }
  }
  
}  // start()


//
//  S E L E C T O R S
//


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
check (void) const
{

  typename TTransitionMap::const_iterator   I;
  typename TStateSet::const_iterator        J;
  TStateSet                                 tNoNextStateSet;
  TStateSet                                 tSourceStateSet;
  TStateSet                                 tTargetStateSet;

  //
  //  Calculates no-next states.
  //  First, it calculates source and target state set.
  //
  for (I = tTransitionMap.begin(); ( I != tTransitionMap.end() ) ;++I)
  {
    tTargetStateSet.insert (I->second);
    tSourceStateSet.insert (I->first.first);
  }
  tNoNextStateSet.clear();

  //
  //  And then, the set of no-next states is calculated as:
  //
  //    N = T - S
  //
  //  Where N is no-next states set, T is target states set, and S is the source
  //  states set. Symbol '-' means relative complement of S in T.
  //  If T - S is empty, then N = { initial_state }
  //
  std::set_difference ( tTargetStateSet.begin()                                     ,
                        tTargetStateSet.end()                                       ,
                        tSourceStateSet.begin()                                     ,
                        tSourceStateSet.end()                                       ,
                        std::insert_iterator<TStateSet> ( tNoNextStateSet         ,
                                                          tNoNextStateSet.begin() ) );
  if ( tNoNextStateSet.empty() )
  {
    tNoNextStateSet.insert (tInitialState);
  }

  //
  //  If any element in no-next state set, is not included in final state set,
  //  then there is an integrity error.
  //
  for (J = tNoNextStateSet.begin(); ( J != tNoNextStateSet.end() ) ;++J)
  {
    if ( tFinalStateSet.find (*J) == tFinalStateSet.end() )
    {
      throw TIntegrityException ("state is not final and has no next states", __FILE__, __LINE__);
    }
  }
  
}  // check()


template <typename TState, typename TEvent>
inline mpcl::text::TString mpcl::automaton::TStreamableDfa<TState, TEvent>::
eventToString (const TEvent& krtSOURCE_EVENT) const
  throw (TNotFoundException)
{

  typename TStringToEventMap::const_iterator   I     = tStringToEventMap.begin();
  typename TStringToEventMap::const_iterator   ktEnd = tStringToEventMap.end();

  for (; ( I != ktEnd ) ;++I)
  {
    if ( I->second == krtSOURCE_EVENT )
    {
      break;
    }
  }
  if ( I == ktEnd )
  {
    throw TNotFoundException ("event not found", __FILE__, __LINE__);
  }
  return I->first;

}  // eventToString()


template <typename TState, typename TEvent>
inline mpcl::text::TString mpcl::automaton::TStreamableDfa<TState, TEvent>::
stateToString (const TState& krtSOURCE_STATE) const
  throw (TNotFoundException)
{

  typename TStringToStateMap::const_iterator   I     = tStringToStateMap.begin();
  typename TStringToStateMap::const_iterator   ktEnd = tStringToStateMap.end();

  for (; ( I != ktEnd ) ;++I)
  {
    if ( I->second == krtSOURCE_STATE )
    {
      break;
    }
  }
  if ( I == ktEnd )
  {
    throw TNotFoundException ("state not found", __FILE__, __LINE__);
  }
  return I->first;

}  // stateToString()


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
writeHeader (std::basic_ostream<char_type, traits_type>& rtTARGET_OSTREAM) const
{

  if ( !ySystem.empty() )
  {
    rtTARGET_OSTREAM << "<!doctype dfaml system " << ySystem << ">\n";
  }
  else if ( !yPublic.empty() )
  {
    rtTARGET_OSTREAM << "<!doctype dfaml public \"" << yPublic << "\">\n";
  }
  else
  {
    rtTARGET_OSTREAM << "<!doctype dfaml>\n";
  }
  rtTARGET_OSTREAM << "<dfaml name=\"" << yName << "\">\n";
  if ( !yDescription.empty() )
  {
    rtTARGET_OSTREAM << "  <desc>" << yDescription << "</desc>\n";
  }

}  // writeHeader()


template <typename TState, typename TEvent>
inline void mpcl::automaton::TStreamableDfa<TState, TEvent>::
writeTransitionTable (std::basic_ostream<char_type, traits_type>& rtTARGET_OSTREAM) const
{

  typename TTransitionMap::const_iterator     J;
  typename TStringToStateMap::const_iterator  I = tStringToStateMap.begin();

  //
  //  Writes TRANSTBL beginning tag.
  //
  rtTARGET_OSTREAM << "  <transtbl initial=\""
                   << stateToString (tInitialState)
                   << "\">\n";

  //
  //  Iterates over string to state map.
  //
  for (; ( I != tStringToStateMap.end() ) ;++I)
  {
    //
    //  Writes STATE beginning tag.
    //
    rtTARGET_OSTREAM << "    <state name=\"" << I->first;
    if ( tFinalStateSet.find (I->second) != tFinalStateSet.end() )
    {
      rtTARGET_OSTREAM << "\" type=\"final\">\n";
    }
    else
    {
      rtTARGET_OSTREAM << "\">\n";
    }

    //
    //  Writes the corresponding TRANSIT tags.
    //
    for (J = tTransitionMap.begin(); ( J != tTransitionMap.end() ) ;++J)
    {
      //
      //  Compares state value (from string to state list) to state
      //  value (from transition map).
      //
      if ( I->second == J->first.first )
      {
        rtTARGET_OSTREAM << "      <transit event=\"" 
                         << eventToString (J->first.second)
                         << "\" next=\"" 
                         << stateToString (J->second)
                         << "\">\n";
      }
    }
    rtTARGET_OSTREAM << "    </state>\n";
  }
  rtTARGET_OSTREAM << "  </transtbl>\n";
  
}  // writeTransitionTable()


#endif  // not _MPCL_AUTOMATON_STREAMABLE_DFA__

---