Vcsn  2.2a
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>
12 #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);
215  VCSN_REQUIRE(is_valid(res),
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,
256  format fmt = {}) const
257  {
258  if (is_one(l))
259  o << (fmt == format::latex ? "\\varepsilon" : "\\e");
260  else if (!is_special(l))
261  this->genset()->print(l, o, fmt);
262  return o;
263  }
264 
265  std::ostream&
266  print_set(std::ostream& o, format fmt = {}) const
267  {
268  switch (fmt.kind())
269  {
270  case format::latex:
271  this->genset()->print_set(o, fmt);
272  o << "^*";
273  break;
274  case format::sname:
275  o << "wordset<";
276  this->genset()->print_set(o, fmt);
277  o << '>';
278  break;
279  case format::text:
280  case format::utf8:
281  this->genset()->print_set(o, fmt);
282  o << '*';
283  break;
284  case format::raw:
285  assert(0);
286  break;
287  }
288  return o;
289  }
290 
292  static value_t lgcd(const value_t& w1, const value_t& w2)
293  {
294  return {w1.begin(), boost::mismatch(w1, w2).first};
295  }
296 
299  static value_t ldiv(const value_t& w1, const value_t& w2)
300  {
301  using boost::algorithm::starts_with;
302  VCSN_REQUIRE(starts_with(w2, w1),
303  sname(), ": ldiv: invalid arguments: ", str_escape(w1),
304  ", ", str_escape(w2));
305  return {begin(w2) + size(w1), end(w2)};
306  }
307 
309  static value_t& ldiv_here(const value_t& w1, value_t& w2)
310  {
311  w2 = ldiv(w1, w2);
312  return w2;
313  }
314 
315  const value_t& conjunction(const value_t& l, const value_t& r) const
316  {
317  if (equal(l, r))
318  return l;
319  else
320  raise("conjunction: invalid operation (lhs and rhs are not equal)");
321  }
322  };
323 
324  namespace detail
325  {
327  template <typename GenSet>
328  struct letterized_traits<wordset<GenSet>>
329  {
330  static constexpr bool is_letterized = false;
331 
332  using labelset_t = nullableset<letterset<GenSet>>;
333 
334  static labelset_t labelset(const wordset<GenSet>& ls)
335  {
336  return {ls.genset()};
337  }
338  };
339 
341  template <typename GenSet>
342  struct nullableset_traits<wordset<GenSet>>
343  {
344  using type = wordset<GenSet>;
345  static type value(const wordset<GenSet>& ls)
346  {
347  return ls;
348  }
349  };
350 
351  template <typename GenSet>
352  struct law_traits<wordset<GenSet>>
353  {
354  using type = wordset<GenSet>;
355  static type value(const wordset<GenSet>& ls)
356  {
357  return ls;
358  }
359  };
360 
361  /*-------.
362  | Join. |
363  `-------*/
364 
366 #define DEFINE(Lhs, Rhs) \
367  template <typename GenSet> \
368  struct join_impl<Lhs, Rhs> \
369  { \
370  using type = Rhs; \
371  static type join(const Lhs& lhs, const Rhs& rhs) \
372  { \
373  return {set_union(*lhs.genset(), *rhs.genset())}; \
374  } \
375  }
376 
378  DEFINE(letterset<GenSet>, wordset<GenSet>);
379  DEFINE(nullableset<letterset<GenSet>>, wordset<GenSet>);
380  DEFINE(wordset<GenSet>, wordset<GenSet>);
381 #undef DEFINE
382  }
383 
385  // FIXME: Factor in genset_labelset?
386  template <typename GenSet>
387  wordset<GenSet>
388  meet(const wordset<GenSet>& lhs, const wordset<GenSet>& rhs)
389  {
390  return {set_intersection(*lhs.genset(), *rhs.genset())};
391  }
392 }
ATTRIBUTE_PURE auto has(Args &&...args) const -> decltype(this->genset() -> has(std::forward< Args >(args)...))
std::istringstream is
The input stream: the specification to translate.
Definition: translate.cc:380
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
Definition: functional.hh:66
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
static size_t hash(const value_t &v)
Definition: wordset.hh:194
bool open(bool o) const
Whether unknown letters should be added, or rejected.
Definition: wordset.hh:71
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
wordset(const genset_t &gs={})
Definition: wordset.hh:42
Implementation of labels are words.
Definition: fwd.hh:36
static bool is_special(value_t v) ATTRIBUTE_PURE
Definition: letterset.hh:162
static bool is_one(const value_t &l) ATTRIBUTE_PURE
Definition: wordset.hh:182
typename helper_t::value_t value_t
Definition: nullableset.hh:166
static bool is_special(const value_t &v)
Definition: wordset.hh:143
value_t value(Args &&...args) const
Value constructor.
Definition: wordset.hh:83
word_t word(const value_t &v) const
Convert to a word.
Definition: wordset.hh:89
void convs(std::istream &i, Fun fun) const
Process a label class.
Definition: wordset.hh:249
static constexpr bool is_free()
Definition: wordset.hh:76
Implementation of labels are nullables (letter or empty).
Definition: fwd.hh:15
static symbol sname()
Definition: wordset.hh:50
Print as a parsable type string.
Definition: format.hh:24
static value_t one()
Definition: wordset.hh:176
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:535
value_t conv(std::istream &i, bool=true) const
Read a word from this stream.
Definition: wordset.hh:234
Print for LaTeX.
Definition: format.hh:20
Implementation of labels are letters.
Definition: fwd.hh:11
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: wordset.hh:266
static constexpr bool is_letterized()
Definition: wordset.hh:170
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:89
wordset(std::initializer_list< letter_t > letters)
Definition: wordset.hh:46
typename genset_t::letter_t letter_t
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, format fmt={}) const
Definition: wordset.hh:255
static wordset make(std::istream &is)
Build from the description in is.
Definition: wordset.hh:57
typename genset_t::word_t word_t
Definition: wordset.hh:31
std::ostream & str_escape(std::ostream &os, const std::string &str, const char *special=nullptr)
Output a string, escaping special characters.
Definition: escape.cc:54
This class has no modeling purpose, it only serves to factor code common to letterset and wordset...
value_t conv(const nullableset< LabelSet_ > &ls, const typename nullableset< LabelSet_ >::value_t &v) const
Definition: wordset.hh:223
letter_t value_t
Definition: letterset.hh:32
typename genset_t::letters_t letters_t
static bool equal(const value_t &l, const value_t &r)
Whether l == r.
Definition: wordset.hh:111
STL namespace.
static ATTRIBUTE_PURE bool is_one(value_t l)
Definition: nullableset.hh:246
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
static constexpr bool is_expressionset()
Definition: wordset.hh:158
char eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.cc:37
static word_t letters_of(const value_t &v)
Prepare to iterate over the letters of v.
Definition: wordset.hh:96
static value_t special()
Definition: wordset.hh:137
static word_t letters_of_padded(const value_t &v, letter_t)
Prepare to iterate over the letters of v.
Definition: wordset.hh:104
const labelset_ptr labelset() const
Definition: nullableset.hh:292
word_t value_t
Definition: wordset.hh:34
value_t conv(self_t, const value_t &v) const
Definition: wordset.hh:200
static size_t size(const value_t &v)
Definition: wordset.hh:187
static bool less(const value_t &l, const value_t &r)
Whether l < r.
Definition: wordset.hh:123
value_t conv(const letterset< GenSet_ > &ls, typename letterset< GenSet_ >::value_t v) const
Definition: wordset.hh:207
bool is_valid(const value_t &v) const
Definition: wordset.hh:149
static bool less(const letter_t &l, const letter_t &r)
Whether l < r.
Definition: wordset.hh:117
static constexpr bool has_one()
Definition: wordset.hh:164
std::shared_ptr< const genset_t > genset_ptr
wordset(const genset_ptr &gs)
Definition: wordset.hh:38
An input/output format for valuesets.
Definition: format.hh:11
Definition: a-star.hh:8