Vcsn  2.0
Be Rational
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
expansionset.hh
Go to the documentation of this file.
1 #ifndef VCSN_CORE_RAT_EXPANSIONSET_HH
2 # define VCSN_CORE_RAT_EXPANSIONSET_HH
3 
4 # include <vcsn/algos/split.hh> // ratexp_polynomialset_t.
5 # include <vcsn/misc/map.hh>
6 
7 namespace vcsn
8 {
9 
10  namespace rat
11  {
12 
13  /*---------------.
14  | expansionset. |
15  `---------------*/
16 
17  template <typename RatExpSet>
18  struct expansionset
19  {
20  public:
21  using ratexpset_t = RatExpSet;
25  using ratexp_t = typename ratexpset_t::value_t;
27  using weight_t = typename weightset_t::value_t;
28 
32 
33  constexpr static const char* me() { return "expansion"; }
34 
35  // Keep it sorted to ensure determinism, and better looking
36  // results. Anyway, rough benches show no difference between
37  // map and unordered_map here.
38  using polys_t = std::map<label_t, polynomial_t, vcsn::less<labelset_t>>;
39 
41  struct value_t
42  {
45  };
46 
48  : rs_(rs)
49  {}
50 
52  static std::string sname()
53  {
54  return "expansionset<" + ratexpset_t::sname() + ">";
55  }
56 
58  std::string vname(bool full = true) const
59  {
60  return "expansionset<" + rs_.vname(full) + ">";
61  }
62 
64  std::ostream& print(const value_t& v, std::ostream& o,
65  symbol format = symbol{"text"}) const
66  {
67  bool first = true;
68  if (!ws_.is_zero(v.constant) || v.polynomials.empty())
69  {
70  o << (format == "latex" ? "\\left\\langle " : "<");
71  ws_.print(v.constant, o, format);
72  o << (format == "latex" ? "\\right\\rangle " : ">");
73  first = false;
74  }
75  for (const auto& p: v.polynomials)
76  {
77  if (!first)
78  o << (format == "latex" ? " \\oplus " : " + ");
79  first = false;
80  rs_.labelset()->print(p.first, o, format);
81  o << (format == "latex" ? " \\odot \\left[" : ".[");;
82  ps_.print(p.second, o, format);
83  o << (format == "latex" ? "\\right]" : "]");;
84  }
85  return o;
86  }
87 
91  value_t& normalize_(value_t& res, std::true_type) const
92  {
93  auto one = rs_.labelset()->one();
94  auto i = res.polynomials.find(one);
95  if (i != std::end(res.polynomials))
96  {
97  auto j = i->second.find(rs_.one());
98  if (j != std::end(i->second))
99  {
100  res.constant = ws_.add(res.constant, j->second);
101  i->second.erase(j);
102  if (i->second.empty())
103  res.polynomials.erase(i);
104  }
105  }
106  return res;
107  }
108 
109  value_t& normalize_(value_t& res, std::false_type) const
110  {
111  return res;
112  }
113 
114  value_t& normalize(value_t& res) const
115  {
116  auto has_one = std::integral_constant<bool, context_t::has_one()>();
117  return normalize_(res, has_one);
118  }
119 
122  value_t& denormalize_(value_t& res, std::true_type) const
123  {
124  auto one = rs_.labelset()->one();
125  if (!ws_.is_zero(res.constant))
126  {
127  ps_.add_here(res.polynomials[one],
128  polynomial_t{{rs_.one(), res.constant}});
129  res.constant = ws_.zero();
130  }
131  return res;
132  }
133 
134  value_t& denormalize_(value_t& res, std::false_type) const
135  {
136  return res;
137  }
138 
139  value_t& denormalize(value_t& res) const
140  {
141  auto has_one = std::integral_constant<bool, context_t::has_one()>();
142  return denormalize_(res, has_one);
143  }
144 
146  value_t zero() const
147  {
148  return {ws_.zero(), polys_t{}};
149  }
150 
152  value_t one() const
153  {
154  return {ws_.one(), polys_t{}};
155  }
156 
158  value_t atom(const label_t& l) const
159  {
160  return {ws_.zero(), {{l, ps_.one()}}};
161  }
162 
164  void add_here(value_t& lhs, const value_t& rhs) const
165  {
166  lhs.constant = ws_.add(lhs.constant, rhs.constant);
167  for (const auto& p: rhs.polynomials)
168  ps_.add_here(lhs.polynomials[p.first], p.second);
169  }
170 
172  value_t& lmul_here(const weight_t& w, value_t& res) const
173  {
174  res.constant = ws_.mul(w, res.constant);
175  for (auto& p: res.polynomials)
176  p.second = ps_.lmul(w, p.second);
177  return res;
178  }
179 
181  value_t rmul(const value_t& lhs, const weight_t& w) const
182  {
183  value_t res = {ws_.mul(lhs.constant, w), polys_t{}};
184  for (auto& p: lhs.polynomials)
185  for (const auto& m: p.second)
186  ps_.add_here(res.polynomials[p.first],
187  rs_.rmul(m.first, w), m.second);
188  return res;
189  }
190 
192  value_t& rmul_here(value_t& res, const ratexp_t& rhs) const
193  {
194  for (auto& p: res.polynomials)
195  p.second = ps_.rmul(p.second, rhs);
196  return res;
197  }
198 
200  value_t& ldiv_here(const weight_t& w, value_t& res) const
201  {
202  res.constant = ws_.ldiv(w, res.constant);
203  for (auto& p: res.polynomials)
204  for (auto& m: p.second)
205  m.second = ws_.ldiv(w, m.second);
206  return normalize(res);
207  }
208 
209  void
211  const value_t&, const value_t&,
212  std::false_type) const
213  {}
214 
215  void
217  const value_t& l, const value_t& r,
218  std::true_type) const
219  {
220  // Spontaneous transitions from the lhs.
221  auto one = rs_.labelset()->one();
222  {
223  auto i = l.polynomials.find(one);
224  if (i != std::end(l.polynomials))
225  for (const auto& rhs: r.polynomials)
226  if (!rs_.labelset()->is_one(rhs.first))
227  ps_.add_here(res.polynomials[one],
228  ps_.conjunction(i->second,
229  ps_.lmul(rs_.atom(rhs.first),
230  rhs.second)));
231  }
232  // Spontaneous transitions from the rhs.
233  {
234  auto i = r.polynomials.find(one);
235  if (i != std::end(r.polynomials))
236  for (const auto& lhs: l.polynomials)
237  if (!rs_.labelset()->is_one(lhs.first))
238  ps_.add_here(res.polynomials[one],
239  ps_.conjunction(ps_.lmul(rs_.atom(lhs.first),
240  lhs.second),
241  i->second));
242  }
243  normalize(res);
244  }
245 
247  value_t conjunction(value_t l, value_t r) const
248  {
249  value_t res = zero();
250  denormalize(l);
251  denormalize(r);
252  res.constant = ws_.mul(l.constant, r.constant);
253  for (const auto& p: zip_maps(l.polynomials, r.polynomials))
254  res.polynomials[p.first]
255  = ps_.conjunction(std::get<0>(p.second), std::get<1>(p.second));
256 
257  auto has_one = std::integral_constant<bool, context_t::has_one()>();
258  conjunctions_with_one_(res, l, r, has_one);
259  return res;
260  }
261 
263  polynomial_t as_polynomial(const value_t& v) const
264  {
265  // FIXME: polynomial_t{{rs_.one(), constant}} is wrong,
266  // because the (default) ctor will not eliminate the monomial
267  // when constant is zero.
268  polynomial_t res;
269  ps_.add_here(res, rs_.one(), v.constant);
270  for (const auto& p: v.polynomials)
271  // We may add a label on our maps, and later map it to 0.
272  // In this case polynomialset builds '\z -> 1', i.e., it
273  // does insert \z as a label in the polynomial. Avoid this.
274  //
275  // FIXME: shouldn't polynomialset do that itself?
276  if (!ps_.is_zero(p.second))
277  ps_.add_here(res,
278  rs_.mul(rs_.atom(p.first), as_ratexp(p.second)),
279  ws_.one());
280  return res;
281  }
282 
283  // FIXME: duplicate with expand.
285  {
286  ratexp_t res = rs_.zero();
287  for (const auto& m: p)
288  res = rs_.add(res, rs_.lmul(m.second, m.first));
289  return res;
290  }
291 
292  private:
296  weightset_t ws_ = *rs_.weightset();
299  };
300  }
301 }
302 
303 #endif // !VCSN_CORE_RAT_EXPANSIONSET_HH
Linear combination of labels: map labels to weights.
Definition: fwd.hh:32
value_t & add_here(value_t &v, const value_t &p) const
v += p.
value_t & rmul_here(value_t &res, const ratexp_t &rhs) const
In place right multiplication by a ratexp.
ratexp_polynomialset_t< RatExpSet > make_ratexp_polynomialset(const RatExpSet &rs)
From a RatExpSet to its polynomialset.
Definition: split.hh:34
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:34
typename polynomialset_t::monomial_t monomial_t
Definition: expansionset.hh:31
typename weightset_t::value_t weight_t
Definition: expansionset.hh:27
void conjunctions_with_one_(value_t &, const value_t &, const value_t &, std::false_type) const
static constexpr const char * me()
Definition: expansionset.hh:33
value_t & normalize_(value_t &res, std::false_type) const
value_t & denormalize(value_t &res) const
polynomialset_t ps_
The polynomialset for the polynomials.
boost::flyweight< std::string, boost::flyweights::no_tracking > symbol
An internalized string.
Definition: symbol.hh:24
std::string sname()
Definition: name.hh:31
value_t conjunction(value_t l, value_t r) const
The conjunction of l and r.
value_t & normalize(value_t &res) const
value_t & lmul_here(const weight_t &w, value_t &res) const
Inplace left-multiplication by w of res.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:32
void add_here(value_t &lhs, const value_t &rhs) const
In place addition.
typename value_t::value_type monomial_t
A pair .
weightset_t ws_
Shorthand to the weightset.
static std::string sname()
The static name.
Definition: expansionset.hh:52
value_t & ldiv_here(const weight_t &w, value_t &res) const
Inplace left-division by w of res.
value_t & denormalize_(value_t &res, std::false_type) const
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:33
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:38
value_t rmul(const value_t &lhs, const weight_t &w) const
Right-multiplication of lhs by w.
std::map< label_t, polynomial_t, vcsn::less< labelset_t >> polys_t
Definition: expansionset.hh:38
std::string vname(bool full=true) const
The dynamic name.
Definition: expansionset.hh:58
std::ostream & print(const monomial_t &m, std::ostream &out, symbol format=symbol{"text"}) const
Print a monomial.
typename ratexpset_t::value_t ratexp_t
Definition: expansionset.hh:25
value_t atom(const label_t &l) const
A single label.
constant< type_t::zero, Context > zero
Definition: fwd.hh:97
auto normalize(const Aut &a) -> decltype(copy(a))
Normalize a automaton.
Definition: normalize.hh:21
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:36
polynomial_t as_polynomial(const value_t &v) const
Convert an expansion to a polynomial.
weightset_t_of< ratexpset_t > weightset_t
Definition: expansionset.hh:26
ratexpset_t rs_
The ratexpset used for the expressions.
std::map< label_t, weight_t, vcsn::less< labelset_t >> value_t
value_t & denormalize_(value_t &res, std::true_type) const
Denormalize res move the constant to the polynomial associated to one.
context_t_of< ratexpset_t > context_t
Definition: expansionset.hh:22
value_t zero() const
The zero.
zipped_maps< Dereference, Maps...> zip_maps(Maps &&...maps)
Definition: zip-maps.hh:257
void conjunctions_with_one_(value_t &res, const value_t &l, const value_t &r, std::true_type) const
value_t one() const
The one.
std::ostream & print(const value_t &v, std::ostream &o, symbol format=symbol{"text"}) const
Print a first order development.
Definition: expansionset.hh:64
ratexp_t as_ratexp(const polynomial_t &p) const
typename polynomialset_t::value_t polynomial_t
Definition: expansionset.hh:30
expansionset(const ratexpset_t &rs)
Definition: expansionset.hh:47
value_t & normalize_(value_t &res, std::true_type) const
Normalize res: There must not remain a constant-term associated to one: put it with the constant term...
Definition: expansionset.hh:91
labelset_t_of< context_t > labelset_t
Definition: expansionset.hh:23