Awali
Another Weighted Automata library
nullableset.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 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_LABELSET_NULLABLESET_HH
18 # define AWALI_LABELSET_NULLABLESET_HH
19 
20 # include <cstring> //strncmp
21 # include <memory>
22 # include <set>
23 # include <sstream>
24 
25 #include <awali/sttc/alphabets/setalpha.hh> // intersect
26 #include <awali/sttc/core/kind.hh>
27 //#include <awali/sttc/labelset/genset_labelset.hh>
28 //#include <awali/sttc/labelset/labelset.hh>
31 #include <awali/utils/hash.hh>
32 #include <awali/common/json/node.cc>
33 #include <awali/common/parse_exception.cc>
34 #include <awali/sttc/misc/raise.hh>
35 
36 namespace awali { namespace sttc {
37 
38  namespace internal
39  {
42  template <typename LabelSet>
44  {
45  using labelset_t = LabelSet;
47  using value_t = std::pair<typename labelset_t::value_t, bool>;
48  using kind_t = typename LabelSet::kind_t;
49 
50  static null make(std::istream& is)
51  {
52  // name: nullableset<lal_char(abc)>.
53  // ^^^^^^^^^^^^
54  // labelset
56  eat(is, '<');
57  auto ls = null::labelset_t::make(is);
58  eat(is, '>');
59  return null{ls};
60  }
61 
62  ATTRIBUTE_PURE
63  static constexpr value_t
64  one()
65  {
66  return value_t{null::labelset_t::special(), true};
67  }
68 
69  ATTRIBUTE_PURE
70  static constexpr value_t
72  {
73  return value_t{null::labelset_t::special(), false};
74  }
75 
76  template <typename Ls>
77  ATTRIBUTE_PURE
78  static typename std::enable_if<Ls::has_one(), bool>::type
80  {
81  return std::get<1>(l) || Ls::is_one(get_value(l));
82  }
83 
84  template <typename Ls>
85  ATTRIBUTE_PURE
86  static typename std::enable_if<!Ls::has_one(), bool>::type
88  {
89  return std::get<1>(l);
90  }
91 
92  ATTRIBUTE_PURE
93  static bool
95  {
96  return is_one_<labelset_t>(l);
97  }
98 
99  template <typename... Args>
100  static value_t
101  value(const labelset_t& ls, Args&&... args)
102  {
103  return {ls.value(std::forward<Args>(args)...), false};
104  }
105 
106  ATTRIBUTE_PURE
107  static typename labelset_t::value_t
108  get_value(const value_t& v)
109  {
110  return std::get<0>(v);
111  }
112  };
113 
116  template <typename GenSet>
117  struct nullable_helper<letterset<GenSet>>
118  {
120  using genset_t = GenSet;
122  using value_t = typename labelset_t::value_t;
124 
125  static null
126  make(std::istream& is)
127  {
128  using genset_t = typename labelset_t::genset_t;
129  // name: lal_char(abc)_ratexpset<law_char(xyz)_b>.
130  // ^^^ ^^^^ ^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^
131  // | | | weightset
132  // | | +-- gens
133  // | +-- letter_type
134  // +-- kind
136  if (is.peek() == '_')
137  {
138  eat(is, '_');
139  auto gs = genset_t::make(is);
140  auto ls = labelset_t{gs};
141  return null{ls};
142  }
143  eat(is, '<');
144  auto ls = labelset_t::make(is);
145  eat(is, '>');
146  return null{ls};
147  }
148 
149  ATTRIBUTE_PURE
150  static constexpr typename null::value_t
152  {
153  return genset_t::special_letter();
154  }
155 
156  ATTRIBUTE_PURE
157  static constexpr typename null::value_t
158  one()
159  {
160  return genset_t::one_letter();
161  }
162 
163  ATTRIBUTE_PURE
164  static bool
166  {
167  return l == one();
168  }
169 
170  template <typename... Args>
171  static value_t
172  value(const labelset_t& ls, Args&&... args)
173  {
174  return ls.value(std::forward<Args>(args)...);
175  }
176 
177  ATTRIBUTE_PURE
178  static typename labelset_t::value_t
179  get_value(const value_t& v)
180  {
181  return v;
182  }
183  };
184  }
185 
187  template <typename LabelSet>
188  class nullableset : public LabelSet
189  {
190  public:
191  using labelset_t = LabelSet;
192  using labelset_ptr = std::shared_ptr<const labelset_t>;
195  using kind_t = typename helper_t::kind_t;
196 
197  using value_t = typename helper_t::value_t;
198  //using word_t = typename labelset_t::word_t;
199 
201  : labelset_t{ls}, ls_{std::make_shared<const labelset_t>(ls)}
202  {}
203 
204  nullableset(const std::shared_ptr<const labelset_t>& ls)
205  : labelset_t{ls}, ls_{ls}
206  {}
207 
208  static std::string sname()
209  {
210  return "lan<" + labelset_t::sname() + ">";
211  }
212 
213  std::string vname(bool full = true) const
214  {
215  return "lan<" + labelset()->vname(full) + ">";
216  }
217 
219  static nullableset make(std::istream& i)
220  {
221  return helper_t::make(i);
222  }
223 
227  bool open(bool o) const
228  {
229  return this->labelset()->open(o);
230  }
231 
232  static constexpr bool
234  {
235  return true;
236  }
237 
238  static constexpr bool
240  {
241  return false;
242  }
243 
244  static constexpr bool
246  {
247  return labelset_t::is_letterized();
248  }
249 
250  static constexpr bool is_free()
251  {
252  return false;
253  }
254 
255  ATTRIBUTE_PURE
256  static constexpr value_t
257  one()
258  {
259  return helper_t::one();
260  }
261 
262  ATTRIBUTE_PURE
263  static bool
265  {
266  return helper_t::is_one(l);
267  }
268 
269  bool
270  is_valid(value_t v) const
271  {
272  return labelset()->is_valid(get_value(v)) || is_one(v);
273  }
274 
275  value_t
277  {
278  return v;
279  }
280 
281  const labelset_ptr labelset() const
282  {
283  return ls_;
284  }
285 
286  template <typename... Args>
287  value_t
288  value(Args&&... args) const
289  {
290  return helper_t::value(*ls_, std::forward<Args>(args)...);
291  }
292 
293  /*
294  word_t
295  word(const value_t& l) const
296  {
297  if(is_one(l))
298  return internal::law_traits<LabelSet>::value(*labelset()).one();
299  return labelset()->word(get_value(l));
300  }
301  */
302 
304  static bool equals(const value_t& l, const value_t& r)
305  {
306  if (is_one(l))
307  return is_one(r);
308  return !is_one(r) && labelset_t::equals(get_value(l), get_value(r));
309  }
310 
312  static bool less_than(const value_t& l, const value_t& r)
313  {
314  if (is_one(r))
315  return false;
316  else if (is_one(l))
317  return true;
318  return labelset_t::less_than(get_value(l),
319  get_value(r));
320  }
321 
322  static value_t
324  {
325  return helper_t::special();
326  }
327 
328  static bool
329  is_special(const value_t& l)
330  {
331  return !is_one(l) && labelset_t::is_special(get_value(l));
332  }
333 
334  size_t size(const value_t& v) const
335  {
336  return is_one(v) ? 0 : labelset_t::size(get_value(v));
337  }
338 
339  static size_t hash(const value_t& v)
340  {
341  std::size_t res = 0;
342  std::hash_combine(res, labelset_t::hash(get_value(v)));
343  std::hash_combine(res, helper_t::is_one(v));
344  return res;
345  }
346 
348  value_t
349  conv(std::istream& i) const
350  {
351  value_t res;
352  int c = i.peek();
353  if (c == '\\')
354  {
355  i.ignore();
356  c = i.peek();
357  require(c == 'e', "invalid label: unexpected \\", str_escape(c));
358  i.ignore();
359  res = one();
360  }
361  else
362  res = value(ls_->conv(i));
363  return res;
364  }
365 
366  value_t
367  parse(const std::string& s, size_t& p, bool fixed_domain=true) const {
368  --p;
369  if(s[p]=='e' && p>0 && s[p-1]=='\\'){
370  --p;
371  return one();
372  }
373  else
374  return ls_->parse(s,++p, fixed_domain);
375  }
376 
377 
378  std::set<value_t>
379  convs(std::istream& i) const
380  {
381  auto l = ls_->convs(i);
382  std::set<value_t> res;
383  for (auto v : l)
384  res.emplace(value(v));
385  return res;
386  }
387 
388  std::ostream&
389  print(value_t l, std::ostream& o,
390  const std::string& format = "text") const
391  {
392  if (is_one(l))
393  o << (format == "latex" ? "\\varepsilon" : "\\e");
394  else
395  labelset()->print(get_value(l), o, format);
396  return o;
397  }
398 
399  template<unsigned version = version::fsm_json>
400  value_t
402  version::check_fsmjson<version>();
403  switch (version) {
404  case 1:
405  default:
406  if(p->kind == json::ARRAY)
407  if(p->array()->empty())
408  return one();
409  if(p->kind == json::STRING)
410  if(p->string()->value.empty())
411  return one();
412  return ls_->template value_from_json<version>(p);
413  }
414  }
415 
416 
417  static void
418  make_nullableset_kind(std::istream& is)
419  {
420  char kind[4];
421  is.get(kind, sizeof kind);
422  if (strncmp("lan", kind, 4))
423  raise("kind::make: unexpected: ",str_escape(kind),", expected: lan");
424  }
425 
426  value_t
427  zero() const
428  {
429  return value(labelset()->zero());
430  }
431 
432  bool
433  is_zero(const value_t& v) const
434  {
435  return labelset()->is_zero(get_value(v));
436  }
437 
438  bool
439  is_letter(const value_t& v) const
440  {
441  return labelset()->is_letter(get_value(v));
442  }
443 
444  value_t
445  transpose(const value_t& l) const
446  {
447  if (is_one(l))
448  return l;
449  return value(ls_->transpose(get_value(l)));
450  }
451 
452  std::ostream&
453  print_set(std::ostream& o, const std::string& format = "text") const
454  {
455  if (format == "latex")
456  {
457  o << "(";
458  labelset()->print_set(o, format);
459  o << ")^?";
460  }
461  else if (format == "text")
462  o << vname(true);
463  else
464  raise("invalid format: ", format);
465  return o;
466  }
467 
468 
469 
470  template<unsigned version = version::fsm_json>
472  const
473  {
474  version::check_fsmjson<version>();
475  switch (version) {
476  case 1:
477  default:
478  json::object_t* obj = ls_->template to_json<version>()->object();
479  obj->insert_before("alphabet","allowEpsilon", new json::bool_t(true));
480  return obj;
481  }
482  }
483 
484 
485  template<unsigned version = version::fsm_json>
486  json::node_t*
488  const
489  {
490  version::check_fsmjson<version>();
491  switch (version) {
492  case 1:
493  default:
494  if(is_one(value))
495  return new json::array_t();
496  else
497  return ls_->template value_to_json<version>(value);
498  }
499  }
500 
501  private:
502  static typename labelset_t::value_t
503  get_value(const value_t& v)
504  {
505  return helper_t::get_value(v);
506  }
507 
508  labelset_ptr ls_;
509  };
510 
511 
512 #define DEFINE(Func, Operation, Lhs, Rhs, Res) \
513  template <typename GenSet> \
514  Res \
515  Func(const Lhs& lhs, const Rhs& rhs) \
516  { \
517  return {Operation(lhs.genset(), rhs.genset())}; \
518  }
519 
521  DEFINE(meet, intersection, nullableset<letterset<GenSet>>,
523 
524  DEFINE(meet, intersection, letterset<GenSet>,
526 
528  letterset<GenSet>, nullableset<letterset<GenSet>>)
529 
530  template <typename Lls, typename Rls>
531  auto
532  meet(const nullableset<Lls>& lhs, const nullableset<Rls>& rhs)
533  -> nullableset<decltype(meet(*lhs.labelset(), *rhs.labelset()))>
534  {
535  return {meet(*lhs.labelset(), *rhs.labelset())};
536  }
537 
539  DEFINE(join, get_union, nullableset<letterset<GenSet>>,
541 
542  DEFINE(join, get_union, letterset<GenSet>,
544 
546  letterset<GenSet>, nullableset<letterset<GenSet>>)
547 
548  template <typename Lls, typename Rls>
549  auto
550  join(const nullableset<Lls>& lhs, const nullableset<Rls>& rhs)
551  -> nullableset<decltype(join(*lhs.labelset(), *rhs.labelset()))>
552  {
553  return {join(*lhs.labelset(), *rhs.labelset())};
554  }
555 
556 
557 #undef DEFINE
558 
559 }}//end of ns awali::stc
560 
561 #endif // !AWALI_LABELSET_NULLABLESET_HH
Definition: node.hh:431
unsigned empty() const
Definition: node.hh:467
Definition: node.hh:555
Definition: node.hh:193
virtual string_t const * string() const
Casts this node to string_t.
Definition: node.hh:215
node_kind_t const kind
Definition: node.hh:196
virtual array_t const * array() const
Casts this node to array_t.
Definition: node.hh:207
Definition: node.hh:367
object_t * insert_before(std::string const &ref_key, std::string key, node_t *node)
std::string value
Definition: node.hh:531
The semiring of complex numbers.
Definition: c.hh:44
Implementation of labels are letters.
Definition: letterset.hh:43
letter_t value_t
Definition: letterset.hh:53
value_t value(Args &&... args) const
Value constructor.
Definition: letterset.hh:114
GenSet genset_t
Definition: letterset.hh:45
Implementation of labels are nullables (letter or empty).
Definition: nullableset.hh:189
static size_t hash(const value_t &v)
Definition: nullableset.hh:339
static constexpr bool is_letterized()
Definition: nullableset.hh:245
bool open(bool o) const
Whether unknown letters should be added, or rejected.
Definition: nullableset.hh:227
value_t parse(const std::string &s, size_t &p, bool fixed_domain=true) const
Definition: nullableset.hh:367
std::shared_ptr< const labelset_t > labelset_ptr
Definition: nullableset.hh:192
size_t size(const value_t &v) const
Definition: nullableset.hh:334
static constexpr bool is_ratexpset()
Definition: nullableset.hh:239
typename helper_t::value_t value_t
Definition: nullableset.hh:197
static bool less_than(const value_t &l, const value_t &r)
Whether l < r.
Definition: nullableset.hh:312
bool is_letter(const value_t &v) const
Definition: nullableset.hh:439
value_t zero() const
Definition: nullableset.hh:427
value_t transpose(const value_t &l) const
Definition: nullableset.hh:445
value_t conv(std::istream &i) const
Definition: nullableset.hh:349
static constexpr ATTRIBUTE_PURE value_t one()
Definition: nullableset.hh:257
const labelset_ptr labelset() const
Definition: nullableset.hh:281
std::ostream & print(value_t l, std::ostream &o, const std::string &format="text") const
Definition: nullableset.hh:389
static std::string sname()
Definition: nullableset.hh:208
json::node_t * to_json() const
Definition: nullableset.hh:471
bool is_valid(value_t v) const
Definition: nullableset.hh:270
json::node_t * value_to_json(value_t value) const
Definition: nullableset.hh:487
value_t value_from_json(json::node_t *p) const
Definition: nullableset.hh:401
static bool equals(const value_t &l, const value_t &r)
Whether l == r.
Definition: nullableset.hh:304
static nullableset make(std::istream &i)
Build from the description in is.
Definition: nullableset.hh:219
value_t conv(self_type, value_t v) const
Definition: nullableset.hh:276
static constexpr bool is_free()
Definition: nullableset.hh:250
nullableset(const labelset_t &ls)
Definition: nullableset.hh:200
static constexpr bool has_one()
Definition: nullableset.hh:233
LabelSet labelset_t
Definition: nullableset.hh:191
static ATTRIBUTE_PURE bool is_one(value_t l)
Definition: nullableset.hh:264
std::string vname(bool full=true) const
Definition: nullableset.hh:213
std::set< value_t > convs(std::istream &i) const
Definition: nullableset.hh:379
std::ostream & print_set(std::ostream &o, const std::string &format="text") const
Definition: nullableset.hh:453
static void make_nullableset_kind(std::istream &is)
Definition: nullableset.hh:418
typename helper_t::kind_t kind_t
Definition: nullableset.hh:195
static bool is_special(const value_t &l)
Definition: nullableset.hh:329
value_t value(Args &&... args) const
Definition: nullableset.hh:288
static value_t special()
Definition: nullableset.hh:323
nullableset(const std::shared_ptr< const labelset_t > &ls)
Definition: nullableset.hh:204
bool is_zero(const value_t &v) const
Definition: nullableset.hh:433
The semiring of floating Numbers.
Definition: r.hh:35
labelset_description nullableset(labelset_description ls1)
@ ARRAY
Definition: node.hh:94
@ STRING
Definition: node.hh:97
void eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.hh:62
RatExpSet::ratexp_t less_than(const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
Definition: less_than.hh:166
RatExpSet::ratexp_t equals(const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
Definition: equal_visit.hh:153
auto join(const ratexpset< Ctx1 > &a, const ratexpset< Ctx2 > &b) -> ratexpset< join_t< Ctx1, Ctx2 >>
The union of two ratexpsets.
Definition: ratexpset.hh:445
std::ostream & str_escape(std::ostream &os, const int c)
Definition: escape.hh:30
auto meet(const ratexpset< Ctx1 > &a, const ratexpset< Ctx2 > &b) -> ratexpset< meet_t< Ctx1, Ctx2 >>
The meet of two ratexpsets.
Definition: ratexpset.hh:434
set_alphabet< L2 > get_union(const set_alphabet< L2 > &lhs, const set_alphabet< L2 > &rhs)
Definition: setalpha.hh:364
set_alphabet< L2 > intersection(const set_alphabet< L2 > &lhs, const set_alphabet< L2 > &rhs)
Definition: setalpha.hh:357
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
static const std::string full
Completely version of Awali as a std::string.
Definition: version.hh:42
Main namespace of Awali.
Definition: ato.hh:22
#define DEFINE(Func, Operation, Lhs, Rhs, Res)
Definition: nullableset.hh:512
static ATTRIBUTE_PURE bool is_one(value_t l)
Definition: nullableset.hh:165
static constexpr ATTRIBUTE_PURE null::value_t one()
Definition: nullableset.hh:158
static value_t value(const labelset_t &ls, Args &&... args)
Definition: nullableset.hh:172
static ATTRIBUTE_PURE labelset_t::value_t get_value(const value_t &v)
Definition: nullableset.hh:179
typename labelset_t::value_t value_t
Definition: nullableset.hh:122
static constexpr ATTRIBUTE_PURE null::value_t special()
Definition: nullableset.hh:151
static null make(std::istream &is)
Definition: nullableset.hh:126
Add support for an empty word to a LabelSet that does not provide such special label to this end.
Definition: nullableset.hh:44
std::pair< typename labelset_t::value_t, bool > value_t
Definition: nullableset.hh:47
static ATTRIBUTE_PURE bool is_one(value_t l)
Definition: nullableset.hh:94
static value_t value(const labelset_t &ls, Args &&... args)
Definition: nullableset.hh:101
LabelSet labelset_t
Definition: nullableset.hh:45
static ATTRIBUTE_PURE std::enable_if<!Ls::has_one(), bool >::type is_one_(value_t l)
Definition: nullableset.hh:87
static ATTRIBUTE_PURE std::enable_if< Ls::has_one(), bool >::type is_one_(value_t l)
Definition: nullableset.hh:79
static constexpr ATTRIBUTE_PURE value_t special()
Definition: nullableset.hh:71
static ATTRIBUTE_PURE labelset_t::value_t get_value(const value_t &v)
Definition: nullableset.hh:108
typename LabelSet::kind_t kind_t
Definition: nullableset.hh:48
static constexpr ATTRIBUTE_PURE value_t one()
Definition: nullableset.hh:64
static null make(std::istream &is)
Definition: nullableset.hh:50
marker type for labelsets where labels are nullable
Definition: kind.hh:78