expressionset.hh

Go to the documentation of this file.

#pragma once

#include <set>
#include <string>

#include <vcsn/core/rat/expression.hh>
#include <vcsn/core/rat/identities.hh>
#include <vcsn/core/rat/printer.hh>
#include <vcsn/ctx/context.hh>
#include <vcsn/labelset/labelset.hh>
#include <vcsn/labelset/letterset.hh>
#include <vcsn/labelset/oneset.hh>
#include <vcsn/misc/raise.hh>
#include <vcsn/misc/star-status.hh>
#include <vcsn/misc/symbol.hh>
#include <vcsn/weightset/b.hh>
#include <vcsn/weightset/nmin.hh>
#include <vcsn/weightset/q.hh>
#include <vcsn/weightset/r.hh>
#include <vcsn/weightset/z.hh>
#include <vcsn/weightset/zmin.hh>

#include <vcsn/core/rat/project.hh>

namespace vcsn
{
  namespace rat
  {
  template <typename Context>
  class expressionset_impl
  {
  public:
    using self_t = expressionset<Context>;
    using context_t = Context;
    using labelset_t = labelset_t_of<context_t>;
    using weightset_t = weightset_t_of<context_t>;
    using kind_t = labels_are_expressions;
    using labelset_ptr = typename context_t::labelset_ptr;
    using weightset_ptr = typename context_t::weightset_ptr;
    using label_t = label_t_of<context_t>;
    using weight_t = typename weightset_t::value_t;
    using identities_t = rat::identities;
    using const_visitor = rat::const_visitor<context_t>;

  private:
    const self_t& self() const { return static_cast<const self_t&>(*this); }

  public:
    //
    // See http://stackoverflow.com/questions/15537023 to know why we
    // add the vcsn::rat:: part: GCC wants it, Clang does not care,
    // both are right.
#define DEFINE(Type)                                           \
    using Type ## _t = vcsn::rat::Type<context_t>
    DEFINE(add);
    DEFINE(atom);
    DEFINE(complement);
    DEFINE(compose);
    DEFINE(conjunction);
    DEFINE(infiltrate);
    DEFINE(inner);
    DEFINE(ldivide);
    DEFINE(leaf);
    DEFINE(lweight);
    DEFINE(name);
    DEFINE(node);
    DEFINE(one);
    DEFINE(mul);
    DEFINE(rweight);
    DEFINE(shuffle);
    DEFINE(star);
    DEFINE(transposition);
    DEFINE(tuple);
    DEFINE(zero);
#undef DEFINE

    using value_t = typename node_t::value_t;
    using type_t = typename node_t::type_t;
    using values_t = typename node_t::values_t;

    template <type_t Type>
    using unary_t = unary<Type, context_t>;
    template <type_t Type>
    using variadic_t = variadic<Type, context_t>;

    using word_t = value_t;
    using letter_t = value_t;

    static symbol sname();
    static self_t make(std::istream& is);

    expressionset_impl(const context_t& ctx, identities_t ids = {});

    bool open(bool o) const;

    const context_t& context() const;

    identities_t identities() const;

    const labelset_ptr& labelset() const;
    const weightset_ptr& weightset() const;

    static value_t special()
    {
      return atom(labelset_t::special());
    }

    static bool is_special(const value_t& v)
    {
      return equal(special(), v);
    }

    bool is_letter(value_t) const
    {
      return false;
    }

    bool is_zero(const value_t& v) const ATTRIBUTE_PURE;

    static bool is_one(const value_t& v) ATTRIBUTE_PURE;

    bool is_universal(const value_t& v) const ATTRIBUTE_PURE;

    static constexpr bool is_letterized()
    {
      return false;
    }

    static constexpr bool is_commutative()
    {
      return false;
    }

    static constexpr bool is_idempotent()
    {
      // FIXME: well, the truth is that we are idempotent if the
      // weightset is, _and_ we apply ACI to addition.
      return weightset_t::is_idempotent();
    }

