Vcsn  2.4
Be Rational
add.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <map>
4 
7 #include <vcsn/algos/standard.hh> // is_standard
8 #include <vcsn/algos/tags.hh>
10 #include <vcsn/ctx/traits.hh>
11 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
12 #include <vcsn/dyn/value.hh>
13 #include <vcsn/misc/raise.hh> // require
14 
15 namespace vcsn
16 {
17 
18  /*----------------------------.
19  | add(automaton, automaton). |
20  `----------------------------*/
21 
26  template <Automaton Aut1, Automaton Aut2>
27  Aut1&
28  add_here(Aut1& res, const Aut2& b, standard_tag)
29  {
30  require(is_standard(res), __func__, ": lhs must be standard");
31  require(is_standard(b), __func__, ": rhs must be standard");
32 
33  // State in B -> state in Res.
34  auto m = std::map<state_t_of<Aut2>, state_t_of<Aut1>>
35  {
36  {b->pre(), res->pre()},
37  {b->post(), res->post()},
38  };
39  state_t_of<Aut1> initial = res->dst_of(initial_transitions(res).front());
40  for (auto s: b->states())
41  m.emplace(s, b->is_initial(s) ? initial : res->new_state());
42 
43  // Add b.
44  for (auto t: all_transitions(b))
45  if (b->dst_of(t) == b->post())
46  res->add_transition(m[b->src_of(t)], m[b->dst_of(t)],
47  b->label_of(t),
48  res->weightset()->conv(*b->weightset(),
49  b->weight_of(t)));
50  // Do not add initial transitions, the unique initial state is
51  // already declared as such, and its weight must remain 1.
52  else if (b->src_of(t) != b->pre())
53  res->new_transition(m[b->src_of(t)], m[b->dst_of(t)],
54  b->label_of(t),
55  res->weightset()->conv(*b->weightset(),
56  b->weight_of(t)));
57  return res;
58  }
59 
60  template <Automaton Aut1, Automaton Aut2>
61  auto
62  add_here(Aut1& res, const Aut2& b, deterministic_tag)
63  {
64  add_here(res, b, general_tag{});
65  res = determinize(res)->strip();
66  return res;
67  }
68 
69  template <Automaton Aut1, Automaton Aut2>
70  auto
71  add(const Aut1& lhs, const Aut2& rhs, deterministic_tag)
72  {
73  constexpr bool bb = (std::is_same<weightset_t_of<Aut1>, b>::value
74  && std::is_same<weightset_t_of<Aut2>, b>::value);
75  return detail::static_if<bb>(
76  [] (const auto& lhs, const auto& rhs)
77  {
78  auto prod
79  = detail::make_product_automaton<false>(join_automata(lhs, rhs),
80  lhs, rhs);
81  prod->add();
82  return prod->strip();
83  },
84  [] (const auto& lhs, const auto& rhs)
85  {
86  return determinize(add(lhs, rhs, general_tag{}))->strip();
87  })(lhs, rhs);
88  }
89 
93  template <Automaton Aut1, Automaton Aut2>
94  Aut1&
95  add_here(Aut1& res, const Aut2& b, general_tag)
96  {
97  copy_into(b, res);
98  return res;
99  }
100 
106  template <Automaton Aut1, Automaton Aut2, typename Tag = general_tag>
107  auto
108  add(const Aut1& lhs, const Aut2& rhs, Tag tag = {})
109  -> decltype(join_automata(lhs, rhs))
110  {
111  auto res = join_automata(lhs, rhs);
112  copy_into(lhs, res);
113  add_here(res, rhs, tag);
114  return res;
115  }
116 
117  namespace dyn
118  {
119  namespace detail
120  {
122  template <Automaton Lhs, Automaton Rhs, typename String>
123  automaton
124  add(const automaton& lhs, const automaton& rhs, const std::string& algo)
125  {
126  const auto& l = lhs->as<Lhs>();
127  const auto& r = rhs->as<Rhs>();
129  [l, r](auto tag)
130  {
131  return automaton(::vcsn::add(l, r, tag));
132  },
133  l, r);
134  }
135  }
136  }
137 
138 
139  /*---------------------.
140  | add(Value, Value). |
141  `---------------------*/
142 
144  template <typename ValueSet>
145  typename ValueSet::value_t
146  add(const ValueSet& vs,
147  const typename ValueSet::value_t& lhs,
148  const typename ValueSet::value_t& rhs)
149  {
150  return vs.add(lhs, rhs);
151  }
152 
153 
154  /*-----------------------------.
155  | add(expansion, expansion). |
156  `-----------------------------*/
157 
158  namespace dyn
159  {
160  namespace detail
161  {
163  template <typename ExpansionSetLhs, typename ExpansionSetRhs>
164  expansion
165  add_expansion(const expansion& lhs, const expansion& rhs)
166  {
167  auto join_elts = join<ExpansionSetLhs, ExpansionSetRhs>(lhs, rhs);
168  return {std::get<0>(join_elts),
169  ::vcsn::add(std::get<0>(join_elts),
170  std::get<1>(join_elts), std::get<2>(join_elts))};
171  }
172  }
173  }
174 
175  /*-------------------------------.
176  | add(expression, expression). |
177  `-------------------------------*/
178 
179  namespace dyn
180  {
181  namespace detail
182  {
184  template <typename ExpSetLhs, typename ExpSetRhs>
185  expression
186  add_expression(const expression& lhs, const expression& rhs)
187  {
188  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
189  return {std::get<0>(join_elts),
190  ::vcsn::add(std::get<0>(join_elts),
191  std::get<1>(join_elts), std::get<2>(join_elts))};
192  }
193  }
194  }
195 
196 
197  /*-------------------------------.
198  | add(polynomial, polynomial). |
199  `-------------------------------*/
200 
201  namespace dyn
202  {
203  namespace detail
204  {
206  template <typename PolynomialSetLhs, typename PolynomialSetRhs>
207  polynomial
208  add_polynomial(const polynomial& lhs, const polynomial& rhs)
209  {
210  auto join_elts = join<PolynomialSetLhs, PolynomialSetRhs>(lhs, rhs);
211  return {std::get<0>(join_elts),
212  add(std::get<0>(join_elts),
213  std::get<1>(join_elts), std::get<2>(join_elts))};
214  }
215  }
216  }
217 
218 
219  /*----------------------.
220  | add(weight, weight). |
221  `----------------------*/
222 
223  namespace dyn
224  {
225  namespace detail
226  {
228  template <typename WeightSetLhs, typename WeightSetRhs>
229  weight
230  add_weight(const weight& lhs, const weight& rhs)
231  {
232  auto join_elts = join<WeightSetLhs, WeightSetRhs>(lhs, rhs);
233  return {std::get<0>(join_elts),
234  add(std::get<0>(join_elts),
235  std::get<1>(join_elts), std::get<2>(join_elts))};
236  }
237  }
238  }
239 }
value_impl< detail::expansion_tag > expansion
Definition: fwd.hh:24
expansion add_expansion(const expansion &lhs, const expansion &rhs)
Bridge (add).
Definition: add.hh:165
expression add_expression(const expression &lhs, const expression &rhs)
Bridge (add).
Definition: add.hh:186
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:68
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
return res
Definition: multiply.hh:398
Tag for operations on standard automata.
Definition: tags.hh:32
value_impl< detail::weight_tag > weight
Definition: fwd.hh:28
Aut1 & add_here(Aut1 &res, const Aut2 &b, standard_tag)
Merge transitions of b into those of res.
Definition: add.hh:28
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
Definition: determinize.hh:247
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
auto add(const Aut1 &lhs, const Aut2 &rhs, deterministic_tag)
Definition: add.hh:71
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:166
polynomial add_polynomial(const polynomial &lhs, const polynomial &rhs)
Bridge (add).
Definition: add.hh:208
Definition: a-star.hh:8
auto join_automata(Auts &&...auts) -> decltype(pass(auts->null_state()...), make_mutable_automaton(join(auts->context()...)))
An automaton whose type is the join between those of auts.
Tag for operations on deterministic automata.
Definition: tags.hh:19
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
bool is_standard(const Aut &a)
Whether a is standard.
Definition: standard.hh:28
automaton add(const automaton &lhs, const automaton &rhs, const std::string &algo="auto")
Sum of two automata.
Definition: add.hh:124
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
automaton add(const automaton &lhs, const automaton &rhs, const std::string &algo)
Bridge.
Definition: add.hh:124
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:213
weight add_weight(const weight &lhs, const weight &rhs)
Bridge (add).
Definition: add.hh:230