Vcsn  2.4
Be Rational
wordset.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <memory>
4 
5 #include <boost/range/algorithm/mismatch.hpp>
6 #include <boost/algorithm/string/predicate.hpp> // starts_with
7 #include <boost/optional.hpp>
8 
9 #include <vcsn/core/kind.hh>
10 #include <vcsn/labelset/fwd.hh>
13 #include <vcsn/labelset/letterset.hh> // for letterized_traits
14 #include <vcsn/misc/attributes.hh>
15 #include <vcsn/misc/functional.hh>
16 #include <vcsn/misc/irange.hh>
17 #include <vcsn/misc/raise.hh>
18 
19 namespace vcsn
20 {
22  template <typename GenSet>
23  class wordset: public detail::genset_labelset<GenSet>
24  {
25  public:
26  using genset_t = GenSet;
28  using self_t = wordset;
29  using genset_ptr = std::shared_ptr<const genset_t>;
30 
31  using letter_t = typename genset_t::letter_t;
32  using word_t = typename genset_t::word_t;
33 
34  using value_t = word_t;
35 
37 
38  wordset(const genset_ptr& gs)
39  : super_t{gs}
40  {}
41 
42  wordset(const genset_t& gs = {})
43  : wordset{std::make_shared<const genset_t>(gs)}
44  {}
45 
46  wordset(std::initializer_list<letter_t> letters)
47  : wordset(std::make_shared<const genset_t>(letters))
48  {}
49 
50  static symbol sname()
51  {
52  static auto res = symbol{"wordset<" + super_t::sname() + '>'};
53  return res;
54  }
55 
57  static wordset make(std::istream& is)
58  {
59  // name: wordset<char_letters(abc)>.
60  // ^^^^^^^ ^^^^^^^^^^^^^^^^^
61  // kind genset
62  eat(is, "wordset<");
63  auto gs = genset_t::make(is);
64  eat(is, '>');
65  return gs;
66  }
67 
71  bool open(bool o) const
72  {
73  return this->genset()->open(o);
74  }
75 
76  static constexpr bool is_free()
77  {
78  return false;
79  }
80 
82  template <typename... Args>
83  value_t value(Args&&... args) const
84  {
85  return value_t{std::forward<Args>(args)...};
86  }
87 
89  word_t word(const value_t& v) const
90  {
91  return v;
92  }
93 
95  static word_t
97  {
98  return v;
99  }
100 
103  static word_t
105  {
106  return v;
107  }
108 
110  static bool
111  equal(const value_t& l, const value_t& r)
112  {
113  return l == r;
114  }
115 
117  static bool less(const letter_t& l, const letter_t& r)
118  {
119  return genset_t::less(l, r);
120  }
121 
123  static bool less(const value_t& l, const value_t& r)
124  {
125  // Be sure to use genset::less().
126  auto s1 = size(l);
127  auto s2 = size(r);
128  if (s1 < s2)
129  return true;
130  else if (s2 < s1)
131  return false;
132  else
133  return genset_t::less(l, r);
134  }
135 
136  static value_t
138  {
139  return genset_t::template special<value_t>();
140  }
141 
142  static bool
144  {
145  return v == special();
146  }
147 
148  bool
149  is_valid(const value_t& v) const
150  {
151  for (auto l: v)
152  if (!this->has(l))
153  return false;
154  return true;
155  }
156 
157  static constexpr bool
159  {
160  return false;
161  }
162 
163  static constexpr bool
165  {
166  return true;
167  }
168 
169  static constexpr bool
171  {
172  return false;
173  }
174 
175  static value_t
176  one()
177  {
178  return genset_t::empty_word();
179  }
180 
181  static bool
182  is_one(const value_t& l) ATTRIBUTE_PURE
183  {
184  return genset_t::is_empty_word(l);
185  }
186 
187  static size_t size(const value_t& v)
188  {
189  // Not v.length(), because word_t can actually be a vector
190  // (e.g., with string_letters).
191  return v.size();
192  }
193 
194  static size_t hash(const value_t& v)
195  {
196  return hash_value(v);
197  }
198 
199  value_t
200  conv(self_t, const value_t& v) const
201  {
202  return v;
203  }
204 
205  template <typename GenSet_>
206  value_t
208  typename letterset<GenSet_>::value_t v) const
209  {
210  if (ls.is_special(v))
211  return special();
212  else
213  {
214  auto res = value(v);
216  *this, ": conv: invalid label: ", str_escape(v));
217  return res;
218  }
219  }
220 
221  template <typename LabelSet_>
222  value_t
224  const typename nullableset<LabelSet_>::value_t& v) const
225  {
226  if (ls.is_one(v))
227  return one();
228  else
229  return conv(*ls.labelset(), ls.get_value(v));
230  }
231 
233  value_t
234  conv(std::istream& i, bool = true) const
235  {
236  return this->genset()->get_word(i);
237  }
238 
248  template <typename Fun>
249  void convs(std::istream& i, Fun fun) const
250  {
251  this->convs_(i, [this,fun](letter_t l) { fun(value(l)); });
252  }
253 
254  std::ostream&
255  print(const value_t& l, std::ostream& o = std::cout,
256  format fmt = {}) const
257  {
258  if (is_one(l))
259  o << (fmt == format::latex ? "\\varepsilon"
260  : fmt == format::utf8 ? "ε"
261  : "\\e");
262  else if (!is_special(l))
263  this->genset()->print(l, o, fmt);
264  return o;
265  }
266 
267  std::ostream&
268  print_set(std::ostream& o, format fmt = {}) const
269  {
270  switch (fmt.kind())
271  {
272  case format::latex:
273  this->genset()->print_set(o, fmt);
274  o << "^*";
275  break;
276  case format::sname:
277  o << "wordset<";
278  this->genset()->print_set(o, fmt);
279  o << '>';
280  break;
281  case format::text:
282  case format::utf8:
283  this->genset()->print_set(o, fmt);
284  o << '*';
285  break;
286  case format::raw:
287  assert(0);
288  break;
289  }
290  return o;
291  }
292 
294  static value_t lgcd(const value_t& w1, const value_t& w2)
295  {
296  return {w1.begin(), boost::mismatch(w1, w2).first};
297  }
298 
301  value_t ldivide(const value_t& w1, const value_t& w2) const
302  {
303  auto res = maybe_ldivide(w1, w2);
304  VCSN_REQUIRE(res,
305  *this, ": ldivide: invalid arguments: ",
306  to_string(*this, w1),
307  ", ", to_string(*this, w2));
308  return *res;
309  }
310 
311  boost::optional<value_t>
312  maybe_ldivide(const value_t& w1, const value_t& w2) const
313  {
314  using boost::algorithm::starts_with;
315  if (starts_with(w2, w1))
316  return value_t{begin(w2) + size(w1), end(w2)};
317  else
318  return boost::none;
319  }
320 
322  value_t& ldivide_here(const value_t& w1, value_t& w2) const
323  {
324  w2 = ldivide(w1, w2);
325  return w2;
326  }
327 
330  value_t rdivide(const value_t& w1, const value_t& w2) const
331  {
332  auto res = maybe_rdivide(w1, w2);
333  VCSN_REQUIRE(res,
334  *this, ": rdivide: invalid arguments: ",
335  to_string(*this, w1),
336  ", ", to_string(*this, w2));
337  return *res;
338  }
339 
340  boost::optional<value_t>
341  maybe_rdivide(const value_t& w1, const value_t& w2) const
342  {
343  using boost::algorithm::ends_with;
344  if (ends_with(w1, w2))
345  return value_t{begin(w1), end(w1) - size(w2)};
346  else
347  return boost::none;
348  }
349 
351  value_t& rdivide_here(value_t& w1, const value_t& w2) const
352  {
353  w1 = rdivide(w1, w2);
354  return w1;
355  }
356 
357  const value_t& conjunction(const value_t& l, const value_t& r) const
358  {
359  if (equal(l, r))
360  return l;
361  else
362  raise(*this,
363  ": conjunction: invalid operation (lhs and rhs are not equal): ",
364  to_string(*this, l), ", ", to_string(*this, r));
365  }
366  };
367 
368  namespace detail
369  {
371  template <typename GenSet>
372  struct letterized_traits<wordset<GenSet>>
373  {
374  static constexpr bool is_letterized = false;
375 
376  using labelset_t = nullableset<letterset<GenSet>>;
377 
378  static labelset_t labelset(const wordset<GenSet>& ls)
379  {
380  return {ls.genset()};
381  }
382  };
383 
385  template <typename GenSet>
386  struct nullableset_traits<wordset<GenSet>>
387  {
388  using type = wordset<GenSet>;
389  static type value(const wordset<GenSet>& ls)
390  {
391  return ls;
392  }
393  };
394 
395  template <typename GenSet>
396  struct law_traits<wordset<GenSet>>
397  {
398  using type = wordset<GenSet>;
399  static type value(const wordset<GenSet>& ls)
400  {
401  return ls;
402  }
403  };
404 
405  /*-------.
406  | Join. |
407  `-------*/
408 
410 #define DEFINE(Lhs, Rhs) \
411  template <typename GenSet> \
412  struct join_impl<Lhs, Rhs> \
413  { \
414  using type = Rhs; \
415  static type join(const Lhs& lhs, const Rhs& rhs) \
416  { \
417  return {set_union(*lhs.genset(), *rhs.genset())}; \
418  } \
419  }
420 
422  DEFINE(letterset<GenSet>, wordset<GenSet>);
423  DEFINE(nullableset<letterset<GenSet>>, wordset<GenSet>);
424  DEFINE(wordset<GenSet>, wordset<GenSet>);
425 #undef DEFINE
426  }
427 
429  // FIXME: Factor in genset_labelset?
430  template <typename GenSet>
431  wordset<GenSet>
432  meet(const wordset<GenSet>& lhs, const wordset<GenSet>& rhs)
433  {
434  return {set_intersection(*lhs.genset(), *rhs.genset())};
435  }
436 
437 
438  /*----------------.
439  | random_label. |
440  `----------------*/
441 
443  template <typename GenSet,
444  typename RandomGenerator = std::default_random_engine>
445  typename wordset<GenSet>::value_t
446  random_label(const wordset<GenSet>& ls,
447  RandomGenerator& gen = RandomGenerator())
448  {
449  require(!ls.generators().empty(),
450  "random_label: the alphabet needs at least 1 letter");
451  auto dis = std::uniform_int_distribution<>(0, 5);
452  auto res_label = ls.one();
453  auto pick = make_random_selector(gen);
454  for (auto _: detail::irange(dis(gen)))
455  res_label = ls.mul(res_label, ls.value(pick(ls.generators())));
456  return res_label;
457  }
458 }
STL namespace.
bool is_valid(const value_t &v) const
Definition: wordset.hh:149
static constexpr bool has_one()
Definition: wordset.hh:164
bool open(bool o) const
Whether unknown letters should be added, or rejected.
Definition: wordset.hh:71
char eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.cc:90
Print as a parsable type string.
Definition: format.hh:26
static constexpr bool is_free()
Definition: wordset.hh:76
std::ostream & print(const value_t &l, std::ostream &o=std::cout, format fmt={}) const
Definition: wordset.hh:255
return res
Definition: multiply.hh:398
static word_t letters_of_padded(const value_t &v, letter_t)
Prepare to iterate over the letters of v.
Definition: wordset.hh:104
value_t conv(self_t, const value_t &v) const
Definition: wordset.hh:200
Print for LaTeX.
Definition: format.hh:22
static bool equal(const value_t &l, const value_t &r)
Whether l == r.
Definition: wordset.hh:111
word_t word(const value_t &v) const
Convert to a word.
Definition: wordset.hh:89
typename genset_t::letter_t letter_t
static value_t special()
Definition: wordset.hh:137
void convs_(std::istream &i, Fun fun) const
Read and process a class of letters.
wordset(const genset_ptr &gs)
Definition: wordset.hh:38
wordset(std::initializer_list< letter_t > letters)
Definition: wordset.hh:46
An input/output format for valuesets.
Definition: format.hh:13
wordset(const genset_t &gs={})
Definition: wordset.hh:42
value_t conv(const letterset< GenSet_ > &ls, typename letterset< GenSet_ >::value_t v) const
Definition: wordset.hh:207
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
static bool is_one(const value_t &l) ATTRIBUTE_PURE
Definition: wordset.hh:182
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
static size_t size(const value_t &v)
Definition: wordset.hh:187
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
Definition: functional.hh:30
letter_t value_t
Definition: letterset.hh:33
static size_t hash(const value_t &v)
Definition: wordset.hh:194
static word_t letters_of(const value_t &v)
Prepare to iterate over the letters of v.
Definition: wordset.hh:96
Definition: a-star.hh:8
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
void convs(std::istream &i, Fun fun) const
Process a label class.
Definition: wordset.hh:249
This class has no modeling purpose, it only serves to factor code common to letterset and wordset...
static symbol sname()
Definition: wordset.hh:50
value_t conv(std::istream &i, bool=true) const
Read a word from this stream.
Definition: wordset.hh:234
value_t value(Args &&...args) const
Value constructor.
Definition: wordset.hh:83
Implementation of labels are nullables (letter or empty).
Definition: fwd.hh:14
typename helper_t::value_t value_t
Definition: nullableset.hh:167
word_t value_t
Definition: wordset.hh:34
value_t conv(const nullableset< LabelSet_ > &ls, const typename nullableset< LabelSet_ >::value_t &v) const
Definition: wordset.hh:223
std::shared_ptr< const genset_t > genset_ptr
static constexpr bool is_expressionset()
Definition: wordset.hh:158
std::ostream & str_escape(std::ostream &os, const std::string &str, const char *special=nullptr)
Output a string, escaping special characters.
Definition: escape.cc:51
ATTRIBUTE_PURE auto has(Args &&...args) const -> decltype(this->genset() -> has(std::forward< Args >(args)...))
static ATTRIBUTE_PURE bool is_one(value_t l)
Definition: nullableset.hh:247
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: wordset.hh:268
return v
Definition: multiply.hh:361
typename genset_t::word_t word_t
Definition: wordset.hh:32
Implementation of labels are letters.
Definition: fwd.hh:10
static wordset make(std::istream &is)
Build from the description in is.
Definition: wordset.hh:57
static value_t one()
Definition: wordset.hh:176
static bool less(const value_t &l, const value_t &r)
Whether l < r.
Definition: wordset.hh:123
const labelset_ptr labelset() const
Definition: nullableset.hh:293
static bool is_special(const value_t &v)
Definition: wordset.hh:143
Implementation of labels are words.
Definition: fwd.hh:31
static labelset_t::value_t get_value(const value_t &v)
The (inner) value when it (the outer value) is not one.
Definition: nullableset.hh:586
static bool less(const letter_t &l, const letter_t &r)
Whether l < r.
Definition: wordset.hh:117
static bool is_special(value_t v) ATTRIBUTE_PURE
Definition: letterset.hh:163
static constexpr bool is_letterized()
Definition: wordset.hh:170