    static constexpr bool show_one()
    {
      return false;
    }

    static constexpr bool has_lightening_weights()
    {
      return weightset_t::has_lightening_weights();
    }

    static constexpr bool has_one()
    {
      return true;
    }

    static constexpr bool is_expressionset()
    {
      return true;
    }

    static constexpr bool is_free()
    {
      return false;
    }

    static constexpr star_status_t star_status()
    {
      return star_status_t::STARRABLE;
    }

    template <typename GenSet>
    auto conv(const letterset<GenSet>& ls,
                 typename letterset<GenSet>::value_t v) const -> value_t;
    auto conv(b, typename b::value_t v) const -> value_t;
    auto conv(const z& ws, typename z::value_t v) const -> value_t;
    auto conv(const q& ws, typename q::value_t v) const -> value_t;
    auto conv(const r& ws, typename r::value_t v) const -> value_t;
    auto conv(const nmin& ws, typename nmin::value_t v) const -> value_t;
    auto conv(const zmin& ws, typename zmin::value_t v) const -> value_t;
    template <typename Ctx2>
    auto conv(const expressionset<Ctx2>& ws,
                 typename expressionset<Ctx2>::value_t v) const -> value_t;

    static auto size(const value_t& v) -> size_t;

    static auto compare(const value_t& l, const value_t& r) -> int;

    static auto less(const value_t& l, const value_t& r) -> bool;

    static bool less_linear(const value_t& l, const value_t& r);

    static auto equal(const value_t& l, const value_t& r) -> bool;

    static auto hash(const value_t& v) -> size_t;

    static auto atom(const label_t& v) -> value_t;

    auto name(const value_t& v, symbol name) const -> value_t;

    // Concrete type implementation.
    static auto zero() -> value_t;
    static auto one() -> value_t;
    auto add(const value_t& l, const value_t& r) const -> value_t;
    auto mul(const value_t& l, const value_t& r) const -> value_t;

    auto concat(const value_t& l, const value_t& r) const -> value_t;

    auto compose(const value_t& l, const value_t& r) const -> value_t;

    auto conjunction(const value_t& l, const value_t& r) const -> value_t;

    auto infiltrate(const value_t& l, const value_t& r) const -> value_t;

    auto shuffle(const value_t& l, const value_t& r) const -> value_t;

    template <typename... Value>
    auto tuple(Value&&... v) const -> value_t;

    auto power(const value_t& e, unsigned n) const -> value_t;

    auto ldivide(const value_t& l, const value_t& r) const -> value_t;

    auto rdivide(const value_t& l, const value_t& r) const -> value_t;

    auto star(const value_t& e) const -> value_t;

    auto complement(const value_t& e) const -> value_t;
    auto transposition(const value_t& e) const -> value_t;
    auto rweight(const value_t& e, const weight_t& w) const -> value_t;
    auto lweight(const weight_t& w, const value_t& e) const -> value_t;
    auto transpose(const value_t& e) const -> value_t;

    auto word(label_t l) const -> word_t
    {
      return l;
    }

    template <typename... Args>
    auto letter_class(Args&&... chars) const -> value_t;

    auto conv(std::istream& is, bool = true) const -> value_t;

    auto conv(const self_t&, const value_t& v) const -> value_t;

    template <typename Fun>
    void convs(std::istream&, Fun) const
    {
      raise(*this, ": ranges not implemented");
    }

    auto print(const value_t& v,
               std::ostream& o = std::cout, format fmt = {}) const
      -> std::ostream&;

    auto print_set(std::ostream& o, format fmt = {}) const
      -> std::ostream&;

    template <unsigned Tape, typename Ctx = context_t>
    using project_t
      = expressionset<detail::project_context<Tape, Ctx>>;

    template <unsigned Tape>
    auto project() const
      -> project_t<Tape>
    {
      return vcsn::detail::project<Tape>(self());
    }

    template <size_t Tape>
    auto project(const value_t& v) const
      -> decltype(::vcsn::rat::project<Tape>(this->self(), v))
    {
      return ::vcsn::rat::project<Tape>(self(), v);
    }

