Vcsn  2.4
Be Rational
expressionset.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <set>
4 #include <string>
5 
9 #include <vcsn/ctx/context.hh>
12 #include <vcsn/labelset/oneset.hh>
13 #include <vcsn/misc/raise.hh>
14 #include <vcsn/misc/star-status.hh>
15 #include <vcsn/weightset/b.hh>
16 #include <vcsn/weightset/nmin.hh>
17 #include <vcsn/weightset/q.hh>
18 #include <vcsn/weightset/r.hh>
19 #include <vcsn/weightset/z.hh>
20 #include <vcsn/weightset/zmin.hh>
21 
22 #include <vcsn/core/rat/project.hh>
23 
24 namespace vcsn
25 {
26  namespace rat
27  {
30  template <typename Context>
32  {
33  public:
35  using context_t = Context;
39  using labelset_ptr = typename context_t::labelset_ptr;
40  using weightset_ptr = typename context_t::weightset_ptr;
42  using weight_t = typename weightset_t::value_t;
45 
46  private:
57  const self_t& self() const { return static_cast<const self_t&>(*this); }
58 
59  public:
61  //
62  // See http://stackoverflow.com/questions/15537023 to know why we
63  // add the vcsn::rat:: part: GCC wants it, Clang does not care,
64  // both are right.
65 #define DEFINE(Type) \
66  using Type ## _t = vcsn::rat::Type<context_t>
86 #undef DEFINE
87 
89  using value_t = typename node_t::value_t;
91  using type_t = typename node_t::type_t;
93  using values_t = typename node_t::values_t;
94 
95  template <type_t Type>
97  template <type_t Type>
99 
100  using word_t = value_t;
101  using letter_t = value_t;
102 
104  static symbol sname();
106  static self_t make(std::istream& is);
107 
112 
116  bool open(bool o) const;
117 
119  const context_t& context() const;
120 
122  identities_t identities() const;
123 
125  const labelset_ptr& labelset() const;
127  const weightset_ptr& weightset() const;
128 
130  static value_t special()
131  {
132  return atom(labelset_t::special());
133  }
134 
136  static bool is_special(const value_t& v)
137  {
138  return equal(special(), v);
139  }
140 
142  bool is_letter(value_t) const
143  {
144  return false;
145  }
146 
150  bool is_zero(const value_t& v) const ATTRIBUTE_PURE;
151 
155  static bool is_one(const value_t& v) ATTRIBUTE_PURE;
156 
158  bool is_universal(const value_t& v) const ATTRIBUTE_PURE;
159 
161  static constexpr bool is_letterized()
162  {
163  return false;
164  }
165 
167  static constexpr bool is_commutative()
168  {
169  return false;
170  }
171 
173  static constexpr bool is_idempotent()
174  {
175  // FIXME: well, the truth is that we are idempotent if the
176  // weightset is, _and_ we apply ACI to addition.
177  return weightset_t::is_idempotent();
178  }
179 
181  static constexpr bool show_one()
182  {
183  return false;
184  }
185 
187  static constexpr bool has_lightening_weights()
188  {
189  return weightset_t::has_lightening_weights();
190  }
191 
193  static constexpr bool has_one()
194  {
195  return true;
196  }
197 
199  static constexpr bool is_expressionset()
200  {
201  return true;
202  }
203 
205  static constexpr bool is_free()
206  {
207  return false;
208  }
209 
211  static constexpr star_status_t star_status()
212  {
214  }
215 
216  template <typename GenSet>
217  auto conv(const letterset<GenSet>& ls,
218  typename letterset<GenSet>::value_t v) const -> value_t;
219  auto conv(b, typename b::value_t v) const -> value_t;
220  auto conv(const z& ws, typename z::value_t v) const -> value_t;
221  auto conv(const q& ws, typename q::value_t v) const -> value_t;
222  auto conv(const r& ws, typename r::value_t v) const -> value_t;
223  auto conv(const nmin& ws, typename nmin::value_t v) const -> value_t;
224  auto conv(const zmin& ws, typename zmin::value_t v) const -> value_t;
225  template <typename Ctx2>
226  auto conv(const expressionset<Ctx2>& ws,
227  typename expressionset<Ctx2>::value_t v) const -> value_t;
228 
230  static size_t size(const value_t& v);
231 
233  static bool less(const value_t& l, const value_t& r);
234 
239  static bool less_linear(const value_t& l, const value_t& r);
240 
242  static bool equal(const value_t& l, const value_t& r);
243 
245  static size_t hash(const value_t& v);
246 
248  static auto atom(const label_t& v)
249  -> value_t;
250 
251  // Concrete type implementation.
252  auto zero() const -> value_t;
253  static auto one() -> value_t;
254  auto add(const value_t& l, const value_t& r) const -> value_t;
255  auto mul(const value_t& l, const value_t& r) const -> value_t;
256 
266  auto concat(const value_t& l, const value_t& r) const -> value_t;
267 
269  auto compose(const value_t& l, const value_t& r) const -> value_t;
270 
272  auto conjunction(const value_t& l, const value_t& r) const -> value_t;
273 
275  auto infiltrate(const value_t& l, const value_t& r) const -> value_t;
276 
278  auto shuffle(const value_t& l, const value_t& r) const -> value_t;
279 
281  template <typename... Value>
282  auto tuple(Value&&... v) const -> value_t;
283 
285  auto power(const value_t& e, unsigned n) const -> value_t;
286 
288  auto ldivide(const value_t& l, const value_t& r) const -> value_t;
289 
291  auto rdivide(const value_t& l, const value_t& r) const -> value_t;
292 
294  auto star(const value_t& e) const -> value_t;
295 
297  auto complement(const value_t& e) const -> value_t;
299  auto transposition(const value_t& e) const -> value_t;
301  auto rweight(const value_t& e, const weight_t& w) const -> value_t;
303  auto lweight(const weight_t& w, const value_t& e) const -> value_t;
305  auto transpose(const value_t& e) const -> value_t;
306 
308  auto word(label_t l) const -> word_t
309  {
310  return l;
311  }
312 
314  template <typename... Args>
315  auto letter_class(Args&&... chars) const -> value_t;
316 
318  auto conv(std::istream& is, bool = true) const -> value_t;
319 
321  auto conv(const self_t&, const value_t& v) const -> value_t;
322 
324  template <typename Fun>
325  void convs(std::istream&, Fun) const
326  {
327  raise(*this, ": ranges not implemented");
328  }
329 
330  auto print(const value_t& v,
331  std::ostream& o = std::cout, format fmt = {}) const
332  -> std::ostream&;
333 
335  auto print_set(std::ostream& o, format fmt = {}) const
336  -> std::ostream&;
337 
339  template <unsigned Tape, typename Ctx = context_t>
340  using project_t
342 
344  template <unsigned Tape>
345  auto project() const
346  -> project_t<Tape>
347  {
348  return vcsn::detail::project<Tape>(self());
349  }
350 
352  template <size_t Tape>
353  auto project(const value_t& v) const
354  -> decltype(::vcsn::rat::project<Tape>(this->self(), v))
355  {
356  return ::vcsn::rat::project<Tape>(self(), v);
357  }
358 
359  template <typename Sequence>
361 
362  template <size_t... I>
363  struct as_tupleset_impl<detail::index_sequence<I...>>
364  {
367 
368  static type value(const self_t& self)
369  {
370  return {detail::project<I>(self)...};
371  }
372  };
373 
375  template <typename Ctx = context_t>
376  using as_tupleset_t
378 
383  template <typename Ctx = context_t>
384  auto as_tupleset() const
385  -> std::enable_if_t<Ctx::is_lat, as_tupleset_t<Ctx>>
386  {
388  }
389 
390  private:
393  auto add_(values_t&& vs) const -> value_t;
394 
395  auto add_linear_(const add_t& addends, const value_t& r) const -> value_t;
396  auto add_linear_(const add_t& s1, const add_t& s2) const -> value_t;
397 
401  auto add_linear_(const value_t& l, const value_t& r) const -> value_t;
402 
405  static auto unwrap_possible_lweight_(const value_t& e) -> value_t;
408  static type_t type_ignoring_lweight_(const value_t& e);
411  static weight_t possibly_implicit_lweight_(const value_t& e);
412 
416  template <type_t Type>
417  void gather_(values_t& res, const value_t& v) const;
418 
423  template <type_t Type>
424  values_t gather_(const value_t& l, const value_t& r) const;
425 
427  auto concat_(const value_t& l, const value_t& r, std::true_type) const -> value_t;
429  auto concat_(const value_t& l, const value_t& r, std::false_type) const -> value_t;
430 
432  template <typename LabelSet_, typename... Args>
433  auto letter_class_(const Args&&... chars, std::true_type) const -> value_t;
434 
436  template <typename LabelSet_>
437  value_t
438  letter_class_(std::set<std::pair<typename LabelSet_::letter_t,
439  typename LabelSet_::letter_t>> chars,
440  bool accept,
441  std::false_type) const;
442 
444  template <typename Dummy = void>
446  {
448  static bool is_label(const tuple_t& v)
449  {
450  return is_label_(v, labelset_t::indices);
451  }
452 
455  label_t as_label(const tuple_t& v) const
456  {
457  return as_label_(v, labelset_t::indices);
458  }
459 
461  template <size_t... I>
463  {
464  for (auto b: {(std::get<I>(v.sub())->type() == type_t::atom
465  || (std::get<I>(v.sub())->type() == type_t::one
466  && labelset_t::template valueset_t<I>::has_one()))...})
467  if (!b)
468  return false;
469  return true;
470  }
471 
472  template <size_t... I>
474  {
475  return label_t{as_label_<I>(v)...};
476  }
477 
479  template <size_t I>
480  typename project_t<I>::label_t as_label_(const tuple_t& v) const
481  {
482  if (std::get<I>(v.sub())->type() == type_t::one)
483  return detail::label_one(rs_.labelset()->template set<I>());
484  else
485  return std::dynamic_pointer_cast<const typename project_t<I>::atom_t>
486  (std::get<I>(v.sub()))->value();
487  }
488  const self_t& rs_;
489  };
490 
491  private:
496  };
497  } // rat::
498 
499  namespace detail
500  {
502  template <typename Ctx>
504  {
506  static type value(const type& ls)
507  {
508  return ls;
509  }
510  };
511 
513  template <typename Ctx>
515  {
517  static type value(const type& ls)
518  {
519  return ls;
520  }
521  };
522 
524  template <typename Ctx1, typename Ctx2>
525  struct join_impl<expressionset<Ctx1>, expressionset<Ctx2>>
526  {
528 
529  static type join(const expressionset<Ctx1>& lhs,
530  const expressionset<Ctx2>& rhs)
531  {
532  return {vcsn::join(lhs.context(), rhs.context()),
533  vcsn::join(lhs.identities(), rhs.identities())};
534  }
535  };
536 
538  // FIXME: what about the other labelsets?
539  template <typename GenSet1, typename Ctx2>
540  struct join_impl<letterset<GenSet1>, expressionset<Ctx2>>
541  {
545 
546  static type join(const letterset<GenSet1>& a,
547  const expressionset<Ctx2>& b)
548  {
549  return {context_t{vcsn::join(a, *b.labelset()), *b.weightset()},
550  b.identities()};
551  }
552  };
553 
554  // B. FIXME: screams for refactoring!
555  template <typename Context>
556  struct join_impl<b, expressionset<Context>>
557  {
559  static type join(const b&, const expressionset<Context>& rhs)
560  {
561  return rhs;
562  }
563  };
564 
565  template <typename W1, typename W2>
567 
568  template <typename WeightSet, typename Context>
570  {
574  static type join(const WeightSet& ws, const expressionset<Context>& rs)
575  {
576  return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
577  rs.identities()};
578  }
579  };
580 #define JOIN_IMPL_SIMPLE(WS) \
581  template <typename Context> \
582  struct join_impl<WS, expressionset<Context>> \
583  : public join_impl_simple<WS, expressionset<Context>> \
584  {};
585 
586 
591 
592 #undef JOIN_IMPL_SIMPLE
593 
594  }
595 
597  template <typename LabelSet, typename WeightSet>
598  auto
600  rat::identities ids = {})
602  {
603  return {ctx, ids};
604  }
605 
607  template <typename Context>
608  auto
610  rat::identities ids = {})
611  -> expressionset<Context>
612  {
613  return {rs.context(), ids};
614  }
615 
617  template <typename Ctx1, typename Ctx2>
618  auto
621  {
622  return {meet(a.context(), b.context()),
623  meet(a.identities(), b.identities())};
624  }
625 
626 
627  /*----------------.
628  | random_label. |
629  `----------------*/
630 
632  template <typename Context,
633  typename RandomGenerator = std::default_random_engine>
636  RandomGenerator& gen = RandomGenerator())
637  {
638  return rs.atom(random_label(*rs.labelset(), gen));
639  }
640 } // namespace vcsn
641 
643 
644 // This is ugly, yet I don't know how to address this circular
645 // dependency another way: expressionset.hxx uses is-valid-expression.hh,
646 // which, of course, also uses expressionset.hh.
647 //
648 // So let's have expressionset.hh first accept a forward declaration (via
649 // algos/fwd.hh), then provide here the needed definition. Do not
650 // leave this inside the CPP guard.
651 
STL namespace.
auto concat_(const value_t &l, const value_t &r, std::true_type) const -> value_t
If labelset is wordset.
static auto atom(const label_t &v) -> value_t
Build a label.
#define JOIN_IMPL_SIMPLE(WS)
typename as_tupleset_impl< typename labelset_t_of< Ctx >::indices_t::type >::type as_tupleset_t
If we are multitape, our type as a tupleset.
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
labelset_t_of< context_t > labelset_t
static symbol sname()
Static description key.
static constexpr bool is_idempotent()
When used as WeightSet.
Implementation of nodes of tuple of rational expressions.
Definition: expression.hh:173
std::shared_ptr< const node_t > value_t
An expression usable with value semantics.
Definition: expression.hh:88
typename weightset_t::value_t weight_t
typename node_t::type_t type_t
Type tag for AST classes.
std::vector< value_t > values_t
Definition: expression.hh:89
static constexpr bool show_one()
When used as WeightSet.
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
auto rdivide(const value_t &l, const value_t &r) const -> value_t
Build a right division: l {/} r.
auto make_expressionset(const context< LabelSet, WeightSet > &ctx, rat::identities ids={}) -> expressionset< context< LabelSet, WeightSet >>
Shorthand to expressionset constructor.
static type join(const expressionset< Ctx1 > &lhs, const expressionset< Ctx2 > &rhs)
identities meet(identities i1, identities i2)
Definition: identities.cc:76
expressionset_impl(const context_t &ctx, identities_t ids={})
Constructor.
An inner node implementing a weight.
Definition: expression.hh:255
static constexpr bool has_one()
When used as WeightSet.
identities_t identities() const
Accessor to the identities set.
static bool is_one(const value_t &v) ATTRIBUTE_PURE
Whether v is the \\e.
const labelset_ptr & labelset() const
Accessor to the labelset.
const weightset_ptr & weightset() const
Accessor to the weightset.
always valid.
Definition: star-status.hh:17
An input/output format for valuesets.
Definition: format.hh:13
static constexpr star_status_t star_status()
When used as WeightSet.
rat::type_t type_t
The possible types of expressions.
Definition: expression.hh:26
static constexpr bool is_free()
When used as WeightSet.
decltype(join(std::declval< ValueSets >()...)) join_t
The type of the join of the ValueSets.
Definition: join.hh:78
static constexpr bool is_letterized()
When used as a labelset.
type_t
The possible types of expressions.
Definition: fwd.hh:39
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
static type join(const WeightSet &ws, const expressionset< Context > &rs)
label_t as_label_(const tuple_t &v, detail::index_sequence< I... >) const
static constexpr bool is_commutative()
When used as WeightSet.
auto word(label_t l) const -> word_t
Make a `word' out of an expression.
The smallest nullableset which includes LabelSet.
Definition: labelset.hh:139
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
#define DEFINE(Type)
Type of expressions.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
letter_t value_t
Definition: letterset.hh:33
static bool less(const value_t &l, const value_t &r)
Whether l < r.
auto zero() const -> value_t
context_t ctx_
The context of the expressions.
auto letter_class(Args &&...chars) const -> value_t
An expression matching one character amongst chars.
static value_t special()
When used as a LabelSet.
auto conv(const letterset< GenSet > &ls, typename letterset< GenSet >::value_t v) const -> value_t
typename node_t::values_t values_t
A list (vector) of expressions.
std::string type(const automaton &a)
The implementation type of a.
Definition: others.cc:239
auto transpose(const value_t &e) const -> value_t
The transposed of this rational expression.
static bool is_label(const tuple_t &v)
Are all the components labels?
Definition: a-star.hh:8
auto add_linear_(const add_t &addends, const value_t &r) const -> value_t
static bool is_label_(const tuple_t &v, detail::index_sequence< I... >)
Are all the components on I... labels?
void gather_(values_t &res, const value_t &v) const
Push v in res, applying associativity if possible.
A typed expression set.
typename context_t::weightset_ptr weightset_ptr
bool is_zero(const value_t &v) const ATTRIBUTE_PURE
Whether v is the \\z.
static type_t type_ignoring_lweight_(const value_t &e)
The type of e, or the type of its child if e is a lweight.
project_t< I >::label_t as_label_(const tuple_t &v) const
The expression on tape I is actually a label: get it.
A structure that implements the computation of join(V1, V2).
Definition: join.hh:18
bool open(bool o) const
Whether unknown letters should be added, or rejected.
The LAW from a LAL.
Definition: labelset.hh:250
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:252
static self_t make(std::istream &is)
Build from the description in is.
typename context_t::labelset_ptr labelset_ptr
weightset_t_of< context_t > weightset_t
typename node_t::value_t value_t
An expression (a shared pointer to a tree).
auto add_(values_t &&vs) const -> value_t
From a list of values, build a sum, taking care of the empty and singleton cases. ...
void convs(std::istream &, Fun) const
Read a range of expressions.
const context_t & context() const
Accessor to the context.
static type join(const letterset< GenSet1 > &a, const expressionset< Ctx2 > &b)
auto label_one(const LabelSet &ls) -> typename LabelSet::value_t
Enjoy type inference.
Definition: labelset.hh:55
label_t as_label(const tuple_t &v) const
All the components are (single-tape) labels: make this a multitape label.
static weight_t possibly_implicit_lweight_(const value_t &e)
The weight of e if it's an lweight, otherwise the weight one().
bool is_letter(value_t) const
When used as a LabelSet.
static size_t hash(const value_t &v)
Hash v.
static bool less_linear(const value_t &l, const value_t &r)
Whether l < r, ignoring lweight.
const identities_t ids_
The set of rewriting rules to apply.
An expressionset can implement several different sets of identities on expressions.
Definition: identities.hh:21
weightset_mixin< rat::expressionset_impl< Context >> expressionset
Definition: fwd.hh:205
auto concat(const value_t &l, const value_t &r) const -> value_t
Similar to mul, but in the case of LAW, merge the labels.
An inner node with multiple children.
Definition: expression.hh:118
return v
Definition: multiply.hh:361
auto print_set(std::ostream &o, format fmt={}) const -> std::ostream &
Format the description of this expressionset.
Turn a tuple of expressions that are labels into a multi-tape label.
Implementation of labels are letters.
Definition: fwd.hh:10
star_status_t
Definition: star-status.hh:5
The root from which to derive the final node types.
Definition: expression.hh:289
static size_t size(const value_t &v)
The size of v.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
static bool is_special(const value_t &v)
When used as a LabelSet.
auto print(const value_t &v, std::ostream &o=std::cout, format fmt={}) const -> std::ostream &
bool is_universal(const value_t &v) const ATTRIBUTE_PURE
Whether v is the 0{c}.
auto power(const value_t &e, unsigned n) const -> value_t
Add a power operator: e{n}.
auto join(const ValueSet &vs) -> ValueSet
The join of a single valueset.
Definition: join.hh:44
static auto unwrap_possible_lweight_(const value_t &e) -> value_t
If e is an lweight, then its child, otherwise e.
const values_t sub() const
Definition: expression.hh:210
auto letter_class_(const Args &&...chars, std::true_type) const -> value_t
If labelset is oneset.
expressionset< Context >::value_t random_label(const expressionset< Context > &rs, RandomGenerator &gen=RandomGenerator())
Random label from expressionset: limited to a single label.
static type join(const b &, const expressionset< Context > &rhs)
static constexpr bool has_lightening_weights()
When used as WeightSet.
An inner node.
Definition: expression.hh:101
expressionset< Context > self_t
label_t_of< context_t > label_t
auto as_tupleset() const -> std::enable_if_t< Ctx::is_lat, as_tupleset_t< Ctx >>
If we are multitape, ourself as a tupleset.
static bool equal(const value_t &l, const value_t &r)
Whether l == r.
The abstract parameterized, root for all rational expression types.
Definition: expression.hh:80
vcsn::rat::add< context_t > add_t
auto project(const value_t &v) const -> decltype(::vcsn::rat::project< Tape >(this->self(), v))
Project a multitape expression.
static constexpr bool is_expressionset()
When used as WeightSet.
expressionset< detail::project_context< Tape, Ctx >> project_t
The type of the expressionset for the Tape-th tape.
auto project() const -> project_t< Tape >
The expressionset for the Tape-th tape.