Vcsn  2.2
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/expression.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);
80  expression_t res = res_;
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 
97  using tuple_t = typename super_t::tuple_t;
98  virtual void visit(const tuple_t&, std::true_type) override
99  {
100  raise(me(), ": tuple is not supported");
101  }
102 
104  {
105  if (operation_ == box)
106  box_of(v);
107  else
108  dot_of(v);
109  }
110 
112  void box_of(const prod_t& v)
113  {
114  using detail::any_of;
115  if (any_of(v,
116  [this](const expression_t& n)
117  {
118  return ws_.is_zero(constant_term(rs_, n));
119  }))
120  {
121  // Some factor has a null constant-term.
122  operation_ = dot;
123  dot_of(v);
124  operation_ = box;
125  }
126  else
127  {
128  // All the factors have a non null constant-term.
129  v.head()->accept(*this);
130  expression_t res = res_;
131  for (auto c: v.tail())
132  {
133  c->accept(*this);
134  res = rs_.add(res, res_);
135  }
136  res_ = std::move(res);
137  }
138  }
139 
141  void dot_of(const prod_t& v)
142  {
143  v.head()->accept(*this);
144  expression_t res = res_;
145  for (auto c: v.tail())
146  {
147  c->accept(*this);
148  res = rs_.mul(res, res_);
149  }
150  res_ = std::move(res);
151  }
152 
154  {
155  if (operation_ == dot)
156  {
157  operation_ = box;
158  v.sub()->accept(*this);
159  res_ = rs_.star(res_);
160  res_ = rs_.lmul(ws_.star(constant_term(rs_, v.sub())), res_);
161  operation_ = dot;
162  }
163  else
164  {
165  v.sub()->accept(*this);
166  }
167  }
168 
169  private:
172  weightset_t ws_ = *rs_.weightset();
177  };
178 
179  } // rat::
180 
182  template <typename ExpSet>
183  inline
184  typename ExpSet::value_t
185  star_normal_form(const ExpSet& rs, const typename ExpSet::value_t& e)
186  {
188  return star_normal_form(e);
189  }
190 
191  namespace dyn
192  {
193  namespace detail
194  {
196  template <typename ExpSet>
197  inline
198  expression
200  {
201  const auto& e = exp->as<ExpSet>();
202  return make_expression(e.expressionset(),
203  ::vcsn::star_normal_form(e.expressionset(),
204  e.expression()));
205  }
206  }
207  }
208 
209 } // vcsn::
context_t_of< expressionset_t > context_t
void box_of(const prod_t &v)
Handling of a product by the box operator.
static constexpr const char * me()
Name of this algorithm, for error messages.
typename weightset_t::value_t weight_t
void dot_of(const prod_t &v)
Handling of a product by the dot operator.
operation_t
The type of the operator.
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:68
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
virtual void visit(const tuple_t &, std::true_type) override
bool any_of(const Range &r, Predicate p)
Definition: algorithm.hh:15
typename expressionset_t::value_t expression_t
expression_t operator()(const expression_t &v)
Definition: a-star.hh:8
weightset_t_of< context_t > weightset_t
STL namespace.
An inner node with multiple children.
Definition: expression.hh:118
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
star_normal_form_visitor(const expressionset_t &rs)
ExpSet::value_t star_normal_form(const ExpSet &rs, const typename ExpSet::value_t &e)
Star-normal form of an expression.
typename ExpSet::const_visitor super_t
auto rs
Definition: lift.hh:151
expression star_normal_form(const expression &exp)
Bridge.
weightset_t ws_
Shorthand to the weightset.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
An inner node implementing a weight.
Definition: expression.hh:264
operation_t operation_
The current operation.
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
typename super_t::tuple_t tuple_t
expression make_expression(const ExpSet &rs, const typename ExpSet::value_t &r)
Definition: expression.hh:97