Vcsn  2.3
Be Rational
zpc.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #include <vcsn/core/automaton.hh> // all_in
7 #include <vcsn/ctx/fwd.hh>
8 #include <vcsn/ctx/traits.hh>
9 #include <vcsn/dyn/automaton.hh>
10 #include <vcsn/dyn/value.hh>
11 #include <vcsn/labelset/labelset.hh> // make_nullableset_context
12 #include <vcsn/misc/getargs.hh>
13 #include <vcsn/misc/raise.hh>
14 
15 namespace vcsn
16 {
17  namespace rat
18  {
23  template <Automaton Aut,
24  typename ExpSet>
26  : public ExpSet::const_visitor
27  {
28  static_assert(labelset_t_of<Aut>::has_one(),
29  "zpc: requires nullable labels");
30 
31  public:
32  using automaton_t = Aut;
33  using expressionset_t = ExpSet;
38 
39  using super_t = typename expressionset_t::const_visitor;
40 
42  constexpr static const char* me() { return "zpc"; }
43 
46  const expressionset_t& rs,
47  bool compact)
48  : rs_(rs)
50  , compact_(compact)
51  {}
52 
53  zpc_visitor(const expressionset_t& rs, bool compact)
54  : zpc_visitor(rs.context(), rs, compact)
55  {}
56 
58  operator()(const typename expressionset_t::value_t& v)
59  {
60  try
61  {
62  v->accept(*this);
63  res_->set_initial(initial_);
64  res_->set_final(final_);
65 
66  for (auto t: all_in(res_, res_->post()))
67  res_->set_weight(t, ws_.mul(res_->weight_of(t), final_weight_));
68 
69  return std::move(res_);
70  }
71  catch (const std::runtime_error& e)
72  {
73  raise(e,
74  " while computing ZPC automaton of: ", to_string(rs_, v));
75  }
76  }
77 
78  private:
86  using tuple_t = typename super_t::tuple_t;
87  void visit(const tuple_t&, std::true_type) override
88  {
89  raise(me(), ": tuple is not supported");
90  }
91 
93  {
94  initial_ = res_->new_state();
95  final_ = res_->new_state();
96  }
97 
99  {
100  initial_ = res_->new_state();
101  final_ = res_->new_state();
102 
103  res_->set_final(initial_);
104  }
105 
107  {
108  initial_ = res_->new_state();
109  final_ = res_->new_state();
110  // The automaton and the expression might have different
111  // labelsets.
112  res_->new_transition(initial_, final_,
113  res_->labelset()->conv(*rs_.labelset(),
114  e.value()));
115  }
116 
118  {
119  if (compact_)
120  add_compact(e);
121  else
122  add_regular(e);
123  }
124 
126  {
127  if (compact_)
128  prod_compact(e);
129  else
130  prod_regular(e);
131  }
132 
134  {
135  state_t initial = res_->new_state();
136 
137  e.sub()->accept(*this);
138 
139  state_t final = res_->new_state();
140 
141  auto cst = ws_.star(res_->get_final_weight(initial_));
142  res_->unset_final(initial_);
143 
144  res_->new_transition(initial, initial_, epsilon_, cst);
145  res_->new_transition(final_, final, epsilon_, cst);
146  res_->new_transition(final_, initial_, epsilon_, cst);
147 
148  initial_ = initial;
149  final_ = final;
150 
151  res_->set_final(initial_, cst);
152  }
153 
155  {
156  e.sub()->accept(*this);
157 
158  const weight_t& w = e.weight();
159  for (auto t: all_out(res_, initial_))
160  res_->set_weight(t, ws_.mul(w, res_->weight_of(t)));
161  }
162 
164  {
165  e.sub()->accept(*this);
166 
167  final_weight_ = ws_.mul(e.weight(), final_weight_);
168  }
169 
170  void add_regular(const add_t& e)
171  {
172  state_t initial = res_->new_state();
173 
174  weight_t cst = ws_.zero();
175  std::vector<state_t> finals_;
176 
177  for (auto c: e)
178  {
179  c->accept(*this);
180  res_->new_transition(initial, initial_, epsilon_);
181  finals_.push_back(final_);
182 
183  cst = ws_.add(cst, res_->get_final_weight(initial_));
184  res_->unset_final(initial_);
185  }
186 
187  state_t final = res_->new_state();
188 
189  for (auto s: finals_)
190  res_->new_transition(s, final, epsilon_);
191 
192  initial_ = initial;
193  final_ = final;
194 
195  // Constant term weight.
196  res_->set_final(initial_, cst);
197  }
198 
199  void prod_regular(const mul_t& e)
200  {
201  std::vector<state_t> state_stack;
202 
203  // Number of 'initial' states to create.
204  for (auto i = 0; i < e.size() - 1; ++i)
205  state_stack.push_back(res_->new_state());
206 
207  e.head()->accept(*this);
208 
209  // In each methods prod_regular, prod_compact and add_compact,
210  // sometimes it's necessary to create simultaneously
211  // two sub-automaton, the first one's states are postfixes by _e and
212  // the next one (creation order) by _f.
213  state_t initial_e = initial_;
214  state_t final_e = final_;
215 
216  // Default value of initial for the compact form.
217  state_t initial = initial_e;
218  state_t final = automaton_t::element_type::null_state();
219 
220  initial = state_stack.back();
221  state_stack.pop_back();
222  res_->new_transition(initial, initial_e, epsilon_);
223 
224  for (auto t: e.tail())
225  {
226  t->accept(*this);
227 
228  final = res_->new_state();
229  res_->new_transition(final_, final, epsilon_);
230 
231  auto cst_e = res_->get_final_weight(initial_e);
232  auto cst_f = res_->get_final_weight(initial_);
233 
234  res_->new_transition(initial, initial_, epsilon_, cst_e);
235  res_->unset_final(initial_e);
236  res_->new_transition(final_e, final, epsilon_, cst_f);
237  res_->unset_final(initial_);
238 
239  res_->set_final(initial, ws_.mul(cst_e, cst_f));
240 
241  res_->new_transition(final_e, initial_, epsilon_);
242 
243  initial_e = initial;
244  final_e = final;
245 
246  if (!state_stack.empty())
247  {
248  initial = state_stack.back();
249  state_stack.pop_back();
250 
251  res_->new_transition(initial, initial_e, epsilon_);
252  }
253  }
254 
255  initial_ = initial;
256  final_ = final;
257  }
258 
259  void add_compact(const add_t& e)
260  {
261  e.head()->accept(*this);
262 
263  weight_t cst = res_->get_final_weight(initial_);
264  res_->unset_final(initial_);
265 
266  state_t initial = initial_;
267  state_t initial_e = initial;
268  state_t final_e = final_;
269 
270  for (auto c: e.tail())
271  {
272  c->accept(*this);
273  cst = ws_.add(cst, res_->get_final_weight(initial_));
274  res_->unset_final(initial_);
275 
276  res_->new_transition(initial_e, initial_, epsilon_);
277  res_->new_transition(final_e, final_, epsilon_);
278 
279  initial_e = initial_;
280  final_e = final_;
281  }
282 
283  initial_ = initial;
284 
285  res_->set_final(initial_, cst);
286  }
287 
288  void prod_compact(const mul_t& e)
289  {
290  e.head()->accept(*this);
291 
292  state_t initial_e = initial_;
293  state_t final_e = final_;
294 
295  // Default value of initial for the compact form.
296  state_t initial = initial_e;
297  state_t final;
298 
299  for (auto t: e.tail())
300  {
301  t->accept(*this);
302  final = final_;
303 
304  auto cst_e = res_->get_final_weight(initial_e);
305  auto cst_f = res_->get_final_weight(initial_);
306 
307  res_->new_transition(initial, initial_, epsilon_, cst_e);
308  res_->unset_final(initial_e);
309  res_->new_transition(final_e, final, epsilon_, cst_f);
310  res_->unset_final(initial_);
311 
312  res_->set_final(initial, ws_.mul(cst_e, cst_f));
313 
314  res_->new_transition(final_e, initial_, epsilon_);
315 
316  initial_e = initial;
317  final_e = final;
318  }
319 
320  initial_ = initial;
321  final_ = final;
322  }
323 
324  private:
326  const weightset_t& ws_ = *rs_.weightset();
329  const label_t epsilon_ = res_->labelset()->one();
330  state_t initial_ = automaton_t::element_type::null_state();
331  state_t final_ = automaton_t::element_type::null_state();
332  weight_t final_weight_ = ws_.one();
334  const bool compact_;
335  };
336  } // rat::
337 
342  template <Automaton Aut, typename ExpSet>
343  Aut
345  const ExpSet& rs,
346  const typename ExpSet::value_t& r,
347  const std::string& algo = "auto")
348  {
349  static const auto map = getarg<bool>
350  {
351  "zpc version",
352  {
353  // name, compact.
354  // Beware of the conversion from const char* to bool here.
355  // http://stackoverflow.com/questions/13268608/.
356  {"auto", std::string("regular")},
357  {"compact", true},
358  {"regular", false},
359  }
360  };
361  auto zpc = rat::zpc_visitor<Aut, ExpSet>{ctx, rs, map[algo]};
362  return zpc(r);
363  }
364 
365  namespace dyn
366  {
367  namespace detail
368  {
369  /*-----------------.
370  | dyn::zpc(exp). |
371  `-----------------*/
372 
374  template <typename ExpSet, typename String>
375  automaton
376  zpc(const expression& exp, const std::string& algo)
377  {
378  // FIXME: So far, there is a single implementation of expressions,
379  // but we should actually be parameterized by its type too.
380  using expressionset_t = ExpSet;
381  const auto& e = exp->as<expressionset_t>();
382  auto ctx
383  = vcsn::detail::make_nullableset_context(e.valueset().context());
384  using ctx_t = decltype(ctx);
385  using automaton_t = mutable_automaton<ctx_t>;
386  return ::vcsn::zpc<automaton_t>(ctx, e.valueset(), e.value(), algo);
387  }
388  }
389  }
390 } // vcsn::
VCSN_RAT_VISIT(atom, e)
Definition: zpc.hh:106
return v
Definition: multiply.hh:361
zpc_visitor(const expressionset_t &rs, bool compact)
Definition: zpc.hh:53
VCSN_RAT_VISIT(zero,)
Definition: zpc.hh:92
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
SharedPtr make_shared_ptr(Args &&...args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:13
VCSN_RAT_VISIT(rweight, e)
Definition: zpc.hh:163
#define Automaton
Definition: automaton.hh:23
context_t_of< automaton_t > context_t
Definition: zpc.hh:34
void add_compact(const add_t &e)
Definition: zpc.hh:259
STL namespace.
typename super_t::tuple_t tuple_t
Definition: zpc.hh:86
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
ExpSet expressionset_t
Definition: zpc.hh:33
VCSN_RAT_VISIT(add, e)
Definition: zpc.hh:117
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
automaton zpc(const expression &exp, const std::string &algo)
Bridge.
Definition: zpc.hh:376
An inner node implementing a weight.
Definition: expression.hh:264
void add_regular(const add_t &e)
Definition: zpc.hh:170
weight_t_of< expressionset_t > weight_t
Definition: zpc.hh:36
VCSN_RAT_VISIT(mul, e)
Definition: zpc.hh:125
automaton_t operator()(const typename expressionset_t::value_t &v)
Definition: zpc.hh:58
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
label_t_of< automaton_t > label_t
Definition: zpc.hh:328
auto rs
Definition: lift.hh:152
state_t initial_
Definition: zpc.hh:330
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
void prod_compact(const mul_t &e)
Definition: zpc.hh:288
const bool compact_
Whether to build the "compact" version of the ZPC automaton.
Definition: zpc.hh:334
VCSN_RAT_VISIT(lweight, e)
Definition: zpc.hh:154
nullableset_context_t< context< LabelSet, WeightSet > > make_nullableset_context(const context< LabelSet, WeightSet > &ctx)
The nullableset context of a context.
Definition: labelset.hh:163
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:94
automaton_t res_
Definition: zpc.hh:327
void prod_regular(const mul_t &e)
Definition: zpc.hh:199
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: zpc.hh:42
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:41
Aut zpc(const context_t_of< Aut > &ctx, const ExpSet &rs, const typename ExpSet::value_t &r, const std::string &algo="auto")
Build a ZPC automaton from an expression.
Definition: zpc.hh:344
const weightset_t & ws_
Definition: zpc.hh:326
weightset_t_of< expressionset_t > weightset_t
Definition: zpc.hh:35
zpc_visitor(const context_t &ctx, const expressionset_t &rs, bool compact)
Build an automaton of context ctx.
Definition: zpc.hh:45
const label_t epsilon_
Definition: zpc.hh:329
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
An inner node with multiple children.
Definition: expression.hh:118
state_t_of< automaton_t > state_t
Definition: zpc.hh:37
A mapping from strings to Values.
Definition: getargs.hh:33
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:75
weight_t final_weight_
Definition: zpc.hh:332
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
VCSN_RAT_VISIT(star, e)
Definition: zpc.hh:133
Build a ZPC automaton from an expression.
Definition: zpc.hh:25
VCSN_RAT_VISIT(one,)
Definition: zpc.hh:98
const expressionset_t & rs_
Definition: zpc.hh:325
typename expressionset_t::const_visitor super_t
Definition: zpc.hh:39
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
void visit(const tuple_t &, std::true_type) override
Definition: zpc.hh:87