Awali
Another Weighted Automata library
zz.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_F_HH
18 # define AWALI_WEIGHTSET_F_HH
19 
20 # include <cassert>
21 # include <ostream>
22 # include <string>
23 
25 #include <awali/utils/hash.hh>
26 #include <awali/sttc/misc/raise.hh>
27 #include <awali/common/enums.hh>
30 
31 namespace awali {
32  namespace sttc {
38  template <unsigned int N>
39  class zz {
40  public:
41  using self_type = zz<N>;
42 
43  zz() {
44  if(N<2)
45  raise("Cyclic semirings should have a characteristic larger than 1");
46  }
47 
48  static std::string sname()
49  {
50  return "zz"+std::to_string(N);
51  }
52 
53  std::string vname(bool = true) const
54  {
55  return sname();
56  }
57 
59  static zz<N> make(std::istream& is)
60  {
61  eat(is, sname());
62  return {};
63  }
64 
65  using value_t = int;
66  using finite_t = bool;
67  static const finite_t finite=true;
68 
69  static value_t
70  zero()
71  {
72  return 0;
73  }
74 
75  static value_t
76  one()
77  {
78  return 1;
79  }
80 
81  static value_t
82  add(const value_t l, const value_t r)
83  {
84  return (l+r)%N;
85  }
86 
87  static value_t
88  sub(const value_t l, const value_t r)
89  {
90  return (l-r)%N;
91  }
92 
93  static value_t
94  mul(const value_t l, const value_t r)
95  {
96  return (l*r)%N;
97  }
98 
99  static value_t
100  rdiv(const value_t l, const value_t r)
101  {
102  require(!is_zero(r), sname()+" div: division by zero");
103  int calc=0;
104  for (int i=1; i<N; i++) {
105  calc = (calc+r)%N; // calc is always equal to (i*r)%N
106  if ( calc == 1 )
107  return ( (l*i)%N );
108  if ( calc == 0 )
109  throw std::runtime_error(sname()+": division by a divisor of 0:"+std::to_string(r));
110  }
111  throw std::runtime_error(sname()+": unreachable code");
112  }
113 
114  static value_t
115  ldiv(const value_t l, const value_t r)
116  {
117  return rdiv(r, l);
118  }
119 
120  static value_t
121  star(const value_t v)
122  {
123  if ( v == 0 )
124  return 1;
125  else
126  throw std::domain_error("Weightset "+sname()+": given value ("+std::to_string(v)+") is not starrable");
127  }
128 
129  static bool
130  equals(const value_t l, const value_t r)
131  {
132  return l%N == r%N ;
133  }
134 
136  static bool less_than(value_t lhs, value_t rhs)
137  {
138  return lhs%N < rhs%N;
139  }
140 
141  constexpr static bool is_special(value_t)
142  {
143  return false;
144  }
145 
146  static bool
147  is_zero(const value_t v)
148  {
149  return ( (v%N) == 0);
150  }
151 
152  static bool
153  is_one(const value_t v)
154  {
155  return ( (v%N) == 1);
156  }
157 
158  static constexpr bool is_commutative_semiring() { return true; }
159 
160  static constexpr bool show_one() { return false; }
161 
162  static constexpr
164 
165  static value_t
167  {
168  return v;
169  }
170 
171  static size_t hash(value_t v)
172  {
173  return utils::hash_value(v);
174  }
175 
176  static value_t
178  {
179  return v%N;
180  }
181 
182  static value_t
183  conv(std::istream& stream)
184  {
185  int i;
186  if (stream >> i) {
187  if (i>= (signed) N)
188  throw parse_exception("Weight-Set "+sname()+": parsed value ("+std::to_string(i)+") is too great.");
189  return i;
190  } else
191  sttc::fail_reading(stream, sname() + ": invalid value");
192  }
193 
194  static value_t
195  parse(const std::string & s, size_t& p) {
196  size_t i=p;
197  for(; i>0 && s[i-1]>='0' && s[i-1]<='9'; --i)
198  ;
199  if(i==p)
200  throw parse_exception("Wrong "+sname()+" value");
201  std::istringstream st(s.substr(i, p-i));
202  value_t x;
203  st >> x;
204  p=i;
205  if (x>= (signed)N)
206  throw parse_exception("Weight-Set "+sname()+": parsed value ("+s.substr(i, p-i)+") is too great.");
207  return x;
208  }
209 
210  static std::ostream&
211  print(const value_t v, std::ostream& o,
212  const std::string& format= "text")
213  {
214  return o << v;
215  }
216 
217  std::ostream&
218  print_set(std::ostream& o, const std::string& format = "text") const
219  {
220  if (format == "latex")
221  o << "\\mathbb{F}_" << N;
222  else if (format == "text")
223  o << "Z/" << N << 'Z';
224  else
225  raise("invalid format: ", format);
226  return o;
227  }
228 
229 
230  template<unsigned version = version::fsm_json>
231  static json::node_t*
233  {
234  switch (version) {
235  case 0:
236  throw parse_exception("[zz] Unsupported fsm-json version:"
237  + std::to_string(version));
238  case 1:
239  default:
240  json::object_t* obj = new json::object_t();
241  obj->push_back("semiring", new json::string_t("Cyclic"));
242  obj->push_back("characteristic", new json::int_t(N));
243  return (obj);
244  }
245  }
246 
247 
248  template<unsigned version = version::fsm_json>
250  const
251  {
252  switch (version) {
253  case 0:
254  throw parse_exception("[zz] Unsupported fsm-json version:"
255  + std::to_string(version));
256  case 1:
257  default:
258  return new json::int_t(v);
259  }
260  }
261 
262 
263  template<unsigned version = version::fsm_json>
264  value_t
266  const
267  {
268  switch (version) {
269  case 0:
270  throw parse_exception("[letterset] Unsupported fsm-json version:"
271  + std::to_string(version));
272  case 1:
273  default:
274  return p->to_int();
275  }
276  }
277 
278  };
279 
280  template<unsigned N>
281  inline
282  zz<N> join(const zz<N>&, const zz<N>&) { return {}; }
283 
284  }
285 }//end of ns awali::stc
286 
287 #endif // !AWALI_WEIGHTSET_F_HH
Definition: node.hh:483
Definition: node.hh:191
virtual int to_int() const
Coerces this node_t to int.
Definition: node.hh:319
Definition: node.hh:365
object_t * push_back(std::string key, node_t *node)
Definition: node.hh:526
The semiring of floating Numbers.
Definition: r.hh:35
The cyclic semiring with characteristic N.
Definition: zz.hh:39
static constexpr bool show_one()
Definition: zz.hh:160
static bool less_than(value_t lhs, value_t rhs)
Whether lhs < rhs.
Definition: zz.hh:136
static value_t add(const value_t l, const value_t r)
Definition: zz.hh:82
static value_t mul(const value_t l, const value_t r)
Definition: zz.hh:94
static size_t hash(value_t v)
Definition: zz.hh:171
static value_t star(const value_t v)
Definition: zz.hh:121
static constexpr bool is_commutative_semiring()
Definition: zz.hh:158
static bool is_one(const value_t v)
Definition: zz.hh:153
value_t value_from_json(json::node_t const *p) const
Definition: zz.hh:265
static value_t rdiv(const value_t l, const value_t r)
Definition: zz.hh:100
json::node_t * value_to_json(value_t v) const
Definition: zz.hh:249
bool finite_t
Definition: zz.hh:66
static value_t zero()
Definition: zz.hh:70
static constexpr star_status_t star_status()
Definition: zz.hh:163
std::string vname(bool=true) const
Definition: zz.hh:53
static value_t one()
Definition: zz.hh:76
static json::node_t * to_json()
Definition: zz.hh:232
static std::string sname()
Definition: zz.hh:48
static bool equals(const value_t l, const value_t r)
Definition: zz.hh:130
static value_t parse(const std::string &s, size_t &p)
Definition: zz.hh:195
static value_t ldiv(const value_t l, const value_t r)
Definition: zz.hh:115
static value_t transpose(const value_t v)
Definition: zz.hh:166
static std::ostream & print(const value_t v, std::ostream &o, const std::string &format="text")
Definition: zz.hh:211
static value_t conv(std::istream &stream)
Definition: zz.hh:183
static value_t sub(const value_t l, const value_t r)
Definition: zz.hh:88
static value_t conv(self_type, value_t v)
Definition: zz.hh:177
std::ostream & print_set(std::ostream &o, const std::string &format="text") const
Definition: zz.hh:218
constexpr static bool is_special(value_t)
Definition: zz.hh:141
static bool is_zero(const value_t v)
Definition: zz.hh:147
static const finite_t finite
Definition: zz.hh:67
static zz< N > make(std::istream &is)
Build from the description in is.
Definition: zz.hh:59
int value_t
Definition: zz.hh:65
zz()
Definition: zz.hh:43
star_status_t
The different behaviours a weightset may have with respect to the star.
Definition: enums.hh:161
@ NON_STARRABLE
Definition: enums.hh:164
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
Main namespace of Awali.
Definition: ato.hh:22
Exceptions thrown during parsing.
Definition: parse_exception.hh:26