Generated on Tue Oct 22 2013 00:49:04 for Gecode by doxygen 1.8.4
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