Awali
Another Weighted Automata library
q.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2021 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_WEIGHTSET_Q_HH
18 #define AWALI_WEIGHTSET_Q_HH
19 
20 #include <string>
21 #include <ostream>
22 
23 #include <awali/utils/arith.hh>
24 
25 #include <awali/common/qfraction.cc>
26 #include <awali/common/enums.hh>
27 
29 #include <awali/utils/hash.hh>
30 
31 #include <awali/sttc/misc/raise.hh>
32 #include <awali/sttc/misc/stream.hh> // eat
35 
36 namespace awali {
37  namespace sttc {
42  class q {
43  public:
44  using self_type = q;
45 
46  static std::string sname()
47  {
48  return "q";
49  }
50 
51  std::string vname(bool = true) const
52  {
53  return sname();
54  }
55 
57  static q make(std::istream& is)
58  {
59  eat(is, sname());
60  return {};
61  }
62 
64 
65  static unsigned int abs(int a)
66  {
67  return a < 0 ? -a : a;
68  }
69 
70 
71  static value_t zero()
72  {
73  return value_t{0, 1};
74  }
75 
76  static value_t one()
77  {
78  return value_t{1, 1};
79  }
80 
81  static value_t add(const value_t l, const value_t r)
82  {
83  unsigned int cm = utils::lcm(l.den, abs(r.den));
84  return value_t{l.num * int (cm / l.den) + r.num * int (cm / r.den),
85  cm}.reduce();
86  }
87 
88  static value_t sub(const value_t l, const value_t r)
89  {
90  unsigned int cm = utils::lcm(l.den, abs(r.den));
91  return value_t{l.num * int (cm / l.den) - r.num * int (cm / r.den),
92  cm}.reduce();
93  }
94 
95  static value_t mul(const value_t l, const value_t r)
96  {
97  return value_t{l.num * r.num, l.den * r.den}.reduce();
98  }
99 
100  static value_t
101  rdiv(const value_t l, const value_t r)
102  {
103  require(!is_zero(r), "div: division by zero");
104  if (0 < r.num)
105  return value_t{l.num * int(r.den), l.den * r.num}.reduce();
106  else
107  return value_t{-l.num * int(r.den), l.den * -r.num}.reduce();
108  }
109 
110  static value_t
111  ldiv(const value_t l, const value_t r)
112  {
113  return rdiv(r, l);
114  }
115 
116  value_t star(const value_t v) const
117  {
118  // Bad casting when v.den is too big
119  if (abs(v.num) < v.den)
120  // No need to reduce: numerator and denominators are primes.
121  return {int(v.den), v.den - v.num};
122  else
123  raise(sname(), ": star: invalid value: ", format(*this, v));
124  }
125 
126  static bool is_special(const value_t) // C++11: cannot be constexpr.
127  {
128  return false;
129  }
130 
131  static bool is_zero(const value_t v)
132  {
133  return v.num == 0;
134  }
135 
136  static bool is_one(const value_t v)
137  {
138  // All values are normalized.
139  return v.num == 1 && v.den == 1;
140  }
141 
142  static bool equals(const value_t l, const value_t r)
143  {
144  return l==r;
145  }
146 
148  static bool less_than(value_t lhs, value_t rhs)
149  {
150  return lhs < rhs;
151  }
152 
153  static constexpr bool is_commutative_semiring() { return true; }
154 
155  static constexpr bool show_one() { return false; }
156  static constexpr star_status_t star_status() { return star_status_t::ABSVAL; }
157 
158  static value_t
159  abs(const value_t v)
160  {
161  return v.num < 0 ? (value_t{-v.num, v.den}) : v;
162  }
163 
164  static value_t
166  {
167  return v;
168  }
169 
170  static size_t hash(value_t v)
171  {
172  size_t res = 0;
173  std::hash_combine(res, utils::hash_value(v.num));
174  std::hash_combine(res, utils::hash_value(v.den));
175  return res;
176  }
177 
178  static value_t
180  {
181  return v;
182  }
183 
184  static value_t
186  {
187  return {v, 1};
188  }
189 
190  static value_t
192  {
193  return {(int)v, 1};
194  }
195 
196  static value_t
198  {
199  return {v, 1};
200  }
201 
202  static value_t
203  conv(std::istream& i)
204  {
205  int num;
206  if (! (i >> num))
207  fail_reading(i, sname() + ": invalid numerator");
208 
209  // If we have a slash after the numerator then we have a
210  // denominator as well.
211  char maybe_slash;
212  if ((maybe_slash = i.peek()) != '/')
213  return value_t{num, 1};
214  eat(i, '/');
215 
216  // operator>> with an istream and an unsigned int silently
217  // mangles a negative number into its two's complement
218  // representation as a positive number.
219  if (i.peek() == '-')
220  {
221  num = - num;
222  eat(i, '-');
223  }
224 
225  unsigned int den;
226  if (i >> den)
227  {
228  // Make sure our rational respects our constraints.
229  if (den == 0)
230  throw std::domain_error(sname() + ": zero denominator");
231  return value_t{num, den}.reduce();
232  }
233  else
234  fail_reading(i, sname() + ": invalid denominator");
235  }
236 
237  static value_t
238  parse(const std::string & s, size_t& p) {
239  return internal::lr_parse_qfraction(s,p);
240  }
241 
242 
243  static std::ostream&
244  print(const value_t v, std::ostream& o,
245  const std::string& format = "text")
246  {
247  if (format == "json") {
248  if(v.den ==1u)
249  return o << v.num;
250  o<< "{\"num\":" << v.num << ", \"den\":" << v.den << '}';
251  return o;
252  }
253  if (format == "latex")
254  {
255  if (v.den == 1)
256  o << v.num;
257  else
258  o << "\\frac{" << v.num << "}{" << v.den << '}';
259  }
260  else
261  {
262  o << v.num;
263  if (v.den != 1)
264  o << '/' << v.den;
265  }
266  return o;
267  }
268 
269  std::ostream&
270  print_set(std::ostream& o, const std::string& format = "text") const
271  {
272  if (format == "latex")
273  o << "\\mathbb{Q}";
274  else if (format == "text")
275  o << "Q";
276  else
277  raise("invalid format: ", format);
278  return o;
279  }
280 
281  template<unsigned version = version::fsm_json>
283  to_json() const
284  {
285  switch (version) {
286  case 0:
287  throw parse_exception("[q] Unsupported fsm-json version:"
288  + std::to_string(version));
289  case 1:
290  default:
291  return new json::object_t("semiring", new json::string_t("Q"));
292  }
293  }
294 
295  template<unsigned version = version::fsm_json>
297  const
298  {
299  switch (version) {
300  case 0:
301  throw parse_exception("[q] Unsupported fsm-json version:"
302  + std::to_string(version));
303  case 1:
304  default:
305  if(v.den ==1u)
306  return new json::int_t(v.num);
307  json::object_t* l = new json::object_t();
308  l->push_back("num",new json::int_t(v.num));
309  l->push_back("den",new json::int_t(v.den));
310  return l;
311  }
312  }
313 
314  template<unsigned version = version::fsm_json>
316  const
317  {
318  switch (version) {
319  case 0:
320  case 1:
321  default:
322  switch(p->kind) {
323  case json::FLOATING:
325  "[Q] value_from_json: node is of kind FLOATING and we do "
326  "not support double to qfraction conversion");
327  case json::BOOLEAN:
328  case json::INTEGER:
329  case json::STRING: {
330  try {return value_t{p->to_int(),1u};}
331  catch (json::coercion_exception&) {}
332  std::stringstream ss(p->string()->value);
333  value_t v = conv(ss); // This might be wrong
334  if (ss.eof())
335  return v;
337  "[Q] value_from_json: node is of kind STRING and is not a "
338  "proper qfraction representation.");
339  }
340  case json::ARRAY :{
341  std::vector<json::node_t*> const& v = p->array()->values;
342  if (p->arity()!=2)
344  "[Q] value_from_json: node is of kind ARRAY and needs to "
345  " have two children to be interpreted as a qfraction.");
346  return value_t(p->at(0)->to_int(),p->at(1)->to_int());
347  }
348  case json::OBJECT :{
349  int n;
350  if(!p->has_child("num")) {
352  "[Q] value_from_json: node is of kind OBJECT and needs to "
353  "have a \"num\" field to be interpreted as a qfraction.");
354  }
355  try {
356  n = p->at("num")->to_int();
357  } catch (json::coercion_exception& e) {
359  "[Q] value_from_json:: node is of kind OBJECT, hence the "
360  "node associated with \"num\" needs to be coercible to "
361  "int. " + std::string(e.what()));
362  }
363  if (p->has_child("den"))
364  return value_t(n, p->at("den")->to_int());
365  else
366  return value_t(n);
367  }
368  case json::_NULL:
370  "[Q] value_from_json: node is of kind NULL and cannot be "
371  "interpreted as a qfraction.");
372  }
373  throw std::runtime_error("json parser Q");
374  }
375  }
376 
377  };
378 
379  inline q join(const q&, const q&) { return {}; }
380 
381  inline q join(const z&, const q&) { return {}; }
382  inline q join(const q&, const z&) { return {}; }
383 
384  inline q join(const n&, const q&) { return {}; }
385  inline q join(const q&, const n&) { return {}; }
386 
387  inline q join(const b&, const q&) { return {}; }
388  inline q join(const q&, const b&) { return {}; }
389 
390  }
391 }//end of ns awali::stc
392 
393 
394 
395 
396 #endif // !AWALI_WEIGHTSET_Q_HH
std::vector< node_t * > const & values
Definition: node.hh:429
Exception used when trying to coerce a node to a given type.
Definition: exceptions.hh:83
virtual const char * what() const noexcept override
Definition: exceptions.hh:40
Definition: node.hh:483
Definition: node.hh:191
virtual node_t * at(std::string const &key)
virtual int to_int() const
Coerces this node_t to int.
Definition: node.hh:319
virtual string_t const * string() const
Casts this node to string_t.
Definition: node.hh:213
virtual bool has_child(std::string const &) const
Definition: node.hh:282
node_kind_t const kind
Definition: node.hh:194
virtual unsigned arity() const
Definition: node.hh:353
virtual array_t const * array() const
Casts this node to array_t.
Definition: node.hh:205
Definition: node.hh:365
object_t * push_back(std::string key, node_t *node)
Definition: node.hh:526
std::string value
Definition: node.hh:528
Definition: qfraction.hh:26
q_fraction_t & reduce()
den_t den
Definition: qfraction.hh:32
num_t num
Definition: qfraction.hh:31
The Boolean semring.
Definition: b.hh:38
bool value_t
Definition: b.hh:56
The semiring of Natural numbers.
Definition: n.hh:34
unsigned int value_t
Definition: n.hh:55
The semiring of rational numbers.
Definition: q.hh:42
value_t star(const value_t v) const
Definition: q.hh:116
static value_t one()
Definition: q.hh:76
json::node_t * value_to_json(value_t v) const
Definition: q.hh:296
static size_t hash(value_t v)
Definition: q.hh:170
static value_t mul(const value_t l, const value_t r)
Definition: q.hh:95
static value_t parse(const std::string &s, size_t &p)
Definition: q.hh:238
value_t value_from_json(json::node_t const *p) const
Definition: q.hh:315
static value_t conv(z, z::value_t v)
Definition: q.hh:185
static constexpr bool show_one()
Definition: q.hh:155
static value_t add(const value_t l, const value_t r)
Definition: q.hh:81
static bool less_than(value_t lhs, value_t rhs)
Whether lhs < rhs.
Definition: q.hh:148
static value_t abs(const value_t v)
Definition: q.hh:159
static value_t ldiv(const value_t l, const value_t r)
Definition: q.hh:111
static value_t transpose(const value_t v)
Definition: q.hh:165
static value_t conv(b, b::value_t v)
Definition: q.hh:197
static bool is_special(const value_t)
Definition: q.hh:126
static bool is_one(const value_t v)
Definition: q.hh:136
static value_t conv(std::istream &i)
Definition: q.hh:203
static value_t conv(n, n::value_t v)
Definition: q.hh:191
static value_t rdiv(const value_t l, const value_t r)
Definition: q.hh:101
static bool is_zero(const value_t v)
Definition: q.hh:131
static std::string sname()
Definition: q.hh:46
std::ostream & print_set(std::ostream &o, const std::string &format="text") const
Definition: q.hh:270
json::object_t * to_json() const
Definition: q.hh:283
std::string vname(bool=true) const
Definition: q.hh:51
static value_t conv(self_type, value_t v)
Definition: q.hh:179
static q make(std::istream &is)
Build from the description in is.
Definition: q.hh:57
static value_t zero()
Definition: q.hh:71
static constexpr bool is_commutative_semiring()
Definition: q.hh:153
static std::ostream & print(const value_t v, std::ostream &o, const std::string &format="text")
Definition: q.hh:244
static constexpr star_status_t star_status()
Definition: q.hh:156
static unsigned int abs(int a)
Definition: q.hh:65
static value_t sub(const value_t l, const value_t r)
Definition: q.hh:88
static bool equals(const value_t l, const value_t r)
Definition: q.hh:142
q_fraction_t value_t
Definition: q.hh:63
The semiring of floating Numbers.
Definition: r.hh:35
The semiring of Integers.
Definition: z.hh:35
int value_t
Definition: z.hh:56
star_status_t
The different behaviours a weightset may have with respect to the star.
Definition: enums.hh:161
@ ABSVAL
Definition: enums.hh:166
@ OBJECT
Definition: node.hh:90
@ INTEGER
Definition: node.hh:92
@ ARRAY
Definition: node.hh:91
@ BOOLEAN
Definition: node.hh:95
@ STRING
Definition: node.hh:94
@ FLOATING
Definition: node.hh:93
@ _NULL
Definition: node.hh:96
q_fraction_t lr_parse_qfraction(std::string const &s, size_t &p, bool allow_empty=false, q_fraction_t value_if_empty={1, 1})
Reads a q_fraction_t left of position p in string, by using as many characters as possible.
Definition: lr_parse_number.hh:353
std::string to_string(identities i)
void eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.hh:62
ATTRIBUTE_NORETURN void fail_reading(std::istream &is, std::string explanation)
Throw an exception after failing to read from is.
Definition: stream.hh:93
auto join(const ratexpset< Ctx1 > &a, const ratexpset< Ctx2 > &b) -> ratexpset< join_t< Ctx1, Ctx2 >>
The union of two ratexpsets.
Definition: ratexpset.hh:448
auto format(const ValueSet &vs, const typename ValueSet::value_t &v, Args &&... args) -> std::string
Format v via vs.print.
Definition: stream.hh:109
void require(bool b, Args &&... args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:55
std::size_t hash_value(const T &v)
Definition: hash.hh:76
ATTRIBUTE_CONST unsigned int lcm(unsigned int a, unsigned int b)
Definition: arith.hh:41
Main namespace of Awali.
Definition: ato.hh:22
Exceptions thrown during parsing.
Definition: parse_exception.hh:26