    template <typename Sequence>
    struct as_tupleset_impl;

    template <size_t... I>
    struct as_tupleset_impl<detail::index_sequence<I...>>
    {
      using type = tupleset<project_t<I, context_t>...>;

      static type value(const self_t& self)
      {
        return {detail::project<I>(self)...};
      }
    };

    template <typename Ctx = context_t>
    using as_tupleset_t
      = typename as_tupleset_impl<typename labelset_t_of<Ctx>::indices_t::type>::type;

    template <typename Ctx = context_t>
    auto as_tupleset() const
      -> std::enable_if_t<Ctx::is_lat, as_tupleset_t<Ctx>>
    {
      return as_tupleset_impl<typename labelset_t_of<Ctx>::indices_t::type>::value(self());
    }

  private:
    auto add_(values_t&& vs) const -> value_t;

    auto add_linear_(const add_t& addends, const value_t& r) const -> value_t;
    auto add_linear_(const add_t& s1, const add_t& s2) const -> value_t;

    auto add_linear_(const value_t& l, const value_t& r) const -> value_t;

    static auto unwrap_possible_lweight_(const value_t& e) -> value_t;
    static type_t type_ignoring_lweight_(const value_t& e);
    static weight_t possibly_implicit_lweight_(const value_t& e);

    template <type_t Type>
    void gather_(values_t& res, const value_t& v) const;

    template <type_t Type>
    values_t gather_(const value_t& l, const value_t& r) const;

    auto concat_(const value_t& l, const value_t& r, std::true_type) const -> value_t;
    auto concat_(const value_t& l, const value_t& r, std::false_type) const -> value_t;

    template <typename LabelSet_, typename... Args>
    auto letter_class_(const Args&&... chars, std::true_type) const -> value_t;

    template <typename LabelSet_>
    value_t
    letter_class_(std::set<std::pair<typename LabelSet_::letter_t,
                                     typename LabelSet_::letter_t>> chars,
                  bool accept,
                  std::false_type) const;

    template <typename Dummy = void>
    struct tuple_of_label
    {
      static bool is_label(const tuple_t& v)
      {
        return is_label_(v, labelset_t::indices);
      }

      label_t as_label(const tuple_t& v) const
      {
        return as_label_(v, labelset_t::indices);
      }

      template <size_t... I>
      static bool is_label_(const tuple_t& v, detail::index_sequence<I...>)
      {
        for (auto b: {(std::get<I>(v.sub())->type() == type_t::atom
                       || (std::get<I>(v.sub())->type() == type_t::one
                           && labelset_t::template valueset_t<I>::has_one()))...})
          if (!b)
            return false;
        return true;
      }

      template <size_t... I>
      label_t as_label_(const tuple_t& v, detail::index_sequence<I...>) const
      {
        return label_t{as_label_<I>(v)...};
      }

      template <size_t I>
      typename project_t<I>::label_t as_label_(const tuple_t& v) const
      {
        if (std::get<I>(v.sub())->type() == type_t::one)
          return detail::label_one(rs_.labelset()->template set<I>());
        else
          return std::dynamic_pointer_cast<const typename project_t<I>::atom_t>
                 (std::get<I>(v.sub()))->value();
      }
      const self_t& rs_;
    };

  private:
    context_t ctx_;
    const identities_t ids_;
  };
  } // rat::

  namespace detail
  {
    template <typename Ctx>
    struct nullableset_traits<expressionset<Ctx>>
    {
      using type = expressionset<Ctx>;
      static type value(const type& ls)
      {
        return ls;
      }
    };

    template <typename Ctx>
    struct law_traits<expressionset<Ctx>>
    {
      using type = expressionset<Ctx>;
      static type value(const type& ls)
      {
        return ls;
      }
    };

