ccopy.h

Go to the documentation of this file.
00001 /*
00002  * ASTL - the Automaton Standard Template Library.
00003  * C++ generic components for Finite State Automata handling.
00004  * Copyright (C) 2000-2006 Vincent Le Maout (vincent.lemaout@chello.fr).
00005  * 
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Lesser General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2.1 of the License, or (at your option) any later version.
00010  * 
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Lesser General Public License for more details.
00015  * 
00016  * You should have received a copy of the GNU Lesser General Public
00017  * License along with this library; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019  *
00020  */
00021 
00024 #ifndef ASTL_CCOPY_H
00025 #define ASTL_CCOPY_H
00026 
00027 
00028 #include <iostream>
00029 #include <map>
00030 #include <stack>
00031 #include <string>
00032 
00033 using namespace std;
00034 
00035 namespace astl {
00036 
00059 template <typename DFirstC, typename DFA>
00060 typename DFA::state_type 
00061 trim(DFA &out, DFirstC first, DFirstC last = DFirstC())
00062 {
00063   typedef map<typename DFirstC::state_type,
00064     typename DFA::state_type> mapper;
00065   mapper mapping;
00066   typename DFirstC::state_type i = first.src();
00067 
00068   while (first != last) {     // while not end of range
00069     while(first.forward());   // get down as much as possible
00070 
00071     // copy aim state if final:
00072     typename DFA::state_type p;
00073     if (first.aim_final()) {
00074       typename mapper::iterator i = 
00075         mapping.insert(make_pair(first.aim(), DFA::null_state)).first;
00076       if (i->second == DFA::null_state) {   // inserted ?
00077         i->second = out.new_state();
00078         out.tag(i->second) = first.aim_tag(); // don't reorder (dot)
00079         out.final(i->second) = true;
00080       }
00081     }
00082 
00083     do { // while moving backward (pop) copy current
00084       // transition (q, first.letter(), p) 
00085       // copy source state if needed:
00086       typename mapper::const_iterator dest = mapping.find(first.aim());
00087       if (dest != mapping.end()) p = dest->second;
00088       else p = DFA::null_state;
00089       
00090       if (p != DFA::null_state || first.src_final()) {
00091         typename mapper::iterator i = mapping.insert(make_pair(first.src(), DFA::null_state)).first;
00092         if (i->second == DFA::null_state) {
00093           i->second = out.new_state();
00094           out.tag(i->second) = first.src_tag(); // don't reorder (dot)
00095           out.final(i->second) = first.src_final();
00096         }
00097         if (p != DFA::null_state)       // copy transition ?
00098           out.set_trans(i->second, first.letter(), p);
00099         
00100         // shift (q, first.letter(), p) => (q', first.letter()', q)
00101         p = i->second;
00102       }
00103     } while (! first.forward());
00104   }
00105   return mapping[i];
00106 }
00107 
00130 template <class DFirstC, class DFA>
00131 typename DFA::state_type 
00132 clone(DFA &out, DFirstC first, DFirstC last = DFirstC())
00133 {
00134   if (first == last) return DFA::null_state;
00135 
00136 #ifdef _MSC_VER
00137   // VC++6.0 has a non standard behavior and refuses 'typename' keyword:
00138   typedef DFirstC::state_type cursor_state;
00139   typedef DFA::state_type          dfa_state;
00140 #else
00141   typedef typename DFirstC::state_type cursor_state;
00142   typedef typename DFA::state_type          dfa_state;
00143 #endif
00144 
00145   map<cursor_state, dfa_state> mapping;
00146   cursor_state i = first.src();
00147   dfa_state q;
00148 
00149   while (first != last) {     // while not end of range
00150 
00151     // copy source state if needed:
00152     typename map<cursor_state, dfa_state>::iterator i 
00153       = mapping.insert(make_pair(first.src(), DFA::null_state)).first;
00154     if (i->second == DFA::null_state) {  // inserted ?
00155       i->second = out.new_state();
00156       out.tag(i->second) = first.src_tag(); // don't reorder (dot)
00157       out.final(i->second) = first.src_final();
00158     }
00159     q = i->second;
00160 
00161     do {                      // while moving forward
00162       // copy current transition (q, first.letter(), p)
00163       // copy aim state if needed:
00164       typename map<cursor_state, dfa_state>::iterator i 
00165         = mapping.insert(make_pair(first.aim(), DFA::null_state)).first;
00166 
00167       if (i->second == DFA::null_state) {
00168         i->second = out.new_state();
00169         out.tag(i->second) = first.aim_tag(); // don't reorder
00170         out.final(i->second) = first.aim_final();
00171       }
00172 
00173       // copy transition:
00174       out.set_trans(q, first.letter(), i->second);
00175       // shift (q, first.letter(), p) => (p, first.letter()', p')
00176       q = i->second;
00177     } while (first.forward());
00178 
00179     while (!first.forward());   // pop
00180   }
00181   return mapping[i];
00182 }
00183 
00184 } // namespace astl
00185 
00186 #endif      
00187 
00188 
00189 
00190 
00191 
00192 
00193 
00194 
00195 
00196 

Generated on Sun Mar 8 02:41:30 2009 for ASTL by  doxygen 1.5.7.1