Vcsn  2.3
Be Rational
setalpha.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <cassert>
4 #include <initializer_list>
5 #include <stdexcept>
6 
7 #include <boost/container/flat_set.hpp>
8 #include <boost/optional.hpp>
9 #include <boost/version.hpp>
10 
11 #include <vcsn/misc/escape.hh>
12 #include <vcsn/misc/format.hh>
13 #include <vcsn/misc/raise.hh>
14 #include <vcsn/misc/set.hh>
15 #include <vcsn/misc/stream.hh> // eat.
16 #include <vcsn/misc/symbol.hh>
17 #include <vcsn/misc/type_traits.hh>
18 
19 namespace vcsn
20 {
22  template <typename Key, typename Compare, typename Allocator>
23  ATTRIBUTE_PURE
24  bool
25  has(const boost::container::flat_set<Key, Compare, Allocator>& s,
26  const Key& e)
27  {
28  return s.find(e) != s.end();
29  }
30 
34  template <typename L>
35  class set_alphabet: public L
36  {
37  public:
38  using letter_t = typename L::letter_t;
39  using word_t = typename L::word_t;
40  using letters_t
41  = boost::container::flat_set<letter_t, vcsn::less<L, letter_t>>;
44 
45  static symbol sname()
46  {
47  static auto res = L::sname();
48  return res;
49  }
50 
51  static set_alphabet make(std::istream& is)
52  {
53  // name: char_letters(abc)
54  // ^^^^^^^^^^^^ ^^^
55  // letter_type gens
56  eat(is, sname());
57 
58  // The result.
60 
61  // This labelset might be open: no initial letter is given, they
62  // will be discovered afterwards.
63  if (is.peek() == '(')
64  {
65  is.ignore();
66  // Previously read character, for intervals. We don't
67  // immediately add the letters: on 'a-z' we would firsts add
68  // 'a', and then ask for the interval from 'a' to 'z', which
69  // would add 'a' twice uselessly.
70  //
71  // Rather, keep the 'a' in \a prev, and flush prev when needed.
72  boost::optional<letter_t> prev;
73  while (true)
74  switch (is.peek())
75  {
76  case EOF:
77  raise(sname(), ": make: invalid end-of-file");
78  break;
79 
80  case ')':
81  eat(is, ')');
82  goto done;
83 
84  case '-':
85  if (prev)
86  {
87  eat(is, '-');
88  res.add_range(*prev, L::get_letter(is));
89  prev = boost::none;
90  break;
91  }
92  else
93  goto insert;
94 
95  insert:
96  default:
97  {
98  if (prev)
99  res.add_letter(*prev);
100  prev = L::get_letter(is);
101  break;
102  }
103  }
104  done:
105  if (prev)
106  res.add_letter(*prev);
107  ;
108  }
109  else // is.peek() != '('
110  res.open_ = true;
111  return res;
112  }
113 
114  set_alphabet() = default;
115  set_alphabet(const set_alphabet&) = default;
116  set_alphabet(std::initializer_list<letter_t> l)
117 #if 105700 <= BOOST_VERSION
118  : alphabet_{l}
119 #else
120  : alphabet_{l.begin(), l.end()}
121 #endif
122  {}
124  : alphabet_{l}
125  {}
126 
130  bool open(bool o) const
131  {
132  std::swap(o, open_);
133  return o;
134  }
135 
137  set_alphabet&
139  {
140  VCSN_REQUIRE(l != this->template special<letter_t>(),
141  *this,
142  ": add_letter: the special letter is reserved: ",
143  str_escape(l));
144  alphabet_.insert(l);
145  return *this;
146  }
147 
150  template <typename Letter, typename Enable = void>
151  struct has_range: std::false_type {};
152 
153  template <typename Letter>
154  struct has_range<Letter,
155  decltype((++std::declval<Letter&>(), void()))>
156  : std::true_type
157  {};
158 
161  -> set_alphabet&
162  {
163  return add_range_<letter_t>(l1, l2);
164  }
165 
166  template <typename Letter>
167  auto add_range_(Letter l1, Letter l2)
168  -> std::enable_if_t<has_range<Letter>{}, set_alphabet&>
169  {
170  for (/* empty */; L::less(l1, l2); ++l1)
171  add_letter(l1);
172  // The last letter. Do not do this in the loop, we might
173  // overflow the capacity of char. Check validity, so that 'z-a'
174  // is empty.
175  if (L::equal(l1, l2))
176  add_letter(l1);
177  return *this;
178  }
179 
180  template <typename Letter>
181  auto add_range_(Letter, Letter)
182  -> std::enable_if_t<!has_range<Letter>{}, set_alphabet&>
183  {
184  raise(*this, ": does not support letter ranges");
185  }
186 
188  bool
189  has(letter_t l) const
190  {
191  if (open_)
192  {
193  // FIXME: OMG...
194  const_cast<set_alphabet&>(*this).add_letter(l);
195  return true;
196  }
197  else
199  }
200 
202  word_t
203  get_word(std::istream& i) const
204  {
205  require(!i.bad(), *this, ": conv: invalid stream");
206  // Either an empty word: "\e", or a sequence of non-separators.
207  if (i.good() && i.peek() == '\\')
208  {
209  i.ignore();
210  int c = i.peek();
211  if (c == 'e')
212  {
213  i.ignore();
214  return {};
215  }
216  else
217  i.unget();
218  }
219 
220  // Stop as soon as it might be a special character (such as
221  // delimiters in polynomials, or tuple separators).
222  //
223  // The empty word (i.e., an empty stream) is a valid
224  // representation of the mpty word. We want to be able to call
225  // `aut.eval("")`, instead of mandating `aut.eval("\e")`.
226  word_t res;
227  int c = i.peek();
228  while (i.good()
229  && (c = i.peek()) != EOF
230  && !isspace(c)
231  && c != '+'
232  && c != ','
233  && c != '|'
234  && c != '('
235  && c != ')')
236  {
237  letter_t l = L::get_letter(i, true);
238  VCSN_REQUIRE(has(l), *this, ": invalid letter: ", str_escape(l));
239  // FIXME: in-place mul or temporary vector to build the
240  // string.
241  res = this->mul(res, l);
242  }
243  return res;
244  }
245 
246  using iterator = typename letters_t::const_iterator;
247  using const_iterator = typename letters_t::const_iterator;
248 
250  {
251  return alphabet_.begin();
252  }
253 
255  {
256  return alphabet_.end();
257  }
258 
260  {
261  return alphabet_.begin();
262  }
263 
265  {
266  return alphabet_.end();
267  }
268 
270  bool empty() const
271  {
272  return alphabet_.empty();
273  }
274 
276  {
277  return alphabet_.find(l);
278  }
279 
280  std::ostream&
281  print_set(std::ostream& o, format fmt = {}) const
282  {
283  switch (fmt.kind())
284  {
285  case format::latex:
286  {
287  o << "\\{";
288  const char *sep = "";
289  for (letter_t l: alphabet_)
290  {
291  o << sep;
292  if (! this->is_letter(l))
293  o << "\\mathit{";
294  this->print(l, o, fmt);
295  if (! this->is_letter(l))
296  o << '}';
297  sep = ", ";
298  }
299  if (open_)
300  o << sep << "\\ldots";
301  o << "\\}";
302  }
303  break;
304 
305  case format::sname:
306  o << sname() << '(';
307  for (letter_t l: alphabet_)
308  this->print(l, o, format::sname);
309  // FIXME: Don't display openness here, as our "make()"
310  // parser is not ready for it.
311  o << ')';
312  break;
313 
314  case format::text:
315  case format::utf8:
316  o << '{';
317  for (letter_t l: alphabet_)
318  this->print(l, o, format::sname);
319  if (open_)
320  o << "...";
321  o << '}';
322  break;
323 
324  case format::raw:
325  assert(0);
326  break;
327  }
328  return o;
329  }
330 
332  friend set_alphabet
334  {
335  return {set_intersection(lhs.alphabet_, rhs.alphabet_)};
336  }
337 
339  friend set_alphabet
340  set_union(const set_alphabet& lhs, const set_alphabet& rhs)
341  {
342  return {set_union(lhs.alphabet_, rhs.alphabet_)};
343  }
344 
345  private:
346  // FIXME: OMG...
348  mutable bool open_ = false;
349  };
350 }
letters_t alphabet_
Definition: setalpha.hh:347
const_iterator cend() const
Definition: setalpha.hh:264
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
set_alphabet & add_letter(letter_t l)
Modify this by adding l, and return *this.
Definition: setalpha.hh:138
STL namespace.
static set_alphabet make(std::istream &is)
Definition: setalpha.hh:51
Whether the genset supports the range concept: whether we can use '++' on letters.
Definition: setalpha.hh:151
friend set_alphabet set_union(const set_alphabet &lhs, const set_alphabet &rhs)
Compute the union with another alphabet.
Definition: setalpha.hh:340
symbol sname()
Definition: name.hh:65
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
const_iterator end() const
Definition: setalpha.hh:254
A set of letters of type L.
Definition: setalpha.hh:35
set_alphabet(const letters_t &l)
Definition: setalpha.hh:123
Print as a parsable type string.
Definition: format.hh:26
const_iterator find(letter_t l) const
Definition: setalpha.hh:275
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
return res
Definition: multiply.hh:398
typename letters_t::const_iterator const_iterator
Definition: setalpha.hh:247
auto add_range_(Letter l1, Letter l2) -> std::enable_if_t< has_range< Letter >
Definition: setalpha.hh:167
const_iterator begin() const
Definition: setalpha.hh:249
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
std::ostream & print(const Aut &aut, std::ostream &out=std::cout, const std::string &fmt="default")
Definition: print.hh:74
Definition: a-star.hh:8
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
An input/output format for valuesets.
Definition: format.hh:13
auto add_range(letter_t l1, letter_t l2) -> set_alphabet &
Add a range of letters, if it is accepted by the labelset.
Definition: setalpha.hh:160
set_alphabet &bool has(letter_t l) const
Whether l is a letter.
Definition: setalpha.hh:189
typename L::word_t word_t
Definition: setalpha.hh:39
Print as is. For instance, don't try to escape labels.
Definition: format.hh:24
const_iterator cbegin() const
Definition: setalpha.hh:259
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
bool open(bool o) const
Whether unknown letters should be added, or rejected.
Definition: setalpha.hh:130
set_alphabet()=default
word_t get_word(std::istream &i) const
Extract and return the next word from i.
Definition: setalpha.hh:203
friend set_alphabet set_intersection(const set_alphabet &lhs, const set_alphabet &rhs)
Compute the intersection with another alphabet.
Definition: setalpha.hh:333
boost::container::flat_set< letter_t, vcsn::less< L, letter_t >> letters_t
Definition: setalpha.hh:41
typename L::letter_t letter_t
Definition: setalpha.hh:38
typename letters_t::const_iterator iterator
Definition: setalpha.hh:246
static symbol sname()
Definition: setalpha.hh:45
auto add_range_(Letter, Letter) -> std::enable_if_t<!has_range< Letter >
Definition: setalpha.hh:181
Print for LaTeX.
Definition: format.hh:22
bool empty() const
Whether this alphabet has no letters.
Definition: setalpha.hh:270
Print as plain (ASCII) text, escaped.
Definition: format.hh:28
char eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.cc:90
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: setalpha.hh:281
set_alphabet(std::initializer_list< letter_t > l)
Definition: setalpha.hh:116
letter_t value_type
The type of our values, when seen as a container.
Definition: setalpha.hh:43