    template <typename Ctx1, typename Ctx2>
    struct join_impl<expressionset<Ctx1>, expressionset<Ctx2>>
    {
      using type1 = expressionset<Ctx1>;
      using type2 = expressionset<Ctx2>;
      using type = expressionset<join_t<Ctx1, Ctx2>>;

      static type join(const type1& a, const type2& b)
      {
        return {vcsn::join(a.context(), b.context()),
                vcsn::join(a.identities(), b.identities())};
      }
    };

    // FIXME: what about the other labelsets?
    template <typename GenSet1, typename Ctx2>
    struct join_impl<letterset<GenSet1>, expressionset<Ctx2>>
    {
      using type1 = letterset<GenSet1>;
      using type2 = expressionset<Ctx2>;
      using context_t = context<join_t<letterset<GenSet1>, labelset_t_of<Ctx2>>,
                                weightset_t_of<Ctx2>>;
      using type = expressionset<context_t>;

      static type join(const type1& a, const type2& b)
      {
        return {context_t{vcsn::join(a, *b.labelset()), *b.weightset()},
                          b.identities()};
      }
    };

    // B.  FIXME: screams for refactoring!
    template <typename Context>
    struct join_impl<b, expressionset<Context>>
    {
      using type = expressionset<Context>;
      static type join(const b&, const type& rhs)
      {
        return rhs;
      }
    };

    template <typename W1, typename W2>
    struct join_impl_simple;

    template <typename WeightSet, typename Context>
    struct join_impl_simple<WeightSet, expressionset<Context>>
    {
      using type1 = WeightSet;
      using type2 = expressionset<Context>;
      using context_t = context<labelset_t_of<Context>,
                                join_t<WeightSet, weightset_t_of<Context>>>;
      using type = expressionset<context_t>;
      static type join(const type1& ws, const type2& rs)
      {
        return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
                rs.identities()};
      }
    };
#define JOIN_IMPL_SIMPLE(WS)                                    \
    template <typename Context>                                 \
    struct join_impl<WS, expressionset<Context>>                \
      : public join_impl_simple<WS, expressionset<Context>>     \
    {};


    JOIN_IMPL_SIMPLE(z);
    JOIN_IMPL_SIMPLE(q);
    JOIN_IMPL_SIMPLE(r);
    JOIN_IMPL_SIMPLE(zmin);

#undef JOIN_IMPL_SIMPLE

  }

  template <typename LabelSet, typename WeightSet>
  auto
  make_expressionset(const context<LabelSet, WeightSet>& ctx,
                     rat::identities ids = {})
    -> expressionset<context<LabelSet, WeightSet>>
  {
    return {ctx, ids};
  }

  template <typename Context>
  auto
  make_expressionset(const expressionset<Context>& rs,
                     rat::identities ids = {})
    -> expressionset<Context>
  {
    return {rs.context(), ids};
  }

  template <typename Context>
  struct is_multitape<expressionset<Context>>
    : is_multitape<Context>
  {};

  template <typename Ctx1, typename Ctx2>
  auto
  meet(const expressionset<Ctx1>& a, const expressionset<Ctx2>& b)
    -> expressionset<meet_t<Ctx1, Ctx2>>
  {
    return {meet(a.context(), b.context()),
            meet(a.identities(), b.identities())};
  }


  /*----------------.
  | random_label.   |
  `----------------*/

  template <typename Context,
            typename RandomGenerator = std::default_random_engine>
  typename expressionset<Context>::value_t
  random_label(const expressionset<Context>& rs,
               RandomGenerator& gen = RandomGenerator())
  {
    return rs.atom(random_label(*rs.labelset(), gen));
  }
} // namespace vcsn

#include <vcsn/core/rat/expressionset.hxx>

// This is ugly, yet I don't know how to address this circular
// dependency another way: expressionset.hxx uses is-valid-expression.hh,
// which, of course, also uses expressionset.hh.
//
// So let's have expressionset.hh first accept a forward declaration (via
// algos/fwd.hh), then provide here the needed definition.  Do not
// leave this inside the CPP guard.

#include <vcsn/algos/is-valid-expression.hh>