Vcsn  2.4 Be Rational
multiply.hh
Go to the documentation of this file.
1 #pragma once
2
3 #include <unordered_map>
4
5 #include <vcsn/algos/copy.hh>
7 #include <vcsn/algos/standard.hh>
8 #include <vcsn/algos/star.hh>
10 #include <vcsn/algos/tags.hh>
11 #include <vcsn/core/automaton.hh>
12 #include <vcsn/core/join.hh>
14 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
15 #include <vcsn/dyn/value.hh>
16 #include <vcsn/misc/raise.hh> // require
17 #include <vcsn/misc/to.hh> // to
18 #include <vcsn/misc/type_traits.hh> // to
19 #include <vcsn/misc/vector.hh> // make_vector
20
21 namespace vcsn
22 {
23  /*----------------------------------.
24  | multiply(automaton, automaton). |
25  `----------------------------------*/
26
32  template <Automaton Aut1, Automaton Aut2>
33  Aut1&
34  multiply_here(Aut1& res, const Aut2& b, deterministic_tag)
35  {
36  static_assert(labelset_t_of<Aut1>::is_free(),
37  "multiply_here: requires free labelset");
38  multiply_here(res, b, standard_tag{});
39  res = determinize(res)->strip();
40  return res;
41  }
42
46  template <Automaton Aut1, Automaton Aut2>
47  Aut1&
48  multiply_here(Aut1& res, const Aut2& b, general_tag)
49  {
50  const auto& ls = *res->labelset();
51  const auto& ws = *res->weightset();
52  const auto& bws = *b->weightset();
53
54  // The set of the current (left-hand side) final transitions.
55  // Store these transitions by copy.
56  auto final_ts = detail::make_vector(final_transitions(res));
57
58  // The set of the current (right-hand side) initial transitions.
59  // Store these transitions by copy.
60  auto init_ts = detail::make_vector(initial_transitions(b));
61
62  auto copy = make_copier(b, res);
63  copy([](state_t_of<Aut2>) { return true; },
64  // Import all the B transitions, except the initial ones.
65  [b] (transition_t_of<Aut2> t) { return b->src_of(t) != b->pre(); });
66  const auto& map = copy.state_map();
67
68  // Branch all the final transitions of res to the initial ones in b.
69  for (auto t1: final_ts)
70  {
71  auto s1 = res->src_of(t1);
72  auto w1 = res->weight_of(t1);
73  res->del_transition(t1);
74  for (auto t2: init_ts)
75  res->new_transition(s1,
76  map.at(b->dst_of(t2)),
77  ls.one(),
78  ws.mul(w1,
79  ws.conv(bws, b->weight_of(t2))));
80  }
81  return res;
82  }
83
87  template <Automaton Aut1, Automaton Aut2>
88  Aut1&
89  multiply_here(Aut1& res, const Aut2& b, standard_tag = {})
90  {
91  const auto& ls = *res->labelset();
92  const auto& bls = *b->labelset();
93  const auto& ws = *res->weightset();
94  const auto& bws = *b->weightset();
95
96  // The set of the current (left-hand side) final transitions.
97  // Store these transitions by copy.
98  auto final_ts = detail::make_vector(final_transitions(res));
99
100  // The set of the current (right-hand side) initial transitions.
101  // Store these transitions by copy.
102  auto init_ts = detail::make_vector(initial_transitions(b));
103
104  auto copy = make_copier(b, res);
105  copy(// In order to keep b's transitions unbroken we have to keep its
106  // initial states which have at least one incoming transition.
107  [b](state_t_of<Aut2> s)
108  {
109  return !b->is_initial(s) || !in(b, s).empty();
110  },
111  // Import b's transitions, except the initial ones (and those
112  // from its (genuine) initial state).
113  [b] (transition_t_of<Aut2> t) { return b->src_of(t) != b->pre(); });
114  const auto& map = copy.state_map();
115
116  // Branch all the final transitions of res to the successors of
117  // b's initial states.
118  for (auto t1: final_ts)
119  {
120  // Remove the previous final transition first, as we might add
121  // a final transition for the same state later.
122  //
123  // For instance on "<2>a+(<3>\e+<5>a)", the final state s1 of
124  // <2>a will be made final thanks to <3>\e. So if we compute
125  // the new transitions from s1 and then remove t1, we will
126  // have removed the fact that s1 is final thanks to <3>\e.
127  //
128  // Besides, s1 will become final with weight <3>, which might
129  // interfere with <5>a too.
130  auto s1 = res->src_of(t1);
131  auto w1 = res->weight_of(t1);
132  res->del_transition(t1);
133  for (auto t2: init_ts)
134  {
135  auto w2 = b->weight_of(t2);
136  for (auto t3: all_out(b, b->dst_of(t2)))
137  res->set_transition(s1,
138  map.at(b->dst_of(t3)),
139  ls.conv(bls, b->label_of(t3)),
140  ws.mul(w1,
141  ws.conv(bws, w2),
142  ws.conv(bws, b->weight_of(t3))));
143  }
144  }
145  return res;
146  }
147
149  template <Automaton Aut1, Automaton Aut2, typename Tag = general_tag>
150  auto
151  multiply(const Aut1& lhs, const Aut2& rhs, Tag tag = {})
152  -> decltype(lhs->null_state(), // SFINAE.
153  rhs->null_state(), // SFINAE.
154  detail::make_join_automaton(tag, lhs, rhs))
155  {
156  auto res = detail::make_join_automaton(tag, lhs, rhs);
157  copy_into(lhs, res);
158  multiply_here(res, rhs, tag);
159  return res;
160  }
161
162  namespace dyn
163  {
164  namespace detail
165  {
167  template <Automaton Lhs, Automaton Rhs, typename String>
168  automaton
169  multiply(const automaton& lhs, const automaton& rhs,
170  const std::string& algo)
171  {
172  const auto& l = lhs->as<Lhs>();
173  const auto& r = rhs->as<Rhs>();
175  (algo == "auto" ? "standard" : algo,
176  [l, r](auto tag)
177  {
178  return automaton(::vcsn::multiply(l, r, tag));
179  },
180  l, r);
181  }
182  }
183  }
184
185  /*---------------------------------.
186  | multiply(automaton, min, max). |
187  `---------------------------------*/
188
193  // The return type, via SFINAE on aut->null_state(), makes the
194  // difference with another overload, `<ValueSet>(ValueSet, value,
195  // value)`, which coincides in the case ValueSet = Z, hence value =
196  // int.
197  //
198  // Unfortunately, fresh_automaton_t_of, which uses
199  // context_t_of<Aut>, is not SFINAE transparent: it causes a hard
200  // failure instead of being ignored.
201  //
202  // FIXME: if you know how to use fresh_automaton_t_of instead, let
203  // me know.
204  template <Automaton Aut, typename Tag = general_tag>
205  auto
206  multiply(const Aut& aut, to exp, Tag tag = {})
207  -> decltype(aut->null_state(), // SFINAE.
208  detail::make_join_automaton(tag, aut))
209  {
210  auto res = detail::make_join_automaton(tag, aut);
211  if (exp.max == -1)
212  {
213  res = star(aut, tag);
214  if (exp.min)
215  res = multiply(multiply(aut, to{exp.min}, tag), res, tag);
216  }
217  else
218  {
219  if (exp.min == 0)
220  {
221  //automatonset::one().
222  auto s = res->new_state();
223  res->set_initial(s);
224  res->set_final(s);
225  }
226  else
227  {
228  auto tag_aut = detail::make_join_automaton(tag, aut);
229  copy_into(aut, res);
230  copy_into(aut, tag_aut);
231  for (int n = 1; n < exp.min; ++n)
232  res = multiply(res, tag_aut, tag);
233  }
234  if (exp.min < exp.max)
235  {
236  // Aut sum = automatonset.one();
237  auto sum = detail::make_join_automaton(tag, aut);
238  {
239  auto s = sum->new_state();
240  sum->set_initial(s);
241  sum->set_final(s);
242  }
243  for (int n = 1; n <= exp.max - exp.min; ++n)
244  sum = strip(add(sum, multiply(aut, to{n}, tag), tag));
245  res = multiply(res, sum, tag);
246  }
247  }
248  return res;
249  }
250
251  namespace dyn
252  {
253  namespace detail
254  {
256  template <Automaton Aut, typename Int1, typename Int2, typename String>
257  automaton
258  multiply_repeated(const automaton& a, int min, int max,
259  const std::string& algo)
260  {
261  const auto& aut = a->as<Aut>();
263  [aut, min, max](auto tag)
264  {
265  return automaton(::vcsn::multiply(aut, to{min, max}, tag));
266  },
267  aut);
268  }
269  }
270  }
271
272
273  /*------------------------------------.
274  | multiply(expression, expression). |
275  `------------------------------------*/
276
278  template <typename ValueSet>
279  typename ValueSet::value_t
280  multiply(const ValueSet& vs,
281  const typename ValueSet::value_t& lhs,
282  const typename ValueSet::value_t& rhs)
283  {
284  return vs.mul(lhs, rhs);
285  }
286
287  namespace dyn
288  {
289  namespace detail
290  {
292  template <typename ExpSetLhs, typename ExpSetRhs>
293  expression
294  multiply_expression(const expression& lhs, const expression& rhs)
295  {
296  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
297  return {std::get<0>(join_elts),
298  ::vcsn::multiply(std::get<0>(join_elts),
299  std::get<1>(join_elts),
300  std::get<2>(join_elts))};
301  }
302  }
303  }
304
305  namespace dyn
306  {
307  namespace detail
308  {
310  template <typename ExpSetLhs, typename ExpSetRhs>
311  expression
313  {
314  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
315  auto res = std::get<0>(join_elts).concat(std::get<1>(join_elts),
316  std::get<2>(join_elts));
317  return {std::get<0>(join_elts), res};
318  }
319  }
320  }
321
322
323  /*-----------------------------.
324  | multiply(value, min, max). |
325  `-----------------------------*/
326
328  template <typename ValueSet>
330  = decltype(std::declval<ValueSet>()
332  std::declval<typename ValueSet::value_t>()));
333
335  template <typename ValueSet>
337
343  template <typename ValueSet>
344  auto
345  multiply(const ValueSet& vs, const typename ValueSet::value_t& v,
346  const to& exp)
348  typename ValueSet::value_t>
349  {
350  VCSN_REQUIRE(exp.single() && exp.finite(),
351  vs, ": invalid range exponent: ", exp);
352  return detail::static_if<detail::has_power_mem_fn<ValueSet>{}>
353  ([](const auto& vs, const auto& v, auto n){ return vs.power(v, n); },
354  [](const auto& vs, const auto& v, auto n)
355  {
356  auto res = vs.one();
357  if (!vs.is_one(v))
358  while (n--)
359  res = vs.mul(res, v);
360  return res;
361  })(vs, v, exp.min);
362  }
363
373  template <typename ValueSet>
374  auto
375  multiply(const ValueSet& vs, const typename ValueSet::value_t& v,
376  const to& exp)
378  typename ValueSet::value_t>
379  {
380  auto res = typename ValueSet::value_t{};
381  if (exp.max == -1)
382  {
383  res = vs.star(v);
384  if (exp.min)
385  res = vs.mul(vs.power(v, exp.min), res);
386  }
387  else
388  {
389  res = vs.power(v, exp.min);
390  if (exp.min < exp.max)
391  {
392  auto sum = vs.one();
393  for (int n = 1; n <= exp.max - exp.min; ++n)
394  sum = vs.add(sum, vs.power(v, n));
395  res = vs.mul(res, sum);
396  }
397  }
398  return res;
399  }
400
401  namespace dyn
402  {
403  namespace detail
404  {
406  template <typename ExpSet, typename Int1, typename Int2>
407  expression
408  multiply_expression_repeated(const expression& re, int min, int max)
409  {
410  const auto& r = re->as<ExpSet>();
411  return {r.valueset(),
412  ::vcsn::multiply(r.valueset(), r.value(), to{min, max})};
413  }
414  }
415  }
416
417
418  /*--------------------------.
419  | multiply(label, label). |
420  `--------------------------*/
421
422  namespace dyn
423  {
424  namespace detail
425  {
427  template <typename LabelSetLhs, typename LabelSetRhs>
428  label
429  multiply_label(const label& lhs, const label& rhs)
430  {
431  const auto& l = lhs->as<LabelSetLhs>();
432  const auto& r = rhs->as<LabelSetRhs>();
433  auto rs = join(l.valueset(), r.valueset());
434  auto lr = rs.conv(l.valueset(), l.value());
435  auto rr = rs.conv(r.valueset(), r.value());
436  return {rs, multiply(rs, lr, rr)};
437  }
438
440  template <typename LabelSet, typename Int>
441  label
442  multiply_label_repeated(const label& re, int exp)
443  {
444  const auto& r = re->as<LabelSet>();
445  return {r.valueset(),
446  ::vcsn::multiply(r.valueset(), r.value(), to{exp})};
447  }
448  }
449  }
450
451
452  /*------------------------------------.
453  | multiply(polynomial, polynomial). |
454  `------------------------------------*/
455
456  namespace dyn
457  {
458  namespace detail
459  {
461  template <typename PolynomialSetLhs, typename PolynomialSetRhs>
462  polynomial
463  multiply_polynomial(const polynomial& lhs, const polynomial& rhs)
464  {
465  auto join_elts = join<PolynomialSetLhs, PolynomialSetRhs>(lhs, rhs);
466  return {std::get<0>(join_elts), multiply(std::get<0>(join_elts),
467  std::get<1>(join_elts),
468  std::get<2>(join_elts))};
469  }
470  }
471  }
472
473  /*----------------------------.
474  | multiply(weight, weight). |
475  `----------------------------*/
476
477  namespace dyn
478  {
479  namespace detail
480  {
482  template <typename WeightSetLhs, typename WeightSetRhs>
483  weight
484  multiply_weight(const weight& lhs, const weight& rhs)
485  {
486  const auto& l = lhs->as<WeightSetLhs>();
487  const auto& r = rhs->as<WeightSetRhs>();
488  auto ws = join(l.valueset(), r.valueset());
489  auto lw = ws.conv(l.valueset(), l.value());
490  auto rw = ws.conv(r.valueset(), r.value());
491  return {ws, ::vcsn::multiply(ws, lw, rw)};
492  }
493
495  template <typename WeightSet, typename Int1, typename Int2>
496  weight
497  multiply_weight_repeated(const weight& wgt, int min, int max)
498  {
499  const auto& w = wgt->as<WeightSet>();
500  return {w.valueset(),
501  ::vcsn::multiply(w.valueset(), w.value(), to{min, max})};
502  }
503  }
504  }
505 }
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
weight multiply_weight_repeated(const weight &wgt, int min, int max)
Bridge (multiply).
Definition: multiply.hh:497
void copy_into(const AutIn &in, AutOut &out, KeepState keep_state, KeepTrans keep_trans)
Copy selected states and transitions of an automaton.
Definition: copy.hh:267
Tag for operations on all automata.
Definition: tags.hh:22
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
bool single() const
Whether features a single exponent.
Definition: to.hh:63
Tag for operations on standard automata.
Definition: tags.hh:32
int max
Definition: to.hh:69
value_impl< detail::weight_tag > weight
Definition: fwd.hh:28
expression multiply_expression_repeated(const expression &re, int min, int max)
Bridge (multiply).
Definition: multiply.hh:408
context join(const context &lhs, const context &rhs)
The join between two contexts, i.e., their lowest common supertype.
auto make_join_automaton(deterministic_tag, Auts &&...auts) -> decltype(join_automata(std::forward< Auts >(auts)...))
Make an empty automaton which is a supertype of others.
Definition: tags.hh:101
expression multiply_expression(const expression &lhs, const expression &rhs)
Bridge (multiply).
Definition: multiply.hh:294
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
Definition: determinize.hh:247
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:177
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:256
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48
weight multiply_weight(const weight &lhs, const weight &rhs)
Bridge (multiply).
Definition: multiply.hh:484
auto add(const Aut1 &lhs, const Aut2 &rhs, deterministic_tag)
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
label multiply_label_repeated(const label &re, int exp)
Bridge (multiply).
Definition: multiply.hh:442
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:166
label multiply_label(const label &lhs, const label &rhs)
Bridge (multiply).
Definition: multiply.hh:429
return exp min
Definition: multiply.hh:361
automaton multiply(const automaton &lhs, const automaton &rhs, const std::string &algo)
Bridge.
Definition: multiply.hh:169
Definition: a-star.hh:8
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:134
Aut1 & multiply_here(Aut1 &res, const Aut2 &b, deterministic_tag)
Append automaton b to res.
Definition: multiply.hh:34
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
Tag for operations on deterministic automata.
Definition: tags.hh:19
The type of the add member function in valuesets.
Definition: multiply.hh:332
bool finite() const
Whether the max exponent is finte.
Definition: to.hh:57
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
auto multiply(const ValueSet &vs, const typename ValueSet::value_t &v, const to &exp) -> std::enable_if_t<!has_add_mem_fn< ValueSet >
Repeated multiplication of values that cannot be added.
Definition: multiply.hh:345
auto multiply(const Aut1 &lhs, const Aut2 &rhs, Tag tag={}) -> decltype(lhs->null_state(), rhs->null_state(), detail::make_join_automaton(tag, lhs, rhs))
Concatenate two automata, general case.
Definition: multiply.hh:151
automaton multiply_repeated(const automaton &a, int min, int max, const std::string &algo)
Bridge (multiply).
Definition: multiply.hh:258
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:177
return v
Definition: multiply.hh:361
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
expression concatenate_expression(const expression &lhs, const expression &rhs)
Bridge (concatenate).
Definition: multiply.hh:312
automaton multiply(const automaton &lhs, const automaton &rhs, const std::string &algo="auto")
Multiply (concatenate) two automata.
Definition: multiply.hh:169
auto & as()
Extract wrapped typed value.
Definition: value.hh:53
int min
Definition: to.hh:68
auto star(const Aut &aut, Tag tag={}) -> decltype(detail::make_join_automaton(tag, aut))
Star of an automaton.
Definition: star.hh:108
auto strip(const Aut &aut)
Remove (all) the decorations from a decorated automaton.
Definition: strip.hh:34
automaton add(const automaton &lhs, const automaton &rhs, const std::string &algo="auto")
Sum of two automata.
An exponent, or range of exponents.
Definition: to.hh:25
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
value_impl< detail::label_tag > label
Definition: fwd.hh:26
polynomial multiply_polynomial(const polynomial &lhs, const polynomial &rhs)
Bridge (multiply).
Definition: multiply.hh:463
A dyn Value/ValueSet.
Definition: fwd.hh:23
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
auto dispatch_tags(std::string algo, Operation op, Aut &&...auts)
Dispatch an operation between automata depending on their nature.
Definition: tags.hh:46
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27