Vcsn  2.4
Be Rational
labelset.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/optional.hpp>
4 #include <boost/range/algorithm/find.hpp>
5 #include <boost/range/algorithm/find_if.hpp>
6 #include <boost/range/algorithm/for_each.hpp>
7 #include <boost/range/algorithm_ext/is_sorted.hpp>
8 
9 #include <vcsn/ctx/context.hh>
10 #include <vcsn/ctx/traits.hh> // labelset_t_of
11 #include <vcsn/misc/algorithm.hh> // none_of
12 #include <vcsn/misc/functional.hh> // less
13 #include <vcsn/misc/random.hh>
14 #include <vcsn/misc/static-if.hh>
15 #include <vcsn/misc/type_traits.hh> // detect
16 
17 namespace vcsn
18 {
19  namespace detail
20  {
22  template <typename LabelSet>
24  = decltype(std::declval<LabelSet>().generators());
25 
27  template <typename LabelSet>
29 
30 
31  /*-----------.
32  | has_one. |
33  `-----------*/
34 
35  template <typename LabelSet>
36  using one_t = decltype(std::declval<LabelSet>().one());
37 
38  template <typename LabelSet>
40 
41 
42  /*-------------.
43  | label_one. |
44  `-------------*/
45 
46 #if defined __GNUC__ && !defined __clang__
47  // GCC can't figure out that this one does return, because of the template
48  // instanciation, where one of them doesn't return.
49 # pragma GCC diagnostic push
50 # pragma GCC diagnostic ignored "-Wsuggest-attribute=noreturn"
51 #endif
52 
54  template <typename LabelSet>
55  auto label_one(const LabelSet& ls)
56  -> typename LabelSet::value_t
57  {
58  return static_if<LabelSet::has_one()>
59  ([](const auto& ls) { return ls.one(); },
60  [](const auto& ls) -> typename LabelSet::value_t
61  {
62  raise(ls, ": does not feature a neutral");
63  })
64  (ls);
65  }
66 
67 #if defined __GNUC__ && !defined __clang__
68 # pragma GCC diagnostic pop
69 #endif
70 
71 
72  /*-------------------.
73  | make_letterized. |
74  `-------------------*/
75 
79  template <typename LabelSet>
81  {
82  static constexpr bool is_letterized = true;
83 
84  using labelset_t = LabelSet;
85  static labelset_t labelset(const labelset_t& ls)
86  {
87  return std::make_shared<labelset_t>(labelset_t{ls.genset()});
88  }
89  };
90 
91  template <typename LabelSet>
92  using letterized_t =
94 
95  template <typename LabelSet>
96  using is_letterized_t =
98 
99  template <typename LabelSet>
101  make_letterized(const LabelSet& ls)
102  {
104  }
105 
106 
107  /*---------------------------.
108  | make_letterized_context. |
109  `---------------------------*/
110 
111  template <typename Context>
112  using letterized_context =
115 
117  template <typename LabelSet, typename WeightSet>
120  {
121  return {make_letterized(*c.labelset()), *c.weightset()};
122  }
123 
124 
125  /*--------------------.
126  | make_nullableset. |
127  `--------------------*/
128 
137  template <typename LabelSet,
138  typename Enable = void>
140  {};
141 
143  template <typename LabelSet>
145 
147  template <typename LabelSet>
149  make_nullableset(const LabelSet& ls)
150  {
152  };
153 
154  /*----------------------------.
155  | make_nullableset_context. |
156  `----------------------------*/
157 
158  template <typename Ctx>
161 
163  template <typename LabelSet, typename WeightSet>
166  {
167  return {make_nullableset(*ctx.labelset()), *ctx.weightset()};
168  }
169 
170 
171  /*---------------.
172  | make_proper. |
173  `---------------*/
174 
182  template <typename LabelSet>
184  {
185  using type = LabelSet;
186  static type value(const LabelSet& ls)
187  {
188  return ls;
189  }
190  };
191 
193  template <typename LabelSet>
195 
197  template <typename LabelSet>
199  make_proper(const LabelSet& ls)
200  {
202  }
203 
204 
205  /*-----------------------.
206  | make_proper_context. |
207  `-----------------------*/
208 
209  template <typename Context>
210  using proper_context =
213 
215  template <typename LabelSet, typename WeightSet>
216  auto
219  {
220  return {make_proper(*ctx.labelset()), *ctx.weightset()};
221  }
222 
223 
224  /*---------------------.
225  | make_free_context. |
226  `---------------------*/
227 
228  template <typename Context>
229  using free_context =
232 
234  template <typename LabelSet, typename WeightSet>
237  {
238  return {make_proper(make_letterized(*c.labelset())), *c.weightset()};
239  }
240 
241 
242  /*---------------.
243  | make_wordset. |
244  `---------------*/
245 
249  template <typename ValueSet>
250  struct law_traits
251  {};
252 
254  template <typename LabelSet>
256 
258  template <typename LabelSet>
259  inline law_t<LabelSet>
260  make_wordset(const LabelSet& ls)
261  {
262  return law_traits<LabelSet>::value(ls);
263  };
264 
265  /*--------------------.
266  | make_word_context. |
267  `--------------------*/
268 
269  template <typename Ctx>
270  using word_context_t
271  = context<law_t<labelset_t_of<Ctx>>, weightset_t_of<Ctx>>;
272 
274  template <typename LabelSet, typename WeightSet>
277  {
278  return {make_wordset(*ctx.labelset()), *ctx.weightset()};
279  }
280 
281 
282  /*---------------------.
283  | print_label_class. |
284  `---------------------*/
285 
290  template <typename LabelSet>
291  std::ostream&
292  print_label_ranges_(const LabelSet& ls,
293  const std::vector<typename LabelSet::value_t>& letters,
294  const std::vector<typename LabelSet::value_t>& alphabet,
295  std::ostream& out,
296  format fmt)
297  {
298  for (auto it = std::begin(letters), letters_end = std::end(letters);
299  it != letters_end; ++it)
300  {
301  auto end = std::mismatch(it, letters_end,
302  boost::range::find(alphabet, *it),
303  alphabet.end()).first;
304  ls.print(*it, out, fmt);
305  // No range for two letters or less.
306  auto width = std::distance(it, end);
307  if (2 < width)
308  {
309  it += width - 1;
310  // Using `-` in LaTeX math mode means minus (wow, 4
311  // m-words in a row), which results in a long dash, and
312  // too much space around it.
313  out << (fmt == format::latex ? "\\textrm{-}" : "-");
314  ls.print(*it, out, fmt);
315  }
316  }
317  return out;
318  }
319 
324  template <typename LabelSet>
325  std::ostream&
326  print_label_class(const LabelSet& ls,
327  const std::vector<typename LabelSet::value_t>& letters,
328  std::ostream& out,
329  format fmt)
330  {
331  using letters_t = std::vector<typename LabelSet::value_t>;
332  // In alphabetical order.
333  auto alphabet = letters_t{};
334  for (auto l : ls.generators())
335  alphabet.emplace_back(ls.value(l));
336 
337  out << '[';
338  // If the letters are strictly increasing (hence using
339  // less_equal, not just less), and are many compared to the
340  // alphabet (say, at least two thirds), then we should probably
341  // use negated classes instead.
342  if (boost::is_sorted(letters, vcsn::less_equal<LabelSet>{})
343  && 2 * boost::distance(alphabet) < 3 * boost::distance(letters))
344  {
345  // FIXME: we can certainly do better and avoid the
346  // construction of this vector.
347  auto negated = letters_t{};
348  for (auto l: alphabet)
349  if (none_of_equal(letters, l))
350  negated.emplace_back(l);
351  out << (fmt == format::latex ? "\\hat{}" : "^");
352  print_label_ranges_(ls, negated, alphabet, out, fmt);
353  }
354  else
355  print_label_ranges_(ls, letters, alphabet, out, fmt);
356  out << ']';
357 
358  return out;
359  }
360 
361  template <typename LabelSet>
362  typename LabelSet::letters_t
363  conv_label_class_(const LabelSet& ls, std::istream& i);
364 
370  //
380  template <typename LabelSet, typename Fun>
381  void
382  conv_label_class_(const LabelSet& ls, std::istream& i, Fun fun)
383  {
384  using letter_t = typename LabelSet::letter_t;
385  using letters_t = typename LabelSet::letters_t;
386  if (i.peek() == '^')
387  {
388  i.ignore();
389  auto alphabet = letters_t{};
390  for (auto l : ls.generators())
391  alphabet.insert(l);
392  boost::for_each(set_difference(alphabet, conv_label_class_(ls, i)),
393  fun);
394  }
395  else
396  {
397  // The last letter we read, for intervals.
398  auto prev = boost::optional<letter_t>{};
399  while (i.peek() != EOF && i.peek() != ']')
400  if (i.peek() == '-')
401  {
402  i.ignore();
403  // Handle a range.
404  // FIXME: ls instead of ls.sname would be better.
405  require(prev,
406  ls.sname(), ": letter classes cannot begin with '-'");
407  require(i.peek() != ']',
408  ls.sname(), ": letter classes cannot finish with '-'");
409 
410  // [prev - l2].
411  letter_t l2 = ls.get_letter(i);
412  // Skip prev, which was already processed.
413  auto gens = ls.generators();
414  auto i = std::find(std::begin(gens), std::end(gens), *prev);
415  // FIXME: Cannot use std::next here, in the case of tuples.
416  if (i != std::end(gens))
417  ++i;
418  for (;
419  i != std::end(gens) && *i < l2;
420  ++i)
421  fun(*i);
422  // The last letter. Do not do this in the loop,
423  // we might overflow the capacity of char.
424  // Check validity, so that 'z-a' is empty.
425  if (*prev < l2)
426  fun(l2);
427 
428  prev = boost::none;
429  }
430  else
431  {
432  letter_t l = ls.get_letter(i);
433  fun(l);
434  prev = l;
435  }
436  }
437  }
438 
440  template <typename LabelSet>
441  typename LabelSet::letters_t
442  conv_label_class_(const LabelSet& ls, std::istream& i)
443  {
444  using letter_t = typename LabelSet::letter_t;
445  using letters_t = typename LabelSet::letters_t;
446 
447  letters_t res;
448  conv_label_class_(ls, i, [&res](letter_t l){ res.insert(l); });
449  return res;
450  }
451  }
452 
454  template <typename LabelSet,
455  typename RandomGenerator = std::default_random_engine>
456  typename LabelSet::value_t
457  random_label(const LabelSet& ls,
458  RandomGenerator& gen = RandomGenerator())
459  {
460  require(!ls.generators().empty(),
461  "random_label: the alphabet needs at least 1 letter");
462  // Pick a member of a container following a uniform distribution.
463  auto pick = make_random_selector(gen);
464  return ls.value(pick(ls.generators()));
465  }
466 }
context< nullableset_t< labelset_t_of< Ctx >>, weightset_t_of< Ctx >> nullableset_context_t
Definition: labelset.hh:160
typename nullableset_traits< LabelSet >::type nullableset_t
The smallest nullableset that includes LabelSet.
Definition: labelset.hh:144
free_context< context< LabelSet, WeightSet > > make_free_context(const context< LabelSet, WeightSet > &c)
The free context for c.
Definition: labelset.hh:236
context< proper_t< letterized_t< labelset_t_of< Context >>>, weightset_t_of< Context >> free_context
Definition: labelset.hh:231
return res
Definition: multiply.hh:398
Print for LaTeX.
Definition: format.hh:22
context< proper_t< labelset_t_of< Context >>, weightset_t_of< Context >> proper_context
Definition: labelset.hh:212
word_context_t< context< LabelSet, WeightSet > > make_word_context(const context< LabelSet, WeightSet > &ctx)
The wordset context of a context.
Definition: labelset.hh:276
A traits to compute the letterized context.
Definition: labelset.hh:80
An input/output format for valuesets.
Definition: format.hh:13
proper_t< LabelSet > make_proper(const LabelSet &ls)
The corresponding proper LabelSet.
Definition: labelset.hh:199
static type value(const LabelSet &ls)
Definition: labelset.hh:186
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
decltype(std::declval< LabelSet >().one()) one_t
Definition: labelset.hh:36
The smallest nullableset which includes LabelSet.
Definition: labelset.hh:139
const weightset_ptr & weightset() const
Definition: context.hh:100
Container set_difference(const Container &s1, const Container &s2)
The set of members of s1 that are not members of s2.
Definition: algorithm.hh:171
Definition: a-star.hh:8
Functor to compare Values of ValueSets.
Definition: functional.hh:89
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
random_selector< RandomGenerator > make_random_selector(RandomGenerator &g)
Definition: random.hh:102
From a labelset, its non-nullable labelset.
Definition: labelset.hh:183
typename law_traits< LabelSet >::type law_t
The smallest wordset that includes LabelSet.
Definition: labelset.hh:255
bool_constant< letterized_traits< LabelSet >::is_letterized > is_letterized_t
Definition: labelset.hh:97
The LAW from a LAL.
Definition: labelset.hh:250
auto label_one(const LabelSet &ls) -> typename LabelSet::value_t
Enjoy type inference.
Definition: labelset.hh:55
std::integral_constant< bool, B > bool_constant
Definition: type_traits.hh:12
const labelset_ptr & labelset() const
Definition: context.hh:95
typename letterized_traits< LabelSet >::labelset_t letterized_t
Definition: labelset.hh:93
static labelset_t labelset(const labelset_t &ls)
Definition: labelset.hh:85
context< letterized_t< labelset_t_of< Context >>, weightset_t_of< Context >> letterized_context
Definition: labelset.hh:114
letterized_context< context< LabelSet, WeightSet > > make_letterized_context(const context< LabelSet, WeightSet > &c)
The letterized context for c.
Definition: labelset.hh:119
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
context< law_t< labelset_t_of< Ctx >>, weightset_t_of< Ctx >> word_context_t
Definition: labelset.hh:271
nullableset_context_t< context< LabelSet, WeightSet > > make_nullableset_context(const context< LabelSet, WeightSet > &ctx)
The nullableset context of a context.
Definition: labelset.hh:165
bool none_of_equal(const Range &r, const Value &value)
Definition: algorithm.hh:148
LabelSet::letters_t conv_label_class_(const LabelSet &ls, std::istream &i)
Read a set of letters (hence, guaranteed in order, and unique).
Definition: labelset.hh:442
expressionset< Context >::value_t random_label(const expressionset< Context > &rs, RandomGenerator &gen=RandomGenerator())
Random label from expressionset: limited to a single label.
auto make_proper_context(const context< LabelSet, WeightSet > &ctx) -> proper_context< context< LabelSet, WeightSet >>
From a context, its non-nullable context.
Definition: labelset.hh:217
typename proper_traits< LabelSet >::type proper_t
The type of the corresponding proper LabelSet.
Definition: labelset.hh:194
std::ostream & print_label_ranges_(const LabelSet &ls, const std::vector< typename LabelSet::value_t > &letters, const std::vector< typename LabelSet::value_t > &alphabet, std::ostream &out, format fmt)
Print a set of labels with ranges.
Definition: labelset.hh:292
std::ostream & print_label_class(const LabelSet &ls, const std::vector< typename LabelSet::value_t > &letters, std::ostream &out, format fmt)
Print a set of labels (letterized) with classes.
Definition: labelset.hh:326
letterized_t< LabelSet > make_letterized(const LabelSet &ls)
Definition: labelset.hh:101
decltype(std::declval< LabelSet >().generators()) generators_mem_fn_t
The type of the LabelSet::generators() member function.
Definition: labelset.hh:24
static constexpr bool is_letterized
Definition: labelset.hh:82
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:260
nullableset_t< LabelSet > make_nullableset(const LabelSet &ls)
The nullableset of a labelset.
Definition: labelset.hh:149