Vcsn  2.2
Be Rational
star-height.hh
Go to the documentation of this file.
1 #pragma once
2 
4 
5 namespace vcsn
6 {
7  namespace detail
8  {
9  template <typename ExpSet>
11  : public ExpSet::const_visitor
12  {
13  public:
14  using expressionset_t = ExpSet;
15  using super_t = typename expressionset_t::const_visitor;
16  using node_t = typename super_t::node_t;
17 
19  constexpr static const char* me() { return "star_height"; }
20 
22  unsigned
24  {
25  height_ = 0;
26  v.accept(*this);
27  return height_;
28  }
29 
31  unsigned
32  operator()(const std::shared_ptr<const node_t>& v)
33  {
34  return operator()(*v);
35  }
36 
37  private:
38 
39  VCSN_RAT_VISIT(atom,) {}
40  VCSN_RAT_VISIT(complement, v) { visit_(v); }
41  VCSN_RAT_VISIT(conjunction, v) { visit_(v); }
42  VCSN_RAT_VISIT(infiltration, v) { visit_(v); }
43  VCSN_RAT_VISIT(ldiv, v) { visit_(v); }
44  VCSN_RAT_VISIT(lweight, v) { v.sub()->accept(*this); }
45  VCSN_RAT_VISIT(one,) {}
46  VCSN_RAT_VISIT(prod, v) { visit_(v); }
47  VCSN_RAT_VISIT(rweight, v) { v.sub()->accept(*this); }
48  VCSN_RAT_VISIT(shuffle, v) { visit_(v); }
49  VCSN_RAT_VISIT(star, v) { ++height_; visit_(v); }
50  VCSN_RAT_VISIT(sum, v) { visit_(v); }
51  VCSN_RAT_VISIT(transposition, v){ visit_(v); }
52  VCSN_RAT_VISIT(zero,) {}
53 
54  template <rat::type_t Type>
55  using unary_t = typename super_t::template unary_t<Type>;
56 
58  template <rat::exp::type_t Type>
59  void visit_(const unary_t<Type>& v)
60  {
61  v.sub()->accept(*this);
62  }
63 
64  template <rat::type_t Type>
65  using variadic_t = typename super_t::template variadic_t<Type>;
66 
68  template <rat::type_t Type>
69  void visit_(const variadic_t<Type>& n)
70  {
71  /* The height of an n-ary is the max of the n heights. */
72  auto max = height_;
73  auto initial = height_;
74  for (auto child : n)
75  {
76  height_ = initial;
77  child->accept(*this);
78  if (max < height_)
79  max = height_;
80  }
81  height_ = max;
82  }
83 
84  using tuple_t = typename super_t::tuple_t;
85  virtual void visit(const tuple_t&, std::true_type) override
86  {
87  raise(me(), ": tuple is not supported");
88  }
89 
91  unsigned height_;
92  };
93  } // namespace detail
94 
95 
97  template <typename ExpSet>
98  inline
99  unsigned
100  star_height(const typename ExpSet::value_t& e)
101  {
103  return s(e);
104  }
105 
106  namespace dyn
107  {
108  namespace detail
109  {
111  template <typename ExpSet>
112  unsigned
114  {
115  const auto& e = exp->as<ExpSet>();
116  return ::vcsn::star_height<ExpSet>(e.expression());
117  }
118  }
119  }
120 } // namespace vcsn
unsigned operator()(const node_t &v)
Entry point: return the size of v.
Definition: star-height.hh:23
void visit_(const variadic_t< Type > &n)
Traverse variadic node.
Definition: star-height.hh:69
typename super_t::tuple_t tuple_t
Definition: star-height.hh:84
Definition: a-star.hh:8
unsigned height_
The current star height.
Definition: star-height.hh:91
void visit_(const unary_t< Type > &v)
Traverse unary node.
Definition: star-height.hh:59
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: star-height.hh:19
unsigned operator()(const std::shared_ptr< const node_t > &v)
Entry point: return the size of v.
Definition: star-height.hh:32
virtual void visit(const tuple_t &, std::true_type) override
Definition: star-height.hh:85
VCSN_RAT_VISIT(conjunction, v)
Definition: star-height.hh:41
VCSN_RAT_VISIT(infiltration, v)
Definition: star-height.hh:42
VCSN_RAT_VISIT(complement, v)
Definition: star-height.hh:40
typename super_t::template variadic_t< Type > variadic_t
Definition: star-height.hh:65
unsigned star_height(const expression &exp)
Bridge.
Definition: star-height.hh:113
typename expressionset_t::const_visitor super_t
Definition: star-height.hh:15
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
VCSN_RAT_VISIT(transposition, v)
Definition: star-height.hh:51
unsigned star_height(const typename ExpSet::value_t &e)
Star height of an expression.
Definition: star-height.hh:100
typename super_t::node_t node_t
Definition: star-height.hh:16
typename super_t::template unary_t< Type > unary_t
Definition: star-height.hh:55