FSARep.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class FSARep
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _FSARep_h_
00010 #define _FSARep_h_
00011 
00012 
00013 #include "RefCounter.h"
00014 
00015 #include "map"
00016 #include "set"
00017 #include "list"
00018 #include "vector"
00019 using namespace std;
00020 
00021 
00022 //---------------------------------------------------------------------------//
00023 //-------------------------------- FSAEdge ----------------------------------//
00024 //---------------------------------------------------------------------------//
00025 
00026 
00027 struct FSAEdge 
00028 {
00029 
00030   FSAEdge( ) : target(-1), label(0) { }
00031   // dummy constructor, not to be used, required for STL::map
00032 
00033   FSAEdge( int t , int l ) : target(t), label(l) { }
00034 
00035   bool operator ==( const FSAEdge& e ) const {
00036     return target==e.target && label==e.label;
00037   }
00038 
00039   bool operator < ( const FSAEdge& e ) const {
00040     if( label<e.label )
00041       return true;
00042     if( label>e.label )
00043       return false;
00044 
00045     if( target<e.target )
00046       return true;
00047     return false;
00048   }
00049 
00050   int target;
00051   int label;
00052 };
00053 
00054 
00055 //---------------------------------------------------------------------------//
00056 //------------------------------- FSAState ----------------------------------//
00057 //---------------------------------------------------------------------------//
00058 
00059 
00060 struct FSAState 
00061 {
00062   typedef FSAEdge edge_type;
00063   
00064   FSAState( int s ) : theState(s) { }
00065   FSAState( ) : theState(0) { }
00066   // doomy constructor for class map
00067   
00068   bool operator== ( const FSAState& s ) const { 
00069     return theState==s.theState; 
00070   }
00071   bool operator< ( const FSAState& s ) const { 
00072     return theState<s.theState; 
00073   }
00074 
00075   set< edge_type > in;
00076   set< edge_type > out;
00077   int theState;
00078 };
00079 
00080 
00081 //---------------------------------------------------------------------------//
00082 //------------------------------- FSAState ----------------------------------//
00083 //---------------------------------------------------------------------------//
00084 
00085 
00086 struct FoldDetails
00087 {
00088         FoldDetails( int b , int l , int n , const FSAState& s1 , const FSAState& s2 ) :
00089                 base(b), label(l), state_num( n ), state1(s1), state2(s2) { }
00090 
00091         int base;
00092         int label;
00093         int state_num;
00094         FSAState state1;
00095         FSAState state2;
00096 };
00097 
00098 
00099 //---------------------------------------------------------------------------//
00100 //-------------------------------- FSARep -----------------------------------//
00101 //---------------------------------------------------------------------------//
00102 
00103 
00104 class FSARep : public RefCounter
00105 {
00106   friend class FSA;
00107 
00108   typedef FSAState::edge_type edge_type;
00109 
00111   //                                                     //
00112   //  Constructors                                       //
00113   //                                                     //
00115 
00116  private:
00117 
00118   FSARep( );
00119 
00120 
00122   //                                                     //
00123   //  Accessors:                                         //
00124   //                                                     //
00126 public:
00127 
00128   
00129   FSARep* clone( ) const { return new FSARep( *this ); }
00130 
00132   //                                                     //
00133   //  Subgroup graph functions:                          //
00134   //                                                     //
00136 public:
00137 
00139   void fold( const set< int >* candidates = NULL ,  list< FoldDetails >* details = NULL );
00140   
00142   void pinch( int state1 , int state2 );
00143   
00145   void unfold( const list< FoldDetails >& details );
00146   
00148   void liftup( const list< FoldDetails >& details , list< FSAEdge >& path , int init_state );
00149   
00151   //                                                     //
00152   //  Adding and removing elements                       //
00153   //                                                     //
00155 
00156 public:
00158   int    newState( );
00160   void eraseState( int state );
00162   void   newEdge( int state1 , int state2 , int label );
00164   void eraseEdge( int state1 , int state2 , int label );
00165   
00167   template< class ConstIntIterator > void addLoop( int vert  , ConstIntIterator F , ConstIntIterator L ) {
00168     if( F==L ) return;
00169     int cur_vert = vert;
00170     ConstIntIterator L2 = L;
00171     --L2;
00172     for( ConstIntIterator IT=F ; IT!=L2 ; ++IT ) {
00173       int new_vert = newState( );
00174       newEdge( cur_vert , new_vert ,  *IT );
00175       newEdge( new_vert , cur_vert , -*IT );
00176       cur_vert = new_vert;
00177     }
00178     
00179     newEdge( cur_vert , vert ,  *L2 );
00180     newEdge( vert , cur_vert , -*L2 );
00181   }
00182 
00184   template< class ConstIntIterator > void addRay ( int vert , ConstIntIterator F , ConstIntIterator L ) {
00185     int cur_vert = vert;
00186     for( ConstIntIterator IT=F ; IT!=L ; ++IT ) {
00187       int new_vert = newState( );
00188       newEdge( cur_vert , new_vert ,  *IT );
00189       newEdge( new_vert , cur_vert , -*IT );
00190       cur_vert = new_vert;
00191     }
00192   }
00193   
00195   void addFSA ( int vert1 , int vert2 , const FSARep& fsa ) { exit( 1 ); }
00196 
00197   const map< int , FSAState >& getStates( ) const { return theStates; }
00198         map< int , FSAState >& getStates( )       { return theStates; }
00199 
00201   //                                                     //
00202   //  Initial and terminal states:                       //
00203   //                                                     //
00205 public:
00206   void makeInitial    ( int s ) { initStates.insert( s ); }
00207   void makeTerminal   ( int s ) { termStates.insert( s ); }
00208   void makeNonInitial ( int s ) { initStates.erase ( s ); }
00209   void makeNonTerminal( int s ) { termStates.erase ( s ); }
00210   const set< int >& getInitStates( ) const { return initStates; }
00211   const set< int >& getTermStates( ) const { return termStates; }
00212 
00214   //                                                     //
00215   //  Data members                                       //
00216   //                                                     //
00218   
00219 private:
00220 
00221   // friend class AdvCPAlgorithm;
00222   
00223   map< int , FSAState > theStates;
00224   // here argument (int) coincide with FSAState.theState
00225 
00226   int maxState;
00227   
00228   set< int > initStates;
00229   // the set of initial states
00230   set< int > termStates;
00231   // the set of terminal states
00232 };
00233 
00235 void reducePath( list< FSAEdge >& path , int init_state );
00236 
00237 
00238 #endif
00239 

Generated on Sun Dec 3 10:58:57 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6