Generated on Thu Mar 13 2014 04:39:31 for Gecode by doxygen 1.8.1.2
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: 2010-04-08 20:35:31 +1000 (Thu, 08 Apr 2010) $ by $Author: schulte $
11  * $Revision: 10684 $
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  /*
157  * Iterating over all transitions
158  *
159  */
160 
163  const DFAI* o = static_cast<DFAI*>(d.object());
164  if (o != NULL) {
165  c_trans = &o->trans[0];
166  e_trans = c_trans+o->n_trans;
167  } else {
168  c_trans = e_trans = NULL;
169  }
170  }
171 
174  const DFAI* o = static_cast<DFAI*>(d.object());
175  if (o != NULL) {
176  int mask = (1<<o->n_log)-1;
177  int p = n & mask;
178  while ((o->table[p].fst != NULL) && (o->table[p].symbol != n))
179  p = (p+1) & mask;
180  c_trans = o->table[p].fst;
181  e_trans = o->table[p].lst;
182  } else {
183  c_trans = e_trans = NULL;
184  }
185  }
186 
187  forceinline bool
189  return c_trans < e_trans;
190  }
191 
192  forceinline void
194  c_trans++;
195  }
196 
197  forceinline int
199  return c_trans->i_state;
200  }
201 
202  forceinline int
204  return c_trans->symbol;
205  }
206 
207  forceinline int
209  return c_trans->o_state;
210  }
211 
212  /*
213  * Iterating over symbols
214  *
215  */
216 
219  const DFAI* o = static_cast<DFAI*>(d.object());
220  if (o != NULL) {
221  c_trans = &o->trans[0];
222  e_trans = c_trans+o->n_trans;
223  } else {
224  c_trans = e_trans = NULL;
225  }
226  }
227 
228  forceinline bool
230  return c_trans < e_trans;
231  }
232 
233  forceinline void
235  int s = c_trans->symbol;
236  do {
237  c_trans++;
238  } while ((c_trans < e_trans) && (s == c_trans->symbol));
239  }
240 
241  forceinline int
242  DFA::Symbols::val(void) const {
243  return c_trans->symbol;
244  }
245 
246 
247  template<class Char, class Traits>
248  std::basic_ostream<Char,Traits>&
249  operator <<(std::basic_ostream<Char,Traits>& os, const DFA& d) {
250  std::basic_ostringstream<Char,Traits> st;
251  st.copyfmt(os); st.width(0);
252  st << "Start state: 0" << std::endl
253  << "States: 0..." << d.n_states()-1 << std::endl
254  << "Transitions:";
255  for (int s = 0; s < static_cast<int>(d.n_states()); s++) {
256  DFA::Transitions t(d);
257  int n = 0;
258  while (t()) {
259  if (t.i_state() == s) {
260  if ((n % 4) == 0)
261  st << std::endl << "\t";
262  st << "[" << t.i_state() << "]"
263  << "- " << t.symbol() << " >"
264  << "[" << t.o_state() << "] ";
265  ++n;
266  }
267  ++t;
268  }
269  }
270  st << std::endl << "Final states: "
271  << std::endl
272  << "\t[" << d.final_fst() << "] ... ["
273  << d.final_lst()-1 << "]"
274  << std::endl;
275  return os << st.str();
276  }
277 
278 }
279 
280 
281 // STATISTICS: int-prop
282