nfa.h

/***************************************************************************
                          nfa.h  -  description
                             -------------------
    begin                : Wed Nov 26 2003
    copyright            : (C) 2003 by Jacques Gasselin de Richebourg
    email                : jacquesgasselin@hotmail.com
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU Lesser General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This library 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     *
 *   Lesser General Public License for more details.                       *
 *                                                                         *
 *   You should have received a copy of the GNU Lesser General Public      *
 *   License along with this library; if not, write to the Free Software   *
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA *
 *                                                                         *
 ***************************************************************************/

#ifndef NFA_H
#define NFA_H

#include <list>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>

void NFAunitTest(void);
  
template <class InType>
class FAState;

template <class InType>
class NFA;

template <class InType>
class FATraversalPointer
{
   typedef FAState<InType> stateType;

   stateType* atState;
   bool dead;
   
   public:


   FATraversalPointer(stateType* beginState)
   :atState(beginState),dead(false) {};

   FATraversalPointer(const FATraversalPointer& _fa )
   :atState(_fa.atState),dead(_fa.dead) {};

   ~FATraversalPointer(){};

   bool operator ==( const FATraversalPointer& _fa )
   {
      if( atState == _fa.atState )
         return true;
      return false;
   }
   
   void traverse( const InType& in )
   {
      atState->traverse( *this, in );
   }

   bool isDead() { return dead; }
   
   void kill() { dead = true; }
};

template <class InType>
class FAEdge
{
   InType acceptedInput;

   typedef FAState<InType> stateType;

   stateType* to;
   
   public:
   
   FAEdge(const InType& _in, stateType* const _to = NULL)
   :acceptedInput(_in), to(_to) {}
   
   ~FAEdge(){};

   void setAcceptedInput( const InType& in )
   {
      acceptedInput = in;
   }

   bool canTraverseAlong( const InType& in )
   {
      if(acceptedInput == in)
         return true;
      else
         return false;
   }

   void connectTo(stateType* const _to)
   { to = _to; }
   
   stateType* getDesination() { return to; }
         
};

template <class InType>
class FAState
{
   typedef std::vector< FAEdge<InType> * > EdgeVectorType;
   typedef FATraversalPointer<InType> TraversalPtr;


   EdgeVectorType edgeVector;

   public:                  
   
   FAState(NFA<InType>* const pa, bool _goal = false )
   :parentAutomata( pa ),goalState(_goal) { edgeVector.clear(); }
   
   virtual ~FAState()
   {
      typename EdgeVectorType::iterator li = edgeVector.begin();
      typename EdgeVectorType::iterator end = edgeVector.end();

      while( li != end )
      {
         delete (*li);
         ++li;
      }
      
      edgeVector.clear();
   };

   virtual void traverse(  TraversalPtr& ptr, const InType& in )
   {
      typename EdgeVectorType::iterator li = edgeVector.begin();
      typename EdgeVectorType::iterator end = edgeVector.end();

      bool accepted = false;
      
      while( li != end )
      {
         if( (*li)->canTraverseAlong( in ) )  //generate offspring
         {
            parentAutomata->addTraversalPtr( TraversalPtr( (*li)->getDesination() ) );
            accepted = true;
         }
         ++li;
      };

      // the pointer goes dead
      if( !accepted )
      {
         if(goalState)
         { // dead pointers here satisfy the goal
            parentAutomata->setGoal();
         }
      }

      ptr.kill();
   }

   FAEdge<InType>* addEdge( const InType& _in, int _stateIndex )
   {
      FAEdge<InType>* temp = new FAEdge<InType>( _in, parentAutomata->getState(_stateIndex) ); 
      edgeVector.push_back( temp );
      return temp;
   }

   FAEdge<InType>* addEdge( const InType& _in )
   {
      FAEdge<InType>* temp = new FAEdge<InType>( _in, NULL );
      edgeVector.push_back( temp );
      return temp;
   }

   FAEdge<InType>* const getEdge(unsigned index )
   {
      return edgeVector[index];
   }

   FAEdge<InType>* const operator [](unsigned index)
   {
      return edgeVector[index];
   }

   void setGoalState( void )
   { goalState = true; }
   
   private:

   NFA<InType>* parentAutomata;
   bool goalState;


};

template <class InType>
class NFA
{
   typedef FATraversalPointer<InType> TraversalPtr;
   typedef std::list<TraversalPtr > TraversalListType;
   typedef FAState<InType> StateType;
   typedef std::vector<StateType* > StateListType;

   bool goalReached;
   int token;
   TraversalListType travPtrList;
   TraversalListType waitingTravPtrList;
   
   public:

   NFA(int t = 0)
   :goalReached(false),token(t)
   { }
   
   virtual ~NFA()
   {
      typename StateListType::iterator li = stateList.begin();
      typename StateListType::iterator end = stateList.end();

      while( li != end )
      {
         delete (*li);
         ++li;
      };

      stateList.clear();
      travPtrList.clear();
   }

   virtual const int getToken( void )
   {
      unsetGoal();
      return token;
   }

   virtual void setToken( int _t )
   {
      token = _t;
   }

   virtual bool scanInput(const InType& t)
   {
      travPtrList.push_back( TraversalPtr( *(stateList.begin()) ) );
      //add a new empty pointer each round
      
      typename TraversalListType::iterator li = waitingTravPtrList.begin();
      typename TraversalListType::iterator end = waitingTravPtrList.end();

      while( li != end )
      {
         travPtrList.push_back( *li );
         ++li;
      };
      //copy over the waiting pointers
      waitingTravPtrList.clear();

      li = travPtrList.begin();
      end = travPtrList.end();

      while( li != end )
      {
         li->traverse( t );
         ++li;
      };
      //traverse all living pointers

      li = travPtrList.begin();
      end = travPtrList.end();

      while( li != end )
      {
         if( !li->isDead() )
            waitingTravPtrList.push_back( *li );
         ++li;
      };
      //make all living pointers wait, and kill the rest
      
      travPtrList.clear();
      
      return goalReached;
   }

   virtual void addTraversalPtr( const TraversalPtr& ptr )
   {
      waitingTravPtrList.push_back( ptr );
   }
   
   virtual void addState( void )
   {
      stateList.push_back( new StateType(this) );
   }

   virtual StateType* const getState( unsigned index )
   {
      while( index >= stateList.size() )
         addState();
      
      return stateList[index];
   }

   StateType* const operator []( unsigned index)
   {
      while( index >= stateList.size() )
         addState();

      return stateList[index];
   }
   
   virtual void setGoal( void )
   { goalReached = true; }

   protected:


   virtual void unsetGoal( void )
   { goalReached = false; }


   private:

   StateListType stateList;
   
};
       

#endif

---