Vcsn  2.3
Be Rational
q.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <ostream>
4 #include <string>
5 
6 #include <vcsn/core/join.hh>
7 #include <vcsn/misc/format.hh>
8 #include <vcsn/misc/functional.hh> // hash_combine
9 #include <vcsn/misc/math.hh>
10 #include <vcsn/misc/raise.hh>
11 #include <vcsn/misc/star-status.hh>
12 #include <vcsn/misc/stream.hh> // eat
13 #include <vcsn/misc/symbol.hh>
14 #include <vcsn/weightset/b.hh>
15 #include <vcsn/weightset/fwd.hh>
17 #include <vcsn/weightset/z.hh>
18 
19 namespace vcsn
20 {
21  namespace detail
22  {
23  class q_impl
24  {
25  public:
26  using self_t = q;
27 
28  static symbol sname()
29  {
30  static auto res = symbol{"q"};
31  return res;
32  }
33 
35  static q make(std::istream& is)
36  {
37  eat(is, sname());
38  return {};
39  }
40 
41  struct value_t
42  {
43  value_t(int n = 0, unsigned d = 1)
44  : num(n)
45  , den(d)
46  {}
47 
50  {
51  int gc = gcd(abs(num), den);
52  num /= gc;
53  den /= gc;
54  return *this;
55  }
56 
57  int num;
58  unsigned int den;
59  };
60 
61  static unsigned int abs(int a)
62  {
63  return a < 0 ? -a : a;
64  }
65 
66  static value_t zero()
67  {
68  return value_t{0, 1};
69  }
70 
71  static value_t one()
72  {
73  return value_t{1, 1};
74  }
75 
76  static value_t add(const value_t l, const value_t r)
77  {
78  unsigned int cm = lcm(l.den, abs(r.den));
79  return value_t{l.num * int (cm / l.den) + r.num * int (cm / r.den),
80  cm}.reduce();
81  }
82 
83  static value_t sub(const value_t l, const value_t r)
84  {
85  unsigned int cm = lcm(l.den, abs(r.den));
86  return value_t{l.num * int (cm / l.den) - r.num * int (cm / r.den),
87  cm}.reduce();
88  }
89 
90  static value_t mul(const value_t l, const value_t r)
91  {
92  return value_t{l.num * r.num, l.den * r.den}.reduce();
93  }
94 
96  value_t
97  lgcd(const value_t l, const value_t r) const
98  {
99  require(!is_zero(l), *this, ": lgcd: invalid lhs: zero");
100  require(!is_zero(r), *this, ": lgcd: invalid rhs: zero");
101  return l;
102  }
103 
104  value_t
105  rgcd(const value_t l, const value_t r) const
106  {
107  return lgcd(l, r);
108  }
109 
110  value_t
111  rdivide(const value_t l, const value_t r) const
112  {
113  require(!is_zero(r), *this, ": div: division by zero");
114  if (0 < r.num)
115  return value_t{l.num * int(r.den), l.den * r.num}.reduce();
116  else
117  return value_t{-l.num * int(r.den), l.den * -r.num}.reduce();
118  }
119 
120  value_t
121  ldivide(const value_t l, const value_t r) const
122  {
123  return rdivide(r, l);
124  }
125 
126  value_t star(const value_t v) const
127  {
128  if (abs(v.num) < v.den)
129  // No need to reduce: numerator and denominator are coprime.
130  return {int(v.den), v.den - v.num};
131  else
132  raise_not_starrable(*this, v);
133  }
134 
135  static bool is_special(const value_t) // C++11: cannot be constexpr.
136  {
137  return false;
138  }
139 
140  static bool is_zero(const value_t v)
141  {
142  return v.num == 0;
143  }
144 
145  static bool is_one(const value_t v)
146  {
147  // All values are normalized.
148  return v.num == 1 && v.den == 1;
149  }
150 
151  static bool equal(const value_t l, const value_t r)
152  {
153  return l.num == r.num && l.den == r.den;
154  }
155 
157  static bool less(const value_t lhs, const value_t rhs)
158  {
159  return lhs.num * static_cast<long>(rhs.den)
160  < rhs.num * static_cast<long>(lhs.den);
161  }
162 
163  static constexpr bool is_commutative() { return true; }
164  static constexpr bool has_lightening_weights() { return true; }
165 
166  static constexpr bool show_one() { return false; }
167  static constexpr star_status_t star_status() { return star_status_t::ABSVAL; }
168 
169  static value_t
170  abs(const value_t v)
171  {
172  return v.num < 0 ? (value_t{-v.num, v.den}) : v;
173  }
174 
175  static value_t
177  {
178  return v;
179  }
180 
181  static size_t hash(const value_t v)
182  {
183  size_t res = 0;
184  hash_combine(res, hash_value(v.num));
185  hash_combine(res, hash_value(v.den));
186  return res;
187  }
188 
189  static value_t
191  {
192  return v;
193  }
194 
195  static value_t
196  conv(z, const z::value_t v)
197  {
198  return {v, 1};
199  }
200 
201  static value_t
202  conv(b, const b::value_t v)
203  {
204  return {v, 1};
205  }
206 
207  value_t
208  conv(std::istream& i, bool = true) const
209  {
210  int num;
211  if (!(i >> num))
212  raise(*this, ": invalid numerator: ", i);
213 
214  // If we have a slash after the numerator then we have a
215  // denominator as well.
216  if (i.peek() == '/')
217  {
218  eat(i, '/');
219 
220  // operator>> with an istream and an unsigned int silently
221  // mangles a negative number into its two's complement
222  // representation as a positive number.
223  if (i.peek() == '-')
224  {
225  num = - num;
226  eat(i, '-');
227  }
228 
229  unsigned int den;
230  if (!(i >> den))
231  raise(*this, ": invalid denominator: ", i);
232  // Make sure our rational respects our constraints.
233  require(den, *this, ": null denominator");
234  return value_t{num, den}.reduce();
235  }
236  else
237  return value_t{num, 1};
238  }
239 
240  static std::ostream&
241  print(const value_t v, std::ostream& o = std::cout,
242  format fmt = {})
243  {
244  if (fmt == format::latex)
245  {
246  if (v.den == 1)
247  o << v.num;
248  else
249  o << "\\frac{" << v.num << "}{" << v.den << '}';
250  }
251  else
252  {
253  o << v.num;
254  if (v.den != 1)
255  o << '/' << v.den;
256  }
257  return o;
258  }
259 
260  std::ostream&
261  print_set(std::ostream& o, format fmt = {}) const
262  {
263  switch (fmt.kind())
264  {
265  case format::latex:
266  o << "\\mathbb{Q}";
267  break;
268  case format::sname:
269  o << sname();
270  break;
271  case format::text:
272  o << "Q";
273  break;
274  case format::utf8:
275  o << "ℚ";
276  break;
277  case format::raw:
278  assert(0);
279  break;
280  }
281  return o;
282  }
283  };
284 
285  /*-------.
286  | join. |
287  `-------*/
288 
289  VCSN_JOIN_SIMPLE(b, q);
290  VCSN_JOIN_SIMPLE(z, q);
291  VCSN_JOIN_SIMPLE(q, q);
292  }
293 }
static value_t transpose(const value_t v)
Definition: q.hh:176
static bool less(const value_t lhs, const value_t rhs)
Whether lhs < rhs.
Definition: q.hh:157
weightset_mixin< detail::q_impl > q
Definition: fwd.hh:52
static std::ostream & print(const value_t v, std::ostream &o=std::cout, format fmt={})
Definition: q.hh:241
static value_t zero()
Definition: q.hh:66
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
unsigned int den
Definition: q.hh:58
star_status_t
Definition: star-status.hh:5
static unsigned int abs(int a)
Definition: q.hh:61
static bool is_special(const value_t)
Definition: q.hh:135
static constexpr bool is_commutative()
Definition: q.hh:163
ATTRIBUTE_NORETURN void raise_not_starrable(const WeightSet &ws, const typename WeightSet::value_t &w)
This value is not starrable.
Definition: raise.hh:100
static bool is_one(const value_t v)
Definition: q.hh:145
ATTRIBUTE_PURE unsigned int lcm(unsigned int a, unsigned int b)
Lowest common multiple.
Definition: math.hh:28
Print as a parsable type string.
Definition: format.hh:26
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
return res
Definition: multiply.hh:398
static value_t conv(b, const b::value_t v)
Definition: q.hh:202
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
Definition: functional.hh:30
static value_t mul(const value_t l, const value_t r)
Definition: q.hh:90
static constexpr star_status_t star_status()
Definition: q.hh:167
static bool equal(const value_t l, const value_t r)
Definition: q.hh:151
static value_t add(const value_t l, const value_t r)
Definition: q.hh:76
value_t(int n=0, unsigned d=1)
Definition: q.hh:43
VCSN_JOIN_SIMPLE(b, b)
value_t lgcd(const value_t l, const value_t r) const
GCD: arbitrarily the first argument.
Definition: q.hh:97
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: q.hh:261
Definition: a-star.hh:8
static q make(std::istream &is)
Build from the description in is.
Definition: q.hh:35
static value_t sub(const value_t l, const value_t r)
Definition: q.hh:83
An input/output format for valuesets.
Definition: format.hh:13
static value_t conv(self_t, const value_t v)
Definition: q.hh:190
Print as is. For instance, don't try to escape labels.
Definition: format.hh:24
static size_t hash(const value_t v)
Definition: q.hh:181
value_t ldivide(const value_t l, const value_t r) const
Definition: q.hh:121
value_t star(const value_t v) const
Definition: q.hh:126
static value_t conv(z, const z::value_t v)
Definition: q.hh:196
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
void hash_combine(std::size_t &seed, const T &v)
Definition: functional.hh:48
static symbol sname()
Definition: q.hh:28
static constexpr bool has_lightening_weights()
Definition: q.hh:164
weightset_mixin< detail::z_impl > z
Definition: fwd.hh:56
value_t rgcd(const value_t l, const value_t r) const
Definition: q.hh:105
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48
Print for LaTeX.
Definition: format.hh:22
ATTRIBUTE_PURE unsigned int gcd(unsigned int a, unsigned int b)
Greatest common divisor.
Definition: math.hh:13
static bool is_zero(const value_t v)
Definition: q.hh:140
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
Print as plain (ASCII) text, escaped.
Definition: format.hh:28
static constexpr bool show_one()
Definition: q.hh:166
valid iff proper succeeds on the "absolute value" of the automaton
Definition: star-status.hh:9
static value_t abs(const value_t v)
Definition: q.hh:170
char eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.cc:90
value_t conv(std::istream &i, bool=true) const
Definition: q.hh:208
value_t rdivide(const value_t l, const value_t r) const
Definition: q.hh:111
static value_t one()
Definition: q.hh:71
value_t & reduce()
Put it in normal form.
Definition: q.hh:49