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