Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
dfa.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <sstream>
39 
40 namespace Gecode {
41 
47  public:
49  int n_states;
51  unsigned int n_symbols;
53  int n_trans;
55  unsigned int max_degree;
57  int final_fst;
59  int final_lst;
61  std::size_t key;
65  class HashEntry {
66  public:
67  int symbol;
68  const Transition* fst;
69  const Transition* lst;
70  };
74  int n_log;
76  void fill(void);
78  DFAI(int nt);
80  GECODE_INT_EXPORT DFAI(void);
82  virtual ~DFAI(void);
83  };
84 
87  : trans(nt == 0 ? NULL : heap.alloc<Transition>(nt)) {}
88 
91  if (n_trans > 0)
92  heap.rfree(trans);
93  heap.rfree(table);
94  }
95 
96  forceinline void
98  key = static_cast<std::size_t>(n_states);
103  // Compute smallest logarithm larger than n_symbols
104  n_log = 1;
105  while (n_symbols >= static_cast<unsigned int>(1<<n_log))
106  n_log++;
107  // Allocate memory
108  table = heap.alloc<HashEntry>(1<<n_log);
109  // Initialize table
110  for (int i=(1<<n_log); i--; )
111  table[i].fst = table[i].lst = NULL;
112  int mask = (1 << n_log) - 1;
113  // Enter transitions to table
114  for (int i = 0; i<n_trans; ) {
115  cmb_hash(key, trans[i].i_state);
116  cmb_hash(key, trans[i].symbol);
117  cmb_hash(key, trans[i].o_state);
118  int s = trans[i].symbol;
119  Transition* fst = &trans[i];
120  i++;
121  while ((i<n_trans) && (trans[i].symbol == s))
122  i++;
123  Transition* lst = &trans[i];
124  // Enter with linear collision resolution
125  int p = s & mask;
126  while (table[p].fst != NULL)
127  p = (p+1) & mask;
128  table[p].symbol = s;
129  table[p].fst = fst;
130  table[p].lst = lst;
131  }
132  }
133 
135  DFA::DFA(void) {}
136 
137 
139  DFA::DFA(const DFA& d)
140  : SharedHandle(d) {}
141 
142  forceinline int
143  DFA::n_states(void) const {
144  const DFAI* d = static_cast<DFAI*>(object());
145  return (d == NULL) ? 1 : d->n_states;
146  }
147 
148  forceinline unsigned int
149  DFA::n_symbols(void) const {
150  const DFAI* d = static_cast<DFAI*>(object());
151  return (d == NULL) ? 0 : d->n_symbols;
152  }
153 
154  forceinline int
155  DFA::n_transitions(void) const {
156  const DFAI* d = static_cast<DFAI*>(object());
157  return (d == NULL) ? 0 : d->n_trans;
158  }
159 
160  forceinline unsigned int
161  DFA::max_degree(void) const {
162  const DFAI* d = static_cast<DFAI*>(object());
163  return (d == NULL) ? 0 : d->max_degree;
164  }
165 
166  forceinline int
167  DFA::final_fst(void) const {
168  const DFAI* d = static_cast<DFAI*>(object());
169  return (d == NULL) ? 0 : d->final_fst;
170  }
171 
172  forceinline int
173  DFA::final_lst(void) const {
174  const DFAI* d = static_cast<DFAI*>(object());
175  return (d == NULL) ? 0 : d->final_lst;
176  }
177 
178  forceinline int
179  DFA::symbol_min(void) const {
180  const DFAI* d = static_cast<DFAI*>(object());
181  return ((d != NULL) && (d->n_trans > 0)) ?
182  d->trans[0].symbol : Int::Limits::min;
183  }
184 
185  forceinline int
186  DFA::symbol_max(void) const {
187  const DFAI* d = static_cast<DFAI*>(object());
188  return ((d != NULL) && (d->n_trans > 0)) ?
190  }
191 
192  forceinline std::size_t
193  DFA::hash(void) const {
194  const DFAI* d = static_cast<DFAI*>(object());
195  return (d != NULL) ? d->key : 0;
196  }
197 
198 
199  /*
200  * Constructing transitions
201  *
202  */
203 
206 
208  DFA::Transition::Transition(int i_state0, int symbol0, int o_state0)
209  : i_state(i_state0), symbol(symbol0), o_state(o_state0) {}
210 
211  /*
212  * Iterating over all transitions
213  *
214  */
215 
218  const DFAI* o = static_cast<DFAI*>(d.object());
219  if (o != NULL) {
220  c_trans = &o->trans[0];
221  e_trans = c_trans+o->n_trans;
222  } else {
223  c_trans = e_trans = NULL;
224  }
225  }
226 
229  const DFAI* o = static_cast<DFAI*>(d.object());
230  if (o != NULL) {
231  int mask = (1<<o->n_log)-1;
232  int p = n & mask;
233  while ((o->table[p].fst != NULL) && (o->table[p].symbol != n))
234  p = (p+1) & mask;
235  c_trans = o->table[p].fst;
236  e_trans = o->table[p].lst;
237  } else {
238  c_trans = e_trans = NULL;
239  }
240  }
241 
242  forceinline bool
244  return c_trans < e_trans;
245  }
246 
247  forceinline void
249  c_trans++;
250  }
251 
252  forceinline int
254  return c_trans->i_state;
255  }
256 
257  forceinline int
259  return c_trans->symbol;
260  }
261 
262  forceinline int
264  return c_trans->o_state;
265  }
266 
267  /*
268  * Iterating over symbols
269  *
270  */
271 
274  const DFAI* o = static_cast<DFAI*>(d.object());
275  if (o != NULL) {
276  c_trans = &o->trans[0];
277  e_trans = c_trans+o->n_trans;
278  } else {
279  c_trans = e_trans = NULL;
280  }
281  }
282 
283  forceinline bool
285  return c_trans < e_trans;
286  }
287 
288  forceinline void
290  int s = c_trans->symbol;
291  do {
292  c_trans++;
293  } while ((c_trans < e_trans) && (s == c_trans->symbol));
294  }
295 
296  forceinline int
297  DFA::Symbols::val(void) const {
298  return c_trans->symbol;
299  }
300 
301 
302  template<class Char, class Traits>
303  std::basic_ostream<Char,Traits>&
304  operator <<(std::basic_ostream<Char,Traits>& os, const DFA& d) {
305  std::basic_ostringstream<Char,Traits> st;
306  st.copyfmt(os); st.width(0);
307  st << "Start state: 0" << std::endl
308  << "States: 0..." << d.n_states()-1 << std::endl
309  << "Transitions:";
310  for (int s = 0; s < static_cast<int>(d.n_states()); s++) {
312  int n = 0;
313  while (t()) {
314  if (t.i_state() == s) {
315  if ((n % 4) == 0)
316  st << std::endl << "\t";
317  st << "[" << t.i_state() << "]"
318  << "- " << t.symbol() << " >"
319  << "[" << t.o_state() << "] ";
320  ++n;
321  }
322  ++t;
323  }
324  }
325  st << std::endl << "Final states: "
326  << std::endl
327  << "\t[" << d.final_fst() << "] ... ["
328  << d.final_lst()-1 << "]"
329  << std::endl;
330  return os << st.str();
331  }
332 
333  forceinline bool
334  DFA::operator ==(const DFA& d) const {
335  if (n_states() != d.n_states())
336  return false;
337  if (n_transitions() != d.n_transitions())
338  return false;
339  if (n_symbols() != d.n_symbols())
340  return false;
341  if (max_degree() != d.max_degree())
342  return false;
343  if (final_fst() != d.final_fst())
344  return false;
345  if (final_lst() != d.final_lst())
346  return false;
347  return equal(d);
348  }
349 
350  forceinline bool
351  DFA::operator !=(const DFA& d) const {
352  return !(*this == d);
353  }
354 
355 
356 }
357 
358 
359 // STATISTICS: int-prop
360 
Transitions(const DFA &d)
Initialize to all transitions of DFA d.
Definition: dfa.hpp:217
int i_state(void) const
Return in-state of current transition.
Definition: dfa.hpp:253
int symbol
symbol
Definition: int.hh:2039
NodeType t
Type of node.
Definition: bool-expr.cpp:234
int n_trans
Number of transitions.
Definition: dfa.hpp:53
int final_fst
First final state.
Definition: dfa.hpp:57
int final_fst(void) const
Return the number of the first final state.
Definition: dfa.hpp:167
The shared handle.
void cmb_hash(std::size_t &seed, int h)
Combine hash value h into seed.
Definition: hash.hpp:56
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
Symbols(const DFA &d)
Initialize to symbols of DFA d.
Definition: dfa.hpp:273
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:127
std::size_t hash(void) const
Return hash key.
Definition: dfa.hpp:193
void operator++(void)
Move iterator to next transition.
Definition: dfa.hpp:248
std::size_t key
Hash key.
Definition: dfa.hpp:61
#define forceinline
Definition: config.hpp:182
const int max
Largest allowed integer value.
Definition: int.hh:116
bool operator()(void) const
Test whether iterator still at a transition.
Definition: dfa.hpp:243
const int min
Smallest allowed integer value.
Definition: int.hh:118
Gecode::IntSet d(v, 7)
Specification of transition range.
Definition: dfa.hpp:65
Transition * trans
The transitions.
Definition: dfa.hpp:63
const Transition * fst
First transition for the symbol.
Definition: dfa.hpp:68
Deterministic finite automaton (DFA)
Definition: int.hh:2027
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:435
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int final_lst
Last final state.
Definition: dfa.hpp:59
bool operator!=(const DFA &d) const
Test whether DFA is not equal to d.
Definition: dfa.hpp:351
SharedHandle::Object * object(void) const
Access to the shared object.
virtual ~DFAI(void)
Delete automaton implemenentation.
Definition: dfa.hpp:90
int n_transitions(void) const
Return the number of transitions.
Definition: dfa.hpp:155
Specification of a DFA transition.
Definition: int.hh:2036
int symbol_max(void) const
Return largest symbol in DFA.
Definition: dfa.hpp:186
unsigned int n_symbols
Number of symbols.
Definition: dfa.hpp:51
bool operator==(const DFA &d) const
Test whether DFA is equal to d.
Definition: dfa.hpp:334
DFAI(void)
Initialize automaton implementation as empty.
DFA(void)
Initialize for DFA accepting the empty word.
Definition: dfa.hpp:135
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition: dfa.hpp:161
Heap heap
The single global heap.
Definition: heap.cpp:48
HashEntry * table
The transition hash table by symbol.
Definition: dfa.hpp:72
void fill(void)
Fill hash table.
Definition: dfa.hpp:97
Data stored for a DFA.
Definition: dfa.hpp:46
const Transition * lst
Last transition for the symbol.
Definition: dfa.hpp:69
Iterator for DFA transitions (sorted by symbols)
Definition: int.hh:2047
void operator++(void)
Move iterator to next symbol.
Definition: dfa.hpp:289
bool operator()(void) const
Test whether iterator still at a symbol.
Definition: dfa.hpp:284
int n_states
Number of states.
Definition: dfa.hpp:49
int n_states(void) const
Return the number of states.
Definition: dfa.hpp:143
int val(void) const
Return current symbol.
Definition: dfa.hpp:297
Gecode toplevel namespace
int symbol_min(void) const
Return smallest symbol in DFA.
Definition: dfa.hpp:179
int n_log
Size of table (as binary logarithm)
Definition: dfa.hpp:74
int final_lst(void) const
Return the number of the last final state.
Definition: dfa.hpp:173
#define GECODE_INT_EXPORT
Definition: int.hh:81
unsigned int n_symbols(void) const
Return the number of symbols.
Definition: dfa.hpp:149
int symbol(void) const
Return symbol of current transition.
Definition: dfa.hpp:258
int o_state(void) const
Return out-state of current transition.
Definition: dfa.hpp:263
unsigned int max_degree
Maximal degree (in-degree and out-degree of any state) and maximal number of transitions per symbol...
Definition: dfa.hpp:55