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