Generated on Thu Apr 11 13:59:09 2019 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <sstream>
00035 
00036 namespace Gecode {
00037 
00042   class DFA::DFAI : public SharedHandle::Object {
00043   public:
00045     int n_states;
00047     unsigned int n_symbols;
00049     int n_trans;
00051     unsigned int max_degree;
00053     int final_fst;
00055     int final_lst;
00057     std::size_t key;
00059     Transition* trans;
00061     class HashEntry {
00062     public:
00063       int symbol;            
00064       const Transition* fst; 
00065       const Transition* lst; 
00066     };
00068     HashEntry* table;
00070     int n_log;
00072     void fill(void);
00074     DFAI(int nt);
00076     GECODE_INT_EXPORT DFAI(void);
00078     virtual ~DFAI(void);
00079   };
00080 
00081   forceinline
00082   DFA::DFAI::DFAI(int nt)
00083     : trans(nt == 0 ? NULL : heap.alloc<Transition>(nt)) {}
00084 
00085   forceinline
00086   DFA::DFAI::~DFAI(void) {
00087     if (n_trans > 0)
00088       heap.rfree(trans);
00089     heap.rfree(table);
00090   }
00091 
00092   forceinline void
00093   DFA::DFAI::fill(void) {
00094     key = static_cast<std::size_t>(n_states);
00095     cmb_hash(key, n_trans);
00096     cmb_hash(key, n_symbols);
00097     cmb_hash(key, final_fst);
00098     cmb_hash(key, final_lst);
00099     // Compute smallest logarithm larger than n_symbols
00100     n_log = 1;
00101     while (n_symbols >= static_cast<unsigned int>(1<<n_log))
00102       n_log++;
00103     // Allocate memory
00104     table = heap.alloc<HashEntry>(1<<n_log);
00105     // Initialize table
00106     for (int i=(1<<n_log); i--; )
00107       table[i].fst = table[i].lst = NULL;
00108     int mask = (1 << n_log) - 1;
00109     // Enter transitions to table
00110     for (int i = 0; i<n_trans; ) {
00111       cmb_hash(key, trans[i].i_state);
00112       cmb_hash(key, trans[i].symbol);
00113       cmb_hash(key, trans[i].o_state);
00114       int s = trans[i].symbol;
00115       Transition* fst = &trans[i];
00116       i++;
00117       while ((i<n_trans) && (trans[i].symbol == s))
00118         i++;
00119       Transition* lst = &trans[i];
00120       // Enter with linear collision resolution
00121       int p = s & mask;
00122       while (table[p].fst != NULL)
00123         p = (p+1) & mask;
00124       table[p].symbol = s;
00125       table[p].fst    = fst;
00126       table[p].lst    = lst;
00127     }
00128   }
00129 
00130   forceinline
00131   DFA::DFA(void) {}
00132 
00133 
00134   forceinline
00135   DFA::DFA(const DFA& d)
00136     : SharedHandle(d) {}
00137 
00138   forceinline int
00139   DFA::n_states(void) const {
00140     const DFAI* d = static_cast<DFAI*>(object());
00141     return (d == NULL) ? 1 : d->n_states;
00142   }
00143 
00144   forceinline unsigned int
00145   DFA::n_symbols(void) const {
00146     const DFAI* d = static_cast<DFAI*>(object());
00147     return (d == NULL) ? 0 : d->n_symbols;
00148   }
00149 
00150   forceinline int
00151   DFA::n_transitions(void) const {
00152     const DFAI* d = static_cast<DFAI*>(object());
00153     return (d == NULL) ? 0 : d->n_trans;
00154   }
00155 
00156   forceinline unsigned int
00157   DFA::max_degree(void) const {
00158     const DFAI* d = static_cast<DFAI*>(object());
00159     return (d == NULL) ? 0 : d->max_degree;
00160   }
00161 
00162   forceinline int
00163   DFA::final_fst(void) const {
00164     const DFAI* d = static_cast<DFAI*>(object());
00165     return (d == NULL) ? 0 : d->final_fst;
00166   }
00167 
00168   forceinline int
00169   DFA::final_lst(void) const {
00170     const DFAI* d = static_cast<DFAI*>(object());
00171     return (d == NULL) ? 0 : d->final_lst;
00172   }
00173 
00174   forceinline int
00175   DFA::symbol_min(void) const {
00176     const DFAI* d = static_cast<DFAI*>(object());
00177     return ((d != NULL) && (d->n_trans > 0)) ?
00178       d->trans[0].symbol : Int::Limits::min;
00179   }
00180 
00181   forceinline int
00182   DFA::symbol_max(void) const {
00183     const DFAI* d = static_cast<DFAI*>(object());
00184     return ((d != NULL) && (d->n_trans > 0)) ?
00185       d->trans[d->n_trans-1].symbol : Int::Limits::max;
00186   }
00187 
00188   forceinline std::size_t
00189   DFA::hash(void) const {
00190     const DFAI* d = static_cast<DFAI*>(object());
00191     return (d != NULL) ? d->key : 0;
00192   }
00193 
00194 
00195   /*
00196    * Constructing transitions
00197    *
00198    */
00199 
00200   forceinline
00201   DFA::Transition::Transition(void) {}
00202 
00203   forceinline
00204   DFA::Transition::Transition(int i_state0, int symbol0, int o_state0)
00205     : i_state(i_state0), symbol(symbol0), o_state(o_state0) {}
00206 
00207   /*
00208    * Iterating over all transitions
00209    *
00210    */
00211 
00212   forceinline
00213   DFA::Transitions::Transitions(const DFA& d) {
00214     const DFAI* o = static_cast<DFAI*>(d.object());
00215     if (o != NULL) {
00216       c_trans = &o->trans[0];
00217       e_trans = c_trans+o->n_trans;
00218     } else {
00219       c_trans = e_trans = NULL;
00220     }
00221   }
00222 
00223   forceinline
00224   DFA::Transitions::Transitions(const DFA& d, int n) {
00225     const DFAI* o = static_cast<DFAI*>(d.object());
00226     if (o != NULL) {
00227       int mask = (1<<o->n_log)-1;
00228       int p = n & mask;
00229       while ((o->table[p].fst != NULL) && (o->table[p].symbol != n))
00230         p = (p+1) & mask;
00231       c_trans = o->table[p].fst;
00232       e_trans = o->table[p].lst;
00233     } else {
00234       c_trans = e_trans = NULL;
00235     }
00236   }
00237 
00238   forceinline bool
00239   DFA::Transitions::operator ()(void) const {
00240     return c_trans < e_trans;
00241   }
00242 
00243   forceinline void
00244   DFA::Transitions::operator ++(void) {
00245     c_trans++;
00246   }
00247 
00248   forceinline int
00249   DFA::Transitions::i_state(void) const {
00250     return c_trans->i_state;
00251   }
00252 
00253   forceinline int
00254   DFA::Transitions::symbol(void) const {
00255     return c_trans->symbol;
00256   }
00257 
00258   forceinline int
00259   DFA::Transitions::o_state(void) const {
00260     return c_trans->o_state;
00261   }
00262 
00263   /*
00264    * Iterating over symbols
00265    *
00266    */
00267 
00268   forceinline
00269   DFA::Symbols::Symbols(const DFA& d) {
00270     const DFAI* o = static_cast<DFAI*>(d.object());
00271     if (o != NULL) {
00272       c_trans = &o->trans[0];
00273       e_trans = c_trans+o->n_trans;
00274     } else {
00275       c_trans = e_trans = NULL;
00276     }
00277   }
00278 
00279   forceinline bool
00280   DFA::Symbols::operator ()(void) const {
00281     return c_trans < e_trans;
00282   }
00283 
00284   forceinline void
00285   DFA::Symbols::operator ++(void) {
00286     int s = c_trans->symbol;
00287     do {
00288       c_trans++;
00289     } while ((c_trans < e_trans) && (s == c_trans->symbol));
00290   }
00291 
00292   forceinline int
00293   DFA::Symbols::val(void) const {
00294     return c_trans->symbol;
00295   }
00296 
00297 
00298   template<class Char, class Traits>
00299   std::basic_ostream<Char,Traits>&
00300   operator <<(std::basic_ostream<Char,Traits>& os, const DFA& d) {
00301     std::basic_ostringstream<Char,Traits> st;
00302     st.copyfmt(os); st.width(0);
00303     st << "Start state: 0" << std::endl
00304        << "States:      0..." << d.n_states()-1 << std::endl
00305        << "Transitions:";
00306     for (int s = 0; s < static_cast<int>(d.n_states()); s++) {
00307       DFA::Transitions t(d);
00308       int n = 0;
00309       while (t()) {
00310         if (t.i_state() == s) {
00311           if ((n % 4) == 0)
00312             st << std::endl << "\t";
00313           st << "[" << t.i_state() << "]"
00314              << "- " << t.symbol() << " >"
00315              << "[" << t.o_state() << "]  ";
00316           ++n;
00317         }
00318         ++t;
00319       }
00320     }
00321     st << std::endl << "Final states: "
00322        << std::endl
00323        << "\t[" << d.final_fst() << "] ... ["
00324        << d.final_lst()-1 << "]"
00325        << std::endl;
00326     return os << st.str();
00327   }
00328 
00329   forceinline bool
00330   DFA::operator ==(const DFA& d) const {
00331     if (n_states() != d.n_states())
00332       return false;
00333     if (n_transitions() != d.n_transitions())
00334       return false;
00335     if (n_symbols() != d.n_symbols())
00336       return false;
00337     if (max_degree() != d.max_degree())
00338       return false;
00339     if (final_fst() != d.final_fst())
00340       return false;
00341     if (final_lst() != d.final_lst())
00342       return false;
00343     return equal(d);
00344   }
00345 
00346   forceinline bool
00347   DFA::operator !=(const DFA& d) const {
00348     return !(*this == d);
00349   }
00350 
00351 
00352 }
00353 
00354 
00355 // STATISTICS: int-prop
00356