Vcsn  2.2
Be Rational
split.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #include <vcsn/ctx/fwd.hh>
5 #include <vcsn/dyn/polynomial.hh>
6 #include <vcsn/dyn/expression.hh>
7 #include <vcsn/misc/raise.hh>
9 
10 namespace vcsn
11 {
12 
13  namespace rat
14  {
15  // FIXME: this is a general feature which is useful elsewhere.
16  // E.g., expand.
17 
19  template <typename ExpSet>
21  = polynomialset<context<ExpSet,
23 
25  template <typename ExpSet>
28 
30  template <typename ExpSet>
31  inline
34  {
35  using context_t = context<ExpSet,
37  return context_t{rs, *rs.weightset()};
38  }
39  }
40 
41 
42  /*---------------------.
43  | split(expression). |
44  `---------------------*/
45 
46  namespace rat
47  {
76  template <typename ExpSet>
78  : public ExpSet::const_visitor
79  {
80  public:
81  using expressionset_t = ExpSet;
85  using expression_t = typename expressionset_t::value_t;
87  using weight_t = typename weightset_t::value_t;
88 
91 
92  using super_t = typename expressionset_t::const_visitor;
93 
95  constexpr static const char* me() { return "split"; }
96 
98  : rs_(rs)
99  {}
100 
103  {
104  return split(v);
105  }
106 
109  {
110  v->accept(*this);
111  return std::move(res_);
112  }
113 
115  {
116  res_ = ps_.zero();
117  }
118 
120  {
121  res_ = polynomial_t{{rs_.one(), ws_.one()}};
122  }
123 
125  {
126  res_ = polynomial_t{{rs_.atom(e.value()), ws_.one()}};
127  }
128 
130  {
131  polynomial_t res = ps_.zero();
132  for (const auto& v: e)
133  {
134  v->accept(*this);
135  ps_.add_here(res, res_);
136  }
137  res_ = std::move(res);
138  }
139 
145  {
146  // B(l).
147  polynomial_t l_split = split(l);
148  // constant-term(B(l)).
149  weight_t l_split_const = ps_.get_weight(l_split, rs_.one());
150  // proper(B(l)).
151  ps_.del_weight(l_split, rs_.one());
152 
153  // res = proper(B(l)).r + constant-term(B(l))B(r).
154  return ps_.add(ps_.rmul_label(l_split, r),
155  ps_.lmul(l_split_const, split(r)));
156  }
157 
162  {
163  polynomial_t res;
164  for (const auto& m: l)
165  ps_.add_here(res, ps_.lmul(weight_of(m), product(label_of(m), r)));
166  return res;
167  }
168 
171  {
172  auto res = product(e[0], e[1]);
173  for (unsigned i = 2, n = e.size(); i < n; ++i)
174  res = product(res, e[i]);
175  res_ = std::move(res);
176  }
177 
183  {
184  // B(l).
185  polynomial_t l_split = split(l);
186  // constant-term(B(l)).
187  weight_t l_split_const = ps_.get_weight(l_split, rs_.one());
188  // proper(B(l)).
189  ps_.del_weight(l_split, rs_.one());
190 
191  // res = proper(B(l))&r.
192  polynomial_t res;
193  for (const auto& e: l_split)
194  ps_.add_here(res, rs_.conjunction(label_of(e), r), weight_of(e));
195  // res += constant-term(B(l))B(r)
196  ps_.add_here(res,
197  ps_.lmul(l_split_const, split(r)));
198  return res;
199  }
200 
205  {
206  polynomial_t res;
207  for (const auto& m: l)
208  ps_.add_here(res, ps_.lmul(weight_of(m), conjunction(label_of(m), r)));
209  return res;
210  }
211 
214  {
215  auto res = conjunction(e[0], e[1]);
216  for (unsigned i = 2, n = e.size(); i < n; ++i)
217  res = conjunction(res, e[i]);
218  res_ = std::move(res);
219  }
220 
226 
227  using tuple_t = typename super_t::tuple_t;
228  virtual void visit(const tuple_t&, std::true_type) override
229  {
230  raise(me(), ": tuple is not supported");
231  }
232 
234  {
235  res_ = polynomial_t{{e.shared_from_this(), ws_.one()}};
236  }
237 
239  {
240  e.sub()->accept(*this);
241  res_ = ps_.lmul(e.weight(), res_);
242  }
243 
245  {
246  e.sub()->accept(*this);
247  res_ = ps_.rmul(res_, e.weight());
248  }
249 
250  private:
253  weightset_t ws_ = *rs_.weightset();
257  };
258  }
259 
261  template <typename ExpSet>
262  inline
264  split(const ExpSet& rs, const typename ExpSet::value_t& e)
265  {
267  return split(e);
268  }
269 
270  namespace dyn
271  {
272  namespace detail
273  {
275  template <typename ExpSet>
276  polynomial
277  split(const expression& exp)
278  {
279  const auto& e = exp->as<ExpSet>();
280  const auto& rs = e.expressionset();
282  return make_polynomial(ps,
283  vcsn::split<ExpSet>(rs, e.expression()));
284  }
285  }
286  }
287 
289  template <typename PolynomialSet>
290  inline
291  typename PolynomialSet::value_t
292  split_polynomial(const PolynomialSet& ps,
293  const typename PolynomialSet::value_t& p)
294  {
295  using polynomial_t = typename PolynomialSet::value_t;
296  // This is a polynomial of rational expressions.
297  const auto& rs = *ps.labelset();
298  polynomial_t res;
299  for (const auto& m: p)
300  res = ps.add(res, ps.lmul(weight_of(m), split(rs, label_of(m))));
301  return res;
302  }
303 
305  template <typename ExpSet>
306  inline
307  rat::expression_polynomial_t<ExpSet>
309  {
311  }
312 
313  namespace dyn
314  {
315  namespace detail
316  {
318  template <typename PolynomialSet>
319  polynomial
321  {
322  const auto& p = poly->as<PolynomialSet>();
323  const auto& ps = p.polynomialset();
324  return make_polynomial
325  (ps,
326  vcsn::split_polynomial<PolynomialSet>(ps, p.polynomial()));
327  }
328  }
329  }
330 } // vcsn::
polynomial_t conjunction(const polynomial_t &l, const expression_t &r)
The split-product of l with r.
Definition: split.hh:204
virtual void visit(const tuple_t &, std::true_type) override
Definition: split.hh:228
polynomialset< context< ExpSet, weightset_t_of< ExpSet >>> expression_polynomialset_t
Type of PolynomialSet of expressions from the ExpSet type.
Definition: split.hh:22
typename expression_polynomialset_t< ExpSet >::value_t expression_polynomial_t
Type of polynomials of expressions from the ExpSet type.
Definition: split.hh:27
VCSN_RAT_VISIT(lweight, e)
Definition: split.hh:238
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:68
std::shared_ptr< const detail::polynomial_base > polynomial
Definition: fwd.hh:70
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
polynomial_t split(const expression_t &v)
Easy recursion.
Definition: split.hh:108
polynomial make_polynomial(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Definition: polynomial.hh:103
Definition: a-star.hh:8
polynomial split(const expression &exp)
Bridge.
Definition: split.hh:277
STL namespace.
typename expressionset_t::value_t expression_t
Definition: split.hh:85
PolynomialSet::value_t split_polynomial(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Split a polynomial of expressions, given the polynomialset.
Definition: split.hh:292
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
polynomialset_t ps_
Definition: split.hh:254
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
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
The weight of a welement.
Definition: wet.hh:154
VCSN_RAT_VISIT(rweight, e)
Definition: split.hh:244
weightset_mixin< detail::polynomialset_impl< Context, Kind >> polynomialset
Definition: fwd.hh:63
polynomial_t res_
The result.
Definition: split.hh:256
typename super_t::tuple_t tuple_t
Definition: split.hh:227
VCSN_RAT_VISIT(atom, e)
Definition: split.hh:124
std::shared_ptr< const detail::context_base > context
A dyn::context.
Definition: fwd.hh:43
typename weightset_t::value_t weight_t
Definition: split.hh:87
auto rs
Definition: lift.hh:151
polynomial_t product(const expression_t &l, const expression_t &r)
The split-product of l with r.
Definition: split.hh:144
polynomial split_polynomial(const polynomial &poly)
Bridge (split).
Definition: split.hh:320
weightset_t ws_
Shorthand to the weightset.
Definition: split.hh:253
VCSN_RAT_VISIT(prod, e)
Handle an n-ary product.
Definition: split.hh:170
labelset_t_of< context_t > labelset_t
Definition: split.hh:83
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
polynomial_t conjunction(const expression_t &l, const expression_t &r)
The split-product of l with r.
Definition: split.hh:182
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
typename expressionset_t::const_visitor super_t
Definition: split.hh:92
An inner node implementing a weight.
Definition: expression.hh:264
Break a rational expression into a polynomial.
Definition: split.hh:77
expressionset_t rs_
Definition: split.hh:251
split_visitor(const expressionset_t &rs)
Definition: split.hh:97
VCSN_RAT_VISIT(conjunction, e)
Handle an n-ary conjunction.
Definition: split.hh:213
weightset_t_of< expressionset_t > weightset_t
Definition: split.hh:86
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
VCSN_RAT_VISIT(star, e)
Definition: split.hh:233
polynomial_t product(const polynomial_t &l, const expression_t &r)
The split-product of l with r.
Definition: split.hh:161
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: split.hh:95
expression_polynomialset_t< ExpSet > make_expression_polynomialset(const ExpSet &rs)
From a ExpSet to its polynomialset.
Definition: split.hh:33
typename polynomialset_t::value_t polynomial_t
Definition: split.hh:90
context_t_of< expressionset_t > context_t
Definition: split.hh:82
polynomial_t operator()(const expression_t &v)
Break an expression into a polynomial.
Definition: split.hh:102
rat::expression_polynomial_t< ExpSet > split(const ExpSet &rs, const typename ExpSet::value_t &e)
Split an expression.
Definition: split.hh:264
label_t_of< context_t > label_t
Definition: split.hh:84