Vcsn  2.4
Be Rational
star-normal-form.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/ctx/fwd.hh>
6 #include <vcsn/dyn/value.hh>
7 #include <vcsn/misc/algorithm.hh> // any_of
8 #include <vcsn/misc/raise.hh>
9 #include <vcsn/weightset/b.hh>
10 
11 namespace vcsn
12 {
13 
14  namespace rat
15  {
16 
17  /*--------------------------------.
18  | star_normal_form(expression). |
19  `--------------------------------*/
20 
27  template <typename ExpSet>
29  : public ExpSet::const_visitor
30  {
31  public:
32  using expressionset_t = ExpSet;
33  using expression_t = typename expressionset_t::value_t;
36  static_assert(std::is_same<weightset_t, b>::value,
37  "star_normal_form: requires Boolean weights");
38 
39  using weight_t = typename weightset_t::value_t;
40 
41  using super_t = typename ExpSet::const_visitor;
42 
44  constexpr static const char* me() { return "star_normal_form"; }
45 
47  enum operation_t { dot, box };
48 
50  : rs_(rs)
51  {}
52 
55  {
56  operation_ = dot;
57  v->accept(*this);
58  return std::move(res_);
59  }
60 
62  {
63  res_ = rs_.zero();
64  }
65 
67  {
68  res_ = operation_ == box ? rs_.zero() : rs_.one();
69  }
70 
72  {
73  res_ = rs_.atom(v.value());
74  }
75 
76  // Plain traversal for sums.
78  {
79  v.head()->accept(*this);
81  for (auto c: v.tail())
82  {
83  c->accept(*this);
84  res = rs_.add(res, res_);
85  }
86  res_ = std::move(res);
87  }
88 
98  using tuple_t = typename super_t::tuple_t;
99  void visit(const tuple_t&, std::true_type) override
100  {
101  raise(me(), ": tuple is not supported");
102  }
103 
105  {
106  if (operation_ == box)
107  box_of(v);
108  else
109  dot_of(v);
110  }
111 
113  void box_of(const mul_t& v)
114  {
115  using detail::any_of;
116  if (any_of(v,
117  [this](const expression_t& n)
118  {
119  return ws_.is_zero(constant_term(rs_, n));
120  }))
121  {
122  // Some factor has a null constant-term.
123  operation_ = dot;
124  dot_of(v);
125  operation_ = box;
126  }
127  else
128  {
129  // All the factors have a non null constant-term.
130  v.head()->accept(*this);
132  for (auto c: v.tail())
133  {
134  c->accept(*this);
135  res = rs_.add(res, res_);
136  }
137  res_ = std::move(res);
138  }
139  }
140 
142  void dot_of(const mul_t& v)
143  {
144  v.head()->accept(*this);
146  for (auto c: v.tail())
147  {
148  c->accept(*this);
149  res = rs_.mul(res, res_);
150  }
151  res_ = std::move(res);
152  }
153 
155  {
156  if (operation_ == dot)
157  {
158  operation_ = box;
159  v.sub()->accept(*this);
160  res_ = rs_.star(res_);
161  res_ = rs_.lweight(ws_.star(constant_term(rs_, v.sub())), res_);
162  operation_ = dot;
163  }
164  else
165  {
166  v.sub()->accept(*this);
167  }
168  }
169 
170  private:
173  weightset_t ws_ = *rs_.weightset();
178  };
179 
180  } // rat::
181 
183  template <typename ExpSet>
184  typename ExpSet::value_t
185  star_normal_form(const ExpSet& rs, const typename ExpSet::value_t& e)
186  {
188  return snf(e);
189  }
190 
191  namespace dyn
192  {
193  namespace detail
194  {
196  template <typename ExpSet>
197  expression
199  {
200  const auto& e = exp->as<ExpSet>();
201  return {e.valueset(), ::vcsn::star_normal_form(e.valueset(),
202  e.value())};
203  }
204  }
205  }
206 
207 } // vcsn::
STL namespace.
void dot_of(const mul_t &v)
Handling of a product by the dot operator.
typename weightset_t::value_t weight_t
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
bool any_of(const Range &r, Predicate p)
Definition: algorithm.hh:16
typename expressionset_t::value_t expression_t
An inner node implementing a weight.
Definition: expression.hh:255
weightset_t ws_
Shorthand to the weightset.
void visit(const tuple_t &, std::true_type) override
context_t_of< expressionset_t > context_t
Definition: a-star.hh:8
operation_t
The type of the operator.
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:74
expression_t operator()(const expression_t &v)
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
expression star_normal_form(const expression &exp)
Bridge.
An inner node with multiple children.
Definition: expression.hh:118
return v
Definition: multiply.hh:361
static constexpr const char * me()
Name of this algorithm, for error messages.
star_normal_form_visitor(const expressionset_t &rs)
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
ExpSet::value_t star_normal_form(const ExpSet &rs, const typename ExpSet::value_t &e)
Star-normal form of an expression.
operation_t operation_
The current operation.
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
void box_of(const mul_t &v)
Handling of a product by the box operator.
weightset_t_of< context_t > weightset_t
typename super_t::tuple_t tuple_t
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
typename ExpSet::const_visitor super_t