00001
00002
00003
00004
00005
00006
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
00024
00025
00026
00027 struct FSAEdge
00028 {
00029
00030 FSAEdge( ) : target(-1), label(0) { }
00031
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
00057
00058
00059
00060 struct FSAState
00061 {
00062 typedef FSAEdge edge_type;
00063
00064 FSAState( int s ) : theState(s) { }
00065 FSAState( ) : theState(0) { }
00066
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
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
00101
00102
00103
00104 class FSARep : public RefCounter
00105 {
00106 friend class FSA;
00107
00108 typedef FSAState::edge_type edge_type;
00109
00111
00112
00113
00115
00116 private:
00117
00118 FSARep( );
00119
00120
00122
00123
00124
00126 public:
00127
00128
00129 FSARep* clone( ) const { return new FSARep( *this ); }
00130
00132
00133
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
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
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
00216
00218
00219 private:
00220
00221
00222
00223 map< int , FSAState > theStates;
00224
00225
00226 int maxState;
00227
00228 set< int > initStates;
00229
00230 set< int > termStates;
00231
00232 };
00233
00235 void reducePath( list< FSAEdge >& path , int init_state );
00236
00237
00238 #endif
00239