Vcsn  2.3
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 
99 #undef DEFINE
100 
101  using tuple_t = typename super_t::tuple_t;
102 
103  template <bool = context_t::is_lat,
104  typename Dummy = void>
105  struct visit_tuple
106  {
107  using tupleset_t = typename expressionset_t::template as_tupleset_t<>;
109  bool operator()(const tuple_t& lhs)
110  {
111  return operator()(lhs,
112  *down_pointer_cast<const tuple_t>(visitor_.rhs_));
113  }
114 
116  bool operator()(const tuple_t& lhs, const tuple_t& rhs)
117  {
118  return tupleset_t::less(lhs.sub(), rhs.sub());
119  }
120 
121  const less& visitor_;
122  };
123 
124  template <typename Dummy>
125  struct visit_tuple<false, Dummy>
126  {
127  bool operator()(const tuple_t&)
128  {
130  }
132  };
133 
134  void visit(const tuple_t& v, std::true_type) override
135  {
136  res_ = visit_tuple<>{*this}(v);
137  }
138 
139  /*-------------------------------------------------------.
140  | Binary functions that compare two nodes of same type. |
141  `-------------------------------------------------------*/
142 
143  bool less_(const zero_t&, const zero_t&)
144  {
145  return false;
146  }
147 
148  bool less_(const one_t&, const one_t&)
149  {
150  return false;
151  }
152 
153  bool less_(const atom_t& lhs, const atom_t& rhs)
154  {
155  return labelset_t::less(lhs.value(), rhs.value());
156  }
157 
158  template <rat::exp::type_t Type>
159  bool less_(const variadic_t<Type>& lhs, const variadic_t<Type>& rhs)
160  {
161  using boost::range::lexicographical_compare;
162  auto ls = lhs.size();
163  auto rs = rhs.size();
164  if (ls < rs)
165  return true;
166  else if (rs < ls)
167  return false;
168  else
169  return lexicographical_compare(lhs, rhs,
171  }
172 
173  template <rat::exp::type_t Type>
174  bool less_(const unary_t<Type>& lhs, const unary_t<Type>& rhs)
175  {
176  return expressionset_t::less(lhs.sub(), rhs.sub());
177  }
178 
179  template <rat::exp::type_t Type>
180  bool less_(const weight_node_t<Type>& lhs, const weight_node_t<Type>& rhs)
181  {
182  // Lexicographic comparison on sub-expression, and then weight.
183  if (expressionset_t::less(lhs.sub(), rhs.sub()))
184  return true;
185  else if (expressionset_t::less(rhs.sub(), lhs.sub()))
186  return false;
187  else
188  return weightset_t::less(lhs.weight(), rhs.weight());
189  }
190 
191  private:
196  bool res_;
197  };
198  }
199 }
return v
Definition: multiply.hh:361
#define DEFINE(Type)
Definition: less.hh:78
bool less_(const one_t &, const one_t &)
Definition: less.hh:148
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
bool operator()(expression_t lhs, expression_t rhs)
Whether lhs < rhs.
Definition: less.hh:47
typename super_t::template weight_node_t< Type > weight_node_t
Definition: less.hh:39
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
weightset_t_of< context_t > weightset_t
Definition: less.hh:28
typename super_t::template unary_t< Type > unary_t
Definition: less.hh:35
bool less_(const variadic_t< Type > &lhs, const variadic_t< Type > &rhs)
Definition: less.hh:159
typename expressionset_t::const_visitor super_t
Definition: less.hh:31
ExpSet expressionset_t
Definition: less.hh:25
bool operator()(const tuple_t &lhs)
Entry point: down_cast rhs_ and bounce to binary operator().
Definition: less.hh:109
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
A functor to check whether one rational expression is (strictly) less than another one...
Definition: less.hh:21
An inner node implementing a weight.
Definition: expression.hh:264
typename super_t::template variadic_t< Type > variadic_t
Definition: less.hh:37
expression_t rhs_
The right-hand side expression with which the current node is compared.
Definition: less.hh:194
auto rs
Definition: lift.hh:152
Definition: a-star.hh:8
bool res_
The current result.
Definition: less.hh:196
typename super_t::inner_t inner_t
Definition: less.hh:33
bool less_(const atom_t &lhs, const atom_t &rhs)
Definition: less.hh:153
const less & visitor_
Definition: less.hh:121
void visit(const tuple_t &v, std::true_type) override
Definition: less.hh:134
Functor to compare Values of ValueSets.
Definition: functional.hh:76
typename super_t::tuple_t tuple_t
Definition: less.hh:101
bool less_(const zero_t &, const zero_t &)
Definition: less.hh:143
decltype(std::declval< LabelSet >().one()) one_t
Definition: labelset.hh:34
typename super_t::node_t node_t
Definition: less.hh:32
typename expressionset_t::value_t expression_t
Definition: less.hh:30
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
An inner node with multiple children.
Definition: expression.hh:118
typename expressionset_t::template as_tupleset_t<> tupleset_t
Definition: less.hh:107
weight_t_of< context_t > weight_t
Definition: less.hh:29
bool less_(const unary_t< Type > &lhs, const unary_t< Type > &rhs)
Definition: less.hh:174
bool operator()(const tuple_t &lhs, const tuple_t &rhs)
Binary operator().
Definition: less.hh:116
labelset_t_of< context_t > labelset_t
Definition: less.hh:27
bool less_(const weight_node_t< Type > &lhs, const weight_node_t< Type > &rhs)
Definition: less.hh:180
context_t_of< expressionset_t > context_t
Definition: less.hh:26