9 #include <boost/optional.hpp>
10 #include <boost/range/algorithm/equal.hpp>
11 #include <boost/range/algorithm/find_if.hpp>
12 #include <boost/range/algorithm/lexicographical_compare.hpp>
32 # pragma clang diagnostic push
33 # pragma clang diagnostic ignored "-Wunused-value"
35 template <
typename LabelSet>
36 auto label_is_zero(
const LabelSet& ls,
const typename LabelSet::value_t* l)
37 -> decltype(ls.is_zero(l), bool())
39 return ls.is_zero(*l);
43 # pragma clang diagnostic pop
46 template <
typename LabelSet>
50 template <typename LabelSet>
58 template <
typename WeightSet>
68 template <
typename Context, wet_kind_t Kind>
75 template <
typename Context, wet_kind_t Kind>
87 using label_t =
typename labelset_t::value_t;
110 const self_t&
self()
const {
return static_cast<const self_t&
>(*this); }
212 template <wet_kind_t WetType>
216 && std::is_same<weightset_t, b>::value),
219 for (
const auto& m:
r)
225 template <wet_kind_t WetType>
229 && std::is_same<weightset_t, b>::value,
239 return add_here_impl<value_t::kind>(l,
r);
264 raise(
sname(),
": sub_here: invalid arguments: ",
286 for (
const auto& rm: r)
306 template <wet_kind_t WetType>
313 for (
const auto& lm: l)
314 for (
const auto& rm:
r)
323 template <wet_kind_t WetType>
329 return l.set() &
r.set();
337 return mul_impl<value_t::kind>(l,
r);
346 for (
const auto& m: p)
364 for (
const auto& lm: l)
365 for (
const auto& rm: r)
378 for (
const auto& lm: l)
379 for (
const auto& rm: r)
392 for (
const auto& p: zip_maps<vcsn::as_tuple>(l, r))
412 return {{i->first,
weightset()->star(i->second)}};
425 for (
const auto& m: v)
435 for (
const auto& m: v)
447 for (
const auto& m: v)
467 for (
const auto& m: v)
477 for (
const auto& lhs: v)
489 for (
const auto& lhs: l)
499 raise(
sname(),
": rdiv: not implemented (",
515 for (
const auto& m: r)
525 raise(
sname(),
": ldiv: division by zero");
530 std::cerr <<
"ldiv(";
531 print(l, std::cerr) <<
", ";
532 print(r, std::cerr) <<
"\n";
538 std::cerr <<
"factor = ";
print(
factor, std::cerr) <<
"\n";
542 std::cerr <<
"res = ";
print(res, std::cerr) <<
"\n";
547 std::cerr <<
"rem = ";
print(remainder, std::cerr) <<
"\n";
551 std::cerr <<
"ldiv(";
552 print(l, std::cerr) <<
", ";
553 print(r, std::cerr) <<
") = ";
554 print(res, std::cerr) <<
" rem: ";
555 print(remainder, std::cerr) <<
"\n";
558 raise(
sname(),
": ldiv: not implemented (",
596 auto i = begin(lhs), i_end = end(lhs);
597 auto j = begin(rhs), j_end = end(rhs);
599 i != i_end && j != j_end
600 &&
labelset()->equal(i->first, j->first);
605 if (i != i_end || j != j_end)
615 template <
typename WeightSet,
typename Dummy =
void>
626 template <
typename Dummy>
633 for (
const auto& m: v)
642 template <
typename Ctx, wet_kind_t Knd,
typename Dummy>
650 for (
const auto& p: v)
699 template <
typename... Polys>
704 auto res = value_t{};
709 this->weightset()->mul(ms.second...));
711 std::forward<Polys>(vs)...);
724 for (
const auto& m: v)
759 template <wet_kind_t WetType>
769 template <wet_kind_t WetType>
776 return l.set() ==
r.set();
783 return equal_impl<value_t::kind>(l,
r);
808 return weightset_t::is_one(i->second);
827 return weightset_t::star_status();
840 template <
typename WS>
842 conv(
const WS& ws,
const typename WS::value_t&
v)
const
848 template <
typename C, wet_kind_t K>
853 const typename C::labelset_t& sls = *sps.labelset();
854 const typename C::weightset_t& sws = *sps.weightset();
858 for (
const auto& m: v)
879 template <wet_kind_t WetType>
886 return boost::range::lexicographical_compare(l,
r,
monomial_less);
889 template <wet_kind_t WetType>
896 return l.set() <
r.set();
903 return less_impl<value_t::kind>(l,
r);
911 for (
const auto& i: v)
929 template <wet_kind_t WetType>
937 for (
const auto& m: p)
942 template <wet_kind_t WetType>
955 return hash_impl<value_t::kind>(
v);
963 eat(is,
"polynomialset<");
964 auto ctx = Context::make(is);
974 o <<
"\\mathsf{Poly}[";
982 o <<
"polynomialset<";
996 boost::optional<label_t>
997 conv_label(std::istream& i,
bool weighted,
const char sep =
'+')
const
1000 assert(peek !=
'[');
1004 if (i.peek() ==
'z')
1018 if (peek == EOF || peek == sep || isspace(peek))
1032 sname(),
": conv: invalid monomial: ",
1034 " (did you mean \\e or \\z?)");
1066 boost::optional<monomial_t>
1069 #define SKIP_SPACES() \
1070 while (isspace(i.peek())) \
1078 bool weighted = i.peek() ==
langle;
1085 "\\z is invalid for monomials");
1099 conv(std::istream& i,
const char sep =
'+')
const
1102 #define SKIP_SPACES() \
1103 while (isspace(i.peek())) \
1110 bool weighted = i.peek() ==
langle;
1116 if (i.peek() ==
'[')
1121 else if (
auto l =
conv_label(i, weighted, sep))
1126 if (i.peek() == sep)
1142 static bool parens = getenv(
"VCSN_PARENS");
1161 const std::string& sep =
" + ")
const
1165 out << (latex ?
"\\emptyset" :
"\\z");
1167 print_<context_t>(
v, out, fmt,
1168 latex && sep ==
" + " ?
" \\oplus " : sep);
1178 static bool parens = getenv(
"VCSN_PARENS");
1182 weightset()->print(w, out, fmt.for_weights());
1192 const std::string& sep)
const
1195 for (
const auto& m: v)
1209 const std::string& sep)
const
1215 if (sep ==
" + " || v.size() <= 2)
1226 if (!std::all_of(std::next(first_letter), end(v),
1234 if (first_letter != begin(v))
1247 std::vector<label_t> letters;
1248 for (
const auto& m: v)
1259 template <
typename Ctx>
1264 const std::string& sep =
" + ")
const
1271 template <
typename Ctx>
1276 const std::string& sep =
" + ")
const
1302 return {
vcsn::join(ps1.context(), ps2.context())};
1315 return {*ps1.labelset(),
vcsn::join(*ps1.weightset(), ws2)};
static constexpr bool show_one()
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.
value_t mul(const value_t &l, const monomial_t &rhs) const
Right product by a monomial.
std::ostream & str_escape(std::ostream &os, const std::string &str)
Output a string, escaping special characters.
Container::value_type front(const Container &container)
The first member of this Container.
value_t complement(const value_t &v) const
Complement this polynomial.
ps_t::value_t operator()(const value_t &v) const
static symbol sname()
The static name.
static constexpr char rangle
Right marker for weight in concrete syntax.
auto factor(const Aut &aut) -> decltype(::vcsn::copy(aut))
format for_labels() const
A copy of this format, but to print labels.
value_t conv(const WS &ws, const typename WS::value_t &v) const
FIXME: use enable_if to prevent this from being instantiated when WS is a polynomialset.
value_t & add_here(value_t &l, const value_t &r) const
weightset_mixin< detail::r_impl > r
monomial_t determinize(value_t v) const
"Determinize" this polynomial: turn into a monomial.
value_t & set_weight(value_t &v, const label_t &l, const weight_t w) const
Set the monomial of l in v to weight w.
auto norm(const value_t &v) const -> weight_t
The norm: the weight with which we should divide a polynomial to normalize it.
std::ostream & print_set(std::ostream &o, format fmt={}) const
weightset_t_of< context_t > weightset_t
boost::optional< monomial_t > conv_monomial(std::istream &i, const char sep= '+') const
Read a monomial from a stream.
const weightset_ptr & weightset() const
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
void clear(value_t &v)
Set to zero.
A structure that implements the computation of join(V1, V2).
static ATTRIBUTE_PURE size_t hash(const monomial_t &m, size_t res=0)
auto join(const ValueSet &vs) -> ValueSet
The join of a single valueset.
std::istringstream is
The input stream: the specification to translate.
weight_t_of< context_t > weight_t
wet_of< context_t, Kind > value_t
vcsn::enable_if_t< labelset_t_of< Ctx >::is_letterized(), std::ostream & > print_(const value_t &v, std::ostream &out, format fmt={}, const std::string &sep=" + ") const
Print a non-null value for a letterized labelset (e.g., letterset or nullableset. ...
auto mul(const value_t &p, const label_t &l, const weight_t w) const -> value_t
The product of polynomials l and r.
polynomialset_impl(const context_t &ctx)
weight_t scalar_product(const value_t &l, const value_t &r) const
The sum of the weights of the common labels.
auto tuple(Polys &&...vs) const -> value_t
Build a tuple of polynomials: (e.E+f.F)|(g.G+h.H) => eg.
static ATTRIBUTE_PURE auto less_impl(const value_t &l, const value_t &r) -> enable_if_t< WetType==wet_kind_t::bitset, bool >
value_t sub(const value_t &l, const value_t &r) const
The subtraction of polynomials l and r.
static ATTRIBUTE_PURE auto less_impl(const value_t &l, const value_t &r) -> enable_if_t< WetType!=wet_kind_t::bitset, bool >
char eat(std::istream &is, char c)
Check lookahead character and advance.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
value_t & del_weight(value_t &v, const label_t &l) const
Remove the monomial of l in v.
value_t conv(std::istream &i, const char sep= '+') const
Read a polynomial from a stream.
typename std::enable_if< Cond, T >::type enable_if_t
static ATTRIBUTE_PURE auto hash_impl(const value_t &p) -> enable_if_t< WetType!=wet_kind_t::bitset, size_t >
value_t star(const value_t &v) const
The star of polynomial v.
labelset_t_of< context_t > labelset_t
z::value_t operator()(const value_t &v) const
weight_t conv_weight(std::istream &i) const
Read a weight, if there is one, bracketed.
label_t to_label(const value_t &v) const
Convert into a label.
std::ostream & print_without_classes_(const value_t &v, std::ostream &out, format fmt, const std::string &sep) const
Print a polynomial value without classes.
const weight_t get_weight(const value_t &v, const label_t &l) const ATTRIBUTE_PURE
static const monomial_t & monomial_one()
The unit monomial.
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
typename value_t::value_type monomial_t
A pair
static ATTRIBUTE_PURE size_t hash(const value_t &v)
static constexpr char langle
Left marker for weight in concrete syntax.
static type join(const polynomialset< Ctx1, Kind1 > &ps1, const polynomialset< Ctx2, Kind2 > &ps2)
void hash_combine(std::size_t &seed, const T &v)
value_t lmul_label(const label_t &lhs, const value_t &v) const
Left product by a label.
auto mul_impl(const value_t &l, const value_t &r) const -> enable_if_t< WetType!=wet_kind_t::bitset, value_t >
The product of polynomials l and r.
polynomialset_impl()=delete
static ATTRIBUTE_PURE bool equal(const value_t &l, const value_t &r)
static dyn::context ctx(const driver &d)
Get the context of the driver.
typename context_t::labelset_ptr labelset_ptr
value_t conv(const polynomialset< C, K > &sps, const typename polynomialset< C, K >::value_t &v) const
Convert from another polynomialset to type_t.
weight_t normalize_here(value_t &v) const
Normalize v in place: compute the LGCD of the weights, ldiv the monomials with that factor...
value_t conjunction(const value_t &l, const value_t &r) const
The conjunction of polynomials l and r.
static ATTRIBUTE_PURE auto equal_impl(const value_t &l, const value_t &r) -> enable_if_t< WetType==wet_kind_t::bitset, bool >
vcsn::enable_if_t<!labelset_t_of< Ctx >::is_letterized(), std::ostream & > print_(const value_t &v, std::ostream &out, format fmt={}, const std::string &sep=" + ") const
Print a non-null value for a non letterized labelset.
Provide a variadic mul on top of a binary mul(), and one().
value_t normalize(value_t res) const
Normalized v.
static self_t make(std::istream &is)
Build from the description in is.
static ATTRIBUTE_PURE auto equal_impl(const value_t &l, const value_t &r) -> enable_if_t< WetType!=wet_kind_t::bitset, bool >
typename labelset_t::value_t label_t
Polynomials over labels.
value_t & add_here(value_t &v, const monomial_t &m) const
v += m.
decltype(join(std::declval< ValueSets >()...)) join_t
The type of the join of the ValueSets.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
const context_t & context() const
static ATTRIBUTE_PURE auto hash_impl(const value_t &p) -> enable_if_t< WetType==wet_kind_t::bitset, size_t >
void require(bool b, Args &&...args)
If b is not verified, raise an error with args as message.
WeightSet::value_t operator()(const value_t &v) const
auto add_here_impl(value_t &l, const value_t &r) const -> enable_if_t<!(WetType==wet_kind_t::bitset &&std::is_same< weightset_t, b >::value), value_t & >
v += p, default case.
std::string to_string(direction d)
Conversion to string.
auto add_here_impl(value_t &l, const value_t &r) const -> enable_if_t< WetType==wet_kind_t::bitset &&std::is_same< weightset_t, b >::value, value_t & >
v += p, B and bitsets.
value_t ldiv(const value_t &l, const value_t &r) const
auto mul_impl(const value_t &l, const value_t &r) const -> enable_if_t< WetType==wet_kind_t::bitset, value_t >
The product of polynomials l and r.
auto mul(const value_t &l, const value_t &r) const -> value_t
The product of polynomials l and r.
static const value_t & one()
The unit polynomial.
static ATTRIBUTE_PURE bool monomial_less(const monomial_t &lhs, const monomial_t &rhs)
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
std::ostream & print(const value_t &v, std::ostream &out, format fmt={}, const std::string &sep=" + ") const
Print a value (a polynomial).
value_t mul(const monomial_t &lhs, const value_t &v) const
Left product by a monomial.
typename context_t::weightset_ptr weightset_ptr
const value_t & zero() const
vcsn::enable_if_t<!is_letterized_t< labelset_t_of< Aut > >{}, bool > is_letterized(const Aut &aut)
std::ostream & print_weight_(const weight_t w, std::ostream &out, format fmt) const
Print a weight.
value_t transpose(const value_t &v) const
Linear combination of labels: map labels to weights.
wet< label_t_of< Context >, weight_t_of< Context >, Kind, vcsn::less< labelset_t_of< Context >>, vcsn::hash< labelset_t_of< Context >>, vcsn::equal_to< labelset_t_of< Context >>> wet_of
The corresponding wet for a LabelSet -> WeightSet context.
std::ostream & print_with_classes_(const value_t &v, std::ostream &out, format fmt, const std::string &sep) const
Print a polynomial value with classes.
static type join(const polynomialset< Ctx1, Kind1 > &ps1, const WS2 &ws2)
In the general case, normalize by the first (non null) weight.
value_t lgcd(const value_t &lhs, const value_t &rhs) const
LGCD between two polynomials.
const labelset_ptr & labelset() const
value_t lmul(const weight_t w, const value_t &v) const
Left exterior product.
static ATTRIBUTE_PURE bool less(const value_t &l, const value_t &r)
value_t ldiv(const monomial_t &l, const value_t &r) const
Left division by a monomial.
value_t rdiv(const value_t &l, const value_t &r) const
value_t & new_weight(value_t &v, const label_t &l, const weight_t w) const
Set the monomial of l in v to weight k.
auto conv(const ValueSet &vs, const std::string &str, Args &&...args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
Parse str via vs.conv.
void weight_set(welement< Label, Weight > &m, const Weight &w)
value_t & sub_here(value_t &v, const monomial_t &m) const
v -= m.
static constexpr star_status_t star_status()
std::ostream & print(const monomial_t &m, std::ostream &out, format fmt={}) const
Print a monomial.
monomial_t mul(const monomial_t &l, const monomial_t &r) const
The product of monomials l and r.
static bool is_one(const value_t &v) ATTRIBUTE_PURE
Whether is the unit polynomial.
value_t add(const value_t &l, const value_t &r) const
The sum of polynomials l and r.
value_t rmul(const value_t &v, const weight_t w) const
Right exterior product.
value_t & add_here(value_t &v, const label_t &l, const weight_t k) const
v += l.
value_t & rdiv_here(value_t &v, const weight_t w) const
Right exterior division.
std::string bracketed(std::istream &i, char lbracket, char rbracket)
Extract the string which is here between lbracket and rbracket.
value_t & ldiv_here(const weight_t w, value_t &v) const
Left exterior division.
value_t infiltration(const value_t &l, const value_t &r) const
The infiltration of polynomials l and r.
void cross(Fun f)
Variadic Cartesian product of containers.
static value_t conv(self_t, const value_t &v)
Conversion from (this and) other weightsets.
constant< type_t::one, Context > one
static constexpr bool is_commutative()
value_t rmul_label(const value_t &v, const label_t &rhs) const
Right product.
static ATTRIBUTE_PURE bool monomial_equal(const monomial_t &lhs, const monomial_t &rhs)
bool is_zero(const value_t &v) const
monomial_t ldiv(const monomial_t &l, const monomial_t &r) const
auto label_is_zero(const LabelSet &ls, const typename LabelSet::value_t *l) -> decltype(ls.is_zero(l), bool())
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
boost::optional< label_t > conv_label(std::istream &i, bool weighted, const char sep= '+') const
Read a label, if there is one.