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