00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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) {
00069 while(first.forward());
00070
00071
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) {
00077 i->second = out.new_state();
00078 out.tag(i->second) = first.aim_tag();
00079 out.final(i->second) = true;
00080 }
00081 }
00082
00083 do {
00084
00085
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();
00095 out.final(i->second) = first.src_final();
00096 }
00097 if (p != DFA::null_state)
00098 out.set_trans(i->second, first.letter(), p);
00099
00100
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
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) {
00150
00151
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) {
00155 i->second = out.new_state();
00156 out.tag(i->second) = first.src_tag();
00157 out.final(i->second) = first.src_final();
00158 }
00159 q = i->second;
00160
00161 do {
00162
00163
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();
00170 out.final(i->second) = first.aim_final();
00171 }
00172
00173
00174 out.set_trans(q, first.letter(), i->second);
00175
00176 q = i->second;
00177 } while (first.forward());
00178
00179 while (!first.forward());
00180 }
00181 return mapping[i];
00182 }
00183
00184 }
00185
00186 #endif
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196