Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.1
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: 2013-03-07 17:39:13 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13458 $
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;
63  class HashEntry {
64  public:
65  int symbol;
66  const Transition* fst;
67  const Transition* lst;
68  };
72  int n_log;
74  GECODE_INT_EXPORT void fill(void);
76  DFAI(int nt);
78  GECODE_INT_EXPORT DFAI(void);
80  virtual ~DFAI(void);
82  GECODE_INT_EXPORT virtual SharedHandle::Object* copy(void) const;
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 
97  DFA::DFA(void) {}
98 
99 
101  DFA::DFA(const DFA& d)
102  : SharedHandle(d) {}
103 
104  forceinline int
105  DFA::n_states(void) const {
106  const DFAI* d = static_cast<DFAI*>(object());
107  return (d == NULL) ? 1 : d->n_states;
108  }
109 
110  forceinline unsigned int
111  DFA::n_symbols(void) const {
112  const DFAI* d = static_cast<DFAI*>(object());
113  return (d == NULL) ? 0 : d->n_symbols;
114  }
115 
116  forceinline int
117  DFA::n_transitions(void) const {
118  const DFAI* d = static_cast<DFAI*>(object());
119  return (d == NULL) ? 0 : d->n_trans;
120  }
121 
122  forceinline unsigned int
123  DFA::max_degree(void) const {
124  const DFAI* d = static_cast<DFAI*>(object());
125  return (d == NULL) ? 0 : d->max_degree;
126  }
127 
128  forceinline int
129  DFA::final_fst(void) const {
130  const DFAI* d = static_cast<DFAI*>(object());
131  return (d == NULL) ? 0 : d->final_fst;
132  }
133 
134  forceinline int
135  DFA::final_lst(void) const {
136  const DFAI* d = static_cast<DFAI*>(object());
137  return (d == NULL) ? 0 : d->final_lst;
138  }
139 
140  forceinline int
141  DFA::symbol_min(void) const {
142  const DFAI* d = static_cast<DFAI*>(object());
143  return ((d != NULL) && (d->n_trans > 0)) ?
144  d->trans[0].symbol : Int::Limits::min;
145  }
146 
147  forceinline int
148  DFA::symbol_max(void) const {
149  const DFAI* d = static_cast<DFAI*>(object());
150  return ((d != NULL) && (d->n_trans > 0)) ?
152  }
153 
154 
155  /*
156  * Constructing transitions
157  *
158  */
159 
162 
164  DFA::Transition::Transition(int i_state0, int symbol0, int o_state0)
165  : i_state(i_state0), symbol(symbol0), o_state(o_state0) {}
166 
167  /*
168  * Iterating over all transitions
169  *
170  */
171 
174  const DFAI* o = static_cast<DFAI*>(d.object());
175  if (o != NULL) {
176  c_trans = &o->trans[0];
177  e_trans = c_trans+o->n_trans;
178  } else {
179  c_trans = e_trans = NULL;
180  }
181  }
182 
185  const DFAI* o = static_cast<DFAI*>(d.object());
186  if (o != NULL) {
187  int mask = (1<<o->n_log)-1;
188  int p = n & mask;
189  while ((o->table[p].fst != NULL) && (o->table[p].symbol != n))
190  p = (p+1) & mask;
191  c_trans = o->table[p].fst;
192  e_trans = o->table[p].lst;
193  } else {
194  c_trans = e_trans = NULL;
195  }
196  }
197 
198  forceinline bool
200  return c_trans < e_trans;
201  }
202 
203  forceinline void
205  c_trans++;
206  }
207 
208  forceinline int
210  return c_trans->i_state;
211  }
212 
213  forceinline int
215  return c_trans->symbol;
216  }
217 
218  forceinline int
220  return c_trans->o_state;
221  }
222 
223  /*
224  * Iterating over symbols
225  *
226  */
227 
230  const DFAI* o = static_cast<DFAI*>(d.object());
231  if (o != NULL) {
232  c_trans = &o->trans[0];
233  e_trans = c_trans+o->n_trans;
234  } else {
235  c_trans = e_trans = NULL;
236  }
237  }
238 
239  forceinline bool
241  return c_trans < e_trans;
242  }
243 
244  forceinline void
246  int s = c_trans->symbol;
247  do {
248  c_trans++;
249  } while ((c_trans < e_trans) && (s == c_trans->symbol));
250  }
251 
252  forceinline int
253  DFA::Symbols::val(void) const {
254  return c_trans->symbol;
255  }
256 
257 
258  template<class Char, class Traits>
259  std::basic_ostream<Char,Traits>&
260  operator <<(std::basic_ostream<Char,Traits>& os, const DFA& d) {
261  std::basic_ostringstream<Char,Traits> st;
262  st.copyfmt(os); st.width(0);
263  st << "Start state: 0" << std::endl
264  << "States: 0..." << d.n_states()-1 << std::endl
265  << "Transitions:";
266  for (int s = 0; s < static_cast<int>(d.n_states()); s++) {
268  int n = 0;
269  while (t()) {
270  if (t.i_state() == s) {
271  if ((n % 4) == 0)
272  st << std::endl << "\t";
273  st << "[" << t.i_state() << "]"
274  << "- " << t.symbol() << " >"
275  << "[" << t.o_state() << "] ";
276  ++n;
277  }
278  ++t;
279  }
280  }
281  st << std::endl << "Final states: "
282  << std::endl
283  << "\t[" << d.final_fst() << "] ... ["
284  << d.final_lst()-1 << "]"
285  << std::endl;
286  return os << st.str();
287  }
288 
289 }
290 
291 
292 // STATISTICS: int-prop
293 
Transitions(const DFA &d)
Initialize to all transitions of DFA d.
Definition: dfa.hpp:173
int symbol
symbol
Definition: int.hh:1890
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
The shared handle.
Definition: core.hpp:79
int final_fst(void) const
Return the number of the first final state.
Definition: dfa.hpp:129
int o_state(void) const
Return out-state of current transition.
Definition: dfa.hpp:219
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
int final_lst(void) const
Return the number of the last final state.
Definition: dfa.hpp:135
Symbols(const DFA &d)
Initialize to symbols of DFA d.
Definition: dfa.hpp:229
bool operator()(void) const
Test whether iterator still at a symbol.
Definition: dfa.hpp:240
void operator++(void)
Move iterator to next transition.
Definition: dfa.hpp:204
virtual SharedHandle::Object * copy(void) const
Create a copy.
Definition: dfa.cpp:489
const int max
Largest allowed integer value.
Definition: int.hh:113
const int min
Smallest allowed integer value.
Definition: int.hh:115
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
Specification of transition range.
Definition: dfa.hpp:63
Transition * trans
The transitions.
Definition: dfa.hpp:61
const Transition * fst
First transition for the symbol.
Definition: dfa.hpp:66
Deterministic finite automaton (DFA)
Definition: int.hh:1881
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
unsigned int n_symbols(void) const
Return the number of symbols.
Definition: dfa.hpp:111
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int final_lst
Last final state.
Definition: dfa.hpp:59
virtual ~DFAI(void)
Delete automaton implemenentation.
Definition: dfa.hpp:90
int i_state(void) const
Return in-state of current transition.
Definition: dfa.hpp:209
Specification of a DFA transition.
Definition: int.hh:1887
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition: dfa.hpp:123
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:127
unsigned int n_symbols
Number of symbols.
Definition: dfa.hpp:51
bool operator()(void) const
Test whether iterator still at a transition.
Definition: dfa.hpp:199
int n_transitions(void) const
Return the number of transitions.
Definition: dfa.hpp:117
DFAI(void)
Initialize automaton implementation as empty.
DFA(void)
Initialize for DFA accepting the empty word.
Definition: dfa.hpp:97
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:2619
int symbol(void) const
Return symbol of current transition.
Definition: dfa.hpp:214
int val(void) const
Return current symbol.
Definition: dfa.hpp:253
#define forceinline
Definition: config.hpp:132
HashEntry * table
The transition hash table by symbol.
Definition: dfa.hpp:70
void fill(void)
Fill hash table.
Definition: dfa.cpp:503
Data stored for a DFA.
Definition: dfa.hpp:46
const Transition * lst
Last transition for the symbol.
Definition: dfa.hpp:67
Iterator for DFA transitions (sorted by symbols)
Definition: int.hh:1898
int n_states(void) const
Return the number of states.
Definition: dfa.hpp:105
The shared object.
Definition: core.hpp:88
void operator++(void)
Move iterator to next symbol.
Definition: dfa.hpp:245
int n_states
Number of states.
Definition: dfa.hpp:49
Gecode toplevel namespace
int n_log
Size of table (as binary logarithm)
Definition: dfa.hpp:72
#define GECODE_INT_EXPORT
Definition: int.hh:78
int symbol_min(void) const
Return smallest symbol in DFA.
Definition: dfa.hpp:141
int symbol_max(void) const
Return largest symbol in DFA.
Definition: dfa.hpp:148
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