Vcsn  2.2
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/type_traits.hh> // detect
14 
15 namespace vcsn
16 {
17  namespace detail
18  {
20  template <typename LabelSet>
21  using generators_t = decltype(std::declval<LabelSet>().generators());
22 
24  template <typename LabelSet>
26 
27 
28  /*-----------.
29  | has_one. |
30  `-----------*/
31 
32  template <typename LabelSet>
33  using one_t = decltype(std::declval<LabelSet>().one());
34 
35  template <typename LabelSet>
37 
38 
39  /*-------------.
40  | label_one. |
41  `-------------*/
42 
44  template <typename LabelSet>
45  auto label_one()
46  -> std::enable_if_t<LabelSet::has_one(),
47  typename LabelSet::value_t>
48  {
49  return LabelSet::one();
50  }
51 
52  template <typename LabelSet>
53  ATTRIBUTE_NORETURN
54  auto label_one()
55  -> std::enable_if_t<!LabelSet::has_one(),
56  typename LabelSet::value_t>
57  {
58  raise(LabelSet::sname(), ": does not feature a neutral");
59  }
60 
61 #if defined __GNUC__ && !defined __clang__
62  // GCC can't figure out that this one does return, because of the template
63  // instanciation, where one of them doesn't return.
64 # pragma GCC diagnostic push
65 # pragma GCC diagnostic ignored "-Wsuggest-attribute=noreturn"
66 #endif
67 
69  template <typename LabelSet>
70  auto label_one(const LabelSet&)
71  -> typename LabelSet::value_t
72  {
73  return label_one<LabelSet>();
74  }
75 
76 #if defined __GNUC__ && !defined __clang__
77 # pragma GCC diagnostic pop
78 #endif
79 
80 
81  /*-------------------.
82  | make_letterized. |
83  `-------------------*/
84 
88  template <typename LabelSet>
90  {
91  static constexpr bool is_letterized = true;
92 
93  using labelset_t = LabelSet;
94  static labelset_t labelset(const labelset_t& ls)
95  {
96  return std::make_shared<labelset_t>(labelset_t{ls.genset()});
97  }
98  };
99 
100  template <typename LabelSet>
101  using letterized_t =
103 
104  template <typename LabelSet>
105  using is_letterized_t =
107 
108  template <typename LabelSet>
110  make_letterized(const LabelSet& ls)
111  {
113  }
114 
115 
116  /*---------------------------.
117  | make_letterized_context. |
118  `---------------------------*/
119 
120  template <typename Context>
121  using letterized_context =
124 
126  template <typename LabelSet, typename WeightSet>
129  {
130  return {make_letterized(*c.labelset()), *c.weightset()};
131  }
132 
133 
134  /*--------------------.
135  | make_nullableset. |
136  `--------------------*/
137 
146  template <typename LabelSet,
147  typename Enable = void>
149  {};
150 
152  template <typename LabelSet>
154 
156  template <typename LabelSet>
158  make_nullableset(const LabelSet& ls)
159  {
161  };
162 
163  /*----------------------------.
164  | make_nullableset_context. |
165  `----------------------------*/
166 
167  template <typename Ctx>
170 
172  template <typename LabelSet, typename WeightSet>
175  {
176  return {make_nullableset(*ctx.labelset()), *ctx.weightset()};
177  }
178 
179 
180  /*---------------.
181  | make_proper. |
182  `---------------*/
183 
191  template <typename LabelSet>
193  {
194  using type = LabelSet;
195  static type value(const LabelSet& ls)
196  {
197  return ls;
198  }
199  };
200 
202  template <typename LabelSet>
204 
206  template <typename LabelSet>
208  make_proper(const LabelSet& ls)
209  {
211  }
212 
213 
214  /*-----------------------.
215  | make_proper_context. |
216  `-----------------------*/
217 
218  template <typename Context>
219  using proper_context =
222 
224  template <typename LabelSet, typename WeightSet>
225  auto
228  {
229  return {make_proper(*ctx.labelset()), *ctx.weightset()};
230  }
231 
232 
233  /*---------------------.
234  | make_free_context. |
235  `---------------------*/
236 
237  template <typename Context>
238  using free_context =
241 
243  template <typename LabelSet, typename WeightSet>
246  {
247  return {make_proper(make_letterized(*c.labelset())), *c.weightset()};
248  }
249 
250 
251  /*---------------.
252  | make_wordset. |
253  `---------------*/
254 
258  template <typename ValueSet>
259  struct law_traits
260  {};
261 
263  template <typename LabelSet>
265 
267  template <typename LabelSet>
268  inline law_t<LabelSet>
269  make_wordset(const LabelSet& ls)
270  {
271  return law_traits<LabelSet>::value(ls);
272  };
273 
274  /*--------------------.
275  | make_word_context. |
276  `--------------------*/
277 
278  template <typename Ctx>
279  using word_context_t
280  = context<law_t<labelset_t_of<Ctx>>, weightset_t_of<Ctx>>;
281 
283  template <typename LabelSet, typename WeightSet>
286  {
287  return {make_wordset(*ctx.labelset()), *ctx.weightset()};
288  }
289 
290 
291  /*---------------------.
292  | print_label_class. |
293  `---------------------*/
294 
299  template <typename LabelSet>
300  std::ostream&
301  print_label_ranges_(const LabelSet& ls,
302  const std::vector<typename LabelSet::value_t>& letters,
303  const std::vector<typename LabelSet::value_t>& alphabet,
304  std::ostream& out,
305  format fmt)
306  {
307  for (auto it = std::begin(letters), letters_end = std::end(letters);
308  it != letters_end; ++it)
309  {
310  auto end = std::mismatch(it, letters_end,
311  boost::range::find(alphabet, *it),
312  alphabet.end()).first;
313  ls.print(*it, out, fmt);
314  // No range for two letters or less.
315  auto width = std::distance(it, end);
316  if (2 < width)
317  {
318  it += width - 1;
319  // Using `-` in LaTeX math mode means minus (wow, 4
320  // m-words in a row), which results in a long dash, and
321  // too much space around it.
322  out << (fmt == format::latex ? "\\textrm{-}" : "-");
323  ls.print(*it, out, fmt);
324  }
325  }
326  return out;
327  }
328 
333  template <typename LabelSet>
334  std::ostream&
335  print_label_class(const LabelSet& ls,
336  const std::vector<typename LabelSet::value_t>& letters,
337  std::ostream& out,
338  format fmt)
339  {
340  using letters_t = std::vector<typename LabelSet::value_t>;
341  // In alphabetical order.
342  auto alphabet = letters_t{};
343  for (auto l : ls.generators())
344  alphabet.emplace_back(ls.value(l));
345 
346  out << '[';
347  // If the letters are strictly increasing (hence using
348  // less_equal, not just less), and are many compared to the
349  // alphabet (say, at least two thirds), then we should probably
350  // use negated classes instead.
351  if (boost::is_sorted(letters, vcsn::less_equal<LabelSet>{})
352  && 2 * boost::distance(alphabet) < 3 * boost::distance(letters))
353  {
354  // FIXME: we can certainly do better and avoid the
355  // construction of this vector.
356  auto negated = letters_t{};
357  for (auto l: alphabet)
358  if (none_of_equal(letters, l))
359  negated.emplace_back(l);
360  out << (fmt == format::latex ? "\\hat{}" : "^");
361  print_label_ranges_(ls, negated, alphabet, out, fmt);
362  }
363  else
364  print_label_ranges_(ls, letters, alphabet, out, fmt);
365  out << ']';
366 
367  return out;
368  }
369 
370  template <typename LabelSet>
371  typename LabelSet::letters_t
372  conv_label_class_(const LabelSet& ls, std::istream& i);
373 
379  //
389  template <typename LabelSet, typename Fun>
390  void
391  conv_label_class_(const LabelSet& ls, std::istream& i, Fun fun)
392  {
393  using letter_t = typename LabelSet::letter_t;
394  using letters_t = typename LabelSet::letters_t;
395  if (i.peek() == '^')
396  {
397  i.ignore();
398  auto alphabet = letters_t{};
399  for (auto l : ls.generators())
400  alphabet.insert(l);
401  boost::for_each(set_difference(alphabet, conv_label_class_(ls, i)),
402  fun);
403  }
404  else
405  {
406  // The last letter we read, for intervals.
407  auto prev = boost::optional<letter_t>{};
408  while (i.peek() != EOF && i.peek() != ']')
409  if (i.peek() == '-')
410  {
411  i.ignore();
412  // Handle a range.
413  require(prev,
414  "letter classes cannot begin with '-'");
415  require(i.peek() != ']',
416  "letter classes cannot finish with '-'");
417 
418  // [prev - l2].
419  letter_t l2 = ls.get_letter(i);
420  // Skip prev, which was already processed.
421  auto gens = ls.generators();
422  auto i = boost::range::find(gens, *prev);
423  // FIXME: Cannot use std::next here, in the case of tuples.
424  if (i != std::end(gens))
425  ++i;
426  for (;
427  i != std::end(gens) && *i < l2;
428  ++i)
429  fun(*i);
430  // The last letter. Do not do this in the loop,
431  // we might overflow the capacity of char.
432  // Check validity, so that 'z-a' is empty.
433  if (*prev < l2)
434  fun(l2);
435 
436  prev = boost::none;
437  }
438  else
439  {
440  letter_t l = ls.get_letter(i);
441  fun(l);
442  prev = l;
443  }
444  }
445  }
446 
448  template <typename LabelSet>
449  typename LabelSet::letters_t
450  conv_label_class_(const LabelSet& ls, std::istream& i)
451  {
452  using letter_t = typename LabelSet::letter_t;
453  using letters_t = typename LabelSet::letters_t;
454 
455  letters_t res;
456  conv_label_class_(ls, i, [&res](letter_t l){ res.insert(l); });
457  return res;
458  }
459  }
460 }
context< letterized_t< labelset_t_of< Context >>, weightset_t_of< Context >> letterized_context
Definition: labelset.hh:123
std::integral_constant< bool, B > bool_constant
Definition: type_traits.hh:12
typename letterized_traits< LabelSet >::labelset_t letterized_t
Definition: labelset.hh:102
const weightset_ptr & weightset() const
Definition: context.hh:100
auto make_proper_context(const context< LabelSet, WeightSet > &ctx) -> proper_context< context< LabelSet, WeightSet >>
From a context, its non-nullable context.
Definition: labelset.hh:226
context< proper_t< letterized_t< labelset_t_of< Context >>>, weightset_t_of< Context >> free_context
Definition: labelset.hh:240
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
decltype(std::declval< LabelSet >().one()) one_t
Definition: labelset.hh:33
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
decltype(std::declval< LabelSet >().generators()) generators_t
A probe for the LabelSet::generators().
Definition: labelset.hh:21
A traits to compute the letterized context.
Definition: labelset.hh:89
Print for LaTeX.
Definition: format.hh:20
bool_constant< letterized_traits< LabelSet >::is_letterized > is_letterized_t
Definition: labelset.hh:106
context< law_t< labelset_t_of< Ctx >>, weightset_t_of< Ctx >> word_context_t
Definition: labelset.hh:280
context< proper_t< labelset_t_of< Context >>, weightset_t_of< Context >> proper_context
Definition: labelset.hh:221
static type value(const LabelSet &ls)
Definition: labelset.hh:195
An input/output format for valuesets.
Definition: format.hh:11
typename nullableset_traits< LabelSet >::type nullableset_t
The smallest nullableset that includes LabelSet.
Definition: labelset.hh:153
context< nullableset_t< labelset_t_of< Ctx >>, weightset_t_of< Ctx >> nullableset_context_t
Definition: labelset.hh:169
static constexpr bool is_letterized
Definition: labelset.hh:91
constant< type_t::one, Context > one
Definition: fwd.hh:111
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
word_context_t< context< LabelSet, WeightSet > > make_word_context(const context< LabelSet, WeightSet > &ctx)
The wordset context of a context.
Definition: labelset.hh:285
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:301
const labelset_ptr & labelset() const
Definition: context.hh:95
nullableset_context_t< context< LabelSet, WeightSet > > make_nullableset_context(const context< LabelSet, WeightSet > &ctx)
The nullableset context of a context.
Definition: labelset.hh:174
The LAW from a LAL.
Definition: labelset.hh:259
typename law_traits< LabelSet >::type law_t
The smallest wordset that includes LabelSet.
Definition: labelset.hh:264
auto label_one() -> std::enable_if_t< LabelSet::has_one(), typename LabelSet::value_t >
This LabelSet's one(), if supported.
Definition: labelset.hh:45
Functor to compare Values of ValueSets.
Definition: functional.hh:91
From a labelset, its non-nullable labelset.
Definition: labelset.hh:192
bool none_of_equal(const Range &r, const Value &value)
Definition: algorithm.hh:139
symbol sname()
Definition: name.hh:67
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:269
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
typename proper_traits< LabelSet >::type proper_t
The type of the corresponding proper LabelSet.
Definition: labelset.hh:203
Container set_difference(const Container &s1, const Container &s2)
The set of members of s1 that are not members of s2.
Definition: algorithm.hh:150
The smallest nullableset which includes LabelSet.
Definition: labelset.hh:148
proper_t< LabelSet > make_proper(const LabelSet &ls)
The corresponding proper LabelSet.
Definition: labelset.hh:208
letterized_t< LabelSet > make_letterized(const LabelSet &ls)
Definition: labelset.hh:110
static labelset_t labelset(const labelset_t &ls)
Definition: labelset.hh:94
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:335
free_context< context< LabelSet, WeightSet > > make_free_context(const context< LabelSet, WeightSet > &c)
The free context for c.
Definition: labelset.hh:245
nullableset_t< LabelSet > make_nullableset(const LabelSet &ls)
The nullableset of a labelset.
Definition: labelset.hh:158
letterized_context< context< LabelSet, WeightSet > > make_letterized_context(const context< LabelSet, WeightSet > &c)
The letterized context for c.
Definition: labelset.hh:128
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:450