Vcsn  2.3
Be Rational
wordset.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <memory>
4 #include <set>
5 
6 #include <boost/range/algorithm/mismatch.hpp>
7 #include <boost/algorithm/string/predicate.hpp> // starts_with
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/raise.hh>
17 
18 namespace vcsn
19 {
21  template <typename GenSet>
22  class wordset: public detail::genset_labelset<GenSet>
23  {
24  public:
25  using genset_t = GenSet;
27  using self_t = wordset;
28  using genset_ptr = std::shared_ptr<const genset_t>;
29 
30  using letter_t = typename genset_t::letter_t;
31  using word_t = typename genset_t::word_t;
32  using letters_t = std::set<letter_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  using boost::algorithm::starts_with;
304  VCSN_REQUIRE(starts_with(w2, w1),
305  *this, ": ldivide: invalid arguments: ", str_escape(w1),
306  ", ", str_escape(w2));
307  return {begin(w2) + size(w1), end(w2)};
308  }
309 
311  value_t& ldivide_here(const value_t& w1, value_t& w2) const
312  {
313  w2 = ldivide(w1, w2);
314  return w2;
315  }
316 
317  const value_t& conjunction(const value_t& l, const value_t& r) const
318  {
319  if (equal(l, r))
320  return l;
321  else
322  raise(*this,
323  ": conjunction: invalid operation (lhs and rhs are not equal): ",
324  to_string(*this, l), ", ", to_string(*this, r));
325  }
326  };
327 
328  namespace detail
329  {
331  template <typename GenSet>
332  struct letterized_traits<wordset<GenSet>>
333  {
334  static constexpr bool is_letterized = false;
335 
336  using labelset_t = nullableset<letterset<GenSet>>;
337 
338  static labelset_t labelset(const wordset<GenSet>& ls)
339  {
340  return {ls.genset()};
341  }
342  };
343 
345  template <typename GenSet>
346  struct nullableset_traits<wordset<GenSet>>
347  {
348  using type = wordset<GenSet>;
349  static type value(const wordset<GenSet>& ls)
350  {
351  return ls;
352  }
353  };
354 
355  template <typename GenSet>
356  struct law_traits<wordset<GenSet>>
357  {
358  using type = wordset<GenSet>;
359  static type value(const wordset<GenSet>& ls)
360  {
361  return ls;
362  }
363  };
364 
365  /*-------.
366  | Join. |
367  `-------*/
368 
370 #define DEFINE(Lhs, Rhs) \
371  template <typename GenSet> \
372  struct join_impl<Lhs, Rhs> \
373  { \
374  using type = Rhs; \
375  static type join(const Lhs& lhs, const Rhs& rhs) \
376  { \
377  return {set_union(*lhs.genset(), *rhs.genset())}; \
378  } \
379  }
380 
382  DEFINE(letterset<GenSet>, wordset<GenSet>);
383  DEFINE(nullableset<letterset<GenSet>>, wordset<GenSet>);
384  DEFINE(wordset<GenSet>, wordset<GenSet>);
385 #undef DEFINE
386  }
387 
389  // FIXME: Factor in genset_labelset?
390  template <typename GenSet>
391  wordset<GenSet>
392  meet(const wordset<GenSet>& lhs, const wordset<GenSet>& rhs)
393  {
394  return {set_intersection(*lhs.genset(), *rhs.genset())};
395  }
396 }
return v
Definition: multiply.hh:361
static ATTRIBUTE_PURE bool is_one(value_t l)
Definition: nullableset.hh:246
static size_t size(const value_t &v)
Definition: wordset.hh:187
static bool is_special(const value_t &v)
Definition: wordset.hh:143
wordset(const genset_t &gs={})
Definition: wordset.hh:42
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
STL namespace.
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:549
std::shared_ptr< const genset_t > genset_ptr
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
Implementation of labels are letters.
Definition: fwd.hh:10
static size_t hash(const value_t &v)
Definition: wordset.hh:194
typename helper_t::value_t value_t
Definition: nullableset.hh:166
static symbol sname()
Definition: wordset.hh:50
value_t value(Args &&...args) const
Value constructor.
Definition: wordset.hh:83
Print as a parsable type string.
Definition: format.hh:26
value_t conv(std::istream &i, bool=true) const
Read a word from this stream.
Definition: wordset.hh:234
void convs(std::istream &i, Fun fun) const
Process a label class.
Definition: wordset.hh:249
word_t word(const value_t &v) const
Convert to a word.
Definition: wordset.hh:89
bool open(bool o) const
Whether unknown letters should be added, or rejected.
Definition: wordset.hh:71
Implementation of labels are nullables (letter or empty).
Definition: fwd.hh:14
static bool is_one(const value_t &l) ATTRIBUTE_PURE
Definition: wordset.hh:182
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: wordset.hh:268
void convs_(std::istream &i, Fun fun) const
Read and process a class of letters.
std::ostream & print(const value_t &l, std::ostream &o=std::cout, format fmt={}) const
Definition: wordset.hh:255
typename genset_t::word_t word_t
Definition: wordset.hh:31
wordset(std::initializer_list< letter_t > letters)
Definition: wordset.hh:46
return res
Definition: multiply.hh:398
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
Definition: functional.hh:30
This class has no modeling purpose, it only serves to factor code common to letterset and wordset...
static constexpr bool is_free()
Definition: wordset.hh:76
typename genset_t::letters_t letters_t
letter_t value_t
Definition: letterset.hh:32
Definition: a-star.hh:8
static constexpr bool is_letterized()
Definition: wordset.hh:170
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
static constexpr bool is_expressionset()
Definition: wordset.hh:158
An input/output format for valuesets.
Definition: format.hh:13
ATTRIBUTE_PURE auto has(Args &&...args) const -> decltype(this->genset() -> has(std::forward< Args >(args)...))
static value_t one()
Definition: wordset.hh:176
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
static wordset make(std::istream &is)
Build from the description in is.
Definition: wordset.hh:57
Implementation of labels are words.
Definition: fwd.hh:31
typename genset_t::letter_t letter_t
static value_t special()
Definition: wordset.hh:137
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
static bool is_special(value_t v) ATTRIBUTE_PURE
Definition: letterset.hh:162
static bool equal(const value_t &l, const value_t &r)
Whether l == r.
Definition: wordset.hh:111
value_t conv(const letterset< GenSet_ > &ls, typename letterset< GenSet_ >::value_t v) const
Definition: wordset.hh:207
Print for LaTeX.
Definition: format.hh:22
static word_t letters_of_padded(const value_t &v, letter_t)
Prepare to iterate over the letters of v.
Definition: wordset.hh:104
static constexpr bool has_one()
Definition: wordset.hh:164
bool is_valid(const value_t &v) const
Definition: wordset.hh:149
const labelset_ptr labelset() const
Definition: nullableset.hh:292
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
static word_t letters_of(const value_t &v)
Prepare to iterate over the letters of v.
Definition: wordset.hh:96
wordset(const genset_ptr &gs)
Definition: wordset.hh:38
value_t conv(self_t, const value_t &v) const
Definition: wordset.hh:200
char eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.cc:90
static bool less(const value_t &l, const value_t &r)
Whether l < r.
Definition: wordset.hh:123
static bool less(const letter_t &l, const letter_t &r)
Whether l < r.
Definition: wordset.hh:117
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54