Vcsn  2.2
Be Rational
less.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/range/algorithm/lexicographical_compare.hpp>
4 
5 #include <vcsn/core/rat/fwd.hh>
6 #include <vcsn/core/rat/size.hh>
8 #include <vcsn/misc/cast.hh>
9 #include <vcsn/misc/functional.hh> // vcsn::less
10 
11 namespace vcsn
12 {
13 
14  namespace rat
15  {
16 
20  template <typename ExpSet>
21  class less
22  : public ExpSet::const_visitor
23  {
24  public:
25  using expressionset_t = ExpSet;
30  using expression_t = typename expressionset_t::value_t;
31  using super_t = typename expressionset_t::const_visitor;
32  using node_t = typename super_t::node_t;
33  using inner_t = typename super_t::inner_t;
34  template <rat::exp::type_t Type>
35  using unary_t = typename super_t::template unary_t<Type>;
36  template <rat::exp::type_t Type>
37  using variadic_t = typename super_t::template variadic_t<Type>;
38  template <rat::exp::type_t Type>
39  using weight_node_t = typename super_t::template weight_node_t<Type>;
40 
48  {
49  if (lhs == rhs)
50  return false;
51  else
52  {
53  size_t lhss = size<ExpSet>(lhs);
54  size_t rhss = size<ExpSet>(rhs);
55 
56  if (lhss < rhss)
57  return true;
58  else if (lhss > rhss)
59  return false;
60  else if (lhs->type() < rhs->type())
61  return true;
62  else if (lhs->type() > rhs->type())
63  return false;
64  else
65  {
66  rhs_ = rhs;
67  lhs->accept(*this);
68  return res_;
69  }
70  }
71  }
72 
73  private:
74  /*-----------------------------------------------------------.
75  | Unary visit functions than bounces to their binary peers. |
76  `-----------------------------------------------------------*/
77 
78 #define DEFINE(Type) \
79  VCSN_RAT_VISIT(Type, lhs) \
80  { \
81  res_ = less_(lhs, *down_pointer_cast<const Type ## _t>(rhs_)); \
82  }
83 
98 #undef DEFINE
99 
100  using tuple_t = typename super_t::tuple_t;
101 
102  template <bool = context_t::is_lat,
103  typename Dummy = void>
104  struct visit_tuple
105  {
106  using tupleset_t = typename expressionset_t::template as_tupleset_t<>;
108  bool operator()(const tuple_t& lhs)
109  {
110  return operator()(lhs,
111  *down_pointer_cast<const tuple_t>(visitor_.rhs_));
112  }
113 
115  bool operator()(const tuple_t& lhs, const tuple_t& rhs)
116  {
117  return tupleset_t::less(lhs.sub(), rhs.sub());
118  }
119 
120  const less& visitor_;
121  };
122 
123  template <typename Dummy>
124  struct visit_tuple<false, Dummy>
125  {
126  bool operator()(const tuple_t&)
127  {
129  }
131  };
132 
133  void visit(const tuple_t& v, std::true_type) override
134  {
135  res_ = visit_tuple<>{*this}(v);
136  }
137 
138  /*-------------------------------------------------------.
139  | Binary functions that compare two nodes of same type. |
140  `-------------------------------------------------------*/
141 
142  bool less_(const zero_t&, const zero_t&)
143  {
144  return false;
145  }
146 
147  bool less_(const one_t&, const one_t&)
148  {
149  return false;
150  }
151 
152  bool less_(const atom_t& lhs, const atom_t& rhs)
153  {
154  return labelset_t::less(lhs.value(), rhs.value());
155  }
156 
157  template <rat::exp::type_t Type>
158  bool less_(const variadic_t<Type>& lhs, const variadic_t<Type>& rhs)
159  {
160  using boost::range::lexicographical_compare;
161  auto ls = lhs.size();
162  auto rs = rhs.size();
163  if (ls < rs)
164  return true;
165  else if (rs < ls)
166  return false;
167  else
168  return lexicographical_compare(lhs, rhs,
170  }
171 
172  template <rat::exp::type_t Type>
173  bool less_(const unary_t<Type>& lhs, const unary_t<Type>& rhs)
174  {
175  return expressionset_t::less(lhs.sub(), rhs.sub());
176  }
177 
178  template <rat::exp::type_t Type>
179  bool less_(const weight_node_t<Type>& lhs, const weight_node_t<Type>& rhs)
180  {
181  // Lexicographic comparison on sub-expression, and then weight.
182  if (expressionset_t::less(lhs.sub(), rhs.sub()))
183  return true;
184  else if (expressionset_t::less(rhs.sub(), lhs.sub()))
185  return false;
186  else
187  return weightset_t::less(lhs.weight(), rhs.weight());
188  }
189 
190  private:
195  bool res_;
196  };
197  }
198 }
typename super_t::template unary_t< Type > unary_t
Definition: less.hh:35
bool res_
The current result.
Definition: less.hh:195
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
bool operator()(const tuple_t &lhs)
Entry point: down_cast rhs_ and bounce to binary operator().
Definition: less.hh:108
decltype(std::declval< LabelSet >().one()) one_t
Definition: labelset.hh:33
bool operator()(const tuple_t &lhs, const tuple_t &rhs)
Binary operator().
Definition: less.hh:115
labelset_t_of< context_t > labelset_t
Definition: less.hh:27
A functor to check whether one rational expression is (strictly) less than another one...
Definition: less.hh:21
expression_t rhs_
The right-hand side expression with which the current node is compared.
Definition: less.hh:193
Definition: a-star.hh:8
#define DEFINE(Type)
Definition: less.hh:78
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
typename super_t::template variadic_t< Type > variadic_t
Definition: less.hh:37
An inner node with multiple children.
Definition: expression.hh:118
bool less_(const variadic_t< Type > &lhs, const variadic_t< Type > &rhs)
Definition: less.hh:158
const less & visitor_
Definition: less.hh:120
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:58
weightset_t_of< context_t > weightset_t
Definition: less.hh:28
bool less_(const unary_t< Type > &lhs, const unary_t< Type > &rhs)
Definition: less.hh:173
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
context_t_of< expressionset_t > context_t
Definition: less.hh:26
weight_t_of< context_t > weight_t
Definition: less.hh:29
bool less_(const weight_node_t< Type > &lhs, const weight_node_t< Type > &rhs)
Definition: less.hh:179
bool less_(const zero_t &, const zero_t &)
Definition: less.hh:142
auto rs
Definition: lift.hh:151
typename expressionset_t::template as_tupleset_t<> tupleset_t
Definition: less.hh:106
typename super_t::inner_t inner_t
Definition: less.hh:33
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
typename super_t::template weight_node_t< Type > weight_node_t
Definition: less.hh:39
ExpSet expressionset_t
Definition: less.hh:25
typename super_t::node_t node_t
Definition: less.hh:32
typename expressionset_t::const_visitor super_t
Definition: less.hh:31
bool less_(const one_t &, const one_t &)
Definition: less.hh:147
An inner node implementing a weight.
Definition: expression.hh:264
bool operator()(expression_t lhs, expression_t rhs)
Whether lhs < rhs.
Definition: less.hh:47
typename super_t::tuple_t tuple_t
Definition: less.hh:100
void visit(const tuple_t &v, std::true_type) override
Definition: less.hh:133
typename expressionset_t::value_t expression_t
Definition: less.hh:30
bool less_(const atom_t &lhs, const atom_t &rhs)
Definition: less.hh:152
Functor to compare Values of ValueSets.
Definition: functional.hh:78