dfa.hpp
Go to the documentation of this file.00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <sstream> 00039 00040 namespace Gecode { 00041 00046 class DFA::DFAI : public SharedHandle::Object { 00047 public: 00049 int n_states; 00051 unsigned int n_symbols; 00053 int n_trans; 00055 unsigned int max_degree; 00057 int final_fst; 00059 int final_lst; 00061 Transition* trans; 00063 class HashEntry { 00064 public: 00065 int symbol; 00066 const Transition* fst; 00067 const Transition* lst; 00068 }; 00070 HashEntry* table; 00072 int n_log; 00074 GECODE_INT_EXPORT void fill(void); 00076 DFAI(int nt); 00078 GECODE_INT_EXPORT DFAI(void); 00080 virtual ~DFAI(void); 00082 GECODE_INT_EXPORT virtual SharedHandle::Object* copy(void) const; 00083 }; 00084 00085 forceinline 00086 DFA::DFAI::DFAI(int nt) 00087 : trans(nt == 0 ? NULL : heap.alloc<Transition>(nt)) {} 00088 00089 forceinline 00090 DFA::DFAI::~DFAI(void) { 00091 if (n_trans > 0) 00092 heap.rfree(trans); 00093 heap.rfree(table); 00094 } 00095 00096 forceinline 00097 DFA::DFA(void) {} 00098 00099 00100 forceinline 00101 DFA::DFA(const DFA& d) 00102 : SharedHandle(d) {} 00103 00104 forceinline int 00105 DFA::n_states(void) const { 00106 const DFAI* d = static_cast<DFAI*>(object()); 00107 return (d == NULL) ? 1 : d->n_states; 00108 } 00109 00110 forceinline unsigned int 00111 DFA::n_symbols(void) const { 00112 const DFAI* d = static_cast<DFAI*>(object()); 00113 return (d == NULL) ? 0 : d->n_symbols; 00114 } 00115 00116 forceinline int 00117 DFA::n_transitions(void) const { 00118 const DFAI* d = static_cast<DFAI*>(object()); 00119 return (d == NULL) ? 0 : d->n_trans; 00120 } 00121 00122 forceinline unsigned int 00123 DFA::max_degree(void) const { 00124 const DFAI* d = static_cast<DFAI*>(object()); 00125 return (d == NULL) ? 0 : d->max_degree; 00126 } 00127 00128 forceinline int 00129 DFA::final_fst(void) const { 00130 const DFAI* d = static_cast<DFAI*>(object()); 00131 return (d == NULL) ? 0 : d->final_fst; 00132 } 00133 00134 forceinline int 00135 DFA::final_lst(void) const { 00136 const DFAI* d = static_cast<DFAI*>(object()); 00137 return (d == NULL) ? 0 : d->final_lst; 00138 } 00139 00140 forceinline int 00141 DFA::symbol_min(void) const { 00142 const DFAI* d = static_cast<DFAI*>(object()); 00143 return ((d != NULL) && (d->n_trans > 0)) ? 00144 d->trans[0].symbol : Int::Limits::min; 00145 } 00146 00147 forceinline int 00148 DFA::symbol_max(void) const { 00149 const DFAI* d = static_cast<DFAI*>(object()); 00150 return ((d != NULL) && (d->n_trans > 0)) ? 00151 d->trans[d->n_trans-1].symbol : Int::Limits::max; 00152 } 00153 00154 00155 00156 /* 00157 * Iterating over all transitions 00158 * 00159 */ 00160 00161 forceinline 00162 DFA::Transitions::Transitions(const DFA& d) { 00163 const DFAI* o = static_cast<DFAI*>(d.object()); 00164 if (o != NULL) { 00165 c_trans = &o->trans[0]; 00166 e_trans = c_trans+o->n_trans; 00167 } else { 00168 c_trans = e_trans = NULL; 00169 } 00170 } 00171 00172 forceinline 00173 DFA::Transitions::Transitions(const DFA& d, int n) { 00174 const DFAI* o = static_cast<DFAI*>(d.object()); 00175 if (o != NULL) { 00176 int mask = (1<<o->n_log)-1; 00177 int p = n & mask; 00178 while ((o->table[p].fst != NULL) && (o->table[p].symbol != n)) 00179 p = (p+1) & mask; 00180 c_trans = o->table[p].fst; 00181 e_trans = o->table[p].lst; 00182 } else { 00183 c_trans = e_trans = NULL; 00184 } 00185 } 00186 00187 forceinline bool 00188 DFA::Transitions::operator ()(void) const { 00189 return c_trans < e_trans; 00190 } 00191 00192 forceinline void 00193 DFA::Transitions::operator ++(void) { 00194 c_trans++; 00195 } 00196 00197 forceinline int 00198 DFA::Transitions::i_state(void) const { 00199 return c_trans->i_state; 00200 } 00201 00202 forceinline int 00203 DFA::Transitions::symbol(void) const { 00204 return c_trans->symbol; 00205 } 00206 00207 forceinline int 00208 DFA::Transitions::o_state(void) const { 00209 return c_trans->o_state; 00210 } 00211 00212 /* 00213 * Iterating over symbols 00214 * 00215 */ 00216 00217 forceinline 00218 DFA::Symbols::Symbols(const DFA& d) { 00219 const DFAI* o = static_cast<DFAI*>(d.object()); 00220 if (o != NULL) { 00221 c_trans = &o->trans[0]; 00222 e_trans = c_trans+o->n_trans; 00223 } else { 00224 c_trans = e_trans = NULL; 00225 } 00226 } 00227 00228 forceinline bool 00229 DFA::Symbols::operator ()(void) const { 00230 return c_trans < e_trans; 00231 } 00232 00233 forceinline void 00234 DFA::Symbols::operator ++(void) { 00235 int s = c_trans->symbol; 00236 do { 00237 c_trans++; 00238 } while ((c_trans < e_trans) && (s == c_trans->symbol)); 00239 } 00240 00241 forceinline int 00242 DFA::Symbols::val(void) const { 00243 return c_trans->symbol; 00244 } 00245 00246 00247 template<class Char, class Traits> 00248 std::basic_ostream<Char,Traits>& 00249 operator <<(std::basic_ostream<Char,Traits>& os, const DFA& d) { 00250 std::basic_ostringstream<Char,Traits> st; 00251 st.copyfmt(os); st.width(0); 00252 st << "Start state: 0" << std::endl 00253 << "States: 0..." << d.n_states()-1 << std::endl 00254 << "Transitions:"; 00255 for (int s = 0; s < static_cast<int>(d.n_states()); s++) { 00256 DFA::Transitions t(d); 00257 int n = 0; 00258 while (t()) { 00259 if (t.i_state() == s) { 00260 if ((n % 4) == 0) 00261 st << std::endl << "\t"; 00262 st << "[" << t.i_state() << "]" 00263 << "- " << t.symbol() << " >" 00264 << "[" << t.o_state() << "] "; 00265 ++n; 00266 } 00267 ++t; 00268 } 00269 } 00270 st << std::endl << "Final states: " 00271 << std::endl 00272 << "\t[" << d.final_fst() << "] ... [" 00273 << d.final_lst()-1 << "]" 00274 << std::endl; 00275 return os << st.str(); 00276 } 00277 00278 } 00279 00280 00281 // STATISTICS: int-prop 00282