94 key =
static_cast<std::size_t
>(
n_states);
101 while (
n_symbols >=
static_cast<unsigned int>(1<<n_log))
106 for (
int i=(1<<n_log); i--; )
107 table[i].fst = table[i].lst = NULL;
108 int mask = (1 << n_log) - 1;
110 for (
int i = 0; i<n_trans; ) {
114 int s = trans[i].symbol;
117 while ((i<n_trans) && (trans[i].symbol == s))
122 while (table[
p].fst != NULL)
141 return (d == NULL) ? 1 : d->n_states;
147 return (d == NULL) ? 0 : d->n_symbols;
153 return (d == NULL) ? 0 : d->n_trans;
159 return (d == NULL) ? 0 : d->max_degree;
165 return (d == NULL) ? 0 : d->final_fst;
171 return (d == NULL) ? 0 : d->final_lst;
177 return ((d != NULL) && (d->n_trans > 0)) ?
184 return ((d != NULL) && (d->n_trans > 0)) ?
191 return (d != NULL) ? d->key : 0;
205 : i_state(i_state0), symbol(symbol0), o_state(o_state0) {}
216 c_trans = &o->
trans[0];
219 c_trans = e_trans = NULL;
227 int mask = (1<<o->
n_log)-1;
234 c_trans = e_trans = NULL;
240 return c_trans < e_trans;
250 return c_trans->i_state;
255 return c_trans->symbol;
260 return c_trans->o_state;
272 c_trans = &o->
trans[0];
275 c_trans = e_trans = NULL;
281 return c_trans < e_trans;
286 int s = c_trans->symbol;
289 }
while ((c_trans < e_trans) && (s == c_trans->symbol));
294 return c_trans->symbol;
298 template<
class Char,
class Traits>
299 std::basic_ostream<Char,Traits>&
301 std::basic_ostringstream<Char,Traits> st;
302 st.copyfmt(os); st.width(0);
303 st <<
"Start state: 0" << std::endl
304 <<
"States: 0..." << d.n_states()-1 << std::endl
306 for (
int s = 0; s < static_cast<int>(d.n_states()); s++) {
310 if (
t.i_state() == s) {
312 st << std::endl <<
"\t";
313 st <<
"[" <<
t.i_state() <<
"]"
314 <<
"- " <<
t.symbol() <<
" >"
315 <<
"[" <<
t.o_state() <<
"] ";
321 st << std::endl <<
"Final states: "
323 <<
"\t[" <<
d.final_fst() <<
"] ... ["
324 <<
d.final_lst()-1 <<
"]"
326 return os << st.str();
348 return !(*
this == d);
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Specification of transition range.
const Transition * lst
Last transition for the symbol.
const Transition * fst
First transition for the symbol.
int final_lst
Last final state.
HashEntry * table
The transition hash table by symbol.
int n_states
Number of states.
unsigned int max_degree
Maximal degree (in-degree and out-degree of any state) and maximal number of transitions per symbol.
int n_trans
Number of transitions.
unsigned int n_symbols
Number of symbols.
virtual ~DFAI(void)
Delete automaton implemenentation.
int final_fst
First final state.
int n_log
Size of table (as binary logarithm)
DFAI(void)
Initialize automaton implementation as empty.
void fill(void)
Fill hash table.
Transition * trans
The transitions.
int val(void) const
Return current symbol.
void operator++(void)
Move iterator to next symbol.
bool operator()(void) const
Test whether iterator still at a symbol.
Symbols(const DFA &d)
Initialize to symbols of DFA d.
Specification of a DFA transition.
Iterator for DFA transitions (sorted by symbols)
int o_state(void) const
Return out-state of current transition.
void operator++(void)
Move iterator to next transition.
bool operator()(void) const
Test whether iterator still at a transition.
Transitions(const DFA &d)
Initialize to all transitions of DFA d.
int i_state(void) const
Return in-state of current transition.
int symbol(void) const
Return symbol of current transition.
Deterministic finite automaton (DFA)
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const DFA &d)
bool operator==(const DFA &d) const
Test whether DFA is equal to d.
int symbol_max(void) const
Return largest symbol in DFA.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
int n_states(void) const
Return the number of states.
int symbol_min(void) const
Return smallest symbol in DFA.
DFA(void)
Initialize for DFA accepting the empty word.
int final_lst(void) const
Return the number of the last final state.
int n_transitions(void) const
Return the number of transitions.
unsigned int n_symbols(void) const
Return the number of symbols.
std::size_t hash(void) const
Return hash key.
bool operator!=(const DFA &d) const
Test whether DFA is not equal to d.
int final_fst(void) const
Return the number of the first final state.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
void rfree(void *p)
Free memory block starting at p.
SharedHandle::Object * object(void) const
Access to the shared object.
#define GECODE_INT_EXPORT
Heap heap
The single global heap.
const int min
Smallest allowed integer value.
const int max
Largest allowed integer value.
Gecode toplevel namespace
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.