dekker.one
fork
Configure Feed
Select the types of activity you want to include in your feed.
this repo has no description
fork
Configure Feed
Select the types of activity you want to include in your feed.
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
36namespace Gecode {
37
38 /**
39 * \brief Data stored for a %DFA
40 *
41 */
42 class DFA::DFAI : public SharedHandle::Object {
43 public:
44 /// Number of states
45 int n_states;
46 /// Number of symbols
47 unsigned int n_symbols;
48 /// Number of transitions
49 int n_trans;
50 /// Maximal degree (in-degree and out-degree of any state) and maximal number of transitions per symbol
51 unsigned int max_degree;
52 /// First final state
53 int final_fst;
54 /// Last final state
55 int final_lst;
56 /// Hash key
57 std::size_t key;
58 /// The transitions
59 Transition* trans;
60 /// Specification of transition range
61 class HashEntry {
62 public:
63 int symbol; ///< Symbol
64 const Transition* fst; ///< First transition for the symbol
65 const Transition* lst; ///< Last transition for the symbol
66 };
67 /// The transition hash table by symbol
68 HashEntry* table;
69 /// Size of table (as binary logarithm)
70 int n_log;
71 /// Fill hash table
72 void fill(void);
73 /// Initialize automaton implementation with \a nt transitions
74 DFAI(int nt);
75 /// Initialize automaton implementation as empty
76 GECODE_INT_EXPORT DFAI(void);
77 /// Delete automaton implemenentation
78 virtual ~DFAI(void);
79 };
80
81 forceinline
82 DFA::DFAI::DFAI(int nt)
83 : trans(nt == 0 ? nullptr : heap.alloc<Transition>(nt)) {}
84
85 forceinline
86 DFA::DFAI::~DFAI(void) {
87 if (n_trans > 0)
88 heap.rfree(trans);
89 heap.rfree(table);
90 }
91
92 forceinline void
93 DFA::DFAI::fill(void) {
94 key = static_cast<std::size_t>(n_states);
95 cmb_hash(key, n_trans);
96 cmb_hash(key, n_symbols);
97 cmb_hash(key, final_fst);
98 cmb_hash(key, final_lst);
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 = nullptr;
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 != nullptr)
123 p = (p+1) & mask;
124 table[p].symbol = s;
125 table[p].fst = fst;
126 table[p].lst = lst;
127 }
128 }
129
130 forceinline
131 DFA::DFA(void) {}
132
133
134 forceinline
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 == nullptr) ? 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 == nullptr) ? 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 == nullptr) ? 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 == nullptr) ? 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 == nullptr) ? 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 == nullptr) ? 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 != nullptr) && (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 != nullptr) && (d->n_trans > 0)) ?
185 d->trans[d->n_trans-1].symbol : Int::Limits::max;
186 }
187
188 forceinline std::size_t
189 DFA::hash(void) const {
190 const DFAI* d = static_cast<DFAI*>(object());
191 return (d != nullptr) ? d->key : 0;
192 }
193
194
195 /*
196 * Constructing transitions
197 *
198 */
199
200 forceinline
201 DFA::Transition::Transition(void) {}
202
203 forceinline
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
212 forceinline
213 DFA::Transitions::Transitions(const DFA& d) {
214 const DFAI* o = static_cast<DFAI*>(d.object());
215 if (o != nullptr) {
216 c_trans = &o->trans[0];
217 e_trans = c_trans+o->n_trans;
218 } else {
219 c_trans = e_trans = nullptr;
220 }
221 }
222
223 forceinline
224 DFA::Transitions::Transitions(const DFA& d, int n) {
225 const DFAI* o = static_cast<DFAI*>(d.object());
226 if (o != nullptr) {
227 int mask = (1<<o->n_log)-1;
228 int p = n & mask;
229 while ((o->table[p].fst != nullptr) && (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 = nullptr;
235 }
236 }
237
238 forceinline bool
239 DFA::Transitions::operator ()(void) const {
240 return c_trans < e_trans;
241 }
242
243 forceinline void
244 DFA::Transitions::operator ++(void) {
245 c_trans++;
246 }
247
248 forceinline int
249 DFA::Transitions::i_state(void) const {
250 return c_trans->i_state;
251 }
252
253 forceinline int
254 DFA::Transitions::symbol(void) const {
255 return c_trans->symbol;
256 }
257
258 forceinline int
259 DFA::Transitions::o_state(void) const {
260 return c_trans->o_state;
261 }
262
263 /*
264 * Iterating over symbols
265 *
266 */
267
268 forceinline
269 DFA::Symbols::Symbols(const DFA& d) {
270 const DFAI* o = static_cast<DFAI*>(d.object());
271 if (o != nullptr) {
272 c_trans = &o->trans[0];
273 e_trans = c_trans+o->n_trans;
274 } else {
275 c_trans = e_trans = nullptr;
276 }
277 }
278
279 forceinline bool
280 DFA::Symbols::operator ()(void) const {
281 return c_trans < e_trans;
282 }
283
284 forceinline void
285 DFA::Symbols::operator ++(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++) {
307 DFA::Transitions t(d);
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